Ecole d'ingénieur et centre de recherche en Sciences du numérique

Cache policies for linear utility maximization

Neglia, Giovanni; Carra, Damiano; Michiardi, Pietro

IEEE/ACM Transactions on Networking, February 2018, Vol.26, N°1

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. We prove that DynqLRU asymptotically asymptotic converges 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.

Doi Bibtex

Titre:Cache policies for linear utility maximization
Type:Journal
Langue:English
Ville:
Date:
Département:Data Science
Eurecom ref:5436
Copyright: © 2018 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Bibtex: @article{EURECOM+5436, doi = {http://dx.doi.org/10.1109/TNET.2017.2783623}, year = {2018}, month = {01}, title = {{C}ache policies for linear utility maximization}, author = {{N}eglia, {G}iovanni and {C}arra, {D}amiano and {M}ichiardi, {P}ietro}, journal = {{IEEE}/{ACM} {T}ransactions on {N}etworking, {F}ebruary 2018, {V}ol.26, {N}°1}, url = {http://www.eurecom.fr/publication/5436} }
Voir aussi: