论文标题
以年龄为中心的缓存的最佳安排：障碍和计算
Optimal Scheduling of Age-centric Caching: Tractability and Computation
论文作者
论文摘要
信息时代的概念（AOI）已成为网络和控制系统中重要的性能指标。以AOI为代表的信息新鲜度自然是在缓存的背景下出现的。我们为时间嵌入式系统的最佳调度更新提供了最佳调查更新，其中内容的大小各不相同。缓存和进行内容更新的容量有限。每个内容都与AOI中单调减少的实用程序函数相关联。对于此组合优化问题，我们提出以下贡献。首先，我们提供了解决问题障碍边界的理论结果。特别是，通过使用网络流进行重新制定，我们证明边界基本上取决于内容是否相等的大小。其次，我们为问题得出了一个整数线性公式，可以为小规模场景获得最佳解决方案。接下来，通过数学重新制定，我们使用重复的列生成得出了可扩展的优化算法。此外，该算法计算全局最佳限制的界限，可用于评估任何调度解决方案的性能。与贪婪的时间表相比，大规模场景的性能评估证明了该算法的优势。最后，我们将工作的适用性扩展到循环调度。
The notion of age of information (AoI) has become an important performance metric in network and control systems. Information freshness, represented by AoI, naturally arises in the context of caching. We address optimal scheduling of cache updates for a time-slotted system where the contents vary in size. There is limited capacity for the cache and for making content updates. Each content is associated with a utility function that is monotonically decreasing in the AoI. For this combinatorial optimization problem, we present the following contributions. First, we provide theoretical results settling the boundary of problem tractability. In particular, by a reformulation using network flows, we prove the boundary is essentially determined by whether or not the contents are of equal size. Second, we derive an integer linear formulation for the problem, of which the optimal solution can be obtained for small-scale scenarios. Next, via a mathematical reformulation, we derive a scalable optimization algorithm using repeated column generation. In addition, the algorithm computes a bound of global optimum, that can be used to assess the performance of any scheduling solution. Performance evaluation of large-scale scenarios demonstrates the strengths of the algorithm in comparison to a greedy schedule. Finally, we extend the applicability of our work to cyclic scheduling.
