{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T19:08:43Z","timestamp":1768676923807,"version":"3.49.0"},"reference-count":41,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2023,2,24]],"date-time":"2023-02-24T00:00:00Z","timestamp":1677196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Future Internet"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/fi15030091","type":"journal-article","created":{"date-parts":[[2023,2,27]],"date-time":"2023-02-27T04:13:16Z","timestamp":1677471196000},"page":"91","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Scope and Accuracy of Analytic and Approximate Results for FIFO, Clock-Based and LRU Caching Performance"],"prefix":"10.3390","volume":"15","author":[{"given":"Gerhard","family":"Hasslinger","sequence":"first","affiliation":[{"name":"Deutsche Telekom, 64289 Darmstadt, Germany"}]},{"given":"Konstantinos","family":"Ntougias","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Cyprus, Nicosia 22006, Cyprus"}]},{"given":"Frank","family":"Hasslinger","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Darmstadt University of Technology, 64289 Darmstadt, Germany"}]},{"given":"Oliver","family":"Hohlfeld","sequence":"additional","affiliation":[{"name":"Distributed Systems Group, University of Kassel, 34127 Kassel, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2023,2,24]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1145\/954339.954341","article-title":"A survey of web cache replacement strategies","volume":"35","author":"Podlipnik","year":"2003","journal-title":"ACM Comput. Surv."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1109\/90.649565","article-title":"Internet web servers: Workload characterization and performance implications","volume":"5","author":"Arlitt","year":"1997","journal-title":"IEEE Trans. Netw."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Li, S., Xu, J., van der Schaar, M., and Li, W. (2016, January 10\u201314). Popularity-driven content caching. Proceedings of the IEEE Infocom, San Francisco, CA, USA.","DOI":"10.1109\/INFOCOM.2016.7524381"},{"key":"ref_4","first-page":"1111","article-title":"The role of caching in future communication systems and networks","volume":"36","author":"Paschos","year":"2018","journal-title":"IEEE JSAC"},{"key":"ref_5","unstructured":"Corbato, F.J. (1968). A paging experiment with the Multics system. MIT Proj. MAC Rep. MAC-M-384, 1\u201314."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1109\/TC.1973.5009115","article-title":"A unified approach to the evaluation of a class of replacement algorithms","volume":"100","author":"Gelenbe","year":"1973","journal-title":"IEEE Trans. on Comp."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1287\/opre.13.4.609","article-title":"On serial files with relocatable records","volume":"13","author":"McCabe","year":"1965","journal-title":"Oper. Res."},{"key":"ref_8","unstructured":"King, W.F. (1971, January 23\u201328). Analysis of demand paging algorithms. Proceedings of the IFIP Congress, Ljubljana, Yugoslavia."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1352","DOI":"10.1109\/TC.2001.970573","article-title":"LRFU: A spectrum of policies that subsumes the least recently used and least frequently used policies","volume":"50","author":"Lee","year":"2001","journal-title":"IEEE Trans. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1109\/TNET.2019.2913677","article-title":"A Utility optimization approach to network cache design","volume":"27","author":"Dehghan","year":"2019","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/j.comnet.2017.04.044","article-title":"Performance evaluation for new web caching strategies combining LRU with score-based selection","volume":"125","author":"Hasslinger","year":"2017","journal-title":"Comput. Netw."},{"key":"ref_12","first-page":"1314","article-title":"Accurate learning or fast mixing? Dynamic adaptability of caching algorithms","volume":"36","author":"Li","year":"2018","journal-title":"IEEE JSAC"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1561\/0100000104","article-title":"Cache optimization models and algorithms","volume":"16","author":"Paschos","year":"2020","journal-title":"Found. Trends Commun. Inf. Theory"},{"key":"ref_14","unstructured":"Eytan, O., Harnik, D., Ofer, E., Friedman, R., and Kat, R. (2020, January 13\u201314). It\u2019s time to revisit LRU vs. FIFO. Proceedings of the 12th USENIX HotStorage Workshop, Berkeley, CA, USA."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Hasslinger, G., Ntougias, K., Hasslinger, F., and Hohlfeld, O. (2019, January 11\u201313). Fast and efficient web caching methods regarding the properties per data. Proceedings of the IEEE CAMAD, Limassol, Cyprus.","DOI":"10.1109\/CAMAD.2019.8858459"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3468521","article-title":"A large-scale analysis of key-value cache clusters at Twitter","volume":"17","author":"Yang","year":"2021","journal-title":"ACM Trans. Storage"},{"key":"ref_17","unstructured":"ElAarag, H. (2013). Web Proxy Cache Strategies: Simulation, Implementation and Performance Evaluation, Springer Publisher."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1109\/MC.2004.1297303","article-title":"Outperforming LRU with an adaptive replacement cache algorithm","volume":"37","author":"Megiddo","year":"2004","journal-title":"IEEE Comput."},{"key":"ref_19","first-page":"49","article-title":"Coordinated caching and QoS-aware resource allocation for spectrum sharing","volume":"112","author":"Ntougias","year":"2020","journal-title":"Wirel. Pers. Comm."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Gast, N., and Van Houdt, B. (2015, January 15\u201319). Transient and steady-state regime of a family of list-based cache replacement algorithms. Proceedings of the ACM Sigmetrics, Portland, OR, USA.","DOI":"10.1145\/2745844.2745850"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Hasslinger, G., Ntougias, K., Hasslinger, F., and Hohlfeld, O. (2022, January 19). Analysis of the LRU cache startup phase and convergence time and error bounds on approximations by Fagin and Che. Proceedings of the WiOpt Symposium, CCDWN workshop, Turin, Italy.","DOI":"10.23919\/WiOpt56218.2022.9930556"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Wong, K.Y., Yeung, A., Choi, K.C., Lei, P., and Lam, C.T. (2021, January 22\u201325). Exact transient analysis on LRU cache startup for IoT. Proceedings of the 9th International Conference on Information Technology: IoT and Smart City, New York, NY, USA.","DOI":"10.1145\/3512576.3512632"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/S0022-0000(77)80014-7","article-title":"Asymptotic miss ratios over independent references","volume":"14","author":"Fagin","year":"1977","journal-title":"J. Comp. Syst. Sci."},{"key":"ref_24","first-page":"1305","article-title":"Hierarchical web caching systems: Modeling, and experimental design","volume":"20","author":"Che","year":"2002","journal-title":"IEEE JSAC"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Dan, A., and Towsley, D. (1990, January 22\u201325). An approximate analysis of the LRU and FIFO buffer replacement schemes. Proceedings of the ACM SIGMETRICS, Boulder, CO, USA.","DOI":"10.1145\/98457.98525"},{"key":"ref_26","unstructured":"Berthet, C. (2017). Approximation of LRU caches miss rate: Application to power-law popularities. arXiv."},{"key":"ref_27","unstructured":"Brenner, M. (2020). A Lyapunov analysis of LRU. [Master Thesis, University of Illinois Urbana-Champaign]."},{"key":"ref_28","unstructured":"Fricker, C., Robert, P., and Roberts, J. (2012, January 4\u20137). A versatile, accurate approximation for LRU cache performance. Proceedings of the ITC 24, Krakow, Poland."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Poojary, P., Moharir, S., and Jagannathan, K. (2021, January 18\u201321). A coupon collector based approximation for LRU cache hits for Zipf requests. Proceedings of the 19th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt), Philadelphia, PA, USA.","DOI":"10.23919\/WiOpt52861.2021.9589882"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1137\/0207025","article-title":"Efficient calculation of expected miss ratios in the independent reference model","volume":"7","author":"Fagin","year":"1978","journal-title":"SIAM J. Comput."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Breslau, L., Cao, P., Fan, L., Phillips, G., and Shenker, S. (1999, January 21\u201325). Web caching and Zipf-like distributions: Evidence and implications. Proceedings of the IEEE Infocom, New York, NY, USA.","DOI":"10.1109\/INFCOM.1999.749260"},{"key":"ref_32","first-page":"1839","article-title":"Unraveling the impact of temporal and geographical locality in caching systems","volume":"17","author":"Traverso","year":"2015","journal-title":"IEEE Trans."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Hasslinger, G., Kunbaz, M., Hasslinger, F., and Bauschert, T. (2017, January 15\u201319). Web caching evaluation for Wikipedia request statistics. Proceedings of the IEEE WiOpt Symposium, Paris, France.","DOI":"10.23919\/WIOPT.2017.7959873"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Rosensweig, E.J., Menasche, D.S., and Kruose, J. (2013, January 14\u201319). On the steady-state of cache networks. Proceedings of the IEEE Infocom, Turin, Italy.","DOI":"10.1109\/INFCOM.2013.6566874"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3155335","article-title":"A product-form model for the performance evaluation of a bandwidth allocation strategy in WSN","volume":"28","author":"Marin","year":"2018","journal-title":"ACM TOMACS"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/j.peva.2012.05.008","article-title":"Fluid limit analysis of FIFO and RR caching for IRM","volume":"69","author":"Tsukada","year":"2012","journal-title":"Perform. Eval."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2896380","article-title":"A unified approach to the performance analysis of caching systems","volume":"1","author":"Garetto","year":"2016","journal-title":"ACM Trans. Model. Perform. Eval. Comput. Syst."},{"key":"ref_38","unstructured":"Gast, N., and Van Houdt, B. (2017). Performance Evaluation, Elsevier."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"1472","DOI":"10.1109\/TNET.2012.2227338","article-title":"Estimating instantaneous cache hit ratio using Markov chain analysis","volume":"21","author":"Gomaa","year":"2013","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"239","DOI":"10.2307\/3214811","article-title":"LRU is better than FIFO under the independent reference model","volume":"29","author":"Gandolf","year":"1992","journal-title":"J. Appl. Probab."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0166-5316(01)00045-1","article-title":"Probabilistic methods for web caching","volume":"46","author":"Starobinsky","year":"2001","journal-title":"Perf. Eval."}],"container-title":["Future Internet"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-5903\/15\/3\/91\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:41:55Z","timestamp":1760121715000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-5903\/15\/3\/91"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,24]]},"references-count":41,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,3]]}},"alternative-id":["fi15030091"],"URL":"https:\/\/doi.org\/10.3390\/fi15030091","relation":{},"ISSN":["1999-5903"],"issn-type":[{"value":"1999-5903","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,24]]}}}