Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Web Development

Digital Dandelions: Graphing the Internet Topology


What looks like the head of a digital dandelion is map of the Internet generated by new algorithms from computer scientists at Universary of California, 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.

Computer scientists have devised 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," says Priya Mahadevan. Mahadevan just completed her computer science Ph.D. at UCSD’s Jacobs School of Engineering. In October, she will join Hewlett Packard Labs.

[Click image to view at full size]
Digital dandelion or new semi-random Internet map?

"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 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).

Digital Dandelions Compared. (left) Original-sized 939 node 2K-random HOT graph; (right) the rescaled 2,000-node version that retains important interconnectivity characteristics of the original.

"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.

The authors -- Priya Mahadevan, Calvin Hubble, and Amin Vahdat from UCSD’s Department of Computer Science and Engineering; and Bradley Huffaker and Dimitri Krioukov from CAIDA, the Cooperative Association for Internet Data Analysis which is based at the UCSD's Supercomputer Center -- are making the source code for their topology generator publicly available. They've also written a SIGCOMM paper Orbis: Rescaling Degree Correlations to Generate Annotated Internet Topologies.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.