Digital Dandelions

August 31, 2007
Digital Dandelion
What looks like the head of a digital dandelion is a map of the Internet generated by new algorithms from computer scientists at UC San Diego. This map features Internet nodes –- the red dots –- and linkages –- the green lines. But it is no ordinary map. It is a (mostly) randomly generated graph that retains the essential characteristics of a specific corner of the Internet but doubles the number of nodes. Credit: UC San Diego

What looks like the head of a digital dandelion is a map of the Internet generated by new algorithms from computer scientists at UC San Diego. This map features Internet nodes – the red dots – and linkages – the green lines. But it is no ordinary map. It is a (mostly) randomly generated graph that retains the essential characteristics of a specific corner of the Internet but doubles the number of nodes.

On August 30 in Kyoto, Japan at ACM SIGCOMM, the premier computer networking conference, UCSD computer scientists presented techniques for producing annotated, Internet router graphs of different sizes – based on observations of Internet characteristics.

The graph annotations include information about the relevant peer-to-peer business relationships that help to determine the paths that packets of information take as they travel across the Internet.

Generating these kinds of graphs is critical for a wide range of computer science research.

“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,” said Priya Mahadevan, the first author on the SIGCOMM 2007 paper. Mahadevan just completed her computer science Ph.D. at UCSD’s Jacobs School of Engineering. In October, she will join Hewlett Packard Laboratories in Palo Alto, CA.

“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,” said Amin Vahdat, the senior author on the paper, a computer science professor at UCSD and the Director of UCSD’s Center for Networked Systems (CNS) – an industrial/academic collaboration investigating emerging issues in computing systems that are both very large (planetary scale) and very small (the scale of wireless sensor networks).

The authors are making the source code for their topology generator publicly available and hope that it will benefit a range of studies.

“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,” said Vahdat.

Source: University of California - San Diego

Explore further: Does your smartphone make you less likely to trust others?

Related Stories

Does your smartphone make you less likely to trust others?

January 12, 2017

Imagine you are visiting a new city and get lost on your way to that famous must-see museum. In times of yore – actually just about 10 years ago – you might have had to consult a friendly local to direct you. Today, with ...

How blockchain will transform our cities

December 14, 2016

Many trends on the horizon offer opportunities that could transform our cities. From self-driving vehicles and the sharing economy through to cloud computing and blockchain technologies, each of these trends is quite significant ...

Exploring our changing Earth, in real time

January 2, 2017

Across the Lamont-Doherty Earth Observatory campus, scientists are exploring undersea volcanoes, monitoring coastal erosion along hard-to-reach shorelines, and studying the movement of sea ice – all in real time. By loading ...

Recommended for you

WhatsApp vulnerable to snooping: report

January 13, 2017

The Facebook-owned mobile messaging service WhatsApp is vulnerable to interception, the Guardian newspaper reported on Friday, sparking concern over an app advertised as putting an emphasis on privacy.

US gov't accuses Fiat Chrysler of cheating on emissions

January 12, 2017

The U.S. government accused Fiat Chrysler on Thursday of failing to disclose software in some of its pickups and SUVs with diesel engines that allows them to emit more pollution than allowed under the Clean Air Act.

0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.