IMA Complex Systems Seminar

1:30, Thursday, February 19, 2004



Understanding and Limiting BGP Instabilities


Zhi-Li Zhang

Department of Computer Science

University of Minnesota

Minneapolis, MN 55455-0159


Slow convergence in the Internet can be directly attributable to the path exploration phenomenon, inherent in all path vector protocols. The root cause for path exploration is the dependency among paths propagated through the network. Addressing this problem in BGP is particularly difficult as the AS Paths exchanged between BGP routers are highly summarized.


In the first part of this talk, we will describe why the path exploration cannot be countered effectively within the existing BGP framework, and propose a simple, novel mechanism -- forward edge sequence number to annotate the AS Paths with additional information. With this mechanism, we develop an enhanced path vector algorithm, EPIC, which can be shown to limit path exploration and lead to faster convergence. In contrast to other solutions, EPIC is shown to be correct on a very general model of Internet topology and BGP operation. Using theoretical analysis and simulations, we demonstrate that EPIC can achieve a dramatic reduction in routing convergence time, as compared to BGP and other existing solutions.


In the second part of the talk, we will briefly discuss some of initial work on identifying locations and causes of BGP instabilities using observed BGP updates from one or multiple vantage points, and the difficulties we encountered. Perhaps more innovative or sophisticated approaches are necessary, and this is where we would like to obtain some help from mathematicians/statisticians.