More Web Proxy on the site http://driver.im/

Article

Using the last-mile model as a distributed scheme for available bandwidth prediction

Authors:

Olivier Beaumont,

Lionel Eyraud-Dubois,

Young J. WonAuthors Info & Claims

Euro-Par'11: Proceedings of the 17th international conference on Parallel processing - Volume Part I

Pages 103 - 116

Published: 29 August 2011 Publication History

Abstract

Several Network Coordinate Systems have been proposed to predict unknown network distances between a large number of Internet nodes by using only a small number of measurements. These systems focus on predicting latency, and they are not adapted to the prediction of available bandwidth. But end-to-end path available bandwidth is an important metric for the performance optimisation in many high throughput distributed applications, such as video streaming and file sharing networks. In this paper, we propose to perform available bandwidth prediction with the last-mile model, in which each node is characterised by its incoming and outgoing capacities. This model has been used in several theoretical works for distributed applications. We design decentralised heuristics to compute the capacities of each node so as to minimise the prediction error. We show that our algorithms can achieve a competitive accuracy even with asymmetric and erroneous end-to-end measurement datasets. A comparison with existing models (Vivaldi, Sequoia, PathGuru, DMF) is provided. Simulation results also show that our heuristics can provide good quality predictions even when using a very small number of measurements.

References

[1]

Beaumont, O., Bonichon, N., Eyraud-Dubois, L.: Scheduling divisibleworkloads on heterogeneous platforms under bounded multi-port model. In: IEEE IPDPS 2008, pp. 1-7 (April 2008).

[2]

Beaumont, O., Eyraud-Dubois, L., Agrawal, S.K.: Broadcasting on large scale heterogeneous platforms under the bounded multi-port model. In: IEEE IPDPS 2010, pp. 1-10 (April 2010).

[3]

Bonald, T., Massoulié, L., Mathieu, F., Perino, D., Twigg, A.: Epidemic live streaming: optimal performance trade-offs. ACM SIGMETRICS Perform. Eval. Rev. 36, 325-336 (2008).

Digital Library

[4]

Boufkhad, Y., Mathieu, F., de Montgolfier, F., Perino, D., Viennot, L.: An upload bandwidth threshold for peer-to-peer video-on-demand scalability. In: IEEE IPDPS 2009, pp. 1-10 (May 2009).

Digital Library

[5]

Chun, B., Culler, D., Roscoe, T., Bavier, A., Peterson, L., Wawrzoniak, M., Bowman, M.: Planetlab: an overlay testbed for broad-coverage services. ACM SIGCOMM Comput. Commun. Rev. 33, 3-12 (2003).

Digital Library

[6]

Dabek, F., Cox, R., Kaashoek, F., Morris, R.: Vivaldi: a decentralized network coordinate system. In: ACM SIGCOMM 2004, Portland, OR, USA, pp. 15-26 (September 2004).

Digital Library

[7]

Dinitz, M.: Online, dynamic, and distributed embeddings of approximate ultrametrics. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol. 5218, pp. 152-166. Springer, Heidelberg (2008).

Digital Library

[8]

Dischinger, M., Haeberlen, A., Gummadi, K.P., Saroiu, S.: Characterizing residential broadband networks. In: IMC 2007, San Diego, CA, USA, pp. 43-56 (October 2007).

Digital Library

[9]

Goldoni, E., Schivi, M.: End-to-end available bandwidth estimation tools, an experimental comparison. In: Ricciato, F., Mellia, M., Biersack, E. (eds.) TMA 2010. LNCS, vol. 6003, pp. 171-182. Springer, Heidelberg (2010).

Digital Library

[10]

Hu, N., Steenkiste, P.: Exploiting internet route sharing for large scale available bandwidth estimation. In: IMC 2005, pp. 16-16 (October 2005).

Digital Library

[11]

Ledlie, J., Gardner, P., Seltzer, M.: Network coordinates in the wild. In: USENIX NSDI 2007, pp. 299-311 (April 2007).

Digital Library

[12]

Li, N.H., Li, L.E., Mao, Z.M., Steenkiste, P., Wang, J.: A measurement study of internet bottlenecks. In: IEEE INFOCOM 2005 (March 2005).

[13]

Liao, Y., Geurts, P., Leduc, G.: Network distance prediction based on decentralized matrix factorization. In: IFIP NETWORKING 2010, pp. 15-26 (May 2010).

Digital Library

[14]

Liu, S., Zhang-Shen, R., Jiang, W., Rexford, J., Chiang, M.: Performance bounds for peer-assisted live streaming. ACM SIGMETRICS Perform. Eval. Rev. 36, 313- 324 (2008).

Digital Library

[15]

Mao, L.K.Y., Saul, Smith, J.M.: Ides: An internet distance estimation service for large networks. IEEE JSAC 24(12), 2273 (2006).

[16]

E., T.S., Ng, H.Z.: Predicting internet network distance with coordinates-based approaches. In: IEEE INFOCOM 2002, pp. 170-179 (June 2002).

[17]

Ramasubramanian, V., Malkhi, D., Kuhn, F., Balakrishnan, M., Gupta, A., Akella, A.: On the treeness of internet latency and bandwidth. In: ACM SIGMETRICS 2009, Seattle, WA, USA, pp. 61-72 (June 2009).

Digital Library

[18]

Suh, K., Diot, C., Kurose, J., Massoulie, L., Neumann, C., Towsley, D., Varvello, M.: Push-to-peer video-on-demand system: Design and evaluation. IEEE JSAC 25(9), 1706-1716 (2007).

Digital Library

[19]

Xing, C., Chen, M., Yan, L.: Predicting available bandwidth of internet path with ultra metric space-based approaches. In: IEEE GLOBECOM 2009 (December2009).

Digital Library

[20]

Yalagandula, P., Sharma, P., Banerjee, S., Basu, S., Lee, S.-J.: S3: a scalable sensing service for monitoring large networked systems. In: ACM SIGCOMM Workshop on Internet Network Management, Pisa, Italy, pp. 71-76 (September 2006).

Digital Library

Cited By

Bobelin LLegrand AMárquez DNavarro PQuinson MSuter FThiery C(2012)Scalable Multi-purpose Network Representation for Large Scale Distributed System SimulationProceedings of the 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (ccgrid 2012)10.1109/CCGrid.2012.31(220-227)Online publication date: 13-May-2012
https://dl.acm.org/doi/10.1109/CCGrid.2012.31

Recommendations

Predicting available bandwidth of internet path with ultra metric space-based approaches
GLOBECOM'09: Proceedings of the 28th IEEE conference on Global telecommunications

Internet path available bandwidth is an important metric for distributed application performance optimization. However, current network coordinate system causes large errors when being used to predict such performance metric. In this paper, based on ...
Feedback-assisted robust estimation of available bandwidth

The packet pair technique is a widely used method for estimating the available bandwidth of an end-to-end network path. We characterize the stochastic nature of the packet pair dispersion caused by bursty cross traffic and its adverse effect on ...
A Novel Available Bandwidth Measurement Method Based on the Pathload
IFITA '09: Proceedings of the 2009 International Forum on Information Technology and Applications - Volume 01

In this paper, we present a new available bandwidth measurement method with the characters of fast-convergence and high-accuracy, which is the improvement of Pathload. Pathload sends probe stream at specific rate and estimates the available bandwidth ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Euro-Par'11: Proceedings of the 17th international conference on Parallel processing - Volume Part I

August 2011

593 pages

ISBN:9783642233999

Editors:
Emmanuel Jeannot
INRIA, Talence Cedex, France
,
Raymond Namyst
Université de Bordeaux, INRIA, Talence Cedex, France
,
Jean Roman
Université de Bordeaux, INRIA, Talence Cedex, France

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 29 August 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bobelin LLegrand AMárquez DNavarro PQuinson MSuter FThiery C(2012)Scalable Multi-purpose Network Representation for Large Scale Distributed System SimulationProceedings of the 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (ccgrid 2012)10.1109/CCGrid.2012.31(220-227)Online publication date: 13-May-2012
https://dl.acm.org/doi/10.1109/CCGrid.2012.31

View Options

View options

Media

Figures

Other

Tables

View Table of Contents