How to Construct a Correct and Scalable iBGP Configuration

Mythili Vutukuru, Paul Valiant, Swastik Kopparty, Hari Balakrishnan
IEEE INFOCOM, Barcelona, Spain, April 2006

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. Unfortunately, route reflector configurations violate important correctness properties, 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 times fewer iBGP sessions than a full mesh.

[PDF (233KB)] [PostScript (343KB)]

Bibtex Entry:

@inproceedings{vutukuru2006how,
   author =       "Mythili Vutukuru and Paul Valiant and Swastik Kopparty and Hari Balakrishnan",
   title =        "{How to Construct a Correct and Scalable iBGP Configuration}",
   booktitle =    {IEEE INFOCOM},
   year =         {2006},
   month =        {April},
   address =      {Barcelona, Spain}
}