Scope and Accuracy of Analytic and Approximate Results for FIFO, Clock-Based and LRU Caching Performance

Gerhard Hasslinger (), Konstantinos Ntougias, Frank Hasslinger and Oliver Hohlfeld
Additional contact information
Gerhard Hasslinger: Deutsche Telekom, 64289 Darmstadt, Germany
Konstantinos Ntougias: Department of Electrical and Computer Engineering, University of Cyprus, Nicosia 22006, Cyprus
Frank Hasslinger: Department of Computer Science, Darmstadt University of Technology, 64289 Darmstadt, Germany
Oliver Hohlfeld: Distributed Systems Group, University of Kassel, 34127 Kassel, Germany

Future Internet, 2023, vol. 15, issue 3, 1-17

Abstract: We evaluate analysis results and approximations for the performance of basic caching methods, assuming independent requests. Compared with simulative evaluations, the analysis results are accurate, but their computation is tractable only within a limited scope. We compare the scalability of analytical FIFO and LRU solutions including extensions for multisegment caches and for caches with data of varying sizes. On the other hand, approximations have been proposed for the FIFO and LRU hit ratio. They are simple and scalable, but their accuracy is confirmed mainly through asymptotic behaviour only for large caches. We derive bounds on the approximation errors in a detailed worst-case study with a focus on small caches. The approximations are extended to data of different sizes. Then a fraction of unused cache space can add to the deviations, which is estimated in order to improve the solution.

Keywords: FIFO; RANDOM; LRU; LFU; clock-based and multisegment caches; Markov analysis; hit ratio approximations; deviation bounds; variable data size (search for similar items in EconPapers)
JEL-codes: O3 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/1999-5903/15/3/91/pdf (application/pdf)
https://www.mdpi.com/1999-5903/15/3/91/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jftint:v:15:y:2023:i:3:p:91-:d:1079669

Access Statistics for this article

Future Internet is currently edited by Ms. Grace You

More articles in Future Internet from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().