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.

( -- 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

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

Explore further: Star power: Troubled ITER nuclear fusion project looks for new path

Related Stories

ICANN chief stepping down in early 2016

1 hour ago


HP sells stake in China unit for $2.3 bn

1 hour ago

Hewlett-Packard announced Thursday it was selling a 51 percent stake in its China-based server business, creating a joint venture with Tsinghua Holdings that will be a sector leader in China.

Recommended for you

SLAC gears up for dark matter hunt with LUX-ZEPLIN

May 21, 2015


First images of LHC collisions at 13 TeV

May 21, 2015


User comments : 6

Adjust slider to filter visible comments by rank

Display comments: newest first

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.
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.
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.
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?
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.
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?


Click here to reset your password.