Analysis of Page Replacement Policies in the Fluid Limit

References

• Bahat O., Makowski A. M. Optimal replacement policies for non-uniform cache objects with optional eviction. Proc. IEEE INFOCOM 2003: The 22nd Annual Joint Conf. IEEE Comput. Comm. Societies (2003) (IEEE Computer Society Press, Los Alamitos, CA) 427–437Google Scholar
• Breslau L., Cao P., Fan L., Phillips G., Shenker S. Web caching and Zipf-like distributions: Evidence and implications. Proc. IEEE INFOCOM 1999: The 18th Annual Joint Conf. IEEE Comput. Comm. Societies (1999) (IEEE Computer Society Press, Los Alamitos, CA) 126–134Crossref, Google Scholar
• Che H., Tung Y., Wang Z. Hierarchical Web caching systems: Modeling, design and experimental results. IEEE J. Selected Areas Comm. (2002) 20(7):1305–1314Crossref, Google Scholar
• Fill J. A. Limits and rates of convergence for the distribution of search cost under the move-to-front rule. Theoret. Comput. Sci. (1996) 164(1–2):185–206Crossref, Google Scholar
• Fill J. A., Holst L. On the distribution of search cost for the move-to-front rule. Random Structures and Algorithms (1996) 8(3):179–186Crossref, Google Scholar
• Flajolet P., Gardy D., Thimonier L. Birthday paradox, coupon collectors, caching algorithms, and self-organizing search. Discrete Appl. Math. (1992) 39(3):207–229Crossref, Google Scholar
• Gonnet G. H., Munro J. I., Suwanda H. Exegesis of self-organizing linear search. SIAM J. Comput. (1981) 10(3):613–637Crossref, Google Scholar
• Hama T., Hirade R. Cache policy optimization for response cache of Web application server. (2004) . Technical report RT0572, IBM Research, Yamoto-shi, JapanGoogle Scholar
• Hendricks W. J. The stationary distribution of an interesting Markov chain. J. Appl. Probab. (1972) 9(1):231–233Crossref, Google Scholar
• Jelenković P. R. Asymptotic approximation of the move-to-front search cost distribution and least-recently-used caching fault probabilities. Ann. Appl. Probab. (1999) 9(2):430–464Crossref, Google Scholar
• Jelenković P. R., Radovanović A. Least-recently-used caching with dependent requests. Theoret. Comput. Sci. (2004a) 326(1–3):293–327Crossref, Google Scholar
• Jelenković P. R., Radovanović A. Optimizing LRU caching for variable document sizes. Combinatorics, Probab. Comput. (2004b) 13(4–5):627–643Crossref, Google Scholar
• Jiang S., Zhang X. LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance. Proc. 2002 ACM SIGMETRICS Internat. Conf. Measurement and Modeling Comput. Systems (2002) (ACM Press, New York) 31–42Crossref, Google Scholar
• Johnson T., Shasha D. 2Q: A low overhead high performance buffer management replacement algorithm. Proc. 20th Internat. Conf. Very Large Data Bases (1994) (Morgan Kaufmann, San Francisco) 439–450Google Scholar
• Laoutaris N., Che H., Stavrakakis I. The LCD interconnection of LRU caches and its analysis. Performance Eval. (2006) 63(7):609–634Crossref, Google Scholar
• Law A. M., Kelton W. D.Simulation Modeling and Analysis (2000) 3rd ed.(McGraw-Hill Higher Education, Burr Ridge, IL) Google Scholar
• McCabe J. On serial files with relocatable records. Oper. Res. (1965) 13(4):609–618Link, Google Scholar
• Megiddo N., Modha D. S. ARC: A self-tuning, low overhead replacement cache. Proc. 2nd USENIX Conf. File and Storage Technologies (2003) (USENIX Association, Berkeley, CA) 115–130Google Scholar
• O'Neil E. J., O'Neil P. E., Weikum G. The LRU-K page replacement algorithm for database disk buffering. Proc. 1993 ACM SIGMOD Internat. Conf. Management of Data (1993) (ACM Press, New York) 297–306Crossref, Google Scholar
• Sugimoto T., Miyoshi N. On the asymptotics of fault probability in least-recently-used caching with Zipf-type request distribution. Random Structures and Algorithms (2006) 29(3):296–323Crossref, Google Scholar
• Zhou Y., Philbin J., Li K. The multi-queue replacement algorithm for second level buffer caches. Proc. 2001 USENIX Annual Tech. Conf. (2001) (USENIX Association, Berkeley, CA) 91–104Google Scholar