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

A promising means to increase efficiency of cellular networks compared to existing architectures is to proactively cache data in the base stations. The idea is to store part of the data at the wireless edge and use the backhaul only to refresh the stored data. Data replacement will depend on the users’ demand distribution over time. As this distribution is varying slowly, the stored data can be refreshed at off-peak times. In this way, caches containing popular content serve as helpers to the overall system and decrease the maximum backhaul load [1–5].
Our goal in this paper is on developing low-complexity distributed and asynchronous content placement algorithms. This is of practical relevance in cellular networks in which an operator wants to optimize the stored content in caches (i.e., base stations) while keeping the communication in the network to a minimum. In that case it will help that caches exchange information only locally.
We consider continuous and discrete models in which caches are located at arbitrary locations in the plane or in the grid. Caches know their own coverage area as well as the coverage areas of other caches that overlap with this region. There is a content catalog from which users request files according to a known probability distribution. Each cache can store a limited number of files and the goal is to maximize the probability that a user at an arbitrary location in the plane will find the file that she requires in one of the caches that she is covered by. We develop a low-complexity asynchronous distributed cooperative content placement caching algorithms that require communication only between caches with overlapping coverage areas. In the basic algorithm, at each iteration a cache will selfishly update its cache content by minimizing the local miss probability and by considering the content stored by neighbouring caches. We provide a game theoretic perspective on our algorithm and relate the algorithm to the best response dynamics in a potential game. We demonstrate that our algorithm has polynomial step update complexity (in network and catalog size) and has overall convergence in polynomial time. This does not happen in general in potential games. We also provide two simulated annealing-type algorithms (stochastic [6] and deterministic) that finds the best equilibrium corresponding to the global minimum of the miss probability. Finally, we illustrate our results by a number of numerical results with synthetic and real world network models.