P2P流媒体中动态分级传输模型及传输算法
刘衍珩, 李松江, 王爱民
吉林大学 计算机科学与技术学院,长春 130022

作者简介:刘衍珩(1958-),男,教授,博士生导师.研究方向:网络通信与协议设计.E-mail:yhliu@jlu.edu.cn

摘要

针对流媒体直播系统中因带宽利用率低带来的传输延迟过高的问题,提出了根据节点上传带宽进行动态分级的传输模型。给出了模型初始分级及动态调整的量化依据和方法,并设计了在该模型下的并发传输算法。同级节点并发地进行数据主动传输,同时每个级别节点以几何增长率产生种子并不断向其直接下级节点发送,不断加速该级别节点内部的并发传输,从而实现了带宽的最大化利用并降低了传输的整体延迟。与现有的传输算法进行了仿真对比,结果表明:并发传输算法在将数据内容切分到足够多的份数时,数据块传递到全部节点所花费的总时间单元及节点耗费的平均时间单元均最少。

关键词: 计算机应用; P2P流媒体; 动态分级传输; 传输算法
中图分类号:TP391 文献标志码:A 文章编号:1671-5497(2016)01-0259-06
Dynamic layering model and transmission algorithm in P2P live streaming system
LIU Yan-heng, LI Song-jiang, WANG Ai-min
College of Computer Science and Technology, Jilin University, Changchun 130012,China
Abstract

To solve the transmission delay exorbitant problem in P2P live streaming system, we develop a dynamic layering model based on the uploading bandwidth of peers, and introduce its quantitative basis and method of the initialization and dynamic adjustment. Based on this model, we propose a new parallel transmission algorithm. Meanwhile, each layer of the peers generates seeds at geometric growth rate and transmits them to the lower layer continuously. In mathematical modeling analysis, when the parallel transmission algorithm divides the data content into sufficient units, the total time unit and average time unit costs for transmitting the data content to all the peers are better than the existing transmission algorithm.

Keyword: computer application; P2P live streaming; dynamic layering model; parallel transmission algorithm
0 引 言

流媒体应用正逐渐成为互联网的重要应用之一, 但传统的客户端/服务器结构在流媒体应用上, 由于带宽的瓶颈无法响应全部用户的流媒体观看请求[1]。相反, P2P流媒体则在学术界引起了广泛关注, 因为P2P流媒体的基本目标就是将流媒体内容在播放期限前从视频源头传递给全部节点[2]。像视频会议这样的应用, 要求播放延迟被控制在几百毫秒之内, 其余的应用如网络电视, 容忍度略高, 但也不能在直播中出现几分钟的播放延迟。

针对P2P流媒体存在的延迟问题, 有很多学者进行了研究, 文献[3]列举了播放延迟产生的原因, 并给出了在不同结构下P2P流媒体的播放延迟表现; 文献[4]给出了树的形状对于播放延迟的影响。文献[5]通过建立稳定节点层来消除因节点的频繁进入及离开对于播放延迟的影响。文献[6]则针对P2P流媒体性能提出了分析模型, 主要研究了节点随机的加入和离开网络时, 系统中的各个元素如何影响流媒体系统性能。文献[7]针对单树结构、多树结构进行了对比分析, 并提出了一种雪球传输方式。文献[7]中单树结构、多树结构及雪球传输3种方式在N个节点组成的系统中, 传输一个数据块的平均延迟分别为(N+1)/2、 (m+1)/(2log2m)log2N+O(1)、log2N+1。可以看到雪球结构针对单数据块传输要远远优于其他两种传输结构, 但是对于持续传输数据块的情况, 需花时间找到相对空闲的节点来进行新数据块的传输, 否则会影响到旧数据块的传输效率[8]。文献[7]只给出了该调度算法存在的证明, 并没有给出该调度算法的具体实现过程。

本文提出了一种新的动态分级传输模型, 该模型根据节点的上传能力对节点进行分级, 保证上传能力强的节点级别靠近服务器, 获得较低的块传输延迟。同时为了避免分级可能导致的上传带宽浪费或不足的情况发生, 建立了动态分级的机制并给出了动态调整的方法和量化依据, 避免了优秀节点成为搭便车节点的可能。在该模型的基础上进一步提出了并发传输算法, 同级节点间相互协作并发传输, 每个级别以几何增长率产生并发种子并不断向其直接下级节点发送从而实现了级别之间的宏观并发传送, 并在同级节点完全遍历后转而全力开始下级节点的单向传输, 降低了传输的整体延迟。

1 动态分级传输模型

动态分级传输模型及相关假设和本文所用到的符号如下:r为视频速率; N为节点个数; us为流媒体服务器上传带宽; i为级别标识, 服务器处于0级; ni为级别i中的节点数量; ui为级别i中节点的上传带宽; mi级节点可向上访问的级别数量; li为级别i中全部节点所提供的带宽和; di为级别i中全部节点所消耗的带宽和; si为级别i中节点剩余带宽; c为视频内容切割份数; T为数据块传递到全部节点所需时间单元; D为数据块传递的平均延迟; x(i)为第i级别的节点数量; Ks为服务器带宽增长倍数; K1为上传带宽速率大于r的节点带宽增长倍数; K2为上传带宽速率小于r的节点带宽增长倍数; Z(i)为单个时间单元内传输的节点数量。

对于网络场景, 做了如下假设:①节点拥有足够的下载带宽, 上传带宽则受到限制, 是整个系统的瓶颈; ②节点的上传带宽被认为是已知的, 每个节点有能力连接多个节点; ③不限制节点的网络拓扑结构及实际位置, 忽略节点间传输的延迟差异。

动态分级传输模型描述如下:

(1)在节点加入网络时, 根据节点的上传带宽进行分级。所有上传能力小于r的节点统一划分为最后一级, 可得u1> u2> > r> ui

(2)节点可以与同级节点建立关联。

(3)节点默认允许访问上一级节点, 同时也可以动态调整访问级别, 调整的级数m根据每级节点的剩余带宽来进行计算。级别i-m节点的剩余带宽在大于0的同时, 还需要满足式(1), 即si-m同直到si-1的各级别上传带宽之和, 要不小于消耗带宽之和。

si-mx=i-m+1i-1(dx-lx)(1)

m的初始值为2, 当满足式(1)时, m的值加1, 再次进行判断, 直到不满足式(1)为止。如果m为2时不满足式(1), m保持1的状态。由此, 可以计算得出第i级别能向上调整的最大层数m。随着节点的动态加入和离开, 一旦出现不满足式(1)的情况, 即上层节点的剩余带宽不足以满足该层节点的下载需要时, 需要将m减1, 直到重新满足式(1)为止, 以此来保证上级节点带宽的合理配置。

(4)上级节点可向下级节点传输数据, 但是下级节点不向上级节点传输数据。

模型中按照节点的上传带宽能力划分了不同层次, 旨在实现传输初期的层内并发传输和层间并发传输, 以降低传输的整体延迟。在传输的中后期, 上级节点全部遍历后将全力发起对下级节点的单向传输。节点的延迟大小直接受其所在层次的制约, 在动态分级传输模型下, 可以动态调整上传能力大的节点与服务器间隔级数, 保证其最小。从而减少上传带宽大的节点从服务器获得数据需要花费的时间单元, 并可以将接收到的数据传递给更多的节点, 使得数据在整个系统中传递的总次数降低, 也就降低了整个系统的平均延迟。同时, 因为上传能力强的节点会不断被调整到模型上层, 其上传能力始终得到充分利用, 保证了此类节点带宽的最大化利用。

2 并发传输算法

在动态分级传输模型的基础之上, 提出了一种同级节点内并发传输、不同级别间也并发传输的算法。

假设将数据内容平均分割为c份, 那么一个节点获得一个完整数据内容的过程, 可以转化成一个节点从其他节点接收c-1个分组内容, 并合并为一个完整数据内容的过程。算法的步骤如下:

Step 1 服务器获得一个数据块内容; 服务器将数据块分割为c个分组内容, 当一个时间单元为1 s时, 每个分组内容的大小为r/c

Step 2 服务器选取c个节点; 服务器在一个时间单元内, 将c个分组内容分别传输给c个节点。

Step 3 每个节点从同级别但获取不同分组内容的c-1个节点接收其余分组内容, 同时向这c-1个节点同步传输自身拥有的子数据组。

Step 4 每个节点同时选择下一级别的M个节点传输自身拥有的分组内容; 其中

M=(u-r)c/r+1

这里r为定值, 可以看出M的大小同节点的上传能力及c的大小相关, M越大算法的整体效率越高。

Step 5 重复Step 3和Step 4。

Step 6 当包括最下一级节点在内的所有请求节点全部接收到完整的数据块内容, 则本轮传输结束。

因为每次都按照上传带宽最大容量向多个节点主动同步传输相同数据, 与依据请求产生的随机传输相比更有效地利用了节点的上传带宽。基于动态分级传输模型的支持, 同层内节点之间实现并发传输; 同时, 上下两级的节点之间以M作为放大倍数不断地并发传输数据, 达到了传递种子启动不同级别之间的并发传输的效果, 而且伴随着当前级别之间节点传输的倍数放大, 种子被传递的数量也随之增大, 几何级提高了整个网络所有级别内部的数据传输速度, 实现了层间的整体并发传输; 当上层全层节点均获得所需要数据后, 这部分优秀节点将全力发起对下层节点的单向传输, 实现了高带宽节点对弱节点带宽的有序支援, 可以最大化地利用整体带宽, 降低整体延迟水平。

2.1 流媒体系统中的数据块传输

在流媒体系统中, 流媒体速率r可视为服务器每个时间单元都需要发送r个新的数据块, 则每个节点为了能够流畅播放, 需要在每个时间单元都接收到r个新的数据块。将一个时间单元内获得的r个数据块分成c组, 将每组数据块传递给一个节点, 最终组合成r个数据块。如图1(a)所示在时间单元0时, 源节点向第一级的4个节点传输数据块组。图1(b)显示在时间单元1时, 第一级的4个节点间互相传递数据块组、并分别向第二级4个节点传输数据块组的过程。图1(c)显示在时间单元2时, 第二级的4个节点间互相传递数据块组、并分别向第三级的4个节点传输数据块组的过程。

图1 并发传输算法传递示意图Fig.1 Data block parallel transmission

每个节点要向与它同级的c-1个节点及下一级的一个节点传输一个数据块组, 需要节点具有能在一个时间单元内对外上传r个数据块的能力。假设节点具备这样的上传能力, 那么第i级节点的节点数量x(i)=c× i, 当T=N/c个时间单元后, 全部节点可以获得全部的数据块组, 其中平均延迟D为:

D=1N1+i=1T-1(i+1)c+(T+1)(N-x(T-1))

N=TC时, D为1/N+N/(2c)+3/2。由此可以看出并发传输方式能够完全适应流媒体系统中持续数据块的传输。在实际的流媒体系统中, 节点的上传能力不一定总是宽裕的, 接下来将讨论并发传输算法如何适应节点上传带宽不足的情况。

2.2 数据块的丢失

在P2P流媒体系统中, 数据块的丢失是不可避免的。节点从上一级的节点中可以获得1个数据块, 并从同级节点中获得c-1个数据块。定义最大的数据包丢失概率为p, 那么节点肯定可接收到(1-p)× c个数据块。在MDC编码或者SVC编码[9, 10]中, 只要概率p不大于编码所能承受的丢包概率, 则节点可以忽略此次丢包。

另一方面, 节点可以同网状结构中的节点一样, 以“ 拉” 的形式根据动态分级模型从上级节点处获取数据块, 这同网状结构节点的数据块获取过程是一样的。因此, 个别数据包的重传不会影响到节点的视频观看。

3 在复杂情景下的并发传输算法

在实际情况中, 根据节点的上传带宽能否达到媒体播放速率r, 将节点分为上传能力大于r的节点和上传能力小于r的节点。认为上传能力大于r的节点带宽是rK1倍, 上传能力小于r的节点带宽是rK2倍, 服务器的上传带宽是rKs倍。

3.1 节点上传能力大于r

服务器的带宽增加了Ks倍, 按照并发传输算法的描述, 在第1个时间单元结束时, 会有Ksc个节点获得完整的数据内容。可以得到:

x(i)=Ksc× i

T=N/(Ksc)

D=1/N+N/(2Ksc)+3/2

N一定的情况下, 服务器带宽的增加, 可以为上层全部节点带来Ks倍的时间缩短。如果将节点的上传带宽增加K1倍, 那么每个节点在接收到数据块后, 可以再向K1c个节点传输数据块, 其中包含c-1个同级节点, (K1-1)c+1个下级节点, 即相当于下一层节点相对于上一层节点增加了(K1-1)c+1倍。那么可以得到:

x(i)=Ks k=1i(K1c-c+1)

当时间T= log(K1c-c+1)(N(1+K1)/Ks+1)时, 全部节点获得完整数据内容。此时, 平均下载时间为:

D=1/N{1+Ksc i=1T-1(i+1) (K1c-c+1)i-1+

T(N-x(T-1))}。

N=Ksc(1-(K1c-c+1)T-1)/(1-(K1c-c+1))时:

D=1N{1+Ksci=1T(i+1)(K1c-c+1)i-1}

当节点带宽增加K1倍时, 相当于服务器带宽增加Ks倍, 每级节点由Ksc× i增加为 (K1c-c+1)i-1, 所花费的时间单元也由N/Ksc变为 log(K1c-c+1)(N(1+K1)/Ks+1), 这两个表达式的值接近对数关系, 由此可以看到, 增加节点上传带宽带来的性能提升, 要远远优于增加服务器带宽带来的性能提升。因此, 将节点进行分级管理, 令上传带宽大的节点处于上层位置, 可以充分发挥这些节点的带宽优势, 从而提升数据块的传递效率。

3.2 节点上传能力小于r

当节点的上传能力小于r时, 节点缺乏将自身的数据块同步传递给其他c-1个节点的能力。节点此时只能向同层的节点发送数据块组, 同时不可能向下层节点发送数据块。为了弥补缺失的上传带宽, 这类上传能力小于r的节点, 需要从上层上传能力大于r的节点处获取更多的数据块。如图2所示, K21节点, 它除了从K11、K23、K24节点获得数据外, 还需要从K13节点获取数据, 以弥补因为K23节点的上传带宽不足导致的数据块缺失问题。

图2 下层节点从K1节点获取数据块示意图Fig.2 Last layer nodes obtain media chunk from K1 node

所有的上层节点的上传带宽总是会被下级节点完全占用。而所有的下层节点的上传带宽也全部被使用了。满足整个网络能够流畅播放的条件为上传总带宽大于等于下载总带宽。在T+1时刻上传总带宽等于下载总带宽。如果下层节点的数量增加, 则会出现上传总带宽小于下载总带宽的情况, 则不能满足新增节点的正常播放。

设在T时间单元, 有Ksc (K1c-c+1)T-1个上层节点拥有相同的数据块组, 在T+1时间单元里会向x个下层节点传输数据。那么这x个节点在T+1时间单元可以向同层的节点传递K2cx个数据块组, 并需要从其他c-1个节点下载数据。那么这x个节点同上层节点的上传带宽之和应该满足x个节点的下载需要。

Ksc (K1c-c+1)T+K2cx=cx

x=Ks (K1c-c+1)T/(1-K2)

Z(T+1)=cx=Ks (K1c-c+1)T/(1-K2)

所以下层节点的最大值为:

Ks(K1c-c+1)T/(1-K2)

即所有的节点在T+1时间单元时, 即 log(K1c-c+1)(N(1+K1)/Ks+1)+1时刻, 获取了全部的数据块。

普通的P2P流媒体系统因为不存在分层这样的处理, 对于节点的延迟就无法按照上述公式进行精确控制, 其延迟可能被加大。同时对于上传带宽大的节点, 会因为整体延迟过高而延迟至下轮传输开始, 导致无法向其他节点提供有效的数据块, 降低了整体网络的带宽利用率。在并发传输算法中, 上述两个问题都得到了有效的避免。

4 对比和分析

将并发传输算法同目前单数据块传输效果最好的雪球传输方法分别在单数据块传输、流媒体系统传输的情景下通过数学建模进行分析对比。

节点上传带宽为1时, 雪球方式与并发传输算法所消耗的时间单元及节点平均延迟如表1所示。

表1 雪球传输算法与并发传输算法性能对比 Table 1 Performance comparison between snowball and parallel transmission
4.1 分组数据cD的关系

可以看出当2T-1=Tc时, 两种方式的节点平均延迟的对比可以被认为是log2NN/2c+3/2之间的比较。

图3所示, 在一定的节点数目N内, 并发传输算法的节点平均延迟要小于雪球方式, 而伴随着c的增大, N的值也随之增大。可以得出结论:在节点上传带宽相同、且c大于一定数值时, 并发传输算法的TD都要优于雪球算法。

图3 并发传输算法和雪球传输算法性能对比Fig.3 Performance of parallel transmission and snow-ball

4.2 分组数目c与带宽的关系

节点带宽增加到Ks后, 雪球传输算法和并发传输算法的节点平均延迟分别为:

(Ks+1)/(2Ks)lo gKsN+O(1)

1/N{1+c× i=1T(i+1) Ksi}

因为Ksc同为变量, 所以两种方式不好进行比较。所以利用另一种方式进行比较。设每一层的节点个数为z(i), 对于并发传输算法有:

z(i)=0, (i=0)(Ksc-c+1)ic, (i> 0)

而对于雪球方式来讲, 其zs(i)= Ksi+1。这里可以很清楚地得到结论:

z(i)> zs(i), c> Ksz(i)=zs(i), c=Ksz(i)< zs(i), c< Ks

N相同时单位时间内获得数据块的节点数量越大, 传递到全部N个节点所需的时间越小, 平均节点延迟也越小。可以得出结论, 当c> Ks时, 并发传输算法要优于雪球传输算法。

T=log2(N/N1)/N1+2(雪球传输算法)log(K1c-c+1)(N(1+K1)/Ks+1)(并发传输算法)

在流媒体系统中, 两种算法的条件不同, 所以并不能简单地进行比较。

雪球算法的并发随机性很强, 难以进行调度, 而并发传输算法因为分层模型的采用所以并发的可控性很强, 可以根据需要予以调度, 更加合理利用带宽。而且, 在大规模的流媒体网络里, 雪球算法在传输一个数据块时, 会连接大量不同的节点, 大量的连接过程不可避免地会产生延迟。而并发传输算法在传输时, 连接的节点集合相对比较稳定, 连接过程产生的延迟大大低于雪球算法。

5 结束语

本文对P2P网状结构进行了结构化处理, 解决了上传带宽大的节点利用率低的问题。在动态分级传输模型的基础上, 提出了并发传输算法, 实现了基于分层结构的高度立体并发传输, 上传带宽大的节点之间遍历的过程中也全力单向支援带宽不足的节点, 帮助生成足够多的种子, 可以在更短的时间单元内将数据块传输给全部节点。同现有的效率最优的雪球传输算法进行了比较, 在一定条件下, 在传输效率上要优于雪球传输算法, 并且在持续传输数据内容的情况下, 要比雪球算法更易于实现。将进一步研究如何更合理地进行分级操作及降低因节点的加入或离开导致的传输不稳定引起的延迟问题。

The authors have declared that no competing interests exist.

参考文献
[1] Ramzan N, Park H, Izquierdo E. Video streaming over P2P networks: challenges and opportunities[J]. Signal Processing on Image Communication, 2012, 27(5): 401-411. [本文引用:1]
[2] Shen Z J, Luo J, Zimmermann R, et al. Peer-to-peer media streaming : insights and new developments[J]. Proceedings of the IEEE, 2011, 99(12): 2089-2109. [本文引用:1]
[3] Zhang X Y, Hassanein H. A survey of peer-to-peer live video streaming schemes-an algorithmic perspective[J]. Computer Networks, 2012, 56(15): 3548-3579. [本文引用:1]
[4] Zhang X Y, Hassanein H. Understand ing the impact of neighboring strategy in peer-to-peer multimedia streaming applications[J]. Computer Networks, 2012, 35(15): 1893-1901. [本文引用:1]
[5] Wang F, Liu J C, Xiong Y Q. Stable peers: existence, importance, and application in peer-to-peer live video streaming[C]∥The 27th IEEE Conference on Computer Communications, 2008: 2038-2046. [本文引用:1]
[6] Kumar R, Liu Y, Ross K. Stochastic fluid theory for P2P streaming systems[C]∥The 26th IEEE Conference on Computer Communications, 2007: 919-927. [本文引用:1]
[7] Liu Y. On the minimum delay peer-to-peer video streaming : how realtime can it be?[C]∥ACM Multimedia, 2007: 127-136. [本文引用:1]
[8] Magharei N, Rejaie R, Guo Y. Mesh or multiple-tree: a comparative study of live P2P streaming approaches[C]∥IEEE INFOCOM, 2007: 1424-1432. [本文引用:1]
[9] Xu Y Y, Zhu C, Zeng W J, et al. Multiple description coded video streaming in peer-to-peer networks[J]. Signal Processing on Image Communication, 2012, 27(5): 417-429. [本文引用:1]
[10] 宋俊平, 张棪, 周旭, . 基于SVC 的P2P 流媒体系统研究综述[J]. 计算机应用研究, 2013, 30(4): 965-970.
Song Jun-ping, Zhang Yan, Zhou Xu, et al. Survey of research on SVC-based P2P streaming systems[J]. Application Research of Computers, 2013, 30(4): 965-970. [本文引用:1]