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, the cache maintains an ordered list of documents in the following way. When a document of size s is requested and found in the cache, then with probability p s it is moved to the front of the cache; otherwise the cache stays unchanged. Similarly, if the requested document of size s is not found in the cache, the algorithm places it with probability p s to the front of the cache or leaves the cache unchanged with the complementary probability (1 − p s). The successive randomized decisions are independent and the corresponding success probabilities p s are completely determined by the size of the currently requested document. In the case of a replacement, the necessary number of documents that are least recently moved to the front of the cache are removed in order to accommodate the newly placed document. 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. Combinatorics, Probability & Computing, to appear