（计算机系统结构专业论文）基于网络编码的视频播放系统设计.pdf

中文摘要 中文摘要 目前，流媒体正被应用到许多重要领域，如：远程教育、网络视频会议、视 频点播等。应用层组播技术被应用到网络流媒体数据分发上后，使大规模用户的 流媒体应用成为了可能，从而使流媒体的应用得到了进一步的推广。网络编码技 术在应用层组播的基础上，采用在源节点和中间节点对组播数据进行编码的方 式，进一步提高了网络数据的分发效率，因此将网络编码技术应用到流媒体数据 的分发上将具有重要意义。 本文首先对应用层组播技术和网络编码技术的发展现状做了详细的介绍，并 对应用层组播的组网方式和网络编码的编码解码方式做了深入的分析，在此基 础上提出了基于网络编码的视频播放系统的设计方案，系统设计的目标是设计一 种高效率的、可扩展性好的、支持多媒体数据在i n t e m e t 上多点传输的系统。系 统在网状应用层组播模型的基础上构造出2 冗余组播图作为系统运行的网络组播 图，并在媒体数据的传输上采用网络编码技术，提高了媒体数据的分发效率，同 时使整个网络的流量更加均衡。 本文对组播图的建立和网络编码的编码解码方式做了讨论和研究，然后对 系统的整体功能和实现方法做了分析，主要成果可以概括为： 1 、设计了基于网络编码的视频播放系统。对系统的设计目标、系统结构、 工作流程等做了详细的介绍。 2 、对现有应用层组播模型做了详细的分析，并在网状应用层组播模型的基 础上构造出了2 冗余组播图模型做为系统的网络基础。 3 、对网络编码的编码解码过程做了详细的介绍，并对编码系数的生成、管 理和分发方式以及节点中编码解码的过程做了详细的设计。 4 、将网络编码技术应用到系统中媒体数据的分发上。 最后本文运用网络拓扑产生器( i n e t 3 o ) 生成的网络拓扑，构造了一个虚拟 的网络环境，对整个系统进行了仿真，并对系统中节点接收数据的延迟、接收数 据的效率、网络节点的负载状况和网络链路的负载状况做了测试和分析，同时对 使用网络编码前后系统的性能做出了比较，从而证明系统的性能达到了需要的效 果。 关键词：应用层组播，网络编码，流媒体，2 冗余组播图 a b s t r 氏c t a b s t r a c t a tp r e s e n t t h es t r e a m i n gm e d i ai sb e i n ga p p l i e dt om a n yi m p o r t a n tf i e l d s ，s u c hi l l s ： l o n g s t a n c ee d u e a t i o n i n t e m e tv i d e oe o n f e r e n c i n g v i d e oo nd e m a n d ，a n ds oo n 。a t t e r a p p l i c a t i o nl a y e rm u l t i e a s tt e c h n o l o g yh a sb e e na p p l i e dt od i s t n b u t ei n t e m e ts t r e a m i n g d a t a , s t r e a m i n gm e d i aa p p l i c a t i o n sb a s e0 1 1l a r g e - s c a l el t l s e r sb e c o m ep o s s i b l e s o s t r e a m i n gm e d i aa p p l i c a t i o n sh a sb e e nf u r t h e rp r o m o t e d t h em u l t i e a s td a t ai se n c o d e d i nt h e $ o l l l c en o d ea n di n t c r m i d i a t en o d e st h r o u g hn e t w o r kc o d i n gt e c h n o l o g y , a n d f l l r t h c ri m p r o v et h ee f f i c i e n c yo f t h ed i s t r i b u t i o no f n e t w o r kd a t a t h e r e f o r e , i tw i l lh a v e i m p o r t a n ts i g n i f i c a n c et h a tn e t w o r kc o d i n gt e e l a n o l o g yi sa p p l i e d t ot h ed i s l r i b u t i o no f s t r e a m i n gd a t a i nt h i sp a p e r , t h ed e v e l o p m e n ts t a t u so ft h ea p p l i c a t i o nl a y e rm u l t i e a s tt e c h n o l o g y a n dn e t w o r kc o d i n gt e c h n o l o g yi sd e s c r i b e di nd e t a i l ，a n dn e t w o r kc o n s t r u c t i o na p p r o c h o ft h ea p p l i c a t i o nl a y e rm u l t i e a s ta n de n c o d i n g | d e c o d i n gm e t h o do fn e t w o r kc o d i n g a r ci n - d e p t ha n a l y s e d b a s eo nt h i s , v e d i or , 1 a ys y s t e mb a s eo nn e t w o r kc o d i n gi sp u t f o r w a r d t h eg o a lo fs y s t e md e s i g ni st od e s i g nas y s t e mt h a ti th a sh i g h - e f f i c i e n c y , g o o ds c a l a b i l i t ya n ds u p p o r tm u l t i - p o i n tt r a n s m i s s i o no fm u l t i m e d i a d a t a0 1 3 t h ei n t e m e t t h e2 - r e d u n d a n tm u l t i e a s tg r a p hi sc o n s t r u c t e d 罄f t m d a t i o nn e t w o r ko fs y s t e m , a n d n e t w o r kc o d i n gt e c h n o l o g yi sa p p l i e dt ot h ed i s t r i b u t i o no f s t r e a m i n gd a t ai nt h es y s t e m b a s eo nt h i s ，t h ed i s t r i b u t i o nr a t eo fm e d i ad a t ai si m p r o v e d a n dt h et r a f f i co fe n t i r e n e t w o r ki sm o r eb a l a n c e a b l e , t o o t h ec o n s t r u c t i o nm e t h o do ft h em u l t i c a s tn e t w o r ka n de n c o d i n g d e c o d i n gm e t h o d o ft h en e t w o r kc o d i n ga l es t u d i e di nt h i sp a p e r t h e nt h es y s t e m so v e r a l lf t m e t i o na n d m e t h o d sa r ca n a l y s e d m a i nr e s u l t s 蝴b es u m m e du p 粼： 1 d e s i g nl t t v e d i op l a ys y s t e mb a s eo nn e t w o r kc o d i n g 。t h es y s t e m sd e s i g n o b j e c t i v e s ，s t r u c t u r e ，w o r kp r o c e s s e s ，a n ds oo n , i sd e s c r i b e di nd e t a i l 2 。a n a l y s i st h ee x i s t i n ga l 犟l i c a t i o nl a y e rm u l t i c a s tm o d e l ，a n dc o n s t r u c t e dt h e2 - r e d u n d a n tm u l t i e a s tg r a p h 黼f t m d a t i o nn e t w o r ko fs y s t e m i i 麟塔1 f l 醯c t 3 i n t r o d u c et h ee n c o d i n g d e c o d i n gp r o c e s so fn e t w o r kc o d i n g , a n dd e s i g nt h e g e n e r a t i o n 、m a n a g e m e n t 、d i s t r i b u t i o no ft h ec o d ec o e f f i c i e n ta n dt h ee n c o d i n g d e c o d i n gp r o c e s si nt h en o d e 4 a p p l yn e t w o r kc o d i n gt e c h n o l o g y t ot h ed i s t r i b u t i o no f m e d i ad a t ai nt h es y s t e m a tl a s t , an 幽v o r kt o p o l o g yi s g e n e r e t e dt h r o u g hn e t w o r kt o p o l o g yg e n e r a t o r ( i n e t 3 o ) i nt h i sp a p e r , a n dav i r t u a ln e t w o r ke n v i r o n m e n ti sc o n s t r u c t e d , a n dt h ee n t i r e s y s t e mi ss i m u l a t e d m a j o rt e s to f t h ef o l l o w i n ga s p e c t s ：d e l a y , e f f i c i e n c y , b 斑o f n o d e s a n dl o a do f e d g e s a n dc o m p a r ed e l a ya n de f f i c i e n c yo fu s i n gn e t w o r kc o d i n ga n dn o u s i n gn e t w o r kc o d i n g t h er e s u l tp r o v e st h ep e r f o r m a n c eo fs y s t e ma c h i e v et h er e x t u i r e d r e s u l t s k e y w o r d $ ：a p p l i c a t i o nl a y e rm u l t i c a s t , n e t w o r kc o d i n g , s t e a m i n gm e d i a , 2 - r e d u n d a n t m u l t i c a s tg r a p h 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他入已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：纠 建日期：凌嘲年卅弘日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：纠建 导师签名： 立 墨 日期：a 嬲年岁, 目2 ce t 第一章引言 第一章引言 近年来远程教育、实时网络电视、网络视频会议和视频点播等日益普及，流 媒体数据的分发效率越来越重要，应用层组播技术顺利的解决了传统的c s 架构 中服务器瓶颈的问题，但目前的流媒体分发效率仍然无法满足现有网络应用的需 要，为了进一步提高流媒体的分发效率，本文将网络编码技术和应用层组播技术 相结合，应用于流媒体数据的分发，有效的提高了流媒体的分发效率。本章将介 绍本文的研究背景和主要工作。 1 1 研究背景 1 1 1 组播技术的发展 网络应用的需求是推动网络技术发展的主要动力，随着近年来i n t e m e t 的不 断发展，网络用户的大量增加，还有各种多媒体业务的大量应用以及各种各样的 新兴业务的大量涌现，例如：远程网络教育，视屏音屏点播，远程电视电话会议 等等，导致传统的点对点的单播通信方式由于其严重的带宽浪费和效率低下已经 不能适应这些要求了。于是人们提出了组播的概念。 1 9 8 8 年s t e v ed e e r i n g 首先在他的博士论文中提出口组播。口组播用于一对 多、多对多、多对一的组通信。它是一种有效的数据传输应用，发送的同一数据 在物理链路中只传输一次，减少了数据包在网络传输中的冗余，节约了带宽，提 高了传输效率【l 】。 但实现口组播需要一些前提条件【2 】【3 】【4 】( 5 】，即组播源和接收者以及两者之间 的下层网络都必须支持组播。这包括：1 ) 主机的t c p i p 实现支持发送和接收m 组播，2 ) 主机的网络接口支持组播，3 ) 所有介于组播源和接收者之间的路由 器、集线器、交换机、t c p i p 栈、防火墙均需支持组播，4 ) 有一套p 地址分配 策略，并能将第三层m 地址映射到第二层m a c 地址，5 ) 有一套用于加入、离 开、查询的组管理协议，即i g m p 。6 ) 支持p 组播的应用层软件。这些前提条 件在实现上面却遇到了一些困难。 电子科技大学硕士学位论文 同时，p 组播打破了传统的计费模式，当前的组播的服务模式没有支持组播 的计费，所以d 组播要在当前的服务模式和协议体系结构下普遍化和商业化，会 遇到很多困难。 由于以上原因，d 组播在i n t e m e t 上没有得到广泛的应用。 面对口组播业务在i n t e r a c t 中的困难，近年来一些研究者开始反思口组播体 系结构本身的问题，并针对口组播所存在的这些问题，提出了将复杂的组播功能 放在端系统实现的新思想【6 j 。端系统组播又称为应用层组播( a p p l i c a t i o nl a y e r m u l t i c a s t ) 。应用层组播节点是组播成员主机，数据路由、复制、转发功能都由成 员主机完成，成员主机之间建立一个叠加在口网络之上的、实现组播业务逻辑的 功能性网络，成为叠加网( o v e r l a yn e t w o r k ) 。主机基于自组织算法建立和维护 叠加网。应用层组播的基本模型7 j 如图1 1 所示。 ( a ) m 组播( b ) 应用层组播 图1 - 1i p 组播与应用层组播 那么应用层组播相对于p 组播来说具有以下一些优点【8 】： 1 ) 无组播中复杂的地址结构、复杂的协议。 2 ) 由于应用层组播的状态在主机系统中维护，不需要改变现有的网络路由 器，不需要网络设备的升级和功能扩展，所以应用层组播能够很快的进入应用。 3 ) 接入控制更容易实现。由于单播技术在这方面比较成熟，而应用层组播 是通过终端系统之间单播来实现的，所以差错控制、流控制、拥塞控制容易实 现。 同时，应用层组播也存在一些局限性【9 】： 1 ) 比起口组播来说，应用层组播的可靠性更差。 2 ) 由于端系统对口网络的了解有限，节点参与组网时，只能通过探测一些 网络性能参数，选取的逻辑链路难以优化，所以可扩展性不好。 2 第一章引言 3 ) 在应用层组播中，数据要经过终端系统，所以相比其p 组播来说，延迟 比较大。 4 ) 相对于m 组播来说，由于应用层组播在数据传输过程中会产生数据冗 余，所以传输效率更低。 但是应用层组播相对于口组播来说，优点还是主要的，所以近几年来得到了 很大的发展。目前应用层组播的研究主要集中于视屏会议系统、媒体流的分发系 统和定阅分发系统等【1 0 1 。这主要是利用了多媒体信息的性质，即在传输链路的质 量下降时，用户仍可以收到低速率或者不完整的信息。 1 1 2 网络编码的发展 随着各种通信网络与人们工作生活的各个方面结合的越来越紧密，用户数量 的大量增加，网络服务的多样化以及针对网络传输质量要求的不断增加，如何提 高现有网络资源的利用率，优化网络，已成为当今网络通信研究的重要课题之 一。2 0 0 0 年a h l s w e d e 等【l l 】根据网络信息流的概念指出，网络组播的最大容量等 于发送节点和组播组中各接收节点之间的最小割的最小值，该最值称作网络组播 的最大流限。对于一般的网络，这一容量很难通过传统的组播路由获得，但却可 以通过网络编码组播获得。网络编码指网络节点的输入链路与输出链路上传播的 数据的相互关系。网络编码思想是在y e u n g 的对称分层编码【1 2 1 3 1 1 4 1 【1 5 】的基础上 ( a ) 边的容量 ( b ) 坤组播( c ) 网络编码 图l - 2 口组图播和网络编码 3 电子科技大学硕士学位论文 提出的，他将分层编码在信源节点的编码推广到允许整个网络节点进行编码来获 得网络组播的最大流限。 在图1 2 中给出了一个口组播和使用网络编码的应用层组播的一个例子。在 图1 2 ( a ) 中给出了边的容量；图1 2 ( b ) 中给出了口组播；图1 - 2 ( 0 中是采用网络 编码的组播，可以看出，采用网络编码后，可以获得网络组播的最大流限。从中 可以看出网络编码较口组播的好处。 在文献【1 6 】中通过对网络编码的研究，指出当网络编码的符号域足够大时，通 过网络编码可以获得网络组播的最大流限。文献【1 1 】中提出了线性编码算法，通过 在每一条边上分配一个线性无关的向量，可以获得网络组播的最大流限。在文献 【1 7 】中对在一个无环网络上的线性网络编码做出了扩展，同时对基本的概念做出了 严格的定义。在文献【1 8 l 中提出了网络编码在一个网状组播网络中的应用，它通过 在网状组播网络中构造一个组播树来支持网络编码的应用，并进行了仿真试验来 证明网络编码有助于提高效率。在文献【1 9 】中将网络编码技术应用到了一个大尺度 的内容分发上，提出了一个适用于大型文件分发的组播模型。在最近的【2 0 】【2 1 1 中论 述了网络编码在流媒体上的应用。 现在网络编码的研究引起了许多科研院所的关注。在网络编码提出后不久， 贝尔实验室和m r r 等联合许多研究人员和师生进行合作研究。微软公司也投入很 多人力和物力进行研究。最近惠普和英特尔等也加入了网络编码的研究，有报告 指出，网络编码将引发下一代网络革命。 1 2 论文的主要工作和目标 论文的主要工作包括： 1 ) 对应用层组播技术的研究。研究如何在不改变i n t e r n e t 底层网络结构的前 提下，通过在覆盖网( o v e r l a yn e t w o r k ) 机制下的应用层组播模式为大规模的流媒 体传输服务提供网络支持。 2 ) 对网络编码技术的研究。将它与应用层组播技术相结合，应用于流媒体 的分发，提高流媒体的分发效率，减少中间节点的连接数量，均匀网络链路的压 力，并提高系统的可靠性。 3 ) 同已有协议兼容。为了保持兼容性，提高系统的应用范围，系统应该能 够尽量采用己有的规范协议，能够同现有的媒体应用工具相配合。 4 第一章引言 4 ) 对应用层组播技术仿真的研究。通过对以往应用层组播仿真技术的研究 的基础上，设计了基于i n e t 3 0 的仿真系统，对整个系统做了仿真。 本论文的研究目标为：设计出适合大规模内容分发的组播模型，并结合网络 编码技术，为多媒体数据的视频播放提供网络支持，提高流媒体内容发送的效 率，同时能够减少中间节点的转发压力，均匀网络链路压力，使视频多媒体能够 很好的应用于i n t o r n e t 中。 1 3 论文结构介绍 通过对应用层组播和网络编码技术的结合，设计出了一个基于网络编码的视 频播放系统，该系统在流媒体数据的分发上有更好的效率，大量的减少了网络链 路的压力，并且具有更好的可靠性和柔韧性。 本文组织如下： 第二章“相关技术刀主要介绍了系统所涉及到的相关技术，其中包括： 应 用层组播技术、网络编码技术和实时传输协议r t p 。 第三章“系统的需求分析和整体设计”介绍了系统的整体结构和介绍了系统 的主要模块的设计。 第四章“组播图和网络编码的设计 主要介绍了作为整个系统基础的网络组 播图模型的构造以及用于数据分发的线性网络编码算法的设计。 第五章“网络视频播放系统的设计 介绍了在底层网络构造完成后，整个系 统的完整构造。 第六章“系统仿真和性能测试 对基于网络编码的视频播放系统进行性能测 试。 第七章“结束语对全文做出了总结，同时根据存在的问题，给出下一步的 研究方向。 电子科技大学硕士学位论文 第二章相关技术 本章内容如下：首先介绍组播技术的原理和发展现状，然后介绍网络编码技 术和发展现状，最后介绍多媒体数据传输所采用的传输协议r t p 和r t c p 2 2 1 。 2 1 组播技术 随着近年来i n t e m e t 的不断发展，网络用户的大量增加，还有各种多媒体业 务的大量应用以及各种各样的新兴业务的大量涌现，例如：远程网络教育，视频 音频点播，远程电视电话会议等等，导致传统的点对点的单播通信方式由于其严 重的带宽浪费和效率低下已经不能适应这些要求了。于是人们提出了组播的概 念。下面简单的介绍两种组播模式，m 组播和应用层组播。 2 1 1ip 组播 组播是区别于单播的一种数据传输模式。单播是一种一对一的数据传输模 式，而组播是一种一对多的数据传输模式，可以将一份数据同时发送到一组主机 上。8 0 年代早期，组播技术仅被局域网络所支持，其应用也局限在l a n 环境， 比如以太网和令牌网络。通过网桥和互联网络连接的扩充局域网不支持组播数据 的传输。从一开始组播地址就被设计为口地址簇中的单独的一个地址类别，但是 仍没有标准的使用方法。在8 0 年代后期，d e e r i n g 把组播技术扩展到基于报交换 的互联网的疋网络层中，才真正有了口组播技术1 2 3 】【2 4 】。d e e r i n g 对于口组播的 定义是：将数据包发送到共享相同口地址的一个主机组中，组的成员个数可 以为零个或多个。口组播功能由网络层的路由器实现的，相比单播模式，口组播 是一种实现流媒体分发的有效技术，避免了数据的冗余并提高了网络带宽的利用 效率。在d e e r i n g 提出口组播技术后，组播骨干网( m b o n e ) l z 习诞生，标志着组 播技术在i n t e m e t 上第一次广泛使用。m b o n e 由各个隧道组成，隧道的终端是实 现距离矢量组播路由协议( d v m r p ) 2 6 】的工作站。这些工作站能够处理由单播 技术封装的组播数据包，把数据包发到由路由协议计算的特定的输出接口。1 9 9 2 年3 月，m b o l l e 进行了第一次应用。在s a nd i e g o 举行的i e t f 会议通过m b o n e 网络把音频流发送到全球2 0 个站点。 6 第二章相关技术 由子其内在缺陷d v m r p 是不可扩展的。因为它在构建组播树的时候采用 搿泛洪和剪枝机制。在d v m r p 中，每个路由器周期性地发布i g m p 请求查询 组成员的状态。叶子路由器收到查询请求后，将发送一个剪枝消息表明它没有直 接依附的组成员节点。如果中闻路由器在除与源路由器的接口外的其他所有接口 收到剪枝消息，它将把该消息向源路由器发送。因此，为了支持组播，每个路由 器都必须维护所有组播会话的状态信息，不管路由器是否属于该组播会话。所 以，d v m r p 也被称为密集型协议，即使在剪枝很少的情况下仍将导致消息的密 集型传输。随着m b o i l c 的扩展和本地模式组播的出现，路由器直接支持缀播功 能，密集型组播路由的低效率问题越来越凸现了。从而出现了一种新的组播路由 协议一稀琉型组播路由协议( t h es p a r s em o d em u l t i c a s tr o u t i n gp r o t o c 0 1 ) p i m s m 2 7 1 。是被广泛实现的稀疏型协议。p i m s m 降低了d v m r p 某些方面的复杂 度，但是它却引入了许多其他问题。这些问题到豳前还没有充分的解决。 缀然经过研究者多年的努力，瑶组播仍然存在着许多闯题，阻碍了撙组捶 的开发和组播应用的部署。最突出的问题有组播地址分配模式的缺乏、访问控制 机制和域闻组播路由协议的缺乏粥】阎。 首先是缺乏一个灵活和可扩展的组播地址分配模式。地址分配模式对于任何 组播应用的部署都是非常重要的，因为地址分配模式直接影响可用组播地址的分 配速度。但是，在一个扁平组播地址空间( 每个口地址是3 2 位，没有地理和拓 扑意义) ，设计这种地址分配模式是相当复杂的。所以，大部分组播应用随机选 择一个组播地址，期望它没有被使用。随着组播组数嚣的增加，地址冲突的概率 也随之增加，给组播应用增加了不必要的复杂度。 第二、壹予缺少有效的访闯控卷| 机制，在瑾缀播模型孛，任何主机在没有加 入组播组的情况下，向一个组播地址发送些无用的消息发动攻击，比如著名的 分布式拒绝服务攻击【2 9 】。直到有了i g m p v 3 3 0 1 ，组播接受者才有能力主动选择是 否接受数据。在i g m p v 3 中，增加了数据源端过滤器，允许接受端指定它们想要 侦听的源数据端。但是，i g m p v 3 没有在主机操作系统上广泛的实现，它是扩展 性也还是未知数。 最后，域间组播路由协议的实现是肼组播技术能否广泛部署的关键问题。域 闻组播路由协议提供了自治系统之间的基本路由和聚合路豳的方法，使得缓播服 务提供者能够在不知底层网络的情况下进行透明地连接。路由聚合能有效减小了 路由表的规模，对于i n t e m e t 的扩展是有必要的。但是，到目前为止提出的所有 域间组播路由协议的复杂度和效率都不熊令人满意。 ? 电子科技大学硕士学位论文 p 组播的可靠性也是有待继续研究的问题。在组播模式中，数据包的传输可 靠性和单播中时一样的，都只提供b e s t - e f f o r t 服务，但是口组播路由器在为组播 提供可靠性传输、拥塞控制和流量控制等服务要比单播复杂的多。 2 1 2 应用层组播 由于p 组播所面临的种种困难，人们提出了应用层组播，即将组播的模式放 到应用层上进行。在图2 1 中，对口组播和应用层组播做了一个简单的比较。 ( a ) 口组播( b ) 应用层组播 图2 - 1 应用层组播和p 组播的区别 应用层组播思想提出后短短几年的时间，多个研究机构开展了应用层组播体 系结构的研究项目，包括：n a r a d a 3 1 1 、 a l m i 3 5 1 、h m ( h o s tm u l t i c a s t ) 【3 6 】等。 应用层组播协议通常把组成员组织成两个逻辑拓扑：控制拓扑和数据传输拓 扑。拓扑上的每条边都相当于一条单播连线。控制拓扑主要用来在端系统间周期 性的交换控制信息来发现和恢复由于一些成员的非法离开造成的拓扑破坏。数据 拓扑通常是控制拓扑的一个子集，主要用来表明数据包的传输路径。数据拓扑一 般是一棵树型结构，而控制拓扑则要求有更多的连接，所以通常是一个网状拓扑 结构。因此，根据构建控制拓扑和数据拓扑的顺序，可以将目前网络层组播协议 的实现方法分为：网状优先方法、树状优先方法以及隐式方法三大类。 所谓网状优先就是组成员首先要在他们之间建立网状的控制拓扑，在控制拓 扑上，每一对组成员之间可能不止一条路径。在网状的控制拓扑之上，每个组成 员随后再构造出从数据源到每个组成员的分发树，也就是数据拓扑。而树状优先 8 第二章相关技术 和网状优先恰好相反，组成员首先在他们之间构造组播分发树，随后每个组成员 再通过互相之间交换信息发现他的非邻居成员，并建立与这些非邻居成员的连 接，从而构造控制拓扑。隐含方式构造的控制拓扑需要满足一定的属说性。隐含 方式在构建控制拓扑的同时也就同时定义了数据拓扑。 下面简单对这三种实现方法做一个介绍： 2 1 2 1 网状优先方法 在此类方案中，组的成员首先自己组织成一个网状的拓扑，即控制拓扑，每 两个成员之间有多条路径。目前比较成熟的方案有：n a r a d a ，s c a t t c r c a s t 。在这个 网状拓扑中，每一个成员都会保存这个组中其他的所有成员的状态信息，而且这 个信息将会得到周期性的刷新。 1 n a r a d a n a r a d a 协议首先在组播成员之间建立一个网状的叠加网，然后在叠加网上运 行组播路由协议，建立一棵组播转发树。通过动态探测网络状态，n a r a d a 动态地 对叠加网进行维护和改良。 1 ) 加入新成员时组播树的建立 当有成员加入组时，n a r a d a 假设该成员可以利用外部引导机制获得组成员的 列表。这个列表并不需要非常的完全和准确，但至少要包含一个当前活动的组成 员。 该成员从它的列表中随机的选择一些组成员和给他们发送加入邻居的信息请 求。重复这个过程，直到从列表成员中获得响应。一旦获得加入，成员开始与它 的邻居交换刷新信息，使成员之间能相互的了解。 n a r a d a 中每个成员都会保留所有其它组成员的信息，当组成员发生改变时， 改变信息将会通过控制拓扑传输到所有成员中，也增加了整个系统的健壮性。同 时每个成员也会周期性地产生一个状态刷新消息及时刷新自己所保留的所有成员 状态信息。 2 ) 发送数据传输 n a r a d a 的数据传输拓扑实际上就是控制拓扑的生成树。即建立一个以数据处 理源为根的网状拓扑的生成树。它使用了距离向量协议来使每个成员得到整个网 络的路由信息：成员间定时地交换路由信息( 包括到每个其他成员的路由花费和 相应的路由) ，并且只和相邻成员交换这种信息。n a r a d a 的数据传输拓扑一特定 数据源传输树是采用类似于d v m r p 的反向路径转发算法在每个接收者和源点间 9 电子科技大学硕士学位论文 计算得到的。即组成员m 只接收邻居n 转发的数据源的数据，当且仅当n 是m 到达数据源s 的最短路经上的下一跳节点。 3 ) 节点的退出与失效 组内成员会主动的或被动的离开拓扑。如果是主动离开，该成员只需要提前 通知它的邻居节点，如果被动离开则邻居节点并不能立刻知道组成员的改变，他 们通过在一段时间内没有收到该节点的交换信息知道节点失效。 同时，伴随节点的离开可能会造成网络拓扑的分裂，所以每个组成员会把未 收到更新消息的成员纪录下来，并且周期性的探测这些成员，确定是成员失效， 还是应该在他们之间建立新的链路。 4 ) 控制拓扑的优化 由于成员的加入和离开、网络环境的变化等等都会影响到拓扑的质量，因此 n a r a d a 会周期地对控制拓扑进行优化：每个成员会定期与随机选出的数个成员进 行传输延迟测量，根据这些测量结果利用一个最优化算法来保持叠加网络成员问 路径的最佳化。 2 s c a t t e r c a s t s c a t t e r c a s t 是一种基于应用层组播实现因特网大规模广播业务的体系结构。 主要思路是：在网络中部署一些专用服务器，在应用层构造一个实现组播转发功 能的特殊网络。这和完全基于用户主机的方案相比具有更高的稳定性；但使用专 用的服务器降低了灵活性。 2 1 2 2 树状优先方法 与网状优先方法不同，基于树状优先的应用层组播协议首先建立起一个共享 的数据传输树拓扑。然后，根据这个树状拓扑增加一些成员间的连接便可组成控 制网状拓扑。比较有代表性的协议有o v e r c a s t 、y o i d 和h m t p 等。 1 o v e r c a s t o v e r c a s t 是解决因特网内容分布的一个体系结构，实现可靠的组播业务。通 过在网络中部署o v e r c a s t 节点，然后由应用层组播机制将该节点组成一个骨干转 发网络，能够以可靠的方式实现内容的分发。o v e r c a s t 和s c a t t e r c a s t 思想有些类 似，采用在网络边界部署应用层组播节点组成一个业务网络的策略，两者在实现 应用层组网的机制不同，并且o v e r c a s t 侧重也实现数据的可靠分发。 o v e r c a s t 是为那些具有单个业务源且期望具有高带宽的应用而设计的。 o v e r c a s t 的目标就是要最大化从根到所有节点之间的带宽。 1 0 第二章相关技术 1 ) 树的建立过程 在o v e r c a s t 中假定系统中有一个注册点能够知道组成员的信息，当有一个新 的成员希望加入到组内时，首先通过注册点获得树的根节点的信息。然后把根节 点作为当前节点开始循环的寻找远离根节点但是带宽依然充足的位置。在每一次 循环中，新成员测量它到当前节点的带宽以及它到当前节点的子成员的带宽，如 果它到当前节点子成员的带宽不小于它到当前节点的带宽，那么它把该子成员作 为新的当前节点开始新一轮的加入过程。如果有多个子节点满足带宽的要求，那 么选择距离自己最近的成员。如果没有子成员符合要求，那么当前节点就是新的 组成员应该加入的点。 每个组成员会从它的父节点获得兄弟节点以及祖父和先驱节点的信息，由此 构成控制拓扑。 2 ) 树的优化 每个节点周期性的测量它到兄弟节点以及祖父和先驱节点的带宽。如果节点 发现它与某个兄弟节点之间的带宽不小于它到父节点的带宽，那么它就脱离当前 的父节点加入到这个兄弟节点。同样，如果节点发现它到祖父节点的带宽大于它 到父节点的带宽，那么它脱离父节点加入到祖父节点。当某个组成员的父节点失 效时，它可以利用它保存的祖父以及先驱节点的信息一级级向上追溯直到找到一 个可用的节点为止。 2 y o i d y o i d 是a c l r i ( a t & tc e n t e rf o ri n t e r a c tr e s e a r c ha ti c s i ) 研究中心提出的 基于应用层组播的一整套内容分发的解决方案，包括了应用层组播之上的可靠、 安全、拥塞控制等机制。y m t p ( y o i dm u l f i c a s tt r e ep r o t o c 0 1 ) 是y o i d 体系的 核心，是一种自组织的拓扑管理协议，将主机组织成网状和共享的组播转发树。 当有新成员需要加入时，其会查询r p ( r e n d e z v o u sp o i n t ) 得到已加入的成员的信 息，然后新成员通过这些信息找到合适的父节点。一个节点如果成为这个新成员 的合适的父节点必须满足两个条件：如果选其做新成员的父节点，树拓扑上将不 会出现循环；如果选新成员做其子节点不会超过其度的要求。如果新成员找到多 个合适的父节点，那么它将根据具体实际亮度的要求来找出最合适的一个父节 点。 为了防止由于某个非叶结点的意外断开而使得整个数据传输树被分割，y o i d 中的每个成员会在数据传输拓扑上随机选取一些非父节点填加到其的连接，这样 便组成了控制拓扑。 电予科技大学硕士学位论文 3 h m t p 3 7 1 h m t p ( h o s tm u l t i c a s tt r e ep r o t o c 0 1 ) 与y o i d 有穰多类似之缝，数据传输拓 扑与y o i d 相似，h m t p 中成员的主要目的便是查找合适的父节点。 加入新成员的部骤如下： 1 ) 通过查询r p 获得树的根节点信息。 2 ) 从根节点开始，在每一层h 都会找到离岛已最近的节点x 。如果x 的子节 点数小于其度的上限，那么h 就选择x 作为其父节点加入。否则，h 就会到x 节 点的予节点中寻找合适的父节点。 h m t p 中的成员都会保留它到根节点路径上的所有节点的信息。为了适应网 络环境的变化，每个成员会周期性地通过重新启动上述的新节点加入程序，为自 己寻找更优化的父节点，从而对树的结构进行优傀。 h m t p 并不显示地构成一个控制网状拓扑，而是每个节点都会缓存部分其它 节点的信息，并周期地进行更新。这样，郯使在r p 点不可用时，整个数据传输 拓扑可以在意外情况下进行修复。 4 a l m i a l m i 提出了将应用层组播作为端系统基础服务功能的体系结构。它在操作 系统的套接口( s o c k e t ) 之上，以中间件( m i d d l e w a r e ) 的形式向上层应用提供组 播服务的结构，中闻件实现皇组织组露、组播复制和转发功熊，在组播成员节点 之间组成一个应用层组播网。a l m i 研究组以j a v a 代码实现了中间件的原型。 a l m i 的囱组织协议在组成员节点之闻建立和维护一棵共享的最小代价生成 树( m i n i m u ms p a n n i n gt r e e ) ，支持规模较小的多方通信。a l m i 可以针对上层的 应用震求构建不同性能的叠加网。 2 1 2 3 隐含方式 这里分绍一种有代表性的方法：n i c e 3 羽。n i c e 是一种可扩震的应用层组搋 主要针对大量接收者的低带宽、数据流应用，它基于分层的结构，同时具有较小的 控制受荷，有剩予它的扩展性。n i c e 的数据拓扑隐含在它的控制拓扑中，因丽还可 以支持不同源的数据分发树；并且由于它的分层，进行错误检测较为迅速。 第二章相关技术 2 2 网络编码 2 2 1 网络流的基本概念 对于一个有向图g = - ( v ，功，这里v 表示图中节点的集合，e 表示边的集 合。网络中的一条边用( a ，b ) 表示，这里a ，b 为网络中的两个节点。 定义2 1 一个连通的且无环的有向图c r = - ( v ，e ) ，如果满足下列条件： 1 ) 有且仅有一个入度为0 的顶点s 。这个顶点s 称为发点或源。 2 ) 有且仅有一个出度为0 的顶点t 。这个顶点t 称为收点或汇。 3 ) 每条边上都带有一个非负数的权，称作边的容量。记边( i ，j ) 的容量为 嘶，j ) ，则称图g = - ( v ，e ) 为运输网络，简称为网络。 s 图2 - 2 运输网络 在运输网络中，除发点s 与收点t 外，其余的顶点称为中间点。如图2 2 即为 一个运输网络的示意图。对图中任一顶点v 定义边集： i n e d g e s ( v ) = w i ( w ，v ) e ) o u t e d g e s ( v ) = w l ( v ，w ee ) 分别表示流入和流出节点v 的边的集合，其大小称作节点v 的入度 ( i n d e g r e e ( v ) ) 和出度( o u t d e g r e e ( v ) ) 。 定义2 2 在网络c r = ( v ，e ) 中，如每条边( i ，j ) 都对应一个非负实数f ( i ，j ) ，且它满足条件： 1 ) f ( i ，j ) q ( i ，j ) ，如果不存在边( i ，j ) ，则f ( i ，j ) = 0 。 2 ) 对所有中间节点 ，恒有 1 3 电子科技大学硕士学位论文 厂( f ，d = f ( j ，足) 拒矿 k e g 这表示中间点i 的流量守恒，输入与输出的量相等。 3 ) 对于源点8 和收点t 有： f ( s ，f ) = 厂u ，f ) = w 公式( 2 1 ) 公式( 2 2 ) w 成为该网络流的流量，而且从s 点流出的总量等于流入收点t 的总量。称f ( i ，j ) 为边( i ，j ) 的流量，f 称为网络g 的流函数，简称为流f o 在运输问题中，f ( i ，j ) 表示通过路线( i ，j ) 的商品数量。1 ) 表示线路 ( “j ) 上运输的商品数量不能超过它的容量。2 ) 表示每个中转站运入的商品总 数等于运出的商品总数。3 ) 表示从源点运出的商品总数等于运入汇点的商品总 数。 定义2 3 在网络g 中，( i ，j ) e ，如果f ( i ，j ) = c ( i ，j ) ，则称边( i ，j ) 是饱和的。如果f ( i ，j ) ， c ( x ，朋= + + 如+ 鼢= 4 + 3 + 2 + 4 = 1 3 。 很显然，对于一对节点，其不同的割对应的容量