Mapping New Paths for a Stressed-Out Internet

Published 09/09/2010

The San Diego Supercomputer Center and Cooperative Association for Internet Data Analysis (CAIDA) at the University of California, San Diego, in a collaboration with researchers from Universitat de Barcelona in Spain and the University of Cyprus, have created the first geometric "atlas" of the Internet as part of a project to prevent our most ubiquitous form of communication from collapsing within the next decade or so.

The map of the Internet, as built and described in the Nature Communications paper, shows the locations of Internet systems on the hyperbolic plane. Image courtesy of Dmitri Krioukov, SDSC/CAIDA

"We compare routing in the Internet today to using a hypothetical road atlas, which is really just a long encoded list of road intersections and connections that would require drivers to pore through each line to plot a course to their destination without using any geographical, or geometrical, information which helps us navigate through the space in real life," said Krioukov, principal investigator of the project.

Now imagine that a road - or in the case of the Internet, a connection - is closed for some reason and there is no geographical atlas to plot a new course, just a long list of connections that need to be updated. "That is basically how routing in the Internet works today - it is based on a topographical map that does not take into account any geometric coordinates in any space," said Krioukov, who with his colleagues at CAIDA have been managing a project called Archipelago, or Ark, that constantly monitors the topology of the Internet, or the structure of its interconnections.

Like many experts, however, Krioukov is concerned that existing Internet routing, which relies on only this topological information, is not really sustainable. "It is very complicated, inefficient, and difficult to scale to the rapidly growing size of the Internet, which is now accessed by more than a billion people each day. In fact, we are already seeing parts of the Internet become intermittently unreachable, sinking into so-called black holes, which is a clear sign of instability."

Krioukov and his colleagues have developed an in-depth theory that uses hyperbolic geometry to describe a negatively curved shape of complex networks such as the Internet. This theory appears in paper Hyperbolic Geometry of Complex Networks, published by Physical Review E today. In their Nature Communications paper, the researchers employ this theory, Ark's data, and statistical inference methods to build a geometric map of the Internet. They show that routing using such a map would be superior to the existing routing, which is based on pure topology.

Instead of perpetually accessing and rebuilding a reference list of all available network paths, each router in the Internet would know only its hyperbolic coordinates and the coordinates of its neighbors so it could route in the right direction, only relaying the information to its closest neighbor in that direction, according to the researchers. Known as "greedy routing", this process would dramatically increase the overall efficiency and scalability of the Internet. "We believe that using such a routing architecture based on hyperbolic geometry will create the best possible levels of efficiency in terms of speed, accuracy, and resistance to damage," said Krioukov.

However the researchers caution that actually implementing and deploying such a routing structure in the Internet might be as challenging, if not more challenging, than discovering its hidden space. "There are many technical and non-technical issues to be resolved before the Internet map that we found would be the map that the Internet uses," said Krioukov.

The research was in part funded by the National Science Foundation, along with Spain's Direcção Geral de Ensino Superior (DGES), Generalitat de Catalunya, and by Cisco Systems. The Internet mapping paper as published in Nature Communications and the Physical Review E paper can be found online.

About CAIDA
SDSC's CAIDA group is a collaborative undertaking among organizations in the commercial, government, and research sectors aimed at promoting greater cooperation in the engineering and maintenance of a robust, scalable global Internet infrastructure. Late last month, the National Science Foundation announced that SDSC's CAIDA was selected as part of a series of awards aimed at pursuing new and innovative ways to create a next-generation Internet. The four new projects, each worth up to $8 million over three years, are part of the NSF's Future Internet Architecture (FIA) program.

About SDSC
As an organized research unit of UC San Diego, SDSC is a national leader in creating and providing cyberinfrastructure for data-intensive research. Cyberinfrastructure refers to an accessible and integrated network of computer-based resources and expertise, focused on accelerating scientific inquiry and discovery. Celebrating its 25th anniversary in 2010, SDSC is a founding member of TeraGrid, the nation's largest open-access scientific discovery infrastructure.

Media Contacts:
Jan Zverina, SDSC Communications
858 534-5111 or jzverina@sdsc.edu

Warren R. Froelich, SDSC Communications
858 822-3622 or froelich@sdsc.edu

Related Links

San Diego Supercomputer Center (SDSC): http://www.sdsc.edu/
CAIDA: http://www.caida.org/home/
CAIDA's Archipelago project: http://www.caida.org/projects/ark/
National Science Foundation: http://nsf.gov/
Universitat de Barcelona: http://www.ub.edu/web/ub/en/
University of Cyprus: http://www.ucy.ac.cy/
UC San Diego: http://www.ucsd.edu/