Mapping new paths for stressed-out Internet

Sep 10, 2010
Image credit: Nature Communications

(PhysOrg.com) -- 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.

In a paper published this week in Nature Communications, CAIDA researcher Dmitri Krioukov, along with Marián Boguñá (Universitat de Barcelona) and Fragkiskos Papadopoulos (University of Cyprus), describe how they discovered a latent hyperbolic, or negatively curved, space hidden beneath the Internet’s topology, leading them to devise a method to create an Internet map using hyperbolic geometry. In their paper, "Sustaining the Internet with Hyperbolic Mapping," the researchers say such a map would lead to a more robust Internet routing architecture because it simplifies path-finding throughout the network.

“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 the paper "Hyperbolic Geometry of Complex Networks," published by Physical Review E today (Sept. 9). 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 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 mapping paper as published in can be found here. The Physical Review E paper can be found here.

Explore further: Powerful new software plug-in detects bugs in spreadsheets

Related Stories

IPv6: Challenge to Internet freedom?

Mar 20, 2006

A China-backed Internet technical standard reportedly might allow the traceability of Internet users, especially those opposing government policies.

Internet Growth Follows Moore's Law Too

Jan 14, 2009

(PhysOrg.com) -- Originally, Moore’s Law described the number of transistors that can fit on an integrated circuit, which doubles approximately every 18 months. Now, a team of researchers from China has ...

Cisco Invests $12 Million in R&D Center in Japan

Dec 18, 2004

Tokyo R&D Center to Focus on Internet Software and Routing Technology, Drawing on Japan's Leadership in the Broadband Market Cisco Systems, Inc., today announced its intent to open research and development center in Tokyo, Japa ...

Recommended for you

Researchers developing algorithms to detect fake reviews

Oct 21, 2014

Anyone who has conducted business online—from booking a hotel to buying a book to finding a new dentist or selling their wares—has come across reviews of said products and services. Chances are they've also encountered ...

User comments : 2

Adjust slider to filter visible comments by rank

Display comments: newest first

snwboardn
1 / 5 (1) Sep 10, 2010
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


I don't get it... Where does the router get a hyperbolic connection? Sounds like it still would have to get router updates... Just sounds like a fancy word for what routers already use, metrics. In fact Cisco's EIGRP does the same thing, it keeps backup routes in memory so that if a connection goes down it has a backup ready to go...
dtxx
1 / 5 (3) Sep 10, 2010
The answer is IPv6, not this.