CaltechAUTHORS
  A Caltech Library Service

Understanding Internet topology: principles, models, and validation

Alderson, David and Li, Lun and Willinger, Walter and Doyle, John C. (2005) Understanding Internet topology: principles, models, and validation. IEEE/ACM Transactions on Networking, 13 (6). pp. 1205-1218. ISSN 1063-6692. http://resolver.caltech.edu/CaltechAUTHORS:ALDieeeacmtn05

[img]
Preview
PDF
See Usage Policy.

1137Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:ALDieeeacmtn05

Abstract

Building on a recent effort that combines a first-principles approach to modeling router-level connectivity with a more pragmatic use of statistics and graph theory, we show in this paper that for the Internet, an improved understanding of its physical infrastructure is possible by viewing the physical connectivity as an annotated graph that delivers raw connectivity and bandwidth to the upper layers in the TCP/IP protocol stack, subject to practical constraints (e.g., router technology) and economic considerations (e.g., link costs). More importantly, by relying on data from Abilene, a Tier-1 ISP, and the Rocketfuel project, we provide empirical evidence in support of the proposed approach and its consistency with networking reality. To illustrate its utility, we: 1) show that our approach provides insight into the origin of high variability in measured or inferred router-level maps; 2) demonstrate that it easily accommodates the incorporation of additional objectives of network design (e.g., robustness to router failure); and 3) discuss how it complements ongoing community efforts to reverse-engineer the Internet.


Item Type:Article
Additional Information:© Copyright 2005 IEEE. Reprinted with permission. Manuscript received January 21, 2005; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor E. Zegura. [Posted online: 2005-12-19] This work was supported in part by Boeing, the Air Force Office of Scientific Research (AFOSR), and Caltech’s Lee Center for Advanced Networking. Parts of this work were done at the Institute of Pure and Applied Mathematics (IPAM) at UCLA, as part of the 2002 annual program on Large-Scale Communication Networks. Partial and preliminary results appeared in the Proceedings of ACM SIGCOMM, Portland, OR, August 2004. The authors are indebted to M. Roughan for generating Fig. 8 and negotiating its suitability for “public consumption,” N. Spring for assistance in using the Rocketfuel data, S. Shalunov for data on the Abilene network, H. Sherman for help with the CENIC backbone, and R. Govindan and S. Low for fruitful discussions of router-level topologies. The authors also thank the four anonymous SIGCOMM reviewers for constructive comments on an earlier version of this paper.
Subject Keywords:Degree-based generators, heuristically optimal topology, network design, network topology, router configuration, topology metrics
Record Number:CaltechAUTHORS:ALDieeeacmtn05
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:ALDieeeacmtn05
Alternative URL:http://dx.doi.org/10.1109/TNET.2005.861250
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1825
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:20 Feb 2006
Last Modified:26 Dec 2012 08:46

Repository Staff Only: item control page