Optimization-Based Approaches to Complex Network Topology
Overview:
We propose a novel approach to the study of complex network topology
in which we use an optimization framework to model the mechanisms
driving network design and 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
provides a framework that reconciles the domain-specific details
of vastly different systems with general principles underlying network
evolution and growth. 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
understood as the natural by-product of an approximately optimal
solution to a network design problem. In short, we
advocate here an approach to network topology design,
modeling, and generation that is based on the concept of
Highly Optimized Tolerance (HOT).
We use the router-level Internet as our principle case study in
complex networks in order to illustrate how differences in the
assumptions and methodologies
of engineering and statistical physics have led to strikingly
different conclusions about large-scale network properties, such as
robustness to failure and attack. Perhaps most
significantly, this work has shown that recently popular models of
so-called "scale-free networks" are both inadequate and inaccurate
representations of the Internet and that they provide results that are
in many ways the opposite of the real network. In particular,
the claim that power-law distibutions in node degree imply the
existence of a fragile hub-like network core are simply not correct,
and therefore the interpretation of the scale-free "Achilles' heel"
as a fragile point under attack does not follow.
Moreover, this work has demonstrated that the most
essential "robust, yet fragile" features of the Internet and other
highly evolved systems actually come from aspects that are only
indirectly related to network connectivity.
While scale-free networks are theoretically fascinating, our belief is
that this framework has been misapplied to high-technology (and
biological) systems where an iterative design process means that the
resulting structure is inherently nonrandom. An unexpected
consequence of this work has been the discovery of new graph
theoretical insights for scale-free networks, much of which are as yet
unexplored.
Publications:
-
Towards a Theory of Scale-Free Graphs:
Definition, Properties, and Implications.
L. Li, D. Alderson, J. Doyle, and W. Willinger.
Internet Mathematics. In Press. (2006)
[abstract,
matlab code,
data]
-
Understanding Internet Topology: Principles, Models, and Validation.
D Alderson, L Li, W Willinger, JC Doyle.
IEEE/ACM TRANSACTIONS ON NETWORKING, Dec. 2005.
[pdf]
-
The ``Robust Yet Fragile'' Nature of the Internet.
J. Doyle, D. Alderson, L. Li,
S. Low, M. Roughan, S. Shalunov,
R. Tanaka, and W. Willinger.
Proceedings of the National Academy of Sciences USA.
October 11, 2005 | vol. 102 | no. 41 | 14497-14502.
(Published online before print October 4, 2005, 10.1073/pnas.0501426102)
[abstract,
online article]
Among Top 50 most downloaded PNAS articles
-
The Role of
Optimization in Understanding and Modeling Internet Topology.
D. Alderson, W. Willinger, L. Li, and J. Doyle.
In
Telecommunications Planning: Innovations in Pricing, Network
Design and Management.
S. Raghavan and G. Anandlingham, eds.
Springer. In Press. (2005)
[
abstract]
-
A contrasting look at self-organization in the Internet
and next-generation communication systems.
D. Alderson and W. Willinger.
IEEE Communications Magazine. July 2005.
[abstract]
-
More "Normal" Than Normal: Scaling Distributions and Complex
Systems.
W. Willinger, D. Alderson, J. Doyle, and L. Li.
Proceedings of the 2004 Winter
Simulation Conference.
R.G. Ingalls, M.D. Rossetti, J.S. Smith,
and B.A. Peters, eds.
December 2004.
[pdf,
abstract]
-
A pragmatic approach
to dealing with high variability in network measurements.
W. Willinger, D. Alderson, and L. Li.
Proc. ACM SIGCOMM Internet Measurement Workshop 2004,
Taormina, Sicily, Italy, October 25-27, 2004.
[pdf,
abstract]
-
A First-Principles
Approach to Understanding the Internet's Router-Level Topology.
L. Li, D. Alderson, W. Willinger, and J. Doyle.
Proc. ACM SIGCOMM 2004, Portland, Oregon, Aug.30-Sept.2, 2004.
[pdf,
abstract]
-
Technological and Economic and Economic Drivers and
Constraints in the Internet's "Last Mile".
D. Alderson.
Technical Report
CIT-CDS-04-004, Engineering Division, California Institute of Technology,
February 2004. [pdf,
abstract]
-
Toward an
Optimization-Driven Framework for Designing and Generating Realistic
Internet Topologies.
D. Alderson, J. Doyle, R. Govindan, and W. Willinger.
ACM HotNets-I, Princeton, NJ, October 2002.
In ACM SIGCOMM Computer Communications Review,
Vol. 33, No. 1, January 2003.
[pdf,
abstract]
Presentations:
-
More "Normal" Than Normal: Scaling Distributions and Complex
Systems.
D. Alderson, W. Willinger, J. Doyle, and L. Li.
Advanced Tutorial at the 2004 Winter
Simulation Conference. December 2004.
[slides]
-
A First-Principles
Approach to Understanding the Internet's Router-Level Topology.
L. Li, D. Alderson, W. Willinger, and J. Doyle.
Proc. ACM SIGCOMM 2004, Portland, Oregon, Aug.30-Sept.2, 2004.
[slides]
-
"Optimization-based Approaches to Understanding and Modeling Internet
Topology"
David Alderson.
Tutorial Presentation at 7th INFORMS Telecommunications
Conference. Boca Raton, FL. March 2004.
[slides]
-
"The Role of Design in the Internet and Other Complex Systems"
David Alderson.
IMA Workshop on Robustness in
Complex Systems.
Institute for Mathematics and its Applications,
University of Minnesota. February 10, 2004.
[slides]
-
"Toward an Optimization-Driven Framework for Designing and Generating
Realistic Internet Topologies"
David Alderson, John Doyle, Ramesh Govindan, and Walter Willinger.
First Workshop on Hot Topics in Networks (HotNets-I).
28-29 October 2002, Princeton, New Jersey, USA.
[slides]
-
"Optimization-Based Approaches to Realistic Topology Generation"
David Alderson.
IPAM Program on Large-Scale Communication Networks.
Lake Arrowhead, June 2002.
[slides ]
Last Updated: August 24, 2005.