Neighbor-specific BGP: more flexible routing policies while improving global stability

ABSTRACT

The Border Gateway Protocol (BGP) offers network administrators considerable flexibility in controlling how traffic flows through their networks. However, the interaction between routing policies in different Autonomous Systems (ASes) can lead to protocol oscillation. The best-known sufficient conditions of BGP global routing stability impose restrictions on the kinds of local routing policies individual ASes can safely implement. In this paper, we present neighbor-specific BGP (NS-BGP), a modest extension to BGP that enables a much wider range of local policies without compromising global stability. Whereas a conventional BGP-speaking router selects a single "best" route (for each destination prefix), NS-BGP allows a router to customize the route selection on behalf of each neighbor. For example, one neighbor may prefer the shortest route, another the most secure route, and yet another the least expensive route. Surprisingly, we prove that the much more flexible NS-BGP is guaranteed to be stable under much less restrictive conditions on how routers "rank" the candidate routes. We also show that it is safe to deploy NS-BGP incrementally, as a routing system with a partial deployment of NS-BGP is guaranteed to be stable, even in the presence of failure and other topology changes. In addition to our theoretical results, we also describe how NS-BGP can be deployed by individual ASes independently without changes to the BGP message format or collaboration from neighboring ASes.

REFERENCES

• 1: Anindya Basu , Chih-Hao Luke Ong , April Rasala , F. Bruce Shepherd , Gordon Wilfong, Route oscillations in I-BGP with route reflection, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 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: Chi-kin Chau, Policy-based routing with non-strict preferences, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 4: Luc De Ghein, MPLS Fundamentals, Cisco Press, 2006
• 5: N. Duffield, K. Gopalan, M. R. Hines, A. Shaikh, and J. E. van der Merwe. Measurement informed route selection. In Proc. Passive and Active Measurement Conference (Extended Abstract), 2007.
• 6: Nick Feamster , Ramesh Johari , Hari Balakrishnan, Implications of autonomy for the expressiveness of policy routing, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 7: Joan Feigenbaum , Christos Papadimitriou , Rahul Sami , Scott Shenker, A BGP-based mechanism for lowest-cost routing, Distributed Computing, v.18 n.1, p.61-72, July 2005 [doi>10.1007/s00446-005-0122-y]
• 8: L. Gao, T. G. Griffin, and J. Rexford. Inherently safe backup routing with BGP. In Proc. IEEE INFOCOM, pages 547--556, April 2001.
• 9: Lixin Gao , Jennifer Rexford, Stable internet routing without global coordination, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.681-692, December 2001 [doi>10.1109/90.974523]
• 10: Sharon Goldberg , Shai Halevi , Aaron D. Jaggard , Vijay Ramachandran , Rebecca N. Wright, Rationality and traffic attraction: incentives for honest path announcements in bgp, Proceedings of the ACM SIGCOMM 2008 conference on Data communication, August 17-22, 2008, Seattle, WA, USA
• 11: T. Griffin and G. Huston. BGP wedgies. RFC 4264, November 2005.
• 12: Timothy G. Griffin , Aaron D. Jaggard , Vijay Ramachandran, Design principles of policy languages for path vector protocols, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863964]
• 13: Timothy G. Griffin , F. Bruce Shepherd , Gordon Wilfong, The stable paths problem and interdomain routing, IEEE/ACM Transactions on Networking (TON), v.10 n.2, April 2002
• 14: 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
• 15: Timothy Griffin , Gordon T. Wilfong, Analysis of the MED Oscillation Problem in BGP, Proceedings of the 10th IEEE International Conference on Network Protocols, p.90-99, November 12-15, 2002
• 16: Timothy G. Griffin , Gordon Wilfong, On the correctness of IBGP configuration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 17: IETF. Advertisement of Multiple Paths in BGP, July 2008. http://tools.ietf.org/html/draft-walton-bgp-add-paths-06. Internet Draft. Expires January 2009.
• 18: Josh Karlin , Stephanie Forrest , Jennifer Rexford, Autonomous security for autonomous systems, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.15, p.2908-2923, October, 2008 [doi>10.1016/j.comnet.2008.06.012]
• 19: Hagay Levin , Michael Schapira , Aviv Zohar, Interdomain routing and games, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374388]
• 20: R. Mahajan, D. Wetherall, and T. Anderson. Mutually controlled routing with independent ISPs. In Proc. Networked Systems Design and Implementation, 2007.
• 21: Wolfgang Mühlbauer , Anja Feldmann , Olaf Maennel , Matthew Roughan , Steve Uhlig, Building an AS-topology model that captures route diversity, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 22: Number of BGP routes a large ISP sees in total. Discussion on NANOG mailing list, http://www.merit.edu/mail.archives/nanog/2007-04/msg00502.html.
• 23: M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT press, 1994.
• 24: Ivan Pepelnjak, MPLS and VPN Architectures, Cisco Press, 2000
• 25: R. Sami, M. Schapira, and A. Zohar. Security and selfishness in interdomain routing. Technical report, Leibniz Center for Research in Computer Science, 2008.
• 26: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 27: S. Uhlig and S. Tandel. Quantifying the impact of route-reflection on BGP routes diversity inside a tier-1 network. In Proc. IFIP NETWORKING, 2006.
• 28: J. Van der Merwe , A. Cepleanu , K. D'Souza , B. Freeman , A. Greenberg , D. Knight , R. McMillan , D. Moloney , J. Mulligan , H. Nguyen , M. Nguyen , A. Ramarajan , S. Saad , M. Satterlee , T. Spencer , D. Toll , S. Zelingher, Dynamic connectivity management with an intelligent route service control point, Proceedings of the 2006 SIGCOMM workshop on Internet network management, p.29-34, September 11-15, 2006, Pisa, Italy [doi>10.1145/1162638.1162643]
• 29: Patrick Verkaik , Dan Pei , Tom Scholl , Aman Shaikh , Alex C. Snoeren , Jacobus E. van der Merwe, Wresting control from BGP: scalable fine-grained route control, 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference, p.1-14, June 17-22, 2007, Santa Clara, CA
• 30: Y. Wang, I. Avramopoulos, and J. Rexford. Design for configurability: Rethinking interdomain routing policies from the ground up. IEEE Journal on Selected Areas in Communications, April 2009.
• 31: Y. R. Yang, H. Xie, H. Wang, A. Silberschatz, Y. Liu, L. E. Li, and A. Krishnamurthy. On route selection for interdomain traffic engineering. IEEE Network Magazine, November 2005.

INDEX TERMS

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

General Terms:
Algorithms, Design, Theory

Keywords:
bgp, flexibility, policy, routing, stability