[112072] in North American Network Operators' Group
RE: Greedy Routing
daemon@ATHENA.MIT.EDU (Deepak Jain)
Wed Feb 18 18:02:50 2009
From: Deepak Jain <deepak@ai.net>
To: "Valdis.Kletnieks@vt.edu" <Valdis.Kletnieks@vt.edu>, Rod Beck
<Rod.Beck@hiberniaatlantic.com>
Date: Wed, 18 Feb 2009 18:01:06 -0500
In-Reply-To: <31096.1234996515@turing-police.cc.vt.edu>
Cc: nanog list <nanog@nanog.org>
Errors-To: nanog-bounces@nanog.org
>=20
> Maybe there's some critical insight in the paper that Physorg managed
> to totally not mention, I dunno.
I saw it the same way...=20
" 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 t=
he metric distance between them, then such networks are difficult to naviga=
te, as there is no way to choose one node over another based on distance. B=
ut when there is a connection between the link existence probability and th=
e 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 len=
gths... 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 w=
orks 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
AiNET
