TY - GEN
T1 - How to construct a correct and scalable iBGP configuration
AU - Vutukuru, Mythili
AU - Valiant, Paul
AU - Kopparty, Swastik
AU - Balakrishnan, Hari
PY - 2006
Y1 - 2006
N2 - The Internet's current interdomain routing protocol, BGP (Border Gateway Protocol), 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). In a "full mesh" iBGP configuration, every router has a BGP session with every border router in the AS. Because a full mesh configuration has a large number of iBGP sessions and does not scale well, configurations based on route reflectors are commonly used for intra-AS route dissemination [2]. Unfortunately, route reflector configurations violate important correctness properties [12], including loop-free forwarding and complete visibility to all eBGP-learned best routes, especially in the face of router and link failures. This paper presents and analyzes the first (to our knowledge) algorithm, BGPSep, to construct an iBGP session configuration that is both correct and more scalable than a full mesh. BGPSep uses the notion of a graph separator - a small set of nodes whose removal partitions a graph into connected components of roughly equal sizes-to choose route reflectors and iBGP sessions in a way that guarantees correctness. We evaluate an implementation of the BGPSep algorithm on several real-world and simulated network topologies and find that iBGP configurations generated by BGPSep have between 2.5 to 5× fewer iBGP sessions than a full mesh.
AB - The Internet's current interdomain routing protocol, BGP (Border Gateway Protocol), 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). In a "full mesh" iBGP configuration, every router has a BGP session with every border router in the AS. Because a full mesh configuration has a large number of iBGP sessions and does not scale well, configurations based on route reflectors are commonly used for intra-AS route dissemination [2]. Unfortunately, route reflector configurations violate important correctness properties [12], including loop-free forwarding and complete visibility to all eBGP-learned best routes, especially in the face of router and link failures. This paper presents and analyzes the first (to our knowledge) algorithm, BGPSep, to construct an iBGP session configuration that is both correct and more scalable than a full mesh. BGPSep uses the notion of a graph separator - a small set of nodes whose removal partitions a graph into connected components of roughly equal sizes-to choose route reflectors and iBGP sessions in a way that guarantees correctness. We evaluate an implementation of the BGPSep algorithm on several real-world and simulated network topologies and find that iBGP configurations generated by BGPSep have between 2.5 to 5× fewer iBGP sessions than a full mesh.
UR - http://www.scopus.com/inward/record.url?scp=33750347050&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33750347050&partnerID=8YFLogxK
U2 - 10.1109/INFOCOM.2006.122
DO - 10.1109/INFOCOM.2006.122
M3 - Conference contribution
AN - SCOPUS:33750347050
SN - 1424402212
SN - 9781424402212
T3 - Proceedings - IEEE INFOCOM
BT - Proceedings - INFOCOM 2006
T2 - INFOCOM 2006: 25th IEEE International Conference on Computer Communications
Y2 - 23 April 2006 through 29 April 2006
ER -