NDLI: Transient and steady-state regime of a family of list-based cache replacement algorithms

Content Provider	Springer Nature Link
Author	Gast, Nicolas Houdt, Benny
Copyright Year	2016
Abstract	We study the performance of a family of cache replacement algorithms. The cache is decomposed into lists. Some of these lists can be virtual in the sense that only meta-data are stored in those lists. An item enters the cache via the first list and jumps to the next list whenever a hit on it occurs. The classical policies FIFO, RANDOM, CLIMB, and its hybrids are obtained as special cases. We present explicit expressions for the cache content distribution and miss probability under the IRM model. We develop an algorithm with a time complexity that is polynomial in the cache size and linear in the number of items to compute the exact miss probability. We introduce lower and upper bounds on the latter that can be computed in a time that is linear in the cache size times the number of items. We introduce a mean-field model to approximate the transient behavior of the miss probability and prove that this model becomes exact as the cache size and number of items go to infinity. We show that the set of ODEs associated to the mean-field model has a unique fixed point that can be used to approximate the miss probability in case the exact computation is too time consuming. Using this approximation, we provide guidelines on how to select a replacement algorithm within the family considered such that a good trade-off is achieved between the cache reactivity and its steady-state hit probability. We simulate these cache replacement algorithms on traces of real data and show that they can outperform LRU. Finally, we also disprove the well-known conjecture that the CLIMB algorithm is the optimal finite-memory replacement algorithm under the IRM model.
Ending Page	328
Page Count	36
Starting Page	293
File Format	PDF
ISSN	02570130
e-ISSN	15729443
Journal	Queueing Systems
Issue Number	3-4
Volume Number	83
Language	English
Publisher	Springer US
Publisher Date	2016-06-15
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Systems Theory, Control Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) Probability Theory and Stochastic Processes Self-organizing lists Miss ratio Information storage and retrieval Cache replacement policies Storage management Performance evaluation; queueing; scheduling Operation Research/Decision Theory Supply Chain Management Computer Communication Networks Independent reference model
Content Type	Text
Resource Type	Article
Subject	Statistics and Probability Management Science and Operations Research Computational Theory and Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Transient and Steady-state Regime of a Family of List-based Cache Replacement Algorithms

The acquisition queue

Ergodic Theory for Controlled Markov Chains with Stationary Inputs

Local stability in a transient Markov chain

Steady-state analysis of shortest expected delay routing

Loss systems in a random environment: steady state analysis

Estimating Instantaneous Cache Hit Ratio Using Markov Chain Analysis

Analysis of queueing systems with customer interjections

A Tandem Queueing model for an appointment-based service system

Transient and steady-state regime of a family of list-based cache replacement algorithms

Similar Documents

Transient and Steady-state Regime of a Family of List-based Cache Replacement Algorithms

The acquisition queue

Ergodic Theory for Controlled Markov Chains with Stationary Inputs

Local stability in a transient Markov chain

Steady-state analysis of shortest expected delay routing

Loss systems in a random environment: steady state analysis

Estimating Instantaneous Cache Hit Ratio Using Markov Chain Analysis

Analysis of queueing systems with customer interjections

A Tandem Queueing model for an appointment-based service system

Transient and steady-state regime of a family of list-based cache replacement algorithms