Modeling Perfect LFU on cache systems using Markov chain

Modeling Perfect LFU on cache systems using Markov chain | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Article Modeling Perfect LFU on cache systems using Markov chain Emese Sziklay, Tamás Jursonovics This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-8887948/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted 7 You are reading this latest preprint version Abstract Accurately estimating the load on the origin server is crucial for the correct and efficient operation of a Content Delivery Network (CDN). Since CDNs rely heavily on caching, simulating caches with arbitrary topologies is essential. This paper presents a methodology for modeling the Perfect Least Frequently Used (PLFU) cache algorithm. While the literature has extensively documented various eviction strategies, including Least Recently Used (LRU), First-In First-Out (FIFO), and Random, there has been a lack of Markov models for frequency based caching algorithms. This work addresses that gap. The PLFU cache algorithm, being a stochastic process, can be represented as a Markov process after the cache has been in operation for a sufficient period. The proposed model enables the estimation of per-object miss rates for both single caches and cache networks, applicable directly to the PLFU algorithm and indirectly to Tiny-LFU strategies. Given that many CDNs employ LFU-like eviction policies, we show that our novel model provides practitioners and decision-makers with a practical tool for designing and deploying CDNs effectively. Physical sciences/Engineering Physical sciences/Mathematics and computing cache modeling Markov model W-TinyLFU hit rate Content Delivery Network Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Under Review Version 1 posted Reviews received at journal 09 Mar, 2026 Reviewers agreed at journal 06 Mar, 2026 Reviewers invited by journal 06 Mar, 2026 Editor assigned by journal 06 Mar, 2026 Editor invited by journal 02 Mar, 2026 Submission checks completed at journal 26 Feb, 2026 First submitted to journal 26 Feb, 2026 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-8887948","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Article","associatedPublications":[],"authors":[{"id":603367804,"identity":"b660e5b1-9199-4803-89a7-fcdaca3e17bd","order_by":0,"name":"Emese Sziklay","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABCklEQVRIie3OMUvDQBjG8ecIpEug6xXRfALhJBAE/TB3k0sGRwepOQ7MUuxav0jmlBeaJR+gQ8GGQrtmkoJFvFKqU1JHwftPz3A/3gNcrj8ZM1gedyPQB7zUzqKbyOOcCAxSMJ12E3jfxAvwCxKOyQj5SBeXWVavbu8XHD2dLRssVNpCRDE1Us4oiqsqihKx5gimWk+wbidMm0L6pPJ54p8lgobgSpsA1EpCwyz5pKf8bbP5uBbEEdba7DoIZsxI9UwyniP2sCfcHkYHERUzQr3cXeVVEg1GlviB0q92RK0fG5cr3rzfhHFZ1s12R7zfo6LZPtB568cOmZ/pH653v7cNT75wuVyuf9wX60VjFUnBPNgAAAAASUVORK5CYII=","orcid":"","institution":"Eötvös Loránd University","correspondingAuthor":true,"prefix":"","firstName":"Emese","middleName":"","lastName":"Sziklay","suffix":""},{"id":603367805,"identity":"0eb4d113-2116-4be1-ae1b-bd9e8ddfc45c","order_by":1,"name":"Tamás Jursonovics","email":"","orcid":"","institution":"Deutsche Telekom (Germany)","correspondingAuthor":false,"prefix":"","firstName":"Tamás","middleName":"","lastName":"Jursonovics","suffix":""}],"badges":[],"createdAt":"2026-02-15 18:53:07","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-8887948/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-8887948/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":104375441,"identity":"bfcbf551-cac8-47b5-ad20-55cb240bd766","added_by":"auto","created_at":"2026-03-11 06:21:58","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":678981,"visible":true,"origin":"","legend":"","description":"","filename":"MarkovPLFU.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8887948/v1_covered_b99a5eae-2c48-4c31-8894-b9b16bf8bde5.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Modeling Perfect LFU on cache systems using Markov chain","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"scientific-reports","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"scirep","sideBox":"Learn more about [Scientific Reports](http://www.nature.com/srep/)","snPcode":"","submissionUrl":"","title":"Scientific Reports","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Scientific Reports","inReviewEnabled":true,"inReviewRevisionsEnabled":true},"keywords":"cache modeling, Markov model, W-TinyLFU, hit rate, Content Delivery Network","lastPublishedDoi":"10.21203/rs.3.rs-8887948/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-8887948/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Accurately estimating the load on the origin server is crucial for the correct and efficient operation of a Content Delivery Network (CDN). Since CDNs rely heavily on caching, simulating caches with arbitrary topologies is essential. This paper presents a methodology for modeling the Perfect Least Frequently Used (PLFU) cache algorithm. While the literature has extensively documented various eviction strategies, including Least Recently Used (LRU), First-In First-Out (FIFO), and Random, there has been a lack of Markov models for frequency based caching algorithms. This work addresses that gap. The PLFU cache algorithm, being a stochastic process, can be represented as a Markov process after the cache has been in operation for a sufficient period. The proposed model enables the estimation of per-object miss rates for both single caches and cache networks, applicable directly to the PLFU algorithm and indirectly to Tiny-LFU strategies. Given that many CDNs employ LFU-like eviction policies, we show that our novel model provides practitioners and decision-makers with a practical tool for designing and deploying CDNs effectively.","manuscriptTitle":"Modeling Perfect LFU on cache systems using Markov chain","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-03-11 06:21:42","doi":"10.21203/rs.3.rs-8887948/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"editorInvitedReview","content":"","date":"2026-03-09T19:43:09+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"85590505713543316751498989981905387067","date":"2026-03-06T16:55:14+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2026-03-06T11:48:59+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2026-03-06T11:47:17+00:00","index":"","fulltext":""},{"type":"editorInvited","content":"","date":"2026-03-02T22:47:04+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2026-02-26T18:29:30+00:00","index":"","fulltext":""},{"type":"submitted","content":"Scientific Reports","date":"2026-02-26T09:33:26+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"scientific-reports","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"scirep","sideBox":"Learn more about [Scientific Reports](http://www.nature.com/srep/)","snPcode":"","submissionUrl":"","title":"Scientific Reports","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Scientific Reports","inReviewEnabled":true,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"142e2b28-3cf7-4565-9a0f-903d2ac184fe","owner":[],"postedDate":"March 11th, 2026","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[{"id":64205451,"name":"Physical sciences/Engineering"},{"id":64205452,"name":"Physical sciences/Mathematics and computing"}],"tags":[],"updatedAt":"2026-03-11T06:21:42+00:00","versionOfRecord":[],"versionCreatedAt":"2026-03-11 06:21:42","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-8887948","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-8887948","identity":"rs-8887948","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}