More Web Proxy on the site http://driver.im/

research-article

Access-Time-Aware Cache Algorithms

Authors:

Giovanni Neglia,

Vaishnav Janardhan,

Pietro Michiardi,

Dimitra TsigkariAuthors Info & Claims

ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS), Volume 2, Issue 4

Article No.: 21, Pages 1 - 29

https://doi.org/10.1145/3149001

Published: 21 November 2017 Publication History

Abstract

Most of the caching algorithms are oblivious to requests’ timescale, but caching systems are capacity constrained and, in practical cases, the hit rate may be limited by the cache’s impossibility to serve requests fast enough. In particular, the hard-disk access time can be the key factor capping cache performance. In this article, we present a new cache replacement policy that takes advantage of a hierarchical caching architecture, and in particular of access-time difference between memory and disk. Our policy is optimal when requests follow the independent reference model and significantly reduces the hard-disk load, as shown also by our realistic, trace-driven evaluation. Moreover, we show that our policy can be considered in a more general context, since it can be easily adapted to minimize any retrieval cost, as far as costs add over cache misses.

References

[1]

Marc Abrams, Charles R. Standridge, Ghaleb Abdulla, Stephen Williams, and Edward A. Fox. 1995. Caching proxies: Limitations and potentials. In Proceedings of the 4th International World Wide Web Conference (WWW’95).

[2]

Andrea Araldo, Dario Rossi, and Fabio Martignon. 2016. Cost-aware caching: Caching more (costly items) for less (ISPs operational expenditures). IEEE Transactions on Parallel and Distributed Systems 27, 5 (May 2016), 1316--1330.

Digital Library

[3]

Rakesh Barve, Elizabeth Shriver, Phillip B. Gibbons, Bruce K. Hillyer, Yossi Matias, and Jeffrey Scott Vitter. 1999. Modeling and optimizing I/O throughput of multiple disks on a bus. In Proceedings of the 1999 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS’99). ACM, New York, 83--92.

Digital Library

[4]

Daniel S. Berger, Ramesh K. Sitaraman, and Mor Harchol-Balter. 2017. AdaptSize: Orchestrating the hot object memory cache in a content delivery network. In Proceedings of the 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI’17).

Digital Library

[5]

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

Digital Library

[6]

Niv Buchbinder and Joseph Naor. 2005. Online Primal-Dual Algorithms for Covering and Packing Problems. Springer, Berlin, 689--701.

Digital Library

[7]

Pei Cao and Sandy Irani. 1997. Cost-aware WWW proxy caching algorithms. In Proceedings of the USENIX Symposium on Internet Technologies and Systems on USENIX Symposium on Internet Technologies and Systems (USITS’97). USENIX Association, Berkeley, CA, 18.

Digital Library

[8]

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

Digital Library

[9]

Edward Grady Coffman and Peter J. Denning. 1973. Operating Systems Theory. Prentice-Hall, Englewood Cliffs, NJ. http://opac.inria.fr/record=b1079172

Digital Library

[10]

Mostafa Dehghan, Laurent Massoulié, Don Towsley, Dan Menasche, and Y. C. Tay. 2016. A utility optimization approach to network cache design. In The 35th Annual IEEE International Conference on Computer Communications (IEEE INFOCOM’16). 1--9.

[11]

Ronald Fagin. 1977. Asymptotic miss ratios over independent references. Journal of Computer and System Sciences 14, 2 (1977), 222--250.

[12]

Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, and Neal E. Young. 1991. Competitive paging algorithms. Journal of Algorithms 12 (1991), 685--699.

Digital Library

[13]

Nicaise Choungmo Fofack, Philippe Nain, Giovanni Neglia, and Don Towsley. 2014. Performance evaluation of hierarchical TTL-based cache networks. Computer Networks 65 (2014), 212--231.

[14]

Christine Fricker, Philippe Robert, and James Roberts. 2012a. A versatile and accurate approximation for LRU cache performance. In Proceedings of the 24th International Teletraffic Congress (ITC’12). International Teletraffic Congress, Article 8, 8 pages.

Digital Library

[15]

Christing Fricker, Philippe Robert, Jim Roberts, and Nada Sbihi. 2012b. Impact of traffic mix on caching performance in a content-centric network. In Proceedings of the 31th IEEE International Conference on Computer Communications (INFOCOM’12).

[16]

Michele Garetto, Emilio Leonardi, and Valentina Martina. 2016. A unified approach to the performance analysis of caching systems. ACM Transactions on Modeling and Performance Evaluation of Computing Systems 1, 3, Article 12 (May 2016), 28 pages.

Digital Library

[17]

Predrag R. Jelenkovic and Ana Radovanovic. 2004. Optimizing LRU caching for variable document sizes. Combinatorics, Probability, and Computing 13, 4--5 (July 2004), 627--643.

Digital Library

[18]

Hans Kellerer, Ulrich Pferschy, and David Pisinger. 2004. Knapsack Problems. Springer, Berlin. I--XX, 1--546 pages.

[19]

Mathieu Leconte, Georgios Paschos, Lazaros Gkatzikis, Moez Draief, Spyridon Vassilaras, and Symeon Chouvardas. 2016. Placing dynamic content in caches with small population. In Proceedings of the 35th IEEE International Conference on Computer Communications (INFOCOM’16).

[20]

Suoheng Li, Jie Xu, Mihaela van der Schaar, and Weiping Li. 2016. Popularity-driven content caching. In Proceedings of the 35th IEEE International Conference on Computer Communications (INFOCOM’16).

[21]

Bruce M. Maggs and Ramesh K. Sitaraman. 2015. Algorithmic nuggets in content delivery. SIGCOMM Computer Communication Review 45, 3 (July 2015), 52--66.

Digital Library

[22]

Valentina Martina, Michele Garetto, and Emilio Leonardi. 2014. A unified approach to the performance analysis of caching systems. In IEEE Conference on Computer Communications (IEEE INFOCOM’14). 2040--2048.

[23]

Giovanni Neglia, Damiano Carra, Ming Dong Feng, Vaishnav Janardhan, Pietro Michiardi, and Dimitra Tsigkari. 2016. Access-time aware cache algorithms. In Proceedings of the 28th International Teletraffic Congress (ITC’16).

[24]

Giovanni Neglia, Damiano Carra, and Pietro Michiardi. 2017. Cache policies for linear utility maximization. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM’17).

[25]

Spencer W. Ng. 1998. Advances in disk technology: Performance issues. IEEE Computer 31 (1998), 75--81.

Digital Library

[26]

Erik Nygren, Ramesh K. Sitaraman, and Jennifer Sun. 2010. The Akamai network: A platform for high-performance internet applications. SIGOPS Operating System Reviews 44, 3 (Aug. 2010), 2--19.

Digital Library

[27]

Valentino Pacifici and Gyorgy Dán. 2016. Coordinated selfish distributed caching for peering content-centric networks. IEEE/ACM Transactions on Networking 24, 6 (2016), 3690--3701.

Digital Library

[28]

Giuseppe Rossini, Davide Rossi, Michele Garetto, and Emilio Leonardi. 2014. Multi-Terabyte and multi-Gbps information centric routers. In Proceedings of the 33th IEEE International Conference on Computer Communications (INFOCOM’14).

[29]

M. Zubair Shafiq, Amir R. Khakpour, and Alex X. Liu. 2016. Characterizing caching workload of a large commercial content delivery network. In The 35th Annual IEEE International Conference on Computer Communications (IEEE INFOCOM’16). IEEE, 1--9.

[30]

Samta Shukla and Alhussein A. Abouzeid. 2016. On designing optimal memory damage aware caching policies for content-centric networks. In 14th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt’16). 163--170.

[31]

David Starobinski and David Tse. 2001. Probabilistic methods for web caching. Performance Evaluation 46, 2--3 (2001), 125--137.

Digital Library

[32]

Brian S. Thomson, Judith B. Bruckner, and Andrew M. Bruckner. 2001. Elementary Real Analysis. Prentice-Hall.

[33]

Stefano Traverso, Mohamed Ahmed, Michele Garetto, Paolo Giaccone, Emilio Leonardi, and Saverio Niccolini. 2013. Temporal locality in today’s content caching: Why it matters and how to model it. SIGCOMM Computer Communication Review 43, 5 (Nov. 2013), 5--12.

Digital Library

[34]

Neal E. Young. 2008. Online paging and caching. In Encyclopedia of Algorithms. Springer US, Boston, 601--604.

Cited By

Faticanti FNeglia G(2024)Optimistic online caching for batched requestsComputer Networks10.1016/j.comnet.2024.110341244(110341)Online publication date: May-2024
https://doi.org/10.1016/j.comnet.2024.110341
Si Salem TNeglia GIoannidis S(2023)No-regret Caching via Online Mirror DescentACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/36052098:4(1-32)Online publication date: 11-Aug-2023
https://dl.acm.org/doi/10.1145/3605209
Einziger GHimelbrand OWaisbard E(2023)Boosting Cache Performance by Access Time MeasurementsACM Transactions on Storage10.1145/357277819:1(1-29)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3572778
Show More Cited By

Index Terms

Access-Time-Aware Cache Algorithms
1. Networks
  1. Network performance evaluation
    1. Network performance analysis
2. Theory of computation
  1. Design and analysis of algorithms
    1. Online algorithms
      1. Caching and paging algorithms

Recommendations

Size-Aware Cache Management for Compressed Cache Architectures
A practical way to increase the effective capacity of a microprocessor's cache, without physically increasing the cache size, is to employ data compression. Last-Level Caches (LLC) are particularly amenable to such compression schemes, since the primary ...
Distance-aware L2 cache organizations for scalable multiprocessor systems
Special issue: Reconfigurable embedded systems: Synthesis, design and application

In order to provide the scalability to the multiprocessor systems, it is important to keep the remote memory access time in bounds so that it does not impose much additional overhead as the system grows.In this paper, we suggest an LRU/distance-aware ...
Adaptive Cache Bypassing for Inclusive Last Level Caches
IPDPS '13: Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing

Cache hierarchy designs, including bypassing, replacement, and the inclusion property, have significant performance impact. Recent works on high performance caches have shown that cache bypassing is an effective technique to enhance the last level cache ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Performance Evaluation of Computing Systems

ACM Transactions on Modeling and Performance Evaluation of Computing Systems Volume 2, Issue 4

December 2017

145 pages

ISSN:2376-3639

EISSN:2376-3647

DOI:10.1145/3133236

Editors:
Sem Borst
Nokia Bell Labs / Eindhoven University of Technology, Netherlands
,
Carey Williamson
University of Calgary, Canada

Issue’s Table of Contents

Copyright © 2017 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: 21 November 2017

Accepted: 01 July 2017

Revised: 01 June 2017

Received: 01 August 2016

Published in TOMPECS Volume 2, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Italian National Group for Scientific Computation (GNCS-INDAM)
Bodossaki Foundation, Greece

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
366
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)2

Reflects downloads up to 23 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Faticanti FNeglia G(2024)Optimistic online caching for batched requestsComputer Networks10.1016/j.comnet.2024.110341244(110341)Online publication date: May-2024
https://doi.org/10.1016/j.comnet.2024.110341
Si Salem TNeglia GIoannidis S(2023)No-regret Caching via Online Mirror DescentACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/36052098:4(1-32)Online publication date: 11-Aug-2023
https://dl.acm.org/doi/10.1145/3605209
Einziger GHimelbrand OWaisbard E(2023)Boosting Cache Performance by Access Time MeasurementsACM Transactions on Storage10.1145/357277819:1(1-29)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3572778
Mazziane YFaticanti FNeglia GAlouf S(2023)No- Regret Caching with Noisy Request Estimates2023 IEEE Virtual Conference on Communications (VCC)10.1109/VCC60689.2023.10474978(341-346)Online publication date: 28-Nov-2023
https://doi.org/10.1109/VCC60689.2023.10474978
Elsayed KRizk A(2023)Time-to-Live Caching With Network Delays: Exact Analysis and Computable ApproximationsIEEE/ACM Transactions on Networking10.1109/TNET.2022.320791431:3(1087-1100)Online publication date: Jun-2023
https://doi.org/10.1109/TNET.2022.3207914
Faticanti FNeglia G(2023)Optimistic Online Caching for Batched RequestsICC 2023 - IEEE International Conference on Communications10.1109/ICC45041.2023.10278692(6243-6248)Online publication date: 28-May-2023
https://doi.org/10.1109/ICC45041.2023.10278692
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
Einziger GEytan OFriedman RManes B(2022)Lightweight Robust Size Aware Cache ManagementACM Transactions on Storage10.1145/350792018:3(1-23)Online publication date: 24-Aug-2022
https://dl.acm.org/doi/10.1145/3507920
Ahani GYuan DSun S(2022)Optimal Scheduling of Age-Centric Caching: Tractability and ComputationIEEE Transactions on Mobile Computing10.1109/TMC.2020.304510421:8(2939-2954)Online publication date: 1-Aug-2022
https://doi.org/10.1109/TMC.2020.3045104
Ricardo GTuholukova ANeglia GSpyropoulos T(2021)Caching Policies for Delay Minimization in Small Cell Networks With Coordinated Multi-Point Joint TransmissionsIEEE/ACM Transactions on Networking10.1109/TNET.2021.306226929:3(1105-1115)Online publication date: Jun-2021
https://doi.org/10.1109/TNET.2021.3062269
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents