Slow convergence in the Internet can be directly attributed 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 this talk, we describe why the path exploration cannot be countered effectively within the existing BGP framework, and propose a simple, novel mechanism using forward edge sequence number to annotate the AS Paths with additional information. Then, 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, our solution 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 improvement in routing convergence, compared to BGP and other existing solutions.

Speaker Bio:

Zhi-Li Zhang received the B.S. degree in computer science from Nanjing University, China, in 1986 and his M.S. and Ph.D. degrees in computer science from the University of Massachusetts in 1992 and 1997. In 1997 he joined the Computer Science and Engineering faculty at the University of Minnesota, where he is currently an Associate Professor. Dr. Zhang's research interests include computer communications and networks, especially the QoS, routing and security issues in Internet, wireless networks and multimedia systems. He is co-recipient of an ACM SIGMETRICS best paper award and an IEEE ICNP best paper award. Dr. Zhang is an associate editor for IEEE/ACM Transactions on Networking and Computer Networks. He has served on technical program committees for many conferences/workshops including ACM SIGCOMM,SIGMETRICS, IEEE INFOCOM and IEEE ICNP. He is/was co-chair for IEEE INFOCOM 2006 and IWQoS'04. Dr. Zhang received the National Science Foundation CAREER Award in 1997, and U. of Minnesota McKnight Land-grant Professorship in 2000.