Ten years in the evolution of the internet ecosystem

ABSTRACT

Our goal is to understand the evolution of the Autonomous System (AS) ecosystem over the last decade. Instead of focusing on abstract topological properties, we classify ASes into a number of "species" depending on their function and business type. Further, we consider the semantics of inter-AS links, in terms of customer-provider versus peering relations. We find that the available historic datasets from RouteViews and RIPE are not sufficient to infer the evolution of peering links, and so we restrict our focus to customer-provider links. Our findings highlight some important trends in the evolution of the Internet over the last decade, and hint at what the Internet is heading towards. After an exponential increase phase until 2001, the Internet now grows linearly in terms of both ASes and inter-AS links. The growth is mostly due to enterprise networks and content/access providers at the periphery of the Internet. The average path length remains almost constant mostly due to the increasing multihoming degree of transit and content/access providers. In recent years, enterprise networks prefer to connect to small transit providers, while content/access providers connect equally to both large and small transit providers. The AS species differ significantly from each other with respect to their rewiring 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 precedes strong repulsiveness by 3-9 months. Finally, in terms of regional growth, we find that the AS ecosystem is now larger and more dynamic in Europe than in North America.

REFERENCES

• 1: R. Albert and A. L. Barabasi. Topology of Evolving Networks: Local Events and Universality. Physical Review Letters 85, 5234, 2000.
• 2: A. L. Barabasi and R. Albert. Emergence of Scaling in Random Networks. Science 286 509512, 1999.
• 3: T. Bu and D. Towsley. On Distinguishing Between Internet Power Law Topology Generators. In Proceedings of IEEE Infocom, 2002.
• 4: J. M. Carlson and J. Doyle. Highly Optimized Tolerance: A Mechanism for Power Laws in Designed Systems. Physical Review E 60, 1999.
• 5: Hyunseok Chang , Sugih Jamin , Z. Morley Mao , Walter Willinger, An empirical approach to modeling inter-AS traffic matrices, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.12-12, October 19-21, 2005, Berkeley, CA
• 6: Hyunseok Chang , Sugih Jamin , Walter Willinger, Internet connectivity at the AS-level: an optimization-driven modeling approach, Proceedings of the ACM SIGCOMM workshop on Models, methods and tools for reproducible network research, August 25-27, 2003, Karlsruhe, Germany [doi>10.1145/944773.944780]
• 7: H. Chang, S. Jamin, and W. Willinger. To Peer or Not to Peer: Modeling the Evolution of the Internet's AS-Level Topology. In Proceedings of IEEE Infocom, 2006.
• 8: H. Chang and W. Willinger. Difficulties Measuring the Internet's AS-Level Ecosystem. In Proceedings of the 40th Annual Conference on Information Sciences and Systems, 2006.
• 9: Q. Chen, H. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. The Origin of Power-Laws in Internet Topologies Revisited. In Proceedings of IEEE Infocom, 2002.
• 10: R. Cohen and D. Raz. The Internet Dark Matter - On the Missing Links in the AS Connectivity Map. In Proceedings of IEEE Infocom, 2006.
• 11: Xenofontas Dimitropoulos , Dmitri Krioukov , Marina Fomenkov , Bradley Huffaker , Young Hyun , kc claffy , George Riley, AS relationships: inference and validation, ACM SIGCOMM Computer Communication Review, v.37 n.1, January 2007 [doi>10.1145/1198255.1198259]
• 12: X. Dimitropoulos, D. Krioukov, G. Riley, and K. Claffy. Revealing the Autonomous System Taxonomy: The Machine Learning Approach. In Proceedings of Passive and Active Measurement Conference (PAM), 2006
• 13: N. Economides. The Economics of the Internet Backbone. Handbook of Telecommunications Economics Ed. S. Majumdar, I. Vogelsang, M. Cave. Amsterdam: Elsevier Publishers, 2006.
• 14: Alex Fabrikant , Elias Koutsoupias , Christos H. Papadimitriou, Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.110-122, July 08-13, 2002
• 15: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 16: Lixin Gao, On inferring autonomous system relationships in the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.733-745, December 2001 [doi>10.1109/90.974527]
• 17: Hamed Haddadi , Steve Uhlig , Andrew Moore , Richard Mortier , Miguel Rio, Modeling internet topology dynamics, ACM SIGCOMM Computer Communication Review, v.38 n.2, April 2008 [doi>10.1145/1355734.1355745]
• 18: Y. He, G. Siganos, M. Faloutsos, and S. V. Krishnamurthy. A Systematic Framework for Unearthing the Missing Links: Measurements and Impact. In Proceedings of 4th USENIX/SIGCOMM NSDI, 2007.
• 19: G. Huston. The 32-bit AS Number Report. http://www.potaroo.net/tools/asn32.
• 20: E. F. Keller. Revisiting "Scale-free" Networks. BioEssays 27, Wiley Periodicals Inc., 2005.
• 21: Dmitri Krioukov , kc claffy , Marina Fomenkov , Fan Chung , Alessandro Vespignani , Walter Willinger, The workshop on internet topology (wit) report, ACM SIGCOMM Computer Communication Review, v.37 n.1, January 2007 [doi>10.1145/1198255.1198267]
• 22: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graph evolution: Densification and shrinking diameters, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.1, p.2-es, March 2007 [doi>10.1145/1217299.1217301]
• 23: Damien Magoni , Jean Jacques Pansiot, Analysis of the autonomous system network topology, ACM SIGCOMM Computer Communication Review, v.31 n.3, July 2001 [doi>10.1145/505659.505663]
• 24: Priya Mahadevan , Dmitri Krioukov , Marina Fomenkov , Xenofontas Dimitropoulos , k c claffy , Amin Vahdat, The internet AS-level topology: three data sources and one definitive metric, ACM SIGCOMM Computer Communication Review, v.36 n.1, January 2006 [doi>10.1145/1111322.1111328]
• 25: W. B. Norton. The Evolution of the U.S. Internet Peering Ecosystem. Equinix white papers, 2004.
• 26: Ricardo V. Oliveira , Dan Pei , Walter Willinger , Beichuan Zhang , Lixia Zhang, In search of the elusive ground truth: the internet's as-level connectivity structure, Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 02-06, 2008, Annapolis, MD, USA
• 27: Ricardo V. Oliveira , Beichuan Zhang , Lixia Zhang, Observing the evolution of internet as topology, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 28: S. Park, D. M. Pennock, and C. L. Giles. Comparing Static and Dynamic Measurements and Models of the Internet's AS Topology. In Proceedings of IEEE Infocom, 2004.
• 29: RIPE. RIPE Network Coordination Centre. http://www.ripe.net.
• 30: Routeviews. University of Oregon Route Views Project. http://www.routeviews.org.
• 31: M. A. Serrano, M. Boguna, and A. D. Guilera. Modeling the Internet. The European Physics Journal B, 2006.
• 32: G. Siganos, M. Faloutsos, and C. Faloutsos. The Evolution of the Internet: Topology and Routing. University of California, Riverside technical report.
• 33: L. Subramanian, S. Agarwal, J. Rexford, and R. Katz. Characterizing the Internet hierarchy from Multiple Vantage Points. In Proceedings of IEEE Infocom, 2002.
• 34: Hongsuda Tangmunarunkit , John Doyle , Ramesh Govindan , Walter Willinger , Sugih Jamin , Scott Shenker, Does AS size determine degree in as topology?, ACM SIGCOMM Computer Communication Review, v.31 n.5, p.7-8, October 2001 [doi>10.1145/1037107.1037108]
• 35: X. Wang and D. Loguinov. Wealth-Based Evolution Model for the Internet AS-Level Topology. In Proceedings of IEEE Infocom, 2006.
• 36: S. H. Yook, H. Jeong, and A. L. Barabasi. Modeling the Internet's Large-scale Topology. Proceedings of the National Academy of Sciences, 2002.
• 37: Beichuan Zhang , Raymond Liu , Daniel Massey , Lixia Zhang, Collecting the internet AS-level topology, ACM SIGCOMM Computer Communication Review, v.35 n.1, January 2005 [doi>10.1145/1052812.1052825]
• 38: Ying Zhang , Zheng Zhang , Zhuoqing Morley Mao , Charlie Hu , Bruce MacDowell Maggs, On the impact of route monitor selection, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298336]
• 39: S. Zhou. Understanding the Evolution Dynamics of Internet Topology. Physical Review E, vol. 74, 2006

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

General Terms:
Economics, Measurement

Keywords:
economics, evolution, internet topology, measurement