Implicit source routes for on-demand ad hoc network routing

In an ad hoc network, the use of source routing has many advantages, including simplicity, correctness, and flexibility. For example, all routing decisions for a packet are made by the sender of the packet, avoiding the need for up-to-date routing information at intermediate nodes and allowing the routes used to be trivially guaranteed loop-free. It is also possible for the sender to use different routes for different packets, without requiring coordination or explicit support by the intermediate nodes. In addition, on-demand source routing has performed very strongly when compared against other proposed protocol designs. However, source routing has the disadvantage of increased per-packet overhead due to the source route header that must be present in every packet originated or forwarded. In this paper, we propose and analyze the use in ad hoc networks of implicit source routing, and show that it preserves the advantages of source routing while avoiding the associated per-packet overhead in most cases. We evaluated this technique through detailed simulations of ad hoc networks based on the Dynamic Source Routing protocol (DSR), an on-demand ad hoc network routing protocol based on source routing. Although routing packet overhead increased slightly with implicit source routing, by about 12.3%, the total number of bytes of overhead decreased substantially, by between 44 and 86%. On all other metrics evaluated, the performance of DSR either did not change significantly or actually improved somewhat, due to indirect effects of the reduced routing overhead.