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 metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-02987388
Contributor : Philippe Nain <>
Submitted on : Tuesday, November 3, 2020 - 7:10:53 PM
Last modification on : Tuesday, November 17, 2020 - 12:10:13 PM

File

HR_bound_Performance.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02987388, version 1

Citation

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. ⟨hal-02987388⟩

Share

Metrics

Record views

25

Files downloads

50