Timothy G. Griffin
ABSTRACT
The Border Gateway Protocol (BGP) has two distinct modes of operation. External BGP (EBGP) exchanges reachability information between autonomous systems, while Internal BGP (IBGP) exchanges external reachability information within an autonomous system. We study several routing anomalies that are unique to IBGP because, unlike EBGP, forwarding paths and signaling paths are not always symmetric. In particular, we focus on anomalies that can cause the protocol to diverge, and those that can cause a router's chosen forwarding path to an egress point to be deflected by another router on that path. Deflections can greatly complicate the debugging of routing problems, and in the worst case multiple deflections can combine to form persistent forwarding loops. We define a correct IBGP configuration to be one that is anomaly free for every possible set of routes sent by neighboring autonomous systems. We show that determination of IBGP configuration correctness is NP-hard. However, we give simple sufficient conditions on network configurations that guarantee correctness.
- Anindya Basu, C.-H. Luke Ong, April Rasala, F. Bruce Shepherd, and Gordon Wilfong. Route oscillations in I-BGP with route reflection. In Proceedings of ACM SIGCOMM, 2002.]] Google Scholar
Digital Library
- T. Bates, R. Chandra, and E. Chen. BGP route reflection: An alternative to full mesh IBGP. RFC 2796, 2000.]] Google ScholarDigital Library
- Marc Blanchet, Florent Parent, and Bill St-Arnaud. Optical BGP (OBGP): InterAS lightpath provisioning. Internet Draft draft-parent-obgp-01.txt. Work in progress.]]Google Scholar
- Cisco. Endless BGP Convergence Problem in Cisco IOS Software Releases. Field Note, October 10 2001, http://www.cisco.com/warp/public/770/fn12942.html.]]Google Scholar
- Rohit Dube. A comparison of scaling techniques for BGP. ACM Computer Communication Review, 29(3), 1999.]] Google ScholarDigital Library
- Rohit Dube and John G. Scudder. BGP scaling techniques revisited. ACM Computer Communication Review, 29(5), 1999.]] Google ScholarDigital Library
- L. Gao, T. G. Grin, and J. Rexford. Inherently safe backup routing with BGP. In Proceedings of the 20th IEEE Conference on Computer Communications (Infocom 2001), Anchorage, Alaska, April 2001.]]Google Scholar
- Lixin Gao and Jennifer Rexford. Stable internet routing without global coordination. In Proceedings of ACM SIGMETRICS, June 2000.]] Google ScholarDigital Library
- M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., San Francisco, CA, 1979.]] Google ScholarDigital Library
- T. G. Griffin and G. Wilfong. A safe path vector protocol. In Proceedings of the 19th Annual IEEE Conference on Computer Communications (Infocom 2000), Tel Aviv, Israel, March 2000.]]Google ScholarCross Ref
- Timothy G. Griffin, F. Bruce Shepherd, and Gordon Wilfong. Policy disputes in path-vector protocols. In Proceedings of Seventh International Conference on Network Protocols (ICNP'99), pages 21--30, 1999.]] Google ScholarDigital Library
- Timothy G. Griffin, F. Bruce Shepherd, and Gordon Wilfong. The stable paths problem and interdomain routing. IEEE/ACM Transactions on Networking, 2002.]] Google ScholarDigital Library
- Timothy G. Griffin and Gordon Wilfong. An analysis of BGP convergence properties. In Proceedings of ACM SIGCOMM, pages 277--288, 1999.]] Google ScholarDigital Library
- Timothy G. Griffin and Gordon Wilfong. Analysis of the MED oscillation problem in BGP. unpublished manuscript, 2002.]]Google Scholar
- S. Halabi and D. McPherson. Internet Routing Architectures. Cisco Press, Indianapolis, Indiana, second edition, 2000.]] Google ScholarDigital Library
- C. Huitema. Routing in the Internet. Prentice Hall, 2000.]] Google ScholarDigital Library
- Ratul Mahajan, David Wetherall, and Tom Anderson. Understanding BGP misconfigurations. In Proceedings of ACM SIGCOMM, 2002.]] Google ScholarDigital Library
- D. McPherson, V. Gill, D. Walton, and A. Retana. BGP persistent route oscillation condition. Internet Draft draft-ietf-idr-route-oscillation-01.txt , Work In Progress, 2002.]]Google Scholar
- Y. Rekhter and T. Li. A Border Gateway Protocol. RFC 1771 (BGP version 4), March 1995.]] Google ScholarDigital Library
- Jonathan Rosenberg, Hussein Salma, and Matt Squire. Telephony routing over IP (TRIP). RFC 3219. January 2002.]] Google ScholarDigital Library
- P. Traina, D. McPherson, and J. Scudder. Autonomous system confederations for BGP. RFC 3056, 2001.]] Google ScholarDigital Library
- Kanan Varadhan, Ramesh Govindan, and Deborah Estrin. Persistent route oscillations in inter-domain routing. Computer Networks, 32:1--16, 2000.]]Google ScholarCross Ref
Index Terms
- On the correctness of IBGP configuration
Recommendations
On the correctness of IBGP configuration
Proceedings of the 2002 SIGCOMM conferenceThe Border Gateway Protocol (BGP) has two distinct modes of operation. External BGP (EBGP) exchanges reachability information between autonomous systems, while Internal BGP (IBGP) exchanges external reachability information within an autonomous system. ...
Designing optimal iBGP route-reflection topologies
NETWORKING'08: Proceedings of the 7th international IFIP-TC6 networking conference on AdHoc and sensor networks, wireless networks, next generation internetThe Border Gateway Protocol (BGP) is used today by all Autonomous Systems (AS) in the Internet. Inside each AS, iBGP sessions distribute the external routes among the routers. In large ASs, relying on a full-mesh of iBGP sessions between routers is not ...
Preventing persistent oscillations and loops in IBGP configuration with route reflection
Internal Border Gateway Protocol (IBGP) is responsible for distributing external reachability information, obtained via External-BGP (EBGP) sessions, within an autonomous system (AS). To avoid a full mesh of IBGP sessions between all the BGP speakers of ...
Comments