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. W. Aiello, F. Chung, and L. Lu. A random graph model for massive graphs. In STOC 2000, 2000.
2. M. Andrews and L. Zhang. The access network design problem. 39th IEEE FOCS, 1998.
3. D. Awduche, J. Agogbua, J. McManus. An approach to optimal peering between autonomous systems in the Internet. Proc. of Inter. Conf. on Comp. Commun. and Networks, 1998.
4. P. Baake and T. Wichmann. On the economics of Internet peering. Netnomics, 1(1), 1999.
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. H. Burch and B. Cheswick. Mapping the Internet. IEEE Computer, 32(4), 1999.
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. A. Fabrikant, E. Koutsoupias, and C. Papadimitriou. Heuristically Optimized Trade-offs: A new paradigm for power laws in the Internet. ICALP 2002. pp. 110--122. 2002.
17. C. Faloutsos, P. Faloutsos, and M. Faloutsos. On power-law relationships of the Internet topology. Proc. ACM SIGCOMM'99, pp. 251--262, 1999.
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. G. Huston. ISP Survival Guide: Strategies for Running a Competitive ISP. John Wiley & Sons, New York, 2000.
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. A. Medina, A. Lakhina, I. Matta, and J. Byers. BRITE: An approach to universal topology generation. Proc. MASCOTS'01, 2001.
24. A. Meyerson, K. Mungala, S. Plotkin. Designing networks incrementally. 41st IEEE FOCS, 2001.
25. J. Pansiot and D. Grad. On routes and multicast trees in the Internet. ACM Comp. Comm. Rev., 1997.
26. F.S. Salman, J. Cheriyan, R. Ravi, and S. Subramanian. Buy at bulk design: approximating the single-sink installation problem. In Proc. 8th ACM-SIAM Symp. on Discrete Algorithms, pp. 619--628, 1997. (Revised, 1998.)
27. H. Simon. On a class of skew distribution functions. Biometrika, 42:425--440, 1955.
28. N. Spring, R. Mahajan, and D. Weatherall. Measuring ISP topologies with rocketfuel. Proc. ACM SIGCOMM'02 (to appear).
29. H. Tangmunarunkit, J. Doyle, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. Does AS size determine degree in AS topology? ACM Comp. Comm. Rev., 31, pp. 7--10, 2001.
30. H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, W. Willinger. Network topology generators: Degree-based vs. structural. Proc. ACM SIGCOMM'02 (to appear).
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. E. Zegura, K. Calvert, and M. Donahoo. A quantitative comparison of graph-based model for Internet topology. ACM/IEEE Trans. on Networking, 5(6):770--783, 1997.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Networks

  • Network properties

    • Network structure

  • Network protocols

    • Transport protocols

  • Network types

    • Public Internet