Internet connectivity at the AS-level: an optimization-driven modeling approach

ABSTRACT

Two ASs are connected in the Internet AS graph only if they have a business "peering relationship." By focusing on the AS subgraph AS_PC whose links represent provider-customer relationships, we develop a new optimization-driven model for Internet growth at the AS_PC level. The model's defining feature is an explicit construction of a novel class of intuitive, multi-objective, local optimizations by which the different customer ASs determine in a fully distributed and decentralized fashion their "best" upstream provider AS. Key criteria that are explicitly accounted for in the formulation of these multi-objective optimization problems are (i) AS-geography, i.e., locality and number of PoPs within individual ASs; (ii) AS-specific business models, abstract toy models that describe how individual ASs choose their "best" provider; and (iii) AS evolution, a historic account of the "lives" of individual ASs in a dynamic ISP market. We show that the resulting model is broadly robust, perforce yields graphs that match inferred AS connectivity with respect to a number of different metrics, and is ideal for exploring the impact of new peering incentives or policies on AS-level connectivity.

REFERENCES

• 1: William Aiello , Fan Chung , Linyuan Lu, A random graph model for massive graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.171-180, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335326]
• 2: R. Albert and A.-L. Barabási. Topology of Evolving Networks: Local Events and Universality. Physical Review Letters, 85(24), 2000.
• 3: D. Alderson, J. Doyle, R. Govindan, and W. Willinger. Toward an Optimization-Driven Framework for Designing and Generating Realistic Internet Topologies. In Proc. of HotNets-I, 2002.
• 4: R. Axtell. Zipf distribution of U.S. firm sizes. Science, 293, 2001.
• 5: P. Bak. How Nature Works: The Science of Self-Organized Criticality. Springer-Verlag, 1999.
• 6: A.-L. Barabási. Linked: The New Science of Networks. Perseus Publishing, 2002.
• 7: A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286:509--512, October 1999.
• 8: A. Bookstein. Informetric distributions, Part I/II. Journal of the Amer. Soc. for Information Science, 41:368--386, 1990.
• 9: CAIDA. NetGeo - The Internet Geographic Database. http://www.caida.org/tools/utilities/netgeo/.
• 10: J. M. Carlson and J. Doyle. Highly Optimized Tolerance: A Mechanism for Power-Laws in Designed Systems. Physical Review E, 60(2):1412--1427, 1999.
• 11: H. Chang, S. Jamin, and W. Willinger. What Causal Forces Shape Internet Connectivity at the AS-level? Technical Report CSE-475-03, EECS Dept., Univ. of Michigan, 2003.
• 12: Q. Chen, H. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. The Origin of Power Laws in Internet Topologies Revisited. In Proc. of IEEE INFOCOM, New York, NY, June 2002.
• 13: J. Doyle and J. M. Carlson. Power Laws, Highly Optimized Tolerance and Generalized Source Coding. Physical Review Letters, 84(24):5656--5659, 2000.
• 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: A. M. Feldman. Welfare Economics and Social Choice Theory. Kluwer, Boston, 1980.
• 17: L. Gao. On Inferring Autonomous System Relationships in the Internet. In Proc. of IEEE Globecom, San Francisco, CA, 2000.
• 18: Genuity. U.S. Dedicated Access PoPs list. http://www.genuity.com.
• 19: R. Govindan and P. Radoslavov. An Analysis of The Internal Structure of Large Autonomous Systems. Technical Report 02-777, CS Dept., Univ. of Southern California, 2002.
• 20: C. Jin, Q. Chen, and S. Jamin. Inet: Internet topology generator. Technical Report CSE-TR-433-00, EECS Dept., Univ. of Michigan, 2000.
• 21: Anukool Lakhina , John W. Byers , Mark Crovella , Ibrahim Matta, On the geographic location of internet resources, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637240]
• 22: Level 3 Communication, Inc. Internet access customer buying guide, 2002. http://www.level3.com.
• 23: Alberto Medina , Anukool Lakhina , Ibrahim Matta , John Byers, BRITE: An Approach to Universal Topology Generation, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.346, August 15-18, 2001
• 24: Venkata N. Padmanabhan , Lakshminarayanan Subramanian, An investigation of geographic mapping techniques for internet hosts, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.173-185, August 2001, San Diego, California, United States
• 25: J. Ramsden and G. Kiss-Haypal. Company size distribution in different countries. Physica A, 277:220--227, 2000.
• 26: Route-Views. University of Oregon Route Views Project. http://www.routeviews.org.
• 27: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 28: L. Subramanian, S. Agarwal, J. Rexford, and R. H. Katz. Characterizing the Internet Hierarchy from Multiple Vantage Points. In Proc. of IEEE INFOCOM, 2002.
• 29: 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]
• 30: W. Willinger, R. Govindan, S. Jamin, V. Paxson, and S. Shenker. Scaling phenomena in the Internet: Critically examining criticality. In Proc. of the National Academy of Sciences, 2001.