Research Abstracts - 2006

How To Construct a Correct and Scalable iBGP Configuration

Mythili Vutukuru, Paul Valiant, Swastik Kopparty, & Hari Balakrishnan

Project Overview

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 iBGP 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. In such configurations, a subset of BGP routers are designated as route reflectors, providing their best routes to other routers configured as their clients. Large networks use route reflectors hierarchically, but they are often configured in an unprincipled fashion. As a result, researchers have found that many correctness properties can be violated leading to routing anomalies like forwarding loops and sub-optimal paths [1].

Although previous work on iBGP configuration correctness [1] gives sufficient conditions to check if a given iBGP configuration is correct, the problem of constructing correct and scalable iBGP configurations has not received much attention. Our work [2] proposes 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 iBGP. 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, while maintaining all the correctness properties of a full-mesh iBGP.

References:

[1] Timothy G. Griffin and Gordon Wilfong. In Proc. ACM SIGCOMM, pp. 17-29, Pittsburg, PA, August 2004.

[2] Mythili Vutukuru, Paul Valiant, Swastik Kopparty, and Hari Balakrishnan. In Proc. IEEE INFOCOM, Barcelona, Spain, April 2006.