Greedy Routing

Deepak Jain deepak at
Wed Feb 18 23:01:06 UTC 2009

> Maybe there's some critical insight in the paper that Physorg managed
> to totally not mention, I dunno.

I saw it the same way... 

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

If your network doesn't calculate or use metrics or weights, or AS path lengths... then you are not able to
throw packets like fairy dust to their intended destination. Worse, if you use metrics unrelated to distance
(like link cost) you could actually send your packets the wrong way.

It's funny, but I think they said that their math shows that the Internet works to generally route packets
(to a shorter path) than other possible paths.

I'm sure that will come as a surprise to all of us.

Deepak Jain

More information about the NANOG mailing list