Ad Hoc On-Demand Distance Vector Routing (AODV)

AODV is a reactive ad-hoc routing protocol. It also discovers routes on an as needed
basis via a route discovery process similar to route discovery in DSR routing protocol. However,
AODV adopts a very different mechanism to maintain routing information. It uses traditional
routing tables, one entry per destination. This is in contrast to DSR, which can maintain multiple
route cache entries for each destination. Without source routing, AODV relies on routing table
entries to propagate a Route Reply (RREP) back to the source and, subsequently, to route data
packets to the destination. AODV uses sequence numbers maintained at each destination to
determine freshness of routing information and to prevent routing loops. All routing packets
carry these sequence numbers.
When a node needs a route to a destination, it broadcasts a Route Request (RREQ)
message. As this message is spread throughout the network, each node that receives it sets up a
reverse route, i.e., a route towards the requesting node. As soon as the RREQ message reaches a
node with fresh enough routes to the specified destination, or the destination itself, a RREP
unicast message is sent back to the requesting node. Intermediate nodes use the reverse routes
created earlier for forwarding RREP messages. If the source node moves, it may reinitiated its
route discovery process. If the intermediate node moves, a special RREP is sent to affected
source nodes. This could cause the destination node to initiate a route discovery of its own, if it
needs to communicate with the requesting node (e.g. to reply to a TCP connection request). To
solve this, the originator of a RREQ message should set a gratuitous RREP flag in the RREQ if it
believes that this situation is likely to occur. An intermediate node receiving a RREQ with this flag set and replying with a RREP must also unicast a gratuitous RREP to the destination node.
This allows the destination node to learn a route back to the requesting node.
Nodes monitor the link status of the next hop in active routes, i.e., routes whose entries
are marked as valid in the routing table. This can be done by observing periodic broadcasts of
HELLO messages (beacons) from other nodes, or any suitable link layer notifications. When a
link failure is detected, a list of unreachable destinations is put into a RERR message and sent
out to neighboring nodes, called precursors that are likely to use the current node as their next
hop towards those destinations. For this purpose, nodes maintain a precursor list for each routing
table entry. Finally, routes are only kept as long as they are needed. If a route is not used for a
certain period of time, its corresponding entry in the routing table is invalidated and subsequently
deleted.
Although AODV does not depend specially on particular aspects of the physical medium
across which packets are disseminated its development has been largely motivated by limited
range broadcast media such as those utilized by infrared or radio frequency wireless
communications adapters Using such media a mobile node can have neighbors which hear its
broad casts and yet do not detect each other (Tanenbaum 1996).
When a route has been established, it is being maintained by the source node as long as
the route is needed. Movements of nodes affect only the routes passing through this specific node
and thus do not have global effects. If the source node moves while having an active session, and
loses connectivity with the next hop of the route, it can rebroadcast an RREQ. If though an
intermediate station loses connectivity with its next hop it initiates a Route Error (RERR)
message and broadcasts it to its precursor nodes and marks the entry of the destination in the route table as invalid, by setting the distance to infinity. The entry will only be discarded after a
certain amount of time, since routing information may still be used. When the RERR message is
received by a neighbor it also marks its route table entry for the destination as invalid and sends
again RERR messages to its precursors (Mario Cagalj, 2003).
References:
1. A. S. Tanenbaum, Computer Networks, 3rd edition, Prentice Hall, 1996.
2. Mario Cagalj, Performance Evaluation of AODV Routing Protocol: Real-Life
Measurements, Semester project report, 2003. Accessed 15/9/14 on
http://icawww.epfl.ch/Publications/Cagalj/ZurkindenCH03.pdf