异构环境下P2P直播流媒体调度算法研究

陈 华，宋建新

(南京邮电大学通信与信息工程学院，江苏 南京 210003)

基于“网”的P2P流媒体技术凭借其优异的可扩展性、成本低及易部署的优势，成为解决大规模流媒体应用最重要的技术途径之一［1］。其主要由两部分组成:覆盖网络创建与维护，数据块调度算法。前者指的是创建和维护覆盖网络拓扑的逻辑，后者指的是节点和邻居之间交换数据块的逻辑。数据块调度算法包含块选择算法和节点选择算法两部分。关于数据块调度算法的研究，一直受到广泛关注。从2005年开始，基于无结构网络的数据驱动(Data－Driven)、基于“网”(Mesh－based)、基于蜂群算法(Swarmingbased)或者基于“拉”式(Pull－based)的调度策略(例如Chainsaw［2］，CoolStreaming［3］，PRIME［4］等)被相继提出。该类型的协议在覆盖网络构建方面，采用随机选择邻居节点的策略，用以构造连接度较高的无结构网络。在流媒体传输方面，主要采用类似Bit－Torrent等文件共享系统传输策略，媒体流被切分成数据片段(Segment或者Block)，每一个节点周期性地向其邻居节点通知它当前拥有的数据片段。与此同时，每一个节点根据其邻居节点的通知，直接向邻居节点周期性地请求它所缺少的数据片段。而节点之间是通过Buffer Map或者其他类似机制来相互通知当前拥有哪些数据片段［5］。Buffer Map中每一位均表示某一个数据片段是否在当前缓存区。虽然核心思想简单，但却有着可扩展性强、稳健性高、实现简单等优点。

以上所提到的文献是由接收端发起数据块调度，同样也可以由发送端来发起数据块调度。文献［6］根据数据块调度算法是由发送端发起还是由接收端发起将其分为“推”和“拉”两大类。近期也有大量的文献对基于“推”策略的算法进行研究，如文献［7－9］等。基于“推”的策略更适合于上行带宽受限的系统，因为其可以根据自身的上行带宽来调整块的发送速率;基于“拉”的策略更适合于下行带宽受限的系统，因为块的请求速率可以根据自身下行带宽来自适应地调整或者优先请求接近播放延时的块。若上行带宽和下行带宽相同，这两种策略的效果是一样的，但是，在现实的网络环境中更容易出现的是上行带宽受限的场景，所以，基于“推”的策略更具一般性。

本文提出一种带宽感知的数据块调度算法，通过优先选择高上行带宽的节点为目的节点，以便其尽可能地为其他节点服务，从而提高系统的性能。

1 系统模型及相关标识

考虑一个基于块的系统，在系统只有一个源节点，源节点产生一定速率的数据流，并将其切割成固定大小的数据块，见图1。

用P表示节点集合，N为节点总数(不含源节点)，Bp表示节点p∈P的上行带宽，Bs表示源节点上行带宽。C(p)表示节点p接收到的块集合，N(c，p)表示仍缺少块c的邻居节点集合。覆盖网络由无向图G(V，E)表示，其中，当且仅当p∈P和q∈P是邻居关系时，(p，q)∈E。数据块大小为L(单位bit)，源速率为l，块传输过程由节点块数据调度算法完成，且每个节点每次只发送一个块给其邻居节点。

图1 系统模型示意图

2 基于带宽感知的数据块调度算法

数据块调度算法由两部分组成:块选择算法和节点选择算法。本文提出的算法LU/WP中块选择算法采用最近有用块优先(LU)，节点选择算法是以正比于邻居点的上行带宽的概率来选择目的节点。

具体描述为，发送节点p从其收到的数据块集合C(p)中选择满足条件N(c，p)的最近数据块c作为待发送的目标块。具体的目的节点选择算法为，缺少数据块c的邻居节点以概率pq被选择为目的节点，其中

式中:N(c，p)为不含数据块 c的邻居节点集合，ωq=f(Bq)=Bq。算法的伪代码可参考:

为了更清楚地解释所提算法，下面将结合图2来说明算法LU/WP完成一次调度的过程。假设调度过程由节点A发起，D1，D2，D3，D4，…为其邻居节点，并且各节点拥有的块如图2所示。

以图2为初始状态的LU/WP算法的具体调度过程为:

1)选择最近有效数据块5作为待发送的块，然后判断是否有邻居节点缺少块5，经分析发现D1，D2，D4节点缺少数据块5，D1，D2，D4成为候选目的节点。

2)根据D1，D2，D4的上行带宽，分别赋予其权值

图2 某一时刻节点A及其邻居节点所拥有的块集合示意图

4)发送数据块给目的节点。

3 性能评价

本文利用一个专门开发用于P2P流媒体系统研究的仿真平台P2PTV－sim来验证算法的性能。将基于带宽感知的算法与传统的LU/RP(最近有用块优先/随机节点选择)算法进行比较。通过对P2PTV－sim源文件中的Config.txt文件对实验场景进行了设置。节点数(不含源节点)Np=5000 ，传输的数据块数Mc=300，块长度L=100 kbit，数据源速率l=1 Mbit/s，服务器上行带宽Bs=10 Mbit/s，回放延时PlayoutDelay=5 s，节点出度outdegree=20。

3.1 场景一

上行带宽均匀分布于［0，Bmax］，平均带宽为=Bmax/2 。考虑上行带宽提供率 r={1.0，1.2，1.4，1.6，1.8，2.0}的情况，r的不同代表着系统的负载不同。实验结果如图3所示。

图3 均匀分布场景带宽提供率对平均块延时的影响

观察图3可以看出，随着带宽提供率的增大，LU/RP和LU/WP算法的平均块传输延时都在下降，但是LU/WP算法的平均块传输延时明显小于LU/RP算法，说明LU/WP算法的性能更优。

3.2 场景二

异构环境中，节点被分为3类，即

在该场景下做了两组实验:一组是上行带宽提供率为 r=1 ，异构度 h={0，0.2，0.4，0.6，0.8，1};另一组是上行带宽提供率为 r=1.4 ，异构度h={0，0.2，0.4，0.6，0.8，1}。实验结果如图4和图5所示。

观察图4和图5可以发现，无论是在带宽提供率为1还是1.4的情况下，LU/RP算法的平均块传输延时都呈增大趋势，而LU/WP算法的平均块传输延时呈下降趋势。这是由于，随着异构度的增大，高上行带宽和低上行带宽节点都将增加，随机选择算法，优先选择到低上行带宽的可能性也在增加，所以性能急剧下降。相反，LU/WP算法则总是优先选择高上行带宽的节点，随着高上行带宽节点增加时，其性能显著提升。可以看出，通过优先选择高上行带宽节点可以改善系统的性能。

4 小结

本文对P2P直播流媒体系统中关键组成部分之一的数据块调度算法进行了研究。提出一种基于带宽感知的数据块调度算法，即让发送节点优先选择高上行带宽的节点作为目的节点。通过仿真发现，基于带宽感知的数据调度算法的平均块传输延时更小。平均块传输延时是P2P流媒体系统最重要的性能指标，故在设计数据块调度算法时充分利用网络环境的异构性能可有效地提高系统的性能。

［1］詹晓涛.CDN与P2P相结合的流媒体系统设计［J］.电视技术，2009，33(6):67－70.

［2］PAI V，KUMAR K，TAMILMANI K，et al.Chainsaw:eliminating trees from overlay multicast［C］//Proc.IPTPS.［S.l.］:Springer，2005:127－140.

［3］ZHANG Xinyan，LIU Jiangchuan，LI Bo，et al.CoolStreaming/DONet:a data－driven overlay network for efficient live media streaming［EB/OL］.［2011－07 －01］. http://www.cs.sfu.ca/～ jcliu/Papers/CoolStreaming.pdf.

［4］MAGHAREI N，REJAIE R.Prime:peer－to－peer receiver－driven meshbased streaming［J］.IEEE/ACM Transactions on Networking，2009，17(4):1052－1065.

［5］郑小乐.对等网络流媒体数据协作传输研究［D］.合肥:中国科学技术大学，2009.

［6］BONALD T，MASSOULI L，MATHIEU F，et al.Epidemic live streaming:optimal performance trade－offs［EB/OL］.［2011－07－01］.http://www.cs.ox.ac.uk/people/andy.twigg/papers/sigmetrics08.pdf.

［7］SANGHAVI S，HAJEK B，MASSOULIE L.Gossiping with multiple messages［J］.IEEE Transactions on Information Theory，2007，53(12):4640－4654.

［8］MASSOULIE L，TWIGG A，GKANTSIDIS C，et al.Randomized decentralized broadcasting algorithms［C］//Proc.INFOCOM 2007.［S.l.］:IEEE Press，2007:1073－1081.

［9］ABENI L，KIRALY C，LO C R.On the optimal scheduling of streaming applications in unstructured meshes［C］//Proc.8th International IFIPTC 6 Networking Conference.Berlin:Springer－Verlag，2009:117－130.