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

https://hal.inria.fr/hal-02987388
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

File

HR_bound_ToMPECS.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02987388, version 2

Collections

Citation

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⟩

Share

Metrics

Record views

131

Files downloads

180