AD HOC ON-DEMAND DISTANCE VECTOR (AODV)

 AODV was proposed to standardization by the RFC 3561 in July 2003. It was designed by the same people who designed DSDV. AODV is a distance vector routing protocol, which means routing decisions will be taken depending on the number of hops to destination. A particularity of this network is to support both multicast and unicast routing.

 Algorithm

  The AODV algorithm is inspired from the Bellman-Ford algorithm like DSDV.

 The principle change is to be On Demand.

 The node will be silent while it does not have data to send. Then, if the upper layer is requesting a route for a packet, a ―ROUTE REQUEST‖ packet will be sent to the direct neighborhood. If a neighbour has a route corresponding to the request, a packet ―ROUTE REPLY‖ will be returned.

 Otherwise,  each  neighbour  will  forward  the  ―ROUTE  REQUEST‖  to  their  own neighborhood, except for the originator and increment the hop value in the packet data.

 They also use this packet for building a reverse route entry (to the originator). This process occurs until a route has been found.

 Another part of this algorithm is the route maintenance.

 While a neighbour is no longer available, if it was a hop for a route, this route is not valid anymore.

 AODV uses ―HELLO‖ packets on a regular basis to check if they are active neighbours.

 Active neighbours are the ones used during a previous route discovery process. If there is no response to the ―HELLO‖ packet sent to a node, then, the originator deletes all associated routes in its routing table. ―HELLO‖ packets are similar to ping requests. 

 While transmitting, if a link is broken (a station did not receive acknowledgment from the layer 2), a ―ROUTE ERROR‖ packet is unicast to all previous forwarders and to the sender of the packet.

Illustration

In the example illustrated by figure 1, A needs to send a packet to I. A ―ROUTE REQUEST‖ packet will be generated and sent to B and D (a). B and D add A in their routing table, as a reverse route, and forward the ―ROUTE REQUEST‖ packet to their neighbours (b). B and D ignored the packet they exchanged each others (as duplicates). The forwarding process continues while no route is known (c). Once I receives the ―ROUTE REQUEST‖ from G (d), it generates the ―ROUTE REPLY‖ packet and sends it to the node it received from. Duplicate packets continue to be ignored while the ―ROUTE REPLY‖ packet goes on the shortest way to A, using previously established reverse routes (e and f).

The reverse routes created by the other nodes that have not been used for the ―ROUTE REPLY‖ are deleted after a delay. G and D will add the route to I once they receive the ―ROUTE REPLY‖ packet.

 Characteristics of AODV

·         Unicast, Broadcast, and Multicast communication.  

·         On-demand route establishment with small delay.

·         All routes are loop-free through use of sequence numbers.  

·         Use of Sequence numbers to track accuracy of information.  

·         Only keeps track of next hop for a route instead of the entire route.  

·         Use of periodic HELLO messages to track neighbors.

 Advantages and Disadvantages

 The main advantage of this protocol is that routes are established on demand and destination sequence numbers are used to find the latest route to the destination. The connection setup delay is lower.

 One of the disadvantages of this protocol is that intermediate nodes can lead to inconsistent routes if the source sequence number is very old and the intermediate nodes have a higher but not the latest destination sequence number, thereby having stale entries. Also multiple RouteReply packets in response to a single RouteRequest packet can lead to heavy control overhead.

 Another disadvantage of AODV is that the periodic beaconing leads to unnecessary bandwidth consumption.