面向网络流量的缓存替换算法比较与分析

缓存替换算法对优化网络处理应用的性能起到关键作用，但目前面向网络流量的缓存替换算法研究主要集中在算法设计和领域应用方面，较少有文献对现有的缓存替换算法在网络环境下的性能进行分析比较。对此，本文针对主要的6种缓存替换算法进行分析和比较。通过分析网络流量的新近度与频度特征，为基于最近最少使用(Least Recently Used, LRU)和最近最不常使用(Least Frequently Used, LFU)的缓存替换算法给出实际依据。对仿真环境和实际系统的实验结果表明，类LRU算法较LFU算法更适用于网络流量，而缓存空间较大时，随机替换算法较LRU算法更适用于多核环境。     

一种基于LRU算法改进的缓存方案研究与实现

LRU（最近最少使用）替换算法在单处理器结构的许多应用中被广泛使用。然而在多处理器结构中,传统LRU算法对降低共享缓存的缺失率并不是最优的。文中研究了基本的缓存块替换算法,在分析LRU算法的基础上,提出基于LRU算法及访问概率改进的缓存方案,综合考虑最近使用次数和访问频率来决定候选的替换块,增强了替换算法对多处理器的适应性。     

三种Web缓存替换的最优化模型研究

根据影响Web缓存性能的文件大小、访问频度、延迟等因素,通过灵活地选择代价因子,得到了命中率最大化、字节命中率最大化和延迟最小化3种Web缓存替换的最优化模型.模拟实验验证了该模型的正确性、灵活性和适用性.     

基于网络代价的流媒体缓存策略研究

该文构造了一种新的流媒体缓存效用函数,该函数综合考虑流媒体节目的流行度特性及传输网络的代价参数;设计了一种针对多视频服务器、基于网络代价的流媒体缓存分配与替换算法(Network Cost Based cache allocation and replacement algorithm, NCB)。仿真实验结果显示,NCB算法有效提高了缓存命中率,降低了传送流媒体所消耗的总体网络代价;该算法在网络结构复杂、节目数量庞大的Internet流媒体应用环境中表现出较优越的性能。     

NDN中基于蚁群替换算法的邻居协作缓存管理策略

为提高NDN(命名数据网络)中的缓存利用率,提出了一种基于蚁群替换算法的邻居协作缓存管理(ACNCM)策略。首先将单节点的缓存替换问题,建模为0/1背包问题,并根据缓存数据的大小、使用频率以及邻居副本深度等信息定义本地存储内容的缓存价值,提出基于蚁群算法的缓存替换算法。然后利用邻域协作的思想,通过路由节点之间定期交换自身节点的缓存信息,对单个节点替换出去的缓存内容,选择邻居节点完成协作式缓存管理。实验结果表明,ACNCM策略在缓存命中率、网络开销和平均响应时延方面均优于现有方法。     

Partition-Based Cache Replacement to Manage Shared L2 Caches

The Least recently used （LRU） replacement has been widely employed by on-chip shared caches. With the increase of cache associativity, the performance gap between LRU and theoretical optimal replacement algorithm is significant, motivating us to design alternative replacement algorithms to improve cache performance. We propose a Partltlon-based cache replace- ment （PCR） algorithm to manage multi-core shared L2 caches. PCR takes into consideration recency and fre- quency information of cache access, and cache resource interference among multiple competing applications. PCR is effective to flter out the less frequently reused blocks through a dynamic insertion/promotlon policy based on the target partitions~ and ensures that some fraction of the working set is retained in the cache to contribute to more hits. Our evaluation shows that PCR improves performance of an 8-core system by an average of 11.3% over LRU-based cache.     

基于一体化网络的映射关系缓存策略

提出了一种针对映射关系查询的预缓存策略：在负责存储节点映射关系的接入交换路由器中设置缓存,将缓存算法应用于通信建立后映射关系的查询过程中.仿真结果表明,预缓存策略和接入路由器缓存策略能有效提高映射关系查询命中率和通信效率.     

基于预测的Web缓存替换策略

为提高Web缓存性能，在缓存替换算法的基础上加入预测机制，提出了基于预测的Web替换策略P-Re。预测算法采用PPM上下文模型，当缓存空间不够用来存放新的对象时，P-Re选择键值较小且未被预测到的对象进行替换。实验表明，基于预测的Web缓存替换算法P-Re相对于传统替换算法而言具有较高的命中率和字节命中率。     

基于序列模式的Servlet容器缓存替换

Servlet缓存能够有效地提高Servlet容器的吞吐量,缩短用户请求的响应时间.然而,Servlet缓存的性能受到缓存替换算法的影响.Servlet容器中的Servlet对应着一定的业务功能,挖掘Servlet之间的业务关联来指导缓存替换算法的设计可以提高Servlet缓存的命中率,进而提高Servlet容器的性能.然而,目前常见的LRU(least recently used),LFU(least frequently used),GDSF(greedy dual size frequency)等缓存替换算法均没有考虑上述问题.将Servlet对应的业务关联定义为Servlet容器序列模式,并提出k步可缓存转移概率图的概念加以表示,给出了序列模式发现算法KCTPG_Discovery.最后,基于Servlet容器序列模式设计了缓存替换算法KP-LRU(k-steps prediction least recently used)和KP-GDSF(k-steps prediction least frequently used).实验结果表明,KP-LRU与KP-GDSF算法比对应的LRU算法和GDSF算法具有更高的缓存命中率,有效地提高了Servlet容器的性能.     

缓存替换算法研究综述

缓存技术作为提高系统性能的重要手段一直是研究的热点。随着网络存储等新技术的出现，存储的层次越来越复杂，原有的简单缓存管理技术已经不合适日趋复杂的应用。频率和时间综合考虑的缓存替换方法、多级缓存的替换技术成为研究的热点。本文综述了缓存替换算法的研究现状，首先介绍传统简单的缓存替换算法及其存在的局限性，而后对单级缓存算法和多级缓存算法当前最新的研究进行了介绍。最后对研究的趋势进行了简单的展望。