The problem of optimal content placement over a network of caches arises in several contexts, including content delivery networks (CDNs), wireless edge networks, and peer-to-peer (P2P) networks. Under a set of demands and routes that requests follow, we wish to determine the content placement across the network that maximizes the expected caching gain, i.e., the reduction of routing costs due to intermediate caching. This objective is not convex, and the offline version of this problem is NP-hard. We seek adaptive algorithms for assigning content to caches that operate without prior knowledge of the demand. We propose a distributed, adaptive algorithm that performs stochastic gradient ascent on a concave relaxation of the caching gain, and construct a probabilistic content placement within a 1-1/e approximation factor from the optimal allocation, in expectation. Motivated by our analysis, we also propose a simpler adaptive heuristic, and show through numerical evaluations that both algorithms significantly outperform traditional algorithms like LRU and LFU over a broad array of network topologies. Next, we focus on the more general problem of jointly optimizing caching and routing decisions to minimize routing costs over an arbitrary network topology. We show that our concave relaxation approach extends to this more general setting, and produce distributed, adaptive algorithms with the same approximation guarantees. The resulting algorithms are shown to outperform the state of the art by several orders of magnitude. Finally, we briefly discuss the extension of this work to a number of other settings, including caching networks with congestion-dependent costs, and caching network with selfish nodes.

Joint work with Stratis Ioannidis