郑伟平

(华南师范大学计算机学院，广东广州510631)

数据缓存是P2P流媒体系统提升性能的重要手段，通过对等节点间共享数据可显著地降低流媒体源服务器的访问压力［1］．其中，考虑数据供求平衡是数据缓存常用的策略;但仅考虑数量关系，忽视了数据的分布情况．另一方面，邻近性(proximity)研究的主要驱动力是实现P2P数据的就近分发，以减少网络区域之间的数据流动［2］．目前，P2P邻近性研究集中在拓扑一致性上［3］，试图通过邻居的就近选取来实现数据的就近访问．在文件共享应用中，节点以下载一个完整文件为目标，对等节点间互为数据源的可能性很高，拓扑一致性算法能够较好地实现就近访问．在流媒体分发中，流媒体文件的容量大、在线播放等特性导致节点通常只存储流媒体对象的部分数据，仅靠邻居选择很难确保就近访问．节点的数据存储情况成为影响数据就近访问的另一关键因素．例如，CHENG 等［4］考虑节点数据存放情况，按播放点的距离将邻居组织成几个同心圆，以增加节点间数据共享的可能性．

为此，本文将数据缓存和邻近性研究结合起来，利用两者的互补优势，提出了一种考虑数据分布的P2P流媒体数据缓存模型．该模型将网络系统划分为多个区域，考虑缓存数据在网络不同区域的供求分布情况，节点根据数据的局部供求关系进行缓存替换，优先满足本区域内节点的数据需求，弥补了传统邻近性研究的不足，在邻居选择算法的配合下，可更好地达到就近访问效果．

1 数据缓存模型

网络运营商可依据管理权限、地理分布、产权归属等因素，静态或动态地将P2P种群节点(覆盖网)划分为多个区域．本文采用地理位置作为划分依据．假设区域内部网络通信的成本远低于区域间的成本，且节点具备标识自身所属区域的能力，假设对等节点可缓存少量数据，但其容量较小，带宽传输能力较弱．为了得到数据缓存的分布情况，建立了一种数据供求平衡的分布式获取及数据替换模型和算法．在存储容量固定的前提下，基于数据供求平衡的缓存替换优化模型可表述如下:

目前多数流媒体系统采用等长度分段，假设流媒体文件被等长分为J段，bi和ni分别为第i段数据的长度和缓存数量，S为系统的缓存容量上限．t为缓存替换的决策时刻;Demand(i，t)表示t时刻本区域内第i段的需求量;Supply(i，t)表示t时刻第i段在本区域的现存副本供应量．上述问题是NPC问题，一般用启发式算法求解．

文献［5］-［7］基于数据供求关系提出了缓存替换模型，但本模型考虑不同区域的供求差异，提出了基于局部供求的缓存替换．文献［6］提出的SD替换算法，需向根节点查询数据分片的供求统计数据，如果请求与供应的比值较高则保留分片，反之将其替换．文献［7］则使用数据供应和需求之间的绝对差值，对非热门数据段造成了歧视．本模型使用相对值的形式(见式(2))，这样更为合理．与文献［5］相同，文中使用分布式算法统计数据供求情况，无需集中查询．

2 数据供求度量及计算

定义1 需求模式:在一段时间［t，t+Δt］内流媒体对象各分段的访问概率分布称为此对象的需求模式，用需求向量PΔtt表示．

一般采用对象的历史流行度来衡量未来需求量，记 fi为第 i段的流行度，PΔtt=［f1，f2，…，fJ］．在缓存决策时，一般使用当前时刻的需求模式，可将简记为P．Pi为向量P的第i个分量，表示第i段(1≤i≤J)的访问需求量．

定义2 供应模式:流媒体对象各分段在系统各节点上现存副本的分布情况称为供应模式，反映了对等节点对各数据段的供应能力，用供应向量M表示．

令mi为当前系统中第i段数据的供应副本量．记M为向量 M的第i个分量，表示第i段的归一化缓存存量，Supply(i，t)=Mi．

定义3 局部供求模式:将统计范围限制在某一区域AN内得到的流媒体对象需求模式和供应模式称为该对象在区域AN上的局部供求模式．

定义4 全局供求模式:流媒体系统覆盖网全体对等节点参与统计得到的流媒体对象的需求模式和供应模式称为此对象的全局供求模式．

2．1 分布式一致性算法

分布式一致性算法［8］是一种分布式均值(averaging)计算方法，文献［5］首次应用此方法来统计数据段供求情况．该算法假设系统中每个节点都维护有某个属性的本地值，通过分布式方法在全局计算该属性平均值．每个节点i设置2个变量:Zi为属性的本地值，Xi为属性的均值状态变量．均值计算过程如下［5，8］:(1)每个节点随机选择 N 个邻居，按某种规则确定相互之间的“发送与接收”关系，并定期交换均值信息;(2)将节点上的Xi初始化为Zi，Zi是本地对属性的观察，随本地观察而改变，Xi值随着与邻居的均值信息交换而变化;(3)发送者i节点向接收者j发送STATE消息，将其维护的Xi告知j;(4)收到Xi后，j将 Xj更新为 Xj+γj(Xi-Xj)，并以REPLY消息将变化量γj(Xi-Xj)告知i;(5)i收到REPLY后将Xi更新为Xi-γj(Xi-Xj)．

图1为算法消息交换过程．均值数据交换时需保持总量守恒，通过节点之间的不断逼近，最终在全网范围得到属性均值．γj为节点步长，可在本地设定，0＜γj＜1．该算法具有较好的特性:支持时变(time-varying)属性的均值计算，具有较快的收敛速度，且支持节点的动态加入/退出［8］，应用分布式一致性算法作为数据供求模式的求解工具．

图1 分布式一致性消息交换Figure 1 Message exchange of distributed consensus

2．2 需求模式的计算

流媒体对象的需求模式由各段流行度确定．LRU-K［9］是常用的流行度预测算法，以过去一段时间对象请求的到达率来估计未来访问热度．记N(t)为t时刻对象最近被访问次数，N(t)只维护到K次，0≤ N(t)≤K．T(N(t))为前N(t)次的访问时间，对象的访问到达率 ω(t)=N(t)/(t-T(N(t)))．LRU-K算法最初面向数据库应用，后来被用于文件缓存、流媒体缓存等领域，很多方案直接将ω(t)作为对象的流行度，用于预测访问趋势．流媒体应用具有按序播放的特点，即请求前一段数据的节点时，会请求下一段数据，邻近数据段的流行度之间存在着“弱蕴含”关系．因此，可将其放在流媒体文件分段序列的上下文中考察其流行度．为此，提出“向后加权LRU-K”算法:先使用LRU-K算法为各分段计算ω(t)，然后将该段与前一段的ω(t)加权和作为该段的流行度，即:

假设流媒体文件分为J段，每个节点i上维护J个流行度观察值，构成了本地向量为节点i上第j段的流行度观察值．节点i还须设置均值状态向量．在系统收敛时，由XPi可算出需求模式向量P，即:

2．2．1 局部需求模式的计算 为了获取局部供求模式，节点只与所属区域网络内的N个随机节点建立分布式一致性的均值信息交换关系，假设系统提供某种识别节点所属区域的机制．计算局部需求模式时，需对本地的流行度观察向量ZPi进行处理．由于P2P节点可为本区域内或区域外的节点提供数据．为了反映区域内部节点的真实数据需求，将节点收到的请求区分为区内请求与区外请求．使用LRUK算法计算各段访问到达率ω(t)时，只统计区内请求．同时，将发向区外节点的数据请求等效为收到的区内请求，一起累计到ω(t)上．如图2所示，a、b、c为同区域的节点，d、e节点在区域外;箭头上的数字表示某一时间段内请求的数据段序号，箭头表示请求方向，如b节点向a节点请求1段和3段．在本实例中，a节点在此时间段内将统计各段的请求到达次数，分别为1、2、2、0 次(对应第1-4 段)．

图2 局部需求模式计算Figure 2 Computation of regional demand pattern

2．2．2 全局需求模式的计算 全局需求模式同样使用LRU-K算法来计算各段请求到达率．但与局部模式不同，其分布式一致性邻居节点在全系统范围内随机选取;且本地流行度观察向量仅统计收到的每段数据的请求个数，不需做特殊处理．

2．3 供应模式的计算

数据段的供应能力与3个因素有关:(1)缓存副本的数量;(2)缓存节点的上传带宽能力;(3)数据段的请求响应概率．文献［5］、［6］的研究只考虑了副本数量．但是，由于节点带宽的异构性，对于缓存同个数据段的不同节点，其上传带宽越大，服务供应能力越强．为此需要考虑缓存节点的带宽能力．另外，缓存节点上保存的其它数据段的流行度也对数据段的供应能力造成影响，即存在各数据段对上传带宽的争用问题．文献［7］对此服务竞争问题进行了详细的阐述，并给出服务概率计算公式，但需要全局信息，计算难度大．本模型的数据供应评估综合上述3个因素，并通过分布式一致性算法巧妙地结合起来．具体如下:

根据节点i的缓存情况，Iik=1表示缓存第k段数据，Iik=0表示不缓存;当节点没有整段缓存数据时，Iik=(节点缓存第k段的数据块数/数据段的总块数)．BWiup为节点平均上传带宽;P为需求模式向量．Fi为节点i缓存的数据段集合．节点i维护1个本地缓存状态向量，通过分布式一致性算法计算和维护均值向量由 ZMi定义式可知，本文对数据供应量的计算同时考虑缓存段数Iik、节点上传带宽能力BWiup和节点对不同请求的服务概率)，更真实地反映了系统的数据供应服务能力，避免了额外的信息收集机制和计算开销．

2．3．1 局部供应模式的计算 局部供应模式的计算较简单:节点与区域内部节点建立拓扑关系后，根据本地的数据段缓存和带宽能力等情况设置和更新本地向量ZMi，并定期和邻居交换均值信息，在系统收敛时，可用XMi计算供应模式:

2．3．2 全局供应模式的计算 全局供应模式的计算过程基本与局部供应模式一致，区别在于其分布式一致性算法邻居在全系统范围内随机选取．

3 基于局部供求平衡的数据缓存管理

全局供求模式与局部供求模式存在差异性．当应用到个体区域时，全局模式不能准确代表该区域的供求关系．而局部模式是在感知数据存放位置的基础上统计的供求关系．故此，为了实现就近访问，本节提出了基于局部供求模式的缓存替换算法，在节点播放完数据块b后，若本地有存储空间则直接缓存，否则调用替换过程DoReplace，其伪代码如下:记录本地已缓存的数据段id到集合S中

int m=Arg MiniSφ(i，t);∥求 φ 值最小的数据段id

int n=get_Segment_id(b);∥求数据块b所在数据段的id

if(n=m)不缓存数据块b;

else从本地第m段中随机选择一块将其替换为b;

更新本地缓存状态ZM;∥为下轮的分布式一致性数据交换做准备

}

4 结果与评价

使用NS2仿真的方法验证算法有效性．系统使用GT-ITM生成920个节点(1个transit域+3个stub域)，0-19号节点为核心交换节点，20-919号为普通节点．设置A、B、C 3个区域，分别在20-319号、320-619号以及620-919号节点中随机选取，各区节点分别处于同个stub域里．各区节点的带宽配置分3 类:(1)上行 512 Kbps、下行 1 Mbps，占 60%;(2)上行1 Mbps、下行1 Mbps，占30%;(3)上行2 Mbps、下行2 Mbps，占10%．系统模拟了1个流媒体服务器，上传带宽为50 Mbps，在紧急窗口内的数据才能向流媒体服务器请求．模拟的流媒体文件长度为30 min，320 Kbps比特率，按每6 s等长分段，每1 s数据封装为40个包．普通节点可缓存20段数据．采用位置感知的邻居选择算法，80%的邻居在区域内选择，其余邻居从区域外挑选．向后加权LRU-K算法中，K=8，α=0．8．分布式一致算法中，节点连接度为4，步长γ为0．2，为了控制消息传输成本，算法每隔1 s才与邻居交换均值信息．实验分别从A、B、C 3区随机选取50、100、150和200个节点，在这4种规模下，各种方案运行10次，取性能平均值作比较．为了评价提出的基于局部供求平衡的数据替换策略(POP_LOCAL)，实验还实现了以下3种缓存策略:随机替换策略(Random)、按序替换策略(Sequence)及基于全局供求平衡的替换策略(POP_GLOBAL)．

4．1 播放流畅度

图3是节点规模为600节点时4种缓存方案的播放流畅度累计分布函数(CDF)．播放流畅度定义为能及时下载(未超过播放时限)的数据块数占下载总块数的比率．Sequence替换方式最差，Random次之;基于供求关系的缓存机制播放流畅度均超过90%，其播放质量均优于Random和Sequence机制．其中，POP_GLOBAL策略下，有90%的节点播放流畅度介于93% ～97%之间;而POP_LOCAL策略大大提高了用户播放质量，所有用户的播放流畅度在97%以上．因此，在节点规模较大的情况下，POP_LOCAL策略在播放质量方面优于POP_GLOBAL策略．即:局部供求模式的缓存替换策略比全局供求模式的更合理．

图3 不同方案下的播放流畅度Figure 3 Playback smooth index of different schemes

4．2 服务器负载

使用流媒体服务器的访问峰值做为衡量服务器负载的指标．在4种节点规模下，Random策略和Sequence策略的性能最差，Sequence策略的服务负载比Random的大．在小节点规模(150个)情况下，各种策略的服务负载相差不大:Sequence策略最差为 8．02 Mbps，POP_GLOBAL 最好为 6．9 Mbps．小节点规模情况下同区域内的节点无法提供节点播放所需的数据，需从其它区域下载数据，从系统全局出发替换数据可获得更好的性能，因此POP_GLOBAL的性能最优．随着节点规模增大，POP_LOCAL策略的优势越来越明显．600个节点时，POP_LOCAL的服务负载为12．43 Mbps，比 POP_GLOBAL的负载小1．17 Mbps．

4．3 数据自供应能力

定义“数据自供应指数”如下:数据自供应指数=系统中从同区域下载的数据总块数/系统中由对等交换得到(非流媒体源服务器提供)的数据总块数．指数值越大，系统数据自供应能力越强，区域间数据流动量越少，网络传输成本越低．

表1给出不同缓存方案的数据自供应能力比较情况．从趋势来看，任一种缓存策略的数据自供应能力都随节点规模的增大而增强．因为，区域节点数量增多，则在内部找到合适数据源的概率增大，数据流动性减弱．从策略比较来看，Sequence策略的数据自供应能力最差;Random次之;而POP_LOCAL能够显著提高系统数据自供应能力，多数情况下性能优于POP_GLOBAL(节点规模为150个时例外)．在600个节点的规模下，POP_LOCAL的数据供应指数高达0．32，比POP_GLOBAL高出6%．可见，在适当的邻居选择算法的配合下，在局部维持数据供求平衡，可将数据分发过程更多地控制在网络局部．

表1 不同方案下的数据供应指数Table 1 Self sufficiency ratio of different s chemes

5 结语

在P2P流媒体分发中，单纯使用拓扑一致性算法无法保证数据就近访问．而基于数据供求关系的传统缓存替换算法仅考虑数据供求数量关系，忽视了数据分布位置因素．为此，本文提出了基于局部数据供求平衡的缓存模型，利用分布式一致性算法作为数据供求统计工具，给出了该模型的分布式求解方案．仿真实验表明，基于局部供求平衡的缓存策略能有效提升播放质量，降低不同区域间的数据流量．在节点规模较大的情况下，该策略的性能优于基于全局供求平衡的替换策略．研究如何降低分布式统计供求模式的网络开销，以及不同的区域规模对缓存性能的影响将作为后续的研究重点．

［1］SHEN Z J，LUO J，ROGER Z，etal．Peer-to-peermedia streaming:Insights and new developments［J］．P IEEE，2011，99(12):2087-2088．

［2］KARAGIANNIS T，RODRIGUEZ P，PAPAGIANNAKI K．Should internet service providers fear peer assisted content distribution［C］∥ACM Internet Measurement Conference，New Orleans，LA，2005．

［3］FIORESE A，SIMOESP，BOAVIDA F．Peer selection in P2P service overlays using geographical location criteria［C］∥12th International Conference on Computational Science and Its Applications，Salvador de Bahia，Brazil，2012:234-248．

［4］CHENG B，JIN H，LIAO X F．RINDY:A ring based overlay network for peer to peer on demand streaming［C］∥Proceedings of Ubiquitous Intelligence and Computing，Wuhan，2006:1048-1058．

［5］YIUW P K，JIN X，CHAN SH G．VMesh:Distributed segment storage for peer-to-peer interactive video streaming［J］．IEEE JSel Area Comm，2007，25(9):1717-1731．

［6］陈刚，张伟文，吴国新．P2P流媒体Cache的置换算法［J］．计算机研究与发展，2007，44(11):1857-1865．

［7］WU J H，LI B C．Keep Cache replacement simple in Peer-Assisted VoD systems［C］∥P IEEE Infocom 2009 Mini-Conference，Rio de Janeiro，Brazil，2009．

［8］MEHYAR M，SPANOSD，PONGSAJAPAN J，et al．A-synchronous distributed averaging on communication networks［J］．IEEE/ACM Transactions on Networking，2007，15(3):512-520．

［9］O'NEIL E J，O'NEIL P E，WEIKUM G．The LRU-K page replacement algorithm for database disk buffering［C］∥ACM SIGMOD．Washington D．C．，1993:297-306．