happygeek 2,411 Most Valuable Poster Team Colleague Featured Poster

Boffins from the University of California, San Diego have succeeded in developing new algorithms to map the Internet. While mapping any network topology can be complex and demanding, mapping the Internet takes the task to a whole new level. Yet Priya Mahadevan and Amin Vahdat think they have accomplished it with the Orbis project which produces maps known as digital dandelions.

Quite apart from being pretty to look at, admittedly in a rather geeky kind of a way, these digital dandelions have a serious use. No matter what the size of the network, understanding the topology is a crucial component in also understanding performance issues, security issues and scalability. Knowing where any weaknesses might lay when it comes to both random failures and targeted attack, being able to predict the likely speed at which a virus may spread, determining the best defence against a denial of service attack all rely upon network topology knowledge.

The topology maps created by Mahadevan and Vahdat really do look like the heads of a dandelion, but the red dots are Internet nodes and the green lines their linkages. Interestingly, what Orbis has done is to create these maps using randomly generated graph data that retains the specific characteristics of a particular piece of the Internet while doubling the number of nodes. This allows predictive models of the Internet to be produced, annotated (with relevant peer-to-peer business relationship data) Internet router graphs of differing sizes but all based upon solid observations of the Internet as is.

As Priya Mahadevan explains "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."

Announcing that the map generator source code will be made available for public download soon, Amin Vahdat added "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. The techniques we have developed for characterizing and recreating Internet characteristics are generally applicable to a broad range of disciplines that consider networks, including physics, biology, chemistry, neuroscience and sociology."