The Many Facets of Internet Topology

Date and time: 
Mon, Nov 6 2006 - 3:30pm
220 Deschutes
Walter Willinger
AT&T Labs-Research
  • Reza Rejaie

The Internet's layered architecture gives rise to a number of different topologies, with the lower layers defining more physical and the higher layers more virtual/logical types of connectivity structures. These topologies are very different and successful Internet topology modeling requires annotating the nodes and edges of the corresponding graphs with information that reflects their network-intrinsic meaning. To illustrate, I will focus on the Internet's router-level topology (i.e., the physical connectivity structure of today's Internet, where nodes are routers/switches and links represent physical connections) and show that it results from very structured and highly optimized tradeoffs between real-world economic and technological objectives and constraints. These findings directly contradict many popular claims, particularly those based on "scale-free" network models that ignore all such engineering tradeoffs and instead emphasize randomness (e.g., preferential attachment) and "universality." Both approaches yield network models that exhibit power law-type degree distributions (for very different reasons, though), but are in all other respects completely opposite from one another, with important implications for studying problems such as virus/worm propagation in the Internet or routing protocol performance.


Walter Willinger received the Diplom (Dipl. Math.) from the ETH Zurich, Switzerland, and the M.S. and Ph.D. degrees from the School of ORIE, Cornell University, Ithaca, NY. He is currently a member of the Information and Software Systems Research Center at AT&T Labs - Research, Florham Park, NJ, and before that, he was a Member of Technical Staff at Bellcore Applied Research (1986-1996). His research interests include studying the multiscale nature of Internet traffic and topology and developing a theoretical foundation for dealing with large-scale communication networks such as the Internet. He is a Fellow of ACM (2005) and a Fellow of IEEE (2005). For his work on the self-similar ("fractal") nature of Internet traffic, he received the 1996 IEEE W.R.G. Baker Prize Award from the IEEE Board of Directors, the 1994 W.R. Bennett Prize Paper Award from the IEEE Communications Society, and the 2006 ACM SIGCOMM "Test of Time" Paper Award.