IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 17, NO. 2, APRIL 2009 445Quantifying Path Exploration in the InternetRicardo Oliveira, Member, IEEE, Beichuan Zhang, Dan Pei, and Lixia ZhangAbstract—Previous measurement studies have shown the exis-tence of path exploration and slow convergence in the global In-ternet routing system, and a number of protocol enhancementshave been proposed to remedy the problem. However, existing mea-surements were conducted only over a small number of testing pre-fixes. There has been no systematic study to quantify the perva-siveness of Border Gateway Protocol (BGP) slow convergence inthe operational Internet, nor any known effort to deploy any of theproposed solutions.In this paper, we present our measurement results that identifyBGP slow convergence events across the entire global routing table.Our data shows that the severity of path exploration and slow con-vergence varies depending on where prefixes are originated andwhere the observations are made in the Internet routing hierarchy.In general, routers in tier-1 Internet service providers (ISPs) ob-serve less path exploration, hence they experience shorter conver-gence delays than routers in edge ASs; prefixes originated fromtier-1 ISPs also experience less path exploration than those origi-nated from edge ASs. Furthermore, our data show that the conver-gence time of route fail-over events is similar to that of new routeannouncements and is significantly shorter than that of route fail-ures. This observation is contrary to the widely held view from pre-vious experiments but confirms our earlier analytical results. Oureffort also led to the development of a path-preference inferencemethod based on the path usage time, which can be used by futurestudies of BGP dynamics.Index Terms—AS topology completeness, Border Gateway Pro-tocol (BGP), inter-domain routing, Internet topology.I. INTRODUCTIONTHE Border Gateway Protocol (BGP) is the routing pro-tocol used in the global Internet. A number of previousanalytical and measurement studies [1]–[3] have shown the ex-istence of BGP path exploration and slow convergence in theoperational Internet routing system, which can potentially leadto severe performance problems in data delivery. Path explo-ration suggests that, in response to path failures or routing policychanges, some BGP routers may try a number of transient pathsManuscript received November 29, 2006; revised September 19, 2007; ap-proved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor Z.-L. Zhang.Current version published April 15, 2009. This material is based upon worksupported by the Defense Advanced Research Projects Agency (DARPA) underContract N66001-04-1-8926 and by the National Science Foundation (NSF)under Contract ANI-0221453. Any opinions, findings, and conclusions or rec-ommendations expressed in this material are those of the authors and do notnecessarily reflect the views of the DARPA or NSF.R. Oliveira and L. Zhang are with the Computer Science Department, Univer-sity of California, Los Angeles, CA 90095 USA (e-mail: [email protected];[email protected]).B. Zhang is with the Computer Science Department, University of Arizona,Tucson, AZ 85721 USA (e-mail: [email protected]).D. Pei is with AT&T Labs–Research, Florham Park, NJ 07932 USA (e-mail:[email protected]).Color versions of one or more of the figures in this paper are available onlineat http://ieeexplore.ieee.org.Digital Object Identifier 10.1109/TNET.2009.2016390Fig. 1. Path exploration triggered by a fail-down event.before selecting a new best path or declaring unreachability toa destination. Consequently, a long time period may elapse be-fore the whole network eventually converges to the final deci-sion, resulting in slow routing convergence. An example of pathexploration is depicted in Fig. 1, where node C’s original pathto node E (path 1) fails due to the failure of link D–E. C reactsto the failure by attempting two alternative paths (paths 2 and 3)before it finally gives up. The experiments in [1]–[3] show thatsome BGP routers can spend up to several minutes exploring alarge number of alternate paths before declaring a destinationunreachable.The analytical models used in the previous studies tend to rep-resent worst case scenarios of path exploration [1], [2], and themeasurement studies have all been based on controlled exper-iments with a small number of beacon prefixes. In the Internetoperational community, there exist various different views re-garding whether BGP path exploration and slow convergencerepresent a significant threat to the network performance, orwhether the severity of the problem, as shown in simulationsand controlled experiments, would be rather rare in practice. Asystematic study is needed to quantify the pervasiveness and sig-nificance of BGP slow convergence in the operational routingsystem, which is the goal of this paper.In this paper, we provide measurement results from the BGPlog data collected by RouteViews [4] and RIPE [5]. For all thedestination prefixes announced in the Internet, we cluster theirBGP updates into routing events and classify the events intodifferent convergence classes. We then characterize path explo-ration and convergence time of each class of events. The resultsreported in this paper are obtained from BGP logs of Januaryand February 2006, which are representative of data we haveexamined during other time periods. The main contributions ofthis paper are summarized as follows.• We provide the first quantitative assessment on path explo-rations for the entire Internet destination prefixes. Our re-1063-6692/$25.00 © 2009 IEEEAuthorized licensed use limited to: Barbara Lange. Downloaded on April 15, 2009 at 01:13 from IEEE Xplore. Restrictions apply.446 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 17, NO. 2, APRIL 2009sults confirmed the wide existence of path exploration andslow convergence in the Internet but also revealed that theextent of the problem depends on where a prefix is orig-inated and where the observation is made in the Internetrouting hierarchy. When observed from a top-tier Internetservice provider (ISP), there is relatively little path explo-ration, and this is especially true when the prefixes beingobserved are also originated from some other top-tier ISPs.On the other hand, an observer in an edge network is likelyto notice a much higher degree of path exploration and slowconvergence, especially when the prefixes being observedare originated