1Twelve Years in the Evolution of the InternetEcosystemAmogh Dhamdhere Constantine DovrolisCAIDA Georgia [email protected] [email protected]—Our goal is to understand the evolution of the Au-tonomous System (AS) ecosystem over the last 12 years. Instead offocusing on abstract topological properties, we classify ASes intoa number of types depending on their function and business type.Further, we consider the semantics of inter-AS links – customer-provider versus peering relations. We find that the availablehistoric datasets from RouteViews and RIPE are not sufficient toinfer the evolution of peering links, and so we restrict our focus tocustomer-provider links. Our findings highlight some importanttrends in the evolution of the Internet over the last 12 years, andhint at what the Internet is heading towards. After an exponentialincrease phase until 2001, the Internet has settled into a slowerexponential growth in terms of both ASes and inter-AS links. Thegrowth is mostly due to enterprise networks and content/accessproviders at the periphery of the Internet. The average pathlength remains almost constant, mostly due to the increasingmultihoming degree of transit and content/access providers. TheAS types differ significantly from each other with respect to theirrewiring activity; content/access providers are the most active.A few large transit providers act as “attractors” or “repellers”of customers. For many providers, strong attractiveness precedesstrong repulsiveness by 3-9 months. Finally, in terms of regionalgrowth, we find that the AS ecosystem is now larger and moredynamic in Europe than in North America.I. INTRODUCTIONThe Internet, as a network of Autonomous Systems (ASes),resembles in several ways a natural ecosystem. ASes of dif-ferent sizes, functions, and business objectives form a numberof AS species that interact to jointly form what we know asthe global Internet. ASes engage in competitive transit (orcustomer-provider) relations, and also in symbiotic peeringrelations1. These relations, which are represented as inter-AS logical links, transfer not only traffic but also economicvalue between ASes. The Internet AS ecosystem is highlydynamic, experiencing growth (birth of new ASes), rewiring(changes in the connectivity of existing ASes), as well asdeaths (of existing ASes). The dynamics of the AS ecosystemare determined both by external “environmental” factors (suchas the state of the global economy or the popularity of newInternet applications) and by complex incentives and objec-tives of each AS. Specifically, ASes attempt to optimize theirutility or financial gains by dynamically changing, directlyThe AS topology data used in this paper is available atwww.cc.gatech.edu/˜amogh/topology.htmlThis work was supported by NSF awards CNS-0347374 (CAREER) andCNS-0831848.1We refer to “settlement free interconnection” as a “peering relation” and“paid transit” as a “customer-provider” relation.or indirectly, the ASes they interact with. For instance, theobjective of a transit provider may be to maximize its profit,and it may approach this goal through competitive pricing andselective peering. The objective of a content provider, on theother hand, may be to have highly reliable Internet accessand minimal transit expenses, and it may pursue these goalsthrough aggressive multihoming and an open peering policy.Our study is motivated by the desire to better understandthis complex ecosystem, the behavior of entities that constituteit (ASes), and the nature of interactions between those entities(AS links). How has the Internet ecosystem been growing? Isgrowth more important than rewiring in terms of the formationof new links? Is the population of transit providers increasing(implying diversification of the transit market) or decreasing(consolidation of the transit market)? Given that the Internetgrows in size, does the average AS-path length also increase?Which ASes engage in aggressive multihoming? What is thepreferred type of transit provider for AS customers? WhichASes tend to constantly adjust their set of providers? Are thereregional differences in how the Internet evolves? These aresome of the questions we ask in this paper.Understanding the evolution of the Internet ecosystem isimportant for several reasons. First, there is a need to developbottom-up models of Internet topology evolution that capturethe interactions between autonomous agents (ASes). As such,we need to study the differences in the business function andincentives of AS types that form this ecosystem. Second, un-derstanding the evolution of the Internet is critical for studyingthe performance of protocols and applications over time. Forinstance, to answer the question “How will BGP perform 10years from now?” we first need to answer the question “Howwill the Internet look 10 years from now?”. Third, there isa need to generate synthetic AS graphs for simulation andanalysis. A study of the evolution of the Internet can provideinputs to such topology generators, e.g., the types of ASes inthe Internet and their topological properties (both static anddynamic) over time. Finally, in light of the recent interest inre-designing the Internet with “clean-slate” approaches, it iscrucial to understand how the existing Internet has evolved.Doing so could help us design new architectures that havean intrinsic capability to evolve towards desirable economic,reliability and performance conditions.There is an extensive literature on AS-level topology mea-surement and modeling (reviewed in detail in Section VIII). Alarge portion of that literature, however, takes a graph-theoreticperspective, viewing all ASes as nodes in a graph and all inter-2AS relations as edges, without considering the type of relation(customer-provider versus peering) or the role of the partic-ipating ASes (customer versus provider). Viewing all ASesas the same type of node ignores the major differences in thefunction and objectives of different ASes. Further, even thoughmost of the previous work on AS-level topology modelingmentions the terms ‘evolution” or “dynamics”, the main focushas been on measurements and modeling of growth, ignoringrewiring. The latter is very important, however, as it representsthe attempt of individual ASes to optimize their connectivity.Finally, most of the earlier work on AS-level topologies hasfocused on macroscopic properties and metrics, such as thedegree