Cache Policies for Linear Utility Maximization

Abstract : Cache policies to minimize the content retrieval cost have been studied through competitive analysis when the miss costs are additive and the sequence of content requests is arbitrary. More recently, a cache utility maximization problem has been introduced, where contents have stationary popularities and utilities are strictly concave in the hit rates. This paper bridges the two formulations, considering linear costs and content popularities. We show that minimizing the retrieval cost corresponds to solving an online knapsack problem, and we propose new dynamic policies inspired by simulated annealing, including DynqLRU, a variant of qLRU. For such policies we prove asymptotic convergence to the optimum under the characteristic time approximation. In a real scenario, popularities vary over time and their estimation is very difficult. DynqLRU does not require popularity estimation, and our realistic, trace-driven evaluation shows that it significantly outperforms state-of-the-art policies, with up to 45% cost reduction.
Type de document :
Rapport
[Research Report] RR-9010, Inria Sophia Antipolis. 2017
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01442693
Contributeur : Giovanni Neglia <>
Soumis le : mardi 31 janvier 2017 - 18:59:59
Dernière modification le : jeudi 11 janvier 2018 - 16:48:02
Document(s) archivé(s) le : lundi 1 mai 2017 - 17:18:25

Fichier

RR-9010.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01442693, version 2

Collections

Citation

Giovanni Neglia, Damiano Carra, Pietro Michiardi. Cache Policies for Linear Utility Maximization. [Research Report] RR-9010, Inria Sophia Antipolis. 2017. 〈hal-01442693v2〉

Partager

Métriques

Consultations de la notice

330

Téléchargements de fichiers

285