基于节点能力的P2P 流媒体推拉结合数据
调度算法#
于洁，双锴*
基金项目：高等学校博士学科点专项科研基金课题（20090005120012）；新一代宽带无线移动通信网国家
科技重大专项（新型移动业务控制网络的架构及关键技术，2010ZX03004-001-01）
作者简介：于洁，（1987-），女，硕士生，主要研究方向：分布式业务网络. E-mail: ivyyu8701@gmail.com
通信联系人：双锴，（1977-），男，副教授。E-mail: shuangk@bupt.edu.cn
5 （北京邮电大学网络与交换技术国家重点实验室，北京 100876）
摘要：现有P2P 流媒体直播系统中缺乏较完善的媒体数据调度算法，导致P2P 流媒体直播业
务出现启动时延较大及播放连续度较差的问题。提出一种推拉结合的数据调度算法，该算法
最大化利用了节点的上传能力，并且针对直播业务实时性较强的特点，在以推模式为主的数
据调度过程中，采用拉模式解决媒体播放不连续的问题，使媒体流在最短时间内恢复正常。
10 实验结果表明，基于推拉结合的数据调度算法可以有效缩短直播业务中的启动时延和提升播
放连续度，改善了流媒体直播系统中的用户体验。
关键词：P2P；流媒体；数据调度；推拉结合
 0 引言
30 近年来，基于P2P 技术的流媒体应用已成为研究热点。通过引入P2P 技术，可以很好
地解决传统C/S 模式中流媒体服务器占用带宽、负载过重的情况。基于Gossip 协议的算法
是目前流行的在P2P 系统中分发消息的算法，视频流媒体网络系统通过Gossip 协议，每个
节点维护系统中部分其他节点的视图，每个节点动态的和其它节点交换缓存信息，并根据缓
存信息交换节点之间的媒体数据。基于Gossip 协议的算法具有很好的可扩展性及动态环境
35 的适应性，对于节点的异常或者不稳定性具有先天的免疫性，即在任意节点上出现的异常情
况不会影响整个系统的正常运行。但由于节点需要在本地开辟较大的缓存来存储流数据，并
且节点间数据交互具有不定性，因此使得节点的启动及播放延迟相对比较大。
本文结合拉模式的优点，提出了一种基于推拉结合的数据调度算法，该算法改进了拉模
式中冗余消息过多、播放延迟较大的不足，能够有效减少冗余消息的产生，并且进一步提高
40 Peer 节点的播放质量。
 1 相关研究
基于P2P 的实时流媒体系统主要涉及两方面的研究内容，一是叠加网的构建，二是数
据分片的传输调度，即媒体内容被分割成若干个大小相同的数据块，节点如何对数据块进行
请求[1]。有效的数据调度算法直接影响节点获取数据的效率以及媒体内容的播放质量。
针对数据调度算法，45 文献[2]提出了一种随机获取的算法（Random），但该算法没有考
虑数据分发本身的不平衡性，导致调度没有起到调度数据块数目均匀的作用，对于加快数据
的传输效果不理想。文献[3]提出了局部最少优先（Local Rarest First, LRF）算法，该算法主
要适用于BitTorrent 这类不需要实时播放媒体数据的文件下载系统，对于实时性数据获取，
该算法的数据获取效果较差，并且带宽利用率不高。文献[4]提出了一种网络编码算法，该算
50 法中提出用网络编码算法来代替LRF 算法，从而提高带宽利用率，但改进并不明显。
2 基于推拉结合的数据调度算法
CollStreaming/DONet 模型[5]提出了一种单一拉模式数据调度算法，该算法中每块数据都
是通过请求节点发出请求而得到，系统中控制消息过多，从而导致传递延迟的增加，这对实
时性要求较高的视频直播是十分不利的。本文针对单一拉模式的数据调度算法的不足，提出
55 一种基于推拉结合模式的数据调度算法。
该算法中综合考虑用户节点的上传带宽、当前服务能力、请求节点数据块的紧迫性等各
方面的因素，在用户节点与其他节点建立了邻居关系后，开始以推模式为主进行数据调度，
极大的减少了数据调度过程中的控制消息。并且当用户播放媒体流不顺畅时，及时在推模式
的基础上采用拉模式，向邻居请求当前缺少的少量数据块，使用户在尽量短的时间内恢复正
60 常播放。
2.1 数据分片原则
在流媒体系统中，服务器都需要把视频节目划分成小的数据块（Buffer Data, BD）。每
个BD 又被分为若干大小相当的分片，称为chunk，用户节点之间以chunk 为单位来传送数
据。
65 根据对已有系统的分析，在PPStream 中[6]，将大小为1MB 的数据块BD 作为一个播放
单元进行播放，每个BD 播放时间长度从14~28 秒不等，平均大约20 秒长。因此本算法中
也将BD 的大小规定为1MB，每个BD 播放长度约为20 秒，当获取一个完整BD 后，即可
对该数据块进行播放。
70 图1 数据分片原则
Fig. 1 Principle of data fragmentation
节点之间通过相互传送自己的BD 块的映射信息（Buffer Map， 简称BM），将自己的
 媒体数据信息广播出去，并获取到邻居的媒体数据拥有状态。每个BM 由一个Offset（Offset
75 是一个BD 中第一个chunk 块的ID 值，用来表示该BD 再视频节目中的相对位置）和一系
列连续的“1”或“0”组成，如果BM 中对应的位置上为“1”，则表示该chunk 片存在于该BD 种，
反之则表示不存在。数据分片表示方式如图1 所示。
2.2 基于推拉结合模式的数据调度算法
本算法中在用户节点加入系统并与若干其他用户节点建立邻居关系后，就开始数据块的
80 推送接收。为了能够发挥P2P 技术的优势，充分利用每个用户节点的上传能力，每个节点
会同时接收从多个邻居节点推送的数据。为了减少推模式中由于重复推送造成冗余数据过
多，导致带宽的浪费，在上述数据分片的基础上，引入一个数据流的概念。将每个BD 中的
chunk 分为几组，每组作为一个数据流，例如分为n 组，则编号为（128 mod n）的chunk 属
于同一个数据流，所有BD 中属于同一组别的数据流都统一由一个邻居向节点推送。
85 邻居节点的节点能力将被作为用户选择邻居服务的主要因素，用户节点通过计算邻居节
点的节点能力来决定向哪些邻居请求数据流。邻居节点能力计算方法具体描述如下：
1） 用户节点向某个邻居节点请求数据流并得到回复后，记录请求开始时间点，将向该
邻居请求的chunk 数记为requestNum，从该邻居实际收到的chunk 数记为
respondNum，requestNum 和respondNum 初始均为0；
90 2） 用户节点收到邻居节点推送的一个chunk 后，将respondNum 加1，并计算从请求开
始时间到当前时间，理论上应该从该邻居获取到的chunk 数，即为当前的
requestNum；
3） requestNum – respondNum 即为该邻居的节点能力，requestNum – respondNum 越小，
表示该邻居的服务能力越强，如果两个邻居的该值相等，则认为上传带宽较大的邻
95 居节点的服务能力较强。
用户节点加入系统后，和该用户建立连接的其他用户节点会从自己的缓冲区间中选择一
个数据块，将该BD 对应的映射信息BM 发送给该用户节点，该用户节点根据邻居节点发送
的BM 来确定自己的初始视频播放位置。然后，用户节点调用数据调度算法，进行媒体数据
的调度。用户A 加入系统后，收到索引服务器发送的节点列表后，与列表中的节点进行通
100 信，成功添加若干个节点到自己的邻居列表后，开始进行媒体数据分片的获取。基于推拉结
合的数据调度算法具体调度流程如下：
1） A 从邻居列表中选择未向自己提供服务的且节点能力最大CS 节点B，向其请求目
前没有邻居推送的数据流；
2） A 收到B 的响应消息后，将其中的数据流信息记录到相应数据结构中，并更新邻居
105 B 的节点能力；
3） A 判断目前未被推送的数据流列表中是否还有记录，并判断目前是否还有其他未向
自己提供服务的CS 邻居；
4） 如果有未被推送的数据流且有未向自己提供服务的邻居，则转向1），继续向其他
CS 邻居请求未被推送的数据流；如果有未被推送的数据流且所有CS 邻居已经向自
110 己提供服务，则转向5）；如果所有数据流已有邻居节点负责推送，则转向6）；
5） 向未向自己提供服务的UE 邻居以数据分片chunk 为单位请求数据，即采用拉模式
向UE 邻居请求目前仍未获取的数据流中的分片；
6） 结束数据调度。
在某些需要紧急播放的BD 还缺少少量的chunk 未获取到时，即由于数据分片获取不及
115 时而导致播放不连续的情况下，会采用拉模式向所有邻居请求未获取到的数据分片。
用户节点在获取邻居节点推送的媒体数据过程中，如果某个邻居下线，导致某些流不能
继续获取，则再次调用数据调度算法，向未向自己提供服务的邻居节点请求被中断服务的数
 据流，如果邻居列表中已无此类邻居节点，则更新邻居列表，获取新的邻居节点，再继续向
新的邻居请求数据流。
120 该基于推拉结合的数据调度算法较好的利用了CS 节点的服务能力，由于直播系统对于
实时数据要求的紧迫性，充分利用CS 节点的服务能力，并灵活利用UE 节点的服务能力，
能够获得更好的播放连续度，提升直播用户体验。
3 仿真实验及性能分析
为了更好地分析推拉结合算法的性能，在仿真中同时实现了基于推拉结合模式和纯拉模
125 式的数据调度算法以便进行比较。
3.1 仿真环境
为了进行大规模的P2P 流媒体系统仿真，采用OMNeT++（Objective Modular Network
Testbed in C++）[7]作为仿真工具，使用OMNeT++上的拓扑生成工具生成了能够支持上千个
用户节点的路由拓扑，并使用INET 自动路由的功能，完成整个拓扑系统中的自动路由寻址
130 工作。配置的所有用户节点在实验周期内以泊松分布规律被触发加入系统，按照对数正态分
布规律停留一段时间后离开。在表1 中实验参数设置下，分别测试对比系统中使用基于纯拉
模式和推拉结合模式两种数据调度算法下的仿真结果。
表1 实验参数设置
135 Tab. 1 Experimental parameters
实验参数 参数值
同时在线用户规模 2000
播放码率（kbps） 400
播放数据单元（KB） 1024
传输数据分片（KB） 8
核心网链路带宽（M） 100
用户接入带宽（M） 0.5-4
邻居数量 15-30
实验时长（小时） 24
其中用户带宽采用系统默认配置方案，参考中国互联网络信息中心发布的《2010 年中
学术论文网Tag：代写硕士论文 代写论文 代写MBA论文 代写毕业论文 论文发表