AODV-Spanning Tree (AODV-ST) is a routing protocol designed for wireless mesh networks. It is an extension to the well-known AODV routing protocol designed for mobile ad hoc networks. Advantages of AODV-ST over AODV include support for high throughput routing metrics, automatic route maintenance for common-case traffic, and low route discovery latency.
You will find below a brief description of AODV-ST and its advantages over AODV. If you want to simply download AODV-ST without diving into the details, click here.
AODV Overview
Before presenting AODV-ST, a brief description AODV is in order. AODV, in short for Ad hoc On Demand Distance Vector routing protocol, is designed for mobile ad hoc networks (MANETs). AODV is an on demand algorithm, meaning that it builds routes between nodes only when needed by source nodes. AODV relies on an optimized flooding mechanism to discover routes. During the optimized flooding, reverse routes are installed towards the source that initiated the route discovery. Once a destination is located, the destination initiates a route reply message (RREP) that is unicasted back to the source along the just discovered reverse route. As the RREP makes its way back to the source, a forward route to the destination is installed at each intermediate node lying on the path traversed by the message. AODV utilizes sequence numbers to ensure route freshness and loop-less data forwarding. A comprehensive description of AODV can be found here.
AODV Drawbacks
AODV, used as-is, can result in poor performance in a wireless mesh network. The reasons are as follows:
AODV lacks support for high throughput routing metrics: AODV is designed to support the shortest hop count metric. This metric favors long, low-bandwidth links over short, high-bandwidth links.
AODV lacks an efficient route maintenance technique: A route discovered with AODV may no longer be the optimal route further along in time. This situation can arise because of network congestion or the fluctuating characteristics of wireless links. AODV lacks a provision to re-discover the new optimal route.
AODV route discovery latency is high: AODV is a reactive routing protocol. This means that AODV does not discover a route until a flow is initiated. This route discovery latency result can be high in large-scale mesh networks.
AODV-ST Advantages
AODV-Spanning Tree (AODV-ST) protocol eliminates the above limitations as follows: First, it supports high throughput metrics, such as the Expected Transmission Count metric (ETX) and the Expected Transmission Time metric (ETT). Our current implementation supports the ETX although other metrics can be easily supported (Check the README contained in package). Second, it proactively maintains spanning trees whose roots are the gateways in the mesh network. Spanning trees significantly reduce route discovery latency and achieve lightweight, soft state route maintenance. Finally, it employs IP-in-IP tunnels to route data traffic from relays to the gateways in the mesh network. Tunneling to the gateway eliminates unnecessary route discovery overhead for external destinations reachable only via the gateway. Tunneling also reduces route table size at each mesh relay to the sum total of number of relays and gateways in the mesh.
The above package has built in support for spanning tree creation, the ETX routing metric, and tunneling to gateways. Support for alternate routing metrics can be enabled by communicating link weights via the proc filesystem. A commented out portion of the the module.c file, if uncommented, should enable this feature.
The current implementation is a modified version of the NIST AODV implementation. Kudos to Luke Klein-Berndt for compiling together such a stable AODV implementation. It proved to be a great starting point for AODV-ST.
Needless to say, AODV-ST comes with no warranties whatsoever. I have tested AODV-ST extensively on a testbed I maintain and I am quite happy with the results. Please feel free to send me any bug reports or general feedback about AODV-ST.
WRT54G Caveat:
For OpenWRT on the Linksys WRT54G, I have noticed that the above package causes the WRT54G to reboot. I have also received feedback of this nature from people who have tried AODV-ST on the WRT54G. This occurs because the above package uses floating point operations to compute link reliability. The WRT54G lacks hardware support for floating point operations and for this reason the device reboots itself. I am told that some floating point emulation packages can address this problem. Unfortunately, I have had no luck getting them to work. As an alternative, I hacked together some code to replace floating point operations with integer operations. Simply replace the files contained in the aodv-st package with the files contained in this package. For instructions on executing AODV-ST on the WRT54G, check here.
The paper motivates the design of AODV-ST. Details on route discovery and route maintenance are also given. Finally, some performance results from the use of AODV and AODV-ST on the UCSB MeshNet are presented.
This work is currently supported in part by the National Science Foundation. Any opinions, findings, and conclusions or recommendations expressed in these materials are those of the author(s) and do not necessarily reflect the views of any of these organizations. We are very grateful to our sponsor - thank you!!!
