Accurate Learning or Fast Mixing? Dynamic Adaptability of Caching Algorithms
Accurate Learning or Fast Mixing? Dynamic Adaptability of Caching Algorithms
复制标题
DOI：
10.1109/jsac.2018.2844984
复制
发表时间：
2017-01
影响因子：
16.4
通讯作者：
Jian Li;S. Shakkottai;John C.S. Lui;V. Subramanian
中科院分区：
文献类型：
--
作者：
Jian Li;S. Shakkottai;John C.S. Lui;V. Subramanian
在静态请求过程下使用稳态命中概率度量的内容缓存算法的典型分析没有考虑可变请求到达过程下的性能损失。在本文中，我们将缓存算法概念化为复杂度有限的在线分布学习算法，并利用这一Vantage从两个角度研究它们的适应性：1）学习固定流行度分布的准确性和2）学习项目流行度的速度。为了实现这一目标，我们计算几个流行的算法的平稳分布之间的距离与基因辅助算法，具有真正的流行度排名的知识，我们用它作为学习精度的衡量标准。然后，我们描述每个算法的混合时间，即，达到平稳分布所需的时间，我们将其用作学习效率的衡量标准。我们合并上述措施，以获得“学习误差”表示如何快速和准确的算法学习的最佳缓存分布，并使用此来确定这两个目标之间的权衡许多流行的缓存算法。根据我们的分析结果，我们提出了一种新的混合算法，自适应最近使用的，学习速度更快，更好的变化的流行。我们数值表明，它也优于所有其他候选算法时，面对一个动态变化的合成请求过程或使用真实的世界的痕迹。
Typical analysis of content caching algorithms using the metric of steady state hit probability under a stationary request process does not account for performance loss under a variable request arrival process. In this paper, we instead conceptualize caching algorithms as complexity-limited online distribution learning algorithms and use this vantage point to study their adaptability from two perspectives: 1) the accuracy of learning a fixed popularity distribution and 2) the speed of learning items’ popularity. In order to attain this goal, we compute the distance between the stationary distributions of several popular algorithms with that of a genie-aided algorithm that has the knowledge of the true popularity ranking, which we use as a measure of learning accuracy. We then characterize the mixing time of each algorithm, i.e., the time needed to attain the stationary distribution, which we use as a measure of learning efficiency. We merge both the abovementioned measures to obtain the “learning error” representing both how quickly and how accurately an algorithm learns the optimal caching distribution and use this to determine the trade-off between these two objectives of many popular caching algorithms. Informed by the results of our analysis, we propose a novel hybrid algorithm, adaptive-least recently used, that learns both faster and better the changes in the popularity. We show numerically that it also outperforms all other candidate algorithms when confronted with either a dynamically changing synthetic request process or using real world traces.