On the scalability of BGP: the roles of topology growth and update rate-limiting

ABSTRACT

The scalability of BGP routing is a major concern for the Internet community. Scalability is an issue in two different aspects: increasing routing table size, and increasing rate of BGP updates. In this paper, we focus on the latter. Our objective is to characterize the churn increase experienced by ASes in different levels of the Internet hierarchy as the network grows. We look at several "what-if" growth scenarios that are either plausible directions in the evolution of the Internet or educational corner cases, and investigate their scalability implications. In addition, we examine the effect of the BGP update rate-limiting timer (MRAI), considering both major variations with which it has been deployed. Our findings explain the dramatically different impact of multi-homing and peering on BGP scalability, identify which topological growth scenarios will lead to faster churn increase, and emphasize the importance of not rate-limiting explicit withdrawals (despite what RFC-4271 recently required).

REFERENCES

• 1: Quagga project website. http://www.quagga.net/.
• 2: SSFNet website. http://www.ssfnet.org/.
• 3: R. Albert and A. L. Barabasi. Statistical mechanics of complex networks. Reviews of Modern Physics, 74: 47, 2002.
• 4: A. L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286: 509--512, October 1999.
• 5: A. Broido, E. Nemeth, and k. claffy. Internet expansion, refinement, and churn. European Transactions on Telecommunications, January 2002.
• 6: Tian Bu , Lixin Gao , Don Towsley, On characterizing BGP routing table growth, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.45 n.1, p.45-54, 15 May 2004 [doi>10.1016/j.comnet.2004.02.003]
• 7: Hyunseok Chang , Sugih Jamin , Walter Willinger, Internet connectivity at the AS-level: an optimization-driven modeling approach, Proceedings of the ACM SIGCOMM workshop on Models, methods and tools for reproducible network research, August 25-27, 2003, Karlsruhe, Germany [doi>10.1145/944773.944780]
• 8: Amogh Dhamdhere , Constantine Dovrolis, Ten years in the evolution of the internet ecosystem, Proceedings of the 8th ACM SIGCOMM conference on Internet measurement, October 20-22, 2008, Vouliagmeni, Greece [doi>10.1145/1452520.1452543]
• 9: X. Dimitropoulos, D. Krioukov, A. Vahdat, and G. Riley. Graph annotations in modeling complex network topologies. arXiv: 0708.3879, 2008.
• 10: Xenofontas A. Dimitropoulos , George F. Riley, Efficient large-scale BGP simulations, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.12, p.2013-2027, 24 August 2006 [doi>10.1016/j.comnet.2005.09.033]
• 11: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 12: 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]
• 13: B. Premore, An Experimental Analysis of BGP Convergence Time, Proceedings of the Ninth International Conference on Network Protocols, p.53, November 11-14, 2001
• 14: Y. He, S. V. Krishnamurthy, M. Faloutsos, and M. Chrobak. Policy-aware topologies for efficient inter-domain routing evaluations. In IEEE INFOCOM 2008 Mini-Conference, Phoenix, AZ, USA, April 2008.
• 15: G. Huston. The BGP instability report. http://bgpupdates.potaroo.net/.
• 16: G. Huston and G. Armitage. Projecting future IPv4 router requirements from trends in dynamic BGP behaviour. In ATNAC, Australia, December 2006.
• 17: Dmitri Krioukov , k c claffy , Kevin Fall , Arthur Brady, On compact routing for the internet, ACM SIGCOMM Computer Communication Review, v.37 n.3, July 2007 [doi>10.1145/1273445.1273450]
• 18: 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
• 19: C. Labovitz, A. Ahuja, R. Wattenhofer, and S. Venkatachary. The impact of Internet policy and topology on delayed routing convergence. In INFOCOM, Anchorage, AK, USA, April 2001.
• 20: Craig Labovitz , G. Robert Malan , Farnam Jahanian, Internet routing instability, ACM SIGCOMM Computer Communication Review, v.27 n.4, p.115-126, Oct. 1997
• 21: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graph evolution: Densification and shrinking diameters, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.1, p.2-es, March 2007 [doi>10.1145/1217299.1217301]
• 22: Jun Li , Michael Guidero , Zhen Wu , Eric Purpus , Toby Ehrenkranz, BGP routing dynamics revisited, ACM SIGCOMM Computer Communication Review, v.37 n.2, April 2007 [doi>10.1145/1232919.1232921]
• 23: L. Li, D. Alderson, R. Tanaka, J. C. Doyle, and W. Willinger. Towards a theory of scale-free graphs: Definition, properties, and implications (extended version). Internet Mathematics, 2005.
• 24: D. Meyer, L. Zhang, and K. Fall. Report from the IAB workshop on routing and addressing. http://tools.ietf.org/id/draft-iab-raws-report-02.txt, April 2007.
• 25: Ricardo Oliveira , Beichuan Zhang , Dan Pei , Rafit Izhak-Ratzin , Lixia Zhang, Quantifying path exploration in the internet, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177116]
• 26: B. Quoitin and S. Uhlig. Modeling the routing of an autonomous system with C-BGP. IEEE Network, 19(6), November 2005.
• 27: Y. Rekhter , T. Li, A Border Gateway Protocol 4 (BGP-4), RFC Editor, 1995
• 28: Y. Rekhter, T. Li, and S. Hares. A border gateway protocol 4 (BGP-4). RFC4271, January 2006.
• 29: RIPE's Routing Information Service. http://www.ripe.net/ris/.
• 30: J. G. Scudder. {idr} re: {rrg} re: BGP path hunting, MRAI timer and path length damping. Message to the IDR mailing list, http://www1.ietf.org/mail-archive/web/idr/current/msg02415.html, June 2007.
• 31: G. Siganos, M. Faloutsos, and C. Faloutsos. The Evolution of the Internet: Topology and Routing. University of California, Riverside technical report, 2002.
• 32: Lakshminarayanan Subramanian , Matthew Caesar , Cheng Tien Ee , Mark Handley , Morley Mao , Scott Shenker , Ion Stoica, HLP: a next generation inter-domain routing protocol, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 33: X. Zhao, B. Zhang, A. Terzis, D. Massey, and L. Zhang. The impact of link failure location on routing dynamics: A formal analysis. In ACM SIGCOMM Asia Workshop, April 2005.
• 34: S. Zhou and R. Mondragon. Accurately Modeling the Internet Topology. Physical Review E, vol. 70, 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Design, Experimentation, Measurement, Performance