Greedy Routing Enables Network Navigation Without a 'Map'

Feb 17, 2009 By Lisa Zyga feature
This illustration shows the path of greedy routing, a navigation strategy in which a node passes information to the neighboring node that is closest to the final destination in hidden metric space. Image credit: Marián Boguna and Dmitri Krioukov.

(PhysOrg.com) -- How does an e-mail get routed so quickly to its recipient's inbox, or a search query generate relevant Web pages from servers from around the world? Navigating the Internet - or any similar network - generally works most efficiently when routers have knowledge of the network's global topology. Without knowing the links between nodes, it's difficult to determine the shortest path between two nodes.

However, a navigation technique called greedy routing has shown that it can find the shortest paths between nodes using only local information, without knowledge of the network’s global topology. Marián Boguna from the University of Barcelona and Dmitri Krioukov from the University of California, San Diego, have shown in a recent study that random, scale-free networks such as the Internet have a peculiar structure that enables information to flow along the shortest routes without global topology knowledge. The surprising results are published in a recent issue of Physical Review Letters.

“As common sense suggests, the computation of shortest paths is commonly believed to require the full and precise knowledge of the full topology, and here we are showing that it's in fact not true - not true for the topologies of real complex networks,” Krioukov told PhysOrg.com.

In greedy routing, a node passes information to the neighboring node that is closest to the final destination in an abstract space called hidden metric space. This space underlies the real network, and distances in this space abstract intrinsic similarities between nodes. The existence of hidden metric spaces under real networks is a conjecture, although researchers have found evidence of their existence for some real networks, including the Internet.

As the researchers explain, some types of networks are not navigable. For instance, if the probability that two nodes are linked doesn’t depend on the metric distance between them, then such networks are difficult to navigate, as there is no way to choose one node over another based on distance. But when there is a connection between the link existence probability and the hidden distance between nodes, metric distances can help to navigate the network, i.e., such networks are “navigable.”

As the scientists explain, an ideal navigating strategy should first pass the information to high-degree nodes, since their numerous connections likely cover long distances, getting closer to the destination node. However, greedy routing doesn’t check nodes’ degrees, but only compares the underlying metric distances between various neighbor nodes and the destination node. Fortunately, as the researchers show for navigable networks, node degree is positively correlated with the distances that the node covers by its links. So the closer to the destination a node is, the more distance it likely reaches, and the higher the degree of the node.

This correlation between a node’s distance to the destination in metric space, the node’s overall reach, and its degree is what makes the greedy routing strategy efficient at determining the shortest paths. In most cases of transferring information with greedy routing, information first travels to nodes with high degrees. Then, when the distance to the destination decreases, the pattern changes so that the information reaches its destination in a few small hops, regardless of node degree.

As the researchers explain, complex networks have a peculiar structure that makes them navigable and that guarantees that information can flow along the shortest routes even without knowledge of the network’s global topology. Regardless of the specifics of the hidden metric space, greedy paths are the shortest paths in synthetic networks with the topologies of real complex networks.

Still, the study leaves open some questions, such as the possibility that real networks may tend to evolve to become navigable, as well as determining which networks have hidden metric spaces and which do not. Using the greedy routing strategy to find the shortest paths for the Internet could greatly improve the efficiency of routing in the Internet, Today, Internet routers must continually update their global topology knowledge, presenting a major scalability bottleneck in Internet growth.

“Routing in the Internet today requires global topological awareness for all routers, which involves enormous and ever-growing inter-router communication overhead,” Krioukov explained. “Routers are constantly detecting, distributing, processing, and recalculating information needed to compute the shortest paths. For example, as soon as a link fails, the adjacent routers send messages to their neighboring routers about this event, those send messages to their neighbors, and so on, resulting in huge and never-abating cascades of routing updates and recalculations. Routers are getting overwhelmed with this overhead. They can't keep up with it, they fail, and black holes - unreachable islands of the Internet - are appearing everywhere.

“With greedy routing, global topology knowledge is not needed, so that this overhead would be removed, and routing would scale and work much better,” he said.

More information: Boguna, Marián; and Krioukov, Dmitri. “Navigating Ultrasmall Worlds in Ultrashort Time.” Physical Review Letters 102, 058701 (2009).

Copyright 2009 PhysOrg.com.
All rights reserved. This material may not be published, broadcast, rewritten or redistributed in whole or part without the express written permission of PhysOrg.com.

Explore further: Robotics meet X-ray lasers in cutting-edge biology studies

add to favorites email to friend print save as pdf

Related Stories

Britain urges Russia to shut down webcam spying site

2 hours ago

A Russian website offering thousands of live feeds peering into bedrooms and offices around the world by accessing poorly secured webcams should be taken down immediately, British officials said on Thursday.

Geologists discover ancient buried canyon in South Tibet

3 hours ago

A team of researchers from Caltech and the China Earthquake Administration has discovered an ancient, deep canyon buried along the Yarlung Tsangpo River in south Tibet, north of the eastern end of the Himalayas. ...

Recommended for you

How the hummingbird achieves its aerobatic feats

22 hours ago

(Phys.org) —The sight of a tiny hummingbird hovering in front of a flower and then darting to another with lightning speed amazes and delights. But it also leaves watchers with a persistent question: How ...

New terahertz device could strengthen security

Nov 21, 2014

We are all familiar with the hassles that accompany air travel. We shuffle through long lines, remove our shoes, and carry liquids in regulation-sized tubes. And even after all the effort, we still wonder if these procedures ...

CERN makes public first data of LHC experiments

Nov 21, 2014

CERN today launched its Open Data Portal where data from real collision events, produced by experiments at the Large Hadron Collider (LHC) will for the first time be made openly available to all. It is expected ...

User comments : 6

Adjust slider to filter visible comments by rank

Display comments: newest first

LWM
3 / 5 (1) Feb 17, 2009
This sounds great, but hardware issues are not addressed here. How is it possible to update the internet with this technology? By the time the hardware would be implemented, a whole new concept beyond the internet will be around.
Adriab
5 / 5 (2) Feb 18, 2009
It's a software approach. As long as the hardware is capable of running the algorithm to do this, we could use the existing infrastructure.
Avitar
not rated yet Feb 18, 2009
The Inernet Infrastructure is in a constant state of refresh. A switch technology generation is only about three years. The expenses for the internet are the right-of-way, installation of fiber, then the switching/driver hardware, then finally the routing/data systems. The same fiber laid by World Com for 30 Megabit/sec DS-3 ten years later was supporting 32 Gigabit/sec WDM without being changed out. In theory the same fiber could support hundreds of Terabits/sec. And yes we have improved the fiber technology since then.
lengould100
not rated yet Feb 18, 2009
Still, how are the routers in "greedy" routing supposed to know which major node is "nearest" their desired destination, without detailed network topology maps?
sanity
not rated yet Feb 20, 2009
The article states "the node's overall reach, and its degree is what makes the greedy routing strategy efficient at determining the shortest paths"

Actually, it is entirely possible to have a small world network where all nodes have exactly the same degree, and it will still be possible to navigate this network efficiently using greedy routing. High-degree nodes are not essential for navigability in a small world network.

The requirement is that the the probability of an edge existing between nodes be inversely proportional to the distance between them per Jon Kleinberg's 2000 paper "Navigation in a Small World". This doesn't necessitate any variation in the degrees of nodes in the network.
alixenos
not rated yet Jul 04, 2009
hi I'm a master student in computer engineering and I'm simulating a routing algorithm that don't need the entire network topology to discover routes. just like the above article deals with.can anyone help me to find more information about the algorithm?

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.