A Low-Complexity Approach to Distributed Cooperative Caching with Geographic Constraints - Archive ouverte HAL Access content directly
Journal Articles Proceedings of the ACM on Measurement and Analysis of Computing Systems Year : 2017

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

(1) , (2, 3) , (2, 3)
1
2
3

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.
Fichier principal
Vignette du fichier
main.pdf (966.52 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01648129 , version 1 (24-11-2017)

Identifiers

Cite

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 , 2017, 1, pp.27:1 - 27:24. ⟨10.1145/3084465⟩. ⟨hal-01648129⟩
94 View
204 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More