A fluid limit for a cache algorithm with general request processes

• Published in: Advances in applied probability 2010-09, Vol.42 (3), p.816-833
• Main Author: Osogami, Takayuki
• Format: Article
• Language: English
• ISSN: 0001-8678; 1475-6064
• DOI: 10.1017/S000186780005045X

We introduce a formal limit, which we refer to as a fluid limit, of scaled stochastic models for a cache managed with the least-recently-used algorithm when requests are issued according to general stochastic point processes. We define our fluid limit as a superposition of dependent replications of the original system with smaller item sizes when the number of replications approaches ∞. We derive the average probability that a requested item is not in a cache (average miss probability) in the fluid limit. We show that, when requests follow inhomogeneous Poisson processes, the average miss probability in the fluid limit closely approximates that in the original system. Also, we compare the asymptotic characteristics, as the cache size approaches ∞, of the average miss probability in the fluid limit to those in the original system.