How to Construct a Correct and Scalable iBGP Configuration
The Border Gateway Protocol (BGP), the current inter domain routing protocol in the Internet, has two modes of operation: eBGP (External BGP), used to exchange routing information between autonomous systems, and iBGP (Internal BGP), used to propagate that information within an autonomous system (AS)...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Language: | en_US |
| Published: |
2005
|
| Online Access: | http://hdl.handle.net/1721.1/30560 |
| _version_ | 1811074458867204096 |
|---|---|
| author | Vutukuru, Mythili Valiant, Paul Kopparty, Swastik Balakrishnan, Hari |
| author2 | Networks and Mobile Systems |
| author_facet | Networks and Mobile Systems Vutukuru, Mythili Valiant, Paul Kopparty, Swastik Balakrishnan, Hari |
| author_sort | Vutukuru, Mythili |
| collection | MIT |
| description | The Border Gateway Protocol (BGP), the current inter domain routing protocol in the Internet, has two modes of operation: eBGP (External BGP), used to exchange routing information between autonomous systems, and iBGP (Internal BGP), used to propagate that information within an autonomous system (AS). This paper focuses on the construction of an iBGP session configuration that guarantees two correctness properties - loop-free forwarding paths and complete visibility to all eBGP-learned best routes - while attempting to minimize the number of iBGP sessions (for scalability) and ensuring that the constructed configuration guarantees the two correctness properties even in the face of link failures and IGPpath changes. Our algorithm constructs an iBGP configuration based on route reflectors, a commonly used way to control the number of iBGP sessions. The algorithm, BGPSep, uses the notion of a graph separator, a (small) set of nodes that partition a graph into connected components of roughly equal sizes, recursively applies this idea to the connected components, and produces a route reflector hierarchy and the associated iBGP sessions. We prove thatBGPSep guarantees the desired correctness properties, andevaluate an implementation of the BGPSep algorithm on several real-world and simulated network topologies. Across these topologies, we find that the number of iBGP sessions with is afactor of 2.5 to 5 times smaller than with a \"full mesh\" iBGP, while guaranteeing the desired correctness properties. |
| first_indexed | 2024-09-23T09:49:46Z |
| id | mit-1721.1/30560 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:49:46Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/305602019-04-12T08:26:07Z How to Construct a Correct and Scalable iBGP Configuration Vutukuru, Mythili Valiant, Paul Kopparty, Swastik Balakrishnan, Hari Networks and Mobile Systems The Border Gateway Protocol (BGP), the current inter domain routing protocol in the Internet, has two modes of operation: eBGP (External BGP), used to exchange routing information between autonomous systems, and iBGP (Internal BGP), used to propagate that information within an autonomous system (AS). This paper focuses on the construction of an iBGP session configuration that guarantees two correctness properties - loop-free forwarding paths and complete visibility to all eBGP-learned best routes - while attempting to minimize the number of iBGP sessions (for scalability) and ensuring that the constructed configuration guarantees the two correctness properties even in the face of link failures and IGPpath changes. Our algorithm constructs an iBGP configuration based on route reflectors, a commonly used way to control the number of iBGP sessions. The algorithm, BGPSep, uses the notion of a graph separator, a (small) set of nodes that partition a graph into connected components of roughly equal sizes, recursively applies this idea to the connected components, and produces a route reflector hierarchy and the associated iBGP sessions. We prove thatBGPSep guarantees the desired correctness properties, andevaluate an implementation of the BGPSep algorithm on several real-world and simulated network topologies. Across these topologies, we find that the number of iBGP sessions with is afactor of 2.5 to 5 times smaller than with a \"full mesh\" iBGP, while guaranteeing the desired correctness properties. 2005-12-22T02:33:41Z 2005-12-22T02:33:41Z 2005-08-03 MIT-CSAIL-TR-2005-049 MIT-LCS-TR-996 http://hdl.handle.net/1721.1/30560 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 13 p. 18855558 bytes 842183 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Vutukuru, Mythili Valiant, Paul Kopparty, Swastik Balakrishnan, Hari How to Construct a Correct and Scalable iBGP Configuration |
| title | How to Construct a Correct and Scalable iBGP Configuration |
| title_full | How to Construct a Correct and Scalable iBGP Configuration |
| title_fullStr | How to Construct a Correct and Scalable iBGP Configuration |
| title_full_unstemmed | How to Construct a Correct and Scalable iBGP Configuration |
| title_short | How to Construct a Correct and Scalable iBGP Configuration |
| title_sort | how to construct a correct and scalable ibgp configuration |
| url | http://hdl.handle.net/1721.1/30560 |
| work_keys_str_mv | AT vutukurumythili howtoconstructacorrectandscalableibgpconfiguration AT valiantpaul howtoconstructacorrectandscalableibgpconfiguration AT koppartyswastik howtoconstructacorrectandscalableibgpconfiguration AT balakrishnanhari howtoconstructacorrectandscalableibgpconfiguration |