A measurement study on the impact of routing events on end-to-end internet path performance

ABSTRACT

Extensive measurement studies have shown that end-to-end Internet path performance degradation is correlated with routing dynamics. However, the root cause of the correlation between routing dynamics and such performance degradation is poorly understood. In particular, how do routing changes result in degraded end-to-end path performance in the first place? How do factors such as topological properties, routing policies, and iBGP configurations affect the extent to which such routing events can cause performance degradation? Answers to these questions are critical for improving network performance.In this paper, we conduct extensive measurement that involves both controlled routing updates through two tier-1 ISPs and active probes of a diverse set of end-to-end paths on the Internet. We find that routing changes contribute to end-to-end packet loss significantly. Specifically, we study failover events in which a link failure leads to a routing change and recovery events in which a link repair causes a routing change. In both cases, it is possible to experience data plane performance degradation in terms of increased long loss burst as well as forwarding loops. Furthermore, we find that common routing policies and iBGP configurations of ISPs can directly affect the end-to-end path performance during routing changes. Our work provides new insights into potential measures that network operators can undertake to enhance network performance.

REFERENCES

• 1: Sharad Agarwal , Chen-Nee Chuah , Supratik Bhattacharyya , Christophe Diot, The impact of BGP dynamics on intra-domain traffic, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 2: Sharad Agarwal , Antonio Nucci , Supratik Bhattacharyya, Measuring the Shared Fate of IGP Engineering and Interdomain Traffic, Proceedings of the 13TH IEEE International Conference on Network Protocols (ICNP'05), p.236-245, November 06-09, 2005 [doi>10.1109/ICNP.2005.22]
• 3: Catherine Boutremans , Gianluca Iannaccone , Christophe Diot, Impact of link failures on VoIP performance, Proceedings of the 12th international workshop on Network and operating systems support for digital audio and video, May 12-14, 2002, Miami, Florida, USA [doi>10.1145/507670.507680]
• 4: CAESAR, M., CALDWELL, D., FEAMSTER, N., REXFORD, J., SHAIKH, A., AND VAN DER MERWE, J. Design and implementation of a Routing Control Platform. In Proc. Networked Systems Design and Implementation (2005).
• 5: Di-Fa Chang , Ramesh Govindan , John Heidemann, The Temporal and Topological Characteristics of BGP Path Changes, Proceedings of the 11th IEEE International Conference on Network Protocols, p.190, November 04-07, 2003
• 6: Nick Feamster , David G. Andersen , Hari Balakrishnan , M. Frans Kaashoek, Measuring the effects of internet path faults on reactive routing, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 7: Anja Feldmann , Olaf Maennel , Z. Morley Mao , Arthur Berger , Bruce Maggs, Locating internet routing instabilities, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 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: GAO, L., GRIFFIN, T., AND REXFORD, J. Inherently Safe Backup Routing with BGP. In Proceedings of IEEE INFOCOM (2001).
• 10: Lixin Gao , Jennifer Rexford, Stable internet routing without global coordination, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.681-692, December 2001 [doi>10.1109/90.974523]
• 11: GRIFFIN, T., AND WILFONG, G. T. A Safe Path Vector Protocol. In Proceedings of IEEE INFOCOM (2000), pp. 490--499.
• 12: Timothy G. Griffin , F. Bruce Shepherd , Gordon Wilfong, The stable paths problem and interdomain routing, IEEE/ACM Transactions on Networking (TON), v.10 n.2, April 2002
• 13: Timothy G. Griffin , Gordon Wilfong, On the correctness of IBGP configuration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 14: LABOVITZ, C., AND AHUJA, A. The Impact of Internet Policy and Topology on Delayed Routing Convergence. In Proceedings of IEEE INFOCOM (Anchorage, Alaska, April 2001).
• 15: Craig Labovitz , Abha Ahuja , Abhijit Bose , Farnam Jahanian, Delayed Internet routing convergence, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.293-306, June 2001 [doi>10.1109/90.929852]
• 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: Craig Labovitz , G. Robert Malan , Farnam Jahanian, Internet routing instability, IEEE/ACM Transactions on Networking (TON), v.6 n.5, p.515-528, Oct. 1998 [doi>10.1109/90.731185]
• 18: Z. Morley Mao , Randy Bush , Timothy G. Griffin , Matthew Roughan, BGP beacons, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948207]
• 19: MARKOPOULOU, A., IANNACCONE, G., BHATTACHARYYA, S., CHUAH, C., AND DIOT, C. Characterization of Failures in an IP Backbone, 2004.
• 20: 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]
• 21: Dan Pei , Xiaoliang Zhao , Dan Massey , Lixia Zhang, A Study of BGP Path Vector Route Looping Behavior, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.720-729, March 24-26, 2004
• 22: PlanetLab. http://www.planet-lab.org.
• 23: Matthew Roughan , Tim Griffin , Morley Mao , Albert Greenberg , Brian Freeman, Combining routing and traffic data for detection of IP forwarding anomalies, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 24: SHAND, M., AND BRYANT, S. IP Fast Reroute Framework. Internet Draft draft-ietf-rtgwg-ipfrr-framework-04.txt, October 2005.
• 25: TEIXEIRA, R., SHAIKH, A., GRIFFIN, T., AND REXFORD, J. Dynamics of hot-potato routing in IP networks, 2004.
• 26: Feng Wang , Lixin Gao , Jia Wang , Jian Qiu, On Understanding of Transient Interdomain Routing Failures, Proceedings of the 13TH IEEE International Conference on Network Protocols (ICNP'05), p.30-39, November 06-09, 2005 [doi>10.1109/ICNP.2005.29]
• 27: Y. Rekhter , T. Li, A Border Gateway Protocol 4 (BGP-4), RFC Editor, 1995

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

General Terms:
Experimentation, Measurement, Reliability

Keywords:
BGP, active probing, event, failover event, packet loss, packet reordering, recovery, routing dynamics