Four Ad Hoc Routing Protocols

Josh Broch, David Maltz, David Johnson, Yih-Chun Hu, Jorjeta Jetcheva, "A performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols"

Protocols

• Destination -Sequenced Distance Vector (DSDV)
• hop-by-hop protocol
• sequence numbers to prevent aging of routes
  
• each time step, every node sends a full dump of its routing table (destination, next hop, last sqn, metric) to its neighbors with route to itself attached as routing advertisement
• routes are imported if they are newer (by sqn) or have better metric and not too old (? I did not really understand the WST fudge factor in this protocol ?)
• Temporally Ordered Routing Algorithm (TORA)
  
  • hop-by-hop protocol
  • assigns height per node and per each destination
  • packets are routed "downhill" to destination
  • routes are requested through "QUERY" which initiates "UPDATES" which will set the heights
    
• Dynamic Source Routing (DSR)
• source-routing
• route requests with unique ID flooded, intermediate nodes append own address to request re-broadcast, flooded route requests are repeated with increasing back-off time and TTL
• destination replies to each route request with "route reply" containing the route sent back to originator of request along the reverse route
  
• store overheared route replies in link cache, run Dijkstra's algorithm for source routing, send route request if no route in link cache
• send route error back to origin of source-routed packet if 802.11 ACK fails, source has to recover
• maintain blacklist for detected unidirectional links (per node)
  


• Ad Hoc On-Demand Distance Vector (AODV)
  
  • hop-by-hop routing
  • combination of DSR and DSDV
    
  
  

Simulation

• ns-2 network simulator extended to model MAC (RTS/CTS ACK) and physical layer (delay, capture, carrier sense, transmission power, antenna gain, receiver sensitivity) behavior of 802.11 and node mobility, ARP, packet buffering
  
• ns is discrete even simulator
  

Performance metrics

• Goal: "measure the ability of [...] routing protocols to react to network topology change while continuing to [...] deliver data packets [...]"
  
• 50 nodes on 1500mx300m space, 210 different scenario files, CBR sources
• No TCP measurements (this is probably a more relevant number as TCP most deployed, but maybe the TCP dynamics has to change to accomodate different link layer characteristics)

Results

• DSDV-SQ fails to converge for high mobility, has high loss rates then
  
• TORA has largest overhead (by almost 10 for high mobility), DSDV-SQ has almost constant overhead independent of number of sources and degree of mobility
  
• TORA has high loss rates and bad overhead when >30 sources
• DSDV-SQ and DSR give slightly better paths