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

Article

Exploiting internet route sharing for large scale available bandwidth estimation

Authors:

Peter SteenkisteAuthors Info & Claims

IMC '05: Proceedings of the 5th ACM SIGCOMM conference on Internet measurement

Page 16

Published: 19 October 2005 Publication History

Publisher Site Get Access

Abstract

Recent progress in active measurement techniques has made it possible to estimate end-to-end path available bandwidth. However, how to efficiently obtain available bandwidth information for the N² paths in a large N-node system remains an open problem. While researchers have developed coordinate-based models that allow any node to quickly and accurately estimate latency in a scalable fashion, no such models exist for available bandwidth. In this paper we introduce BRoute--a scalable available bandwidth estimation system that is based on a route sharing model. The characteristics of BRoute are that its overhead is linear with the number of end nodes in the system, and that it requires only limited cooperation among end nodes. BRoute leverages the fact that most Internet bottlenecks are on path edges, and that edges are shared by many different paths. It uses AS-level source and sink trees to characterize and infer path-edge sharing in a scalable fashion. In this paper, we describe the BRoute architecture and evaluate the performance of its components. Initial experiments show that BRoute can infer path edges with an accuracy of over 80%. In a small case study on Planetlab, 80% of the available bandwidth estimates obtained from BRoute are accurate within 50%.

References

[1]

{1} AS hierarchy data set. http://www.cs.berkeley.edu/ ~sagarwal/research/BGP-hierarchy/.

[2]

{2} Internet measurement infrastructure. http://www.caida. org/analysis/performance/measinfra.

[3]

{3} IP to AS number mapping data set. http://www.research. att.com/~jiawang/as_traceroute.

[4]

{4} Planetlab. https://www.planet-lab.org.

[5]

{5} RIPE RIS (Routing Information Service) Raw Data. http:// www.ripe.net/projects/ris/rawdata.html.

[6]

{6} Rocketfuel Data Sets. http://www.cs.washington.edu/ research/networking/rocketfuel.

[7]

{7} Route Server Wiki. http://www.bgp4.net/cgi-bin/ bgp4wiki.cgi?Route_Server_Wiki.

[8]

{8} University of Oregon Route Views Project. http://www. routeviews.org.

[9]

{9} G. D. Battista, M. Patrignani, and M. Pizzonia. Computing the types of the relationships between autonomous systems. In Proc. IEEE INFOCOM, April 2003.

[10]

{10} A. Broido and k. clafy. Internet topology: Connectivity of ip graphs. In Proc. SPIE International Symposium on Convergence of IT and Communication, 2000.

[11]

{11} R. Carter and M. Crovella. Measuring bottleneck link speed in packet-switched networks. Technical report, Boston University Computer Science Department, March 1996.

Digital Library

[12]

{12} F. Dabek, R. Cox, F. Kaashoek, and R. Morris. Vivaldi: a decentralized network coordinate system. In Proc. ACM SIGCOMM, August 2004.

Digital Library

[13]

{13} B. Donnet, P. Raoult, T. Friedman, and M. Crovella. Efficient algorithms for large-scale topology discovery. In Proc. ACM SIGMETRICS , June 2005.

Digital Library

[14]

{14} L. Gao. On inferring autonomous system relationships in the Internet. IEEE/ACM Trans. Networking, December 2001.

Digital Library

[15]

{15} N. Hu, L. Li, Z. Mao, P. Steenkiste, and J. Wang. Locating Internet bottlenecks: Algorithms, measurements, and implications. In Proc. ACM SIGCOMM, August 2004.

Digital Library

[16]

{16} N. Hu, O. Spatscheck, J. Wang, and P. Steenkiste. Optimizing network performance in replicated hosting. In The Tenth International Workshop on Web Caching and Content Distribution (WCW 2005), September 2005.

Digital Library

[17]

{17} N. Hu and P. Steenkiste. Evaluation and characterization of available bandwidth probing techniques. IEEE JSAC Special Issue in Internet and WWW Measurement, Mapping, and Modeling, 21(6), August 2003.

Digital Library

[18]

{18} M. Jain and C. Dovrolis. End-to-end available bandwidth: Measurement methodology, dynamics, and relation with TCP throughput. In Proc. ACM SIGCOMM, August 2002.

Digital Library

[19]

{19} Z. M. Mao, L. Qiu, J. Wang, and Y. Zhang. On AS-level path inference. In to appear in SIGMETRICS'05, June 2005.

Digital Library

[20]

{20} Z. M. Mao, J. Rexford, J. Wang, and R. Katz. Towards an Accurate AS-level Traceroute Tool. In Proc. ACM SIGCOMM, September 2003.

Digital Library

[21]

{21} B. Melander, M. Bjorkman, and P. Gunningberg. A new end-to-end probing and analysis method for estimating bandwidth bottlenecks. In Proc. IEEE GLOBECOM, November 2000.

[22]

{22} T. S. E. Ng and H. Zhang. Predicting Internet network distance with coordinates-based approaches. In Proc. IEEE INFOCOM, June 2002.

[23]

{23} V. Ribeiro, R. Riedi, R. Baraniuk, J. Navratil, and L. Cottrell. pathchirp: Efficient available bandwidth estimation for network paths. In Proc. PAM, April 2003.

[24]

{24} N. Spring, R. Mahajan, and D. Wetherall. Measuring ISP topologies with rocketfuel. In Proc. ACM SIGCOMM, August 2002.

Digital Library

[25]

{25} J. Strauss, D. Katabi, and F. Kaashoek. A measurement study of available bandwidth estimation tools. In Proc. ACM IMC, October 2003.

Digital Library

[26]

{26} L. Subramanian, S. Agarwal, J. Rexford, and R. H. Katz. Characterizing the Internet hierarchy from multiple vantage points. In Proc. IEEE INFOCOM, June 2002.

Cited By

Gosain DAgarwal AChakravarty SAcharya H(2017)The Devil's in The DetailsProceedings of the 33rd Annual Computer Security Applications Conference10.1145/3134600.3134608(577-589)Online publication date: 4-Dec-2017
https://dl.acm.org/doi/10.1145/3134600.3134608
Sun YJiang JSekar VZhang HLin FWang NKatz-Bassett EHeidemann JGodfrey BFeldmann A(2014)Using Video-Based Measurements to Generate a Real-Time Network Traffic MapProceedings of the 13th ACM Workshop on Hot Topics in Networks10.1145/2670518.2673870(1-7)Online publication date: 27-Oct-2014
https://dl.acm.org/doi/10.1145/2670518.2673870
Donnet BGueye BKaafar M(2012)Path similarity evaluation using Bloom filtersComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2011.11.00356:2(858-869)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1016/j.comnet.2011.11.003
Show More Cited By

Index Terms

Exploiting internet route sharing for large scale available bandwidth estimation

Recommendations

A measurement study of available bandwidth estimation tools
IMC '03: Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement

Available bandwidth estimation is useful for route selection in overlay networks, QoS verification, and traffic engineering. Recent years have seen a surge in interest in available bandwidth estimation. A few tools have been proposed and evaluated in ...
On the applicability of available bandwidth estimation techniques and tools

Available Bandwidth Estimation Techniques and Tools (ABETTs) have recently been envisioned as a supporting mechanism in areas such as compliance of service level agreements, network management, traffic engineering and real-time resource provisioning, ...
A traffic control system for IEEE 802.11 networks based on available bandwidth estimation

To support Quality of service (QoS)-sensitive applications like real-time video streaming in IEEE 802.11 networks, a MAC layer extension for QoS, IEEE 802.11e, has been recently ratified as a standard. This MAC layer solution, however, addresses only ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

IMC '05: Proceedings of the 5th ACM SIGCOMM conference on Internet measurement

October 2005

389 pages

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

USENIX Association

United States

Publication History

Published: 19 October 2005

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 277 of 1,083 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
176
Total Downloads

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

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gosain DAgarwal AChakravarty SAcharya H(2017)The Devil's in The DetailsProceedings of the 33rd Annual Computer Security Applications Conference10.1145/3134600.3134608(577-589)Online publication date: 4-Dec-2017
https://dl.acm.org/doi/10.1145/3134600.3134608
Sun YJiang JSekar VZhang HLin FWang NKatz-Bassett EHeidemann JGodfrey BFeldmann A(2014)Using Video-Based Measurements to Generate a Real-Time Network Traffic MapProceedings of the 13th ACM Workshop on Hot Topics in Networks10.1145/2670518.2673870(1-7)Online publication date: 27-Oct-2014
https://dl.acm.org/doi/10.1145/2670518.2673870
Donnet BGueye BKaafar M(2012)Path similarity evaluation using Bloom filtersComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2011.11.00356:2(858-869)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1016/j.comnet.2011.11.003
Beaumont OEyraud-Dubois LWon Y(2011)Using the last-mile model as a distributed scheme for available bandwidth predictionProceedings of the 17th international conference on Parallel processing - Volume Part I10.5555/2033345.2033358(103-116)Online publication date: 29-Aug-2011
https://dl.acm.org/doi/10.5555/2033345.2033358
Gangam SFahmy SLin BSinha PXu J(2011)Mitigating interference in a network measurement serviceProceedings of the Nineteenth International Workshop on Quality of Service10.5555/1996039.1996082(1-9)Online publication date: 6-Jun-2011
https://dl.acm.org/doi/10.5555/1996039.1996082
Thouin FCoates MRabbat M(2011)Large scale probabilistic available bandwidth estimationComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2011.02.01155:9(2065-2078)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1016/j.comnet.2011.02.011
Douceur JMickens JMoscibroda TPanigrahi D(2010)Collaborative measurements of upload speeds in P2P systemsProceedings of the 29th conference on Information communications10.5555/1833515.1833682(1082-1090)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.5555/1833515.1833682
Douceur JMickens JMoscibroda TPanigrahi DLiebeherr JVentre GBiersack EKeshav S(2009)ThunderDomeProceedings of the 5th international conference on Emerging networking experiments and technologies10.1145/1658939.1658962(193-204)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1145/1658939.1658962
Saucez DDonnet BBonaventure O(2009)On the Impact of Clustering on Measurement ReductionProceedings of the 8th International IFIP-TC 6 Networking Conference10.1007/978-3-642-01399-7_65(835-846)Online publication date: 11-May-2009
https://dl.acm.org/doi/10.1007/978-3-642-01399-7_65
Malli MBarakat CDabbous W(2008)CHESSComputer Communications10.1016/j.comcom.2007.11.00931:6(1239-1253)Online publication date: 1-Apr-2008
https://dl.acm.org/doi/10.1016/j.comcom.2007.11.009
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents