From: Ethan Katz-Bassett (ethan@cs.washington.edu)
Date: Mon Nov 22 2004 - 01:31:27 PST
In this paper, the authors present their protocol for wireless routing. In
the greedy part of the protocol, routers know the position of the
destination and of their neighbors, and forward to the neighbor that is
closest to the destination (and closer than the router itself). If no
neighbor is closer to the destination than the router, the protocol switches
into perimeter mode to route around the empty zone in front of it. The
protocol is stateless in that each node only stores the location of its
neighbors; as the authors point out, in order to do any routing, at a
minimum each node must know something about its neighbors. The protocol
scales well because nodes only store information about neighbors, not the
entire network.
Because it was split into parts, the algorithm was fairly easy to follow. I
thought that the authors did a good job framing the problem in their
introduction, explaining what is hard about wireless routing and why other
routing protocols we have studied (DV, LS, BGP) do not apply in this
context. To point out just one problem, a protocol that floods with every
topology change would not work well with mobile hosts. In the UW
measurement paper we read recently, Neil, Ratul, and Tom concluded that
location information might lead to less inflated BGP routing. It seems like
a modified version of this protocol might work for that; each gateway would
know the location of all other gateways in the same AS (equivalent to
neighbors), and could greedily pick to exit at one closest to the
destination.
The authors assume the existence of a location lookup system; such a system
seems difficult, especially in a wireless setting. They leave it to future
work to investigate how such the protocol will perform with such a system.
Also, the paper assumes a 2d coordinate plane, rather than the 3d that GPS
would give.
As the paper reports, GPSR performed well against DSR in simulations. I do
not know enough about wireless to know if this was the correct protocol and
trial conditions (density, etc) to test against, but the results were
impressive. Overall, I thought the protocol was interesting and powerful; I
wonder how it would perform under real-world conditions.
This archive was generated by hypermail 2.1.6 : Mon Nov 22 2004 - 01:31:33 PST