The Border Gateway Protocol (BGP) is the interdomain routing protocol used in the Internet. Unfortunately, BGP cannot be guaranteed to converge. BGP convergence issues have been studied using a graph theoretic model of BGP called the Stable Paths Problem (SPP). It has been shown that some instances of SPP have no solution and this implies that the corresponding instances of BGP will fail to converge. However, we define a fractional version of SPP and show that any instance of SPP is guaranteed to have a fractional solution. The proof is based on the game theoretic result known as Scarf's Lemma. We then show that a number of well-known graph theoretic problems are actually subproblems of (fractional) SPP. No previous knowledge of BGP or interdomain routing will be assumed; the talk will begin with a brief overview of these issues.
This is joint work with Penny Haxell at University of Waterloo.