|
Published Articles >> Table of Contents >> Abstract
December 2007 (Vol. 56, No. 12)
pp. 1597-1611
On-Bound Selection Cache Replacement Policy for Wireless Data Access
Hui Chen, IEEE
Yang Xiao, IEEE
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TC.2007.70768
Send link to a friend
| Abstract |
|
Cache can be used for mobile devices to reduce usage of limited bandwidth in wireless networks. Ideally, frequently accessed and infrequently updated data items should be cached, and infrequently accessed and frequently updated data items should be evicted or not cached at all. Most of existing cache replacement policies adopt only access information so that frequently updated data items are also cached. As a remedy, we propose a cache replacement policy, called On-Bound Selection (OBS), that uses both data access and update information. The proposed OBS is inspired by an analytical analysis for a server-based Poll-Each-Read (SB-PER) and a revised Call-back (RCB). The OBS provides an upper bound for effective hit ratio and a lower bound for communication cost. The proposed scheme is evaluated and compared with least-frequently-used (LFU) replacement policy through extensive simulations. Simulation results show that the OBS outperforms LFU in terms of both effective hit ratio and communication cost.
|
 References
|
[1] S. Acharya and S. Muthukrishnan, “Scheduling On-Demand Broadcasts: New Metrics and Algorithms,” Proc. ACM MobiCom '98, pp. 43-54, 1998.
[2] A. Balamash and M. Krunz, “An Overview of Web Caching Replacement Algorithms,” IEEE Comm. Surveys and Tutorials, vol. 6, no. 2, pp. 44-56, 2004.
[3] D. Barbará and T. Imielińksi, “Sleepers and Workaholics: Caching Strategies for Mobile Environments (Extended Version),” VLDB J., vol. 4, no. 4, pp. 567-602, 1995.
[4] L. Berslau, P. Cao, L. Fan, G. Phillips, and S. Shenker, “Web Caching and Zipf-Like Distributions: Evidence and Implications,” Proc. IEEE INFOCOM '99, vol. 1, pp. 126-134, Mar. 1999.
[5] P. Barford, A. Bestavros, A. Bradley, and M. Crovella, “Changes in Web Client Access Patterns: Characteristics and Caching Implications,” World Wide Web J., vol. 2, pp. 15-28, 1999.
[6] J. Cai and K.-L. Tan, “Energy-Efficient Selective Cache Invalidation,” Wireless Networks, vol. 5, no. 6, pp. 489-502, 1999.
[7] G. Cao, “Proactive Power-Aware Cache Management for Mobile Computing Systems,” IEEE Trans. Computers, vol. 51, no. 6, pp.608-621, June 2002.
[8] G. Cao, “A Scalable Low-Latency Cache Invalidation Strategy for Mobile Environments,” IEEE Trans. Knowledge and Data Eng., vol. 15, no. 5, Sept./Oct. 2003.
[9] B.Y.L. Chan, A. Si, and H.V. Leong, “Cache Management for Mobile Databases: Design and Evaluation,” Proc. 14th Int'l Conf. Data Eng. (ICDE '98), pp. 54-63, Feb. 1998.
[10] L. Cherkasova and G. Ciardo, “Role of Aging, Frequency, and Size in Web Cache Repalcement Policies,” Lecture Notes in Computer Science, vol. 2110, pp. 114-123, 2001.
[11] H. Chou and D. DeWitt, “An Evaluation of Buffer Management Strategies for Relational Database Systems,” Proc. 11th Int'l Conf. Very Large Data Bases (VLDB '85), pp. 141-172, 1985.
[12] J. Dilley, M. Arlitt, and S. Perret, “Enhancement and Validation of the Squid Cache Replacement Policy,” Proc. Fourth Int'l Web Caching Workshop (WCW '99), 1999.
[13] C.C.F. Fong, J.C.S. Liu, and M.H. Wong, “Quantifying Complexity and Performance Gains of Distributed Caching in a Wireless Network Environment,” Proc. 13th Int'l Conf. Data Eng. (ICDE '97), pp. 104-113, Oct. 1997.
[14] J. Howard, M. Kazar, S. Menees, D. Nichols, M. Satyanarayanan, R. Sidebotham, and M. West, “Scale and Performance in a Distributed File System,” ACM Trans. Computer Systems, vol. 6, no. 1, pp. 51-58, Feb. 1988.
[15] Q.L. Hu and D.L. Lee, “Cache Algorithms Based on Adaptive Invalidation Reports for Mobile Environments,” Cluster Computing, vol. 1, no. 1, pp. 39-48, Feb. 1998.
[16] A. Iyengar, E. Nahum, A. Shaikh, and R. Tewari, “Web Caching, Consistency and Content Distribution,” The Practical Handbook of Internet Computing, M.P. Singh, ed., Chapman & Hall/CRC Press, 2005.
[17] R. Jain, The Art of Computer Systems Performance Analysis. John Wiley & Sons, 1991.
[18] J. Jing, A.K. Elmagarmid, A. Helal, and R. Alonso, “Bit-Sequences: A New Cache Invalidation Method in Mobile Environments,” Mobile Networks and Applications, vol. 2, no. 2, pp. 115-127, 1997.
[19] A. Kahol, S. Khurana, S.K.S. Gupta, and P.K. Srimani, “A Strategy to Manage Cache Consistency in a Distributed Mobile Wireless Environment,” IEEE Trans. Parallel and Distributed Systems, vol. 12, no. 7, pp. 686-700, July 2001.
[20] Y.-B. Lin, W.-R. Lai, and J.-J. Chen, “Effects of Cache Mechanism on Wireless Data Access,” IEEE Trans. Wireless Comm., vol. 2, no. 6, pp. 1240-1246, 2003.
[21] M. Nelson, B. Welch, and J. Ousterhout, “Caching in the Sprite Network File System,” ACM Trans. Computer Systems, vol. 6, no. 1, pp. 134-154, Feb. 1988.
[22] E. O'Neil, P. O'Neil, and G. Weikum, “The LRU-K Page Replacement Algorithm for Database Disk Buffering,” Proc. ACM SIGMOD Int'l Conf. Management of Data, pp. 297-306, 1993.
[23] J.T. Robinson and M.V. Devarakonda, “Data Cache Management Using Frequency-Based Replacement,” Proc. ACM SIGMETRICS Conf., pp. 134-142, 1990.
[24] K.L. Tan, J. Cai, and B.C. Ooi, “An Evaluation of Cache Invalidation Strategies in Wireless Environments,” IEEE Trans. Parallel and Distributed Systems, vol. 12, no. 8, pp. 789-807, Aug. 2001.
[25] A.S. Tanenbaum, Computer Networks, fourth ed. Prentice Hall PTR, 2003.
[26] J. Wang, “A Survey of Web Caching Schemes for the Internet,” ACM SIGCOMM Computer Comm. Rev., vol. 29, no. 5, pp. 36-46, 1999.
[27] K.-L. Wu, P.S. Yu, and M.-S. Chen, “Energy-Efficient Caching for Wireless Mobile Computing,” Proc. 12th Int'l Conf. Data Eng. (ICDE '96), pp. 336-343, Feb. 1996.
[28] Y. Xiao, “Optimal Location Management for Two-Tier PCS Networks,” Computer Comm., vol. 26, no. 10, pp. 1047-1055, June 2003.
[29] J. Xu, Q. Hu, D.L. Lee, and W.-C. Lee, “SAIU: An Efficient Cache Replacement Policy for Wireless On-Demand Broadcasts,” Proc. Ninth ACM Int'l Conf. Information and Knowledge Management (CIKM '00), pp. 46-53, Nov. 2000.
[30] J. Xu, Q. Hu, W.-C. Lee, and D.L. Lee, “Performance Evaluation of an Optimal Cache Replacement Policy for Wireless Data Dissemination,” IEEE Trans. Knowledge and Data Eng., vol. 16, no. 1, pp. 125-139, Jan. 2004.
[31] J. Yin, L. Alvisi, M. Dahlin, and C. Lin, “Volume Leases for Consistency in Large-Scale Systems,” IEEE Trans. Knowledge and Data Eng., vol. 11, no. 4, pp. 563-576, July/Sept. 1999.
[32] J. Yuen, E. Chan, K.Y. Lam, and H.W. Leung, “Cache Invalidation Scheme for Mobile Computing Systems with Real-Time Data,” ACM SIGMOD Record, vol. 29, no. 4, pp. 34-39, 2000.
|
 Additional Information
|
Index Terms- cache, replacement policy, wireless networks, access, update, effective hit ratio, communication cost
Citation:
Hui Chen, Yang Xiao,
"On-Bound Selection Cache Replacement Policy for Wireless Data Access,"
IEEE Transactions on Computers,
vol. 56,
no. 12,
pp. 1597-1611,
Dec.,
2007
|
|
RSS Feed