A versatile and accurate approximation for LRU cache performance

Abstract

In a 2002 paper, Che and co-authors proposed a simple approach for estimating the hit rates of a cache operating the least recently used (LRU) replacement policy. The approximation proves remarkably accurate and is applicable to quite general distributions of object popularity. This paper provides a mathematical explanation for the success of the approximation, notably in configurations where the intuitive arguments of Che, et al clearly do not apply. The approximation is particularly useful in evaluating the performance of current proposals for an information centric network where other approaches fail due to the very large populations of cacheable objects to be taken into account and to their complex popularity law, resulting from the mix of different content types and the filtering effect induced by the lower layers in a cache hierarchy.

Cited by in corpus (33)

• A Utility Optimization Approach to Network Cache Design
• A Cache Management Scheme for Efficient Content Eviction and Replication in Cache Networks
• Practical Bounds on Optimal Caching with Variable Object Sizes
• Analyzing the Performance of LRU Caches under Non-Stationary Traffic Patterns
• Exploring the Memory-Bandwidth Tradeoff in an Information-Centric Network
• Adapting Caching to Audience Retention Rate: Which Video Chunk to Store?
• A Low-Complexity Approach to Distributed Cooperative Caching with Geographic Constraints
• Optimized Dynamic Cache Instantiation and Accurate LRU Approximations under Time-varying Request Volume
• Spatial multi-LRU: Distributed Caching for Wireless Networks with Coverage Overlaps
• A unified approach to the performance analysis of caching systems
• A Swiss Army Knife for Dynamic Caching in Small Cell Networks
• Impact of Traffic Characteristics on Request Aggregation in an NDN Router
• Optimal Dynamic Multicast Scheduling for Cache-Enabled Content-Centric Wireless Networks
• Characterizing Interest Aggregation in Content-Centric Networks
• Go-With-The-Winner: Client-Side Server Selection for Content Delivery
• Adaptive Replication in Distributed Content Delivery Networks
• No-Regret Caching via Online Mirror Descent
• Joint Cache Resource Allocation and Request Routing for In-network Caching Services
• LAC: Introducing Latency-Aware Caching in Information-Centric Networks - Technical Report
• UtilCache: Effectively and Practicably Reducing Link Cost in Information-Centric Network
• Learning to Cache With No Regrets
• Mean Field and Refined Mean Field Approximations for Heterogeneous Systems: It Works!
• Caching under Content Freshness Constraints
• Stationary Distribution of a Generalized LRU-MRU Content Cache
• Modeling LRU caches with Shot Noise request processes
• A General, Tractable and Accurate Model for a Cascade of Caches
• On a caching system with object sharing
• Similarity Caching: Theory and Algorithms
• On the Delay Scaling Laws of Cache Networks
• Temporal Locality in Today's Content Caching: Why it Matters and How to Model it
• NV-Fogstore : Device-aware hybrid caching in fog computing environments
• Asymptotic Miss Ratio of LRU Caching with Consistent Hashing
• An Analytical Model for Performance and Lifetime Estimation of Hybrid DRAM-NVM Main Memories