research-article

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

Authors:

Benny Van HoudtAuthors Info & Claims

SIGMETRICS '15: Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems

Pages 123 - 136

https://doi.org/10.1145/2745844.2745850

Published: 15 June 2015 Publication History

Abstract

In this paper we study the performance of a family of cache replacement algorithms. The cache is decomposed into lists. Items enter the cache via the first list. 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 further 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 tends 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 becomes 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.

References

[1]

O. I. Aven, L. B. Boguslavsky, and Y. A. Kogan. Some results on distribution-free analysis of paging algorithms. IEEE Transactions on Computers, 25(7):737--745, July 1976.

Digital Library

[2]

O. I. Aven, E. G. Coffman, Jr., and Y. A. Kogan. Stochastic Analysis of Computer Storage. Kluwer Academic Publishers, Norwell, MA, USA, 1987.

Digital Library

[3]

O. Babaoglu and D. Ferrari. Two-level replacement decisions in paging stores. IEEE Trans. Comput., 32(12):1151--1159, Dec. 1983.

Digital Library

[4]

M. Benaím and J. Le Boudec. A class of mean field interaction models for computer and communication systems. Performance Evaluation, 65(11--12):823--838, 2008.

Digital Library

[5]

D. S. Berger, P. Gland, S. Singla, and F. Ciucu. Exact analysis of TTL cache networks. Performance Evaluation, 79:2--23, 2014.

Digital Library

[6]

J.-Y. L. Boudec. The stationary behaviour of fluid limits of reversible processes is concentrated on stationary points. arXiv:1009.5021, 2010.

[7]

L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web caching and Zipf-like distributions: Evidence and implications. In INFOCOM'99, volume 1, pages 126--134. IEEE, 1999.

[8]

H. Che, Y. Tung, and Z. Wang. Hierarchical web caching systems: modeling, design and experimental results. IEEE J.Sel. A. Commun., 20(7):1305--1314, 2002.

Digital Library

[9]

A. Dan and D. Towsley. An approximate analysis of the LRU and FIFO buffer replacement schemes. SIGMETRICS Perform. Eval. Rev., 18(1):143--152, Apr. 1990.

Digital Library

[10]

R. Fagin and T. G. Price. Efficient calculation of expected miss ratios in the independent reference model. SIAM J. Comput., 7:288--296, 1978.

Digital Library

[11]

N. C. Fofack, P. Nain, G. Neglia, and D. Towsley. Analysis of TTL-based cache networks. In Valuetools 2012, pages 1--10. IEEE, 2012.

[12]

C. M. Fortuin, P. W. Kasteleyn, and J. Ginibre. Correlation inequalities on some partially ordered sets. Communications in Mathematical Physics, 22(2):89--103, 1971.

[13]

C. Fricker, P. Robert, and J. Roberts. A versatile and accurate approximation for lru cache performance. In Proceedings of the 24th International Teletraffic Congress, ITC '12, pages 8:1--8, 2012.

Digital Library

[14]

M. Gallo, B. Kauffmann, L. Muscariello, A. Simonian, and C. Tanguy. Performance evaluation of the random replacement policy for networks of caches. Performance Evaluation, 72(0):16--36, 2014.

Digital Library

[15]

E. Gelenbe. A unified approach to the evaluation of a class of replacement algorithms. IEEE Trans. Comput., 22(6):611--618, June 1973.

Digital Library

[16]

J. H. Hester and D. S. Hirschberg. Self-organizing linear search. ACM Comput. Surv., 17(3):295--311, Sept. 1985.

Digital Library

[17]

R. Hirade and T. Osogami. Analysis of page replacement policies in the fluid limit. Oper. Res., 58:971--984, July 2010.

Digital Library

[18]

P. Jelenkovic. Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities. Ann. Appl. Probab., 9(2):430--464, May 1999.

[19]

S. Jiang and X. Zhang. LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance. SIGMETRICS Perform. Eval. Rev., 30(1):31--42, June 2002.

Digital Library

[20]

T. Johnson and D. Shasha. 2Q: A low overhead high performance buffer management replacement algorithm. In VLDB '94, pages 439--450, San Francisco, CA, USA, 1994.

Digital Library

[21]

J. Jung, A. W. Berger, and H. Balakrishnan. Modeling TTL-based internet caches. In INFOCOM 2003, volume 1, pages 417--426. IEEE, 2003.

[22]

W. F. King III. Analysis of demand paging algorithms. In IFIP Congress (1), pages 485--490, 1971.

[23]

N. Laoutaris, H. Che, and I. Stavrakakis. The LCD interconnection of LRU caches and its analysis. Perform. Eval., 63(7):609--634, July 2006.

Digital Library

[24]

A. W. Marshall and I. Olkin. Inequalities: theory of majorization and its applications. Academic Press, New York, 1979.

[25]

V. Martina, M. Garetto, and E. Leonardi. A unified approach to the performance analysis of caching systems. In INFOCOM 2014, pages 2040--2048, 2014.

[26]

E. J. Rosensweig, J. Kurose, and D. Towsley. Approximate models for general cache networks. In INFOCOM'10, pages 1100--1108, Piscataway, NJ, USA, 2010. IEEE Press.

Digital Library

[27]

D. Starobinski and D. Tse. Probabilistic methods for web caching. Perform. Eval., 46(2-3):125--137, Oct. 2001.

Digital Library

[28]

N. Tsukada, R. Hirade, and N. Miyoshi. Fluid limit analysis of FIFO and RR caching for independent reference models. Perform. Eval., 69(9):403--412, Sept. 2012.

Digital Library

[29]

J. van den Berg and A. Gandolfi. LRU is better than FIFO under the independent reference model. Journal of Applied Probability, 29(1):pp. 239--243, 1992.

[30]

J. van den Berg and D. F. Towsley. Properties of the miss ratio for a 2-level storage model with LRU or FIFO replacement strategy and independent references. IEEE Trans. Computers, 42(4):508--512, 1993.

Digital Library

[31]

S. Vanichpun and A. M. Makowski. Comparing strength of locality of reference -- popularity, majorization, and some folk theorems. In INFOCOM, 2004.

[32]

S. Vanichpun and A. M. Makowski. The output of a cache under the independent reference model: Where did the locality of reference go? SIGMETRICS Perform. Eval. Rev., 32(1):295--306, June 2004.

Digital Library

[33]

R. D. Yates. A framework for uplink power control in cellular radio systems. Selected Areas in Communications, IEEE Journal on, 13(7):1341--1347, 1995.

Digital Library

[34]

M. Zink, K. Suh, Y. Gu, and J. Kurose. Characteristics of YouTube network traffic at a campus network - measurements, models, and implications. Comput. Netw., 53(4):501--514, Mar. 2009.

Digital Library

Cited By

Gao YCasale GSinghal R(2024)Performance Modeling of Distributed Data Processing in Microservice ApplicationsACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/36872659:4(1-30)Online publication date: 20-Aug-2024
https://dl.acm.org/doi/10.1145/3687265
Wang PJiang HLiu YZhao ZZhou KHuang Z(2024)Beyond Belady to Attain a Seemingly Unattainable Byte Miss Ratio for Content Delivery NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.345209635:11(1949-1963)Online publication date: Nov-2024
https://doi.org/10.1109/TPDS.2024.3452096
Carlsson NEager D(2023)Optimized Dynamic Cache Instantiation and Accurate LRU Approximations Under Time-Varying Request VolumeIEEE Transactions on Cloud Computing10.1109/TCC.2021.311595911:1(779-797)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TCC.2021.3115959
Show More Cited By

Index Terms

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

Recommendations

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

In this paper we study the performance of a family of cache replacement algorithms. The cache is decomposed into lists. Items enter the cache via the first list. An item enters the cache via the first list and jumps to the next list whenever a hit on it ...
Transient and steady-state regime of a family of list-based cache replacement algorithms

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 ...
Proxy Cache Replacement Algorithms: A History-Based Approach

Accesing and circulation of Web objects has been facilitated by the design and implementation of effective caching schemes. Web caching has been integrated in prototype and commercial Web-based information systems in order to reduce the overall ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMETRICS '15: Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems

June 2015

488 pages

ISBN:9781450334860

DOI:10.1145/2745844

General Chairs:
Bill Lin
University of California, San Diego
,
Jun (Jim) Xu
Georgia Tech
,
Program Chairs:
Sudipta Sengupta
Microsoft Research
,
Devavrat Shah
Massachusetts Institute of Technology

ACM SIGMETRICS Performance Evaluation Review Volume 43, Issue 1
Performance evaluation review
June 2015
468 pages
ISSN:0163-5999
DOI:10.1145/2796314
Editors:
Derek Eager
University of Saskatchewan
,
Carey Williamson
University of Calgary
Issue’s Table of Contents

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

EU

Conference

SIGMETRICS '15

Sponsor:

SIGMETRICS

SIGMETRICS '15: ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

June 15 - 19, 2015

Oregon, Portland, USA

Acceptance Rates

SIGMETRICS '15 Paper Acceptance Rate 32 of 239 submissions, 13%;

Overall Acceptance Rate 459 of 2,691 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

58
Total Citations
View Citations
364
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gao YCasale GSinghal R(2024)Performance Modeling of Distributed Data Processing in Microservice ApplicationsACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/36872659:4(1-30)Online publication date: 20-Aug-2024
https://dl.acm.org/doi/10.1145/3687265
Wang PJiang HLiu YZhao ZZhou KHuang Z(2024)Beyond Belady to Attain a Seemingly Unattainable Byte Miss Ratio for Content Delivery NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.345209635:11(1949-1963)Online publication date: Nov-2024
https://doi.org/10.1109/TPDS.2024.3452096
Carlsson NEager D(2023)Optimized Dynamic Cache Instantiation and Accurate LRU Approximations Under Time-Varying Request VolumeIEEE Transactions on Cloud Computing10.1109/TCC.2021.311595911:1(779-797)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TCC.2021.3115959
Incerto EPizziol RTribastone M(2023)μOpt: An Efficient Optimal Autoscaler for Microservice Applications2023 IEEE International Conference on Autonomic Computing and Self-Organizing Systems (ACSOS)10.1109/ACSOS58161.2023.00024(67-76)Online publication date: 25-Sep-2023
https://doi.org/10.1109/ACSOS58161.2023.00024
Srivastava SSingh P(2022)Proof of Optimality based on Greedy Algorithm for Offline Cache Replacement AlgorithmInternational Journal of Next-Generation Computing10.47164/ijngc.v13i3.609Online publication date: 31-Oct-2022
https://doi.org/10.47164/ijngc.v13i3.609
Allmeier SGast N(2022)Mean Field and Refined Mean Field Approximations for Heterogeneous SystemsACM SIGMETRICS Performance Evaluation Review10.1145/3547353.352265350:1(103-104)Online publication date: 7-Jul-2022
https://dl.acm.org/doi/10.1145/3547353.3522653
Randone FBortolussi LTribastone M(2022)Refining Mean-field Approximations by Dynamic State TruncationACM SIGMETRICS Performance Evaluation Review10.1145/3543516.346009949:1(31-32)Online publication date: 7-Jun-2022
https://dl.acm.org/doi/10.1145/3543516.3460099
Allmeier SGast N(2022)rmf tool - A library to Compute (Refined) Mean Field Approximation(s)ACM SIGMETRICS Performance Evaluation Review10.1145/3543146.354315649:4(35-40)Online publication date: 6-Jun-2022
https://dl.acm.org/doi/10.1145/3543146.3543156
Allmeier SGast N(2022)Mean Field and Refined Mean Field Approximations for Heterogeneous SystemsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35080336:1(1-43)Online publication date: 28-Feb-2022
https://dl.acm.org/doi/10.1145/3508033
Allmeier SGast NManjunath DNair JCarlsson NCohen ERobert P(2022)Mean Field and Refined Mean Field Approximations for Heterogeneous SystemsAbstract Proceedings of the 2022 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems10.1145/3489048.3522653(103-104)Online publication date: 6-Jun-2022
https://dl.acm.org/doi/10.1145/3489048.3522653
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents