Source of information: http://www.eecs.harvard.edu/~htk/publication/2000-mobi-karp-kung.pdf
We present Greedy Perimeter Stateless Routing (GPSR), a novel routing protocol for wireless datagram networks that uses the positions of routers and a packet’s destination to make packet forwarding decisions. GPSR makes greedy forwarding decisions using only information about a router’s immediate neighbors in the network topology. When a packet reaches a region where greedy forwarding is impossible, the algorithm recovers by routing around the perimeter of the region. By keeping state only about the local topology, GPSR scales better in per-router state than shortest-path and ad-hoc routing protocols as the number of network destinations increases. Under mobility’s frequent topology changes, GPSR can use local topology information to find correct new routes quickly. We describe the GPSR protocol, and use extensive simulation of mobile wireless networks to compare its performance with that of Dynamic Source Routing. Our simulations demonstrate GPSR’s scalability on densely deployed wireless networks.
In networks comprised entirely of wireless stations, communication
between source and destination nodes may require traversal
of multiple hops, as radio ranges are finite. A community of adhoc
network researchers has proposed, implemented, and measured
a variety of routing algorithms for such networks. The observation
that topology changes more rapidly on a mobile, wireless network
than on wired networks, where the use of Distance Vector
(DV), Link State (LS), and Path Vector routing algorithms is wellestablished,
motivates this body of work.
Small inaccuracies in the state at a router under both DV and LS can cause routing loops or disconnection [29]. When the
topology is in constant flux, as under mobility, LS generates torrents
of link status change messages, and DV either suffers from
out-of-date state [4], or generates torrents of triggered updates.
The two dominant factors in the scaling of a routing algorithm are: the rate
of change of the topology and the number of routers in the routing domain.
Both factors affect the message complexity of DV and LS routing
algorithms: intuitively, pushing current state globally costs packets
proportional to the product of the rate of state change and number
of destinations for the updated state.
Hierarchy is the most widely deployed approach to scale routing as
the number of network destinations increases. Without hierarchy,
Internet routing could not scale to support today’s number of Internet
leaf networks. An Autonomous System runs an intra-domain
routing protocol inside its borders, and appears as a single entity
in the backbone inter-domain routing protocol, BGP. This hierarchy
is based on well-defined and rarely changing administrative
and topological boundaries. It is therefore not easily applicable to
freely moving ad-hoc wireless networks, where topology has no DV and LS algorithms require continual distribution of a current
map of the entire network’s topology to all routers. DV’s Bellman-
Ford approach constructs this global picture transitively; each router
includes its distance from all network destinations in each of its periodic
beacons. LS’s Dijkstra approach directly floods announcements
of the change in any link’s status to every router in the net-
Caching has come to prominence as a strategy for scaling ad-hoc
routing protocols. Dynamic Source Routing (DSR) [12], Ad-Hoc
On-Demand Distance Vector Routing (AODV) [21], and the Zone
Routing Protocol (ZRP) [10] all eschew constantly pushing current
topology information network-wide. Instead, routers running these This research was supported in part by AFOSR MURI Grant
F49620-97-1-0382, and NSF Grant CDA-94-0124, and in part by
Microsoft Research, Nortel, Sprint, ISI, and ACIRI.
as required by their packet forwarding load, and cache it aggressively.
When their cached topological information becomes out-ofdate,
these routers must obtain more current topological information
to continue routing successfully. Caching reduces the routing
protocols’ message load in two ways: it avoids pushing topological
information where the forwarding load does not require it (e.g., at
idle routers), and it often reduces the number of hops between the
router that has the needed topological information and the router
that requires it (i.e., a node closer than a changed link may already
have cached the new status of that link).
We propose the aggressive use of geography to achieve scalability
in our wireless routing protocol, Greedy Perimeter Stateless Routing (GPSR). We aim for scalability under increasing numbers of
nodes in the network, and increasing mobility rate. As these factors
increase, our measures of scalability are: Routing protocol message cost (How many routing protocol
packets does a routing algorithm send?), Application packet delivery success rate (What fraction of
applications’ packets are delivered successfully by a routing
algorithm?), Per-node state (How much storage does a routing algorithm require at each node?)