A versatile and accurate approximation for LRU cache performance

Christine Fricker; Philippe Robert; James Roberts

Source-linked AI summary

A versatile and accurate approximation for LRU cache performance

Christine Fricker, Philippe Robert, James Roberts

arXiv:1202.3974v1Feb 17, 2012cs.NI

TL;DR

Evaluating ICN caches is difficult because content populations are immense and popularity laws are diverse, mixed across content types, and filtered by cache hierarchies. The paper rigorously analyzes the Che approximation for LRU hit rates, showing why it remains accurate beyond its original intuitive assumptions. It concludes that the approximation is a versatile tool for large-scale ICN cache evaluation where alternative approaches can be impractical.

Problem
ICN cache evaluation must handle immense content populations and diverse, composite popularity laws, while alternative methods can become impractical at large scale.
Method
The paper mathematically analyzes the Che approximation for LRU hit rates, deriving it by replacing an S-shaped integral term with a step function at characteristic time tC.
Results
The approximation is accurate even when Che et al.’s intuitive conditions fail, including a geometric-popularity case with N = 100 where discrepancies are visible only slightly for object 1.
Takeaways & Limitations
The Che approximation supports ICN cache evaluation with composite and filtered popularity laws when large populations and diverse catalogues make alternative approaches impractical.
Takeaways & Limitations
The analysis assumes sojourn times are approximately proportional to the request rate of other objects.

Abstract

from arXiv · show

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.

1. Introduction

The paper examines the Che approximation for LRU cache hit rates, which is highly accurate but lacks a rigorous explanation for its broad success. It aims to clarify the approximation’s scope, especially for large and diverse ICN caching problems.

Motivation and contribution: ICN evaluation requires cache-performance tools that handle immense content populations and diverse popularity characteristics.These requirements arise because ICN architectures use networks of caches to trade bandwidth for memory.
Motivation and contribution: The Che approximation estimates LRU cache hit rates and has proved extremely accurate even when its original intuitive justification does not apply.The paper provides more rigorous mathematical arguments to define when the approximation is reliable.
Model: The model assumes independent requests for N objects, with a miss copying the requested object into a capacity-C cache and evicting the least recently requested object.Object n is requested with probability proportional to q(n).
Approximation: The Che approximation expresses each object’s hit rate through a characteristic time tC defined as the unique root of an equation.The supplied passage introduces the hit-rate approximation and the defining root equation, although their displayed formulas are not included here.
Related approaches: An iterative alternative has O(CN) complexity, which can be prohibitive when both cache capacity and object population are very large.Related work also includes comparable-complexity FIFO hit-rate calculations and closed-form estimates restricted to particular popularity laws.

2. Traffic model

The paper models cache requests with an independent reference process and popularity law q(·), including composite and filtered laws relevant to hierarchical ICN caches. It also identifies temporal and spatial locality as boundaries on the model’s validity.

The independent reference model: The independent reference model represents requests as independent object choices with probabilities proportional to the popularity law q(·).An equivalent construction uses independent exponential timers with rates q(n), where the smallest timer determines the next requested object.
Popularity laws: Cache performance depends crucially on q(·), commonly modeled with a generalized Zipf law q(n) = 1/n^α.Observed content types include web pages, BitTorrent files, YouTube documents, and video-on-demand movies, with estimated α often around 0.8.
Popularity laws: A traffic mix should combine content-type popularities according to request proportions and account for differences in object sizes.A single Zipf law may represent homogeneous content but is not sufficient for mixed Internet traffic.
Popularity laws: Higher-layer caches observe a popularity law filtered by misses from lower-layer caches.Figure 1 illustrates the filtered law for requests overflowing a size-1000 cache under Zipf(0.8) popularity with N = 10000.
Popularity laws: The Che approximation accommodates composite popularity laws and filtering without requiring objects to be popularity-ordered or q(n) to be normalized.This flexibility supports the complex popularity patterns encountered in cache hierarchies.
Model validity: The independent reference model assumes popularity remains unchanged, so it is limited for content and catalogues that evolve over time.It may remain acceptable when popularity changes slowly relative to cache churn; week-scale statistics can poorly represent short-lived content.
Model validity: Spatial locality creates regional popularity biases that require more careful specification of popularity laws rather than invalidating the independent reference model outright.For example, a French network may observe high popularity for French-language movies.
Model validity: The independent reference model is considered reasonable when requests arise independently from many users, or when higher-layer caches aggregate many independent low-intensity overflows.The paper concludes that evaluating cache performance requires care in specifying the popularity law.

3. The Che approximation

The Che approximation estimates LRU hit rates using a characteristic time shared across objects, and its accuracy extends to variable-sized objects and popularity laws beyond the original intuitive setting.

3.1. A characteristic time: The approximation models an LRU cache through the time at which C distinct other objects have been requested since an object’s previous request.For object n, a request is a hit when fewer than C other objects are requested before its next request; this leads to the random time T_C(n).
3.1. A characteristic time: Che et al. approximate the random eviction time T_C(n) by a deterministic t_C(n), then use a common characteristic time t_C for all objects.The common-time approximation is supported as reasonable when individual popularities are small relative to total popularity and is retained after numerical verification.
3.1. A characteristic time: The resulting hit rate for object n is h(n) = 1 −e−q(n)tC, with t_C defined as the unique root of the cache-capacity equation.Che et al. refer to t_C as the cache’s characteristic time.
3.2. Variable sized objects: The approximation remains applicable when cache capacity is measured in bytes and objects have different sizes, with size effects incorporated through the capacity equation.The analysis assumes object sizes are much smaller than the cache capacity so boundary effects can be ignored, while the hit-rate formula remains unchanged.
3.2. Variable sized objects: Chunking variable-sized objects into constant-sized pieces yields the same characteristic-time equation, provided chunks inherit their parent object’s popularity.When chunks from one object have different popularities, the paper instead recommends directly specifying a popularity law for chunks.
3.3. Accuracy: For a population of 10,000 objects under Zipf popularity with α = 0.8 or α = 1.2, simulation crosses and approximation lines agree perfectly for practical purposes.The comparison covers objects ranked 1, 10, 100, and 1000 across cache sizes.
3.3. Accuracy: For 100 objects with geometric popularity ρ = 0.9, discrepancies are very slight and visible only for object 1, despite Che et al.’s intuitive arguments not applying.The figure compares objects ranked 1, 4, 16, and 64.

4. Why the approximation works

The paper explains the Che approximation through the distribution of X(t): Gaussian behavior converts cache-time probabilities into an integral whose sharp transition is well approximated by a step function.

4. Why the approximation works: X(t) is modeled as a sum of independent random variables, motivating a Gaussian approximation and the relation P(TC > t) = P(X(t) < C).Simulations support Gaussian behavior for Zipf and geometric popularity laws over the examined times.
4.2. A central limit theorem.: The central-limit result guarantees asymptotic Gaussianity when σ(t) grows unboundedly, but does not explain the excellent small-time or geometric-popularity fit.For geometric popularity, the variance need not increase, so the general asymptotic bound is insufficient to account for the observed accuracy.
4.3. Approximating the hit rates.: Assuming X(t) is Gaussian, Proposition 2 expresses object hit rates through an integral involving the complementary error function.The complementary error function appears after evaluating the Gaussian tail probability.
4.3. Approximating the hit rates.: Because the complementary error function rapidly transitions near m(u) = C, the integral replaces it with the step function 1{m(u)>C}.With m(tC) = C and increasing m(u), this step-function integral yields the Che approximation.

5. Zipf popularity and a large cache

For Zipf popularity, the paper proves that the Che approximation is asymptotically valid by characterizing the characteristic time and the fluctuations of TC. The analysis also explains accuracy when geometric popularity prevents TC from becoming deterministic.

5. Zipf popularity and a large cache: For Zipf popularity, the paper proves asymptotic validity of the Che approximation and characterizes tC without solving the original defining equation.The result is developed from lemmas relating the moments of X(t).
5.1. Preliminary results: The variance of X(t) is expressed in terms of its mean, and a second lemma establishes the relevant large-N behavior under q(n) = 1/n^α.These lemmas provide the moment and scaling ingredients for the asymptotic analysis.
5.2. A Gaussian approximation for TC.: For Zipf popularity with C = ⌊δN⌋, TC is asymptotically Gaussian around tC, with fluctuations smaller than tC as N grows.The centered and scaled fluctuations converge to a centred Gaussian random variable.
5.2. A Gaussian approximation for TC.: The concentration of TC implies TC/tC ∼ 1 and E(e^-qTC) → e^-qtC as C and N tend to infinity.Thus the deterministic characteristic-time argument used by Che et al. applies in this regime.
5.2. A Gaussian approximation for TC.: For geometric popularity, the variance of X(t) is asymptotically constant and small relative to its mean, explaining Che accuracy even though TC is not deterministic.The paper gives m(t) = −log t/log ρ + O(1) and σ(t)^2 = log 2/log ρ + O(1).

6. A “Che approximation” for random replacement

The paper extends the characteristic-time strategy to random replacement, deriving an approximation with complexity comparable to Che’s method. Its accuracy is reported as comparable to the LRU approximation.

6. A “Che approximation” for random replacement: Random replacement is studied because it is simpler to implement than LRU, while its exact analysis is too complex for practical evaluation.The policy overwrites a randomly selected cached object and has the same hit rates as FIFO.
6. A “Che approximation” for random replacement: Using Little’s formula, each hit rate is represented as the product of an object’s cache-entry frequency and average sojourn time.The entry frequency is λ(n) = (1 − h(n))q(n).
6. A “Che approximation” for random replacement: Assuming sojourn time is inversely proportional to the request rate of other objects yields a common constant τC and an equation obtained by setting total hit rates equal to cache size C.The assumption is described as approximate but intuitively reasonable.
6. A “Che approximation” for random replacement: Solving the τC equation gives random-replacement hit rates through the resulting approximation.This equation is presented as the random equivalent of the LRU Che identity.
6. A “Che approximation” for random replacement: The random-replacement approximation has accuracy comparable to the Che approximation, and the FIFO approximation of Dan and Towsley is similarly accurate.The paper notes that the underlying sojourn-time assumption appears reasonable for realistic popularity laws.

7. Application

The application models a diverse ICN traffic mix and uses Che approximations to evaluate cache performance where other approaches are impractical. Results compare LFU, LRU, and random replacement across cache sizes.

The traffic mix combines web, file-sharing, UGC, and VoD content retrieved through a cache.
Very large populations and diverse popularity laws make alternative evaluation approaches, including simulation, impractical.
Objects are divided into 1 KB chunks, with type-specific sizes and Zipf popularity inherited by their chunks.
Che-approximation summations over as many as 10^11 objects are accelerated by grouping nearly equal successive terms.The resulting computation is described as very rapid.
Figure 6 compares overall hit rate against cache size for LFU, LRU, and random replacement using the corresponding approximations.
Random replacement is hardly worse than LRU for this traffic mix, while the results remain readily derived with the Che approximation.

8. Conclusion

The paper concludes that the Che approximation is versatile and highly accurate for predicting LRU cache hit rates. Its analysis supports using the tool for large, diverse ICN cache catalogues and general cache networks.

The Che approximation is a versatile and highly accurate tool for predicting hit-rate performance under LRU replacement.
The paper explains why the approximation works well even when conditions suggested by its authors are not satisfied.
The analysis supports evaluating ICN performance when large populations and diverse content catalogues preclude alternative approaches.
The Che approximation can be combined with the approach in to evaluate large-scale, general cache networks.