TY - JOUR
T1 - Quantifying path exploration in the Internet
AU - Oliveira, Ricardo
AU - Zhang, Beichuan
AU - Pei, Dan
AU - Zhang, Lixia
N1 - Funding Information:
Manuscript received November 29, 2006; revised September 19, 2007; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor Z.-L. Zhang. Current version published April 15, 2009. This material is based upon work supported by the Defense Advanced Research Projects Agency (DARPA) under Contract N66001-04-1-8926 and by the National Science Foundation (NSF) under Contract ANI-0221453. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the DARPA or NSF.
PY - 2009
Y1 - 2009
N2 - Previous measurement studies have shown the existence of path exploration and slow convergence in the global Internet routing system, and a number of protocol enhancements have been proposed to remedy the problem. However, existing measurements were conducted only over a small number of testing prefixes. There has been no systematic study to quantify the pervasiveness of Border Gateway Protocol (BGP) slow convergence in the operational Internet, nor any known effort to deploy any of the proposed solutions. In this paper, we present our measurement results that identify BGP slow convergence events across the entire global routing table. Our data shows that the severity of path exploration and slow convergence varies depending on where prefixes are originated and where the observations are made in the Internet routing hierarchy. In general, routers in tier-1 Internet service providers (ISPs) observe less path exploration, hence they experience shorter convergence delays than routers in edge ASs; prefixes originated from tier-1 ISPs also experience less path exploration than those originated from edge ASs. Furthermore, our data show that the convergence time of route fail-over events is similar to that of new route announcements and is significantly shorter than that of route failures. This observation is contrary to the widely held view from previous experiments but confirms our earlier analytical results. Our effort also led to the development of a path-preference inference method based on the path usage time, which can be used by future studies of BGP dynamics.
AB - Previous measurement studies have shown the existence of path exploration and slow convergence in the global Internet routing system, and a number of protocol enhancements have been proposed to remedy the problem. However, existing measurements were conducted only over a small number of testing prefixes. There has been no systematic study to quantify the pervasiveness of Border Gateway Protocol (BGP) slow convergence in the operational Internet, nor any known effort to deploy any of the proposed solutions. In this paper, we present our measurement results that identify BGP slow convergence events across the entire global routing table. Our data shows that the severity of path exploration and slow convergence varies depending on where prefixes are originated and where the observations are made in the Internet routing hierarchy. In general, routers in tier-1 Internet service providers (ISPs) observe less path exploration, hence they experience shorter convergence delays than routers in edge ASs; prefixes originated from tier-1 ISPs also experience less path exploration than those originated from edge ASs. Furthermore, our data show that the convergence time of route fail-over events is similar to that of new route announcements and is significantly shorter than that of route failures. This observation is contrary to the widely held view from previous experiments but confirms our earlier analytical results. Our effort also led to the development of a path-preference inference method based on the path usage time, which can be used by future studies of BGP dynamics.
KW - AS topology completeness
KW - Border Gateway Protocol (BGP)
KW - Inter-domain routing
KW - Internet topology
UR - http://www.scopus.com/inward/record.url?scp=65549112057&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=65549112057&partnerID=8YFLogxK
U2 - 10.1109/TNET.2009.2016390
DO - 10.1109/TNET.2009.2016390
M3 - Article
AN - SCOPUS:65549112057
SN - 1063-6692
VL - 17
SP - 445
EP - 458
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 2
ER -