LCS Publication Details
Publication Title: How to Construct a Correct and Scalable iBGP Configuration
Publication Author: Vutukuru, Mythili
Additional Authors: Paul Valiant, Swastik Kopparty, Hari Balakrishnan
LCS Document Number: MIT-LCS-TR-996
Publication Date: 8-3-2005
LCS Group: Networks and Mobile Systems
Additional URL:
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 IGP path 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 that BGPSep guarantees the desired correctness properties, and evaluate 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 a factor of 2.5 to 5 times smaller than with a \"full mesh\" iBGP, while guaranteeing the desired correctness properties.
To obtain this publication:

To purchase a printed copy of this publication please contact MIT Document Services.