Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-24T00:59:49.174Z Has data issue: false hasContentIssue false
  • English
  • Français

A fluid limit for a cache algorithm with general request processes

Part of: Stochastic processes Limit theorems Algorithms - Computer Science

Published online by Cambridge University Press:  01 July 2016

Takayuki Osogami
Takayuki Osogami*
Affiliation:
IBM Research - Tokyo
*
∗ Postal address: IBM Research - Tokyo, 1623-14 Shimotsuruma, Yamato-shi, Kanagawa 242-8502, Japan. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We introduce a formal limit, which we refer to as a fluid limit, of scaled stochastic models for a cache managed with the least-recently-used algorithm when requests are issued according to general stochastic point processes. We define our fluid limit as a superposition of dependent replications of the original system with smaller item sizes when the number of replications approaches ∞. We derive the average probability that a requested item is not in a cache (average miss probability) in the fluid limit. We show that, when requests follow inhomogeneous Poisson processes, the average miss probability in the fluid limit closely approximates that in the original system. Also, we compare the asymptotic characteristics, as the cache size approaches ∞, of the average miss probability in the fluid limit to those in the original system.

Keywords

Fluid limitleast recently usedpoint processnonstationaryhit probabilityinsensitivityapproximation

MSC classification

Primary: 68W40: Analysis of algorithms
Secondary: 60G55: Point processes 60F05: Central limit and other weak theorems
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 42 , Issue 3 , September 2010 , pp. 816 - 833
Copyright
Copyright © Applied Probability Trust 2010 

References

Burville, P. J. and Kingman, J. F. C. (1973). On a model for storage and search. J. Appl. Prob. 10, 697–701.Google Scholar
Chu, J.-H. and Knott, G. D. (1993). A new method for computing page-fault rates. SIAM J. Comput. 22, 1319–1330.Google Scholar
Coffman, E. G. Jr. and Jelenković, P. (1999). Performance of the move-to-front algorithm with Markov-modulated request sequences. Operat. Res. Lett. 25, 109–118.Google Scholar
Fill, J. A. (1996). Limits and rates of convergence for the distribution of search cost under the move-to-front rule. Theoret. Comput. Sci. 164, 185–206.Google Scholar
Fill, J. A. and Holst, L. (1996). On the distribution of search cost for the move-to-front rule. Random Structures Algorithms 8, 179–186.Google Scholar
Flajolet, P., Gardy, D. and Thimonier, L. (1992). Birthday paradox, coupon collectors, caching algorithms and self-organizing search. Discrete Appl. Math. 39, 207–229.Google Scholar
Fristedt, B. and Gray, L. (1997). A Modern Approach to Probability Theory. Birkhäuser, Boston, MA.Google Scholar
Hirade, R. and Osogami, T. (2010). Analysis of page replacement policies in the fluid limit. Operat. Res. 58, 971–984 Google Scholar
Jelenković, P. R. (1999). Asymptotic approximation of the move-to-front search cost distribution and least-recently-used caching fault probabilities. Ann. Appl. Prob. 9, 430–464.Google Scholar
Jelenković, P. R. and Radovanović, A. (2004). Least-recently-used caching with dependent requests. Theoret. Comput. Sci. 326, 293–327.Google Scholar
Jelenković, P. R. and Radovanović, A. (2008). The persistent-access-caching algorithm. Random Structures Algorithms 33, 219–251.Google Scholar
Jelenković, P. R., Radovanović, A. and Squillante, M. S. (2006). Critical sizing of LRU caches with dependent requests. J. Appl. Prob. 43, 1013–1027.CrossRefGoogle Scholar
Johnson, T. and Shasha, D. (1994). 2Q: low overhead high performance buffer management replacement algorithm. In Proc. 20th Internat. Conf. Very Large Data Bases, Morgan Kaufmann, San Francisco, CA, pp. 439–450.Google Scholar
Lam, K., Leung, M. Y. and Siu, M. K. (1984). Self-organizing files with dependent accesses. J. Appl. Prob. 21, 343–359.CrossRefGoogle Scholar
McCabe, J. (1965). On serial files with relocatable records. Operat. Res. 13, 609–618.Google Scholar
Nelson, R. (1995). Probability, Stochastic Processes, and Queueing Theory. Springer, New York.CrossRefGoogle Scholar
Osogami, T. (2009). A fluid limit for cache algorithms with general request processes. In Proc. IEEE INFOCOM 2009, pp. 2836–2840.Google Scholar
Rodrigues, E. R. (1995). The performance of the move-to-front scheme under some particular forms of Markov requests. J. Appl. Prob. 32, 1089–1102.Google Scholar
Sigman, K. (1995). Stationary Marked Point Processes: An Intuitive Approach. Chapman & Hall, New York.Google Scholar
Sugimoto, T. and Miyoshi, N. (2006). On the asymptotics of fault probability in least-recently-used caching with Zipf-type request distribution. Random Structures Algorithms 29, 296–323.Google Scholar