Source-linked AI summary
Temporal Locality in Today's Content Caching: Why it Matters and How to Model it
Mohamed Ahmed, Stefano Traverso, Michele Garetto, Paolo Giaccone, Emilio Leonardi, Saverio Niccolini
TL;DR
The paper asks how to model content-request arrivals realistically enough to evaluate caching systems when traces are limited and traffic changes must be explored. Using YouTube traces, it identifies temporal locality and popularity dynamics as important, then proposes the parsimonious Shot-Noise Model. The SNM better accounts for real temporal locality than existing approaches while remaining suitable for analytical and scalable simulation studies.
Problem
Caching evaluations need realistic request-arrival models because trace data may be unavailable or insufficient for testing future traffic scenarios, while IRM assumptions can introduce significant errors.
Method
The paper analyzes YouTube traces from operational residential networks and proposes the Shot-Noise Model, which represents content requests through evolving per-content popularity profiles.
Results
The SNM accurately models cache performance and provides a much better account of temporal locality than the IRM and existing approaches.
Takeaways & Limitations
Cache analyses should model temporal locality and content-popularity dynamics rather than relying on long-term, independent, time-invariant popularity assumptions alone.
Takeaways & Limitations
In the evaluated scenario, IRM accuracy depends on estimating relative popularity over intervals of around one day, a difficult requirement in practice.
Abstract
from arXiv · showhide
The dimensioning of caching systems represents a difficult task in the design of infrastructures for content distribution in the current Internet. This paper addresses the problem of defining a realistic arrival process for the content requests generated by users, due its critical importance for both analytical and simulative evaluations of the performance of caching systems. First, with the aid of YouTube traces collected inside operational residential networks, we identify the characteristics of real traffic that need to be considered or can be safely neglected in order to accurately predict the performance of a cache. Second, we propose a new parsimonious traffic model, named the Shot Noise Model (SNM), that enables users to natively capture the dynamics of content popularity, whilst still being sufficiently simple to be employed effectively for both analytical and scalable simulative studies of caching systems. Finally, our results show that the SNM presents a much better solution to account for the temporal locality observed in real traffic compared to existing approaches.
1. INTRODUCTION
Caching reduces network distance, operator costs, and user-service impacts, but evaluating cache systems requires realistic request models when traces are limited or future traffic changes must be tested. The paper quantifies IRM errors for on-demand video and proposes the Shot-Noise Model as a simpler, scalable alternative that captures temporal locality.
- 1. INTRODUCTION: Trace-driven analysis is limited by dataset size, availability, diversity, privacy concerns, and inability to test traffic profiles that do not yet exist.
- 1. INTRODUCTION: Realistic content-request models are central to accurate analytical and simulation-based evaluations of caching-system performance.The paper focuses on Video-on-Demand systems because multimedia traffic represents a large and growing share of network traffic.
- 1. INTRODUCTION: The paper shows that the classical IRM introduces considerable cache-performance errors in on-demand video delivery.IRM remains widely used because of its tractability.
- 1. INTRODUCTION: The Shot-Noise Model explicitly accounts for temporal locality while retaining simplicity and scalability for analytical and large-scale simulation studies.The paper validates the model’s accuracy using real traffic traces.
- 1. INTRODUCTION: Earlier temporal-locality models mainly studied early WWW traffic, emphasized short-time correlations, and did not model the origins of temporal locality.
2. THE STANDARD APPROACH
The standard IRM assumes fixed, time-invariant, independent content popularity and is attractive for tractable cache analysis, but real popularity varies over time. Trace-based tests show that long-term popularity estimates and destroyed temporal correlations can substantially distort LRU cache predictions.
- 2. THE STANDARD APPROACH: The IRM models requests from a fixed catalogue with constant per-content probabilities and independence from past requests.It is widely adopted because these assumptions support tractable analytic models.
- 2. THE STANDARD APPROACH: Choosing and parameterising the popularity distribution is difficult because cache performance depends heavily on relative content popularity.Zipf-like distributions have empirical support, but their parameterisation is not obvious.
- 2. THE STANDARD APPROACH: As the trace is divided into more slices, fitted Zipf tail α rises from 0.70 at K = 1 to 0.85 at K = 120, while relative-popularity variance also increases.
- 2. THE STANDARD APPROACH: Breaking temporal correlations by random shuffling preserves long-term popularity but can significantly alter LRU cache performance.The shuffled sequence corresponds to the naive IRM treatment of the trace.
- 2. THE STANDARD APPROACH: Correcting IRM requires an evaluation interval matched to cache dynamics and a separately computed popularity distribution for a reduced catalogue.This procedure is not straightforward and depends on the cache scenario.
- 2. THE STANDARD APPROACH: The experiments are constrained to cache sizes whose eviction time is significantly shorter than the traces’ total duration.Observed average eviction times were 2–3 days for cache sizes in the relevant range.
- 2. THE STANDARD APPROACH: 2–10×: the IRM overestimates the cache size required for a target hit probability, especially at low hit probabilities.Increasing K makes the required cache size approach the unmodified-trace result, particularly when slice durations reach a few hours.
3. TOWARDS A NEW MODEL
Real traffic is non-stationary because aggregate request rates vary diurnally and individual-content request rates change over time. The model should capture content-level temporal locality and the joint distribution of request volume and effective life-span, while diurnal variation can be neglected for key cache metrics.
- Traffic characteristics: Two factors drive observed non-stationarity: diurnal aggregate request-rate variation and highly non-stationary request rates for individual contents.The aggregate variation has little impact on main cache metrics such as hit probability because these depend on the content-ID sequence rather than request timestamps.
- Traffic characteristics: Individual videos exhibit heterogeneous request distributions and strong time-locality, with popularity sometimes vanishing within days and sometimes persisting nearly throughout the trace.This motivates describing each content by total request volume V_m and effective life-span l_m.
- Traffic characteristics: Effective life-span l_m is the interval between the requests corresponding to 0.1V_m and 0.9V_m, filtering isolated late outliers from an object's lifetime.Observed values are estimated from requests inside the finite trace window, so they may not equal the true volume and life-span.
- Traffic characteristics: The joint distribution of estimated request volume and effective life-span should be modeled because these metrics are heterogeneous and correlated.A traffic generator must represent short-lived videos and high-volume videos, which can account for more than 27% of requests despite comprising only 2% of videos.
- Traffic characteristics: Seven–10% of videos have estimated life-spans no longer than 5 days, while 2% have estimated volumes of at least 10 and generate more than 27% of requests.These percentages hold across all traces in the data set and identify the content groups most important for accurate traffic generation.
- Traffic characteristics: The parameters V_m and l_m do not fully describe popularity evolution, which can follow complex archetypal growth profiles.Nevertheless, the paper notes that cache performance is essentially driven by the parameter discussed next in the section.
4. SHOT NOISE TRAFFIC MODEL
The Shot Noise Model represents content requests as independent, content-specific processes whose popularity evolves over time, balancing temporal-locality fidelity with analytical and simulation simplicity. Trace fitting and validation show that simplified popularity profiles accurately predict cache performance, while short-lived popular contents and long-lived-content uncertainty require careful treatment.
- The model is designed to represent content popularity dynamics and temporal locality while remaining general, simple, and analytically tractable.Its goals include capturing cache-relevant phenomena, ignoring limited-impact effects, and enabling analysis of popular caching policies.
- Each content m is described by insertion time τ_m, average request count V_m, and popularity profile λ_m(t), with the overall process formed by superposing independent content processes.The profile is nonnegative, causal, integrable, and normalized.
- New contents arrive according to a homogeneous Poisson process of rate γ, while each content generates requests through a time-inhomogeneous Poisson process.These Poisson assumptions are introduced for analytical tractability and are supported by trace observations at very short time scales.
- 4.1 Parameter Fitting: The fitting procedure partitions contents into six classes using measured request volume and life-span, with Class 1 attracting approximately 10% of requests despite containing less than 4% of contents.Because these short-lived contents exhibit strong temporal locality, they can significantly affect cache performance.
- 4.1 Parameter Fitting: Across four traces, class parameters remain similar within a factor of 2, supporting a flexible synthetic model that fits invariant properties and scales context-dependent parameters.The model uses shared popularity-profile shapes for Classes 1–4 and samples class-specific content arrivals.
- 4.2 Model Validation: SNM predictions using uniform or exponential profiles closely match the original trace, whereas shuffled-trace IRM results diverge substantially, especially for small caches.Daily traffic oscillations have marginal cache-performance impact, while highly popular contents with life-spans of a few days should not be neglected.
- 4.1 Parameter Fitting: The model provides accurate cache-performance predictions despite simplified parameter fitting, but month-long traces are insufficient for extracting general laws about long-lived contents.Class 5 life-spans are comparable to the trace length, so the model treats them as stationary to obtain conservative predictions.
5. FINAL CONSIDERATIONS
The paper finds that IRM error in on-demand video cache evaluation is substantial, especially for small caches, and proposes SNM as a practical replacement. SNM captures cache performance accurately while remaining suitable for analytical and scalable simulation studies.
- The first quantification of IRM error in on-demand video delivery shows that its induced error is large enough to make IRM too pessimistic for practical use.The problem is especially pronounced when cache sizes are small.
- For small cache sizes, IRM produces particularly misleading cache-performance estimates.
- The Shot-Noise Model (SNM) is proposed as a parsimonious replacement that accurately models cache performance.
- SNM is sufficiently simple for effective use in both analytical studies and scalable simulations of large caching systems.
- SNM captures fundamental characteristics of temporal locality while flexibly modeling and synthesising content request arrival processes.