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: Timothy G. Griffin , Gordon Wilfong, An analysis of BGP convergence properties, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.277-288, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 4: 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]
• 5: C. Labovitz, R. Malan, and F. Jahanian, "Origins of pathological Internet routing instability," in Proc. IEEE INFOCOM, 1999.
• 6: 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]
• 7: 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
• 8: W. Fang and L. Peterson, "Inter-AS traffic patterns and their implications," in Proc. 1EEE Global lnternet, December 1999.
• 9: Anja Feldmann , Albert Greenberg , Carsten Lund , Nick Reingold , Jennifer Rexford , Fred True, Deriving traffic demands for operational IP networks: methodology and experience, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.265-280, June 2001 [doi>10.1109/90.929850]
• 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: Nick Duffield , Carsten Lund , Mikkel Thorup, Charging from sampled network usage, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505232]
• 16: "NetRatings?' http://www.netratings.com.
• 17: Zhuoqing Morley Mao , Charles D. Cranor , Fred Douglis , Michael Rabinovich , Oliver Spatscheck , Jia Wang, A Precise and Efficient Evaluation of the Proximity Between Web Clients and Their Local DNS Servers, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.229-242, June 10-15, 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

General Terms:
Management, Measurement, Performance