The Origin of Power Laws in Internet TopologiesRevisitedQian Chen Hyunseok Chang Ramesh Govindan Sugih JaminDepartment of EECS Department of EECS ICSI Department of EECSUniversity of Michigan University of Michigan 1947 Center St., Suite 600 University of MichiganAnn Arbor, MI 48109-2122 Ann Arbor, MI 48109-2122 Berkeley, CA 94704-1198 Ann Arbor, MI [email protected] [email protected] [email protected] [email protected] J. Shenker Walter WillingerACIRI/ICSI AT&T Labs-Research1947 Center St., Suite 600 180 Park Ave.Berkeley, CA 94704-1198 Florham Park, NJ [email protected] [email protected]— In a recent paper, Faloutsos et al. [1] found that the interAutonomous System (AS) topology exhibits a power-law vertex degree dis-tribution. This result was quite unexpected in the networking communityand stirred significant interest in exploring the possible causes of this phe-nomenon. The work of Barabasi and Albert [2] and its application to net-work topology generation in the work of Medina et al. [3] have exploreda promising class of models that yield strict power-law vertex degree dis-tributions. In this paper, we re-examine the BGP measurements that formthe basis for the results reported in [1]. We find that by their very nature(i.e., being strictly BGP-based), the data provides a very incomplete pictureof Internet connectivity at the AS level. The AS connectivity maps con-structed from this data (the original maps) typically miss 20–50% or evenmore of the physical links in AS maps constructed using additional sources(the extended maps). Subsequently, we find that while the vertex degree dis-tributions resulting from the extended maps are heavy-tailed, they deviatesignificantly from a strict power law. Finally, we show that available his-torical data does not support the connectivity-based dynamics assumed in[2]. Together, our results suggest that the Internet topology at the AS levelmay well have developed over time following a very different set of growthprocesses than those proposed in [2].I. INTRODUCTIONRecent studies concerning Internet connectivity at the levelof Autonomous Systems (ASs) have attracted considerable atten-tion. For example, the empirically derived power-law relation-ships in the Internet’s AS topology, originally due to Faloutsoset al. [1], suggest that the random and hierarchical graph mod-els that have until recently been used to generate Internet-liketopologies may not capture critical features or relevant struc-tures inherent in actual networks. Pursuing a very different(and—for the networking community—novel) class of dynamicgraph models, Barabasi and Albert [2] show that such power-lawgraphs can arise from a simple dynamic model that combines in-cremental growth with a preference for new nodes to connect toexisting ones that are already well connected (subsequently re-ferred to as the BA model). Citing [1], Barabasi and Albert alsostate that this intuitively appealing growth model applies to theInternet’s AS graph and therefore explains why AS graphs ex-hibit power-law vertex degree distributions. In this paper, we re-visit the measurements used in the original discovery of powerlaws in AS topologies [1]. In re-examining this data, we askthe following two questions: (1) Are the measurements used inThis project is funded in part by NSF grant number ANI-0082287 and byONR grant number N000140110617. Sugih Jamin is further supported by theNSF CAREER Award ANI-9734145, the Presidential Early Career Award forScientists and Engineers (PECASE) 1998, and the Alfred P. Sloan FoundationResearch Fellowship 2001. Additional funding is provided by AT&T Research,and by equipment grants from Sun Microsystems Inc. and Compaq Corp.[1] sufficiently complete to establish a strict power law relation-ship for AS vertex degree distributions? and (2) How can theavailable measurements be used to establish the validity of In-ternet topology models at the AS level such as those proposedby Barabasi and Albert [2]?The measurements that form the basis for the original power-law study [1] consist of BGP routing tables collected by theroute server route-views.oregon-ix.net (henceforth,the Oregon route server) [4]. The use of this data for the pur-pose of studying the Internet’s AS connectivity structure raisesthe following important issue. There is no a priori reason tobelieve that BGP AS paths completely capture the AS topol-ogy. In particular, because of the way BGP routing works, aninstantaneous snapshot of the BGP routing table may not re-veal links belonging to less preferred or non-advertised paths.Consequently, the AS connectivity structure gleaned from theOregon route server data may provide a very incomplete pictureof the physical connectivity that exist in the actual Internet. Amore complete picture of Internet connectivity may potentiallyquestion or even invalidate some of the earlier findings. In Sec-tion II, we provide qualitative and quantitative insight into thedegree of incompleteness of AS connectivity graphs constructedfrom BGP routing tables obtained solely from the Oregon routeserver. In particular, we observe that while the measured ASvertex degrees are clearly highly variable in the sense that theytypically vary over 3–4 orders of magnitude, the vertex degreedistributions resulting from more complete AS graphs do notconform to strict power-law distributions but are consistent withthe more flexible class of heavy-tailed distributions that includethe Weibull distribution as well as the family of distributionswhere only the tail behavior is characterized by a power law butwhere the rest of the distribution can be essentially arbitrary.In Section III we outline a general framework for validatingthe explanatory aspect of any proposed AS-level connectivitymodel. The discovery of an empirical phenomenon, such asthe one reported in [1], is often followed by proposed expla-nations. Such proposed explanations may put forth a dynamicalmodel that identifies a set of more elementary mechanisms asthe main cause of the said phenomenon. A critical feature ofthe validation framework outlined in Section III is that it “closesthe loop” between the discovery process and the proposed ex-planatory model. This “closing of the loop” is achieved by re-quiring that the proposed model also conforms to measured dataat the level where the more elementary mechanisms are verifi-able. In the case at hand, we want to
View Full Document
Unlocking...