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. W. Aiello, F. Chung, and L. Lu. A Random Graph Model for Massive Graphs. In Proc. of the 32nd Annual Symposium on Theory of Computing, 2000.
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 Approximations of Metric Spaces and its Algorithmic Applications. In Proc. 37th IEEE Symposium on Foundations of Computer Science, pages 184--193, October 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. H. Burch and B. Cheswick. Mapping the Internet. IEEE Computer, 32(4):97--98, April 1999.
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. A. B. Downey. Using pathchar to Estimate Link Characteristics. In Proceedings of the ACM SIGCOMM, 1999.
16. A. Fabrikant, E. Koutsoupias, and C. Papadimitriou. Heuristically Optimized Trade-offs. http://www.cs.berkeley.edu/ christos/.
17. C. Faloutsos, P. Faloutsos, and M. Faloutsos. On Power-Law Relationships of the Internet Topology. In Proceedings of the ACM SIGCOMM, Sept. 1999.
18. L. Gao. Inferring autonomous system relationships in the internet. In Proc. IEEE Globecom, San Francisco, CA, 2000.
19. A. Goel and K. Munagala. Extending Greedy Multicast Routing to Delay Sensitive Applications. Technical report, Stanford Univ. Tech Note STAN-CS-TN-99-89, July 1999. Short abstract appeared in the Symposium on Discrete Algorithms, 2000.
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. G. Karypis and V. Kumar. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM Journal on Scientific Computing, 20(1):359--92, 1998.
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. K. Lai and M. G. Baker. Measuring Link Bandwidths Using a Deterministic Model of Packet Delay. In Proceedings of the ACM SIGCOMM, 2000.
27. D. Magoni and J.-J. Pansiot. An Analysis of Autonomous System Network Topology. ACM Computer Communication Review, 31(3), July 2001.
28. A. Medina, A. Lakhina, I. Matta, and J. Byers. BRITE: An Approach to Universal Topology Generation. In Proceedings of MASCOTS 2001, Cincinnati, OH, August 2001.
29. A. Medina, I. Matta, and J. Byers. On the Origin of Power-Laws in Internet Topologies. ACM Computer Communications Review, 30(2), April 2000.
30. R. Motwani. Lecture Notes on Approximation Algorithms - Vol I. Department of Computer Science, Stanford University.
31. D. Palmer and G. Steffen. On Power-Laws In Network Topologies. In Proceedings of IEEE Globecom, 2000.
32. J.-J. Pansiot and D. Grad. On routes and multicast trees in the Internet. ACM SIGCOMM Computer Communication Review, 28(1):41--50, January 1998.
33. K. Park. Impact of topology on traceback techniques. Private communication.
34. D. Peleg and E. Upfal. Constructing disjoint paths on expander graphs. In STOC: ACM Symposium on Theory of Computing (STOC), 1987.
35. G. Phillips, S. Shenker, and H. Tangmunarunkit. Scaling of Multicast Trees: Comments on the Chuang-Sirbu Scaling Law. In Proceedings of the ACM SIGCOMM, Sept. 1999.
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. S. Savage, A. Collins, E. Hoffman, J. Snell, and T. Anderson. The End-to-End Effects of Internet Path Selection. In Proceedings of ACM SIGCOMM, Boston, MA, September 1999.
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. T. Wong and R. Katz. An Analysis of Multicast Forwarding State Scalability. In Proceedings of the 8th IEEE International Conference on Network Protocols (ICNP 2000), Osaka, Japan, November 2000.
50. E. Zegura. Thoughts on Router-level Topology Modeling. The End-to-end interest mailing list.
51. E. Zegura, K. L. Calvert, and M. J. Donahoo. A Quantitative Comparison of Graph-Based Models for Internet Topology. IEEE/ACM Transactions in Networking, 5(6), 1997.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Model development and analysis

      • Model verification and validation

• Networks

  • Network properties

    • Network structure