We study the problem of optimal content placement over a
network of caches. This problem arises naturally in several contexts, including ICNs, CDNs, and P2P networks. Under a given 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; moreover, in general, demands may be a priori unknown. We seek adaptive algorithms for assigning content to caches that operate without prior knowledge of this
demand. We propose a distributed, adaptive algorithm that
performs stochastic gradient ascent on a concave relaxation of the caching gain, and constructs a probabilistic content placement within a 1-1/e approximation factor from the optimal allocation, in expectation. In doing so, we establish that solving this problem under arbitrary cache contents is equivalent to the solution in which cache contents are (a) randomized and (b) independent across nodes. 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.