An Unifying Replacement Approach for Caching Systems

Abstract

A cache replacement algorithm called probability based replacement (PBR) is proposed in this paper. The algorithm makes replacement decision based on the byte accessprobabilities of documents. This concept can be applied to both small conventional web documents and large video documents. The performance of PBR algorithm is studied by both analysis and simulation. By comparing cache hit probability, hit rate and average time spent in three systems, it is shown that the proposed algorithm outperforms the commonly used LRU and LFU algorithms. Simulation results show that, when large video documents are considered, the PBR algorithm provides up to 120% improvement in cache hit rate when comparing to that ofconventional algorithms. The uniqueness of this work is that, unlike previous studies that propose different solutions for different types of documents separately, the proposed PBR algorithm provides a simple and unified approach to serve different types of documents in a single system.