An Efficient Cache Replacement Strategy for the Hybrid Cache Consistency Approach

Authors: Aline Zeitunlian, Ramzi A. Haraty

Abstract:

Caching was suggested as a solution for reducing bandwidth utilization and minimizing query latency in mobile environments. Over the years, different caching approaches have been proposed, some relying on the server to broadcast reports periodically informing of the updated data while others allowed the clients to request for the data whenever needed. Until recently a hybrid cache consistency scheme Scalable Asynchronous Cache Consistency Scheme SACCS was proposed, which combined the two different approaches benefits- and is proved to be more efficient and scalable. Nevertheless, caching has its limitations too, due to the limited cache size and the limited bandwidth, which makes the implementation of cache replacement strategy an important aspect for improving the cache consistency algorithms. In this thesis, we proposed a new cache replacement strategy, the Least Unified Value strategy (LUV) to replace the Least Recently Used (LRU) that SACCS was based on. This paper studies the advantages and the drawbacks of the new proposed strategy, comparing it with different categories of cache replacement strategies.

Keywords: Cache consistency, hybrid algorithm, and mobileenvironments

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1078615

References:

[1] Barbara, D. and Imielinski, T. (1994). Sleepers and Workaholics: Caching Strategies in Mobile Environments. ACM, SIGMOD.
[2] Cao, G. (2002, June). Proactive Power-Aware Cache Management for Mobile Computing Systems. IEEE. Transactions on Computers. Volume 51. No. 6. pp. 608-621.
[3] Jing, J. Elmagarmid, A. Helal, A. and Alonso, R. (1997). Bit-Sequences: An Adaptive Cache Invalidation Method in Mobile Client/Server Environments. ACM. Mobile Networks and Application 2. pp. 115-127. 1997.
[4] Kahol, A. Khurana, S. Gupta, S.K.S. and Srimani, P.K. (2001, July). A Strategy to Manage Cache Consistency in a Disconnected Distributed Environment. IEEE. Transactions on Parallel and Distributed Systems. Vol. 12. No.7. pp. 686-700.
[5] Wang, Z. Das, S. Che, H and Kumar. M (2003). SACCS: Scalable Asynchronous Cache Consistency Scheme for Mobile Environments. IEEE, Proceedings of the 23rd International Conference on Distributed Computing Systems Workshops (ICDCSW-03). pp.1-6.
[6] Wang, Z. Das, S.K. Che, H and Kumar, M. (2004, November). A Scalable Asynchronous Cache Consistency Scheme (SACCS) for Mobile Environments. IEEE Transactions on Parallel and Distributed Systems. Vol. 155, no. 11, pp. 983-995.
[7] Bahn, H. Koh, K. Sam, N. and Min, S. L. (2002). Efficient Replacement of Nonuniform Objects in Web Caches. IEEE. June, 2002. pp.65-73.
[8] Barbara, D. (1999). Mobile Computing and Databases - A Survey. IEEE. Transactions on Knowledge and Data Engineering, Volume 11, No.1, January/February 1999, pp. 108-117.
[9] Wu, K.L. Yu, P.S. and Chen, M.S. (1996). Energy-Efficient Caching for Wireless Mobile Computing. IEEE. pp. 336-343.
[10] Hu, Q. and Lee, D.K. (1998) Cache Algorithms Based on Adaptive Invalidation Reports for Mobile Environments. ACM. Cluster Computing. Volume 1. pp. 39-50.
[11] Cao, G. (2002). Adaptive Power-Aware Cache Management for Mobile Computing Systems. http://www2002.org/CDROM/poster/88.pdf.
[12] Cao, G. (2002) On Improving the Performance of Cache Invalidation in Mobile Environments. Mobile Networks and Application, 7, pp. 291- 303. Kluwer Academic Publishers. Netherlands.
[13] Cao, G. (2003, September/October). A Scalable Low-latency Cache Invalidation Strategy for Mobile Environments. IEEE. Transactions on Knowledge and Data Engineering. Volume 15, No. 5. pp. 1251-1265.
[14] Madhukar, A. and Alhajj, R. (2006, April 23-27). An Adaptive Energy Efficient Cache Invalidation Scheme for Mobile Databases. ACM. SAC 2006. April 23-27, 2006, Dijon, France. pp. 1122-1126.
[15] Shen, H. Kumar, M. Das, S.K. and Wang, Z. (2005). Energy-Efficient Data Caching and Prefetching for Mobile Devices Base on Utility. Mobile Networks and Applications 10, pp. 475-486.
[16] Xu, J. and Hu, Q. (2001). An Optimal Cache Replacement Policy for Wireless Data Dissemination Under Cache Consistency. IEEE. pp.267- 274.
[17] Yin, L. and Cai, Y. (2003) A Generalized Target-Driven Cache Replacement Policy for Mobile Environments. Proceedings of Symposium on Applications and the Internet, 2003. pp. 14-21. 27-31 January 2003. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.59.9274
[18] Shen, H. Kumar, M. Das, S.K. and Wang, Z. (2004). Energy-Efficient Caching and Prefetching with Data Consistency in Mobile Distributed Systems. IEEE. Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS-04).
[19] Seifert, A. and Scholl, M. H. (2002). A Multi-Version Cache Replacement and Prefetching Policy for Hybrid Data Delivery Environments. ACM. Proceedings of the 28th VLDB Conference, Honk Kong, China, 2002.
[20] Santhosh, S. and Shi, W. (2005) A Semantic-Based Cache Replacement Algorithm for Mobile File Access. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.59.9274.
[21] Rabinovich, M. and Spatscheck, O. (2002). Web Caching and Replication (2nd ed.) Boston: Addison-Wesley.
[22] Aggarwal, C. Wolf, J.L. and Yu, P.S. (1999, January-February). Caching on the World Wide Web. IEEE. Transaction on Knowledge and Data Engineering, Volume 11, No. 1, January/February 1999. pp. 94-107.
[23] Podlipnig. S and Boszormenyi, L. (2003, December). A Survey of Web Cache Replacement Strategies. ACM Computing Surveys. Volume. 35. No. 4. pp.374-398.
[24] Lee, D. Choi, J. Kim, J.H. (1999). On the Existence of a Spectrum of Policies that Subsumes the Least recently Used (LRU) and Least Frequently Used (LFU) Policies. ACM. SIGMETRICS -99 5/99 Atlanta, Georgia, USA. pp. 134-143.