. 54
( 87 .)


The MPR set may be calculated according to the following algorithm [27]. Each node
starts with an empty MPR set. The set N is defined to be the set of one-hop neighbors with
which there exists bidirectional connectivity, and the set N2 is the set of two-hop bidirec-
tional neighbors. The first nodes that are selected for the MPR set are those nodes in N
that are the only neighbors of some node in N2. Next, the degree of each node n in N that
is not in the MPR set is calculated, where the degree is the number of nodes in N2 that n
covers that are still uncovered by the MPR set. As long as there are still nodes in N2 that
are not covered by nodes in the MPR set, the node in N that has the highest degree is in-
cluded in the MPR set. Once all the nodes in N2 are covered, this process terminates.
Once each node™s MPR set is selected, routing paths within the network can be deter-
mined. Because OLSR is a proactive protocol, each node maintains a route to every other
node in the network. To diffuse topology information, nodes periodically exchange Topol-
ogy Control (TC) messages with their neighbors. The TC message for a given node lists
the set of neighbors that have selected the sending node as an MPR. This is called the
Multipoint Relay Selector set of the node. Only this set of nodes is advertised within the
network. As a node receives TC messages from the other network nodes, it can create or
modify routing entries to each node in the network using any shortest path routing algo-
rithm, such as a variation of Dijkstra™s algorithm.

10.2.3 Topology Dissemination Based on Reverse-Path Forwarding
A different proactive approach is taken by the Topology-Based Reverse Path Forwarding
(TBRPF) protocol [6]. Like OLSR, TBRPF is a link-state routing protocol; however,
TBRPF employs a different technique for reducing overhead. TBRPF nodes compute a
shortest-path tree to all network nodes. To minimize bandwidth utilization, the nodes then
propagate only part of this tree to their neighbors. TBRPF consists of two main modules:
a neighbor discovery module for maintaining neighborhood information, and a routing
module for topology discovery and route computation.

The neighbor discovery module enables nodes to detect neighors and determine the
type of connectivity to each neighbor. Connectivity can be either bidirectional, unidirec-
tional, or, in the case of a broken link, the link can be lost. Each node periodically broad-
casts a Hello message to its neighbors. The Hello message is differential, in the sense that
only changes in the status of neighbors are reported. Each Hello message contains three
categories of neighbor information. A neighbor can be listed in the neighbor request,
neighbor reply, or neighbor lost category. The categories aid the nodes in determining the
directionality of the links with their neighbors. In general, when a node i changes the sta-
tus of its neighbor j, it includes node j in the appropriate list (indicating the neighbor™s
new status) in (typically) three consecutive Hello messages. This ensures that node j will
either learn of the status change or will declare node i to be lost after missing this number
of Hello messages.
The neighbor request list contains the addresses of those neighbors from which the
node has recently received Hellos, but for which it has not yet been determined that the
link to those neighbors is bidirectional. When a node i receives a Hello from a new neigh-
bor j, node i lists j in its neighbor table and flags the entry as a unidirectional link. The
next time node i transmits a Hello message, node i lists node j in the neighbor request list
of that message. This indicates that i is requesting that j confirm the receipt of i™s Hello, so
that the bidirectionality of the link can be confirmed. When node j receives node i™s Hello
listing j in the neighbor request, node j creates a neighbor table entry for i (if one does not
already exist), and marks the entry as bidirectional. In its next Hello, node j includes i™s
address in the neighbor reply list, indicating that the Hello message from i was received
and a bidirectional link exists. Node i can then update the entry for node j to be bidirec-
tional. To prevent the inclusion of transient links, nodes can wait to receive some thresh-
old number of Hello messages from a neighbor before creating a neighbor table entry for
that node.
Once a node has created a neighbor-table entry for a neighbor, the node must monitor
the status of that link to ensure that connectivity to the neighbor continues to exist. If a
node i misses the threshold number of Hello messages from a neighbor j, it updates the
state of that neighbor to be lost. The next time i sends a Hello message, it includes node j™s
address in the neighbor-lost list. If j receives the Hello, it notes that the bidirectional con-
nection to i has been lost, and it changes the status of node i in its neighbor table to unidi-
rectional. Otherwise, if node j fails to receive further Hello messages, it deletes node i
from its neighbor table and includes it in the neighbor-lost list of future Hello messages.
To perform routing, each TBRPF node computes a shortest-path source tree to each
reachable node in the network. The tree is computed using a modified version of Dijk-
stra™s algorithm. After computing the tree, nodes report only a part of the tree, called the
reportable subtree (RT), to neighboring nodes. To report RT, two types of topology up-
dates message are used. Periodic updates are sent reporting the entire RT. These full up-
dates are utilized to inform new neighbors of RT and ensure that all the necessary topolo-
gy information is eventually propagated. Smaller, more frequent updates are sent as
differential updates. The differential updates report only those changes to RT that have oc-
cured since the last periodic update. To reduce the number of control messages, topology
updates can be combined with Hello messages so that fewer control packets are transmit-
To calculate RT, let T(j) denote the subtree of node i™s source tree rooted at neighbor j.
For each neighbor j, node i includes T(j) in its reportable subtree RT if and only if it deter-
mines that one of its neighbors may select i to be its next hop on its shortest path to j. To

make this determination, node i computes the min-hop paths from each neighbor to every
other neighbor, using the node identification (ID) to break any ties.


Reactive routing techniques, also called on-demand routing, take a very different ap-
proach to routing than proactive protocols. A large percentage of the overhead from
proactive protocols stems from the need for every node to maintain a route to every other
node at all times. In a wired network, where connectivity patterns change relatively infre-
quently and resources are abundant, maintaining full connectivity graphs is a worthwhile
expense. The benefit is that when a route is needed, it is immediately available. In an ad
hoc network, however, link connectivity can change frequently and control overhead is
costly. Because of these reasons, reactive routing approaches take a departure from tradi-
tional Internet routing approaches by not continuously maintaining a route between all
pairs of network nodes. Instead, routes are only discovered when they are actually needed.
When a source node needs to send data packets to some destination, it checks its route
table to determine whether it has a route. If no route exists, it performs a route discovery
procedure to find a path to the destination. Hence, route discovery becomes on-demand. If
two nodes never need to talk to each other, then they do not need to utilize their resources
maintaining a path between each other. The route discovery typically consists of the net-
work-wide flooding of a request message. To reduce overhead, the search area may be re-
duced by a number of optimizations [10. 25, 31].
The benefit of this approach is that signaling overhead is likely to be reduced com-
pared to proactive approaches, particularly in networks with low to moderate traffic loads.
When the number of data sessions in the network becomes high, then the overhead gener-
ated by the route discoveries approaches, and may even surpass, that of the proactive ap-
proaches. The drawback to reactive approaches is the introduction of a route acquisition
latency. That is, when a route is needed by a source node, there is some finite latency
while the route is discovered. In contrast, with a proactive approach, routes are typically
available the moment they are needed. Hence, there is no delay to begin the data session.

10.3.1 Ad Hoc On-Demand Distance Vector Routing
The Ad Hoc On-Demand Distance Vector (AODV) Routing Protocol [48] provides on-de-
mand route discovery in mobile ad hoc networks. Like most reactive routing protocols,
route finding is based on a route discovery cycle involving a broadcast network search and
a unicast reply containing discovered paths. Similar to DSDV AODV relies on per-node se-
quence numbers for loop freedom and for ensuring selection of the most recent routing
path. AODV nodes maintain a route table in which next-hop routing information for desti-
nation nodes is stored. Each routing table entry has an associated lifetime value. If a route
is not utilized within the lifetime period, the route is expired. Otherwise, each time the route
is used, the lifetime period is updated so that the route is not prematurely deleted.
When a source node has data packets to send to some destination, it first checks its
route table to determine whether it already has a route to the destination. If such a route
exists, it can use that route for data packet transmissions. Otherwise, it must initiate a
route discovery procedure to find a route. To start route discovery, the source node creates
a route request (RREQ) packet. It places in this packet the destination node™s IP address,

the last known sequence number for that destination, and the source™s IP address and cur-
rent sequence number. The RREQ also contains a hop count, initialized to zero, and a
RREQ ID. The RREQ ID is a per-node, monotonically increasing counter that is incre-
mented each time the node initiates a new RREQ. In this way, the source IP address, to-
gether with the RREQ ID, uniquely identifies a RREQ and can be used to detect dupli-
cates. After creating this message, the source broadcasts the RREQ to its neighbors.
When a neighboring node receives a RREQ, it first creates a reverse route to the source
node. The node from which it received the RREQ is the next hop to the source node, and
the hop count in the RREQ is incremented by one to get the hop distance from the source.
The node then checks whether it has an unexpired route to the destination. If it does not
have a valid route to the destination, it simply rebroadcasts the RREQ, with the incre-
mented hop count value, to its neighbors. In this manner, the RREQ floods the network in
search of a route to the destination. Figure 10.2(a) illustrates this flooding procedure.
When a node receives a RREQ, it checks whether it has an unexpired route to the des-
tination. If it does have such a route, then one other condition must hold for the node to
generate a reply message indicating the route. The node™s route table entry for the destina-
tion must have a corresponding sequence number that is at least as great as the indicated
destination sequence number in the route request. That is,

dseqrt dseqRREQ

When this condition holds, the node™s route table entry for the destination is at least as re-
cent as the source node™s last known route to the destination. This condition ensures that
the most recent route is selected, and also guarantees loop freedom (see [47] for a proof).
Once this condition is met, the node can create a route reply (RREP) message. The RREP
contains the source node™s IP address, the destination node™s IP address, and the destina-
tion™s sequence number as given by the node™s route table entry for the destination. In ad-
dition, the hop count field in the RREP is set equal to the node™s distance from the desti-
nation. If the destination itself is creating the RREP, the hop count is set equal to zero.
After creating the reply, the node unicasts the message to its next hop toward the source
node. Thus, the reverse route that was created as the RREQ was forwarded is utilized to
route the RREP back to the source node.
When the next hop receives the RREP, it first creates a forward route entry for the desti-
nation node. It uses the node from which it received the RREP as the next hop toward the
destination. The hop count for that route is the hop count in the RREP, incremented by one.
This forward route entry for the destination will be utilized if the source selects this path for
data packet transmissions to the destination. Once the node creates the forward route entry,


(a) RREQ Broadcast (b) RREP Propagation (c) RERR Message

Figure 10.2. AODV route discovery and maintenance.

it forwards the RREP to the destination node. The RREP is thus forwarded hop by hop to
the source node, as indicated in Figure 10.2(b). Once the source receives the RREP, it can
utilize the path for the transmission of data packets. If the source receives more than one
RREP, it selects the route with the greatest sequence number and smallest hop count.
Once a route is established, it must be maintained as long as it is needed. A route that
has been recently utilized for the transmission of data packets is called an active route.
Because of the mobility of the nodes, links along paths are likely to break. Breaks on links
that are not being utilized for the transmission of data packets do not require any repair;
however, breaks in active routes must be quickly repaired so that data packets are not
dropped. When a link break along an active path occurs, the node upstream of the break
(i.e., closer to the source node) invalidates the routes to each of those destinations in its
route table. It then creates a route error (RERR) message. In this message it lists all of the
destinations that are now unreachable due to the loss of the link. After creating the RERR
message, it sends this message to its upstream neighbors that were also utilizing the link.
These nodes, in turn, invalidate the broken routes and send their own RERR messages to
their upstream neighbors that were utilizing the link. The RERR message thus traverses
the reverse path to the source node, as illustrated in Figure 10.2(c). Once the source node
receives the RERR, it can repair the route if the route is still needed.
AODV contains a number of optimizations and optional features [45]. To improve the
protocol performance and reduce overhead, source nodes can utilize an expanding ring
search to search for routes to the destination. The propagation of the RREQ is controlled
by modifying the time to live (TTL) value of the packet. Incrementally larger areas of the
network are searched until a route to the destination is discovered. If a route to the desti-
nation can be found in the local area, a network-wide flood can be avoided.
Another optimization is the local repair of link breaks in active routes. When a link
break occurs, instead of sending a RERR to the source, the node upstream of the break
can try to repair the link locally itself. If successful, fewer data packets are dropped be-
cause the route is repaired more quickly. If the local repair attempt is unsuccessful, a
RERR message is sent to the source node as previously described.
In addition to these optimizations, AODV contains a number of optional features to im-
prove operation in a wide range of scenarios. For instance, during route discovery, if only
intermediate nodes respond and the destination never receives a copy of the RREQ, the des-
tination will not necessarily have a route to the source node. If two-way conversation with
the destination is desired, this lack of route from the destination to the source can be prob-
lematic. Hence, AODV defines a gratuitous RREP that can be sent to the destination node
when a RREP is created by an intermediate node. This gratuitous RREP informs the desti-
nation of a route to the source, as if the destination had performed a route discovery.
Another optional feature is the RREP acknowledgment (RREP-ACK). When unidirection-
al links are suspected, the RREP-ACK can be utilized to ensure the next hop received the
RREP. If an RREP-ACK is not received, blacklists can be utilized to indicate unidirection-
al links so that these links are not used in future route discoveries. In addition, AODV allows
the use of periodic Hello messages for monitoring connectivity to neighboring nodes.

10.3.2 Dynamic Source Routing
The Dynamic Source Routing (DSR) protocol [24] is similar to AODV in that it is a reac-
tive routing protocol with a route discovery cycle for route finding. However, it has a few
important differences.

One of the primary characteristics of DSR is that it is a source routing protocol; instead
of being forwarded hop by hop, data packets contain strict source routes that specify each
node along the path to the destination. Route request (RREQ) and route reply (RREP)
packets accumulate source routes so that once a route is discovered, the source learns the
entire source route and can place that route into subsequent data packets. Figure 10.3(a)
illustrates the process of route discovery. The source node places the destination IP ad-
dress, as well as its own IP address, into the RREQ and then broadcasts the message to its
neighbors. When the neighboring nodes receive the message, they update their route to
the source and then append their own IP addresses to the RREQ. Thus, as the RREQ is
forwarded throughput the network, the traversed path is accumulated in the message.
When intermediate nodes receive the RREQ, they can create or update routing table en-
tries for each of the nodes listed in the source route, not just the source node.
When a node with a route to the destination receives the RREQ, it responds by creating
a RREP. If the node is the destination, it places the accumulated source route from the
RREQ into the RREP. Otherwise, if the node is an intermediate node, it concatenates its
source route to the destination to the accumulated route in the RREQ, and places this new
route into the RREP. Hence, in either scenario the message contains the full route between
the source and the destination. The source route in the RREP is reversed and the RREP is
unicast to the source. Note that as intermediate nodes receive and process the RREP, they
can create or update routing table entries to each of the nodes along the source route. Fig-
ure 10.3(b) illustrates the propagation of two RREPs back to the source. When a link
break in an established path occurs, the node upstream of the break creates a route error
(RERR) message and sends it to the source node.
Instead of maintaining a route table for tracking routing information, DSR utilizes a
route cache. The cache allows multiple route entries to be maintained per destination,
thereby enabling multipath routing, as will be discussed in Section 10.7.1. When one
route to a destination breaks, the source can utilize alternate routes from the route cache,
if they are available, to prevent another route discovery. Similarly, when a link break in a
route occurs, the node upstream of the break can perform route salvaging, whereby it uti-
lizes a different route from its route cache, if one is available, to repair the route. However,
even when route salvaging is performed, a RERR message must still be sent to the source


. 54
( 87 .)