Modeling Topology of Large Internetworks
The explosive growth of internetworking, and particularly of the Internet,
has been accompanied by a wide range of internetworking problems
related to routing, resource reservation, and administration.
The study of algorithms and policies to address such problems often
involves simulation or analysis using an abstraction or model
of the actual network structure and applications.
The reason is clear: networks that are large enough to be interesting
are also expensive and difficult to control; therefore they
are rarely available for experimental purposes.
Moreover, it is generally more efficient to assess solutions using
analysis or simulation --- provided the model is a
"good" abstraction of the real network and application.
It is therefore rather remarkable that studies based on randomly-generated
or trivial network models are so common,
while rigorous analyses of how the results scale or
how they can be applied to actual networks are extremely rare.
Over the next few years, important decisions will be made
regarding the adoption of algorithms and placement of
facilities in the Internet to support scaling to
tens of thousands of administrative domains.
The inputs to these decisions will include simulation
and analyses based on models of networks and applications.
Unfortunately, with the current state of the art
it is very difficult to draw quantitative conclusions
based upon such models; indeed, there is presently no theoretical
basis for assessment of the accuracy of conclusions drawn from models.
A primary objective of our work is therefore to support the study
of large internetworks through scalable, realistic
models of internetwork structure and applications.
An additional objective is to apply and demonstrate the utility
of our models in the development of novel multicast routing algorithms.
Multicast routing is a critical and difficult problem within
large scale internetworking, and serves as a driver for the
rest of our work.
Our approach combines theoretical and experimental techniques.
The first step is formulation of a rigorous definition of model fidelity.
The second step is application of that definition in developing
a set of modeling components, including:
- models of network geography, i.e.,
structure that goes beyond simple topology to include
policy and other considerations, including known scaling properties;
- compositional techniques for abstracting large internets
as aggregates of smaller geographical components;
- models of the session structure of typical applications,
especially multicast applications;
- models of traffic within sessions, derived from
the work of other research groups.
The third step is calibration and refinement of the models:
measurements from real networks and applications are used to
validate the scalability and fidelity of the models, and
additional levels of detail are added to the entire framework.
Publications
- Megan Thomas and Ellen W. Zegura.
"Generation and Analysis of Random Graphs to Model Internetworks."
Technical Report GIT-CC-94-46,
College of Computing, Georgia Tech.
- Ellen W. Zegura, Ken Calvert and S. Bhattacharjee.
"How to Model an Internetwork."
Proceedings of IEEE Infocom '96, San Francisco, CA.
- Ken Calvert, Matt Doar and Ellen W. Zegura.
"Modeling Internet Topology."
To appear in IEEE Communications Magazine, June 1997.
- Ellen W. Zegura, Kenneth Calvert and M. Jeff Donahoo.
"A Quantitative Comparison of Graph-based Models for Internet Topology."
Accepted for publication in IEEE/ACM Transactions on Networking.
Software
- GT-ITM: Georgia Tech Internetwork Topology Models
This is a collection of routines to generate and analyze graphs
using a wide variety of models for internetwork topology. The
graphs are generated in Don Knuth's SGB format; a routine is
provided to convert to an alternative format that may be easier
to parse.
The README file describes the contents
of the distribution.
Here are instructions on how to unpack
the distribution.
Students
- Megan Thomas (CRA summer intern; now at UC-Berkeley)
- Elizabeth Edwards (CRA summer intern; now at Georgia Tech)
- Samrat Bhattacharjee
Contact information:
College of Computing, 801 Atlantic Drive
Georgia Institute of Technology
Atlanta, Georgia 30332-0280
Telephone: +1 404 894 1403
Fax: +1 404 894 0272
Internet: ewz@cc.gatech.edu
Last updated 1997/5/26 (EWZ)