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: Could 'Jedi Putter' be the force golfers need?

add to favorites email to friend print save as pdf

Related Stories

Creative activities outside work can improve job performance

2 hours ago

Employees who pursue creative activities outside of work may find that these activities boost their performance on the job, according to a new study by San Francisco State University organizational psychologist Kevin Eschleman ...

Simplicity is key to co-operative robots

3 hours ago

A way of making hundreds—or even thousands—of tiny robots cluster to carry out tasks without using any memory or processing power has been developed by engineers at the University of Sheffield, UK.

Freight train industry to miss safety deadline

4 hours ago

The U.S. freight railroad industry says only one-fifth of its track will be equipped with mandatory safety technology to prevent most collisions and derailments by the deadline set by Congress.

Recommended for you

Could 'Jedi Putter' be the force golfers need?

Apr 18, 2014

Putting is arguably the most important skill in golf; in fact, it's been described as a game within a game. Now a team of Rice engineering students has devised a training putter that offers golfers audio, ...

Better thermal-imaging lens from waste sulfur

Apr 17, 2014

Sulfur left over from refining fossil fuels can be transformed into cheap, lightweight, plastic lenses for infrared devices, including night-vision goggles, a University of Arizona-led international team ...

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?

More news stories

Poll: Big Bang a big question for most Americans

Few Americans question that smoking causes cancer. But they have more skepticism than confidence in global warming, the age of the Earth and evolution and have the most trouble believing a Big Bang created the universe 13.8 ...