Optimizing LRU caching for variable document sizes, Combin Probab Comput 13

We analyze a class of randomized Least-Recently-Used (LRU) cache replacement algorithms under the independent reference model with generalized Zipf’s law request probabilities. The randomization was recently proposed for Web caching as a mechanism that discriminates between different document sizes. In particular, a requested document that is not found in the cache either replaces a necessary number of least recently used documents with probability depending on its size or the cache is left unchanged. In this framework, we provide explicit asymptotic characterization of the cache fault probability. Using the derived result we prove that the asymptotic performance of this class of algorithms is optimized when the randomization probabilities are chosen inversely proportional to document sizes. In addition, for this optimized and easy to implement policy, we show that its performance is within a constant factor from the optimal static algorithm. Keywords: randomized least-recently-used caching, Zipf’s law distribution, variable document sizes, Web caching, cache fault probability, averages-case analysis This work is supported by the NSF Grant No. 0092113. Submitted to Combinatorics, Probability & Computing.