Skip to Main content Skip to Navigation
Journal articles

A New Upper Bound on Cache Hit Probability for Non-Anticipative Caching Policies

Abstract : Caching systems have long been crucial for improving the performance of a wide variety of network and web based online applications. In such systems, end-to-end application performance heavily depends on the fraction of objects transfered from the cache, also known as the cache hit probability. Many cache eviction policies have been proposed and implemented to improve the hit probability. In this work, we propose a new method to compute an upper bound on hit probability for all non-anticipative caching policies, i.e. for policies that have no knowledge of future requests. At each object request arrival, we use hazard rate (HR) function based ordering to classify the request as a hit or not. Under some statistical assumptions, we prove that our proposed HR based ordering model computes the maximum achievable hit probability and serves as an upper bound for all non-anticipative caching policies. We also provide simulation results to validate its correctness and to compare it to Belady's upper bound. We find it to almost always be tighter than Belady's bound.
Complete list of metadata
Contributor : Philippe Nain Connect in order to contact the contributor
Submitted on : Thursday, August 11, 2022 - 4:35:07 PM
Last modification on : Friday, August 12, 2022 - 3:29:40 AM


Files produced by the author(s)


  • HAL Id : hal-02987388, version 2



Nitish K Panigrahy, Philippe Nain, Giovanni Neglia, Don Towsley. A New Upper Bound on Cache Hit Probability for Non-Anticipative Caching Policies. ACM Transactions on Modeling and Performance Evaluation of Computing Systems, ACM, In press. ⟨hal-02987388v2⟩



Record views


Files downloads