一种基于应答驱动的P2P流媒体数据调度方法

摘要

本发明涉及一种基于应答驱动的P2P流媒体数据调度方法，其数据调度程序操作步骤如下：(1)从本节点缓冲序列的起始位置寻找第一个还不存在的数据块，将其序列号赋给当前数据块nCurrBlock；(2)判断其是否不大于本节点缓冲序列最后一个数据块的序列号，否则转至(9)；(3)判断本节点是否已经持有序列号为nCurrBlock的数据块，若已存在则转至(8)；(4)按照节点选择方法从本节点所有伙伴节点集中选择一个序列号为nCurrBlock的节点并将其赋值给数据提供节点，若不存在，则将数据提供节点置空；(5)判断该节点是否为空，否则转至(8)；(6)向该数据提供节点发送请求数据包，请求序列号为nCurrBlock的数据块；(7)将数据提供节点对应的请求数目字段值加一；(8)将nCurrBlock字段值加一，后转至(2)；(9)本次调度过程结束。

说明书

技术领域

本发明涉及网络流媒体技术领域，特别是一种基于应答驱动的P2P流媒体数据调度方法。

背景技术

P2P(Peer-to-Peer，对等网络)技术是一种基于物理网络的应用层信息控制技术，它是分布式计算的重要发展方向，是未来高速网络中迅速而广泛地分发各种数据的基础。流媒体是指采用流式传输的方式在因特网上传播的媒体格式，如音频、视频或多媒体文件；流媒体技术是未来网络服务体系的重要组成部分，为众多网络应用提供了必需的平台。二者结合起来，构成了一种新兴的网络服务——P2P流媒体。

流媒体传输具有实时性、连续性、数据依赖性等特点。其中实时性要求网络中传输的各视频帧数据必须在特定的播放时限之前到达接收方；连续性要求各视频帧数据必须按照一定的顺序进行播放。压缩的视频数据具有两种类型的数据依赖性：帧间依赖要求接收方在解码一个优先级较低的视频帧之前，必须已解码它所依赖的其它优先级较高的视频帧；帧内要求接收方最好在全部接收到组成一帧的所有数据包之后再进行解码，否则会引起解码错误从而导致显示画面图像破碎等现象，甚至引起解码器程序崩溃而中止播放。

现有的P2P流媒体系统多数基于旧的文件传输的P2P设计思路，没有针对流媒体的特点进行优化，对于单个节点的播放质量并没有从网络结构和数据调度的高度予以保证，在大范围应用的情况下，不同节点之间、甚至单个节点在不同时刻的用户体验相差很大。在P2P流媒体系统中，由于网络的异构性(节点之间带宽的不对称等)、网络带宽的抖动、网络结构的动态性(节点频繁的加入或退出)等原因，对流媒体提供服务质量保证成为流媒体技术领域的一个关键问题。

近年来，基于流言(gossip)协议的P2P网络拓扑构造方法得到了大量的应用，这样构造的网络模型称为网状模型，较之以往的基于树状结构的模型有更强的鲁棒性。在网状模型中，每个节点有若干直接相连的伙伴节点，它可以同时从多个结点请求数据，所以这种模型也叫多源模型。根据数据获取方式的不同，网状模型又可分为三种：数据驱动的网状模型、发送者驱动的网状模型和接收者驱动的网状模型。其中数据驱动的网状模型因其简单、高效和网络中传输的冗余数据较少的特点而得到了广泛的认同。在数据驱动的网状模型中，媒体数据被分成若干个大小相当的块，节点之间以块为单位来传送数据。每个节点维护一个自己的缓冲序列，记录自己持有哪些数据块，然后定时把自己缓冲序列的变化发送给自己所有的伙伴节点，这样每个节点都能及时地了解它的伙伴节点持有哪些数据块。所谓数据调度，就是每个节点定期地向他的伙伴节点请求自己没有的数据，由于在网状模型中可能有多个节点同时持有某块数据，这时候就要决定向哪个伙伴节点请求数据，要求既能充分利用每个节点的空闲带宽使数据尽可能快的收到，同时又能维持整个网络的负载均衡，所以这个过程就需要一个智能的调度算法。

理想的调度算法应该在满足各种网络条件的限制下，使播放启动延时最小，同时使播放过程尽可能流畅。现有技术采用的一些调度算法主要包括：随机调度、循环调度和最少数据优先调度。其中随机调度和循环调度对异构网络的适应性不好，尤其是网络带宽波动时效率很低；而最少数据优先调度不能保证将要播出的数据及时到达，容易造成播放的不流畅，影响服务质量。

发明内容

针对上述问题，本发明的目的是提供一种能够在各种网络条件的限制下达到近似最优的调度、提供尽可能好的服务质量的基于应答驱动的P2P流媒体数据调度方法。

为实现上述目的，本发明采取以下技术方案：一种基于应答驱动的P2P流媒体数据调度方法，其数据调度操作步骤如下：(1)初始化操作，从本节点缓冲序列buffmap的起始位置开始寻找第一个还不存在的数据块，然后将该数据块的序列号赋值给当前数据块nCurrBlock；(2)判断nCurrBlock是否不大于本节点的buffmap中最后一个数据块的序列号，如果不大于则转至步骤(3)，否则转至步骤(9)；(3)判断本节点是否已经持有序列号为nCurrBlock的数据块，如果已经存在则转至步骤(8)，否则转至步骤(4)；(4)按照节点选择方法从本节点的所有伙伴节点集合partnerSet中选择一个持有序列号为nCurrBlock的节点并将其赋值给数据提供节点supplier，如果不存在这样的节点，则将supplier置为空值；(5)判断supplier是否为空值，如果不为空则转至步骤(6)，否则转至步骤(8)；(6)向supplier节点发送请求数据包，请求序列号为nCurrBlock的数据块；(7)将supplier节点对应的请求数目reqNum字段值加一，即：reqNum[supplier]←reqNum[supplier]+1；(8)将nCurrBlock字段值加一，即：nCurrBlock←nCurrBlock+1，然后转至步骤(2)；(9)本次调度过程结束，等待下一次的调度。

所述步骤(4)中节点选择方法，其操作步骤如下：

(a)初始化操作，定义一个临时变量i，设i为最小的满足条件“伙伴节点partnerSet[i]持有序列号为nCurrBlock的数据块”的值，如果存在这样的i，则将partnerSet[i]赋值给supplier，否则令supplier为空值；(b)令临时变量i的值加一，即：i←i+1；(c)判断i是否大于当前的伙伴节点数目partnerNum，如果不大于则转至步骤(d)，否则转至步骤(f)；(d)判断下列三个条件是否同时成立：partnerSet[i]持有序列号为nCurrBlock的数据块，reqNum[partnerSet[i]]＜maxReq，maxReq为最大请求数，reqNum[partnerSet[i]]＜reqNum[supplier]，如果同时成立则转至步骤(e)，否则转至步骤(b)；(e)将partnerSet[i]赋值给supplier，然后转至步骤(b)；(f)supplier即为选定的伙伴节点，作为返回值返回给调度主程序，如果supplier不为空，则本节点可以向它请求序列号为nCurrBlock的数据块。

当所述节点接收到数据包时的操作步骤如下：

(i)本节点从伙伴节点p处收到一个数据包；(ii)判断该数据包是否是某一个数据块的最后一个包，如果是则转到步骤(iii)，否则转至步骤(v)；(iii)将伙伴节点p对应的reqNum减一，即reqNum[p]←reqNum[p]-1；(iv)更新本节点的buffmap，同时向本节点的所有除p以外的其他伙伴节点发送buffmap变化的情况；(v)正常返回。

本发明由于采取以上技术方案，其具有以下优点：1、本发明由于使用了数据调度方法，使得播放端即播放器的启动延时非常短，同时播放过程能够尽可能地流畅，特别是在节点带宽比节目本身码率还要低的情况下，效果非常明显。2、本发明由于在调度时是根据每个节点实时传输数据的情况来决定下一步向哪个伙伴节点请求数据，因此能够尽可能地充分利用各个节点的空闲带宽真正做到“能者多劳”，又最大限度地维护负载均衡，避免某些节点的负担过重。3、本发明的操作是完全分布式执行的，因此它不需要测量或估算某个节点的可用带宽就能使数据的流向最大可能地与实时带宽相吻合，减少调度和数据传输的冗余性。4、本发明因为采用以上方案，在保证服务质量的前提下，通过自动调节，可适应如网络异构性、带宽波动、节点频繁加入或退出等不同的网络状况。

附图说明

图1是本发明提供的基于应答驱动的P2P流媒体数据调度方法的流程图

图2是本发明提供的在请求数据前选择合适节点的流程图

图3是本发明提供的收到数据包时处理的流程图

具体实施方式

下面结合附图和实施例，对本发明进行详细的描述。

图1表示的是本发明所提出的基于应答驱动的P2P流媒体数据调度方法的主流程图，该调度方法被周期性地调用。在介绍具体的调度步骤之前先介绍其中用到的几个输入参数：

partnerSet(伙伴节点集合)：这是一个集合，包含该节点所有的伙伴节点，即直接相连并且有数据交互的节点；

partnerNum(伙伴节点数目)：表示该节点当前连接的伙伴节点数目；

nCurrBlock(当前数据块)：当前要请求的数据块的序列号；

supplier(数据提供节点)：表示可向该节点提供当前数据块的伙伴节点；

reqNum[s](请求的数目)：表示该节点已经向伙伴节点s请求过但还没有收到的数据块的数目；

maxReq(最大请求数)：表示该节点可以同时向一个伙伴节点请求的数据块的最大数目，也就是已经发出请求但还没有收到的数据块的最大数目；

该节点每连接一个新的伙伴节点p，就将相应的reqNum[p]设置为0。

maxReq是一个预先设定的值，它要根据数据块的大小来进行设定。如果数据块偏大，则maxReq要设的小一些，以避免过多的数据重传而浪费带宽；如果数据块偏小，则maxReq要设的大一些，以充分利用各个节点的空闲带宽。

调度方法主程序的操作步骤如下：

(1)初始化操作，从本节点缓冲序列buffmap的起始位置开始寻找第一个还不存在的数据块，然后将该数据块的序列号赋值给当前数据块nCurrBlock；

(2)判断nCurrBlock是否不大于本节点的缓冲图中最后一个数据块的序列号，如果不大于则转至步骤(3)，否则转至步骤(9)结束本程序；

(3)判断本节点是否已经持有序列号为nCurrBlock的数据块，如果已经存在则转至步骤(8)将nCurrBlock字段值加一，否则转至步骤(4)；

(4)按照一定的方法从本节点的所有伙伴节点列表partnerSet中选择一个持有序列号为nCurrBlock的节点并将其赋值给数据提供节点supplier，如果不存在这样的节点，则将supplier置为空值，具体的选择节点的方法参见下面的选择合适节点的流程(如图2所示)；

(5)判断数据提供节点supplier是否为空值，如果不为空则转至步骤(6)，否则转至步骤(8)将nCurrBlock字段值加一；

(6)向supplier节点发送请求数据包，请求序列号为nCurrBlock的数据块；

(7)将supplier节点对应的请求数目reqNum字段值加一，即：reqNum[supplier]←reqNum[supplier]+1；

(8)将nCurrBlock字段值加一，即：nCurrBlock←nCurrBlock+1，然后转至步骤(2)；

(9)本次调度过程结束，等待下一次的调度。

如图2所示，是请求数据前选择合适节点的流程图，将要请求的数据块的序列号为nCurrBlock，选择合适节点的具体操作步骤如下：

(1)初始化操作，定义一个临时变量i，设i为最小的满足条件“伙伴节点partnerSet[i]持有序列号为nCurrBlock的数据块”的值，如果存在这样的i，则将partnerSet[i]赋值给数据提供节点supplier，否则令supplier为空值；

(2)令临时变量i的值加一，即：i←i+1；

(3)判断i是否大于当前的伙伴节点数目partnerNum，如果不大于则转至步骤(4)，否则转至步骤(6)令supplier即为选定的伙伴节点；

(4)判断下列三个条件是否同时成立：

partnerSet[i]持有序列号为nCurrBlock的数据块，

并且请求数目reqNum[partnerSet[i]]＜maxReq，maxReq为最大请求数，并且reqNum[partnerSet[i]]＜reqNum[supplier]，如果同时成立则转至步骤(5)，否则转至步骤(2)；

(5)将partnerSet[i]赋值给supplier，然后转至步骤(2)；

(6)supplier即为选定的伙伴节点，作为返回值返回给调度主程序，如果supplier不为空，则本节点可以向它请求序列号为nCurrBlock的数据块。

如图3所示，是本节点收到数据包时的处理流程，具体操作步骤如下：

(1)本节点从伙伴节点p处收到一个数据包；

(2)判断该数据包是否是某一个数据块的最后一个包，如果是则转到步骤(3)，否则转至步骤(5)正常返回；

(3)将伙伴节点p对应的reqNum减一，即reqNum[p]←reqNum[p]-1；

(4)更新自己的缓冲序列buffmap，同时向自己所有的除p以外的其他伙伴节点发送buffmap变化的情况；

(5)正常返回。

根据前面具体实施方式的叙述，可以发现请求数据时，在多个可选的伙伴节点间选择合适的节点时的主要依据是各个节点对应的reqNum字段值。这个值在建立伙伴关系时初始化为0，每次向一个节点请求一个数据块，就将该节点的reqNum字段值加一，每次从一个节点收到一个数据块，就将该节点的reqNum字段值减一，也就是说调度时是根据每个节点实时传输数据的情况来决定下一步向哪个节点请求数据，真正做到了“能者多劳”，使数据调度与各个节点的可用带宽相吻合，在不需要全局信息的情况下达到了近似最优的调度。