Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

Cache Miss Estimation for Non-Stationary Request Processes

Abstract : The goal of the paper is to evaluate the miss probability of a Least Recently Used (LRU) cache, when it is offered a non-stationary request process given by a Poisson cluster point process. First, we construct a probability space using Palm theory, describing how to consider a tagged document with respect to the rest of the request process. This framework allows us to derive a fundamental integral formula for the expected number of misses of the tagged document. Then, we consider the limit when the cache size and the arrival rate go to infinity in proportion, and use the integral formula to derive an asymptotic expansion of the miss probability in powers of the inverse of the cache size. This enables us to quantify and improve the accuracy of the so-called Che approximation.
Document type :
Journal articles
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Carl Graham Connect in order to contact the contributor
Submitted on : Tuesday, November 28, 2017 - 9:29:18 AM
Last modification on : Thursday, October 29, 2020 - 2:00:05 PM


Files produced by the author(s)




Felipe Olmos, Carl Graham, Alain Simonian. Cache Miss Estimation for Non-Stationary Request Processes. Stochastic Systems, INFORMS Applied Probability Society, 2018, 8 (1), pp.75-90. ⟨10.1287/stsy.2017.0009⟩. ⟨hal-01232173v2⟩



Record views


Files downloads