Alberto Medina
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.
- R. Albert, H. Jeong, and A.-L. Barabási. Diameter of the World-Wide Web. Nature, page 130, September 1999.Google Scholar
- A.-L. Barabási and R. Albert. Emergence of Scaling in Random Networks. Science, pages 509-512, October 1999.Google Scholar
- K. Calvert, M. Doar, and E. Zegura. Modeling Internet Topology. IEEE Transactions on Communications, pages 160-163, December 1997. Google ScholarDigital Library
- M. Crovella and A. Bestavros. Self-Similarity in World Wide Web Traffic: Evidence and Possible Causes. IEEE/ACM Transactions on Networking, pages 835-846, December 1997. Google ScholarDigital Library
- M. Crovella, M. Harchol-Balter, and C. Murta. Task Assignment in a Distributed System: Improving Performance by Unbalancing Load. In Proceedings of ACM Sigmetrics '98 Conference on Measurement and Modeling of Computer Systems Poster Session, Madison, WI, June 1998. Google ScholarDigital Library
- M. Faloutsos, P. Faloutsos, and C. Faloutsos. On Power-Law Relationships of the Internet Topology. In ACM SIGCOMM, Cambridge, MA, September 1999. Google ScholarDigital Library
- B. A. Huberman and L. A. Adamic. Growth Dynamics of the World-Wide Web. Nature, page 131, September 1999.Google Scholar
- V. Paxson. End-to-End Routing Behavior in the Internet, IEEE/ACM Transactions on Networking, pages 601-615, December 1998. Google ScholarDigital Library
- V. Paxson and S. Floyd. Why We Don't Know How To Simulate The Internet. In Proceedings of the 1997 Winter Simulation Conference, Atlanta, GA, January 1997. Google ScholarDigital Library
- G. Phillips and S. Shenker. Scaling of Multicast Trees: Comments on the Chuang-Sirbu Scaling Law. In ACM SIGCOMM '99, Cambridge, MA, August 1999. Google ScholarDigital Library
- D. J. Watts and S. H. Strogatz. Collective Dynamics of 'Small-World' Networks. Nature, pages 440-442, June 1998.Google Scholar
- B. Waxman. Routing of Multipoint Connections. IEEE J. Select. Areas Commun., SAC-6(9): 1617-1622, December 1988.Google Scholar
- S. Wolfram. Mathematica: A System for Doing Mathematics by Computer. Addison-Wesley, 1991. Google ScholarDigital Library
- E. W. Zegura, K. Calvert, and M. J. Donahoo. A Quantitative Comparison of Graph-based Models for Internetworks. IEEE/ACM Transactions on Networking, pages 770-783, December 1997. Google ScholarDigital Library
Index Terms
- On the origin of power laws in Internet topologies
Recommendations
Designing optimal iBGP route-reflection topologies
NETWORKING'08: Proceedings of the 7th international IFIP-TC6 networking conference on AdHoc and sensor networks, wireless networks, next generation internetThe Border Gateway Protocol (BGP) is used today by all Autonomous Systems (AS) in the Internet. Inside each AS, iBGP sessions distribute the external routes among the routers. In large ASs, relying on a full-mesh of iBGP sessions between routers is not ...
Towards capturing representative AS-level Internet topologies
Recent studies on AS-level Internet connectivity have attracted considerable attention. These studies exclusively relied on BGP data from the Oregon route-views [University of Oregon Route Views Project, http:// www.routeviews.org] to derive some ...
Comments