Jointly Optimal Routing and Caching for Arbitrary Network Topologies
Jointly Optimal Routing and Caching for Arbitrary Network Topologies
复制标题
DOI：
10.1145/3125719.3125730
复制
发表时间：
2017-08
影响因子：
16.4
通讯作者：
Stratis Ioannidis;E. Yeh
中科院分区：
文献类型：
--
作者：
Stratis Ioannidis;E. Yeh
我们通过在任意网络拓扑的情况下共同优化缓存和路由决策来研究最小化路由成本的问题。我们将其视为同等的缓存增益最大化问题，并考虑源路由和逐型路由设置。各自的离线问题是NP-HARD。然而，我们表明存在从最佳的恒定近似值内产生解决方案的多项式时间近似算法。我们还生产具有相同近似保证的分布式自适应算法。我们在各种不同的拓扑结构上模拟了自适应算法。与先前的ART相比，我们的算法将路由成本降低了几个数量级，包括在固定路由下优化缓存的算法。
We study a problem of minimizing routing costs by jointly optimizing caching and routing decisions over an arbitrary network topology. We cast this as an equivalent caching gain maximization problem, and consider both source routing and hop-by-hop routing settings. The respective offline problems are NP-hard. Nevertheless, we show that there exist polynomial time approximation algorithms producing solutions within a constant approximation from the optimal. We also produce distributed, adaptive algorithms with the same approximation guarantees. We simulate our adaptive algorithms over a broad array of different topologies. Our algorithms reduce routing costs by several orders of magnitude compared with prior art, including algorithms optimizing caching under fixed routing.