We consider updating strategies for a local cache which downloads time-sensitive files from a remote server through a bandwidth-constrained link. The files are requested randomly from the cache by local users according to a popularity distribution which varies over time according to a Markov chain structure. We measure the freshness of the requested time-sensitive files through their Age of Information (AoI). The goal is then to minimize the average AoI of all requested files by appropriately designing the local cache's downloading strategy. To achieve this goal, the original problem is relaxed and cast into a Constrained Markov Decision Problem (CMDP), which we solve using a Lagrangian approach and Linear Programming. Inspired by this solution for the relaxed problem, we propose a practical cache updating strategy that meets all the constraints of the original problem. Under certain assumptions, the practical updating strategy is shown to be optimal for the original problem in the asymptotic regime of a large number of files. For a finite number of files, we show the gain of our practical updating strategy over the traditional square-root-law strategy (which is optimal for fixed non time-varying file popularities) through numerical simulations.
翻译:我们考虑更新本地缓存策略, 通过带宽限制的链接从远程服务器下载时间敏感文件。 文件由本地用户根据按Markov 链条结构随时间变化而变化的流行分布从缓存中随机请求。 我们测量了要求的时间敏感文件在信息时代的新鲜程度。 然后, 目标是通过适当设计本地缓存下载战略, 将所有请求文件的平均 AoI 最小化。 为了实现这一目标, 最初的问题已经放松, 并被丢入一个 Constraced Markov 决策问题( CMDP ) 中, 我们用 Lagrangian 方法和线性编程来解决 。 受这个宽松问题解决方案的启发, 我们提出了一个符合原始问题所有限制的实用缓存更新战略 。 根据某些假设, 实际的更新战略被证明是最佳的, 用于大量文件的自定义机制中的原始问题 。 对于有限的文件, 我们通过数字模拟, 展示了我们通过传统的平原法律战略( 最适合固定时间变化文件群) 获得的实际更新战略 。