Implicit source routes for on-demand ad hoc network routing

ABSTRACT

In an ad hoc network, the use of source routing has many advanctages, 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 imtermediate 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 orginated or forwarded. In this paper, we propose and analyze the use in ad hoc networks of implicit 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 or DSR either did not change significantly or actually improved somewhat, due to indirect effects of of the reduced routing overhead

REFERENCES

• 1: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 2: M. Scott Corson , Anthony Ephremides, A distributed routing algorithm for mobile wireless networks, Wireless Networks, v.1 n.1, p.61-81, Feb. 1995 [doi>10.1007/BF01196259]
• 3: Samir R. Das, Charles E. Perkins, and Elizabeth M. Royer. Performance Comparison of Two On-demand Routing Protocols for Ad Hoc Networks. In Proceedings of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2000), pages 3-12, 2000.
• 4: Kevin Fall and Kannan Varadhan, editors. ns Notes and Documentation. The VINT Project, UC Berkeley, LBL, USC/ISI, and Xerox PARC, November 1997. Available from http://www-mash.cs.berkeley.edu/ns/.
• 5: Yih-Chun Hu , David B. Johnson, Caching strategies in on-demand routing protocols for wireless ad hoc networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.231-242, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345952]
• 6: Yih-Chun Hu, David B. Johnson, and David A. Maltz. Flow State in the Dynamic Source Routing Protocol for Mobile Ad Hoc Networks. Internet-Draft, draft-ietfmanet- dsrflow-00.txt, February 2001. Work in progress.
• 7: IEEE Computer Society LAN MAN Standards Committee. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, IEEE Std 802.11-1997. The Institute of Electrical and Electronics Engineers, New York, New York, 1997.
• 8: Per Johansson , Tony Larsson , Nicklas Hedman , Bartosz Mielczarek , Mikael Degermark, Scenario-based performance analysis of routing protocols for mobile ad-hoc networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.195-206, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313535]
• 9: David B. Johnson. Routing in Ad Hoc Networks of Mobile Hosts. In Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications (WMCSA'94), pages 158-163, December 1994.
• 10: David B. Johnson and David A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In Mobile Computing, edited by Tomasz Imielinski and Hank Korth, chapter 5, pages 153-181. Kluwer Academic Publishers, 1996.
• 11: David B. Johnson , David A. Maltz , Josh Broch, DSR: the dynamic source routing protocol for multihop wireless ad hoc networks, Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 12: David B. Johnson, David A. Maltz, Yih-Chun Hu, and Jorjeta G. Jetcheva. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks. Internet- Draft, draft-ietf-manet-dsr-05.txt, March 2001. Work in progress.
• 13: John Jubin and Janet D. Tornow. The DARPA Packet Radio Network Protocols. Proceedings of the IEEE, 75(1):21-32, January 1987.
• 14: Young-Bae Ko , Nitin H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.66-75, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288252]
• 15: David A. Maltz, Josh Broch, Jorjeta Jetcheva, and David B. Johnson. The Effects of On-Demand Behavior in Routing Protocols for Multi-Hop Wireless Ad Hoc Networks. IEEE Journal on Selected Areas in Communications, Special Issue on "Wireless Ad Hoc Networks," 17(8):1439-1453, August 1999.
• 16: The Monarch Project. Rice Monarch Project: Mobile Networking Architectures, project home page. Available at http://www.monarch.cs.rice.edu/.
• 17: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 18: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 19: E. Rosen, A. Viswanathan, and R. Callon. Multiprotocol Label Switching Architecture. RFC 3031, January 2001.
• 20: Prasun Sinha, Raghupathy Sivakumar, and Bharghavan Vaduvur. Enhancing Ad Hoc Routing with Dynamic Virtual Infrastructures. In Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2001), April 2001.
• 21: Andrew S. Tanenbaum, Computer networks (3rd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1996

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks
      C.2.2 Network Protocols

General Terms:
Performance, Theory, Verification