PaperlayerView exact revision on arXiv

Source-linked AI summary

A unified approach to the performance analysis of caching systems

Valentina Martina, Michele Garetto, Emilio Leonardi

arXiv:1307.6702v6cs.NIcs.PF

TL;DR

Cache-network analysis is difficult and existing techniques cover limited policies, traffic models, and network settings. The paper extends Che’s decoupling principle into a low-cost unified framework covering broader policies, renewal traffic, and interconnected caches. Its predictions are reported to closely match simulations and are qualitatively confirmed by trace-driven experiments, with k-LRU identified as superior in the considered system-design comparisons.

  • Problem

    Existing cache-analysis techniques have limited scope across policies, traffic conditions, and interconnected-cache settings, while exact analysis is computationally expensive.

  • Method

    The paper generalizes Che’s decoupling principle across caching policies, renewal traffic with temporal locality, and interconnected caches beyond the standard Poisson assumption.

  • Results

    The unified framework provides accurate, low-cost predictions that are reported to closely match simulations and are qualitatively confirmed by trace-driven experiments.

  • Takeaways & Limitations

    The framework supports broad cache-performance analysis and identifies k-LRU as superior in simplicity and performance gains from the system-design perspective.

Abstract

from arXiv · show

We propose a unified methodology to analyse the performance of caches (both isolated and interconnected), by extending and generalizing a decoupling technique originally known as Che's approximation, which provides very accurate results at low computational cost. We consider several caching policies, taking into account the effects of temporal locality. In the case of interconnected caches, our approach allows us to do better than the Poisson approximation commonly adopted in prior work. Our results, validated against simulations and trace-driven experiments, provide interesting insights into the performance of caching systems.

I. INTRODUCTION AND PAPER CONTRIBUTIONS

The paper develops a unified Che-based methodology for analyzing diverse isolated and interconnected caching systems under broader traffic and policy models. The framework is designed for low computational cost and produces predictions that closely match simulations and trace-driven experiments.

  • Motivation: Existing cache-analysis techniques have limited scope, often focusing on LRU or FIFO, IRM traffic, and isolated caches.Analyzing cache networks exactly is computationally expensive, motivating accurate approximations with broader applicability.
  • Core contribution: The paper generalizes Che’s decoupling principle into a methodology for analyzing a variety of caching systems.The approach extends beyond its original setting of a single LRU cache under IRM traffic.
  • Core contribution: The framework covers more insertion and eviction policies, including multi-stage LRU, probabilistic-insertion LRU, FIFO, and RANDOM.These extensions broaden the policy set analyzed under Che’s approximation.
  • Core contribution: The traffic model uses renewal processes to capture temporal locality beyond the traditional IRM.IRM is memoryless with respect to past requests, whereas renewal traffic allows general inter-request time distributions; exponential inter-arrivals recover IRM.
  • Core contribution: The interconnected-cache analysis goes beyond the standard Poisson assumption and accommodates replication strategies such as leave-copy-probabilistically and leave-copy-down.The paper also generalizes its modeling approach to cache networks with mesh topology.
  • Validation and scope: Model predictions are reported as nearly indistinguishable from simulations on almost all plots, while trace-driven experiments qualitatively confirm the insights.The framework is presented as unified, simple, flexible, and low-cost, though not all extension combinations are analyzed.

D. Replication strategies for cache networks

The paper models cache-network replication strategies and uses Che’s decoupling principle to make cache-performance analysis tractable across policies and traffic models.

  • Replication strategies: LCE replicates a retrieved object to every cache on the request’s backward path.
  • Replication strategies: LCP independently sends the retrieved object to each backward-path cache with probability q.
  • Replication strategies: LCD places the object only in the cache preceding the one where it was found, except when it is found in the first visited cache.
  • Analytical approach: Che’s approximation summarizes interactions among contents through a single cache eviction time, enabling decoupled performance analysis.The approach extends beyond LRU to renewal traffic and other caching policies.

A. LRU under renewal traffic

Under renewal traffic, the paper separates time-average occupancy from request-time hit probability and extends Che-style analysis to q-LRU, RANDOM, and FIFO.

  • LRU under renewal traffic: Under renewal traffic, pin(m) and phit(m) differ because PASTA no longer applies; phit(m) is given by FR(m, TC).Occupancy uses the age distribution, while hit probability conditions on an arriving request.
  • q-LRU under IRM and renewal traffic: q-LRU tends asymptotically to LFU as q approaches zero under IRM and renewal traffic when the theorem’s inter-request-tail conditions hold.The stated condition is satisfied for exponential tails but not for power-law distributions.
  • RANDOM and FIFO: Under IRM, RANDOM and FIFO have the same hit probability by Erlang-B insensitivity.Under general renewal traffic, their performance is not necessarily the same.
  • RANDOM and FIFO: For RANDOM and FIFO under renewal traffic, object dynamics are modeled respectively by G/M/1/0 and G/D/1/0 queues.RANDOM uses an exponential sojourn-time approximation, whereas FIFO can use a constant cache residence time.
  • RANDOM and FIFO: Cycle analysis computes occupancy as pin(m) = E[TON]/E[Tcycle], with Tcycle equal to an inter-request interval.For the analyzed model, the resulting expression is pin(m) = λm E[TC] (1 −MR(m, −1/E[TC])).

D. 2-LRU

The paper develops refined Che-based models for 2-LRU, including a four-state Markov-chain formulation that avoids an independence assumption and extensions to renewal traffic.

  • 2-LRU: 2-LRU is analyzed using both a rough approximation with an additional simplifying assumption and a refined Che-based model.Both formulations cover IRM and renewal traffic.
  • 2-LRU: The independence approximation is considered reasonable when the second cache’s eviction time is significantly larger than the meta-cache’s eviction time.This timing difference de-synchronizes the two cache states.
  • 2-LRU: The refined model represents each object’s presence in the meta-cache and second cache with a four-state DTMC.Solving this chain yields the hit probability without requiring cache-state independence.
  • 2-LRU: The model extends to renewal traffic by retaining the same request-arrival-sampled Markov-chain structure while changing transition probabilities.The resulting probabilities use the inter-request-time distribution and cycle analysis.

E. k-LRU

The paper generalizes the analysis from 2-LRU to k-LRU and k-RANDOM, deriving iterative cache relations and an asymptotic connection between k-LRU and LFU.

  • k-LRU: Hit probabilities for k-LRU can be computed iteratively by relating each cache’s probability to that of the preceding cache.The same generalization extends to renewal traffic.
  • k-LRU: As k →∞, k-LRU tends asymptotically to LFU under IRM and renewal traffic, given unbounded inter-request-time support and the stated tail condition.The theorem compares contents with different request rates.
  • k-RANDOM: k-RANDOM can be analyzed with exponential sojourn times in the caches, using a continuous-time Markov chain with 2^k states.For 2-RANDOM, the object dynamics reduce to a four-state CTMC.
  • Small-cache approximations: Small-cache approximations use truncated Taylor expansions of hit and insertion probabilities with respect to T_C →0.These expansions expose how performance depends on object arrival rates and popularity.
  • Small-cache approximations: In the small-cache regime, k-LRU is best because its hit probability depends polynomially on popularity with order k ≥2, whereas other listed policies depend linearly.Among alternatives, q-LRU has a positive quadratic term, while LRU slightly outperforms RANDOM/FIFO.

H. Model validation and insights

Validation shows that the analytical models closely match simulations, while experiments reveal strong effects from temporal locality, insertion policy, and cache size.

  • Model validation: Analytical predictions are barely distinguishable from simulation results, including for 3-LRU despite its additional independence assumption.The evaluation uses IRM traffic with catalogue size M = 10^6 and Zipf exponent α = 0.8.
  • IRM insights: 2-LRU provides huge benefits under IRM, getting very close to LFU and outperforming simple LRU.The result is consistent with the predicted k-LRU convergence toward LFU.
  • Cache-size effects: In the small-cache regime, insertion policies that filter unpopular objects largely outperform policies without request filtering.Differences among policies span almost 1 order of magnitude, while eviction-policy effects are weaker.
  • Temporal locality: Increasing hyper-z traffic’s z strengthens temporal locality, which can have a dramatically beneficial impact on hit probability.The result motivates including temporal locality in analytical cache models.
  • Temporal locality: LFU is no longer optimal under non-IRM traffic because static placement does not adapt to instantaneous traffic conditions.The paper therefore evaluates policies under renewal traffic with temporal locality.
  • Policy comparison: Under strong temporal locality, 2-LRU performs very well because its insertion policy filters unpopular contents while adapting quickly to short-term popularity variations.By contrast, q-LRU performs poorly, especially for small q.
  • Trace-driven validation: On a real YouTube trace, most synthetic-traffic policy rankings still hold: 2-LRU significantly outperforms LRU and q-LRU, while extra meta-caches provide only minor improvements.The trace’s largest considered cache size was limited by its finite duration.

V. CACHE NETWORKS

The paper replaces the standard independent Poisson treatment of interconnected caches with a more accurate Che-based approximation that captures correlations between neighboring caches. In tandem networks, this refinement brings analytical predictions close to simulation results.

  • V. CACHE NETWORKS: The standard network approximation models each cache’s per-object arrivals as independent Poisson processes and solves the system through a multivariable fixed point.It computes forwarded average arrival rates from upstream hit probabilities before applying an IRM cache model.
  • V. CACHE NETWORKS: The improved method extends Che’s approximation to capture correlations among neighboring caches, initially deriving the tandem case before generalizing to arbitrary networks.The method uses different approximations for each replication strategy while retaining low-cost analysis.
  • V. CACHE NETWORKS: At the second cache, forwarded requests are ON-OFF modulated rather than Poisson because requests stop when the object is present upstream.This dependence explains why the second cache’s hit probability can differ substantially from its time-average occupancy probability.
  • V. CACHE NETWORKS: The refined analysis estimates second-cache hits by modeling the relevant non-Poisson request interval with an approximate Poisson process.The interval is constrained by the eviction times of the upstream and downstream caches.
  • V. CACHE NETWORKS: For a tandem network with M = 10^6 and Zipf exponent α = 0.8, the improved approximation brings total hit-probability predictions very close to simulation.The refinement substitutes a more accurate eviction-time term in the second-cache hit-probability formula.

B. Leave-copy-probabilistically

For leave-copy-probabilistically, the analysis preserves the first cache’s q-LRU behavior and derives the second cache’s hit probability from request-history conditions. A Poisson approximation remains necessary for estimating second-cache occupancy.

  • B. Leave-copy-probabilistically: The first cache is analyzed using the standard IRM formula for q-LRU, while the second cache requires separate hit- and occupancy-probability approximations.The first cache is unaffected by the second in this tandem setting.
  • B. Leave-copy-probabilistically: A second-cache hit occurs when the object is stored there but absent from the first cache at request time.The previous request must have produced a hit or triggered insertion at the second cache, subject to upstream insertion constraints.
  • B. Leave-copy-probabilistically: The analysis models forwarded requests that do not trigger upstream insertion as a Poisson process with intensity λ_m(2) · (1 − q).This approximation evaluates the complementary event needed for the second-cache hit probability.
  • B. Leave-copy-probabilistically: When q = 1, the leave-copy-probabilistically expression reduces to the leave-copy-everywhere expression.Thus LCE is recovered as the full-insertion special case.

C. Leave-copy-down

Leave-copy-down creates mutual dependence between caches because insertion upstream requires the object to be present downstream. The resulting equations use joint fixed-point solution and extend through routing-aware network formulas.

  • C. Leave-copy-down: Leave-copy-down is harder to analyze because cache 1 and cache 2 mutually depend on each other.An object can be inserted into cache 1 only when it is already stored in cache 2.
  • C. Leave-copy-down: The occupancy probability of cache 1 is expressed through hits in cache 1 and objects found in cache 2, using PASTA.The resulting relation combines pin(1, m), phit(1, m), and phit(2, m).
  • C. Leave-copy-down: Because the cache occupancies are interdependent, a fixed-point iteration is needed to determine them jointly.The method therefore solves the coupled occupancy equations rather than evaluating each cache independently.
  • C. Leave-copy-down: For general networks, routing fractions r_j,i determine how requests forwarded from cache j contribute to arrivals at cache i.These fractions are treated as inputs reflecting the network’s request-routing strategy.
  • C. Leave-copy-down: Tree networks can be evaluated from leaves toward the root, whereas general mesh networks require a global multivariate fixed point.The refined conditional hit-probability calculation is then de-conditioned over forwarding sources.

E. Model validation and insights

Validation shows close agreement between the analytical model and simulation, including highly correlated chains and cyclic networks. The experiments also distinguish replication strategies and clarify the method’s scope relative to prior work.

  • E. Model validation and insights: In a six-cache chain, analysis and simulation agree excellently for both first-cache and total-network hit probabilities.The chain was selected because it produces strong cache-state correlation and large deviations from the Poisson approximation.
  • E. Model validation and insights: LCP significantly outperforms LCE in the chain, while LCD performs best by exploiting aggregate storage and stronger filtering.LCD is characterized as the dual of k-LRU for cache networks.
  • E. Model validation and insights: In a 1365-cache, six-level 4-ary tree, LCD again provides a large gain over LCE, whereas LCP benefits are limited, especially for α = 0.7.These results are analytical predictions for a topology that is extremely expensive to simulate.
  • E. Model validation and insights: The model also predicts hit probabilities accurately for cache networks containing cycles, including the nine-cache ring topology.This extends validation beyond feed-forward network structures.
  • E. Model validation and insights: The framework targets broad policy and traffic coverage, whereas prior cache-network models often assume independent caches, limited topology, or restricted traffic conditions.Its advantage over one alternative is scalability and applicability to general mesh networks, while that alternative can support only IRM traffic here.
  • E. Model validation and insights: The paper’s stated goal is accurate, unified analysis of isolated and interconnected caches under varied insertion, eviction, and traffic conditions.The framework also supports simple derivations of cache properties, including asymptotic results.

APPENDIX

The appendix develops analytical results for cache occupancy and characteristic times under renewal traffic, including q-LRU and interconnected caches. It also examines limiting behavior as insertion probability q approaches zero and validates theoretical predictions numerically.

  • Small-q asymptotics: The limiting behavior depends on inter-request-time distributions: exponential and hyper-10 traffic approach LFU, whereas Pareto traffic approaches a different limit.Figure 14 plots hit probability against q for cache size 10,000 and α = 0.7, with Pareto exponent γ = 2.
  • Bounded-support case: When more than C contents have bounded inter-request-time support, T_C no longer tends to infinity as q approaches zero.Only contents whose maximum inter-request time is below the limiting characteristic time can have occupancy probability tending to 1, and at most C such contents can do so.
  • Interconnected-cache analysis: The analysis derives cache occupancy probabilities through cycle-based calculations for interconnected caches, relating time spent in cache states to p_in(m).The cycle analysis tracks request arrivals and ON periods to obtain p_in(m).
  • Interconnected-cache analysis: For interconnected caches, the characteristic time T_C diverges as the number of cache stages k grows, while occupancy probabilities converge to a fixed point.The divergence follows from the vanishing probability of the required chain of short inter-request intervals.
Loading 1307.6702v6…