A First-Principles Approach to Understanding theInternet’s Router-level TopologyLun LiCalifornia Instituteof [email protected] AldersonCalifornia Instituteof [email protected] WillingerAT&T [email protected] DoyleCalifornia Instituteof [email protected] detailed understanding of the many facets of the Internet’s topo-logical structure is critical for evaluating the performance of net-working protocols, for assessing the effectiveness of proposed tech-niques to protect the network from nefarious intrusions and at-tacks, or for developing improved designs for resource provision-ing. Previous studies of topology have focused on interpreting mea-surements or on phenomenological descriptions and evaluation ofgraph-theoretic properties of topology generators. We propose acomplementary approach of combining a more subtle use of statis-tics and graph theory with a first-principles theory of router-leveltopology that reflects practical constraints and tradeoffs. Whilethere is an inevitable tradeoff between model complexity and fi-delity, a challenge is to distill from the seemingly endless list ofpotentially relevant technological and economic issues the featuresthat are most essential to a solid understanding of the intrinsic fun-damentals of network topology. We claim that very simple modelsthat incorporate hard technological constraints on router and linkbandwidth and connectivity, together with abstract models of userdemand and network performance, can successfully address thischallenge and further resolve much of the confusion and contro-versy that has surrounded topology generation and evaluation.Categories and Subject DescriptorsC.2.1 [Communication Networks]: Architecture and Design—topologyGeneral TermsPerformance, Design, EconomicsKeywordsNetwork topology, degree-based generators, topology metrics, heuris-tically optimal topology1. INTRODUCTIONRecent attention on the large-scale topological structure of theInternet has been heavily focused on the connectivity of networkPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.SIGCOMM’04, Aug. 30–Sept. 3, 2004, Portland, Oregon, USA.Copyright 2004 ACM 1-58113-862-8/04/0008 ...$5.00.components, whether they be machines in the router-level graph[26, 10] or entire subnetworks (Autonomous Systems) in the AS-level graph [24, 14]. A particular feature of network connectiv-ity that has generated considerable discussion is the prevalence ofheavy-tailed distributions in node degree (e.g., number of connec-tions) and whether or not these heavy-tailed distributions conformto power laws [23, 31, 16, 32]. This macroscopic statistic hasgreatly influenced the generation and evaluation of network topolo-gies. In the current environment, degree distributions and otherlarge-scale statistics are popular metrics for evaluating how repre-sentative a given topology is [42], and proposed topology genera-tors are often evaluated on the basis of whether or not they can re-produce the same types of macroscopic statistics, especially powerlaw-type degree distributions [11].Yet, from our viewpoint, this perspective is both incomplete andin need for corrective action. For one, there exist many differentgraphs having the same distribution of node degree, some of whichmay be considered opposites from the viewpoint of network en-gineering. Furthermore, there are a variety of distinctly differentrandom graph models that might give rise to a given degree distri-bution, and some of these models may have no network-intrinsicmeaning whatsoever. Finally, we advocate here an approach thatis primarily concerned with developing a basic understanding ofthe observed high variability in topology-related measurements andreconciling them with the reality of engineering design. From thisperspective, reproducing abstract mathematical constructs such aspower law distributions is largely a side issue.In this paper, we consider a first-principles approach to under-standing Internet topology at the router-level, where nodes repre-sent routers and links indicate one-hop connectivitybetweenrouters.More specifically, when referring in the following to router-levelconnectivity, we always mean Layer 2, especially when the dis-tinction between Layer 2 vs. Layer 3 issues is important for thepurpose of illuminating the nature of the actual router-level con-nectivity (i.e., node degree) and its physical constraints. For router-level topology issues such as performance, reliability, and robust-ness to component loss, the physical connectivity between routersis more important than the virtual connectivity as defined by thehigher layers of the protocol stack (e.g., IP, MPLS). Moreover, weuse here the notion of “first-principles approach” to describe anattempt at identifying some minimal functional requirements andphysical constraints needed to develop simple models of the In-ternet’s router-level topology that are at the same time illustrative,representative, insightful, and consistent with engineering reality.Far from being exhaustive, this attempt is geared toward account-ing for very basic network-specific aspects, but it can readily beenhanced if some new or less obvious functional requirements orphysical constraints are found to play a critical role. Also, in the3Session 1: Network Geometry and Designprocess of developing models of the Internet router-level connec-tivity that are “as simple as possible, but not simpler”, we focus onsingle ISPs or ASes as the Internet’s fundamental building blocksthat are designed largely in isolation and then connected accordingto both engineering and business considerations.While there are several important factors that contribute to thedesign of an ISP’s router-level topology (e.g., available technol-ogy, economic viability, customer demands, redundancy and geog-raphy) and while opinions will vary about which and how many ofthese factors matter, we focus here on a few critical technologicaland economic considerations that we claim provide insight into thetypes of network topologies that are possible. In