The Role of Optimization in Understanding and Modeling Internet Topology.

D. Alderson, W. Willinger, L. Li, and J. Doyle.

In Press. September 2004.

Abstract: Over the last decade there has been significant interest and attention devoted towards understanding the complex structure of the Internet, particularly its topology and the large-scale properties that can be derived from it. While recent work by empiricists and theoreticians has emphasized certain statistical and mathematical properties of network structure, this article presents an optimization-based perspective that focuses on the objectives, constraints, and other drivers of engineering design. We argue that Internet topology at the router-level can be understood in terms of the tradeoffs between network performance and the technological and economic factors constraining design. Furthermore, we suggest that the formulation of corresponding optimization problems serves as a reasonable starting point for generating ``realistic, yet fictitious'' network topologies. Finally, we describe how this optimization-based perspective is being used in the development of a still-nascent theory for the Internet as a whole.