A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols

J. Broch, D. Maltz, D. Johnson, Y-C Hu, J. Jetcheva, "A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols," ACM Mobicom Conference, (October 1998).

This paper did a detailed simulated performance comparison  of 4 multi-hop wireless Ad Hoc Network Routing Protocols: DSDV, TORA, DSR and AODV. To enable these protocols to be simulated over ns-2, they extended the simulator to include the following:

• Node mobility
• Realistic physical layer (with support of propagation delay, capture effects and carrier sense)
• Radio Network Interfaces
• IEEE 802.11 MAC protocol using DCF

The following routing protocols were simulated and studied as part of this paper:

• DSDV: This protocol involves keeping various tuples of the form < destination, next hop, seq. no, metric > for each destination. It requires each node to periodically broadcast routing updates so that adjacent nodes can learn about best possible routes. The authors talked about 2 modifications of DSDV -- DSDV-SQ and DSDV which differs by the fact that in the former receipt of a new sequence number for a destination will cause a triggered update while in the latter, receipt of  a new metric would result in a triggered update.
• TORA: This is a distributed routing protocol based on a 'link reversal' algorithm. It discovers the routes on demand. The idea is that whenever route A has to QUERY a route to B, it sends a request and a node C in the path sends an UPDATE back to A telling about the path as well as its 'height' wrt B. When A gets the packet, it adjusts its height accordingly to be greater than that of C. These 'heights' help in differentiating between good and bad routes.
• DSR: It uses source routing rather than hop-by-hop routing, with each packet to be routed carrying the complete ordered list of nodes that it must pass in its header. It consists of ROUTE DISCOVERY and ROUTE MAINTENANCE phases. 
• AODV: This was essentially a combination of both DSR (on demand mechanism for Route Discovery) and DSDV (Hop-by-Hop routing, sequence numbers and periodic beacons). 

The evaluation of these protocols was done in a simulated environment of 50 wireless nodes forming an ad hoc network moving  about over a rectangular (1500m X 300m) flat space for 900 seconds of simulated time. Evaluations found out that DSR was a clear winner among all based on both packet recv/sent ratio and routing overhead. There were some intrinsic problems with DSDV due to which it was unable to transmit packets to nodes whose path consisted of broken links. This was due to the fact that DSDV had the limitation of keeping only 1 route per path. As far as the routing overheads were concerned, DSR did the best (probably because it promiscuously hears and caches requests), followed by DSDV-SQ.  TORA and AIDV on the other hand had considerable routing overhead. When moving nodes were brought into picture, pretty much all the protocols behaved in a similar manner as far as send/recv ratios were concerned while DSR clearly outperformed everyone on the routing overhead metric.