P2P流媒体中的数据分配算法

1 相关工作
在多对单传输模式下如何对视频数据进行分配 调度是近几年的研究热点 . 按照分配调度粒度 ,可把 现有工作划分为基于数据包的细粒度调度和基于数 据层的粗粒度调度[ 6 ] . 在细粒度调度中 ,文献 [ 7 ] 提出了多对单模式下 如何在多个发送端之间进行数据和带宽分配 . 文献 [ 8 ] 给出了一种基于带宽测试的数据分配 算法 ,其目的是确保每个数据包仅被一个发送节点 发送 ,同时使数据包的丢失及延迟最小 . 文献 [ 9 ] 提出了一种以 F EC 编码为基础的数据 分配算法 ,其目的是减小数据包在突发丢包网络环 境下的丢失概率 . 文献 [ 4 ] 提出一种多对单的 P2 P 流媒体系统 PROM ISE ,它通过底层的网络得到资源节点的候选 集合 ,并在候选集合中找出速率期望值最高而且能够 满足需要的活跃集合 ,作为接收节点的多发送端. 接 收节点在播放过程中 ,不断地监测发送节点的状况 , 淘汰掉不适合的节点 ,更新活跃集 . PROM ISE 在选 择最优的发送端时采用了拓扑感知技术 , 把发送节 点的状况 ( 带宽和有效性 ) 作为选择的依据进行决 策 . 这种方法的缺点是需要了解太多的底层参数 ,算 法复杂度高 [ 1 ] . 现有的数据分配算法普遍存在对环境要求高 、 计算时间复杂度大等问题 . 为了进一步提高接收端 接收视频的质量 ,本文为多发送端速率和数据分配 问题提出了新的算法 . 与现有方法不同 ,本文给出的 算法有 3 个突出的特点 : 1) 最优速率分配公式有严格的数学推导 , 为公
计算机研究与发展 Jo urnal of Co mp uter Research and Develop ment
ISSN 100021239Π CN 1121777Π TP ( ) 46 11 : 1803 - 1813 , 2009
P2P 流媒体中的数据分配算法
李泽平
1 2
1 ,2
卢显良 聂晓文 李 林
收稿日期 :2008 - 05 - 23 ; 修回日期 :2009 - 06 - 17 基金项目 : 贵州省自然科学基金项目 ( (2003) 3069 号) ; 电子科技大学青年科技基金项目 (L08010601J X0808) ; 电子信息产业发展基金项目
(20022546)
© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved.
摘 要 最近兴起的 P2 P 技术在充分利用客户资源 、 提高系统的可伸缩性方面具有巨大的潜力 , 基于
P2 P 提供视频服务已成为 Internet 的一项重要应用 . 在多对单 P2 P 模式下 , 对多个发送端最优地分配
发送速率和数据是一个难题 . 为此 ,提出了一种新的分配算法 . 首先 ,应用排队论把最优速率分配问题模 型化为非线性最优化问题 ,推导出求解最优化问题的速率分配公式 ; 然后 ,基于该公式提出最优速率分 配算法 ( ORAA) ,并对 ORAA 输出解的最优性给出证明 ;最后 ,提出动态速率分配算法 ( DRAA) . DRAA 对 动态的网络环境具有自适应性 ,能根据网络条件的变化最优地为多个发送端进行速率和数据分配 . 仿真实 验结果表明 ,在不同的参数条件下 ,DRAA 算法减少了计算和通信开销 ,比同类算法有更好的性能 .
Abstract The recently emerging P2 P technologies have huge potential o n reso urce usage and system scalabilit y. Providing P2 P2based media st reaming service , which is an important applicatio n over t he Internet , has at t racted a lot of research interest s. In P2 P media st reaming wit h t he pat tern of multiple sender s and single receiver , it is still a challenge to optimally allocate st reaming rate and media data amo ng multiple senders. To cope wit h t he p ro blem , a new solutio n is p ropo sed. Fir stly , t he aut hor s model t he optimal rate allocatio n p ro blem as a no n2linear optimizatio n p ro blem by applying queueing t heo ry , and derive t he optimal rate allocatio n fo rmula t hat co mp utes t he op timal solutio n. Then , a new optimal rate allocatio n algorit hm ( O RAA ) based o n t he formula is p ropo sed. The O RAA algorit hm can p roduce t he optimal solutio n and t he optimalit y of it s solutio n is p roved. Finally , based o n t he O RAA algorit hm , a dynamic rate allocatio n algorit hm ( DRAA ) is p ropo sed , which can dynamically adapt to net work fluct uatio n and op timally allocate st reaming rate and media data amo ng multiple sender s. Because of it s short running time , t he DRAA algorit hm can be used in real time. Extensive simulatio n result s using N S2 show t hat t he p ropo sed DRAA algorit hm effectively reduces calculatio n and co mmunicatio n overheads , and achieves a bet ter performance t han t he related works wit h different parameter s. Key words peer2to2peer ( P2 P ) ; media st reaming ; video2o n2demand ( VoD ) ; data allocatio n ; video dist ributio n
1 2Biblioteka ( S chool of Com p uter S cience & En gi neeri n g , U ni versit y of Elect ronic S cience an d Technolog y of Chi na , Chen g d u 610054) ( Col le ge of S cience , Gui z hou U ni versit y , Gui y an g 550025)

进行容错编码 ,这些编码后的视频段被预存在数据 源 . 当有节点请求视频时 ,每个视频段的包由多个发 送端共同提供 . 每个发送端应发送的数据包个数由 接收端根据运行 O RAA 算法提供的解向量的分量 值确定 . 4) 提出动态速率分配算法 ( DRAA ) . 由于网 络环境是动态变化的 , 接收节点在视频传输期间通 过运行动态速率分配算法 ( DRAA ) , 实时地监控每 段视频被接收的情况 , 根据需要动态地调整最优数 据源子集的成员构成及相应数据包的分配 , 使接收 端所接收视频的质量始终保持在最好的状态 .
1
1
1
( 电子科技大学计算机科学与工程学院 成都 610054) ( 贵州大学理学院 贵阳 550025) ( lizeping @uestc. edu. cn)
Data Allocation Algorithms in P2 P Streaming
Li Zeping1 ,2 , L u Xianliang1 , Nie Xiaowen1 , and Li Lin1

1804
计算机研究与发展 2009 , 46 ( 11)
关键词 对等网络 ; 流媒体 ; 视频点播 ; 数据分配 ; 视频分发 中图法分类号 TP393
视频点播目前已成为对等 ( peer2to2peer , P2 P ) 网络中一项重要的应用 [ 122 ] . 视频分发是视频点播系 统的核心研究内容 . 目前针对 P2 P 视频分发技术的 划分方法有多种 , 按照数据的发送 、 接收和传输方 式 ,可将分发策略分为单对多模式 、 多对单模式和多 [3 ] 对多模式 3 类 . 单对多模式 ,指一个节点的数据是 来自单一的节点 ,而将其发送到其他多个节点 ,多数 应用层组播协议属于此类型 . 多对单模式 ,指一个请 求节点可能需要多个发送节点给它提供数据 . 因为 视频分发对带宽要求较高 , 而 P2 P 中的节点 , 其所 能够或愿意提供的带宽资源是有限的 , 因此通常需 要多个节点联合协作才能为单个节点提供服务 , 例 如 ,PROM ISE 系统 [ 4 ] 就属于这类技术 . 多对多模 式 ,指任何一个节点既可以接受多个节点的数据 ,也 可以向多个节点发送数据 ,Cool St reamingΠ DoNet [ 5 ] 是这类技术的典型代表 . 本文的工作基于 P2 P 视频分发 , 主要研究在多 对单模式下 ,如何给多个发送端最优地分配数据和 发送速率 ,以最小化请求节点接收视频的时间和提 高请求节点的服务质量 . 在研究和分析现有分发策 略的基础上提出新的速率和数据分配算法 , 本文的 主要工作有 :1) 应用排队论 ,把对多发送端的最优速 率分配问题转化为非线性最优化问题 , 并推导出求 解最优化问题的分配公式 . 2 ) 基于分配公式提出最 优速率分配算法 ( ORAA ) . 根据 1 ) 已建立的分配公 式 ,可以求出最优解 ( 速率分配) 向量 . 由于可能会出 现解向量有负分量的情况 ( 这是由不同数据源可用 带宽差距较大引起的) ,在这种情况下不能直接应用 分配公式 . 为解决此问题 ,本文设计最优速率分配算 法 ( O RAA ) ,它通过先删除带宽最小的数据源再求 最优解的方法 ,逐个淘汰发送速率低的数据源 ,直到 最优解向量的所有分量均为非负为止 . 算法给出解 向量的分量值代表相应数据源应提供的最优发送速 率 ,其中所有正分量对应的数据源构成请求节点的 最优数据源子集 ,值为零的分量对应的数据源作候 选数据源 . 最后证明由 ORAA 算法得到的解向量仍 然是速率分配问题的最优解 . 3 ) 应用 ORAA 算法 , 对多个发送端进行数据分配 . 与文献 [ 4 ] 相同 , 本文 也采用接收端驱动模式对被请求的数据进行数据分 配 . 视频文件在发送端先被划分成长度相等的段 ( segment ) ,每段包含 Δ 个包 , 然后再对每个段的包