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}
}