基于p2p的流媒体技术

　　收稿日期 : 2004 - 11 - 19;修订日期 : 2005 - 02 - 28 　　作者简介 :王艳丽 (1979 - ) ,女 ,宁夏石嘴山人 ,硕士研究生 ,主要研究方向 :网络通信与信息系统 ; 　鲜继清 ( 1946 - ) ,男 ,四川西充人 ,副 教授 ,主要研究方向 :网络通信与信息系统 ; 　白洁 (1979 - ) ,男 (回族 ) ,宁夏石嘴山人 ,硕士研究生 ,主要研究方向 :网络多媒体. 文章编号 : 1001 - 9081 (2005) 06 - 1267 - 04 基于 P2P的流媒体技术 王艳丽 1 ,鲜继清 1 ,白 　洁 2 (1. 重庆邮电学院 通信与信息工程学院 ,重庆 400065; 2. 重庆邮电学院 计算机学院 ,重庆 400065) (nmccwyl@163. com) 摘 　要 :现有的流媒体系统一般是基于客户 /服务器模式和 IP组播技术 ,这限制了用户数量且 IP 组播需先得到 ISP支持 ,故其发展受到很大限制。而在 P2P网络中 ,每个接收数据的用户同时向外转 发数据 ,这就充分利用了以往忽视的客户机资源。首先指出了 P2P流媒体应用中所面临的挑战 ,并 着重从应用层多播树、网络异构性、激励机制等方面阐述了 P2P流媒体的研究现状 ,分析讨论了存在 的问题 ,最后指出进一步的研究方向。 关键词 : P2P;应用层组播 ;流媒体 ;激励 ;异构性 中图分类号 : TP393. 03　　文献标识码 : A M ed ia stream ing ba sed on P2P WANG Yan2li1 , X IAN J i2qing1 , BA I J ie2 (1. School of Comm unica tion and Inform ation Engineering, Chongqing U niversity of Posts & Telecomm unications, Chongqing 400065, Ch ina; 2. School of Com puter Science, Chongqing U niversity of Posts & Telecomm unica tions, Chongqing 400065, Ch ina) Abstract: Current media stream ing system s are often based on the client2server framework and IP2level multicasting supported by ISP, which lim its clients amount to a great extent. In P2P network, each client receives data and forwards it to others at the same time. So large numbers of clients resource ignored before can be effectively used. Firstly challenges in P2P media stream ing app lications were pointed out, then some recent research results such as app lication2level multicast tree, heterogeneity of network and incentive mechanism and so on were introduced. Some existent p roblem s and some remained issues for further research were discussed. Key words: P2P; app lication2level multicast(ALM ); media stream ing; incentive; heterogeneity 0　引言 近年来 ,随着 eMule、B ittorrent[ 1 ]等 P2P应用软件的出现 , 对 P2P网络的研究已广泛展开。P2P网络中 ,每个终端也称 节点同时具有客户端和服务器功能 ,每个节点将接收的 缓存并提供给其他请求节点 ,这充分挖掘了 Internet上被忽视 的客户机资源 ,在利用率、扩展性、容错等方面具有巨大潜力。 把 P2P引入流媒体服务 ,将打破传统的客户 /服务器模式 ,使 服务分散化 ,从而减轻服务器负载并支持更大范围流媒体发 布 ,具有潜在的应用前景。 对面向 Internet流媒体技术 ,最简单的解决办法是为每个 申请者建立一条发送视频流的链接。但太耗费带宽 ,又不能 支持大量观众实时收看 ,申请者接收到的将是低质量视频。 IP组播相对而言是一种好的解决方法 ,但 Internet中多数 ISP 不支持 IP组播 ,造成其发展受限。ALM (即应用层组播 )克服 了 IP组播的缺陷 [ 2 ] :无需更改网络和网络设备的配置 , 在客户机间复制和转发数据 ,数据报沿逻辑链路转发 ,数据路 由、复制、转发功能均由客户机完成 ,客户机间建立一个叠加 在 IP网络上、实现组播业务逻辑功能性网络。 但引入 ALM的流媒体系统仍面临如下问题 :首先 ,如何 构建有效的 ALM树。其次 ,如何适应网络异构性。网络异构 性指因目前 Internet接入方式的多样性 (如 ADSL、ISDN、无线 接入等 ) ,网络上不同链路、节点及终端设备在带宽容量、处 理能力等方面不尽相同。最后 ,如何建立有效的激励机制 ,以 确保节点间的公平性。需要指出 :我们称只享受服务而不提 供服务的节点为“Free rider”,如何防止“Free rider”的存在是 P2P流媒体设计的关键 ,必须保证参与节点都贡献资源 ,一个 P2P系统才能正常工作。本文将从这三个方面阐述 P2P流媒 体的研究现状 ,分析现存的问题 ,并指出今后的研究方向。 1　应用层多播树 在 P2P流媒体中 ,首要问题是将服务器和参与服务的节 点组织成 ALM树。但如何构建有效的 ALM树仍是个难点。 1. 1　单树结构的 ALM 1. 1. 1　小规模的多源 ALM方案 该方案多应用于视频会议 ,例如 ESM [ 2 ]系统。将用户节 点组成一个应用层 mesh,周期性检查 mesh中的连接质量 , mesh上以数据源为根 ,根据带宽、时延各自构造生成树。可 以针对每个源单独优化 ,每个成员维护一个组成员列表 ,可靠 性高 ,但开销大 ,扩展性差。 1. 1. 2　大规模的单源组 ALM方案 例如 N ICE[ 3 ] , Zigzag[ 4 ] ALM树构建方案。两者的思路都 是“分层 ”(H ierarchical)、“分群 ”(Cluster) ,成员只和少量固 第 25卷第 6期 2005年 6月 　 计算机应用 Computer App lications 　 Vol. 25 No. 6 June 2005 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 定数目的节点联系。N ICE (如图 1)的维护管理具有分布性 和自治性 ,节点的维护负载较轻 ,且节点的退出只影响局部节 点 ,不影响根节点。缺点是层次越高的节点负载越重 ,如最高 层的节点的度数达到 O ( logN ) ,当系统规模很大时 ,这会成为 系统的瓶颈。 图 1　N ice ZigZag(如图 2)与 N ICE相似 ,两者在每个节点的平均维 护负载都为 O ( k) ,树的高度都为 O (1ogN ) 。但 ZigZag解决 了 N ICE存在的瓶颈问题。其改进点为 : Zigzag中 Cluster的 管理和数据分发由不同节点完成 ,而 N ICE将两功能统一在 一个节点上。改进后 ,多播树中节点所带子节点数目最多为 O ( k2 ) ,与参与多播树的节点数目无关。 图 2　Zigzag 1. 2　多树结构的 ALM方案 单个组播树的解决方案主要缺陷是 :组播树中 ,转发能力 较小的内部节点可能需承担很大转发负载 ,而叶节点却无需 承担负载。P2P流媒体是一种高带宽的应用 ,单个组播树限 制了 它 的 规 模。基 于 多 树 的 方 案 , 以 CoopNet[ 5 ]、 Sp litStream [ 6 ]为代表 ,在数据的传输路径上引入了冗余 ,视频 流不再由一个组播树来完成转发 ,而是先按设定的编码方式 被分割成视频段 ,然后不同视频段由不同生成树完成转发。 图 3　Sp litStream Sp litStream的设计目标是利用多树结构平衡负载 , Sp litStream将视频流分割成多个 Stripes,每个 Stripe构建自己 的组播树 ,这样可以做到一个节点仅在一个组播树中作为转 发节点 ,在其余组播树中作为叶节点 ,当一个节点出现死机或 网络出现故障时 ,只影响一小部分节点。图 3所显示的是一 个 Sp litStream 组播树的例子 ,源节点 1产生两个 stripes。对 于节点 2的 stripe1,组播树先将它发送到节点 3、4,再发送到 节点 5、6、7和 8。对于节点 8的 stripe2,组播树先将它发送到 节点 5和 6再发送到节点 2、3、4和 7。假设当节点 3出现问 题时 ,仅影响到节点 1、5、8。故通过多个组播树结构传送 ,可 以使每个节点都参与转发视频流 ,降低了对单个节点带宽要 求 ,减少因数据包丢失对系统的影响 , 增强了鲁棒性。 Sp litStream基于 Scribe[ 7 ]协议 , Scribe协议的主要作用是把 P2P网络中的邻近节点连接在一起 ,减少了应用层组播的时 延 ,但是每个参与组播的节点必须转发其不感兴趣的视频流。 CoopNet类似于 Sp litStream,它利用 MDC (多描述编码 ) , 将视频流编码成多个独立的 Descrip tions, 再针对每个 Descrip tion构建 ALM树。与 Sp litStream的区别在于 : CoopNet 基于客户 /服务器模型 ,当服务器未超过负载时 ,服务器直接 向请求客户提供服务 ,当服务器超过负载时 ,服务器指定已享 受服务的客户进行服务。 基于多树结构组播通过采用 MDC编码和多树结构在传 输数据和传送路径中引入冗余 ,在所有参与的节点中平衡了 负载 ,且减少了某个节点失败及数据包丢失对整个系统的影 响。但其缺点也很明显 :采用多树结构 ,需同时维护多个组播 树 ,造成开销过大 ,还需保证多路传送时的数据同步 ,且 MDC 编码效率低。 2　网络异构性 Internet的异构性是制约 P2P流媒体发展的一个重要因 素 ,一种好的解决方案应支持大范围的流媒体发布 ,应最大化 系统的吞吐量且公平分发视频数据到每个接收者。目前的 P2P流媒体技术对网络异构性的解决方案主要有以下几种。 2. 1　复制流 发送源通过不同的组播地址为同一视频服务请求开辟多 个不同质量的组播流 ,接收者选择一个最能与自身接收能力 相匹配的组播流 ,同时每个流可根据相应接收者的反馈 ,在一 定范围内调整流速率。文献 [ 8 ]中将视频源分别编码成高质 量视频 (300Kbp s)、低质量视频 (100Kbp s)和声音 (20Kbp s)来 满足不同带宽节点的需求 ,如图 4所示 ,在节点接收过程中 , 通过丢包率动态地控制视频流速率。该方法的缺点是接收者 能力会随网络状况的变化而变化 ,会在不同流之间跳跃。此 外 ,复制流技术所产生的冗余信息增加了网络负担。 图 4　ESM复制流 2. 2　分层编码 此方法将视频信息分成一个基本层和若干个增强层 ,并 分别在不同的组播地址空间组播。基本层提供最基本的服务 质量 ,可独立完成解码 ,增强层提高了服务质量。文献 [ 9 ]提 出基于分层编码和 multip le2sender方式传递分层视频信息 , 针对多个发送端向同一接收端传递数据 ,提出多个发送端之 间进行带宽和数据分配的方案 ,以解决网络的异构性。 文献 [ 9 ]假设 : 1) { H0 , H1 , H2 , ⋯, HN } 为参与应用层组播的节点 , H0 代 表服务器 ,对于任一节点 HK ,假设 HK 的输入 /输出带宽为 IK /OK; 2) 假设视频流分层为 { l0 , l1 , l2 , ⋯, lL } , l0 为基层 , 其他 为增强层 ,且每层所具有的速率分别为 { r0 , r1 , r2 , ⋯, rL }; 3) Ak 表示节点 Hk 缓存内可用层数量 ; 8621　　　　 计算机应用 2005年 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 4) Q k表示用户 Hk接受视频流的层数量 , Qmk 表示节点 Hk 从 hm 接收视频流的层数量。 并给出计算节点 Hk 接收能力的算法 : UnconstrainedSenders ( Ik , H1 , ⋯, HM ) Q k ← 0 P ← < m = 1 repeat Qmk ←max ( n | ∑Q k +ni =Q k ri ≤Qm , ∑ Q k +n i =0 ri ≤ Ik ) enque ( P, Hm ) Q k ←Q k + Qmk m ←m + 1 until∑Q ki =0 ri > Ik or m > M 该算法输入参数为 : 1) Ik :节点 Hk的输入带宽 ; 2) S = { H0 , H1 , H2 , ⋯, HM } : 可为节点 Hk提供服务的节点集合 ,其中节点按 A1 ≤A2 ≤⋯ ≤AM 排序。算法中 P指存放可提供服务节点的集合。用户节 点的层分配策略如下 : index←0 repeat Hm ← deque ( P) allocate layers ∑index +Qmk - 1 lk to Hm Om ←Om - Omk index←index + Qmk until P = < 该算法通过分层编码且在每层中采用不同的速率解决网 络异构性 ;并在满足异构性的同时 ,追求节点带宽利用率最大 化以降低服务器带宽消耗。但文献 [ 9 ]中层解码必须是累积 的 ,也就是层 K要解码必须同时有前面 1至 K - 1层。接收 者至少要加入基本层 ,并根据自身条件尽可能同时接收多个 增强层。在文献 [ 5 ]、[ 6 ]中采用了非累积层编码 MDC,增加 了灵活性 ,消除了各层之间的优先级 ,但非累积层编码效率 低 ,维护开销大。 3　激励机制 2000年 ,对 P2P文件共享系统 Gnutella[ 11 ] 24小时的运行 活动跟踪记录 ,发现系统 70%的节点未共享本身资源 , 1%的 节点承担了系统 47%的下载负载 , 25%的节点承担了系统 99%的下载负载 [ 12 ]。激励机制是保证 P2P流媒体系统正常 运行的关键 ,但它也是目前 P2P流媒体未能很好解决的问 题 ,对于 P2P流媒体激励机制的经验多数来自 P2P文件下载 系统。目前 , P2P流媒体的激励机制主要有两类。 3. 1　物品交换 (Barter) /征税 ( taxation) Barter是一种 B it2for2B it 的激励机制 , 时下 流 行的 B ittorrent应用了这种激励机制。B it2for2B it指把共享数据划 分成固定大小的数据块 ,每个节点以自己拥有的数据块作为 与别人交换的筹码 ,节点下载数据块的同时必须提供上传。 这种物品交换的方法消除了系统的“Free rider”。Barter虽简 单易实现 ,但它严格地限制了资源薄弱节点的接收带宽 ,故并 不适用于 P2P流媒体系统。 文献 [ 13 ]的线性征税激励机制是在 Barter基础上提出 的 ,它在 P2P流媒体系统的激励机制中引入税收的概念 ,综 合考虑网络中节点的带宽差异 ,提出资源充裕的节点共享富 余的资源 ,并帮助资源匮乏的节点。为了使所有节点享受资 源达到最大化 ,并实现资源的再分配 ,发布者拟订、发布并强 制实施“征税 ”方案 ,参与系统的所有节点必须履行此方案 , 促进系统资源的再分配。方案在接收和上传之间提供一种直 接映射 : f = max[ t3 ( r - G) , 0 ] 其中 f为上传带宽 , r为接收带宽 , t为边际税率 ( t≥1) , G 为补贴 ( demogrant)。G和 t由发布者设置 ,节点负责选择 f和 r,每个节点接收到的资源至少为 G。为保证 P2P流媒体系统的 正常运行 ,必须保证共享资源大于等于接收资源 ,即 ∑fi ≥ ∑ri。当 t = 1且 G = 0时 ,就回到了“B it2for2B it”的激励机 制。如果节点为“Free rider”( f = 0) ,它只能接收到系统给予 的补贴 G ( r = G) ,这样就杜绝了“Free rider”节点只享受服务 不提供服务的行为。 3. 2　互惠机制 (Recip rocity) 互惠机制有直接和间接之分。前者以循环机制为代表 , 后者以信誉机制为代表。 P2P流媒体系统中节点角色的不对称性决定了直接互惠 机制的不适用。 间接互惠机制鼓励节点合作以获取信誉值 ,信誉高的节 点将得到优先对待。文献 [ 14 ]提出了基于积分的激励机制 , 它建立在如下观点之上 : 1) 节点间增进合作促进系统全部节点平均服务质量的 提高 ; 2) 当一个节点上传过多时 , cost (即节点耗费成本 )将影 响其自身和远端接收节点的服务质量 ; 3) 服务质量很大程度上依赖于选择什么样的节点提供 服务。 基于此 ,该激励机制通过间接互惠 [ 10 ]鼓励合作。选择节 点质量的差异性体现了积分的不同 :贡献大的节点允许它有 灵活的节点选择权 ,相应地能得到高质量的视频服务 ,而对于 “Free rider”则限制其节点选择范围 ,其只能收到低质量的视 频 (如图 5)。 图 5　间接互惠机制 假设节点贡献资源 xi ,可获得积分 S i ,并映射为相应的等 级 R i。规定节点只能选择等于或低于本身等级的节点作为服 务供应节点 ,故等级不同的节点可选择供应节点的范围不同。 节点等级越高 , 可供选择的供应节点可靠性越高 , 服务质量 Q i越有保障。Q i使节点获得收益 U i ,节点 i上传资源耗费的成 本 C i又使节点收益 U i降低。故 U i、Q i、C i之间的关系为 : U i ( xi ) = aiQ i ( xi ) - biC ( xi ) ai、bi分别定义了节点 i的视频流质量和共享成本值。上 传字节数 S = B out ,上传资源所耗费节点的成本考虑了存储所 需成本及带宽因素 : C i = cL L iM + cT TiD i 其中 , CL 是单位存储成本 , L i是节点 上传资源块数量。M 是资源块平均大小 , CT 是单位传输成本 , TL 是 I的传送速率 , D i是 i的传输时长。积分 S的累积分布函数为 : F (S ) = ∑ S high i =S low f ( i) 这里 f为积分 S的概率密度函数 ,积分的评定依赖于累积 9621第 6期 王艳丽等 :基于 P2P的流媒体技术 　　　　 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 分布函数 F (S ) 及参与系统的节点数量。最后 ,质量函数 Q i需 考虑的特性为 : 1) 节点积分递增时 ,质量函数非递减 ; 2) 质量无限接近 QMAX , QMAX 为节点接收视频质量由 N S 个最好的供应节点提供 ; 3) 质量函数的初始值为非负数 QB E ,其中 QB E = Q (S i = 0) ≥ 0, QB E 为节点接收视频质量由 0个最好的供应节点提 供。 基于这 3个特性 ,质量函数被定义为 : Q i (R i ) = QMAX , 　　　　　　　　　　 R i ≥ N S Gi R iGi N s QMAX + (1 - R iGiN s ) QB E , otherw ise 其中 , R i为节点 i的等级 , G为可供选择的高质量服务节 点个数 , R iG为高质量服务供应节点数。 需指出 ,线性征税激励机制的前提是共享和接收同步 ,故 适用于 P2P流媒体直播系统 ;互惠激励机制不考虑共享和接 收是否同步的因素 ,因此主要应用于 P2P视频点播系统。 4　结语 基于 P2P的流媒体服务体系目前还处于研究的初步阶 段 ,还有许多问题需要解决。 1) 多播树协议的问题。迄今为止 ,多数系统仅用时延或 负载平衡等一两种属性作为度量值 ,并未综合考虑节点可靠 性、网络带宽、网络时延和数据包丢失率及整个算法的维护开 销。还有一个被忽略的重要属性是 :网络中存在大量的防火 墙和 NAT。目前多数计算机与 Internet连接存在防火墙 ,不能 直接连接 ,故还需深入研究。 2) 如何有效地利用下层网络资源的问题。由于应用层 网络叠加于 IP网络之上 ,这就需要一个测量网络实时状况的 有效方法 ,利用测量到的信息构造适应网络变换的 ALM树。 目前对网络测量已有一些解决方案 ,但如何将其集成到 P2P 流媒体系统中仍未得到解决。 3) 应用层组播的安全问题。应用层组播的安全性研究 包括组播机制和信息传递两个方面。组播是一个开放环境 , 为防止恶意用户的侵入和参与 ,必须提供针对发送者和组成 员的身份鉴别技术。安全性是流媒体组播得以大规模应用的 前提。 4) 数据放置策略。P2P流媒体将资源存储由服务器推 向了拥有强大缓存的终端用户。但由于终端用户在处理能 力、存储和带宽上的差异性 ,采用什么策略在不同的终端放置 数据 ,以达到加快系统响应速度、增强系统的可靠性和扩展性 是值得进一步研究的。 5) 对无线用户的支持。无线局域网技术的蓬勃发展在 为移动用户带来高带宽的同时 ,也使对移动用户的流媒体服 务成为可能。但因无线网络高度动态性和无线信道的误码率 等因素的限制 ,如何在这个特殊的网络中构造 ALM树 ,如何 进行拥塞控制和差错控制还有待进一步研究。 参考文献 : [1 ]　http: / /bitconjurer. org/B itTorrent [ EB /OL ], 2001 - 04. [2 ]　CHU Y2H, RAO SG, ZHANG H. A case for end system multicast [A ]. ACM SIGMETR ICS [C ], 2000. [3 ]　BANERJEE S, BHATTACHARJEE B, KOMMAREDDY C. Scala2 ble app lication layer multicast [A ]. ACM SIGCOMM [C ], 2002. [4 ]　TRAN DA , HUA KA , DO TT. Zigzag : An efficient peer 2 to 2peer scheme for media stream ing [A ]. Subm itted to IEEE INFOCOM [C ], 2003. [5 ]　CHOU PA, PADMANABHAN VN, WANG HJ. Resilient peer2to2 peer stream ing [R ]. M icrosoft Research, 2003. [6 ]　CASTRO M, DRUSCHEL P, KERMARREC A, et a l. Sp litstream: H igh2bandwidth multicast in cooperative environments [A ]. 19 th ACM Symposium on Operating System s Princip les [C ], 2003. [7 ]　CASTRO M, DRUSCHEL P, KERMARREC A2M, et a l. SCR IBE: A Large2scale and Decentralized App lication2level Multicast Infra2 structure [A ]. IEEE JSAC [C ], 2002, 20 (8) : 100 - 110. [8 ]　EUGENE NG TS, RAO SG, SR IPAN IDKULCHA I K, et al. Early Experience with an Internet B roadcast System Based on OverlayMul2 ticast[R ]. USEN IX Annual Technical Conference, 2004. [9 ]　CU IY , NAHRSTEDT K. Layered peer 2 to 2peer stream ing [ A ] . NOSSDAV [C ], 2003. [10 ] NOWAK M, SIGMUND K. Evolution of indirect recip rocity by im2 age scoring [J ]. Nature, 1998, 393: 573 - 577. [11 ] http: / /Gnutella. wego. com [ EB /OL ], 2005. [12 ] ADAR E, HUBERMAN BA. Free riding on Gnutella [ J ]. First Monday, 2000, 5 (10). [13 ] CHU Y2H, CHUANG J, ZHANG H. A Case for Taxation in Peer2 to2Peer Stream ing B roadcast [A ]. ACM SIGCOMM’04 Workshop on Practice and Theory of Incentives in Networked System s ( P INS) [C ], 2004. [14 ] HAB IB A , CHUANG J . Incentive Mechanism for Peer 2 to 2 Peer Media Stream ing [A ]. 12 th IEEE InternationalWorkshop on Quality of Service [C ], 2004. (上接第 1263页 ) [4 ]　L IN JS, L IU M, HUANGNF. The shortest path computation inMOSPF protocol using an annealed Hopfield neural network with a new cooling schedule[J ]. Information Sciences, 2000, (129): 17 - 30. [5 ]　ZHANG S, L IU Z. A new dynam ic routing algorithm based on cha2 otic neural networks[J ]. Journal of china institution of communica2 tion , 2001, (12) : 1 - 7. [6 ]　X IANG F, JUNZHOU L, J IEYIW , et a l. QoS routing based on ge2 netic algorithm. Computer Communications[J ], 1999, (22) : 1394 - 1399. [7 ]　WANG Z, SH I B. Bandwidth2delay2constrained least2cost multicast routing based on heuristic genetic algorithm [J ]. Computer Commu2 nications, 2001, (24) : 685 - 692.[8 ]　HAGH IGHATAB AT, FAEZB K, DEHGHAN M, et a l. GA2Basedheuristic algorithm s forQoS based multicast routing [J ]. Knowledge2Based System s, 2003, (16) : 305 - 312.[9 ]　RAV IKUMAR CP, BAJPA I R. Source2based delay2bounded multi2casting in multimedia networks [ J ]. Computer Communications,1998, (21) : 126 - 132.[10 ] SALAMA HF, REEVES DS, V IN IOTIS Y. Evaluation of multicastrouting algorithm s for real2time communication on high - speed net2works [J ]. IEEE JSAC, 1997, (15) : 332 - 345. 0721　　　　 计算机应用 2005年 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.