Sleepers and workaholics: caching strategies in mobile environments

ABSTRACT

In the mobile wireless computing environment of the future a large number of users equipped with low powered palm-top machines will query databases over the wireless communication channels. Palmtop based units will often be disconnected for prolonged periods of time due to the battery power saving measures; palmtops will also frequencly relocate between different cells and connect to different data servers at different times. Caching of frequently accessed data items will be an important technique that will reduce contention on the narrow bandwidth wireless channel. However, cache invalidation strategies will be severely affected by the disconnection and mobility of the clients. The server may no longer know which clients are currently residing under its cell and which of them are currently on. We propose a taxonomy of different cache invalidation strategies and study the impact of client's disconnection times on their performance. We determine that for the units which are often disconnected (sleepers) the best cache invalidation strategy is based on signatures previously used for efficient file comparison. On the other hand, for units which are connected most of the time (workaholics), the best cache invalidation strategy is based on the periodic broadcast of changed data items.

REFERENCES

• 1: D. Barbarg and T. Imielifiski. Sleepers and Workaholica: Caching Strategies in Mobile Environments. Technical Report MITL-TR-58-93, MITL, June 1993.
• 2: D. Barbará , R. J. Lipton, A Class of Randomized Strategies for Low-Cost Comparison of File Copies, IEEE Transactions on Parallel and Distributed Systems, v.2 n.2, p.160-170, April 1991 [doi>10.1109/71.89062]
• 3: H. Chernoff. A Meassure of Asymptotic Efficiency for Tests of a Hypotesis Based on the Sum of Observations. Annals of Mathemgtical Statistics, 23:493-509, 1952.
• 4: W.K. Fuchs, K. Wu, and J. Abraham. Low-Cost Comparison and Diagnosis of Large Remotely Located Files. In Proceedings of the Fifth Symposium on Reliability of Distributed Software and Database Syatems, January 1986.
• 5: Tomasz Imielinski , B. R. Badrinath, Querying in Highly Mobile Distributed Environments, Proceedings of the 18th International Conference on Very Large Data Bases, p.41-52, August 23-27, 1992
• 6: T. Imielinski, B.R. Badrinath, and S. Viswanathan. Data Dissemination in Wireless and Mobile Environments. Technical Report 59, WINLAB, Rutgers University, 3une 1993.
• 7: Tomasz Imielinski , S. Viswanathan , B. R. Badrinath, Energy efficient indexing on air, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.25-36, May 24-27, 1994, Minneapolis, Minnesota, United States
• 8: T. Madej. An Application of Group Testing to the File Comparison Problem. In Proceedings of the International Conference on Distributed Computing Systems, June 1989.
• 9: S. Rangarajan and D. Fussell. Rectifying Corrupted Files in Distributed File Systems. In Proceedings of the international Conference on Distributed Computing Systems, May 1991.
• 10: R. Sandberg, D. Goldberg, S. Kleiman, D. Walsh, and B. Lyon. Desing and Implementation of the Sun Network Filesystem. In Proceedings of the USENIX Summer Conference, pages 119-130, 3une 1985.
• 11: M. Satyanarayanan , John H. Howard , David A. Nichols , Robert N. Sidebotham , Alfred Z. Spector , Michael J. West, The ITC distributed file system: principles and design, Proceedings of the tenth ACM symposium on Operating systems principles, p.35-50, December 1985, Orcas Island, Washington, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

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

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications
      C.2.1 Network Architecture and Design
          Subjects: Network topology
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.3 Microcomputers
          Subjects: Personal computers

General Terms:
Algorithms, Design, Performance