Network topology generators: degree-based vs. structural

ABSTRACT

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.

REFERENCES

• 1: William Aiello , Fan Chung , Linyuan Lu, A random graph model for massive graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.171-180, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335326]
• 2: R. Albert and A.-L. Barabasi. Topology of Evolving Networks: Local Events and Universality. Physical Review Letters, 85:5234--5237, 2000.
• 3: R. Albert, H. Jeong, and A.-L. Barabasi. Attack and Error Tolerance of Complex Networks. Nature, 406, 2000.
• 4: A.-L. Barabasi and R. Albert. Emergence of Scaling in Random Networks. Science, 286:509--512, 1999.
• 5: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 6: B. Bollobás. Random Graphs. Academic Press, Inc., Orlando, Florida, 1985.
• 7: A. Broido and K. C. Claffy. Internet Topology: Local Properties. In Proceedings of SPIE ITCom 2001, Denver, CO, August 2001.
• 8: T. Bu and D. Towsley. On Distinguishing Between Internet Power-Law Generators. In Proc. of IEEE Infocom, 2002.
• 9: Hal Burch , Bill Cheswick, Mapping the Internet, Computer, v.32 n.4, p.97-98,102, April 1999 [doi>10.1109/2.755008]
• 10: K. Calvert, M. Doar, and E. Zegura. Modelling Internet Topology. IEEE Communications Magazine, June 1997.
• 11: R. C. Chalmers and K. C. Almeroth. Modeling the Branching Characteristics and Efficiency Gains in Global Multicast Trees. In Proceedings of the IEEE Infocom 2001 (to appear), Anchorage, Alaska, USA, April 2001.
• 12: H. Chang, R. Govindan, S. Jamin, W. Willinger, and S. Shenker. On Inferring AS-Level Connectivity from BGP Routing Tables. In Proc. of IEEE Infocom, 2002.
• 13: K. C. Claffy and D. McRobb. Measurement and Visualization of Internet Connectivity and Performance. http://www.caida.org/Tools/Skitter/.
• 14: M. Doar. A Better Model for Generating Test Networks. In Proceeding of IEEE Global Telecommunications Conference (GLOBECOM), November 1996.
• 15: Allen B. Downey, Using pathchar to estimate Internet link characteristics, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.222-223, May 01-04, 1999, Atlanta, Georgia, United States
• 16: A. Fabrikant, E. Koutsoupias, and C. Papadimitriou. Heuristically Optimized Trade-offs. http://www.cs.berkeley.edu/ christos/.
• 17: 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
• 18: L. Gao. Inferring autonomous system relationships in the internet. In Proc. IEEE Globecom, San Francisco, CA, 2000.
• 19: Ashish Goel , Kamesh Munagala, Extending Greedy Multicast Routing to Delay Sensitive Applications, Stanford University, Stanford, CA, 1999
• 20: R. Govindan and H. Tangmunarunkit. Heuristics for Internet Map Discovery. In Proceedings of the IEEE Infocom, Tel-Aviv, Israel, March 2000.
• 21: T. C. Hu. Optimum Communication Spanning Trees. SIAM Journal of Computing, 3:188--195, 1974.
• 22: R. F. i Cancho and R. V. Sole. Optimization in Complex Networks. Condensed Matter Archives, http://xxx.lanl.gov/abs/cond-mat, November 2001.
• 23: C. Jin, Q. Chen, and S. Jamin. Inet: Internet Topology Generator. Technical Report CSE-TR-433-00, EECS Department, University of Michigan, 2000.
• 24: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 25: J. Kleinberg, S. R. Kumar, S. Rajagopalan, P. Raghavan, and A. Tomkins. The Web as a Graph: Measurements, Models and Methods. In International Conference on Combinatorics and Computing, 1999.
• 26: Kevin Lai , Mary Baker, Measuring link bandwidths using a deterministic model of packet delay, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.283-294, August 28-September 01, 2000, Stockholm, Sweden
• 27: 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]
• 28: 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
• 29: 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]
• 30: Rajeev Motwani, Lecture notes on approximation algorithms: Volume I, Stanford University, Stanford, CA, 1993
• 31: D. Palmer and G. Steffen. On Power-Laws In Network Topologies. In Proceedings of IEEE Globecom, 2000.
• 32: Jean-Jacques Pansiot , Dominique Grad, On routes and multicast trees in the Internet, ACM SIGCOMM Computer Communication Review, v.28 n.1, p.41-50, Jan. 1998 [doi>10.1145/280549.280555]
• 33: K. Park. Impact of topology on traceback techniques. Private communication.
• 34: D. Peleg , E. Upfal, Constructing disjoint paths on expander graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.264-273, January 1987, New York, New York, United States [doi>10.1145/28395.28424]
• 35: 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
• 36: P. Radoslavov, H. Tangmunarunkit, H. Yu, R. Govindan, S. Shenker, and D. Estrin. On Characterizing Network Topologies and Analyzing Their Impact on Protocol Design. Technical Report 00-731, University of Southern California, Dept. of CS, February 2000.
• 37: A. Rényi. On the Enumeration of Trees. In Combinatorial Structures and Their Applications, pages 355--360. Gordon and Breach, Science Publishers, June 1969.
• 38: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 39: R. Siamwalla, R. Sharma, and S. Keshav. Discovering Internet Topology. Unpublished manuscript.
• 40: L. Subramanian, S. Agarwal, J. Rexford, and R. Katz. Characterizing the Internet Hierarchy from Multiple Vantage Points. In Proc. of IEEE Infocom, 2002.
• 41: H. Tangmunarunkit, J. Doyle, R. Govindan, S. Jamin, W. Willinger, and S. Shenker. Does AS Size Determine AS Degree? ACM Computer Communication Review, October 2001.
• 42: H. Tangmunarunkit, R. Govindan, S. Jamin, and S. S. W. Willinger. Network Topology Generators: Degree-Based vs. Structural. Technical report, Computer Science Department, University of Southern California, 2002. Technical Report 02-760.
• 43: H. Tangmunarunkit, R. Govindan, S. Shenker, and D. Estrin. The Impact of Policy on Internet Paths. In To appear, Proc. of IEEE INFOCOM, Anchorage, AK, 2001.
• 44: R. van der Hofstad, G. Hooghiemstra, and P. van Mieghem. On the Efficiency of Multicast. Submitted for publication.
• 45: P. van Mieghem, G. Hooghiemstra, and R. van der Hofstad. A scaling law for the hopcount. Technical report, Delft University of Technology, 2000.
• 46: D. Vukadinovic, P. Huang, and T. Erlebach. A Spectral Analysis of the Internet Topology. Technical report, ETH Zurich, 2001.
• 47: D. J. Watts and S. H. Strogatz. Collective Dynamics of Small-World Networks. Nature, 363:202--204, 1998.
• 48: B. M. Waxman. Routing of Multipoint Connections. IEEE Journal of Selected Areas in Communication, 6(9):1617--1622, December 1988.
• 49: Tina Wong , R. Katz, An analysis of multicast forwarding state scalability, Proceedings of the 2000 International Conference on Network Protocols, p.105, November 14-17, 2000
• 50: E. Zegura. Thoughts on Router-level Topology Modeling. The End-to-end interest mailing list.
• 51: 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Measurement, Performance

Keywords:
degree-based generators, hierarchy, large-scale structure, network topology, structural generators, topology characterization, topology generators, topology metrics