nach oben

Queueing Systems

Erschienen in:

14.07.2017

Optimal timer-based caching policies for general arrival processes

verfasst von: Andres Ferragut, Ismael Rodriguez, Fernando Paganini

Erschienen in: Queueing Systems | Ausgabe 3-4/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we analyze the hit performance of cache systems that receive file requests with general arrival distributions and different popularities. We consider timer-based policies, with differentiated timers over which we optimize. The optimal policy is shown to be related to the monotonicity of the hazard rate function of the interarrival distribution. In particular, for decreasing hazard rates, timer policies outperform the static policy of caching the most popular contents. We provide explicit solutions for the optimal policy in the case of Pareto-distributed inter-request times and a Zipf distribution of file popularities, including a compact fluid characterization in the limit of a large number of files. We compare it through simulation with classical policies, such as Least Recently Used and discuss its performance.

Vorheriger Artikel Introduction to special issue: ACM SIGMETRICS 2016

Nächster Artikel Asymptotics of insensitive load balancing and blocking phases

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

The third case does not occur because \(\eta _n(T)\searrow 0\) as \(T\rightarrow \infty \) for this distribution.

The main difference with [17] is that here timers are computed following the optimal TTL policy from Theorem 3.

Aalto, S., Ayesta, U., Righter, R.: On the Gittins index in the M/G/1 queue. Queueing Syst. 63(1), 437–458 (2009)CrossRef

Ahlgren, B., Dannewitz, C., Imbrenda, C., Kutscher, D., Ohlman, B.: A survey of information-centric networking. IEEE Commun. Mag. 50(7), 26–36 (2012)CrossRef

Baccelli, F., Bremaud, P.: Elements of Queueing Theory. Springer-Verlag, Berlin (2013)

Bahat, O., Makowski, A.M.: Measuring consistency in TTL-based caches. Perform. Eval. 62(1), 439–455 (2005)CrossRef

Barrera, J., Fontbona, J.: The limiting move-to-front search-cost in law of large numbers asymptotic regimes. Ann. Appl. Probab. 20(2), 722–752 (2010)CrossRef

Berger, D.S., Gland, P., Singla, S., Ciucu, F.: Exact analysis of TTL cache networks. Perform. Eval. 79, 2–23 (2014)CrossRef

Berger, D.S., Henningsen, S., Ciucu, F., Schmitt, J.B.: Maximizing cache hit ratios by variance reduction. ACM SIGMETRICS Perform. Eval. Rev. 43(2), 57–59 (2015)CrossRef

Bianchi, G., Detti, A., Caponi, A., Blefari Melazzi, N.: Check before storing: what is the performance price of content integrity verification in LRU caching? ACM SIGCOMM Comput. Commun. Rev. 43(3), 59–67 (2013)CrossRef

Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, New York (2004)CrossRef

10.

Breslau, L., Cao, P., Fan, L., Phillips, G., Shenker, S.: Web caching and Zipf-like distributions: evidence and implications. In: Proceedings of IEEE/Infocom, pp. 126–134 (1999)

11.

Che, H., Tung, Y., Wang, Z.: Hierarchical web caching systems: modeling, design and experimental results. IEEE J. Sel. Areas Commun. 20(7), 1305–1314 (2002)CrossRef

12.

Dan, A., Towsley, D.: An approximate analysis of the LRU and FIFO buffer replacement schemes. In: Proceedings of ACM/SIGMETRICS, pp. 143–152 (1990)

13.

Dehghan, M., Massoulié, L., Towsley, D., Menasche, D., Tay, Y.C.: A utility optimization approach to network cache design. In: Proceedings of IEEE/Infocom, pp. 1–9 (2016)

14.

Ferragut, A., Rodriguez, I., Paganini, F.: Optimizing TTL caches under heavy tailed demands. In: Proceedings of ACM/SIGMETRICS, pp. 101–112 (2016)

15.

Fill, J.A.: Limits and rates of convergence for the distribution of search cost under the move-to-front rule. Theor. Comput. Sci. 164(1), 185–206 (1996)CrossRef

16.

Fofack, N.C., Nain, P., Neglia, G., Towsley, D.: Analysis of TTL-based cache networks. In: Proceedings of Intl. Conf on Performance Evaluation Methodologies and Tools (VALUETOOLS), pp. 1–10 (2012)

17.

Fofack, N.C., Nain, P., Neglia, G., Towsley, D.: Performance evaluation of hierarchical TTL-based cache networks. Comput. Netw. 65, 212–231 (2014)CrossRef

18.

Fricker, C., Robert, P., Roberts, J.: A versatile and accurate approximation for LRU cache performance. In: Proceedings of the 24th International Teletraffic Congress, pp. 57–64 (2012)

19.

Gast, N., Houdt, B.V.: Transient and steady-state regime of a family of list-based cache replacement algorithms. In: Proceedings of ACM/SIGMETRICS, pp. 123–136 (2015)

20.

Gelenbe, E.: A unified approach to the evaluation of a class of replacement algorithms. IEEE Trans. Comput. 100(6), 611–618 (1973)CrossRef

21.

Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.1. http://cvxr.com/cvx (2014)

22.

Jacobson, V., Smetters, D.K., Thornton, J.D., Plass, M.F., Briggs, N.H., Braynard, R.L.: Networking named content. In: Proceedings of the ACM/Conext, pp. 1–12 (2009)

23.

Jelenković, P., Radovanović, A.: Asymptotic insensitivity of least-recently-used caching to statistical dependency. In: Proceedings of IEEE/Infocom, pp. 438–447 (2003)

24.

Jelenković, P.R.: Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities. Ann. Appl. Probab. 9(2), 430–464 (1999)CrossRef

25.

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

26.

Jelenković, P.R., Radovanović, A.: The persistent-access-caching algorithm. Random Struct. Algorithms 33(2), 219–251 (2008)

27.

Jelenković, P.R., Radovanović, A., Squillante, M.S.: Critical sizing of LRU caches with dependent requests. J. Appl. Probab. 43(4), 1013–1027 (2006)CrossRef

28.

Jung, J., Berger, A.W., Balakrishnan, H.: Modeling TTL-based internet caches. In: Proceedings of IEEE/Infocom, pp. 417–426 (2003)

29.

King, W.: Analysis of paging algorithms. In: Proceedings of IFIP Congress, pp. 485–490 (1971)

30.

Martina, V., Garetto, M., Leonardi, E.: A unified approach to the performance analysis of caching systems. In: Proceedings of IEEE/Infocom, pp. 2040–2048 (2014)

31.

Osipova, N., Ayesta, U., Avrachenkov, K.: Optimal policy for multi-class scheduling in a single server queue. In: Proceedings of 21st International Teletraffic Congress (ITC), pp. 1–8 (2009)

32.

Rosensweig, E.J., Kurose, J., Towsley, D.: Approximate models for general cache networks. In: Proceedings of IEEE/Infocom, pp. 1–9 (2010)

Titel: Optimal timer-based caching policies for general arrival processes
verfasst von: Andres Ferragut
Ismael Rodriguez
Fernando Paganini
Publikationsdatum: 14.07.2017
Verlag: Springer US
Erschienen in: Queueing Systems / Ausgabe 3-4/2018
Print ISSN: 0257-0130
Elektronische ISSN: 1572-9443
DOI: https://doi.org/10.1007/s11134-017-9540-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3-4/2018

Large deviations in relay-augmented wireless networks

Asymptotics of insensitive load balancing and blocking phases

Optimal heavy-traffic queue length scaling in an incompletely saturated switch

Probabilistic selfish routing in parallel batch and single-server queues

Costly circuits, submodular schedules and approximate Carathéodory Theorems

Introduction to special issue: ACM SIGMETRICS 2016