Network Topology
Generators: Degree-Based vs. Structural. H. Tangmunarunkit (USC-ISI), R. Govindan (ICSI), S. Jamin
(University of Michigan) , S. Shenker (ICSI), W. Willinger (AT&T Research)
Following the long-held belief that the Internet is hierarchical, the network
topology generators most widely used by the Internet research community,
Transit-Stub and Tiers, create networks with a deliberately hierarchical
structure. However, in 1999 a seminal paper by Faloutsos
et al. revealed that the Internet's degree distribution is a power-law.
Because the degree distributions produced by the Transit-Stub and Tiers
generators are not power-laws, the research community has largely dismissed
them as inadequate and proposed new network generators that attempt to
generate graphs with power-law degree distributions.
Contrary to much of the current literature on network topology generators,
this paper starts with the assumption that it is more important for network
generators to accurately model the large-scale structure of the Internet
(such as its hierarchical structure) than to faithfully imitate its local
properties (such as the degree distribution). The purpose of this
paper is to determine, using various topology metrics, which network
generators better represent this large-scale structure. We find,
much to our surprise, that network generators based on the degree
distribution more accurately capture the large-scale structure of measured
topologies. We then seek an explanation for this result by
examining the nature of hierarchy in the Internet more closely; we find that
degree-based generators produce a form of hierarchy that closely resembles
the loosely hierarchical nature of the Internet.
Papers are provided as
a service to all by the members of ACM SIGCOMM.
This
paper is available in Adobe PDF format.
|