Greedy Routing Enables Network Navigation Without a 'Map'
February 17, 2009 By Lisa Zyga
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.
May 21, 2009 |
not rated yet |
0
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.