基于全局信息的缓存替换算法研究

张学圈 张红跃 熊章学 王红青 张鹏远 牛志雷 刘家军

(1.许继电气股份有限公司，河南 许昌 461000;2.华东电力试验研究院有限公司，上海 200437)

缓存技术是计算机中所普遍采用的基本技术之一，并且缓存技术是P2P流媒体技术得以应用的基础。P2P流媒体服务的优点在于通过Peer节点缓存部分数据段，以此在P2P网络中提供更多片源信息，同时通过Peer节点贡献的上载能力，来达到对等节点间的相互服务，从而降低服务器的压力，提高系统服务容量。同时通过缓存技术也可以有效的应对P2P网络结构的不确定性，节点频繁加入、退出网络等因素的影响，为流媒体提供稳定的服务。

虽然通过扩大存储空间可以有效地提供服务片源，但是P2P流媒体的数据缓存还存在以下问题：(1)缓存空间是分布式的，系统的缓存空间分布在加入到系统的不同对等节点上;(2)基于buffer-forwar方式下，各Peer节点的存储空间是有限的;(3)由于Peer节点的不确定性，必然导致缓存空间的总体容量的不确定，它随加入到系统中对等节点的数量变化而变化;(4)由于各对等节点间的松耦合特性，系统的缓存空间难以统一管理;(5)系统对同一流媒体内容一般均缓存有多个副本，其副本数量应与其流行度相关。因此如何解决上述问题将直接影响到P2P流媒体服务的性能和服务的可靠性。

针对以上几种情况，需要针对无效的资源进行替换，调整出更多缓存资源用于缓存稀缺资源。从而从整体达到需求和供给的平衡。减轻服务器压力，提升系统服务性能。通过以上问题分析，本文所述的媒体数据段替换策略可以采用GLFU-PVDP算法，即通过PVDP算法获取全局信息，对本地Peer节点，结合全局信息和本地LFU信息做出缓存替换裁决，从而获取资源的最佳使用。

1 基于全局信息的缓存替换算法

根据缓存中数据的属性，对缓存的数据段进行了如下分类，如图1所示。

图1 数据段分类

(1)过期数据段：缓存的数据段，其已经经过Peer节点播放。Peer节点即使删除该数据段也不会造成本Peer节点播放无法异常。

(2)待播放数据段：缓存的数据段，但是Peer节点还没有播放此部分数据段，如果删除该部分数据段会造成Peer节点播放异常。

(3)正在播放的数据段(PPS)：缓存的数据段，Peer节点正在播放此数据段，无法删除该数据段。

(4)待下载数据段：还没有进入缓存管理的数据段，同时也是Peer节点没有播放过的数据段，Peer节点需要从其它Peer节点或者服务器下载该部分数据段。通常数据段编号是当前播放位置PPS的增序。

其中过期数据段，待播放数据段和正在播放的数据段的数据段可以向其它Peer节点提供服务。而过期数据段可以作为缓存替换候选集合。

本文基于分级覆盖网络组织方式。针对超级节点，需要周期统计通过超级节点转发到服务器的媒体服务请求，考虑到文中的优先级定义，在对服务器请求的同时需要进行优先级的统计。同时超级节点之间需要周期交互获取全局信息。在Peer节点周期上报和请求数据服务的回应中，给出该Peer节点缓存数据的稀缺度评价，用于Peer节点进行数据替换的依据。考虑到服务的提供者是优选本覆盖，随后是其它覆盖网络提供，因而数据段的稀缺度评价优先考虑本覆盖的稀缺度，随后考虑其它覆盖的稀缺度。具体定义参见公式(1-1)，

式中：

LRi——本覆盖网络内数据段i的的稀缺度;

ORi——其它覆盖网络同步的稀缺度信息;

β——调整因子，用于确认稀缺度倾向哪部分信息。

式中：

Rqi——单位时间内向服务器发起的数据段i的访问频率;

Rpi——请求数据段i的总计优先级;

δ——优先级调整因子。

式中：

Oqi——单位时间内同步的其它覆盖网络向服务器发起的数据段i的访问频率;

Opi——其它覆盖网络请求数据段i的总计优先级。

考虑到潮汐效应，不同区域的点播集中程度不同，同时考虑到网络代价，超级节点间的数据同步仅按域进行，不进行域间的数据同步，对于全局数据的有效性也需要考虑，原因如下：根据潮汐效应，针对不同的域可能访问存在突发性和集中性，而全局信息如果仅仅通过简单的加法运算，有可能存在情况是该数据段在域1是热媒体数据段，在域2则不一定是热媒体数据段。如果此时将域1的访问统计也平均到域2，则域2会提供部分额外资源用于服务数据段A，但是本域内访问并不高，而过多地向域1的Peer提供服务，导致网络资源的浪费。

对于数据段的替换发生在以下几种情况：(1)资源利用率不高的时候，即本地缓存的数据段并没有为其它Peer节点服务时，Peer节点可以替换出没有参与服务的数据段用于提前下载将要播出的数据段。(2)在资源利用率高的情况下，需要Peer节点根据待下载数据段的deadline来确定是否进行数据替换，即每个候选替换数据段均有较高时候，就需要根据待下载数据段的此次下载是否会影响到Peer节点当前服务情况而定了。

如果Peer节点判定以上情况发生时及需要进行数据段替换选择，替换依据是结合本地统计信息LFU以及超级节点反馈的稀缺度评价值进行替换。替换只针对过期数据段，替换依据公式(1-4)：

式中：

fi——缓存数据段保留等级;

Dfi——单位时间内数据段i的访问频率;

Ri——从超级节点同步的数据段稀缺度;

θ——稀缺度调整因子。

2 算法实现

2.1 稀缺度统计

在PVDP算法基础上，超级节点为每个数据段设置稀缺标志 A，同时设置属性 I(Lcount-，Lsumprior，Ocount，Osumprior)，其中Lcount记录单位时间内超级节点向服务器转发的数据段i的服务请求，Lsumprior记录转发的请求优先级和;Ocount记录单位时间内同步的其它覆盖网络转发的数据段i的服务请求，Osumprior记录同步的的请求优先级和。超级节点每接收到其它超级节点的广播信息后，累加(Ocount，Osumprior)信息。经过单位时间t，超级节点按照公式(6-2)计算每个数据段的稀缺度，并更新数据段的稀缺标志A。同时向域内其它超级节点广播该覆盖内的每个数据段的(Lcount，Lsumprior)信息，随后设置(Lcount，Lsumprior，Ocount，Osumprior)=(0，0，0，0)。

当超级节点收到Peer节点的资源上报Peer节点能力信息后，根据算法可知，如 Peer缓存数据段(1，2，3，4，5)，其目前可支持上行带宽剩余为可并行支持1个Peer数据的上载，该Peer上报其能力为((1，2，3，4，5)，1)。则超级节点会将数据段(1，2，3，4，5)的稀缺资源标志 A 信息反馈给 Peer节点((1，A1)，(2，A2)，(3，A2)，(4，A2)，(5，A2))。

2.2 Peer节点替换无效缓存

当接收到超级节点的同步信息和缓存数据段的稀缺信息后，Peer节点根据反馈的信息进行数据段服务的选择。

(1)首先检查Peer是否有空闲缓存，如果有则可以直接根据超级节点反馈的服务候选列表进行资源选择。否则进行iiI

(2)根据公式4〉对候选替换数据段进行排序。

(3)如果存在数据段替换fi=0，则数据段i被替换。如果不存在数据段fi=0则进行iv。

(4)如果该数据段的deadline〉ω则表明该数据段不是紧急数据，在本周期内可以不进行下载，因而取消该次数据服务段的请求。算法结束。否则进行v。

(5)选择数据段替换排序最后的数据缓存释放资源，进行数据服务请求。(6)继续选择一个待下载的数据段进行v。具体算法如图2所示。

图1 缓存替换算法

3 仿真分析

为了有效地验证本文提出的算法，我们按照本文提出的模型构造系统仿真模型进行评估。本章节就系统仿真模型进行介绍和结果分析。

3.1 仿真模型与参数设置

仿真模型中我们认为每个peer节点的请求媒体服务是独立的，系统仿真3类Peer的到达，其节点特性如下：上行和下行带宽分别为{1000Kbps，256Kbps}，{2000Kbps，512Kbps}，{4000Kbps，1024Kbps}，并且这 3 类节点按照 0.35，0.4 和 0.25的比率分布，所有Peer节点分布在3个域中。Peer请求媒体服务按照Poisson分布，到达概率为λ=10/s;为了对比验证服务器的负载，系统中设置一台媒体服务器。系统中总计有100个媒体文件，媒体文件的热度符合Zipf-like分布，其中θ=0.271。媒体文件播放速率按照128Kbps，时长100分钟，数据按照30S分段，peer与超级节点的交互周期也是30S，超级节点间数据同步也是30S，数据采集按照每5分钟一次的粒度进行数据采集;每个Peer缓存空间为11个原始数据段的存储空间。稀缺度调整因子θ=0.2，优先级调整因子δ=0.2，本地和外部覆盖调整因子β=0.4，即优先考虑本覆盖的资源需求。

3.2 仿真结果分析

仿真试验中我们分别从控制信息规模，服务延迟，VCR的影响，服务器负载方面仿真和分析，结果如下。

3.2.1 控制开销

针对控制信息我们按照5分钟的采集粒度进行统计，控制信息包括peer向超级节点上报的信息、后续对数据提供者的检索信息以及服务器间，服务器与超级节点间的同步信息和不同覆盖网络间的广播信息。考虑到本文是按照30S的周期进行数据的同步，检索等服务请求，同时控制信息的开销是与节点规模相关，因此我们将统计结果折算为每30S每Peer的开销。图3给出了在不同节点规模情况下本算法在系统正常状态下以及支持VCR操作情况下的统计结果，可以看出本算法较PVDP算法增加了系统开销，但是平均到每个节点的控制面数据开销较PVDP算法而言增加并不明显，但节点平均开销并不大。

图2 控制开销

3.2.2 服务延迟

针对缓存数据替换的有效性，我们通过Peer节点检索服务数据节点的命中次数进行评测，即需要几个hop才可以最终确定服务提供者。理想情况下Peer节点缓存了较多的热点数据段，则应当有较高的检索命中率，即通过几个小的hop交互即可确定服务提供者。同时针对VCR测试，考虑到用户的行为通常是将播放位置调整到热点数据段，即热点数据段的点播较为集中，也是VCR动作的目的调整位置。因而在对系统对VCR支持情况的测试中不同于第3章的方针测试方式，随机调整用户的播放位置，而是设置几个热点数据段位置，随机选择Peer节点触发VCR操作，而VCR动作调整的目标位置随机地落在某个设定的热点数据段位置。为了测试的简单，针对每个媒体数据文件我们设置3个热点播放位置，数据段10，数据段50和数据段90的位置。根据以上设置，我们对GFLU-PVDP算法和PVDP算法，以及P2VoD算法进行了仿真比较。从图4和图5中可以看出由于本文对热点数据段进行了针对性缓存，在Peer节点存储多的副本，从而有效地提高了热点数据检索的成功率，降低了VCR带来的服务延迟。

3.2.3 基于优先级的接入控制和服务器压力

针对服务器负载的仿真试验结果如图6所示。可以看出GFLU-PVDP算法中服务器的负载远低于PVDP算法，其原因在于GFLU-LCSS算法中根据超级节点间的广播信息，针对服务器服务的资源(文中认为的稀缺资源)进行了针对性的缓存，有效地减轻了服务器的压力。同时在GFLU-PVDP算法中结合待下载数据段i的deadline限制了Peer节点的提前下载量，并且保证了在Peer节点间提供了更多的服务候选资源，从而在相同系统规模的情况下，通过GFLU-PVDP缓存替换算法有效地减轻服务器负载，同时系统可以获得更大的服务能力。

图5 服务器压力

4 结论

GLFU-PVDP缓存替换算法，该算法中的超级节点不仅需要同步可用资源信息，还要负责周期统计本覆盖的的稀缺资源，并通过覆盖超级节点间的周期广播获取全局稀缺资源信息，各Peer节点在此信息基础上结合本地缓存数据服务频率进行数据段缓存的替换，来提高缓存数据的命中率，从而做到Peer节点的数据段替换，既兼顾全局稀缺资源的统计信息，又兼顾Peer节点服务资源服务的有效性，提升了系统的服务能力。通过仿真实验表明本文算法可以提高系统缓存的命中率，提升Peer节点集的服务能力，降低媒体服务器的负载压力。解决目前P2P网络结构存在的主要问题，为媒体流的传输、应用提供切实可行的全局信息的替换算法。

[1]CNNIC.2009年中国网民网络视频应用研究报告[R/OL]. Apr， 8， 2010. http：//research. cnnic. cn/html/1270691299d2051.html.

[2]中投顾问.2010-2015年中国网络视频行业投资分析及前景预测报告[R].Feb，2010.

[3]李之棠.P2P原理与技术[R].华中科技大学计算机学院.Jun，4，2007.

[4]雷迎春，程实，吴产乐等。应用网络编码的P2P内容分发[J].计算机研究与发展，2009，46(1)：108-119.

[5]ChiFeng Kao，ChungNan Lee.Aggregate Profit-Based Caching Replacement Algorithms for Streaming Media Transcoding Proxy Systems[J].Multimedia，2007，9(2)：221-230.

[6]徐群，祝永志.集群系统中的负载均衡问题的研究[J].计算机技术与发展，2009，8.

[7]罗杰文.Peer to Peer(P2P)综述[R/OL].Nov，3，2005.http：//docs.huihoo.com/p2p/1/index.html.

[8]Jun Wang，Johan Pouwelse，Jenneke Fokker.Personalization on a peer-to-peer television system[J].Multimedia Tools and Applications，2008，36(1)：89-113.

[9]HsiangFu Yu，HungChang Yang，ChuYi Chien.A Limited Client Capability Broadcasting Scheme for VoD Applications[C].ICN 2008：192-196.

[10]Tsai HsienMing，Ding JenWen，Cheng ShuChen.Providing continuous VCR function with interpolated active buffer management for near VoD system on ubiquitous multimedia environment[C].The 1st IEEE International Conference on Ubi-Media Computing and Workshops，2008：231-236.

[11]吴杰.P2P流媒体内容分发与服务关键技术研究[D].复旦大学博士学位论文，2008.

[12]冯健.P2P点播流媒体服务质量研究[D].国防科技大学博士学位论文，2008.

[13]张明龙，冯博琴，王雪平.并发多媒体服务系统超载模型分析[J].西安交通大学学报，2006，40(2)：161-164.

[14]杨杰.基于P2P的流媒体代理缓存系统[J].电脑与信息技术，2009，17(2)：60-65.

[15]胡懋智，徐恪，夏树涛等.TOW：一种新的P2P实时流媒体缓存替换算法[J].小型微型计算机系统，2009，30(8)：1484-1489.