1:30, Thursday, February 19,
2004
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.