ARTICLE IN PRESS
paths. One path is the shortest path and the other path is a
maximally disjointed path with the shortest path. The authors
defined two paths as maximally disjointed when they have the
least number of common nodes (Lee and Gerla, 2000).
Special control message: In addition to route discovery and
route maintenance control messages, a multipath routing
protocol uses additional control messages. The additional
control messages are used by a mobile node to collect
information about its neighbors so that suitable (node-
disjointed or link-disjointed) paths are discovered. For exam-
ple, a special control message called beckon is used in the
multipath protocol introduced in Yao et al. (2003) to create a
neighbor table. Another special control message called Hello
message is used in the protocol described in An et al. (2005) to
form a hierarchy among mobile nodes of a network. The special
messages used in a multipath routing can overwhelm the
network, especially when the network is large. These messages
can occupy a significant portion of the available bandwidth and
hence can adversely affect the performance of a network.
Route request storm: A multipath routing protocol can
generate a large number of route request messages in a
MANET. In the routing protocols proposed in Lee and Gerla
(2000), Ye et al. (2003) and Mueller and Ghosal (2005),an
intermediate node is not allowed to discard a duplicate request
message. Instead, intermediate nodes forward a duplicate
request message, which can cause a large quantity of
redundant overhead packets in the network.
Inefficient route discovery: The route discovery process of a
multipath routing protocol may not be as efficient as that of
the DSR and AODV protocols. In the route discovery processes
of the DSR or AODV protocols, an intermediate node is allowed
to send a reply from its route cache if it has any suitable route
in its route cache. This route reply helps a source node to find a
route to a destination in the shortest period of time because
the source node does not have to wait until the request packet
reaches a destination node and the destination node replies
back. To find node-disjointed or link-disjointed paths, the
multipath routing protocols proposed in Ye et al. (2003) and
Mueller and Ghosal (2005) prevent an intermediate node from
sending a reply from its route cache. Thus, a source node has to
wait until a destination replies back. Hence, the route
discovery process of a multipath routing protocol takes longer
compared to that of DSR or AODV protocols.
Duplicate packet processing: To ensure reliable data transfer,
the multipath routing protocols proposed in Tsirigos et al.
(2001) and W ang et al. (2005) send duplicate packets
using different paths. Duplicate packets create redundant
packets and thus occupy useful bandwidth. Moreover, to
generate duplicate packets at the source and to filter out these
duplicate packets at the destination, a special arrangement is
required. For example, two agents, namely duplicate packet
agent (DPA) and duplicate packet filter (DPF), are used in the
multipath routing protocol proposed in Wang et al. (2005) to
generate duplicate packets and to filter these duplicate packets,
respectively.
3. Reactive routing protocols for MANETs
Most of the multipath routing protocols cited in this paper
originate from DSR (Broch et al., 1998)orAODV(Perkins, 1997)
protocols. These multipath routing protocols modify the route
discovery and route maintenance mechanisms of DSR and AODV
protocols to improve the performances of a network in terms of
delay, reliability, overhead reduction, energy efficiency and
network throughput. In order to have an understanding of the
proposed multipath routing protocols it is necessary to know the
basic mechanisms of the DSR and AODV protocols.
3.1. The DSR protocol
The DSR (Broch et al., 1998) protocol consists of two basic
mechanisms: (1) route discovery and (2) route maintenance.
Route discovery is the mechanism by which a source node
discovers a route to a destination. When a source node wants to
send a data packet, it first looks into the route cache to find a
route. If a source cannot find a route in its route cache, the source
initiates a route discovery mechanism by broadcasting a request
packet to its neighbors. When a neighbor of a source receives a
request packet, it first checks whether the request packet is
intended for it or not. If a neighbor discovers that it is the
destination, it sends a reply back to the source after copying the
accumulated routing information contained in the route request
packet into a route reply packet. If it is not the destination, it
checks if there is any route available in the route cache for that
destination. If this neighboring node is neither a destination nor
does it have a route in the route cache to that destination, it
appends its address in the route request packet, and then it re-
broadcasts a route request packet to its neighbors. This process
continues until a route request packet reaches the destination
node. Then the destination node replies all route requests. When a
source node receives a route reply packet, it starts sending data
packets using the route indicated in the reply packet. If multiple
paths are discovered, it chooses a path that is the shortest one.
Route maintenance is the mechanism by which a node is able
to detect any change in the network topology. When a node
detects a broken link, for example, by using missing MAC layer
acknowledgments, it removes the link from its route cache and
sends a route error message to each node that has sent packets
over that link.
3.2. The AODV protocol
The AODV protocol (Perkins, 1997) is called a pure on-demand
routing protocol because a mobile node does not have to maintain
any routing information if it is not located in an active path. Like
DSR, the AODV protocol also consists of a route discovery and a
route maintenance mechanism. But the route request packet
structure of the AODV protocol is different from that of the DSR
protocol. To detect a fresh route from a stale route, each node
maintains two counters called node sequence ID and broadcast ID.
Each route request packet contains information about the
destination sequence number and the source sequence number
in addition to source address and destination address. The
sequence numbers are used to indicate the freshness of a route.
Each neighbor node either sends a reply to a source or re-
broadcasts a request message to its neighbors depending on
whether it is the destination or not. If a node is not the
destination, it needs to keep track of a request packet to set up
a reverse path as well as a forward path. When a destination
replies back to a source, it uses the reverse path. Mobile nodes can
determine whether a route is a current one or a stale one by
comparing the destination sequence number in the route request
packet with that of the sequence number stored in the route
cache. If the route request sequence number is greater than the
recorded one, it does not send a reply to the source. Instead, it re-
broadcasts that request message. An intermediate node only
replies from its route cache if the route request sequence number
is less than or equal to the sequence number stored in the route
cache. If a node does have a current route, it sends a reply using a
M. Tarique et al. / Journal of Network and Computer Applications 32 (2009) 1125–11431128