Gibbsian On-Line Distributed Content Caching Strategy for Cellular Networks

In this paper, we develop Gibbs sampling-based techniques for learning the optimal placement of contents in a cellular network. We consider the situation where a finite collection of base stations are scattered on the plane, each covering a cell (possibly overlapping with other cells). Mobile users request downloads from a finite set of contents according to some popularity distribution which may be known or unknown to the base stations. Each base station has a fixed memory space that can store only a strict subset of the contents at a time; hence, if a user requests content that is not stored at any of its serving base stations, the content has to be downloaded from the backhaul. Hence, we consider the problem of optimal content placement which minimizes the rate of download from the backhaul, or equivalently maximize the cache hit rate. It is known that, when multiple cells can overlap with one another (e.g., under dense deployment of base stations in small cell networks), it is not optimal to place the most popular contents in each base station. However, the optimal content placement problem is NP-complete. Using the ideas of Gibbs sampling, we propose simple sequential content update rules that decide whether to store content at a base station (if required from the base station) and which content has to be removed from the corresponding cache, based on the knowledge of contents stored in its neighboring base stations. The update rule is shown to be asymptotically converging to the optimal content placement for all nodes under the knowledge of content popularity. Next, we extend the algorithm to address the situation where content popularities and cell topology are initially unknown, but are estimated as new requests arrive to the base stations; we show that our algorithm working with the running estimates of content popularities and cell topology also converges asymptotically to the optimal content placement. Finally, we demonstrate the improvement in cache hit rate compared with the most popular content placement and independent content placement strategies via numerical exploration.