On the origin of power laws in Internet topologies

ABSTRACT

Recent empirical studies [6] have shown that Internet topologies exhibit power laws of the form y = x ^α for the following relationships: (P1) outdegree of node (domain or router) versus rank; (P2) number of nodes versus outdegree; (P3) number of node pairs within a neighborhood versus neighborhood size (in hops); and (P4) eigenvalues of the adjacency matrix versus rank. However, causes for the appearance of such power laws have not been convincingly given. In this paper, we examine four factors in the formation of Internet topologies. These factors are (F1) preferential connectivity of a new node to existing nodes; (F2) incremental growth of the network; (F3) distribution of nodes in space; and (F4) locality of edge connections. In synthetically generated network topologies, we study the relevance of each factor in causing the aforementioned power laws as well as other properties, namely diameter, average path length and clustering coefficient. Different kinds of network topologies are generated: (T1) topologies generated using our parametrized generator, we call BRITE; (T2) random topologies generated using the well-known Waxman model [12]; (T3) Transit-Stub topologies generated using GT-ITM tool [3]; and (T4) regular grid topologies. We observe that some generated topologies may not obey power laws P1 and P2. Thus, the existence of these power laws can be used to validate the accuracy of a given tool in generating representative Internet topologies. Power laws P3 and P4 were observed in nearly all considered topologies, but different topologies showed different values of the power exponent α. Thus, while the presence of power laws P3 and P4 do not give strong evidence for the representativeness of a generated topology, the value of α in P3 and P4 can be used as a litmus test for the representativeness of a generated topology. We also find that factors F1 and F2 are the key contributors in our study which provide the resemblance of our generated topologies to that of the Internet.

REFERENCES

• 1: R. Albert, H. Jeong, and A.-L. Barabási. Diameter of the World-Wide Web. Nature, page 130, September 1999.
• 2: A.-L. Barabási and R. Albert. Emergence of Scaling in Random Networks. Science, pages 509-512, October 1999.
• 3: K. Calvert, M. Doar, and E. Zegura. Modeling Internet Topology. IEEE Transactions on Communications, pages 160-163, December 1997.
• 4: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 5: Mark E. Crovella , Mor Harchol-Balter , Cristina D. Murta, Task assignment in a distributed system (extended abstract): improving performance by unbalancing load, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.268-269, June 22-26, 1998, Madison, Wisconsin, United States
• 6: 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
• 7: B. A. Huberman and L. A. Adamic. Growth Dynamics of the World-Wide Web. Nature, page 131, September 1999.
• 8: Vern Paxson, End-to-end routing behavior in the Internet, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.601-615, Oct. 1997 [doi>10.1109/90.649563]
• 9: Vern Paxson , Sally Floyd, Why we don't know how to simulate the Internet, Proceedings of the 29th conference on Winter simulation, p.1037-1044, December 07-10, 1997, Atlanta, Georgia, United States [doi>10.1145/268437.268737]
• 10: Graham Phillips , Scott Shenker , Hongsuda Tangmunarunkit, Scaling of multicast trees: comments on the Chuang-Sirbu scaling law, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.41-51, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 11: D. J. Watts and S. H. Strogatz. Collective Dynamics of 'Small-World' Networks. Nature, pages 440-442, June 1998.
• 12: B. Waxman. Routing of Multipoint Connections. IEEE J. Select. Areas Commun., SAC-6(9): 1617-1622, December 1988.
• 13: Stephen Wolfram, Mathematica: a system for doing mathematics by computer (2nd ed.), Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1991
• 14: 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]