A scalable low-latency cache invalidation strategy for mobile environments

ABSTRACT

Caching frequently accessed data items on the client side is an effective technique to improve performance in a mobile environment. Classical cache invalidation strategies are not suitable for mobile environments due to the disconnection and mobility of the mobile clients. One attractive cache invalidation technique is based on invalidation reports (IRs). However, the IR-based cache invalidation solution has two major drawbacks, which have not been addressed is previous research. First, there is a long query latency associated with this solution since a client cannot answer the query until the next IR interval. Second, when the server updates a hot data item, all clients have to query the server and get the data from the server separately, which wastes a large amount of bandwidth. In this paper, we propose an IR-based cache invalidation algorithm which can significantly reduce the query latency and efficiently utilize the broadcast bandwidth. Detailed simulation experiments are carried out to evaluate the proposed methodology. Compared to previous IR-based schemes, our scheme can significantly improve the throughput and reduce the query latency, the number of uplink request, and the broadcast bandwidth requirements.

REFERENCES

• 1: Daniel Barbará , Tomasz Imieliński, Sleepers and workaholics: caching strategies in mobile environments, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.1-12, May 24-27, 1994, Minneapolis, Minnesota, United States
• 2: Anindya Datta , Debra E. VanderMeer , Aslihan Celik , Vijay Kumar, Broadcast protocols to support efficient retrieval from databases by mobile users, ACM Transactions on Database Systems (TODS), v.24 n.1, p.1-79, March 1999 [doi>10.1145/310701.310710]
• 3: The editors of IEEE 802.11, "Wireless LAN Media Access Control (MAC) and Physical Layer (PHY) Specifications," 802.11 Wireless Standards (http ://grouper. ieee.org/groups/8 02/11), 1999.
• 4: George H. Forman , John Zahorjan, The Challenges of Mobile Computing, Computer, v.27 n.4, p.38-47, April 1994 [doi>10.1109/2.274999]
• 5: D.J. Goodman, "Cellular Packet Communication," IEEE ~ans. Communication, 38(8):1272-1280, Aug. 1990.
• 6: Qinglong Hu , Dik Lun Lee, Cache algorithms based on adaptive invalidation reports for mobile environments, Cluster Computing, v.1 n.1, p.39-50, 1998 [doi>10.1023/A:1019012927328]
• 7: T. Imielinski , S. Viswanathan , B. r. Badrinath, Data on Air: Organization and Access, IEEE Transactions on Knowledge and Data Engineering, v.9 n.3, p.353-372, May 1997 [doi>10.1109/69.599926]
• 8: 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
• 9: Jin Jing , Ahmed Elmagarmid , Abdelsalam Sumi Helal , Rafael Alonso, Bit-sequences: an adaptive cache invalidation method in mobile client/server environments, Mobile Networks and Applications, v.2 n.2, p.115-127, Oct. 1997 [doi>10.1023/A:1013616213333]
• 10: M. Kazar, "Synchronization and Caching Issues in the Andrew File System," USENIX Conf., pages 27-36, 1988.
• 11: Wang-Chien Lee , Qinglong Hu , Dik Lun Lee, A study on channel allocation for data dissemination in mobile computing environments, Mobile Networks and Applications, v.4 n.2, p.117-129, May 1999 [doi>10.1023/A:1019190613700]
• 12: R. Powers, "Batteries for Low Power Electronics," Proc. IEEE, 83(4):687-693, April 1995.
• 13: S. Sandberg, D. Goldberg, S. Kleiman, D. Walsh, and B. Lyon, "Design and Implementation of the Sun Network File System," Proc. USENIX Summer Conf., pages 119-130, June 1985.
• 14: Konstantinos Stathatos , Nick Roussopoulos , John S. Baras, Adaptive Data Broadcast in Hybrid Networks, Proceedings of the 23rd International Conference on Very Large Data Bases, p.326-335, August 25-29, 1997
• 15: Nitin H. Vaidya , Sohail Hameed, Scheduling data broadcast in asymmetric communication environments, Wireless Networks, v.5 n.3, p.171-182, May 1999 [doi>10.1023/A:1019142809816]
• 16: Kun-Lung Wu , Philip S. Yu , Ming-Syan Chen, Energy-Efficient Caching for Wireless Mobile Computing, Proceedings of the Twelfth International Conference on Data Engineering, p.336-343, February 26-March 01, 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:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

  C. Computer Systems Organization

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

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