Digital Dandelions

Aug 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: Cutting the cloud computing carbon cost

add to favorites email to friend print save as pdf

Related Stories

Chameleon: Cloud computing for computer science

Aug 26, 2014

Cloud computing has changed the way we work, the way we communicate online, even the way we relax at night with a movie. But even as "the cloud" starts to cross over into popular parlance, the full potential ...

Enabling a new future for cloud computing

Aug 21, 2014

The National Science Foundation (NSF) today announced two $10 million projects to create cloud computing testbeds—to be called "Chameleon" and "CloudLab"—that will enable the academic research community ...

Students see world from station crew's point of view

Aug 19, 2014

NASA is helping students examine their home planet from space without ever leaving the ground, giving them a global perspective by going beyond a map attached to a sphere on a pedestal. The Sally Ride Earth ...

Recommended for you

Cutting the cloud computing carbon cost

Sep 12, 2014

Cloud computing involves displacing data storage and processing from the user's computer on to remote servers. It can provide users with more storage space and computing power that they can then access from anywhere in the ...

Teaching computers the nuances of human conversation

Sep 12, 2014

Computer scientists have successfully developed programs to recognize spoken language, as in automated phone systems that respond to voice prompts and voice-activated assistants like Apple's Siri.

Mapping the connections between diverse sets of data

Sep 12, 2014

What is a map? Most often, it's a visual tool used to demonstrate the relationship between multiple places in geographic space. They're useful because you can look at one and very quickly pick up on the general ...

Google team rises to 2014 visual recognition challenge

Sep 08, 2014

Google's Christian Szegedy, software engineer, blogged Friday about GoogleNet's entry into a visual recognition challenge, the results of which indicate improvements in the state of machine vision technology. ...

User comments : 0