DR-Cache: Distributed Resilient Caching with Latency Guarantees
DR-Cache: Distributed Resilient Caching with Latency Guarantees
复制标题
DOI：
10.1109/infocom.2018.8486316
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Jian Li;T. K. Phan;W. Chai;D. Tuncer;G. Pavlou;D. Griffin;M. Rio
中科院分区：
文献类型：
--
作者：
Jian Li;T. K. Phan;W. Chai;D. Tuncer;G. Pavlou;D. Griffin;M. Rio
当今互联网的主要应用是内容流，它越来越依赖于缓存来满足内容服务器和最终用户之间的延迟的严格条件。这些系统经常面临有限的带宽容量和网络服务器故障的挑战，这降低了缓存性能。在本文中，我们研究的问题，最佳分配的内容在弹性缓存网络，其中每个缓存可能会失败，在某些情况下。给定内容请求率和多个路由路径，我们制定了一个优化问题，以最大化预期的缓存增益，即，由于中间缓存而减少了等待时间。这个问题的离线版本是NP难的。我们首先提出了一个集中的，离线算法，并表明，（1-1/e）的近似比的最佳解决方案可以构建。然后，我们提出了一个分布式上升算法的基础上凹松弛的预期增益。根据我们的分析结果，我们最后提出了一个分布式的弹性缓存算法（DR缓存），是简单的和自适应的网络故障。我们的数字显示，DR缓存显着优于其他候选算法下的合成请求，以及真实的世界的痕迹一类网络拓扑结构。
The dominant application in today's Internet is content streaming, which is increasingly relying on caches to meet the stringent conditions on the latency between content servers and end-users. These systems routinely face the challenges of limited bandwidth capacities and network server failures, which degrade caching performance. In this paper, we study the problem of optimally allocating content over a resilient caching network, in which each cache may fail under some situations. Given content request rates and multiple routing paths, we formulate an optimization problem to maximize the expected caching gain, i.e., the reduction of latency due to intermediate caching. The offline version of this problem is NP-hard. We first propose a centralized, offline algorithm and show that a solution with (1-1/e) approximation ratio to the optimal can be constructed. We then propose a distributed ascent algorithm based on the concave relaxation of the expected gain. Informed by the results of our analysis, we finally propose a distributed resilient caching algorithm (DR-Cache) that is simple and adaptive to network failures. We show numerically that DR-Cache significantly outperforms other candidate algorithms under synthetic requests, as well as real world traces over a class of network topologies.