A Low-Complexity Approach to Distributed Cooperative Caching with Geographic Constraints

Abstract : We consider caching in cellular networks in which each base station is equipped with a cache that can store a limited number of files. The popularity of the files is known and the goal is to place files in the caches such that the probability that a user at an arbitrary location in the plane will find the file that she requires in one of the covering caches is maximized. We develop distributed asynchronous algorithms for deciding which contents to store in which cache. Such cooperative algorithms require communication only between caches with overlapping coverage areas and can operate in asynchronous manner. The development of the algorithms is principally based on an observation that the problem can be viewed as a potential game. Our basic algorithm is derived from the best response dynamics. We demonstrate that the complexity of each best response step is independent of the number of files, linear in the cache capacity and linear in the maximum number of base stations that cover a certain area. Then, we show that the overall algorithm complexity for a discrete cache placement is polynomial in both network size and catalog size. In practical examples, the algorithm converges in just a few iterations. Also, in most cases of interest, the basic algorithm finds the best Nash equilibrium corresponding to the global optimum. We provide two extensions of our basic algorithm based on stochastic and deterministic simulated annealing which find the global optimum. Finally, we demonstrate the hit probability evolution on real and synthetic networks numerically and show that our distributed caching algorithm performs significantly better than storing the most popular content, probabilistic content placement policy and Multi-LRU caching policies.
Type de document :
Article dans une revue
Proceedings of the ACM on Measurement and Analysis of Computing Systems , ACM, 2017, 1, pp.27:1 - 27:24. 〈10.1145/3084465〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01648129
Contributeur : Konstantin Avrachenkov <>
Soumis le : vendredi 24 novembre 2017 - 18:22:09
Dernière modification le : jeudi 11 janvier 2018 - 16:36:43

Fichier

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

Identifiants

Citation

Konstantin Avrachenkov, Jasper Goseling, Berksan Serbetci. A Low-Complexity Approach to Distributed Cooperative Caching with Geographic Constraints. Proceedings of the ACM on Measurement and Analysis of Computing Systems , ACM, 2017, 1, pp.27:1 - 27:24. 〈10.1145/3084465〉. 〈hal-01648129〉

Partager

Métriques

Consultations de la notice

92

Téléchargements de fichiers

31