P2P流媒体数据调度策略研究

韩亚峰（河南科技学院,河南新乡,453003）

P2P流媒体数据调度策略研究

韩亚峰
（河南科技学院,河南新乡,453003）

数据调度算法是P2P研究的热点问题.算法性能的优劣会直接影响到P2P系统的服务质量.通过分析P2P流媒体直播系统中节点能力和数据分片的优先级,提出了最少最小优先调度算法（LRFA）.算法结合了现有的最少优先策略,将数据的稀缺性和时间特性作为重要因素,对节点能力进行了动态估算,最终实现了节点资源的充分利用.

P2P网络；数据调度；数据优先级；稀缺优先；节点能力

近年来基于P2P技术的流媒体应用已成为研究热点[1].P2P流媒体系统中普通主机节点（对等节点,简称Peer节点）从其他Peer节点获取流媒体数据的同时,也承担起为其他Peer节点转发数据的任务,充分利用了空闲的网络、计算、存储等资源,从而使服务器上网络带宽资源消耗大大减少,局部网络的拥塞也相应减少,使系统可扩展性提高,性价比增强.视频直播系统中Peer节点存在带宽、处理能力等方面的差异性,而其作为普通主机节点,服务能力有限,却要承担大量、长时间的流媒体数据处理转发任务,需要面对诸多的困难和挑战.合理的数据调度策略可以解决这些问题,为用户提供高质量的流媒体服务[2].

目前P2P数据调度策略已有一些成熟的研究成果.传统的数据调度策略主要有稀缺优先策略（Local Rarest-firststrategy）、随机策略（pure random strategy）和循环鲁棒策略（Round-robin strategy）.在CoolStreaming中采用的稀缺优先策略,时间响应速度快,但是时间相关的计算依赖于节点之间的带宽的计算.Chinasaw采用随机策略,但这种策略在异构的网络环境中效果差,性能不稳定,不适合用于基于DONet的系统[3].在分层流媒体系统PALS中采用了循环鲁棒策略,较好地实现了节点的负载平衡,但是节点之间带宽的计算复杂,不易实现.为了解决传统算法中存在的问题,本文设计了一种基于DONet系统的数据调度算法,能够适应网络的动态性和异构性,易于实现.

1 P2P流媒体数据调度算法

1.1 数据的表示

流媒体系统中将数据按播放时间进行分片,使得每个数据分片大小相同,为每个数据分片分配一个唯一递增的序号,每个数据分片代表T/ms的数据.系统中用一个滑动窗口来表示缓冲区,缓冲区中是否拥有某个分片的数据可以用缓存映射BM（Buffer Map）来表示[4].缓冲区中数据当前播放位置tp可以分为已播放数据和未播放数据两部分.为了给伙伴节点进行数据转发,已播放数据没有被立即丢掉,而是在缓存中保存一段时间；为了本节点流媒体的正常播放,需要在缓存中保存接收到的即将要播放的数据分片,即未播放数据部分.用播放生存期（playback deadline）来表示当前时刻距离播放该数据分片的时间长短,所以当前时刻正在播放的数据分片的播放生存期为0.缓冲区每隔一段时间就会发出一次数据请求,请求的数据范围为滑动窗口的滑动步长,将此区域的数据称为交换窗口,每次只向邻居请求交换窗口中缺少的数据分片.假设从邻居节点请求并获得数据分片的时延R很小（R＜＜T）,那么下一个时间间隔请求调度的数据分片范围为tp时刻后的数据,为了反映交换窗口中不同位置的数据分片对时间的要求不同,将其分成两部分：紧急区域和非紧急区域,前者指位于交换窗口中播放位置附近的数据部分,后者是指相当长一段时间后才会播放的数据区域,缓冲区中数据的结构如图1所示.理想的数据调度过程,每次只需请求非紧急区域中的数据分片,保证使该区域数据在进入紧急区域时,已经全部到达缓冲区.

图1 缓冲区数据结构Fig.1 Bufferdata structure

1.2 数据的优先级

在P2P系统中,不同的数据分片的重要性是不一样的,一些分片仅有少数的邻居节点拥有,相对稀缺,为了快速增加这些分片的副本,必须优先请求调度.BT文件下载过程,为了提高整体的下载速率,就是采用这样的算法（RarestFirst）.我们可以根据分片的重要性为它定义不同的优先级,用优先级的高低来表示对应分片的重要程度,该数值越大,说明该分片越重要,在调度过程中必须优先调度[5].把稀缺性（Rarest）作为优先级定义的一个重要考虑因素.其次流媒体系统的一个重要特征是对数据有严格的实时性要求,用播放生存期（playback deadline）来反映数据分片时间上的紧急程度,播放生存期数值越小,表明该数据越紧急,相应的优先级也应越高.最终把稀缺性和实时性作为决定数据分片优先级的因素,定义数据分片优先级的计算公式为：

其中s=（sreq-smin）/size,系数α的取值范围[0,1],α具体的值在1.4中给出.PR（*）表示数据分片的稀缺性,是一个单调递减的函数,当r=1,…,5时,PR（r）=106-r,否则PR（r）=1.Σhkj表示节点i的邻居节点中持有数据分片j的节点的个数；第二项PE（*）表示数据分片的实时性,也是一个单调递减的函数,当0≤s≤1时,PE（s）=101-s,否则PE（s）=1.参数的含义如表1所示,假设调度窗口大小为15 s,每个数据分片为500 ms,那么size=30.

表1 数据分片相关参数Tab.1 data segmentrelated parameters

1.3 节点能力的计算

流媒体系统中每隔一个调度周期,Peer节点就会向邻居节点请求一次数据.为了在最短的时间里正确完整地接收到请求的数据,应该选择邻居节点中能量强的进行数据请求.Peer节点并不能完全占用邻居节点的资源,因为邻居节点可能同时要给多个请求节点发送数据,所以它只能分配部分能力给每个请求的Peer节点.系统中Peer节点请求的数据分片可能被多个邻居节点同时拥有,此时Peer节点可以通过计算分配给自己的能力（简称节点能力）,然后选择节点能力大的进行请求.这个能力是个动态变化的值,受多方面因素的影响,包括请求节点的下载带宽、邻居节点的上传带宽、请求节点个数、链路瓶颈等.用传统的方法实时测量开销太大,所以可以依据最近的数据传输情况对节点能力进行实时估算.计算节点能力用到的参数如表2所示.

表2 节点能力相关参数Tab.2 node capability related parameters

初始化CapaAB为Min（OutBandA/num,InBandB,LinkA-B）,可以利用节点B在每个调度周期,都会向邻居节点请求一次数据信息的机会,对邻居节点的能力进行估算.用数据分片的个数作为节点能力的计量单位,因为流媒体系统中数据分片的大小基本相等.节点能力的计算函数如下所示：

CalculateCapa（）

{dataReqNum；

dataRecNum；

if（dataReqNum==0）//第一次向该邻居请求数据分片

CapaAB=Min（OutBandA/num,InBandB,LinkA-B）；

return；

if（dataReqNum==CapaAB）CapaAB=dataRecNum；

}

算法中用dataReqNum保存上次请求的数据分片的数目,因为每次请求数据分片的数量肯定小于节点的能力,所以这个数值一定小于上次估算的该节点的能力.用变量dataRecNum保存上次数据请求发出后,实际接收到的数据分片数量,该算法通过比较dataReqNum与邻居节点能力之间的数量关系,如果小于,估算邻居节点的能力不变,如果相等,那么接收到的数据分片的数量dataRecNum就是此次估算的邻居节点的能力.

1.4 LRFA（LeastRarestFirstScheduling Algorithm）调度算法

系统中一些数据分片副本数量少[6],主要有以下两种情况：①该数据分片在当前节点中接近播放位置,序号较小,在一些邻居节点的缓冲区中已被丢弃；②该数据分片在当前节点中距离播放时刻还有较长时间,序号较大,是一个相对较新的数据分片.只有数据源节点和与源节点直接相连的少数伙伴节点持有这个数据分片,在很多邻居节点的缓冲区中都没有该分片,在带宽有限的情况下,应该首先请求第一种情况,否则可能会导致紧急区域的数据分片在播放以前不能到达.而第二种情况,随着播放时间的推移,这些新的数据分片会被广泛传播.

为了反映节点当前的数据传输任务,避免节点负载过重,为每个节点定义了接受请求数aep_num.接受请求数的值随着数据请求数量的增加而增加,之后每完成一个数据传输任务就减1.算法还考虑到缓冲区紧急区域中数据分片的实时性要求高,优先放入请求队列.具体算法如下：

（1）计算紧急区域中空缺的数据分片的优先级,公式中α=1/2,稀缺性和实时性并重.将数据分片按照优先级数值由高到低排序,之后放入数据请求集合ReqCollection中；

（2）计算非紧急区域中空缺的数据分片的优先级,置α=1,只考虑稀缺性.按照优先级由高到低,放到请求集合ReqCollection中.若请求集合ReqCollection中的数据分片的数量大于设定值,则结束第2步；

（3）调用函数CalculateCapa（）,计算每个邻居节点能力；

（4）按顺序从请求队列中取出数据分片,向拥有该数据分片并且aep_num最小的邻居节点发出数据请求.若aep_num相等,向能力最大的邻居节点请求.将该数据分片的序号放入该邻居节点的请求队列ReqQueue中；

（5）继续第（4）步,直到请求集合ReqCollection中的数据都处理完毕,将数据请求集合ReqCollection清空；

（6）将节点的请求ReqQueue转化成消息发送给邻居,记录该节点本次请求的数据分片数dataRequestNum.

2 实验分析

2.1 问题描述

为了验证数据调度算法的性能,通过改变系统的规模、节点播放速率和系统的运行时间,利用仿真方法进行了模拟实验.算法环境设置：缓存大小为1 min数据量,数据调度周期为1 ms,交换窗口大小为10 ms数据量.

为了评估算法的优劣,主要考虑了3个关键的参数：

参数1：播放停顿频率（playback freeze frequency）,为节点播放视频过程中,单位时间内停顿的次数,即播放停顿的总次数与节点生存时间的比值.

参数2：传输时延（packetlatency）,是从发出数据请求开始计时,到接收到该数据分片的时间,即节点接收数据的等待时间.

参数3：传输率（delivery ratio）,为播放生存期内到达的数据分片的数量与接收的总数据分片数量的比值,反映数据分片有效到达的情况.

将LRFA算法和LRF、Random、Round-Robin算法进行了对比实验,通过改变运行时间、系统规模和播放速率,分别测得系统的播放停顿频率、传输时延和传输率.实验节点300个,播放时长1 h,多次运行,得到的参数平均值见表3.

表3 4种调度算法比较Tab.3 Fourscheduling algorithms comparison

由表3可知,LRFA算法与其余3种算法相比,在播放停顿频率、传输时延、传输率参数方面,均表现出了更好的性能.

3 结论

本文提出了一种最小最少优先的数据调度算法LRFA,解决了当前数据调度算法中不能适应网络动态性和异构性的问题.算法中对缓冲区紧急区域和非紧急区域中数据分片进行优先级的计算,按照数据分片优先级由高到低的次序进行请求.为了节点负载平衡,选择传输任务小并且能力强的邻居节点进行数据请求.经仿真验证,该算法能为用户提供高质量的流媒体服务,具有实用价值.

[1]许建真,许密画,张福炎,等.基于优先级的应用层组播的分层结构模型[J].计算机应用研究,2008,25（5）：12-15.

[2]罗建光,张萌,赵黎,等.基于P2P网络的大规模视频直播系统[J].JournalofSoftware,2007,18（2）：391-399.

[3]Pai V,Kumar K.Chainsaw：Eliminating trees from overlay multicast[C/OL].（2007-09-01）[2012-10-12].http：//mnl.cs.sunysb. edu/home/vinay/papers/chainsaw-iptps.pdf.

[4]吴桂芳.高性能P2P Streaming分发系统模型的研究[J].计算机工程,2007（8）：51-53.

[5]Zhang M,Xiong Y,Zhang Q,et al.Optimizing the Throughput of Data-Driven Peer-to-Peer Streaming[J].IEEE transactions on paralleland distributed systems,2009（1）：97-109.

[6]孙名松,周红敏,唐亮.一种自适应的P2P流媒体数据调度算法[J].计算机应用,2008（3）：558-567.

（责任编辑：卢奇）

Research on data scheduling strategy for P2P media streaming

Han Yafeng
（Henan Institute ofScience and Technology,Xinxiang 453003,China）

Data scheduling algorithm is a very important issue in P2P research,which affects the quality of P2P media streaming．By means of analyzing node capability and data's priority in system,combined with Local Rarest First strategy,the Least Rarest First scheduling algorithm is given that used in P2P live media streaming．The data' rarest and emergence were considered as main factors,estimated the node'upload capability and realized efficiency utilization for node resources．

P2P network；data scheduling；data's priority；rarest first；peer's capability

TP393

A

1008-7516（2013）01-0086-05

10．3969/j．issn．1008-7516．2013．01．021

2012-12-10

韩亚峰（1984-）,女,河南洛阳人,硕士,助教．主要从事P2P技术应用和多媒体技术研究．