research-article

Public Access

Optimizing TTL Caches under Heavy-Tailed Demands

Authors:

Andrés Ferragut,

Ismael Rodriguez,

Fernando PaganiniAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 44, Issue 1

Pages 101 - 112

https://doi.org/10.1145/2964791.2901459

Published: 14 June 2016 Publication History

Abstract

In this paper we analyze the hit performance of cache systems that receive file requests with general arrival distributions and different popularities. We consider timer-based (TTL) policies, with differentiated timers over which we optimize. The optimal policy is shown to be related to the monotonicity of the hazard rate function of the inter-arrival distribution. In particular for decreasing hazard rates, timer policies outperform the static policy of caching the most popular contents. We provide explicit solutions for the optimal policy in the case of Pareto-distributed inter-request times and a Zipf distribution of file popularities, including a compact fluid characterization in the limit of a large number of files. We compare it through simulation with classical policies, such as least-recently-used and discuss its performance. Finally, we analyze extensions of the optimization framework to a line network of caches.

References

[1]

B. Ahlgren, C. Dannewitz, C. Imbrenda, D. Kutscher, and B. Ohlman. A survey of information-centric networking. IEEE Communications Magazine, 50(7):26--36, 2012.

[2]

F. Baccelli and P. Brémaud. Elements of Queueing Theory. Springer-Verlag, Berlin, 2013.

[3]

O. Bahat and A. M. Makowski. Measuring consistency in TTL-based caches. Performance Evaluation, 62(1):439--455, 2005.

Digital Library

[4]

J. Barrera and J. Fontbona. The limiting move-to-front search-cost in law of large numbers asymptotic regimes. Annals of Applied Probability, 20(2):722--752, 2010.

[5]

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

[6]

D. S. Berger, S. Henningsen, F. Ciucu, and J. B. Schmitt. Maximizing cache hit ratios by variance reduction. ACM SIGMETRICS Performance Evaluation Review, 43(2):57--59, 2015.

Digital Library

[7]

G. Bianchi, A. Detti, A. Caponi, and N. Blefari Melazzi. Check before storing: What is the performance price of content integrity verification in LRU caching? ACM SIGCOMM Computer Communication Review, 43(3):59--67, 2013.

Digital Library

[8]

S. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.

Digital Library

[9]

L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web caching and zipf-like distributions: Evidence and implications. In Proc. of IEEE/Infocom 1999, pages 126--134.

[10]

H. Che, Y. Tung, and Z. Wang. Hierarchical web caching systems: Modeling, design and experimental results. IEEE Journal on Selected Areas in Communications, 20(7):1305--1314, 2002.

Digital Library

[11]

A. Dan and D. Towsley. An approximate analysis of the LRU and FIFO buffer replacement schemes. In Proc. of ACM/SIGMETRICS 1990, pages 143--152.

Digital Library

[12]

M. Dehghan, L. Massoulie, D. Towsley, D. Menasche, and Y. C. Tay. A utility optimization approach to network cache design. In Proc. of IEEE/Infocom 2016, page to appear.

[13]

A. Ferragut, I. Rodríguez, and F. Paganini. Optimizing TTL caches under heavy-tailed demands (extended version). Available at http://fi.ort.edu.uy/2243/17/publications.html.

Digital Library

[14]

J. A. Fill. Limits and rates of convergence for the distribution of search cost under the move-to-front rule. Theoretical Computer Science, 164(1):185--206, 1996.

Digital Library

[15]

N. C. Fofack, P. Nain, G. Neglia, and D. Towsley. Analysis of TTL-based cache networks. In Proc. of Intl. Conf on Performance Evaluation Methodologies and Tools (VALUETOOLS), pages 1--10, 2012.

[16]

N. C. Fofack, P. Nain, G. Neglia, and D. Towsley. Performance evaluation of hierarchical TTL-based cache networks. Computer Networks, 65:212--231, 2014.

[17]

C. Fricker, P. Robert, and J. Roberts. A versatile and accurate approximation for LRU cache performance. In Proc. of the 24th International Teletraffic Congress, pages 57--64, 2012.

Digital Library

[18]

N. Gast and B. V. Houdt. Transient and steady-state regime of a family of list-based cache replacement algorithms. In Proc. of ACM/SIGMETRICS 2015, pages 123--136.

Digital Library

[19]

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

Digital Library

[20]

M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming, version 2.1. http://cvxr.com/cvx, Mar. 2014.

[21]

V. Jacobson, D. K. Smetters, J. D. Thornton, M. F. Plass, N. H. Briggs, and R. L. Braynard. Networking named content. In Proc. of the ACM/Conext, pages 1--12, 2009.

Digital Library

[22]

P. Jelenković and A. Radovanović. Asymptotic insensitivity of least-recently-used caching to statistical dependency. In Proc. of IEEE/Infocom 2003, pages 438--447.

[23]

P. R. Jelenković. Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities. Annals of Applied Probability, 9(2):430--464, 1999.

[24]

P. R. Jelenković and A. Radovanović. Least-recently-used caching with dependent requests. Theoretical computer science, 326(1):293--327, 2004.

Digital Library

[25]

P. R. Jelenković and A. Radovanović. The persistent-access-caching algorithm. Random Structures & Algorithms, 33(2):219--251, 2008.

Digital Library

[26]

P. R. Jelenković, A. Radovanović, and M. S. Squillante. Critical sizing of LRU caches with dependent requests. Journal of Applied Probability, 43(4):1013--1027, 2006.

[27]

J. Jung, A. W. Berger, and H. Balakrishnan. Modeling TTL-based internet caches. In Proc. of IEEE/Infocom 2003, pages 417--426.

[28]

W. King. Analysis of paging algorithms. In Proc. of IFIP Congress 1971, pages 485--490.

[29]

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

[30]

E. J. Rosensweig, J. Kurose, and D. Towsley. Approximate models for general cache networks. In Proc. of IEEE/Infocom 2010, pages 1--9.

Digital Library

Cited By

Elsayed KGeyer FRizk A(2024)Utility-Driven Optimization of TTL Cache Hierarchies Under Network Delays2024 IFIP Networking Conference (IFIP Networking)10.23919/IFIPNetworking62109.2024.10619843(249-257)Online publication date: 3-Jun-2024
https://doi.org/10.23919/IFIPNetworking62109.2024.10619843
Torabi HKhazaei HLitoiu MBalsamo SKnottenbelt WAbad CShang W(2024)A Learning-Based Caching Mechanism for Edge Content DeliveryProceedings of the 15th ACM/SPEC International Conference on Performance Engineering10.1145/3629526.3645037(236-246)Online publication date: 7-May-2024
https://dl.acm.org/doi/10.1145/3629526.3645037
Basu Roy RPatel TGarg RTiwari DTsafrir DMUSUVATHI MGupta RAbu-Ghazaleh N(2024)CodeCrunch: Improving Serverless Performance via Function Compression and Cost-Aware Warmup Location OptimizationProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 110.1145/3617232.3624866(85-101)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3617232.3624866
Show More Cited By

Index Terms

Optimizing TTL Caches under Heavy-Tailed Demands
1. Networks
  1. Network performance evaluation
    1. Network performance modeling
2. Theory of computation
  1. Design and analysis of algorithms
    1. Online algorithms
      1. Caching and paging algorithms

Recommendations

Optimizing TTL Caches under Heavy-Tailed Demands
SIGMETRICS '16: Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science

In this paper we analyze the hit performance of cache systems that receive file requests with general arrival distributions and different popularities. We consider timer-based (TTL) policies, with differentiated timers over which we optimize. The ...
False Sharing and Spatial Locality in Multiprocessor Caches

The performance of the data cache in shared-memory multiprocessors has been shown to be different from that in uniprocessors. In particular, cache miss rates in multiprocessors do not show the sharp drop typical of uniprocessors when the size of the ...
Performance aspects of distributed caches using, TTL-based consistency
Automata, languages and programming

The web is the largest distributed database deploying time-to-live-based weak consistency. Each object has a lifetime-duration assigned to it by its origin server. A copy of the object fetched from its origin server is received with maximum time-to-live ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 44, Issue 1

Performance evaluation review

June 2016

409 pages

ISSN:0163-5999

DOI:10.1145/2964791

Editors:
Derek Eager
University of Saskatchewan
,
Carey Williamson
University of Calgary

Issue’s Table of Contents

SIGMETRICS '16: Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science
June 2016
434 pages
ISBN:9781450342667
DOI:10.1145/2896377
General Chairs:
Sara Alouf
Inria, France
,
Alain Jean-Marie
Inria, France
,
Program Chairs:
Nidhi Hegde
Bell Labs, France
,
Alexandre Proutière
KTH, Sweden

Copyright © 2016 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 ACM 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2016

Published in SIGMETRICS Volume 44, Issue 1

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Air Force Office of Scientific Research

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
638
Total Downloads

Downloads (Last 12 months)160
Downloads (Last 6 weeks)29

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Elsayed KGeyer FRizk A(2024)Utility-Driven Optimization of TTL Cache Hierarchies Under Network Delays2024 IFIP Networking Conference (IFIP Networking)10.23919/IFIPNetworking62109.2024.10619843(249-257)Online publication date: 3-Jun-2024
https://doi.org/10.23919/IFIPNetworking62109.2024.10619843
Torabi HKhazaei HLitoiu MBalsamo SKnottenbelt WAbad CShang W(2024)A Learning-Based Caching Mechanism for Edge Content DeliveryProceedings of the 15th ACM/SPEC International Conference on Performance Engineering10.1145/3629526.3645037(236-246)Online publication date: 7-May-2024
https://dl.acm.org/doi/10.1145/3629526.3645037
Basu Roy RPatel TGarg RTiwari DTsafrir DMUSUVATHI MGupta RAbu-Ghazaleh N(2024)CodeCrunch: Improving Serverless Performance via Function Compression and Cost-Aware Warmup Location OptimizationProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 110.1145/3617232.3624866(85-101)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3617232.3624866
Quan GEryilmaz AShroff N(2024)Optimal Edge Caching for Individualized Demand DynamicsIEEE/ACM Transactions on Networking10.1109/TNET.2024.336961132:4(2826-2841)Online publication date: Aug-2024
https://doi.org/10.1109/TNET.2024.3369611
Ferragut ACarrasco MPaganini F(2024)Caching or Pre-fetching? the Role of Hazard Rates2024 60th Annual Allerton Conference on Communication, Control, and Computing10.1109/Allerton63246.2024.10735277(1-8)Online publication date: 24-Sep-2024
https://doi.org/10.1109/Allerton63246.2024.10735277
Ben Mazziane YAlouf SNeglia GMenasche D(2024)TTL model for an LRU-based similarity caching policyComputer Networks10.1016/j.comnet.2024.110206241(110206)Online publication date: Mar-2024
https://doi.org/10.1016/j.comnet.2024.110206
Xiao HZhang XHu ZZheng MLiang Y(2024)A collaborative cache allocation strategy for performance and link cost in mobile edge computingThe Journal of Supercomputing10.1007/s11227-024-06310-780:15(22885-22912)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s11227-024-06310-7
Narayana SKash IEvans RShpitser I(2023)Keep-alive caching for the hawkes processProceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence10.5555/3625834.3625975(1499-1509)Online publication date: 31-Jul-2023
https://dl.acm.org/doi/10.5555/3625834.3625975
Hasslinger GOkhovatzadeh MNtougias KHasslinger FHohlfeld O(2023)An overview of analysis methods and evaluation results for caching strategiesComputer Networks10.1016/j.comnet.2023.109583228(109583)Online publication date: Jun-2023
https://doi.org/10.1016/j.comnet.2023.109583
Roy RPatel TTiwari DFalsafi BFerdman MLu SWenisch T(2022)IceBreaker: warming serverless functions better with heterogeneityProceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3503222.3507750(753-767)Online publication date: 28-Feb-2022
https://dl.acm.org/doi/10.1145/3503222.3507750
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Issue’s Table of Contents