[Nrg-l] CS697 presentation - Monday May 12 @ 2pm

Jorge Londoño jmlon at cs.bu.edu
Fri May 2 11:12:36 EDT 2008

Andrej will be presenting the following paper:

Title:    Geographic routing using hyperbolic space
Author:   Robert Kleinberg.

In Proceedings of the 26th Annual Joint Conference of the IEEE Computer 
and Communications Societies (INFOCOM 2007), pp. 1902-1909.

We propose a scalable and reliable point-to-point routing algorithm for 
ad hoc wireless networks and sensor-nets. Our algorithm assigns to each 
node of the network a virtual coordinate in the hyperbolic plane, and 
performs greedy geographic routing with respect to these virtual 
coordinates. Unlike other proposed greedy routing algorithms based on 
virtual coordinates, our embedding guarantees that the greedy algorithm 
is always successful in finding a route to the destination, if such a 
route exists. We describe a distributed algorithm for computing each 
node's virtual coordinates in the hyperbolic plane, and for greedily 
routing packets to a destination point in the hyperbolic plane. (This 
destination may be the address of another node of the network, or it may 
be an address associated to a piece of content in a Distributed Hash 
Table. In the latter case we prove that the greedy routing strategy 
makes a consistent choice of the node responsible for the address, 
irrespective of the source address of the request.) We evaluate the 
resulting algorithm in terms of both path stretch and node congestion.

More information about the Nrg-l mailing list