Optimum caching versus LRU and LFU: Comparison and combined limited look-ahead strategies
Optimum caching versus LRU and LFU: Comparison and combined limited look-ahead strategies
复制标题
DOI：
10.23919/wiopt.2018.8362880
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
G. Haßlinger;Juho Heikkinen;Konstantinos Ntougias;Frank Hasslinger;O. Hohlfeld
中科院分区：
文献类型：
--
作者：
G. Haßlinger;Juho Heikkinen;Konstantinos Ntougias;Frank Hasslinger;O. Hohlfeld
我们比较了基于最近最少使用(LRU)和最不频繁使用(LFU)替换原则的Web缓存策略与基于Belady算法的最优缓存策略。这些策略的可实现命中率随着利用的关于请求模式的知识的增加而提高，同时计算工作量也在增加。这些结果概述了使用Zipf请求模式的Web缓存在整个相关范围内的性能权衡。在第二部分中，我们研究了有限前瞻最优策略与LRU、LFU或其他非预测方法的组合方法。我们根据请求轨迹和独立参考模型(IRM)的超前预测程度通过仿真评估命中率增益，并对观察到的行为进行分析确认。结果表明，当替换决策由于在长时间内容更新期间遇到新请求而被部分修改时，用于视频流的高速缓存可以从所提出的前瞻技术中受益。
We compare web caching strategies based on the least recently used (LRU) and the least frequently used (LFU) replacement principles with optimum caching according to Belady's algorithm. The achievable hit rates of the strategies are shown to improve with the exploited knowledge about the request pattern while the computation effort is also increasing. The results give an overview of performance tradeoffs in the whole relevant range for web caching with Zipf request pattern. In a second part, we study a combined approach of the optimum strategy for a limited look-ahead with LRU, LFU or other non-predictive methods. We evaluate the hit rate gain depending on the extent of the look-ahead for request traces and for the independent reference model (IRM) via simulation and derive an analytic confirmation of the observed behaviour. It is shown that caching for video streaming can benefit from the proposed look-ahead technique, when replacement decisions can be partly revised due to new requests being encountered during long lasting content updates.