Greedy routing

[pbg at cs.berkeley.edu (Brighten Godfrey)]

> 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