Abstract
An increasing number of networked applications, like video conference and video-on-demand, benefit from knowledge about Internet path measures like available bandwidth. Server selection and placement of infrastructure nodes based on accurate information about network conditions help to improve the quality-of-service of these systems. Acquiring this knowledge usually requires fully-meshed ad-hoc measurements. These, however, introduce a large overhead and a possible delay in communication establishment. Thus, prediction-based approaches like Sequoia have been proposed, which treat path properties as a semimetric and embed them onto trees, leveraging labelling schemes to predict distances between hosts not measured before. In this paper, we identify asymmetry as a cause of serious distortion in these systems causing inaccurate prediction. We study the impact of asymmetric network conditions on the accuracy of existing tree-embedding approaches, and present direction-aware embedding, a novel scheme that separates upstream from downstream properties of hosts and significantly improves the prediction accuracy for highly asymmetric datasets. This is achieved by embedding nodes for each direction separately and constraining the distance calculation to inversely labelled nodes. We evaluate the effectiveness and trade-offs of our approach using synthetic as well as real-world datasets.
Chapter PDF
Similar content being viewed by others
References
Abraham, I., Balakrishnan, M., Kuhn, F., Malkhi, D., Ramasubramanian, V., Talwar, K.: Reconstructing approximate tree metrics. In: Proc. of the 26th Ann. ACM Symp. on Princ. of Distr. Comp., pp. 43–52 (August 2007)
Beaumont, O., Eyraud-Dubois, L., Won, Y.J.: Using the last-mile model as a distributed scheme for available bandwidth prediction. In: Proc. of the 17th Int. Conf. on Par. Proc., pp. 103–116 (2011)
Chun, B., Culler, D., Roscoe, T., Bavier, A., Peterson, L., Wawrzoniak, M., Bowman, M.: Planetlab: an overlay testbed for broad-coverage services. SIGCOMM Comput. Commun. Rev. 33(3), 3–12 (2003)
Dabek, F., Cox, R., Kaashoek, F., Morris, R.: Vivaldi: a decentralized network coordinate system. SIGCOMM Comput. Commun. Rev. 34(4), 15–26 (2004)
Donnet, B., Gueye, B., Kaafar, M.: A survey on network coordinates systems, design, and security. IEEE Comm. Surveys Tutorials 12(4), 488–503 (2010)
Dovrolis, C., Ramanathan, P., Moore, D.: Packet-dispersion techniques and a capacity-estimation methodology. Trans. on Netw. 12(6), 963–977 (2004)
Elser, B., Förschler, A., Fuhrmann, T.: Tuning vivaldi: Achieving increased accuracy and stability. In: Spyropoulos, T., Hummel, K.A. (eds.) IWSOS 2009. LNCS, vol. 5918, pp. 174–184. Springer, Heidelberg (2009)
Francis, P., Jamin, S., Jin, C., Jin, Y., Raz, D., Shavitt, Y., Zhang, L.: Idmaps: a global internet host distance estimation service. Trans. on Netw. 9(5), 525–540 (2001)
Haddow, T., Ho, S.W., Ledlie, J., Lumezanu, C., Draief, M., Pietzuch, P.: On the feasibility of bandwidth detouring. In: Spring, N., Riley, G.F. (eds.) PAM 2011. LNCS, vol. 6579, pp. 81–91. Springer, Heidelberg (2011)
Hu, N., Steenkiste, P.: Exploiting internet route sharing for large scale available bandwidth estimation. In: Proc. of the 5th ACM SIGCOMM Conf. on Internet Meas., p. 16 (2005)
Lakshminarayanan, K., Padmanabhan, V.N.: Some findings on the network performance of broadband hosts. In: Proc. of the 3rd ACM SIGCOMM Conf. on Internet Meas., pp. 45–50 (2003)
Liao, Y., Du, W., Geurts, P., Leduc, G.: Dmfsgd: A decentralized matrix factorization algorithm for network distance prediction. Trans. on Netw. PP(99), 1 (2012)
Liao, Y., Geurts, P., Leduc, G.: Network distance prediction based on decentralized matrix factorization. In: Proc. of the 9th IFIP TC 6 Int. Conf. on Netw., pp. 15–26 (2010)
Liu, S., Zhang-Shen, R., Jiang, W., Rexford, J., Chiang, M.: Performance bounds for peer-assisted live streaming. SIGMETRICS Perform. Eval. Rev. 36(1), 313–324 (2008)
Lumezanu, C., Baden, R., Levin, D., Spring, N., Bhattacharjee, B.: Symbiotic relationships in internet routing overlays. In: Proc. of the 6th USENIX Symp. on Netw. Sys. Des. and Impl., NSDI 2009, pp. 467–480 (2009)
Madhyastha, H.V., Isdal, T., Piatek, M., Dixon, C., Anderson, T., Krishnamurthy, A., Venkataramani, A.: iplane: an information plane for distributed services. In: Proc. of the 7th OSDI Conf., pp. 367–380 (2006)
Mao, Y., Saul, L., Smith, J.: Ides: An internet distance estimation service for large networks. J. on Sel. Areas in Comm. 24(12), 2273–2284 (2006)
Ng, T.S.E., Zhang, H.: Predicting internet network distance with coordinates-based approaches. In: Proc. IEEE INFOCOM, vol. 1, pp. 170–179 (2002)
Paxson, V.: End-to-end routing behavior in the internet. SIGCOMM Comput. Commun. Rev. 36(5), 41–56 (2006)
Peleg, D.: Proximity-preserving labeling schemes. J. Graph Theory 33(3), 167–176 (2000)
Ramasubramanian, V., Malkhi, D., Kuhn, F., Balakrishnan, M., Gupta, A., Akella, A.: On the treeness of internet latency and bandwidth. In: Proc. of the 11th Int. Joint Conf. on Meas. and Modeling of Comp. Sys., pp. 61–72 (2009)
Ribeiro, V., Riedi, R., Baraniuk, R., Navratil, J., Cottrell, L.: pathchirp: Efficient available bandwidth estimation for network paths. In: Passive and Active Meas. Workshop (2003)
Shavitt, Y., Tankel, T.: Hyperbolic embedding of internet graph for distance estimation and overlay construction. Trans. on Netw. 16(1), 25–36 (2008)
Song, S.: Decentralized pairwise bandwidth prediction, Unknown Date, http://www.cs.umd.edu/Grad/scholarlypapers/papers/SukhyunSong.pdf
Song, S., Keleher, P., Bhattacharjee, B., Sussman, A.: Decentralized, accurate, and low-cost network bandwidth prediction. In: Proc. IEEE INFOCOM, pp. 6–10 (April 2011)
Strauss, J., Katabi, D., Kaashoek, F.: A measurement study of available bandwidth estimation tools. In: Proc. of the 3rd ACM SIGCOMM Conf. on Internet Meas., pp. 39–44 (2003)
Xing, C., Chen, M., Yang, L.: Predicting available bandwidth of internet path with ultra metric space-based approaches. In: Proc. of IEEE GLOBECOM, pp. 1–6 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 IFIP International Federation for Information Processing
About this paper
Cite this paper
Schober, S., Brenner, S., Kapitza, R., Hauck, F.J. (2013). Bandwidth Prediction in the Face of Asymmetry. In: Dowling, J., Taïani, F. (eds) Distributed Applications and Interoperable Systems. DAIS 2013. Lecture Notes in Computer Science, vol 7891. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38541-4_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-38541-4_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38540-7
Online ISBN: 978-3-642-38541-4
eBook Packages: Computer ScienceComputer Science (R0)