Locating internet routing instabilities

ABSTRACT

This paper presents a methodology for identifying the autonomous system (or systems) responsible when a routing change is observed and propagated by BGP. The origin of such a routing instability is deduced by examining and correlating BGP updates for many prefixes gathered at many observation points. Although interpreting BGP updates can be perplexing, we find that we can pinpoint the origin to either a single AS or a session between two ASes in most cases. We verify our methodology in two phases. First, we perform simulations on an AS topology derived from actual BGP updates using routing policies that are compatible with inferred peering/customer/provider relationships. In these simulations, in which network and router behavior are "ideal", we inject inter-AS link failures and demonstrate that our methodology can effectively identify most origins of instability. We then develop several heuristics to cope with the limitations of the actual BGP update propagation process and monitoring infrastructure, and apply our methodology and evaluation techniques to actual BGP updates gathered at hundreds of observation points. This approach of relying on data from BGP simulations as well as from measurements enables us to evaluate the inference quality achieved by our approach under ideal situations and how it is correlated with the actual quality and the number of observation points.

REFERENCES

• 1: John W. Stewart, III, BGP4: Inter-Domain Routing in the Internet, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 2: T. Griffin, "What is the Sound of One Route Flapping?," 2002. IPAM.
• 3: M. Caesar, L. Subramanian, and R. H. Katz, "Route cause analysis of Internet routing dynamics," tech. rep., UCB/CSD-04-1302, 2003.
• 4: 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
• 5: Mohit Lad , Akash Nanavati , Dan Massey , Lixia Zhang, An Algorithmic Approach to Identifying Link Failures, Proceedings of the 10th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC'04), p.25-34, March 03-05, 2004
• 6: 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]
• 7: 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
• 8: Jennifer Rexford , Jia Wang , Zhen Xiao , Yin Zhang, BGP routing stability of popular destinations, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637232]
• 9: Zhuoqing Morley Mao , Ramesh Govindan , George Varghese , Randy H. Katz, Route flap damping exacerbates internet routing convergence, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 10: Olaf Maennel , Anja Feldmann, Realistic BGP traffic for test labs, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 11: Renata Teixeira , Jennifer Rexford, A measurement framework for pin-pointing routing changes, Proceedings of the ACM SIGCOMM workshop on Network troubleshooting: research, theory and operations practice meet malfunctioning reality, September 03-03, 2004, Portland, Oregon, USA [doi>10.1145/1016687.1016704]
• 12: B. Premore, An Experimental Analysis of BGP Convergence Time, Proceedings of the Ninth International Conference on Network Protocols, p.53, November 11-14, 2001
• 13: C. Labovitz, R. Wattenhofer, S. Venkatachary, and A. Ahuja, "The impact of Internet policy and topology on delayed routing convergence," in Proc. IEEE INFOCOM, 2001.
• 14: H. Tangmunarunkit, R. Govindan, S. Shenker, and D. Estrin, "The impact of Internet policy on Internet paths," in Proc. IEEE INFOCOM, 2001.
• 15: Craig Labovitz , Abha Ahuja , Abhijit Bose , Farnam Jahanian, Delayed Internet routing convergence, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.175-187, August 28-September 01, 2000, Stockholm, Sweden
• 16: C. Labovitz, R. Malan, and F. Jahanian, "Origins of Internet routing instability," in Proc. IEEE INFOCOM, 1999.
• 17: R. Govindan , A. Reddy, An Analysis of Internet Inter-Domain Topology and Route Stability, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.850, April 09-11, 1997
• 18: RIPE's Routing Information Service. http://data.ris.ripe.net/.
• 19: University of Oregon RouteViews project. http://www.routeviews.org/.
• 20: Lakshminarayanan Subramanian , Venkata N. Padmanabhan , Randy H. Katz, Geographic Properties of Internet Routing, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.243-259, June 10-15, 2002
• 21: A. Feldmann, A. Greenberg, C. Lund, N. Reingold, and J. Rexford, "NetScope: Traffic engineering for IP networks," IEEE Network Magazine, 2000.
• 22: Nick Feamster , Jay Borkenhagen , Jennifer Rexford, Guidelines for interdomain traffic engineering, ACM SIGCOMM Computer Communication Review, v.33 n.5, October 2003 [doi>10.1145/963985.963988]
• 23: Ratul Mahajan , David Wetherall , Tom Anderson, Understanding BGP misconfiguration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 24: L. Gao, "On inferring autonomous system relationships in the Internet," in Proc. IEEE Global Internet, 2000.
• 25: B. Norton, "The art of peering: The peering playbook," 2002.
• 26: K. Varadhan, R. Govindan, and D. Estrin, "Persistent route oscillations in inter-domain routing," tech. rep., USC/ISI-96-631, 1996.
• 27: Z. Mao, L. Qiu, J. Wang, and Y. Zhang, "Inferring AS-level paths with RouteScope," Tech. Rep. TD-5T3RRP, AT&T Labs -- Research, 2003.
• 28: G. Battista, M. Patrignani, and M. Pizzonia, "Computing the Types of the Relationships Between Autonomous Systems," in Proc. IEEE INFOCOM, March 2003.
• 29: L. Subramanian, S. Agarwal, J. Rexford, and R. H. Katz, "Characterizing the Internet hierarchy from multiple vantage points," in Proc. IEEE INFOCOM, 2002.

INDEX TERMS

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

General Terms:
Measurement

Keywords:
BGP, analysis, instability origin, root cause analysis, routing instability, simulation