Skip to Main content Skip to Navigation
Conference papers

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

Nitish Panigrahy 1 Philippe Nain 2 Giovanni Neglia 3 Don Towsley 1
2 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes
3 NEO - Network Engineering and Operations
CRISAM - Inria Sophia Antipolis - Méditerranée
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

Cited literature [20 references]  Display  Hide  Download
Contributor : Philippe Nain Connect in order to contact the contributor
Submitted on : Tuesday, November 3, 2020 - 7:10:53 PM
Last modification on : Wednesday, November 3, 2021 - 5:53:23 AM
Long-term archiving on: : Thursday, February 4, 2021 - 6:58:29 PM


Files produced by the author(s)


  • HAL Id : hal-02987388, version 1


Nitish Panigrahy, Philippe Nain, Giovanni Neglia, Don Towsley. A New Upper Bound on Cache Hit Probability for Non-anticipative Caching Policies. Performance 2020 - 38th International Symposium on Computer Performance, Modeling, Measurements and Evaluation, Nov 2020, Milan / Virtual, Italy. pp.1-6. ⟨hal-02987388⟩



Record views


Files downloads