Reliable interdomain routing through multiple complementary routing processes

ABSTRACT

The Internet inter-domain routing protocol, BGP, experiences frequent routing disruptions such as transient routing loops or loss of connectivity. The goal of this paper is to address this issue while preserving BGP's benefits in terms of operational maturity and flexibility in accommodating diverse policies. In realizing this goal, we apply to inter-domain routing a common concept in the design of highly reliable systems, namely, the use of redundancy, which we introduce in a manner that maximizes compatibility with the existing BGP protocol. The basic idea is to run several, mostly unchanged BGP processes that compute complementary routes, so that in the presence of network instabilities a working path remains available to any destination. The paper outlines the design of this approach and compares it to previously proposed alternatives. The benefits of the scheme are demonstrated using actual BGP data and realistic simulations.

REFERENCES

• 1: A. B. Barr and et al. Improved BGP convergence via ghost flushing. In INFOCOM, 2003.
• 2: Matthew Caesar , Donald Caldwell , Nick Feamster , Jennifer Rexford , Aman Shaikh , Jacobus van der Merwe, Design and implementation of a routing control platform, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.15-28, May 02-04, 2005
• 3: J. Chandrashekar and et al. Limiting path exploration in BGP. In INFOCOM, 2005.
• 4: T. Erlebach and et al. Cuts and disjoint paths in the valley-free path model. In CAAN, 2004.
• 5: 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]
• 6: Lixin Gao , Jennifer Rexford, Stable Internet routing without global coordination, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.307-317, June 18-21, 2000, Santa Clara, California, United States
• 7: Albert Greenberg , Gisli Hjalmtysson , David A. Maltz , Andy Myers , Jennifer Rexford , Geoffrey Xie , Hong Yan , Jibin Zhan , Hui Zhang, A clean slate 4D approach to network control and management, ACM SIGCOMM Computer Communication Review, v.35 n.5, October 2005 [doi>10.1145/1096536.1096541]
• 8: Timothy G. Griffin , Gordon Wilfong, An analysis of BGP convergence properties, ACM SIGCOMM Computer Communication Review, v.29 n.4, p.277-288, Oct. 1999
• 9: Urs Hengartner , Sue Moon , Richard Mortier , Christophe Diot, Detection and analysis of routing loops in packet traces, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637217]
• 10: Nate Kushman , Srikanth Kandula , Dina Katabi, Can you hear me now?!: it must be BGP, ACM SIGCOMM Computer Communication Review, v.37 n.2, April 2007 [doi>10.1145/1232919.1232927]
• 11: N. Kushman and et al. R-BGP: Staying connected in a connected world. In NSDI, 2007.
• 12: A. Kvalbein and et al. Fast IP network recovery using multiple routing configurations. In INFOCOM, 2006.
• 13: 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
• 14: Y. Liao and et al. Multi-process inter-domain routing. Technical Report TR-08-CSE-09, ECE Department, UMass Amherst, 2008. http://rio.ecs.umass.edu/~yliao/mpr-tech.pdf.
• 15: J. Luo and et al. An approach to accelerate convergence for path vector protocol. In Proceedings of Globecom, 2002.
• 16: Murtaza Motiwala , Megan Elmore , Nick Feamster , Santosh Vempala, Path splicing, ACM SIGCOMM Computer Communication Review, v.38 n.4, October 2008
• 17: Dan Pei , Matt Azuma , Dan Massey , Lixia Zhang, BGP-RCN: improving BGP convergence through root cause notification, Computer Networks and ISDN Systems, v.48 n.2, p.175-194, 6 June 205 [doi>10.1016/j.comnet.2004.09.008]
• 18: Feng Wang , Lixin Gao , Jia Wang , Jian Qiu, On Understanding of Transient Interdomain Routing Failures, Proceedings of the 13TH IEEE International Conference on Network Protocols, p.30-39, November 06-09, 2005 [doi>10.1109/ICNP.2005.29]

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance