Home › Ad hoc On-demand Distance Vector Routing (AODV)

Ad hoc On-demand Distance Vector Routing (AODV)

des-sert

des-aodv is our implementation of the Ad hoc On-Demand Distance Vector Routing (AODV) protocol as a variant for underlay routing. The protocol has been modified to optimize the route discovery in scenarios with unidirectional links.

Description:

AODV was developed for application in mobile ad-hoc networks. RFC 3561 highlights that AODV rapidly reacts to topology changes, offers "low processing and memory overhead, low network utilization, and determines unicast routes to destinations within the ad-hoc network".

With AODV no ressources are required when no route is needed as it is a reactive routing protocol. When a route is required and not yet availabe in the routing table, a so called Route-Request (RREQ) packet is broadcasted. The route request will be forwarded by all receiving nodes (flooding) to eventually arrive at the destination. Every node saves the predecessor from which it has received the RREQ.

Source node broadcasts the RREQ packet

When the RREQ packet finally arrives at this destination, a Route-Reply (RREP) packet is sent back to the source node along the path that the RREQ has taken through the network. The links between two nodes on this route could be unidirectional or exhibit a strong link asymmetry. Therefore a flag can be set in the RREP called 'A' bit to indicate that an acknowledgement is required. When a node receives a RREP it checks whether this flag is set and then replies by sending a Route-Reply-Acknowledgement (RREP-ACK) to the previous node from that it got the RREP. Thus the other node knows for sure, that the link is bidirectional. The next image shows how two nodes detect and activate a bidirectional link. When this mechanism is sucessfully used by all nodes along the route, source and destination can be sure that they can reach each other. When des-aodv is used with our custom option to discover asymmetric routes, bidrectional links are not required.

RREP-ACK is send out to activate a bidirectional path

When any node between source and destination receives a RREQ packet and has a matching route in its routing table, the RREQ is not forwarded but a RREP is sent to make the discovery more efficient, i.e., less delay and less overhead. Often there are multiple paths to a destination, which means that multiple RREPs can be generated. In this case, the source node will evaluate the RREPs and select the best route (shorted path as specified in the RFC). When a node detects a broken link, it sends a Route-Error (RERR) packet to the affected nodes, i.e., either a unicast or broadcast message to the nodes that are on a broken route. The next image shows a route that will stay in the routing table of the nodes until it is expired due to inactivity.

The final path will stay for a period of time in the routing table

AODV intends to reduce the number of messages in the network to conserve ressources. For example, sequence numbers are sent within every RREQ. Nodes will not forward packets that have been handled before. Additionally, AODV avoids the count-to-infinity problem with the sequence numbers. RREQ packets have a TTL to limit the forwarding to a specific number of hops. An "expanding ring search" can be applied that starts with a low TTL that is successively increased if no RREP is received. As last, the number of generated packets per time unit is bounded.

Variants:

  • des-aodv: based on the RFC
  • des-aodv-mp: supports asymmetric routes

Deviations from RFC 3561:

  • All links are always monitored for bidirectionality independent of whether the link is used for a route. RREQ are forwarded only when they are received over a bidirectional link. Thus routes are always bidirectional which is not the case in AODV as defined by the RFC.

  • RERR_RATELIMIT, section 6.11, page 23. Router error messages are limited to RERR_RATELIMIT per second but additional messages are not queued but dropped to avoid blocking.

Optional features of RFC 3561:

  • Local route repair, section 6.12., page 25. Nodes detecting a broken link will always send a RERR message. The RFC additionally allows for local link repair which in our opinion might lead to suboptimal routes.

  • Route Error (RERR) Messages, section 6.11, page 23. The RFC allow RERRs to be sent as unicast, broadcast, or iterative unicast. In des-aodv they are always sent as broadcast.