An Efficient Cache Replacement Strategy for the Hybrid Cache Consistency Approach
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:61162", author = "Aline Zeitunlian and Ramzi A. Haraty", title = "An Efficient Cache Replacement Strategy for the Hybrid Cache Consistency Approach", 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", volume = "4", number = "3", pages = "561-6", }
