BGP routing stability of popular destinations

ABSTRACT

The Border Gateway Protocol (BGP) plays a crucial role in the delivery of traffic in the Internet. Fluctuations in BGP routes cause degradation in user performance, increased processing load on routers, and changes in the distribution of traffic load over the network. Although earlier studies have raised concern that BGP routes change quite often, previous work has not considered whether these routing fluctuations affect a significant portion of the traffic. This paper shows that the small number of popular destinations responsible for the bulk of Internet traffic have remarkably stable BGP routes. The vast majority of BGP instability stems from a small number of unpopular destinations. We draw these conclusions from a joint analysis of BGP update messages and flow-level traffic measurements from AT&T's IP backbone. In addition, we analyze the routing stability of destination prefixes corresponding to the NetRating's list of popular Web sites using the update messages collected by the RouteViews and RIPE-NCC servers. Our results suggest that operators can engineer their networks under the assumption that the BGP advertisements associated with most of the traffic are reasonably stable.

References

1. Y. Rekhter and T. Li, "A Border Gateway Protocol." Request for Comments 1771, March 1995.
2. K. Varadhan, R. Govindan, and D. Estrin, "Persistent route oscillations in inter-domain routing," Tech. Rep. 96--631, USC/ISI, February 1996.
3. T.G. Griffin and G. Wilfong, "An analysis of BGP convergence properties," in Proc. ACM SIGCOMM, September 1999.
4. C. Labovitz, R. Malan, and E Jahanian, "Internet routing stability," IEEE/ACM Trans. Networking, pp. 515--528, October 1998.
5. C. Labovitz, R. Malan, and F. Jahanian, "Origins of pathological Internet routing instability," in Proc. IEEE INFOCOM, 1999.
6. C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian, "Delayed Internet routing convergence," IEEE/ACM Trans. Networking, vol. 9, pp. 293--306, June 2001.
7. C. Labovitz, A. Ahuja, and E Jahanian, "Experimental study of Internet stability and wide-area network failures," in Proc. Fault-Tolerant Computing Symposium, June 1999.
8. W. Fang and L. Peterson, "Inter-AS traffic patterns and their implications," in Proc. 1EEE Global lnternet, December 1999.
9. A. Feldmann, A. Greenberg, C. Lund, N. Reingold, J. Rexford, and E True, "Deriving traffic demands for operational IP networks: Methodology and experience," IEEEIACM Trans. Networking, vol. 9, June 2001.
10. N. Taft, S. Bhattacharyya, J. Jetcheva, and C. Diot, "Understanding traffic dynamics at a backbone POP," in Proc. Scalability and Traffic Control in IP Networks, SP1E ITCOM, August 2001.
11. "Route Views Project." http://www.routeviews.org.
12. "RIPE NCC RIS." http://www.ripe.net/ripencc/pub-services/np/ris-index.html.
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, April 2001.
14. "Sampled Netflow." http://www.cisco.com/univercd/cc/td/doc/product/software/iosl20/120newft/1201imit/120s/120sll/12s_sanf.htm.
15. N. Duffield, C. Lund, and M. Thorup, "Charging from sampled network usage," in Proc. Internet Measurement Workshop, November 2001.
16. "NetRatings?' http://www.netratings.com.
17. Z. Mao, C. Cranor, E Douglis, M. Rabinovich, O. Spatscheck, and J. Wang, "A precise and efficient evaluation of the proximity between Web clients and their local DNS servers," in Proc. USENIX, June 2002.

Index Terms

• Networks

  • Network protocols

    • Network layer protocols

      • Routing protocols

    • Transport protocols

  • Network services

    • Network monitoring

  • Network types

    • Public Internet