Check out the new USENIX Web site.

USENIX, The Advanced Computing Systems Association

NSDI '06 — Abstract

Pp. 339–352 of the Proceedings

Geographic Routing Without Planarization

Ben Leong, Barbara Liskov, and Robert Morris, MIT Computer Science and Artificial Intelligence Laboratory


We present a new geographic routing algorithm, Greedy Distributed Spanning Tree Routing (GDSTR), that finds shorter routes and generates less maintenance traffic than previous algorithms. While geographic routing potentially scales well, it faces the problem of what to do at local dead ends where greedy forwarding fails. Existing geographic routing algorithms handle dead ends by planarizing the node connectivity graph and then using the right-hand rule to route around the resulting faces.

GDSTR handles this situation differently by switching instead to routing on a spanning tree until it reaches a point where greedy forwarding can again make progress. In order to choose a direction on the tree that is most likely to make progress towards the destination, each GDSTR node maintains a summary of the area covered by the subtree below each of its tree neighbors. While GDSTR requires only one tree for correctness, it uses two for robustness and to give it an additional forwarding choice.

Our simulations show that GDSTR finds shorter routes than geographic face routing algorithms: GDSTR's stretch is up to 20% less than the best existing algorithm in situations where dead ends are common. In addition, we show that GDSTR requires an order of magnitude less bandwidth to maintain its trees than CLDP, the only distributed planarization algorithm that is known to work with practical radio networks.

  • View the full text of this paper in HTML and PDF. Listen to the presentation in MP3 format.
    Click here if you have forgotten your password Until May 2007, you will need your USENIX membership identification in order to access the full papers. The Proceedings are published as a collective work, © 2006 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.

  • If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.
To become a USENIX Member, please see our Membership Information.

Last changed: 1 June 2006 ch