Internet maps are blooming
It is important to understand network topology to predict its performance and its resilience to attacks. This is why computer scientists at UC San Diego have developed new algorithms which create Internet maps. Their maps -- looking like digital dandelions -- show Internet nodes and their linkages. But they are -- mostly -- randomly generated graphs that describe the characteristics of a specific corner of the Internet but double or triple the number of nodes. These algorithms, which you soon will be able to download, should also improve the scalability of network protocols and applications.
On the left, you can see pictures showing 2,000-node-randomized versions of the original-sized HOT router graph, a representative router-level topology. (Credit:UCSD) The rescaled version (bottom) retains some important interconnectivity characteristics of the original (top).
The lead researcher for this project was Priya Mahadevan, who got her computer science Ph.D. at UCSD and is now moving to Hewlett Packard Laboratories. Amin Vahdat, a computer science professor at UCSD, helped her to manage this project called Orbis.
Here is a quote from Mahadevan. "Defending against denial of service attacks and large-scale worm outbreaks depends on network topology. Our work allows computer scientists to experiment with a range of random graphs that match Internet characteristics. This work is also useful for determining the sensitivity of particular techniques -- like routing protocols and congestion controls -- to network topology and to variations in network topology."
And Vahdat adds: "We're saying, 'here is what the Internet looks like, and here is our recreation of it on a larger scale.' Our algorithm produces random graphs that maintain the important interconnectivity characteristics of the original. The goal is to produce a topology generator capable of outputting a range of annotated Internet topologies of varying sizes based on available measurements of network connectivity and characteristics."
On the Orbis project page, you'll find the questions that research about Internet topology tries to answer.
- Generation: can we efficiently generate ensembles of random but realistic topologies by reproducing a set of simple graph metrics?
- Simulations: how does some (new) protocol or application perform on a set of these realistic topologies?
- Evolution: what are the forces driving the evolution (growth) of the topology of a given network?
This research work has been presented at the ACM SIGCOMM 2007, the networking conference which was held in Kyoto, Japan, in August.
The title of the presentation was "Orbis: Rescaling Degree Correlations to Generate Annotated Internet Topologies." Here is a link to this technical paper (PDF format, 12 pages, 1.04 MB) from which the above pictures have been extracted.
And here is the beginning of the abstract. "Researchers involved in designing network services and protocols rely on results from simulation and emulation environments to evaluate correctness, performance and scalability. To better understand the behavior of these applications and to predict their performance when deployed across the Internet, the generated topologies that serve as input to simulated and emulated environments must closely match real network characteristics, not just in terms of graph structure (node interconnectivity) but also with respect to various node and link annotations. Relevant annotations include link latencies, AS membership and whether a router is a peering or internal router. Finally, it should be possible to rescale a given topology to a variety of sizes while still maintaining its essential characteristics."
Sources: University of California at San Diego news release, via EurekAlert!, August 31, 2007; and various websites
You'll find related stories by following the links below.