Toward an optimization-driven framework for designing and generating realistic Internet topologies

ABSTRACT

We propose a novel approach to the study of Internet topology in which we use an optimization framework to model the mechanisms driving incremental growth. While previous methods of topology generation have focused on explicit replication of statistical properties, such as node hierarchies and node degree distributions, our approach addresses the economic tradeoffs, such as cost and performance, and the technical constraints faced by a single ISP in its network design. By investigating plausible objectives and constraints in the design of actual networks, observed network properties such as certain hierarchical structures and node degree distributions can be expected to be the natural by-product of an approximately optimal solution chosen by network designers and operators. In short, we advocate here essentially an approach to network topology design, modeling, and generation that is based on the concept of Highly Optimized Tolerance (HOT). In contrast with purely descriptive topology modeling, this opens up new areas of research that focus on the causal forces at work in network design and aim at identifying the economic and technical drivers responsible for the observed large-scale network behavior. As a result, the proposed approach should have significantly more predictive power than currently pursued efforts and should provide a scientific foundation for the investigation of other important problems, such as pricing, peering, or the dynamics of routing protocols.

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: Matthew Andrews , Lisa Zhang, The Access Network Design Problem, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.40, November 08-11, 1998
• 3: An Approach to Optimal Peering Between Autonomous Systems in the Internet, Proceedings of the International Conference on Computer Communications and Networks, p.346, October 12-15, 1998
• 4: Pio Baake , Thorsten Wichmann, On the economics of Internet peering, Netnomics, v.1 n.1, p.89-105, March 1999 [doi>10.1023/A:1011449721395 ]
• 5: P. Bak. How Nature Works: The Science of Self-Organized Criticality Copernicus, New York, 1996.
• 6: A. Balakrishnan, T.L. Magnanti, A. Shulman, and R.T. Wong. Models for planning capacity expansion in local access telecommunication networks. Ann. of Oper. Res., 33, pp. 239--284, 1991.
• 7: A.L. Barabasi and R. Albert. Emergence of Scaling in Random Networks. Science, 286:509--512, 1999.
• 8: T. Bu and D. Towsley. On distinguishing between Internet power law topology generators. Proc. IEEE INFOCOM'02, 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.W. Zegura. Modeling Internet topology. IEEE Communications Magazine, 35, pp. 160--163, 1997.
• 11: J.M. Carlson and J.C. Doyle. Highly Optimized Tolerance: Robustness and design in complex systems. Phys. Rev. Lett., 84, pp. 2529--2532, 2000.
• 12: J.M. Carlson and J.C. Doyle. Complexity and Robustness. Proc. Nat. Acad. Sci., 99, suppl. 1, pp. 2538--2545, 2002.
• 13: J. Doyle, J. Carlson, S. Low, F. Paganini, G. Vinnicombe, W. Willinger, J. Hickey, P. Parillo, and L. Vandenberghe. Robustness and the Internet: Theoretical Foundations. http://netlab.caltech.edu/pub/papers/RIPartII.pdf
• 14: H. Chang, Q. Chen, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. The origins of power laws in Internet topologies revisited. Proc. IEEE INFOCOM'02, 2002.
• 15: k. claffy, T. Monk, and D. McRobb. Internet tomography. Nature, 1999.
• 16: 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
• 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: B. Gavish. Topological design of telecommunication networks---local access design methods. Ann. of Oper. Res., 33, pp. 17--71, 1991.
• 19: R. Govindan and H. Tangmunarunkit. Heuristics for Internet map discovery. Proc. IEEE INFOCOM'00, 2000.
• 20: Geoff Huston, ISP survival guide: strategies for running a competitive ISP, John Wiley & Sons, Inc., New York, NY, 1998
• 21: C. Jin, Q. Chen, and S. Jamin. Inet: Internet topology generator. Tech. Rep. CSE-TR-433-00, Univ. of Michigan, Ann Arbor, 2000.
• 22: R. Johari and J. Tsitsiklis. Routing and peering in a competitive Internet. Presentation at IPAM Workshop on Large-Scale Comm. Networks: Topology, Routing, Traffic, and Control, UCLA, 2002.
• 23: 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
• 24: A. Meyerson, Designing Networks Incrementally, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.406, October 14-17, 2001
• 25: 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]
• 26: F. S. Salman , J. Cheriyan , R. Ravi , S. Subramanian, Buy-at-bulk network design: approximating the single-sink edge installation problem, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.619-628, January 05-07, 1997, New Orleans, Louisiana, United States
• 27: H. Simon. On a class of skew distribution functions. Biometrika, 42:425--440, 1955.
• 28: 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
• 29: Hongsuda Tangmunarunkit , John Doyle , Ramesh Govindan , Walter Willinger , Sugih Jamin , Scott Shenker, Does AS size determine degree in as topology?, ACM SIGCOMM Computer Communication Review, v.31 n.5, p.7-8, October 2001 [doi>10.1145/1037107.1037108]
• 30: 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
• 31: D. Vukadinović, P. Huang, and T. Erlebach. A spectral analysis of the Internet topology. ETH TIK-NR. 118, 2001.
• 32: 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.
• 33: 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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Documentation, Experimentation, Performance, Theory

Keywords:
Internet topology, complex systems, highly optimized tolerance, network optimization, robustness