Computer Science

Colloquium Details

The Stable Paths Problem as a Model of BGP Routing

Abstract

Inter-domain routing in the Internet is currently implemented with the Border Gateway Protocol (BGP). This protocol allows every autonomous administrative domain to define local routing policies that are consistent with its own interests. Such locally defined policies can interact in ways that cause various kinds of global routing anomalies --- nondeterministic routing and protocol divergence ("live lock") --- and these anomalies can span multiple autonomous domains making them very difficult to debug and correct. Analysis of BGP is complicated by the fact that route messages carry a number of semantically rich attributes that play a role in the rather complex BGP route selection algorithm and in the implementation of local routing policies. The talk will begin with a short tutorial on BGP, and so no previous knowledge will be assumed (don't panic!).

I'll present a simple static semantics for BGP called the Stable Paths Problem (SPP). This formalism can be viewed as a simple kind of game or as a generalization of the stable matching problem. I'll argue that the BGP protocol can be modeled as a distributed algorithm that attempts to solve instances of the Stable Paths Problem. If the Stable Paths Problem has no solution, the protocol will not converge. The protocol can also diverge when there is a solution but it gets "trapped" down a blind alley. Nondeterministic routing is associated with Stable Path Problems that have multiple solutions. I'll also show that several interesting questions related to SPP (and BGP) solvability are NP-complete.

This talk will survey joint work that I've done with Lixin Gao (UMASS), Jennifer Rexford (AT&T Research) , F. Bruce Shepherd (Bell Labs), and Gordon Wilfong (Bell Labs). Links to papers can be found at http://www.research.att.com/~griffin/bgpresearch.html. An extended BGP tutorial can be found at http://www.research.att.com/~griffin/sigcomm2001_bgp_tutorial/abstract.html