Greedy Routing
http://www.physorg.com/news154093231.html Roderick S. Beck Director of European Sales Hibernia Atlantic 13-15, rue Sedaine, 75011 Paris http://www.hiberniaatlantic.com
Re: Greedy Routing
On Wed, 18 Feb 2009 22:12:02 GMT, Rod Beck said: http://www.physorg.com/news154093231.html From the fine article: 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. Sounds suspiciously like throw the packet at the router that's got the shortest AS path to the destination doesn't it? You don't need to know the entire topology to know router X is 2 AS's closer to the dest than router Y once X and Y have been loaded with the hidden metric space known as a BGP update ;) I'm not sure this article is actually telling us anything we didn't already know. Now if there was a way to compute those distance metrics without global knowledge - if there was only an algorithm that only cared about what was upstream from a locally connected link and whether it was connected. Say, we could call it a link-state routing protocol Now if they were able to actually develop a link-state protocol that involved *only* local adjacency announcements and not flooded announcements, *that* would be something... But what I see here is if somebody developed that, we'd be able to route more efficiently. Maybe there's some critical insight in the paper that Physorg managed to totally not mention, I dunno. pgph2MsWsbdwH.pgp Description: PGP signature
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 AiNET
RE: Greedy Routing
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. Regards, Jake Mertel Nobis Technology Group, L.L.C. Web: http://www.nobistech.net/ 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:dee...@ai.net] Sent: Wednesday, February 18, 2009 5:01 PM To: valdis.kletni...@vt.edu; 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 AiNET
Re: Greedy routing
On Wed, 18 Feb 2009 22:12:02 GMT, Rod Beck said: http://www.physorg.com/news154093231.html From the fine article: 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. Sounds suspiciously like throw the packet at the router that's got the shortest AS path to the destination doesn't it? You don't need to know the entire topology to know router X is 2 AS's closer to the dest than router Y once X and Y have been loaded with the hidden metric space known as a BGP update ;) No, it's quite different from BGP. The high level point is that BGP needs to know a lot of information about the network in order to route, while greedy routing (when it works) requires very little state. To make it concrete: You're right that BGP doesn't need to know the entire topology, but it comes quite close, in terms of the total amount of information it has. To throw the packet at the router that's got the shortest AS path to the destination, you need to have information from every neighbor about every destination. A BGP router in general needs one FIB entry for every destination (IP prefix) in the Internet, i.e., about 300,000 entries, and in the RIB it has potentially 300K from every BGP neighbor potentially, millions of entries. In contrast, greedy routing would require probably less than a dozen entries for the average router. This is because the router only needs to know its own identifier, and those of its immediate neighbors. The routing algorithm has some distance function dist (ID1, ID2). A packet comes with some destination identifier D, and the router compares the distance dist(N, D) for each neighbor N, and forwards the packet to the neighbor with smallest distance. For example, suppose you know the topology is a two-dimensional grid. Then the identifier is the router's (X,Y) coordinates and the distance function can be Euclidean distance. The main catch is of course that most networks don't have such nice regular structure like the grid. Essentially, greedy routing tries to summarize the structure of the network using a very small amount of information. And there are topologies whose pattern of links is too complicated (in a certain sense) for greedy routing to be able to summarize it. Therefore it is interesting when you find a network in which greedy routing works, especially if that network is vaguely realistic. The most well-known example is Jon Kleinberg's work on small world networks (http://tinyurl.com/dye7ub), which gives some theoretical backing to Milgram's six degrees of separation experiment from the 1960s (which basically used a kind of greedy routing). This physorg paper seems to be very much in the same style, showing that greedy routing works on an Internet-like graph. (Disclaimer: I have only read the above article, not the paper.) Of course there are plenty of reasons you would not use this in practice, e.g., it gives the router little control over routing policy, traffic engineering, etc. I'm not sure this article is actually telling us anything we didn't already know. Now if there was a way to compute those distance metrics without global knowledge - if there was only an algorithm that only cared about what was upstream from a locally connected link and whether it was connected. Say, we could call it a link-state routing protocol Now if they were able to actually develop a link-state protocol that involved *only* local adjacency announcements and not flooded announcements, *that* would be something... But what I see here is if somebody developed that, we'd be able to route more efficiently. This is essentially what they are doing. The distance is computed based on only local knowledge, not global knowledge. Each router needs to know only local adjacencies. Caveat: I haven't read the paper and don't know how they assign the router identifiers, so I am answering only about greedy routing in general. ~Brighten Godfrey
