静态与动态结合的流媒体缓存替换算法研究

孙 昕，陈德运

（1.哈尔滨医科大学 基础医学院，黑龙江 哈尔滨150081；2.哈尔滨理工大学 计算机科学与技术学院，黑龙江 哈尔滨150080）

0 引 言

人们对流媒体播放质量和传输速率等方面要求越来越高，但传统的C／S模式点播系统的系统规模受到服务器性能和网络带宽的限制，为了解决这些瓶颈问题，近年来人们都将目光投向了P2P［1］技术，由于P2P技术可以有效地降低服务器负载，并有效地利用网络带宽和节点I／O资源［2］，所以将P2P技术融入流媒体点播系统可以有效解决流媒体数据占用磁盘空间大和传输带宽高等问题［3］。针对于如何提高P2P流媒体QoS（quality of service），本文提出了基于混合P2P的流媒体点播系统中采用静态与动态结合的缓存方案。

1 系统结构

本文采用文献 ［4］所提出的P2PProxy的系统结构，它将P2P的原理用于缓存VOD［5］流媒体：请求同一个视频文件的用户组成一个组，分别存储视频文件的各个部分，当用户无法从组内获得数据时，才从VOD服务器获得数据，这种方法能够有效缓解服务器的压力。如图1所示。

图1 系统结构

服务器的主要功能是提供所有节目资源［6］，这样可以避免纯分布式P2P模式下的版权问题和非法视频问题。同时也要维护各组节点列表，记录节点的登记和退出信息。处理各节点的服务请求，并记录各节点的缓存信息。

根据普通节点的节目请求，服务器将其分配到所有观看该节目的节点所组成的组，普通节点先在该组内查找其所请求节目块，若找到则由组内节点提供服务，否则由服务器提供服务。各节点要边观看边下载部分数据块［7］，以便能为其他请求节点提供服务，从而减轻服务器压力［8］，这一点也正是将P2P技术融入VOD系统的优越性的主要体现。

本文采用的文件划分方法是将待缓存流媒体文件基于时间流划分成相同大小的数据块［9］，整个系统以块为单位对点播内容进行查找、下载、播放等操作。

2 静态与动态结合的缓存替换算法

本文提出了一种称为SDCO （static and dynamic combination）的静态与动态结合的缓存替换算法，该算法由静态数据更新算法，播放数据替换算法和预取综合评定因子算法 （CED）3部分组成，其中，CED算法是SDCO的核心。

2.1 普通节点缓存区的划分

不同于以往的缓存研究，本文将普通节点缓存区分为3个区，分别是固定指派区 （fixed distribute cache，FDC）、当前播放区 （current play cache，CPC）和预取区 （prefetch distribute cache，PDC）。这样分区的目的在于尽可能地充分利用客户端缓存空间，提高其缓存命中率。

2.1.1 固定指派区

由于在系统运行过程中会存在流行度很高的过热数据块和流行度比较低的冷数据块，尤其是在系统刚刚运行时，整个P2P结构的节目播放组中还没有足够的数据块备份量，而动态缓存的研究主要集中在流行度高的数据块来提高VCR操作命中率，这就需要在缓存区中存在静态缓存部分，即固定指派区来存储一些固定分配的数据块，使得冷热数据块得以均衡［10］，尤其在系统运行初期能有效缓解服务器负载。在某个缓存节点i中，设3个区的缓存数据块数量分别为B （i，FDC），B （i，CPC），B （i，PDC），而整个缓存区的总缓存 数量是 B （i，total），其 中的 B （i，FDC）＝αB （i，total），B （i，CPC）＝βB （i，total），B（i，PDC）＝γB （i，total）。α＋β＋γ＝1。

令参数

若某一节点J（第J个到达节点）的值J＜＝C，则由服务器对各个用户节点分配固定缓存内容；当J＞C时，说明整个节目组中的静态固定指派区内已经拥有了该节目的所有数据分块内容，则不再由服务器对该节点进行分配，而是改由在组内节点间缓存的方案，缓存本节点刚刚播放过的数据块内容［11］，以供其他对等节点使用或本节点前跳VCR操作用。该区相应的算法为静态数据更新算法。

2.1.2 当前播放区

该分区主要用来缓存本节点播放点前后的若干数据块。这些缓存数据块序号是连续的，可以保证本节点在没有执行VCR操作时播放节目的流畅性，当其服务节点出现问题时可以保证节目的正常播放，留足了缓冲时间。该分区缓存替换策略采用滑动窗口的方式［12］，始终存放的都是在父节点处获得的播放点前后的数据块。若有其他节点正在向本节点请求同样的数据，则可以继而转发给其子节点。该区相应的算法为播放数据替换算法。

2.1.3 预取区

这一分区的目的主要是用来提高本节点和其他节点的VCR操作命中率，并兼顾全局数据块缓存的优化。预取数据要充分考虑其数据块热度和数据块的稀缺度，并受用户行为因子的影响。其中，数据块热度可由单位时间内的数据块请求量来表示，设数据块i热度为Pi，在t1时刻对于数据块i的请求量为Ri1，在t2时刻对于数据块i的请求量为Ri2，则Pi＝ （Ri2－Ri1）／ （t2－t1）；数据块i稀缺度Si为所有数据块的副本数与数据块i的副本数的比值，即Si＝CBtotal／CBi；用户观看节目时通常都从开头部分开始［13］，然后才决定是否继续观看，所以针对于用户这样的共性行为特征，将节目开始部分数据块的用户行为因子设置为Us，其余部分设置为Uo，Us＞Uo，数据块i用户行为因子Ui＝UoorUs。综合上述内容，本文提出一个概念为 “数据块预取综合评定因子”PS

该区相应的算法为CED替换算法。

2.2 SDCO缓存替换算法

算法1：静态数据更新算法。

UpdateFDC（待缓存数据块i）｛

If（J＜＝C）｛服务器直接分配数据块；｝

Else｛

If（size（i）＜size（FDC的空闲空间））｛

缓存刚刚播过的数据块i；｝

Else｛

Rep （i）＝find（FDC）；／／用数据块i来替换固定区中最久未被使用数据块；｝

｝

算法流程如图2所示。

算法2：播放数据替换算法

ReplaceCPC（待缓存数据块i）｛

If（size（i）＜size（CPC的空闲空间））｛

直接缓存数据块i；｝

Else｛

Rep （i）＝find （CPC）；／／用数据块i替换播放区中最久未使用的数据块；｝

图2 静态数据更新策略流程

｝

算法流程如图3所示。

图3 播放数据置换策略流程

算法3：CED缓存替换算法

ReplacePDC（待缓存数据块i）｛

If（size（i）＜size （PDC的空闲空间）AND Psi＝MAX （total））｛

直接缓存数据块i；｝

Else｛

Rep（i）＝find（PS）；／／该函数找出预取区中PS值最小的数据块进行替换；｝

｝

算法流程如图4所示。

3 仿真实验

本文利用模拟实验，通过在相同数量服务器和对等节点的情况下对等节点分别采用本文提出的SDCO算法和传统的LRU算法的比较来研究SDCO算法的有效性。使用以下3个性能指标来衡量播放质量：①服务器负载；②启动延迟：指用户执行播放或拖动操作，到节目开始正常播放之间的延迟时间。③节点缓存命中率。

图4 CED缓存置换策略流程

本实验在 Windows 2000，Pentium D 2.80GHz，1GB内存，100Mb／s网络带宽的机器上完成。用NS2仿真器来模拟系统中的服务器和对等节点在系统运行中的行为，仿真器由用户的请求驱动［14－15］。实验假定有一台流媒体服务器，其上存有长20个时长为60分钟左右的AVI影片文件，文件码率大致为500Kb／s，200个具有缓存能力的客户端节点，实验中忽略各种事件的处理时间，不考虑实际网络因素的影响 （带宽、拥塞、连接拓扑等）。假设所有节点参数相同而且节点不会中途离开。具体参数如表1所示。

表1 仿真实验中参数值

图5－图8给出了部分实验结果。实验证明SDCO缓存策略在启动延迟、服务器负载和节点缓存命中率方面优于传统的LRU算法。

图5为使用SDCO缓存策略和传统的LRU算法两种不同策略时服务器负载的变化情况。由图中可以看出，在服务器负载方面两种算法相比，SDCO缓存策略更优于传统LRU算法，在系统运行初期，由于普通节点固定缓存区里还没有足够的供其他节点访问的资源，所以两种算法区别不大，但是在当前节目组中服务器连接的普通节点数目大于等于C值时，由于所有数据块在用户节点中都可以找到，使用SDCO缓存策略优势得以体现，服务器负载得到了更加明显的改善。

图5 节点个数与服务器负载关系

图6为使用SDCO缓存策略和传统的LRU算法两种不同策略的情况下启动延迟的变化趋势。纵坐标为进入系统后节点平均启动时延延迟时间 （单位：秒），横坐标为系统对等节点数量 （单位：个）。从图中可以通过比较看出，使用SDCO缓存策略时启动延迟能得到较好的改善，尤其是在当前节目组中服务器连接的普通节点数目大于等于C值时，启动延迟时间得到了更加明显的改善。

图6 节点个数与启动延迟关系

图7 给出了普通用户端缓存存储空间分别为50M、100M、150M、200M、250M、300M 时，采用 SDCO 和LRU两种不同缓存策略情况下的节点网络利用率对比图。由于普通节点缓存空间的加大，将使得普通节点可以存储更多的数据块来为整个系统提供服务，从而使更多的数据可以在对等节点处下载而减轻了服务器负载压力和提高了网络利用率。从图7可以看出，随着普通节点端磁盘缓存空间的不断增加，网络利用率也在随之增大。

节点缓存命中率为节点所请求的数据资源在节点自身缓存区中和对等节点中能成功找到的概率。图8给出了采用SDCO和LRU两种不同缓存策略情况下的用户节点个数与节点缓存命中率对比图。从图8可以看出，随着节点个数的不断增加，节点缓存命中率也在不断增大。采用SD－CO缓存策略优势更加明显，这主要是因为SDCO策略采用了静态与动态结合的方式，并且在预取区中运用了CED策略综合评定各项影响因素，从而提高节点缓存命中率。

4 结束语

本文针对基于混合P2P的流媒体点播系统，提出了静态与动态相结合的SDCO缓存替换算法，静态是指所有用户对等节点都必须留有固定缓存区，在成功加入P2P网络后为其分配固定的缓存内容；而动态指的是用户对等节点可以在其余的缓存区中根据相应的缓存替换策略进行缓存或替换有利于播放性能和执行VCR操作的数据内容。该算法可使节目数据块在同一节目对等节点组中的缓存备份量得到合理均衡的分布，从而满足用户的高质量播放需求。最后通过仿真实验证实了该策略的优势。如何进一步优化3个分区的分配比例来更好地提高系统性能，是我们需要下一步研究的工作。

［1］YIU WPK，JIN X，CHAN SHG.Vmesh：Distributed segment storage for peer－to－peer interactive video streaming ［J］.IEEE Journal on Selected Areas in Communications，2006，25 （9）：1717－1731.

［2］HU Yuqi，HAO Liuyou，SUN Shuang.Cache replacement algorithms for streaming media based on smallest cache value［J］.Computer Engineering and Design，2011，32 （1）：85－88）［胡玉琦，郝留有，孙爽.基于最小价值的流媒体缓存替换算法 ［J］.计算机工程与设计，2011，32 （1）：85－88.］

［3］LEE G J，CHOI C K，CHOI C Y，et al.P2PProxcy：Peer－topeer proxy caching scheme for VOD service ［C］.Sixth International Conference on Computational Intelligence and Multimedia Applications，2007：272－277.

［4］LIU Xuanjia，HUANG Wei，WU Chuan，et al.InstantLeap：An architecture for fast neighbor discovery in large－scale P2PVoD streaming［J］.Multimedia Systems，2010，16 （3）：183－198.

［5］Coyle C L，Heather V.Social networking：Communication revolution or evolution ［J］.Bell Labs Technical Journal，2008，13 （2）：13－18.

［6］YE Tian，DI Wu，Kam Wing Ng.A novel caching mechanism for peer－to－peer based media－on－demand streaming［J］.Journal of Systems Architecture，2008，54 （2）：55－69.

［7］YANG Chuandong，YU Zhenwei，WANG Xinggang.Cache replacement algorithm for hybrid P2Pmedia streaming ［J］.Application Research of Computers，2006，23 （11）：71－73（in Chinese）.［杨传栋，余镇危，王兴刚.混合P2P流媒体的缓存替换算法研究 ［J］.计算机应用研究，2006，23 （11）：71－73.］

［8］MA Jie.Distributed storage transform method for streaming media cache［J］.Computer Engineering and Design，2010，31（20）：4393－4395 （in Chinese）.［马杰.流媒体缓存分散式存储转换方法 ［J］.计算机工程与设计，2010，31 （20）：4393－4395.］

［9］TAKANO R，YOSHIZAWA Y.Offloading VoD server organized dynamically distributed cache using P2Pdelivery［C］.Tokyo：International Conference on Information Networking，2008：1－5.

［10］CHEN Qi，WU Jie.Research and implementation of buffer management scheme in a P2Pstreaming media VOD system［J］.Computer Applications and Softwar，2009，26 （2）：94－96（in Chinese）.［陈起，吴杰.P2P流媒体点播系统中的缓存管理方案的研究和实现 ［J］.计算机应用与软件，2009，26 （2）：94－96.］

［11］Spanos D.Asynchronous distributed averaging on communication networks ［J］.IEEE Trans on Networking，2007，15（3）：512－520.

［12］ZHENG Jie，ZHANG Song，QI Jie.Research and simulation for peer selection strategy on P2Pstreaming ［J］.Computer Engineering and Design，2007，28 （22）：5369－5399 （in Chinese）.［郑婕，张松，齐洁.P2P流媒体节点选择机制的研究与仿真 ［J］.计算机工程与设计，2007，28 （22）：5369－5399.］

［13］GAO Wen.Recent advances in peer－to－peer media streaming systems ［J］.China Comminications，2006，5 （13）：52－57.

［14］SUN Mingsong，TANG Liang，ZHOU Hongmin.Client disk caching strategy on P2PVoD system ［J］.Computer Engineering，2008，34 （20）：71－73 （in Chinese）.［孙名松，唐亮，周红敏.P2P点播系统的客户端磁盘缓存策略 ［J］.计算机工程，2008，34 （20）：71－73.］

［15］ZHANG M，LUO J G，ZHAO L.A peer－to－peer network for live media streaming using apush－pull approach ［C］.Proceedings of ACM Multimedia，2005：287－290.