Distributed group-based cooperative caching in a mobile broadcast environment

ABSTRACT

Caching is a key technique for improving data retrieval performance of mobile clients. The emergence of state-of-the-art peer-to-peer communication technologies now brings to reality what we call "cooperative caching" in which mobile clients not only can retrieve data items from mobile support stations, but also from the cache in their peers, thereby inducing a new dimension for mobile data caching. In this paper, we propose a distributed group-based cooperative caching scheme, in which we define the concept of a tightly-coupled group (TCG) by capturing the data affinity of individual peers and their mobility patterns, in a mobile broadcast environment. A distributed stable peer discovery protocol is proposed for discovering all TCGs dynamically. In addition, a cache signature scheme is adopted to provide hints for the mobile clients to determine whether their required data items are cached by their neighboring peers, and to perform cooperative cache replacement to increase overall data availability. Simulation studies are conducted to evaluate the effectiveness of our distributed group-based cooperative caching scheme.

REFERENCES

• 1: Swarup Acharya , Rafael Alonso , Michael Franklin , Stanley Zdonik, Broadcast disks: data management for asymmetric communication environments, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.199-210, May 22-25, 1995, San Jose, California, United States
• 2: Swarup Acharya , Michael Franklin , Stanley Zdonik, Balancing push and pull for data broadcast, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.183-194, May 11-15, 1997, Tucson, Arizona, United States
• 3: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 4: 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]
• 5: Chi-Yin Chow , Hong Va Leong , Alvin T. S. Chan, Group-Based Cooperative Cache Management for Mobile Clients in a Mobile Environment, Proceedings of the 2004 International Conference on Parallel Processing (ICPP'04), p.83-90, August 15-18, 2004 [doi>10.1109/ICPP.2004.39]
• 6: C.-Y. Chow, H. V. Leong, and A. T. S. Chan. Utilizing the cache space of low-activity clients in a mobile cooperative caching environment. International Journal of Wireless and Mobile Computing (IJWMC), to appear.
• 7: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.281-293, June 2000 [doi>10.1109/90.851975]
• 8: L. M. Feeney and M. Nilsson. Investigating the energy consumption of a wireless network interface in an ad hoc networking environment. In Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pages 1548--1557, April 2001.
• 9: Roy Friedman , Maria Gradinariu , Gwendal Simon, Locating cache proxies in manets, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989482]
• 10: Z. Genova and K. Christensen. Using signatures to improve URL routing. In Proceedings of the 21st IEEE International Performance Computing and Communications Conference (IPCCC), pages 45--52, April 2002.
• 11: Zygmunt J. Haas , Marc R. Pearlman, The performance of query control schemes for the zone routing protocol, IEEE/ACM Transactions on Networking (TON), v.9 n.4, p.427-438, August 2001 [doi>10.1109/90.944341]
• 12: T. Hara. Effective replica allocation in ad hoc networks for improving data accessibility. In Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pages 1568--1576, April 2001.
• 13: Takahiro Hara, Cooperative caching by mobile clients in push-based information systems, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584825]
• 14: Xiaoyan Hong , Mario Gerla , Guangyu Pei , Ching-Chuan Chiang, A group mobility model for ad hoc wireless networks, Proceedings of the 2nd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.53-60, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313237.313248]
• 15: Qinglong Hu , Dik Lun Lee , Wang-Chien Lee, Performance evaluation of a wireless hierarchical data dissemination system, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.163-173, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313528]
• 16: Qinglong Hu , Wang-Chien Lee , Dik Lun Lee, A Hybrid Index Technique for Power Efficient Data Broadcast, Distributed and Parallel Databases, v.9 n.2, p.151-177, March 2001 [doi>10.1023/A:1018944523033]
• 17: H. Kobayashi and L. R. Bahl. Image data compression by predictive coding I: Prediction algorithms. IBM Journal of Research and Development, 18(2):172--179, March 1974.
• 18: W. H. O. Lau , M. Kumar , Svetha Venkatesh, A cooperative cache architecture in support of caching multimedia objects in MANETs, Proceedings of the 5th ACM international workshop on Wireless mobile multimedia, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570790.570800]
• 19: Ken C. K. Lee , Hong Va Leong , Antonio Si, Semantic Data Broadcast for a Mobile Environment Based on Dynamic and Adaptive Chunking, IEEE Transactions on Computers, v.51 n.10, p.1253-1268, October 2002 [doi>10.1109/TC.2002.1039851]
• 20: Wang-Chien Lee , Dik Lun Lee, Signature caching techniques for information filtering in mobile enviroments, Wireless Networks, v.5 n.1, p.57-67, Jan. 1999 [doi>10.1023/A:1019118104364]
• 21: Li Li , Joseph Y. Halpern , Paramvir Bahl , Yi-Min Wang , Roger Wattenhofer, Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.264-273, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384043]
• 22: Eppie Mok , Hong Va Leong , Antonio Si, Transaction Processing in an Asymmetric Mobile Environment, Proceedings of the First International Conference on Mobile Data Access, p.71-81, December 16-17, 1999
• 23: Maria Papadopouli , Henning Schulzrinne, Effects of power conservation, wireless coverage and cooperation on data dissemination among mobile devices, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501431.501433]
• 24: Françoise Sailhan , Valérie Issarny, Cooperative Caching in Ad Hoc Networks, Proceedings of the 4th International Conference on Mobile Data Management, p.13-28, January 21-24, 2003
• 25: H. Schwetman. User's Guide CSIM19 Simulation Engine (C++ Version). Mesquite Software Inc., 1998.
• 26: L. Yin and G. Cao. Supporting cooperative caching in ad hoc networks. In Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), March 2004.
• 27: G. K. Zipf. Human Behavior and the Principle of Least Effort. Addison-Wesley, 1949.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Design, Performance

Keywords:
cooperative caching, mobile computing, mobile data broadcast, peer groups, peer-to-peer computing