An empirical evaluation of wide-area internet bottlenecks

ABSTRACT

Conventional wisdom has been that the performance limitations in the current Internet lie at the edges of the network -- i.e last mile connectivity to users, or access links of stub ASes. As these links are upgraded, however, it is important to consider where new bottlenecks and hot-spots are likely to arise. In this paper, we address this question through an investigation of non-access bottlenecks. These are links within carrier ISPs or between neighboring carriers that could potentially constrain the bandwidth available to long-lived TCP flows. Through an extensive measurement study, we discover, classify, and characterize bottleneck links (primarily in the U.S.) in terms of their location, latency, and available capacity.We find that about 50% of the Internet paths explored have a non-access bottleneck with available capacity less than 50 Mbps, many of which limit the performance of well-connected nodes on the Internet today. Surprisingly, the bottlenecks identified are roughly equally split between intra-ISP links and peering links between ISPs. Also, we find that low-latency links, both intra-ISP and peering, have a significant likelihood of constraining available bandwidth. Finally, we discuss the implications of our findings on related issues such as choosing an access provider and optimizing routes through the network. We believe that these results could be valuable in guiding the design of future network services, such as overlay routing, in terms of which links or paths to avoid (and how to avoid them) in order to improve performance.

REFERENCES

• 1: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 2: Hari Balakrishnan , Mark Stemm , Srinivasan Seshan , Randy H. Katz, Analyzing stability in wide-area network performance, Proceedings of the 1997 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.2-12, June 15-18, 1997, Seattle, Washington, United States
• 3: Lawrence S. Brakmo , Sean W. O'Malley , Larry L. Peterson, TCP Vegas: new techniques for congestion detection and avoidance, Proceedings of the conference on Communications architectures, protocols and applications, p.24-35, August 31-September 02, 1994, London, United Kingdom
• 4: Tian Bu , Nick Duffield , Francesco Lo Presti , Don Towsley, Network tomography on general topologies, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 5: Robert L. Carter , Mark E. Crovella, Measuring bottleneck link speed in packet-switched networks, Performance Evaluation, 27-28, p.297-318, Oct. 1996 [doi>10.1016/0166-5316(96)00036-3]
• 6: Cooperative Association for Internet Data Analysis (CAIDA). Internet tools taxonomy. http://www.caida.org/tools/taxonomy/, October 2002.
• 7: Allen B. Downey, Using pathchar to estimate Internet link characteristics, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.241-250, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 8: Lixin Gao, On inferring autonomous system relationships in the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.733-745, December 2001 [doi>10.1109/90.974527]
• 9: R. Govindan and V. Paxson. Estimating router ICMP generation delays. In Proceedings of Passive and Active Measurement Workshop (PAM), Fort Collins, CO, 2002.
• 10: George Yang , Brian R. Crowley, Network Characterization Service (NCS), Proceedings of the 10th IEEE International Symposium on High Performance Distributed Computing (HPDC-10'01), p.289, August 07-09, 2001
• 11: Urs Hengartner , Sue Moon , Richard Mortier , Christophe Diot, Detection and analysis of routing loops in packet traces, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637217]
• 12: V. Jacobson. pathchar - A Tool to Infer Characteristics of Internet Paths. ftp://ee.lbl.gov/pathchar/, 1997.
• 13: Manish Jain , Constantinos Dovrolis, End-to-end available bandwidth: measurement methodology, dynamics, and relation with TCP throughput, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 14: M. Jain and C. Dovrolis. Pathload: A measurement tool for end-to-end available bandwidth. In Proceedings of Passive and Active Measurement Workshop (PAM), Fort Collins, CO, March 2002.
• 15: Sharad Jaiswal , Gianluca Iannaccone , Christophe Diot , Jim Kurose , Don Towsley, Measurement and classification of out-of-sequence packets in a tier-1 IP backbone, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637218]
• 16: Craig Labovitz , Abha Ahuja , Farnam Jahanian, Experimental Study of Internet Stability and Backbone Failures, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.278, June 15-18, 1999
• 17: K. Lai and M. Baker. Nettimer: A tool for measuring bottleneck link bandwidth. In Proceedings of USENIX Symposium on Internet Technologies and Systems, March 2001.
• 18: B. A. Mah. pchar: A tool for measuring internet path characteristics. http://www.employees.org/~bmah/Software/pchar/, June 2000.
• 19: A. P. Markopoulou, F. A. Tobagi, and M. J. Karam. Assessment of VoIP quality over Internet backbones. In Proceedings of IEEE INFOCOM'02, New York, NY, June 2002.
• 20: M. Mathis and J. Mahdavi. Diagnosing Internet Congestion with a Transport Layer Performance Tool . In Proc. INET '96, Montreal, Canada, June 1996. http://www.isoc.org/inet96/proceedings/.
• 21: Network Characterization Service: Netest and Pipechar. http://www-didc.lbl.gov/pipechar, 1999.
• 22: ns-2 Network Simulator. http://www.isi.edu/nsnam/ns/, 2000.
• 23: Vern Paxson, End-to-end Internet packet dynamics, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.139-152, September 14-18, 1997, Cannes, France
• 24: Vern Paxson, End-to-end routing behavior in the Internet, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.601-615, Oct. 1997 [doi>10.1109/90.649563]
• 25: V. Paxson, A. Adams, and M. Mathis. Experiences with NIMI. In Proceedings of Passive and Active Measurement Workshop (PAM), Hamilton, New Zealand, April 2000.
• 26: PlanetLab. http://www.planet-lab.org, 2002.
• 27: RADB whois Server. whois.radb.net.
• 28: RIPE whois Service. whois.ripe.net.
• 29: BGP Tables from the University of Oregon RouteViews Project. http://moat.nlanr.net/AS/data.
• 30: University of Oregon, RouteViews Project. http://www.routeviews.org.
• 31: Stefan Savage , Thomas Anderson , Amit Aggarwal , David Becker , Neal Cardwell , Andy Collins , Eric Hoffman , John Snell , Amin Vahdat , Geoff Voelker , John Zahorjan, Detour: Informed Internet Routing and Transport, IEEE Micro, v.19 n.1, p.50-59, January 1999 [doi>10.1109/40.748796]
• 32: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 33: L. Subramanian, S. Agarwal, J. Rexford, and R. H. Katz. Characterizing the Internet hierarchy from multiple vantage points. In Proceedings of IEEE INFOCOM, June 2002.
• 34: Traceroute.org. http://www.traceroute.org.
• 35: Yin Zhang , Lee Breslau , Vern Paxson , Scott Shenker, On the characteristics and origins of internet flow rates, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 36: Yin Zhang , Nick Duffield, On the constancy of internet path properties, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505228]
• 37: Y. Zhang, V. Paxson, and S. Shenker. The stationarity of internet path properties: Routing, loss, and throughput. Technical report, ICSI Center for Internet Research, May 2000.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks

General Terms:
Measurement, Performance