On the Origin of Power Laws in Internet TopologiesReportar como inadecuado


On the Origin of Power Laws in Internet Topologies


On the Origin of Power Laws in Internet Topologies - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Citation

Medina, Alberto; Matta, Ibrahim; Byers, John. -On the Origin of Power Laws in Internet Topologies-, Technical Report BUCS-2000-004, Computer Science Department, Boston University, January 20, 2000. Available from: http:-hdl.handle.net-2144-1799

Abstract

Recent empirical studies have shown that Internet topologies exhibit power laws of the form for the following relationships: P1 outdegree of node domain or router versus rank; P2 number of nodes versus outdegree; P3 number of node pairs y = x^α 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; T3 Transit-Stub topologies generated using GT-ITM tool; 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.

CAS: Computer Science: Technical Reports -



Autor: Medina, Alberto - Matta, Ibrahim - Byers, John - -

Fuente: https://open.bu.edu/







Documentos relacionados