Limiting path exploration in BGP Export

@inproceedings{citeulike:866514, abstract = {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 paper, we describe why path exploration cannot be countered effectively within the existing BGP framework, and propose a simple, novel mechanism - forward edge sequence numbers - to annotate the AS paths with additional "path dependency" information. We then develop an enhanced path vector algorithm, EPIC, shown to limit path exploration and lead to faster convergence. In contrast to other solutions, ours 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.}, author = {Chandrashekar, J. and Duan, Z. and Zhang, Z. L. and Krasky, J.}, citeulike-article-id = {866514}, citeulike-linkout-0 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1498520}, journal = {INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE}, keywords = {bpg, exploration, path}, pages = {2337--2348 vol. 4}, posted-at = {2006-09-24 07:37:47}, priority = {0}, title = {Limiting path exploration in BGP}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1498520}, volume = {4}, year = {2005} }

TY - CONF ID - citeulike:866514 L3 - citeulike-article-id:866514 N2 - 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 paper, we describe why path exploration cannot be countered effectively within the existing BGP framework, and propose a simple, novel mechanism - forward edge sequence numbers - to annotate the AS paths with additional "path dependency" information. We then develop an enhanced path vector algorithm, EPIC, shown to limit path exploration and lead to faster convergence. In contrast to other solutions, ours 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. JF - INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE EP - 2348 vol. 4 TI - Limiting path exploration in BGP VL - 4 SP - 2337 KW - bpg KW - exploration KW - path AU - Chandrashekar, J AU - Duan, Z AU - Zhang, ZL AU - Krasky, J PY - 2005/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1498520 ER -