Cache miss estimation for non-stationary request processes

DOI10.1287/STSY.2017.0009zbMATH Open1456.68020arXiv1511.07392OpenAlexW2963475118WikidataQ130199851 ScholiaQ130199851MaRDI QIDQ5113879FDOQ5113879

Carl Graham, Felipe Olmos, Alain Simonian

Publication date: 18 June 2020

Published in: Stochastic Systems (Search for Journal in Brave)

Abstract: The aim of the paper is to evaluate the miss probability of a Least Recently Used (LRU) cache, when it is offered a non-stationary request process given by a Poisson cluster point process. First, we construct a probability space using Palm theory, describing how to consider a tagged document with respect to the rest of the request process. This framework allows us to derive a general integral formula for the expected number of misses of the tagged document. Then, we consider the limit when the cache size and the arrival rate go to infinity proportionally, and use the integral formula to derive an asymptotic expansion of the miss probability in powers of the inverse of the cache size. This enables us to quantify and improve the accuracy of the so-called Che approximation.

Full work available at URL: https://arxiv.org/abs/1511.07392

Recommendations

• A fluid limit for a cache algorithm with general request processes
• Modeling least recently used caches with shot noise request processes
• Least-recently-used caching with dependent requests
• On the asymptotics of fault probability in least-recently-used caching with Zipf-type request distribution
• Optimizing LRU Caching for Variable Document Sizes

zbMATH Keywords

performance evaluationCox processPoisson cluster processChe approximationLRU cache policyscaling limit expansion

Mathematics Subject Classification ID

Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30)

Cites Work

• An Introduction to the Theory of Point Processes
• Title not available (Why is that?)
• Stochastic-Process Limits
• Probability with Martingales
• Applied asymptotic analysis
• An Introduction to the Theory of Point Processes
• Probability: A Graduate Course
• Quasiconvex optimization and location theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (1)

• Markov process analysis for web caching with multiple popularity levels

This page was built for publication: Cache miss estimation for non-stationary request processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113879)