{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T02:17:34Z","timestamp":1790734654673,"version":"4.1.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,9,7]],"date-time":"2018-09-07T00:00:00Z","timestamp":1536278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CNS-1413998 and CNS-1617437"],"award-info":[{"award-number":["CNS-1413998 and CNS-1617437"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"U.S. ARL and the U.K. MoD","award":["W911NF-16-3-0001"],"award-info":[{"award-number":["W911NF-16-3-0001"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>The modeling and analysis of an LRU cache is extremely challenging as exact results for the main performance metrics (e.g., hit rate) are either lacking or cannot be used because of their high computational complexity for large caches. As a result, various approximations have been proposed. The state-of-the-art method is the so-called TTL approximation, first proposed and shown to be asymptotically exact for IRM requests by Fagin [13]. It has been applied to various other workload models and numerically demonstrated to be accurate but without theoretical justification. In this article, we provide theoretical justification for the approximation in the case where distinct contents are described by independent stationary and ergodic processes. We show that this approximation is exact as the cache size and the number of contents go to infinity. This extends earlier results for the independent reference model. Moreover, we establish results not only for the aggregate cache hit probability but also for every individual content. Last, we obtain bounds on the rate of convergence.<\/jats:p>","DOI":"10.1145\/3239164","type":"journal-article","created":{"date-parts":[[2018,9,7]],"date-time":"2018-09-07T12:51:06Z","timestamp":1536324666000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["On the Convergence of the TTL Approximation for an LRU Cache under Independent Stationary Request Processes"],"prefix":"10.1145","volume":"3","author":[{"given":"Bo","family":"Jiang","sequence":"first","affiliation":[{"name":"University of Massachusetts Amherst, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Philippe","family":"Nain","sequence":"additional","affiliation":[{"name":"Inria, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Don","family":"Towsley","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,9,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Introduction to Analytic Number Theory","author":"Apostol T. M.","unstructured":"T. M. Apostol. 1976. Introduction to Analytic Number Theory. Springer-Verlag."},{"key":"e_1_2_1_2_1","unstructured":"B. Baccelli and P. Br\u00e9maud. 2003. Elements of Queueing Theory: Palm Martingale Calculus and Stochastic Recurrences (2nd ed.). Applications of Mathematics Stochastic Modelling and Applied Probability Vol. 26. Springer-Verlag Berlin."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2637364.2592038"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500098.2500106"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208007"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.2307\/3212792"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2002.801752"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4108\/icst.Valuetools.2014.258168"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"N. Choungmo Fofack P. Nain G. Neglia and D. Towsley. 2014. Performance evaluation of hierarchical TTL-based cache networks. Comput. Netw. 65 (June 2014) 212--231.","DOI":"10.1016\/j.comnet.2014.03.006"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(99)00037-1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/98457.98525"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810156.2810161"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(77)80014-7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2896377.2901459"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90177-C"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2414276.2414286"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2896380"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2017.09.002"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1090.0761"},{"key":"e_1_2_1_20_1","unstructured":"P. Jelenkov. 2017. Private communication between P. Jelenkovic and the authors."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.07.029"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0021900200002394"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1029962750"},{"key":"e_1_2_1_24_1","first-page":"485","article-title":"Analysis of demand paging algorithm. Info","volume":"71","author":"King W. F.","year":"1972","unstructured":"W. F. King. 1972. Analysis of demand paging algorithm. Info. Process. 71 (1972), 485--490.","journal-title":"Process."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1041444"},{"key":"e_1_2_1_26_1","volume-title":"Probability Theory I","author":"Lo\u00e8ve M.","unstructured":"M. Lo\u00e8ve. 1977. Probability Theory I (4th ed.). Graduate Texts in Mathematics, Vol. 45. Springer-Verlag, New York.","edition":"4"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1239\/aap\/1282924064"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1833515.1833684"}],"container-title":["ACM Transactions on Modeling and Performance Evaluation of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3239164","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3239164","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3239164","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:24Z","timestamp":1750208244000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3239164"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,7]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3239164"],"URL":"https:\/\/doi.org\/10.1145\/3239164","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"value":"2376-3639","type":"print"},{"value":"2376-3647","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,7]]},"assertion":[{"value":"2018-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}