Ad Hoc On-Demand Distance Vector Routing Protocol

AODV

The Ad Hoc On-Demand Distance Vector Routing Protocol is a reactive routing protocol based on DSDV. It was introduced in 1997. AODV is designed for networks with tens to thousands of mobile nodes. One feature of AODV is the use of a destination sequence number for each routing table entry. The sequence number is created by the destination node. The sequence number included in a route request or route reply is sent to requesting nodes. Sequence number are very important because they ensures loop freedom and is simple to program. Sequence numbers are used by other nodes to determine the freshness of routing information. If a node has the choice between 2 routes to a destination, a node is required to select the one with the greatest sequence number.

AODV deals with routing table. Every node has a routing table. When a node knows a route to the destination, it sends a route reply to the source node. Its entries are:

• Destination IP Address
• Prefix Size
• Destination Sequence Number
• Next Hop IP Address
• Lifetime (expiration or deletion time of the route)
• Hop Count (number of hops to reach the destination)
• Network Interface
• Other state and routing flags (e.g., valid, invalid)

Route Requests (RREQs), Route Replies (RREPs) and Route Errors (RERRs) are message types defined by AODV. The next pictures will give an example of AODV.

Example

S would like to communicate with D



The node broadcasts a RREQ to find a route to the destination. S generates a Route Request with destination adress, Sequence number and Broadcast ID and sent it to his neighbour nodes



Each node receiving the route request sends a route back (Forward Path) to the node.



A route can be determined when the RREQ reaches a node that offers accessibility to the destination, e.g., the destination itself).



The route is made available by unicasting a RREP back to D and is written in the routing table from S. After receiving the route reply every node has to update its routing table if the sequence number is more recent.



Now node S can communicate with node D.



When a link break in an active route is detected, the broken link is invalid and a RERR message is sent to other nodes. If the nodes have a route in their routing table with this link, the route will be erased. Node S sends once again a route request to his neighbour nodes. Or a node on the way to the destination can try to find a route to D. That mechanism is called: Local Route Repair.

Advantages

• loop free routing
• optional multicast
• reduced control overhead

Disadvantages

• delay caused by route discovery process
• bidirectional connection needed in order to detect an unidirectional link

References

[Perkins1997] Original Internet Draft
[Perkins1999] Original Conference Paper
[Perkins2003] Last Internet Draft
[RFC3561] Original RFC

Links

Kernel AODV from the Wireless Communications Techonlogies Group

"Ad Hoc On-Demand Distance Vector Routing Protocol" is mentioned on: Ad-Hoc Protocols (Classification) | Ad-Hoc Protocols (History) | Ad-Hoc Workshop Winter 04/05 (Termine)