  We study the problem of optimal content placement over a network of caches, a
problem naturally arising in several networking applications, including ICNs,
CDNs, and P2P systems. Given a demand of content request rates and paths
followed, we wish to determine the content placement that maximizes the
expected caching gain, i.e., the reduction of routing costs due to intermediate
caching. The offline version of this problem is NP-hard and, in general, the
demand and topology may be a priori unknown. Hence, a distributed, adaptive,
constant approximation content placement algorithm is desired. We show that
path replication, a simple algorithm frequently encountered in literature, can
be arbitrarily suboptimal when combined with traditional eviction policies,
like LRU, LFU, or FIFO. We propose a distributed, adaptive algorithm that
performs stochastic gradient ascent on a concave relaxation of the expected
caching gain, and constructs a probabilistic content placement within 1-1/e
factor from the optimal, in expectation. Motivated by our analysis, we also
propose a novel greedy eviction policy to be used with path replication, and
show through numerical evaluations that both algorithms significantly
outperform path replication with traditional eviction policies over a broad
array of network topologies.
