SpringerLink
Log in

A Cluster Caching Rule in Next Generation Networks

  • Conference paper
  • First Online:
Distributed Computer and Communication Networks (DCCN 2015)

Part of the book series: Communications in Computer and Information Science ((CCIS,volume 601))

Abstract

Probabilistic aspects of caching are considered. The caching serves to keep popular contents inside a memory unit called ‘cache’ to be able to access them quickly. Using extreme value theory we propose a caching strategy called Cluster Caching Rule driven by content popularity that may change in time. A non-Poisson request arrival process is used when requests are statistically correlated. The idea of the new approach is to locate in cache only contents whose popularity exceeds a sufficiently large threshold. Due to dependence and possible heavy-tailed distribution of inter-requests and inter-arrival times of documents, the popularity process builds clusters of exceedances. The cluster and inter-cluster sizes are geometrically distributed as derived in Markovich (2014). We use it to calculate means of the cache utilization and occupancy. We escape assumptions like a constant size of content and a Poisson request process that are typical in the literature.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    If the document size is fixed then a new document evicts one document from the full cache.

  2. 2.

    This follows from (1) since \(\rho _n=1-F(x_{\rho _n})\sim \tau /n\).

  3. 3.

    \(f_n\sim g_n\) implies \(\lim _{n\rightarrow \infty }f_n/g_n=1\).

  4. 4.

    This follows from (1) since \(1-F(x_{\rho _n})=\rho _n=1-q_n\sim \tau /n\) as \(n\rightarrow \infty \).

References

  1. Berger, D.S., Gland, P., Singla, S., Ciucu, F.: Exact analysis of TTL cache networks: the case of caching policies driven by stop** times. In: The ACM International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2014, pp. 595–596 (2014)

    Google Scholar 

  2. Foback, N.C., Nain, P., Neglia, G., Towsley, D.: Analysis of ttl-based cache networks. In: IEEE VALUETOOLS, pp. 1–10 (2012)

    Google Scholar 

  3. Friecker, C., Robert, P., Roberts, J.: A versatile and accurate approximation for LRU cache performance. In: Proceedings of ITC, pp. 1–8 (2012)

    Google Scholar 

  4. Che, H., Tung, Y., Wang, Z.: Hierarchical web caching systems: modeling, design and experimental results. IEEE JSAC 20(7), 1305–1314 (2002)

    Google Scholar 

  5. Jelenković, P.R., Radovanović, A.: Least-recently-used caching with dependent requests. Theoret. Comput. Sci. 326(1–3), 293–327 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  6. Jelenković, P.R., Radovanović, A.: Asymptotic optimality of the static frequency caching in the presence of correlated requests. Oper. Res. Lett. 37(5), 307–311 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  7. Clauset, A., Shalizi, C.R., Newman, M.E.J.: Power-law distributions in empirical data. SIAM Rev. 51(4), 661–703 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  8. Newman, M.E.J.: Power laws, Pareto distributions and Zipfs law [cond-mat.stat-mech] (2006). arxiv:cond-mat/0412004v3

  9. Imbrenda, C., Muscariello, L., Rossi, D.: Analyzing cacheable traffic in ISP access networks for micro CDN applications via content-centric networking. In: ACM SIGCOMM Information Centric Networks (ICN), September 2014

    Google Scholar 

  10. Lee, D., Choi, J., Kim, J.-H., Noh, S.H., Min, S.L., Cho, Y., Kim, C.S.: LRFU: a spectrum of policies that subsumes the least recently used and least frequently used policies. IEEE Trans. Comput. 50(12), 1352–1362 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  11. Markovich, N.M.: Modeling clusters of extreme values. Extremes 17(1), 97–125 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  12. Leadbetter, M.R., Lingren, G., Rootzén, H.: Extremes and Related Properties of Random Sequence and Processes. Springer, New York (1983)

    Book  Google Scholar 

  13. Beirlant, J., Goegebeur, Y., Teugels, J., Segers, J.: Statistics of Extremes: Theory and Applications. Wiley, Chichester, West Sussex (2004)

    Book  MATH  Google Scholar 

  14. Markovich, N.M.: Clusters of extremes: models, estimation and applications (2015, to submitted)

    Google Scholar 

Download references

Acknowledgments

The author was partly supported by the Russian Foundation for Basic Research, grant 13-08-00744 A.

Author information

Authors and Affiliations

  1. V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, Moscow, Russia

    N. Markovich

Authors
  1. N. Markovich
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to N. Markovich .

Editor information

Editors and Affiliations

  1. V.A. Trapeznikov Institute of Control Sc, Russian Academy of Sciences V.A. Trapeznikov Institute of Control Sc, Moscow, Russia

    Vladimir Vishnevsky

  2. V.A. Trapeznikov Inst. of Control Scienc, Russian Academy of Sciences V.A. Trapeznikov Inst. of Control Scienc, Moscow, Russia

    Dmitry Kozyrev

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this paper

Cite this paper

Markovich, N. (2016). A Cluster Caching Rule in Next Generation Networks. In: Vishnevsky, V., Kozyrev, D. (eds) Distributed Computer and Communication Networks. DCCN 2015. Communications in Computer and Information Science, vol 601. Springer, Cham. https://doi.org/10.1007/978-3-319-30843-2_32

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-30843-2_32

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-30842-5

  • Online ISBN: 978-3-319-30843-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation