Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-15T08:13:18.415Z Has data issue: false hasContentIssue false
  • English
  • Français

Critical sizing of LRU caches with dependent requests

Part of:Limit theoremsMarkov processesStochastic processesTheory of data

Published online by Cambridge University Press:  14 July 2016

Predrag R. Jelenković,
Ana Radovanović and
Mark S. Squillante
Predrag R. Jelenković*
Affiliation:
Columbia University
Ana Radovanović*
Affiliation:
IBM T. J. Watson Research Center
Mark S. Squillante*
Affiliation:
IBM T. J. Watson Research Center
*
∗ Postal address: Department of Electrical Engineering, Columbia University, New York, NY 10027, USA. Email address: predrag@ee.columbia.edu
∗∗ Postal address: Department of Mathematical Sciences, IBM T. J. Watson Research Center, PO Box 218, Yorktown Heights, NY 10598, USA.
∗∗ Postal address: Department of Mathematical Sciences, IBM T. J. Watson Research Center, PO Box 218, Yorktown Heights, NY 10598, USA.
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.

It was recently proved by Jelenković and Radovanović (2004) that the least-recently-used (LRU) caching policy, in the presence of semi-Markov-modulated requests that have a generalized Zipf's law popularity distribution, is asymptotically insensitive to the correlation in the request process. However, since the previous result is asymptotic, it remains unclear how small the cache size can become while still retaining the preceding insensitivity property. In this paper, assuming that requests are generated by a nearly completely decomposable Markov-modulated process, we characterize the critical cache size below which the dependency of requests dominates the cache performance. This critical cache size is small relative to the dynamics of the modulating process, and in fact is sublinear with respect to the sojourn times of the modulated chain that determines the dependence structure.

Keywords

Network cachingleast-recently-used cachingmove-to-front searchingnearly completely decomposable Markov processMarkov-modulated processZipf's law

MSC classification

Primary:60J25: Continuous-time Markov processes on general state spaces60F10: Large deviations
Secondary:68P10: Searching and sorting60G50: Sums of independent random variables; random walks

Information

Type
Research Papers
Information
Journal of Applied Probability , Volume 43 , Issue 4 , December 2006, pp. 1013 - 1027
Copyright
© Applied Probability Trust 2006 

Footnotes

Supported by the NSF, grant no. 0092113.

References

Almeida, V., Bestavros, A., Crovella, M. and de Oliviera, A. (1996). Characterizing reference locality in the WWW. In Proc. 4th Internat. Conf. Parallel Distributed Inf. Systems, IEEE Computer Society, Washington, DC, pp. 92–107.Google Scholar
Asmussen, S., Henriksen, L. F. and Klüppelberg, C. (1994). Large claims approximations for risk processes in a Markovian environment. Stoch. Process. Appl. 54, 29–43.Google Scholar
Bentley, J. L. and McGeoch, C. C. (1985). Amortized analyses of self-organizing sequential search heuristics. Commun. Assoc. Comput. Mach. 28, 404–411.Google Scholar
Borodin, A. and El-Yaniv, R. (1998). Online Computation and Competitive Analysis. Cambridge University Press.Google Scholar
Breslau, L., Cao, P., Fan, L., Phillips, G. and Shenker, S. (1999). Web caching and Zipf-like distributions: evidence and implications. In Proc. INFOCOM '99, Vol. 1 (New York, March 1999), pp. 126–134.Google Scholar
Dembo, A. and Zeitouni, O. (1993). Large Deviations Techniques and Applications. Jones and Bartlett, Boston, MA.Google Scholar
Fill, J. A. (1996). An exact formula for the move-to-front rule for self-organizing lists. J. Theoret. Prob. 9, 113–160.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
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 Lazar, A. A. (1998). Subexponential asymptotics of a Markov-modulated random walk with queueing applications. J. Appl. Prob. 35, 325–347.Google Scholar
Jelenković, P. R. and Radovanović, A. (2003.). Asymptotic insensitivity of least-recently-used caching to statistical dependency. In Proc. INFOCOM 2003, Vol. 1 (San Francisco, CA, March–April 2003), pp. 438–447.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. (2004). Optimizing LRU caching for variable document sizes. Combinatorics Prob. Comput. 13, 627–643.Google Scholar
Sleator, D. D. and Tarjan, R. E. (1985). Self-adjusting binary search trees. J. Assoc. Comput. Mach. 32, 652–686.CrossRefGoogle Scholar
Young, N. E. (2000). On-line paging against adversarially biased random inputs. J. Algorithms 37, 218–235.Google Scholar