Approximation of LRU Caches Miss Rate: Application to Power-law Popularities

2017/05/19 by Christian Berthet, Berthet, Christian
Computer Science · #Advanced Data Storage Technologies #Caching and Content Delivery #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Peer-to-Peer Network Technologies #Performance (cs.PF)

paper · pdf · doi:10.48550/arxiv.1705.10738

openalex publication_date 2017/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Building on the 1977 pioneering work of R. Fagin, we give a closed-form expression for the approximated Miss Rate (MR) of LRU Caches assuming a power-law popularity. Asymptotic behavior of this expression is an already known result when power-law parameter is above 1. It is extended to any value of the parameter. In addition, we bring a new analysis of the conditions (cache relative size, popularity parameter) under which the ratio of LRU MR to Static MR is worst-case.

Citations

• Birthday paradox, coupon collectors, caching algorithms and self-organizing search
• Hydrodynamic limit of move-to-front rules and search cost probabilities
• Evaluation techniques for storage hierarchies

Related

• A versatile and accurate approximation for LRU cache performance
• Identity of King and Flajolet & al. Formulae for LRU Miss Rate Exact Computation
• Analyzing the Performance of LRU Caches under Non-Stationary Traffic Patterns
• On the Convergence of the TTL Approximation for an LRU Cache under Independent Stationary Request Processes
• On Resource Pooling and Separation for LRU Caching