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. J. W. Stewart, BGP4: Inter-Domain Routing in the Internet. 1999.
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. D.-F. Chang, R. Govindan, and J. Heidemann, "The temporal and toplogical characteristics of BGP path changes," in Proc. ICNP, 2003.
5. M. Lad, A. Nanavati, D. Massey, and L. Zhang, "An algorithmic approach to identifying link failures," in Proc. PRDC, 2004.
6. Z. M. Mao, R. Bush, T. G. Griffin, and M. Roughan, "BGP Beacons," in Proc. ACM IMC, 2003.
7. N. Feamster, D. G. Andersen, H. Balakrishnan, and M. F. Kaashoek, "Measuring the effects of internet path faults on reactive routing," in Proc. ACM SIGMETRICS, 2003.
8. J. Rexford, J. Wang, Z. Xiao, and Y. Zhang, "BGP routing stability of popular destinations," in Proc. ACM IMW, 2002.
9. Z. M. Mao, R. Govindan, G. Varghese, and R. Katz, "Route flap damping exacerbates Internet routing convergence," in Proc. ACM SIGCOMM, 2002.
10. O. Maennel and A. Feldmann, "Realistic BGP traffic for test labs," in Proc. ACM SIGCOMM, 2002.
11. R. Teixeira and J. Rexford, "A measurement framework for pin-pointing routing changes," in Proc. ACM SIGCOMM Network Troubleshooting Workshop, 2004.
12. T. G. Griffin and B. J. Premore, "An experimental analysis of BGP convergence time," in Proc. ICNP, 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. C. Labovitz, A. Ahuja, A. Abose, and F. Jahanian, "An experimental study of delayed Internet routing convergence," in Proc. ACM SIGCOMM, 2000.
16. C. Labovitz, R. Malan, and F. Jahanian, "Origins of Internet routing instability," in Proc. IEEE INFOCOM, 1999.
17. R. Govindan and A. Reddy, "An analysis of Internet inter-domain topology and route stability," in Proc. IEEE INFOCOM, 1997.
18. RIPE's Routing Information Service. http://data.ris.ripe.net/.
19. University of Oregon RouteViews project. http://www.routeviews.org/.
20. L. Subramanian, V. N. Padmanabhan, and R. H. Katz, "Geographic properties of Internet routing," in Proc. Usenix, 2002.
21. A. Feldmann, A. Greenberg, C. Lund, N. Reingold, and J. Rexford, "NetScope: Traffic engineering for IP networks," IEEE Network Magazine, 2000.
22. N. Feamster, J. Borkenhagen, and J. Rexford, "Guidelines for interdomain traffic engineering," ACM CCR, 2003.
23. D. Wetherall, R. Mahajan, and T. Anderson, "Understanding BGP misconfigurations," in Proc. ACM SIGCOMM, 2002.
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

• Networks

  • Network protocols

    • Network layer protocols

      • Routing protocols