A first-principles approach to understanding the internet's router-level topology

ABSTRACT

A detailed understanding of the many facets of the Internet's topological structure is critical for evaluating the performance of networking protocols, for assessing the effectiveness of proposed techniques to protect the network from nefarious intrusions and attacks, or for developing improved designs for resource provisioning. Previous studies of topology have focused on interpreting measurements or on phenomenological descriptions and evaluation of graph-theoretic properties of topology generators. We propose a complementary approach of combining a more subtle use of statistics and graph theory with a first-principles theory of router-level topology that reflects practical constraints and tradeoffs. While there is an inevitable tradeoff between model complexity and fidelity, a challenge is to distill from the seemingly endless list of potentially relevant technological and economic issues the features that are most essential to a solid understanding of the intrinsic fundamentals of network topology. We claim that very simple models that incorporate hard technological constraints on router and link bandwidth and connectivity, together with abstract models of user demand and network performance, can successfully address this challenge and further resolve much of the confusion and controversy that has surrounded topology generation and evaluation.

REFERENCES

• 1: Abilene Network. Detailed information about the objectives, organization, and development of the Abilene network are available from http://www.internet2.edu/abilene.
• 2: 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]
• 3: R. Albert, and A.-L. Barabási. Statistical Mechanics of Complex Networks, Rev. of Modern Physics (74), 2002.
• 4: R. Albert, H. Jeong, and A.-L. Barabási. Attack and error tolerance of complex networks, Nature 406, 378--382 (2000).
• 5: D. Alderson. Technological and Economic Drivers and Constraints in the Internet's "Last Mile", Tech Report CIT-CDS-04-004, California Institute of Technology (2004).
• 6: David Alderson , John Doyle , Ramesh Govindan , Walter Willinger, Toward an optimization-driven framework for designing and generating realistic Internet topologies, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.41-46, January 2003 [doi>10.1145/774763.774769]
• 7: A.-L. Barabási and R. Albert. Emergence of scaling in random networks, Science 286, 509--512 (1999).
• 8: B. Bollobás and O. Riordan. Robustness and vulnerability of scale-free random graphs, Internet Math. 1, pp. 1--35, 2003.
• 9: Linda Briesemeister , Patrick Lincoln , Phillip Porras, Epidemic profiles and defense of scale-free networks, Proceedings of the 2003 ACM workshop on Rapid malcode, October 27-27, 2003, Washington, DC, USA [doi>10.1145/948187.948200]
• 10: A. Broido and k. Claffy. Internet Topology: Connectivity of IP Graphs, Proceeding of SPIE ITCom WWW Conf. (2001).
• 11: T. Bu and D. Towsley. On distinguishing Between Internet Power Law Topology Generators, IEEE INFOCOM 2002.
• 12: K.L. Calvert, M. Doar, and E. Zegura., Modeling Internet topology, IEEE Communications Magazine, June (1997).
• 13: J.M. Carlson and J.Doyle. Complexity and Robustness PNAS, 99, Suppl. 1, 2539--2545 (2002).
• 14: Hyunseok Chang , Ramesh Govindan , Sugih Jamin , Scott J. Shenker , Walter Willinger, Towards capturing representative AS-level Internet topologies, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 15: Hyunseok Chang , Sugih Jamin , Walter Willinger, Internet connectivity at the AS-level: an optimization-driven modeling approach, Proceedings of the ACM SIGCOMM workshop on Models, methods and tools for reproducible network research, August 25-27, 2003, Karlsruhe, Germany [doi>10.1145/944773.944780]
• 16: Q. Chen, H. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. The Origin of Power Laws in Internet Topologies Revisited, Proc. IEEE INFOCOM 2002.
• 17: F. Chung and L. Lu. The average distance in a random graph with given expected degrees, Internet Mathematics, 1, 91--113, 2003.
• 18: Corporation for Education Network Intitiatives in California (CENIC). Available at http://www.cenic.org.
• 19: Cooperative Association for Internet Data Analysis (CAIDA), Skitter. Available at http://www.caida.org/tools/measurement/skitter/.
• 20: M. B. Doar. A Better Model for Generating Test Networks. In Proc. of GLOBECOM 1996.
• 21: P. Erdos and A. Renyi. On random graphs I Publ. Math. (Debrecen) 9 (1959), 290--297.
• 22: Alex Fabrikant , Elias Koutsoupias , Christos H. Papadimitriou, Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.110-122, July 08-13, 2002
• 23: 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
• 24: L. Gao. On inferring autonomous system relationships in the Internet, in Proc. IEEE Global Internet Symposium, 2000.
• 25: Christos Gkantsidis , Milena Mihail , Amin Saberi, Conductance and congestion in power law graphs, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 26: R. Govindan and H. Tangmunarunkit. Heuristics for Internet Map Discovery, Proc. IEEE INFOCOM 2000.
• 27: Internet2 Consortium. Internet2 NetFlow: Weekly Reports, Available at http://netflow.internet2.edu/weekly/.
• 28: C. Jin, Q. Chen, and S. Jamin. Inet: Internet Topology Generator. Technical Report CSE-TR443-00, Department of EECS, University of Michigan, 2000.
• 29: B.B. Mandelbrot. Fractals and Scaling in Finance: Discontinuity, Concentration, Risk. Springer-Verlag, 1997.
• 30: 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
• 31: 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]
• 32: M. Mitzenmacher. A Brief History of Generative Models for Power Law and Lognormal Distributions, Internet Mathematics. To appear. (2003).
• 33: M.E.J. Newman Assortative Mixing in Networks, Phys. Rev. Lett. 89, 208701(2002).
• 34: M.E.J. Newman. The Structure and Function of Complex Networks, SIAM Review 45, 167--256 (2003).
• 35: A. M. Odlyzko. Internet traffic growth: Sources and implications, in Optical Transmission Systems and Equipment for WDM Networking II, B. B. Dingel, W. Weiershausen, A. K. Dutta, and K.-I. Sato, eds., Proc. SPIE, vol. 5247, 2003, pp. 1--15.
• 36: C. R. Palmer and J. G. Steffan. Generating network topologies that obey power laws. Proc. GLOBECOM 2000.
• 37: R. Pastor-Satorras and A. Vespignani. Epidemic spreading in scale-free networks Physical Review Letters, 86(14), pp. 3200--3203, April 2, 2001.
• 38: M. Roughan, A. Greenberg, C. Kalmanek, M. Rumsewicz, J. Yates and Y. Zhang. Experience in Measuring Backbone Traffic Variability: Models, Metrics, Measurements and Meaning International Teletraffic Congress (ITC) 18, 2003.
• 39: Route Views, University of Oregon Route Views Project, Available at http://www.antc.uoregon.edu/route-views/.
• 40: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 41: L. Subramanian, S. Agarwal, J. Rexford, and R. Katz. Characterizing the Internet Hierarchy from Multiple Vantage Points, Proc. IEEE INFOCOM 2002.
• 42: Hongsuda Tangmunarunkit , Ramesh Govindan , Sugih Jamin , Scott Shenker , Walter Willinger, Network topology generators: degree-based vs. structural, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 43: State of Washington Master Contract for Cisco Products, June 2002. Available from http://techmall.dis.wa.gov/master_contracts/intranet/routers_switches.asp
• 44: B.M. Waxman. Routing of multipoint connections, IEEE Jour. of Selected Areas in Comm., Vol. 6, No. 9, 1988.
• 45: W. Willinger, R. Govindan, S. Jamin, V. Paxson and S. Shenker. Scaling Phenomena in the Internet: Critically examining Criticality Proc. Nat. Acad. Sci., 99, suppl. 1, pp. 2573--2580 (2002).
• 46: K.Wu and A. Liu. The Rearrangement Inequality http://matholymp.com/TUTORIALS/Rear.pdf
• 47: S.-H. Yook, H. Jeong, and A.-L. Barabási. Modeling the Internet's large-scale topology, PNAS 99, 13382-86 (2002).
• 48: 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

General Terms:
Design, Economics, Performance

Keywords:
degree-based generators, heuristically optimal topology, network topology, topology metrics