Modeling Perfect LFU on cache systems using Markov chain

Abstract Accurately estimating the load on the origin server is crucial for the correct and efficient operation of a Content Delivery Network (CDN). Since CDNs rely heavily on caching, simulating caches with arbitrary topologies is essential. This paper presents a methodology for modeling the Perfect Least Frequently Used (PLFU) cache algorithm. While the literature has extensively documented various eviction strategies, including Least Recently Used (LRU), First-In First-Out (FIFO), and Random, there has been a lack of Markov models for frequency based caching algorithms. This work addresses that gap. The PLFU cache algorithm, being a stochastic process, can be represented as a Markov process after the cache has been in operation for a sufficient period. The proposed model enables the estimation of per-object miss rates for both single caches and cache networks, applicable directly to the PLFU algorithm and indirectly to Tiny-LFU strategies. Given that many CDNs employ LFU-like eviction policies, we show that our novel model provides practitioners and decision-makers with a practical tool for designing and deploying CDNs effectively.