Stationary Distribution of a Generalized LRU-MRU Content Cache

2017/04/17 by George Kesidis, Kesidis, George
Computer Science · Materials Science · #Caching and Content Delivery #Covalent Organic Framework Applications #FOS: Computer and information sciences #Opportunistic and Delay-Tolerant Networks #Performance (cs.PF)

paper · pdf · doi:10.48550/arxiv.1704.04849

openalex publication_date 2017/04/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Many different caching mechanisms have been previously proposed, exploring different insertion and eviction policies and their performance individually and as part of caching networks. We obtain a novel closed-form stationary invariant distribution for a generalization of LRU and MRU caching nodes under a reference Markov model. Numerical comparisons are made with an "Incremental Rank Progress" (IRP a.k.a. CLIMB) and random eviction (a.k.a. random replacement) methods under a steady-state Zipf popularity distribution. The range of cache hit probabilities is smaller under MRU and larger under IRP compared to LRU. We conclude with the invariant distribution for a special case of a random-eviction caching tree-network and associated discussion.

Related

• Analyzing the Performance of LRU Caches under Non-Stationary Traffic Patterns
• The Design of Dynamic Probabilistic Caching with Time-Varying Content Popularity
• Performance Evaluation of the Random Replacement Policy for Networks of Caches
• Network Cache Design under Stationary Requests: Exact Analysis and\n Poisson Approximation
• A versatile and accurate approximation for LRU cache performance