On the emergence of highly variable distributions in the autonomous system topology

ABSTRACT

Recent studies observe that vertex degree in the autonomous systems (AS) graph exhibits a highly variable distribution [14, 21]. The most prominent explanatory model for this phenomenon is the Barabasi-Albert (B-A) model [5, 2]. A central feature of the B-A model is preferential connectivity --- meaning that the likelihood a new node in a growing graph will connect to an existing node is proportional to the existing node's degree. In this paper we ask whether a more general explanation than the B-A model, and absent the assumption of preferential connectivity, is consistent with empirical data. We are motivated by two observations: first, AS degree and AS size are highly correlated [10]; and second, highly variable AS size can arise simply through exponential growth. We construct a model incorporating exponential growth in the size of the Internet and in the number of ASes, and show that it yields a size distribution exhibiting a power-law tail. In such a model, if an AS's link formation is roughly proportional to its size, then AS out-degree will also show high variability. Moreover, our approach is more flexible than previous work, since the choice of which AS to connect to does not impact high variability, thus can be freely specified. We instantiate such a model with empirically derived estimates of historical growth rates and show that the resulting degree distribution is in good agreement with that of real AS graphs.

REFERENCES

• 1: W. Aiello , F. Chung, Random Evolution in Massive Graphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.510, October 14-17, 2001
• 2: R. Albert and A. Barabási. Topology of evolving networks: local events and universality. Phys. Rev. Lett., 85:5234--5237, 2000.
• 3: R. Albert and A. Barabási. Statistical mechanics of complex networks. Reviews of Modern Physics, 74:47--97, January 2002.
• 4: D. Alderson, J. Doyle, R. Govindan, and W. Willinger. Toward an Optimization-Driven Framework for Designing and Generating Realistic Internet Topologies. In ACM HotNets-I, Princeton, NJ, October 2002.
• 5: A.-L. Barabási and R. Albert. Emergence of Scaling in Random Networks. Science, 286:509--512, October 1999.
• 6: Boston University Representative Internet Topology Generator (BRITE). At http://www.cs.bu.edu/brite.
• 7: T. Bu and D. Towsley. On Distinguishing between Internet Power Law Topology Generators. In Proceedings of IEEE INFOCOM, New York, NY, June 2002.
• 8: H. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. Towards Capturing Representative AS-Level Internet Topologies. Technical Report UM-CSE-TR-454-02, University of Michigan Computer Science, 2002.
• 9: H. Chang, S. Jamin, and W. Willinger. Inferring AS-level Internet Topology from Router-Level Path Traces. In Proceedings of SPIE ITCom 2001, Denver, CO, August 2001.
• 10: 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, New York, NY, June 2002.
• 11: D. J. deS. Price. Networks of scientific papers. Science, 149:510, 1965.
• 12: D. J. deS. Price. A general theory of bibliometric and other cumulative advantage processes. J. Amer. Soc. Inform. Sci., 27:292, 1976.
• 13: 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
• 14: 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
• 15: M. Fayed, P. Krapivsky, J. Byers, M. Crovella, D. Finkel, and S. Redner. On the size distribution of autonomous systems. Technical Report BUCS-TR-2003-001, Boston University, January 2003.
• 16: R. Govindan and H. Tangmunarunkit. Heuristics for Internet Map Discovery. In Proceedings of IEEE INFOCOM, March 2000.
• 17: Internet Domain Survey. At http://http://www.isc.org/ids/.
• 18: P. L. Krapivsky and S. Redner. Organization of Growing Random Networks. Phys. Rev. E, 63:066123, 2001.
• 19: P. L. Krapivsky, S. Redner, and F. Leyvraz. Connectivity of Growing Random Networks. Phys.Rev.Lett., 85:4629--4632, 2000.
• 20: P. L. Krapivsky, G. J. Rodgers, and S. Redner. Degree distributions of growing networks. Phys. Rev. Lett., 86:5401, 2001.
• 21: 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]
• 22: 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
• 23: Alberto Medina , Ibrahim Matta , John Byers, On the origin of power laws in Internet topologies, ACM SIGCOMM Computer Communication Review, v.30 n.2, April 2000 [doi>10.1145/505680.505683]
• 24: M. Mihail, C. Gkantsidis, and E. Zegura. Spectral analysis of Internet topologies. In Proceedings of IEEE INFOCOM, April 2003.
• 25: M. Mihail and N. Visnoi. On generating graphs with prescribed degree sequences for complex network modeling applications. In Proceedings of Approx. and Randomized Algorithms for Communication Networks (ARACNE), 2002.
• 26: S. Mossa, M. Barthelemy, H. Stanley, and L. A. Nunes Amaral. Truncation of Power Law Behavior in "Scale-Free" Network Models due to Information Filtering. Phys. Rev. Lett., 88(13):138701, March 2002.
• 27: Route Views Project at University of Oregon. At http://archive.routeviews.org/.
• 28: H. A. Simon. On a class of skew distribution functions. Biometrica, 42:425, 1955.
• 29: The Skitter Project. At http://www.caida.org/tools/measurement/skitter/.
• 30: 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]
• 31: Hongsuda Tangmunarunkit , Ramesh Govindan , Sugih Jamin , Scott Shenker , Walter Willinger, Network topology generators: degree-based vs. structural, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 32: Ellen W. Zegura , Kenneth L. Calvert , Michael J. Donahoo, A quantitative comparison of graph-based models for Internet topology, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.770-783, Dec. 1997 [doi>10.1109/90.650138]