Cache miss estimation for non-stationary request processes

DOI10.1287/STSY.2017.0009MaRDI QIDQ5113879zbMATH OpenOpenAlexWikidataFDO

Authors Felipe Olmos, Carl Graham, Alain Simonian

Publication date 18 June 2020

Published in Stochastic Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1324223 (Why is no real title available?)
• scientific article; zbMATH DE number 557946 (Why is no real title available?)
• scientific article; zbMATH DE number 903457 (Why is no real title available?)
• An Introduction to the Theory of Point Processes
• An Introduction to the Theory of Point Processes
• Applied asymptotic analysis
• Lewy-Stampacchia inequality in quasilinear unilateral problems and application to the \(G\)-convergence
• Probability with Martingales
• Probability: a graduate course
• Quasiconvex optimization and location theory
• Stochastic-Process Limits

Cited in

(3)

• Markov process analysis for web caching with multiple popularity levels
• A fluid limit for a cache algorithm with general request processes
• Modeling least recently used caches with shot noise request processes

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)