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). [PDF]

Summary

This paper presents packet level simulation results of four multi-hop wireless ad hoc network routing protocols: DSDV, TORA, DSR, and AODV, in networks of 50 mobile nodes. The authors have extended the ns-2 network simulator to accurately model the MAC and the physical layer behavior of IEEE 802.11 standard, added a realistic wireless transmission channel model, and included node mobility to the simulator.

Protocols Considered

Distance-Sequenced Distance Vector (DSDV) is a hop-by-hop distance vector routing protocol, where each node maintains a routing table listing the “next hop” for each reachable distance and periodically broadcast the table. Sequence number of an entry determines its freshness – the higher the better. Better metric value is used to break a tie. In addition to periodical updates, a route update is triggered whenever a new sequence number is heard. Based on the waiting time to broadcast a triggered update there can be two variations of DSDV. This paper uses DSDV-SQ, where they instantly trigger an update.

Temporally-Ordered Routing Algorithm (TORA) discovers routes on-demand using a distributed link-reversal algorithm. Whenever a node needs to route to a particular destination, it broadcasts a QUERY packet. The recipient of the QUERY packet broadcasts an UPDATE packet. As the UPDATE packet propagates through the network, a directed path is created to the destination. TORA is implemented on top of IMEP (Internet MANET Encapsulation Protocol) for reliable, in-order delivery of control packets. Periodical BEACON and HELLO messages detect link status.

Dynamic Source Routing (DSR) is another on-demand routing protocol that uses source routing rather than hop-by-hop routing; each packet carries a complete, ordered list of nodes that it must traverse to reach the destination. The DSR protocol has two mechanisms: Route Discovery finds the list of nodes to reach a destination after the sender broadcasts a ROUTE-REQUEST packet (route caching is used to improve performance). Route Maintenance detects whether a source route has been invalidated due to topology changes.

Ad Hoc On-Demand Distance Vector (AODV) combines the basic on-demand mechanism of Route Discovery and Route Maintenance of DSR with DSDV hop-by-hop routing, sequence numbers, and periodic beacons of DSDV. Instead of using source routing, hop-by-hop states are created when a Route Discovery request is replied.

All in all, these four protocols differ in several design choices: on-demand vs constant route computation, hop-by-hop vs source routing, use of sequence numbers vs relying on ‘heights’ vs node list in source routing etc.

Evaluation

This paper considers three metrics to compare the protocols: packet delivery ratio (PDR), routing overhead, and path optimality (hop count). Major findings/confirmations are:

• With increasing mobility, PDR of DSDV-SQ drops significantly than the rest of the algorithms. For lower mobility, all the algorithms have closer PDRs.
• For DSR and AODV-LL, PDR is independent of offered traffic load. DSDV-SQ fails to converge after a certain threshold, most the losses caused by its storing only one route which turns out to be broken. TORA, on the other hand, performs well for lower loads but fails miserably once load goes up due to its higher overhead.
• DSDV-SQ maintains a constant routing overhead irrespective of mobility and load. DSR and AODV-LL show similar reaction to mobility and load, but AODV-LL has more overhead due to its lack of optimizations used in DSR and for not using source routing. TORA has high overhead even for smaller load and completely loses applicability with increasing load as IMEP faces congestion collapse.
• Lower speed of node movement does not affect the overhead for DSDV-SQ (it has to perform periodical broadcasting anyway). But in general, lower speed mellows the effect of mobility on all the protocols in terms of PDR and overhead.

Comments

This paper presents a good summary of different protocols for multi hop routing in wireless networks and presents a reasonable evaluation over a very large parameter space. Even though more sophisticated than its contemporary models, several of the important factors in modeling of wireless links are ignored in this paper. And using hop-count as a metric for path optimality is not the best choice. Overall, this was a good paper in its time but should have been replaced by now with experimental evaluation or more accurate simulation models.