From: Seth Cooper (scooper@cs.washington.edu)
Date: Mon Nov 22 2004 - 01:29:37 PST
This paper introduces Greedy Perimeter Stateless Routing (GPSR), a
routing protocol for wireless networks. It recognizes the fact that
both the Link State and Distance Vector routing algorithms need to send
updates to the entire network to ensure consistency whenever topology
changes. This is not acceptable to wireless networks, where hosts are
mobile and topology will change frequently. It is also the case that LS
and DV need to hold state for each possible destination address at each
router, which becomes expensive as networks grow large. Sensitivity to
topology changes and number of routers prevent the traditional
algorithms from scaling in large wireless networks. GPSR attempts to
alleviate these problems by using geography to route packets. Packets
are marked with a destination location; each router only remembers its
immediate neighbors and their locations, and can then forward packets
greedily to the next neighbor closest to the destination.
One strength of the protocol is that it maintains very localized state.
Unlike previous routing algorithms, where even local changes would
have to be propagated nearly globally before the network reached a
consistent state, GPSR only needs to spread local changes locally. As
links are made and broken, only the nodes that lose the link or add the
link need to know about it. Each node only needs to remember its
immediate neighbors, because state is local. It is not necessary for a
node to remember how to reach every node in the network, only its
neighbors. Thus a network can grow arbitrarily large, and most nodes
will not be affected, only the nodes near the new addition.
One weakness of the protocol is the need to find a destination's
location before being able to send to them. Before it is possible for a
source to make a decision about which next hop is correct, it must know
where a packet is headed. The paper suggests a location database. Such
a location database will need to keep locations for all reachable end
hosts, which may not scale well as a network grows large. Also, because
the location database is reachable through GPSR itself, problems may
arise if the database itself moves.
This paper is relevant because it is important to always re-evaluate
protocols currently deployed in the Internet in the face of its
evolution. Although Link State works well when topology does not change
often, the increasing use of wireless networks has given rise to
networks where topology is constantly changing. This paper focuses on
some of the weaknesses of current routing algorithms when they are
confronted with this new development and presents effective solutions to
them.
This archive was generated by hypermail 2.1.6 : Mon Nov 22 2004 - 01:29:39 PST