一种基于激励机制的P2P流媒体数据传输策略

韩亚峰,董孝珍

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

随着P2P技术和流媒体技术的迅速发展,基于P2P的流媒体直播系统已经成为互联网的主要应用之一.为改善传统的树状结构[1]和网状结构[2]的不足,近几年来出现了分层的P2P直播系统模型,如Anysee[3]、PPLive[4]和HCPON[5]等系统,该模型在流媒体数据传输上采用分层异构的方式,提高了系统的服务质量.但由于P2P网络的复杂性、动态性以及流媒体数据量大的特点,在节点负载均衡、节点之间相互配合等方面还存在着一定的问题,这些问题影响了直播系统的播放质量以及规模的扩大.P2P流媒体直播系统中的数据传输策略正是问题的来源之一,因此对于分层P2P直播系统而言,如何通过合理的数据传输策略,在簇内进行有效的数据分发至关重要.

目前,在P2P流媒体直播系统中主要有推、拉以及推拉结合3种数据传输策略.分层结构HCPON[5]簇内采用单一的推传输机制,这种机制使得簇内数据分发较快,但NP节点资源利用率低,并且由于簇首承担了全部的数据分发功能,易引起其负载过重；分层结构PPLive系统,簇内采用单一的拉传输机制,这种机制虽然抗扰动强,NP节点资源利用率有所提高,但该机制传输时延较大,使得簇内数据分发较慢.为充分利用推拉的优点,最近在网状结构中又引入了推拉结合[2,6]的策略,如GridMedia[2].现有的数据传输策略都不能在簇首负载、数据分发速率以及资源利用率等关键性能参数之间达到很好的平衡,同时缺乏相应的激励机制,不能充分发挥P2P网络的优势.对此,本文以分层直播系统LStream为背景,设计了一种基于激励机制的推拉相结合的数据传输策略,该策略结合网状结构中推拉结合的思想,并且引入了激励机制,不但充分利用了网络资源,而且有效地防止了簇首负载过重,减轻了簇首的压力.

1 LStream设计方案

分层P2P流媒体直播系统LStream系统在管理层面上采用节点集中管理方式,整个系统部署一个服务器TrackSrv（TS）管理所有的节点信息.在数据传输上,LStream采用两层分簇架构,簇间采用应用层组播技术构造转发树,簇内基于数据驱动的思想组成覆盖网.系统中参与数据分发的节点主要包括以下几类：CS、SP、SNP以及NP.其中,CS为频道源服务器,实现视频源的编码和发送；SP由系统固定部署的可信且能力较强的节点组成,完成多频道数据的传输；SNP是由TS动态选取的节点,负责一个频道信息的转发,且两者都参与簇间转发树的构造并以簇首的身份实现对簇内NP节点的管理,簇的形成遵循地域相近频道相同的NP节点位于同一簇的原则.

在LStream系统中,SP和SNP形成的上层结构,由于较好的稳定性,采用推的数据传输策略,实现多频道的数据转发；而在簇内,节点稳定性差,采用推机制显然不合适,但拉机制又会使得簇内数据分发较慢.因此,在簇内选择和设计合适的数据传输策略,保证系统的整体性能非常重要.

2 基于激励机制的数据传输策略

本文结合LStream系统的特点,在簇内,设计了一种基于激励机制的推拉相结合的数据传输策略ICTMS（An Incentive based Tree-push/Mesh-pull strategy）,该策略充分结合推拉机制的优点,并引入激励机制.以簇为单位,簇首周期选择上传能力强的若干节点,称这些节点为簇首的逻辑子节点,簇首仅对逻辑子节点采用推机制优先进行数据推送,使得这些节点快速地获得数据并在簇内快速地分发,而簇内其他节点均采用拉机制直接或间接地从这些逻辑子节点获得数据.

2.1 簇首负载分析

为有效地防止簇首负载过重,减轻簇首的压力,需要对簇首的资源分配加以分析.在影响簇首负载的诸多因素中,带宽的均衡分配直接影响系统的播放质量.在LStream系统中,簇首主要负责为子节点和各个簇的逻辑子节点分配带宽,并且ICTMS策略用于簇内,簇首的负载主要与簇首负责的逻辑子节点总数LC有关,如果簇内逻辑子节点数过小,簇内播放质量就会很差；另外簇首管理多个簇且资源有限,如果其中一个簇逻辑子节点过多,势必影响该簇首管理的其他簇的性能,所以ICTMS策略需要解决的首要问题就是要对LC加以限制.

在LStream系统中,主要负责为子节点和逻辑子节点分配上传带宽,当簇首负责转发数据的子节点和逻辑子节点都正常播放时,实际需要的带宽B1与簇首的子节点数n、逻辑子节点总数LC和节点正常播放时簇首需要为它分配的上传带宽b有关,所以对于任意的簇首都有

假设簇首可提供的最大带宽B2是定值,子节点数n已知,并且n个子节点占用的带宽远小于B2.基于这种假设,簇首的负载仅与LC有关,当LC过小时,B1远小于B2,此时簇首带宽利用率低,簇内数据分发较慢；当LC过大时,B1远大于B2,引起簇首负载过重.所以为了有效利用簇首的资源,需要计算恰当的LC值,最佳的条件是

簇首支持的最大逻辑子节点总数应为

在LStream系统中,为充分利用簇首的带宽,尽可能地使得簇首管理的所有的簇都能正常播放,簇首在分配逻辑子节点时,遵循以下原则：先分配小簇,优先满足小簇正常播放的要求；再分配大簇,尽量使这些大簇也能正常播放.基于这种原则,对于任意的簇j,簇首都采用表达式（3）为其分配逻辑子节点数A（j）.具体思想为：比较簇j正常播放时,至少需要的逻辑子节点数B（j）和平均逻辑子节点数C（其中C=MAX（LC）/M,M 表示当前簇首管理的簇数）,如果 j是小簇,令 A（j）=B（j）,否则 A（j）等于未分配的逻辑子节点数除以未分配逻辑子节点的簇数.所以簇j实际分配到的逻辑子节点数A（j）可确定为

2.2 上传能力度量

在ICTMS中,簇内逻辑子节点的选取依据的唯一性能参数是上传能力,如何有效地度量该性能参数,使得这种度量更能充分反映节点的上传能力,是该策略需要解决的另一个重要的问题.该策略中NP节点的上传能力用单位时间内上传的有效数据分片数来表示,所谓有效数据分片是指该分片是在播放时刻之前到达的,并且为了准确地表示NP节点的上传能力,NP节点的上传能力是由邻居节点评价,即对于任意一个NP节点,当前所有的邻居节点都为它周期计算一个评价分数SCORE,并发送给簇首节点,簇首节点收集所有邻居节点对该节点的评价分数,周期计算它的上传能力UC.SCORE的计算公式

其中,节点j代表节点i的任意的一个邻居节点；SCORE（i,j）代表节点j对i的上传能力评价分数；SCORE（i,j,k）表示j从i收到的第k个数据分片的标志,如果该分片在播放时刻之前到达,则该标志为1,否则为0；PNUM代表一个周期内节点i上传给节点j的数据分片总数；NS代表节点i的邻居子节点集合.在一个周期内,节点i的总体上传能力UC（i）可确定为

2.3 算法设计

ICTMS策略中,推机制主要用于簇首向逻辑子节点传输数据.对于系统中的任意NP节点,簇首都为它维护一个上传能力参数UC,该参数周期更新,然后以簇为单位,簇首依据节点的上传能力在簇内周期选择上传能力强的若干逻辑子节点,对逻辑子节点簇首以推的方式直接推送数据,而簇内其他的节点,均采用拉的方式从邻居节点获得数据.并且为减小系统的启动时延,在ICTMS算法中,节点在刚加入系统时,在采用拉的机制从邻居节点获得数据的同时,簇首也采用推的机制为其发送最初的几十秒数据.

算法用到的参数描述,如表1所示.

表1 ICTMS算法相关参数Tab.1 Relative parameters of ICTMS

假设执行ICTMS算法的周期为T,设定时器为timer,当定时器timer为T时,对于当前簇首的管理的任意簇j,簇首都依次执行ICTMS算法,并且定时器timer清零,重新计时,具体算法：

（1）确定LStream系统中簇的划分,簇首节点以及簇内的任意节点；

（2）如果该节点为新加入系统的节点,当前簇首S采用推的机制进行前10 s的数据分发,算法结束；

（3）如果该节点为非新加入节点,簇首通过式（5）周期计算任意邻居节点对该节点的评价分数SCORE,再通过式（6）获得该节点的总体上传能力UC；

（4）对于簇内的任意非新加入节点都执行步骤3,计算该节点的UC；

（5）将簇内节点按照UC由高到低的顺序进行排序；

（6）通过式（3）和式（4）计算当前簇首支持的最大逻辑子节点总数MAX（LC）,进而得到簇实际分配到的逻辑子节点数A；

（7）从簇内节点中选出UC值最大的前A个节点作为簇首的子节点,即SNP节点,簇首通过推的机制先这A个节点进行数据分发,而簇内的其他节点,通过拉的机制从任意邻居节点获得数据.

3 实验验证

采用D_P2P_SIM作为仿真模拟工具,首先通过修改D_P2P_SIM仿真软件,构建LStream系统的拓扑结构,模拟在LStream系统的簇内,分别采用ICTMS、推和拉3种数据传输策略.实验中覆盖网的节点数目限制在0～3 000之间,播放速率为300～340 Kb/s,每个数据包大小为2 Kb,对于任意的簇首,最多管理5个簇,并且每个簇最多有30个普通节点.在拉传输机制下,缓存映射表BM的交换周期和数据请求周期假设都为1 s,每次请求2个数据包,每个数据包的大小为2 Kb,每个普通节点最多有5个邻居节点.在ICTMS算法中,比例因子N为1/2.

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

参数1：平均占用簇首带宽是簇首为自身逻辑子节点提供的上传带宽与簇首的实际带宽的比值,用来衡量簇首的压力,平均占用簇首带宽越多,簇首压力越大.

参数2：平均传输时延,是从发出数据请求到接受到该数据等待的时间,主要用来衡量数据的分发速率,平均数据时延越小,簇内数据分发越快.

参数3：节点上传带宽,即单位时间内簇内所有NP节点上传的数据包之和,主要用来衡量系统的资源利用率,节点的上传带宽越高,系统的资源利用率就高.

参数4：平均启动时延,为簇内NP节点从加入系统时刻到开始播放时刻之间的时间差.

参数5：播放流畅程度,用单位时间内节点收到的数据包数与节点连续播放所需要的数据包数比值来表示.

为避免偶然性,每个实验都经过多次测试,然后取平均值,实验结果如表2所示.

表2 3种数据传输策略比较Tab.2 Comparison of three data transmission strategies

由表2可知,在相同实验环境下,ICTMS策略平均占用簇首的带宽比推机制减少了将近20%,与拉机制几乎相等,这说明,ICTMS策略能够有效的降低簇首的负载,在一定程度上减轻了簇首的压力,有利于系统的可扩展性.在系统规模一定,运行时间相同的情况下,ICTMS的平均传输时延低于拉机制.因此,相对于拉机制,ICTMS策略簇内数据分发更快,更满足直播系统实时性的要求.在运行环境以及运行时间相同的情况下,三种数据传输策略的节点上传带宽和节点平均启动时延对比情况表明,ICTMS策略能够更好地利用节点的带宽资源,因此系统资源利用率更高,并且相对于推和拉机制,ICTMS策略下系统的启动时延更低.随着节点数目的增加,三种数据传输策略的播放质量都有所下降,但ICTMS数据传输策略的下降速度相对于推、拉机制比较平缓.因此与推、拉机制相比,ICTMS数据传输策略具有更好的播放质量,更适合大规模的应用.

4 小结

基于激励机制的推拉相结合的数据传输策略ICTMS,具有以下优点：①充分结合推拉的优点,减小了系统的数据传输时延,从而实现了簇内数据的快速分发；②引入激励机制,在簇内起到了激励作用,从而在一定程度上提高了节点的资源利用率；③兼顾了簇首节点的负载问题,将部分数据分发功能分摊到簇内逻辑子节点上,并通过对逻辑子节点数加以限制以及在各个簇中合理的分配逻辑子节点来防止簇首负担过重、有效减轻簇首压力；④相对于推、拉机制,ICTMS减小了系统的启动时延,进一步提高了系统的整体性能.

[1]Tran D A,Hua K A,Do T.Zigzag：an efficient peer-to-peer scheme for media streaming[C].Proceedings of the IEEE Computer and Communications,INFOCOM,2003：1672-1687.

[2]Xie S S,Li B,Keung GY,et al.Cool-streaming：Design,Theory,and Practice[J].IEEE Transactions,2007,9（8）：1661-1671.

[3]Liao X F,Jin H,Liu YH,et al.AnySee：Peer-to-Peer Live Streaming[C].In：Proc.of INFOCOM'06,2006：1-10.

[4]Long V,Indranil G,Jin L,et al.Mapping the PPLive Network：Studying the Impacts ofMedia Streaming on P2P Overlays[R].UIUC：Tech.Rep,2006.

[5]程普,陈越,黄平川,等.一种分层分簇的P2P流媒体覆盖网络模型[J].计算机工程与应用,2007,43（22）：140-142.

[6]Ouali A,Kerherve B,Jaumard B.Toward New Peering Strategies For Push-Pull Based P2P Streaming Systems[C].Ultra Modern Telecommunications&Workshops,2009.ICUMT'09.International Conference on Digital Object Identifier,2009：1-8.