Greedy Routing

Jake Mertel jake at
Wed Feb 18 23:39:44 UTC 2009

I had to laugh when reading... This is how I think someone who doesn't "get" how the Internet works may try to re-explain what a researcher explained to them about how metrics influence the flow of traffic in BGP path selection.


Jake Mertel
Nobis Technology Group, L.L.C.

Phone: (312) 281-5101 ext. 401
Fax: (808) 356-0417

Mail: 201 West Olive Street
Second Floor, Suite 2B
Bloomington, IL 61701

-----Original Message-----
From: Deepak Jain [mailto:deepak at] 
Sent: Wednesday, February 18, 2009 5:01 PM
To: Valdis.Kletnieks at; Rod Beck
Cc: nanog list
Subject: RE: Greedy Routing

> 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