Adaptive Caching Networks With Optimality Guarantees
Adaptive Caching Networks With Optimality Guarantees
复制标题
DOI：
10.1109/tnet.2018.2793581
复制
发表时间：
2016-04
期刊：
影响因子：
--
通讯作者：
Stratis Ioannidis;E. Yeh
中科院分区：
文献类型：
--
作者：
Stratis Ioannidis;E. Yeh
我们研究的最佳位置的内容在网络上的缓存，一个问题自然出现在几个网络应用程序。给定内容请求速率和所遵循的路径的需求，我们希望确定使预期缓存增益最大化的内容放置，即，由于中间缓存而减少了路由成本。这个问题的离线版本是NP难的，并且一般来说，需求和拓扑可能是先验未知的。因此，需要一种用于将内容放置到高速缓存中的分布式自适应近似算法。我们表明，路径复制，一个简单的算法经常遇到的文献中，可以任意次优结合传统的驱逐政策。我们提出了一个分布式的，自适应的算法，执行随机梯度上升的预期缓存增益的凹松弛，并构造一个概率内容放置在一个$1-1/E$的因素，从最佳的，在预期中。出于我们的分析，我们还提出了一种新的贪婪驱逐政策与路径复制，并通过数值评估表明，这两种算法显着优于传统的驱逐政策在广泛的网络拓扑结构的路径复制。
We study the optimal placement of content over a network of caches, a problem naturally arising in several networking applications. 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 approximation algorithm for placing contents into caches is desired. We show that path replication, a simple algorithm frequently encountered in literature, can be arbitrarily suboptimal when combined with traditional eviction policies. 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 a $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.