Quantifying path exploration in the internet

Ricardo Oliveira, Beichuan Zhang, Dan Pei, Rafit Izhak-Ratzin, Lixia Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

45 Scopus citations


A number of previous measurement studies [10, 12, 17] 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 [21, 15, 4, 20, 5]. However all the previous measurements were conducted over a small number of testing pre-fixes. There has been no systematic study to quantify the pervasiveness of BGP slow convergence in the operational Internet, nor there is any known effort to deploy any of the proposed solutions. In this paper we present our measurement results from identifying 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 ISPs observe less path exploration, hence shorter convergence delays than routers in edge ASes, and prefixes originatd from tier-1 ISPs also experience less path exploration than those originated from edge ASes. Our data also shows that the convergence time of route fail-over events is similar to that of new route announcements, and significantly shorter than that of route failures, which confirms our earlier analytical results [19]. In addition, we also developed a usage-time based path preference inference method which can be used by future studies of BGP dynamics.

Original languageEnglish (US)
Title of host publicationProceedings of the 2006 ACM SIGCOMM Internet Measurement Conference, IMC 2006
Number of pages14
StatePublished - 2006
Event6th ACM SIGCOMM on Internet Measurement Conference, IMC 2006 - Rio de Janeriro, Brazil
Duration: Oct 25 2006Oct 27 2006

Publication series

NameProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC


Other6th ACM SIGCOMM on Internet Measurement Conference, IMC 2006
CityRio de Janeriro


  • BGP
  • Path exploration
  • Routing convergence
  • Slow convergence

ASJC Scopus subject areas

  • Engineering(all)


Dive into the research topics of 'Quantifying path exploration in the internet'. Together they form a unique fingerprint.

Cite this