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 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 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 can be found here. The Physical Review E paper can be
found here.
SOURCE
