Caching strategies in on-demand routing protocols for wireless ad hoc networks

ABSTRACT

An on-demand routing protocol for wireless and hoc networks is one that searches for and attempts to discover a route to some destination node only when a sending node originates a data packet addressed to that node. In order to avoid the need for such a route discovery to be performed before each data packet is sent, such routing protocols must cache routes previously discovered. This paper presents an analysis of the effects of different design choices for this caching in on-demand routing protocols in wireless ad hoc networks, dividing the problem into choices of cache structure, cache capacity, and cache timeout. Our analysis is based on the Dynamic Source Routing protocol (DSR), which operates entirely on-demand. Using detailed simulations of wireless ad hoc networks of 50 mobile nodes, we studied a large number of different caching algorithms that utilize a range of design choices, and simulated each cache primarily over a set of 50 different movement scenarios drawn from 5 different types of mobility models. We also define a set of new mobility metrics that allow accurate characterization of the relative difficulty that a given movement scenario presents to an ad hoc network routing protocol, and we analyze each mobility metric's ability to predict the actual difficulty in terms of routing overhead experienced by the routing protocol across the scenarios in our study.

REFERENCES

• 1: Josh Broch, David B. Johnson, and David A. Maltz. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks. Internet-Draft, draft-ietf-manet-dsr-03.txt, October 1999. Work in progress.
• 2: 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]
• 3: 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/nsd.
• 4: Zygmunt J. Haas. A Routing Protocol for the Reconfigurable Wireless Network. In 1997 IEEE 6th International Conference on Universal Person Communications Record. Bridging the Way to the 21st Century, ICUPC '97, volume 2, pages 562- 566, October 1997.
• 5: 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.
• 6: Internet Engineering Task Force MANET Working Group. Mobile Ad-hoc Networks (manet) Charter. Available at http://www, ietf. orgthtml.charters/manet-charter, html.
• 7: 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]
• 8: David B. Johnson. Routing in Ad Hoc Networks of Mobile Hosts. In Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications, pages 158-163, December 1994.
• 9: 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.
• 10: John Jubin and Janet D. Tornow. The DARPA Packet Radio Network Protocols. Proceedings of the IEEE, 75(1):21-32, January 1987.
• 11: 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]
• 12: Tony Larsson. Personal communication, February 8, 2000.
• 13: Ben Liang. Personal communication, February 4, 2000.
• 14: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• 15: 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
• 16: Miguel Sanchez. RE: Mobility pattern in a MANET, June 25, 1998. IETF MANET Mailing List, Message-ID: <000a01 bda0555d84f9380511352a9e@ msanchez.disca, upv. es>.
• 17: Miguel Sanchez. Re: Node Movement Models in Ad hoc, July 15, 1999. IETF MANET Mailing List, Message-ID: <378DC8F6.B01 CF351 @disca.upv.es>.
• 18: Miguel Sanchez. Personal communication, February 1, 2000.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Measurement, Performance, Standardization, Theory