Asymptotically Exact TTL-Approximations of the Cache Replacement Algorithms LRU(m) and h-LRU

Abstract : Computer system and network performance can be significantly improved by caching frequently used information. When the cache size is limited, the cache replacement algorithm has an important impact on the effectiveness of caching. In this paper we introduce time-to-live (TTL) approximations to determine the cache hit probability of two classes of cache replacement algorithms: the recently introduced h-LRU and LRU(m). These approximations only require the requests to be generated according to a general Markovian arrival process (MAP). This includes phase-type renewal processes and the IRM model as special cases. We provide both numerical and theoretical support for the claim that the proposed TTL approximations are asymptotically exact. In particular, we show that the transient hit probability converges to the solution of a set of ODEs (under the IRM model), where the fixed point of the set of ODEs corresponds to the TTL approximation. We further show, by using synthetic and trace-based workloads, that h-LRU and LRU(m) perform alike, while the latter requires less work when a hit/miss occurs. We also show that, as opposed to LRU, h-LRU and LRU(m) are sensitive to the correlation between consecutive inter-request times.
Type de document :
Communication dans un congrès
28th International Teletraffic Congress (ITC 28), Sep 2016, Würzburg, Germany. Proceedings of the 28th ITC, 2016, 〈https://itc28.org/〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01292269
Contributeur : Nicolas Gast <>
Soumis le : mardi 22 mars 2016 - 17:10:33
Dernière modification le : jeudi 11 octobre 2018 - 08:48:05
Document(s) archivé(s) le : lundi 14 novembre 2016 - 02:14:22

Fichier

multilevelLRU.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : hal-01292269, version 1

Citation

Nicolas Gast, Benny Van Houdt. Asymptotically Exact TTL-Approximations of the Cache Replacement Algorithms LRU(m) and h-LRU. 28th International Teletraffic Congress (ITC 28), Sep 2016, Würzburg, Germany. Proceedings of the 28th ITC, 2016, 〈https://itc28.org/〉. 〈hal-01292269〉

Partager

Métriques

Consultations de la notice

580

Téléchargements de fichiers

261