Energy-efficient data caching and prefetching for mobile devices based on utility

ABSTRACT

In mobile computing environments, vital resources like battery power and wireless channel bandwidth impose significant challenges in ubiquitous information access. In this paper, we propose a novel energy and bandwidth efficient data caching mechanism, called GreedyDual Least Utility (GD-LU), that enhances dynamic data availability while maintaining consistency. The proposed utility-based caching mechanism considers several characteristics of mobile distributed systems, such as connection-disconnection, mobility handoff, data update and user request patterns to achieve significant energy savings in mobile devices. We develop an analytical model for energy consumption of mobile devices in a dynamic data environment. Based on the utility function derived from the analytical model, we propose algorithms for cache replacement and passive prefetching of data objects. Our comprehensive simulation experiments demonstrate that the proposed caching mechanism achieves more than 10% energy saving and near-optimal performance tradeoff between access latency and energy consumption.

REFERENCES

• 1: Swarup Acharya , Stanley Zdonik, Broadcast disks: dissemination-based data management for asymmetric communication environments, 1998
• 2: Swarup Acharya , S. Muthukrishnan, Scheduling on-demand broadcasts: new metrics and algorithms, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.43-54, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288248]
• 3: 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
• 4: Paul Barford , Mark Crovella, Generating representative Web workloads for network and server performance evaluation, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.151-160, June 22-26, 1998, Madison, Wisconsin, United States
• 5: [5] L. Breslau, P. Cao, J. Fan, G. Phillips and S. Shenker, Web caching and zipf-like distributions: Evidence and implications, in IEEE Proceedings of INFOCOM (1999) pp. 126-134.
• 6: Guohong Cao, Proactive Power-Aware Cache Management for Mobile Computing Systems, IEEE Transactions on Computers, v.51 n.6, p.608-621, June 2002 [doi>10.1109/TC.2002.1009147]
• 7: Guohong Cao, A scalable low-latency cache invalidation strategy for mobile environments, Proceedings of the 6th annual international conference on Mobile computing and networking, p.200-209, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345945]
• 8: [8] P. Cao and S. Irani, Cost-aware WWW proxy caching algorithms, in: Proc. USENIX Symp. Internet Technologies and Systems (Dec 1997) pp. 193-206.
• 9: Li Fan , Pei Cao , Wei Lin , Quinn Jacobson, Web prefetching between low-bandwidth clients and proxies: potential and performance, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.178-187, May 01-04, 1999, Atlanta, Georgia, United States
• 10: [10] L. Feeney and M. Nilsson, Investigating the energy consumption of a wireless network interface in an ad hoc networking environment, in: IEEE Proceedings of INFOCOM (2001), Vol. 5, no. 8.
• 11: [11] S. Gitzenis and N. Bambos, Power-controlled data prefetching/caching in wireless packet networks, in: IEEE Proceedings of INFOCOM 2002, New York, June 2002.
• 12: 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]
• 13: Anurag Kahol , Sumit Khurana , Sandeep K.S. Gupta , Pradip K. Srimani, A Strategy to Manage Cache Consistency in a Disconnected Distributed Environment, IEEE Transactions on Parallel and Distributed Systems, v.12 n.7, p.686-700, July 2001 [doi>10.1109/71.940744]
• 14: [14] W.H.O. Lau, M. Kumar and S. Venkatesh, A cache-based mobility-aware scheme for real-time continuous media delivery in wireless networks, in: IEEE International Conference on Multimedia and Expo. (2001).
• 15: Pavan Nuggehalli , Vikram Srinivasan , Carla-Fabiana Chiasserini, Energy-efficient caching strategies in ad hoc wireless networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778419]
• 16: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 17: Luigi Rizzo , Lorenzo Vicisano, Replacement policies for a proxy cache, IEEE/ACM Transactions on Networking (TON), v.8 n.2, p.158-170, April 2000 [doi>10.1109/90.842139]
• 18: [18] H. Shen, M. Kumar, S.K. Das and Z. Wang, Energy-efficient caching and prefetching with data consistency in mobile distributed systems, in: IEEE International Parallel and Distributed Processing Symposium (IPDPS), Santa Fe, NM (April 2004).
• 19: Junho Shim , Peter Scheuermann , Radek Vingralek, Proxy Cache Algorithms: Design, Implementation, and Performance, IEEE Transactions on Knowledge and Data Engineering, v.11 n.4, p.549-562, July 1999 [doi>10.1109/69.790804]
• 20: Chi-Jiun Su , Leandros Tassiulas, Joint broadcast scheduling and user's cache management for efficient information delivery, Wireless Networks, v.6 n.4, p.279-288, July 2000 [doi>10.1023/A:1019102017510]
• 21: Zhijun Wang , Sajal Das , Hao Che , Mohan Kumar, SACCS: Scalable Asynchronous Cache Consistency Scheme for Mobile Environments, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.797, May 19-22, 2003
• 22: Zhijun Wang , Mohan Kumar , Sajal K. Das , Huaping Shen, Investigation of Cache Maintenance Strategies for Multi-cell Environments, Proceedings of the 4th International Conference on Mobile Data Management, p.29-44, January 21-24, 2003
• 23: Roland P. Wooster , Marc Abrams, Proxy caching that estimates page load delays, Selected papers from the sixth international conference on World Wide Web, p.977-986, September 1997, Santa Clara, California, United States
• 24: Jianliang Xu , Qinglong Hu , Wang-Chien Lee , Dik Lun Lee, An Optimal Cache Replacement Policy for Wireless Data Dissemination under Cache Consistency, Proceedings of the 2001 International Conference on Parallel Processing, p.267-276, September 03-07, 2001
• 25: Liangzhong Yin , Guohong Cao , Chita Das , Ajeesh Ashraf, Power-Aware Prefetch in Mobile Environments, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.571, July 02-05, 2002
• 26: [26] N.E. Young, The K-server dual and loose competitivenesss for paging, Algorithmica 11(6) (1994) 525-541.

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.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management

General Terms:
Performance

Keywords:
caching, energy efficient, mobile devices, prefetching, wireless networks