ss">
Preemptive Routing in Ad Hoc Networks
 
Tom Goff
a
Nael Abu-Ghazaleh
b
Dhananjay Phatak
a
Ridvan Kahvecioglu
b
a
Electrical and Computer Engineering Dept.
University of Maryland Baltimore County
Baltimore, MD 21250
b
Computer Science Dept.
SUNY Binghamton
Binghamton, NY 13902
Abstract
Routing in Ad hoc networks is a challenging problem because nodes are mobile and links
are continuously being created and broken. Existing on-demand Ad hoc routing algorithms
initiate route discovery only after a path breaks, incurring a signicant cost in detecting the
disconnection and establishing a new route. In this work, we investigate adding proactive
route selection and maintenance to on-demand Ad hoc routing algorithms. More specif-
ically, when a path is likely to be broken, a warning is sent to the source indicating the
likelihood of a disconnection. The source can then initiate path discovery early, potentially
avoiding the disconnection altogether. A path is considered likely to break when the re-
ceived packet power becomes close to the minimum detectable power (other approaches
are possible). Care must be taken to avoid initiating false route warnings due to uctuations
in received power caused by fading, multipath effects and similar random transient phe-
nomena. Experiments demonstrate that adding proactive route selection and maintenance
to DSR and AODV (on-demand ad hoc routing protocols) signicantly reduces the num-
ber of broken paths, with a small increase in protocol overhead. Packet latency and jitter
also goes down in most cases. Because preemptive routing reduces the number of broken
paths, it also has a secondary effect on TCP performance unnecessary congestion han-
dling measures are avoided. This is observed for TCP trafc under different trafc patterns
(telnet, ftp and http). Additionally, we outline some problems in TCP performance in Ad
hoc environments.
¡
This work was supported by NSF Grants number ECS9875705, CDA800828, and EIA-9911099. Por-
tions of this work appeared in the Proc. of the International Conference on Mobile Computing and Network-
ing (MobiCom01) and the International Conference on Parallel Processing (ICPP01)
Email addresses:
tgoff@umbc.edu
(Tom Goff),
nael@cs.binghamton.edu
(Nael Abu-Ghazaleh),
phatak@umbc.edu
(Dhananjay Phatak),
ridvan kahvecioglu@non.hp.com
(Ridvan Kahvecioglu).
Preprint submitted to Journal of Parallel and Distributed Computing
13 June 2002 1
Introduction
Routing in Ad hoc networks is a challenging problem because of node mobility and the scarcity of
the bandwidth. Ad Hoc routing protocols fall into two categories: (1) Table-driven (proactive); and
(2) On-demand (reactive). Table-driven protocols attempt to maintain consistent, up-to-date routing
information among all nodes in the network. Thus, they require periodic route-update messages
to propagate throughout the network. On the other hand, On-demand protocols initiate a route
request ood whenever there is a path is needed between a pair of nodes. The advantage of the
table-driven approach is that routes to any destination are always available without the overhead of
a route discovery. In contrast, in On-demand routing, the source must wait until a route has been
discovered, but the overhead is signicantly less than Table-driven algorithms where many of the
updates are for unused paths. A large number of routing protocols have been suggested including
proactive (e.g., [13,21,26,29,31]), reactive (e.g., [23,28,30]) and hybrids (e.g., [17]). On demand
protocols provide better routing performance (and potentially lower overhead) for networks were
mobility is frequent; several simulation studies comparing Ad hoc routing protocols are available
in literature [7,10,22].
An active path fails due to mobility when a pair of nodes forming a hop along the path move out
of each others range. In both types of routing algorithm, an alternative path is sought only after
the current path fails. The cost of detecting a failure is high: several retries have to time-out before
a path is pronounced dead. Thus, when a path fails, packets experience large delays before the
failure is detected and a new path is established. In this paper we investigate introducing preemptive
route maintenance to Ad hoc routing protocols. More specically, when two nodes, A and B, are
moving out of each others range, source nodes of active paths that use the hop A to B are warned
that a path break is likely. With this early warning, the source can initiate route discovery and
switch to a more stable path potentially avoiding the path break altogether.
Preemptive route maintenance implements a soft-handoff of active paths when they become en-
dangered. Thus, it combines the best of on-demand and table-driven algorithms: the overhead is
kept small since updates are only triggered by active paths that are likely to break, and hand-off
time is minimized since corrective action is initiated early. Without preemptive maintenance, when
a path break occurs, the connectivity of the ow is interrupted and a hand-off delay is experienced
by the packets that are ready to be sent or in ight. This increases both the average and variance
(jitter) of packet latency. Furthermore, this delay and the loss of any packets in ight causes TCP
congestion avoidance mechanisms to take effect, further harming the performance of TCP con-
nections. Our solution preemptively nds other paths, in many cases seamlessly switching to an
alternative good path before a break, minimizing both the latency and jitter and avoiding inef-
ciencies due to unnecessary TCP backoff and congestion avoidance..
The effect of the suggested method is studied by extending Dynamic Source Routing (DSR) [23];
however, the proposed mechanism is general and can be used to enhance other routing algo-
rithms. To illustrate this generality, we present preliminary results for preemptive extensions to
AODV [30]. In addition, the method does not affect other Ad hoc routing optimizations such as
location awareness [9,24] and query localization [12]. The signal strength is used as the preemp-
2 tive trigger; other warning criteria such as location/velocity and congestion can also be used. In
fact, attributes such as path congestion, battery levels, and number of hops can be integrated into a
quality of path measure to continuously maintain the best path. We also investigate the effect
of using preemptive routing on the performance of TCP for different trafc scenarios. In the pro-
cess, we encounter some inefciencies in TCP performance that, to our knowledge, have not been
discovered by other researchers in this area.
The remainder of this paper is organized as follows. Section 2 introduces the preemptive algo-
rithm and discusses some possible optimizations to it. Section 3 discusses the generation of the
preemptive warning and analytically derives the optimal signal power threshold and compares it to
empirically observed values. Section 5 describes the extensions made to DSR to introduce preemp-
tive maintenance. Section 4 discusses the effect of preemptive routing on TCP operation. Section 6
presents an experimental evaluation of the proposed mechanism. Finally, Section 7 presents con-
cluding remarks.
2
Preemptive Route Maintenance
In traditional mobile and wired-network routing algorithms, a change of path occurs when a link
along the path fails or a shorter path is found. A link failure is costly because multiple retrans-
missions/timeouts are required to detect the failure and a new path has to be found (in on-demand
routing). Since paths fail so infrequently in wired networks, this is not an important cost. However,
routing protocols in mobile networks follow this model despite the signicantly higher frequency
of path disconnections that occur in this environment.
We propose preemptive route maintenance extension to on-demand routing protocols. With pre-
emptive maintenance, recovery is initiated early by detecting that a link is likely to break and nd-
ing and using an alternative path before the cost of a link failure is incurred. This technique is sim-
ilar to soft-handoff techniques used in cellular phone networks as mobiles move across cells [32].
When extended with preemptive maintenance, an on-demand routing algorithm consists of two
components: (i) detecting that a path is likely to be disconnected soon; and (ii) nding a better path
and switching to it. Note the similarity to pure on-demand protocols: we replace path failure, with
the likelihood of failure as the trigger mechanism for route discovery. Note that it is possible to
add preemptive maintenance to table-driven protocols as well to avoid the cost of detecting a path
failure.
A critical component of the proposed scheme is determining when path quality is no longer accept-
able (which generates a preemptive warning). The path quality can incorporate several criteria such
as signal strength, the age of a path, the number of hops, and rate of collisions. In this paper, we
restrict the path quality (and hence the preemptive warnings) to be a function of the signal strength
of received packets with the number of hops being used as secondary measure. Since most breaks
can be attributed to link failures due to node motion in a typical network with mobility, the signal
strength offers the most direct estimate of the ability of the nodes to reach each other. It is impor-
tant that signal power uctuations due to fading and other transient disturbances do not generate
3 erroneous preemptive warnings. The next section examines these issues in more detail describing
our app