（计算机应用技术专业论文）基于p4p的应用层组播框架的研究与实现.pdf

中山人学顾l ：毕业论文基于p 4 p 的舷用层组播框架的训 究j 实现 论文题目： 专业： 硕士生： 指导老师： 基于p 4 p 的应用层组播框架的研究与实现 计算机应用技术 潘志辉 常会友教授 摘要 传统c s 模式在服务器性能上的瓶颈和i p 组播在部署推广上的缺陷，导致 应用层组播的提出，将组播功能的实现转移到应用层上。而应用层组播算法与 p 4 p 技术的结合，能有效的优化覆盖网络，提高覆盖网络的拓扑一致性，从而获 得更好的组播性能。 本文首先在引入应用层组播的概念的基础上，对不同拓扑结构的覆盖网络模 型在网络复杂度和组播性能上进行对比。之后，本文介绍了各种典型的算法，包 括小规模多源组播算法e s m 和a l m i ，大规模单源组播算法n i c e 和z i g z a g ，应用 层组播和i p 组播结合的组播算法h o s tm u l t i c a s t ，以及适应节点稳定性不足的 组播算法p e e r c a s t 。同时本文也针对覆盖网络的拓扑一致性介绍了各种增强机 制，包括希尔伯特编码，l t m 技术以及p 4 p 技术。 本文的主要工作首先是设计了基于p 4 p 技术的p e e r c a s t 改进算法p p c 应用 层组播算法，包括组播树构建维护的原语机制和相关的拓扑管理策略。同时，本 文就算法在传输延迟，丢包率和响应时间等组播性能上进行模拟测试，并通过实 验数据和传统的p e e r c a s t 算法进行对比分析。实验结果表明，p p c 算法能获取 比p e e r c a s t 算法更好的组播性能。 最后，本文在算法设计和测试的基础上，设计并实现了p p c 组播算法的框架， 包括根节点服务器，a p p t r a c k e r ，节目列表服务器，数据源服务器和客户端。组 播框架还包括传输协议，会话中的信令交换流程以及客户端状态机的设计。本文 所设计和实现的框架不仅可以应用在流媒体数据组播方面，在许多需要集中进行 数据分发的场合，如视音频会议、文件分发等领域都具有重要的意义。 关键字：对等网络，应用层组播，p e e r c a s t ，p 4 p 技术 t i t l e ：r e s e a r c ha n di m p l e m e n t a t i o no fp 4 pb a s e da p p l i c a t i o nl a y e rm u l t i c a s t f r a m e w o r k m a j o r ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y n a m e ：z l l i h u ip a n s u p e r v i s o r ：p r o f e s s o rh u i y o uc h a n g a bs t r a c t t h eb o t t l e n e c ko ft r a d i t i o n a lc sm u l t i c a s tp a r a d i g ma n dp o o rd e p l o y m e n to fi p m u l t i c a s t ，l e a d t ot h ep r o p o s i n go fa p p l i c a t i o nl a y e rm u l t i c a s tb a s e do np 2 p t e c h n o l o g yt h a tr e a l i z e sl i v es t r e a m i n gm u l t i c a s to nt h ea p p l i c a t i o nl a y e r a p p l i c a t i o n l a y e rm u l t i c a s tb a s e do np 4 pt e c h n o l o g yc a l le f f e c t i v e l yo p t i m i z et h es t r u c t u r e o f o v e r l a yn e t w o r ka n dt o p o l o g i c a lc o n s i s t e n c y , t h u so b t a i n sb e t t e rp e r f o r m a n c e i nt h i sp a p e r , w ef i r s tm a k eac o m p a r i s o no fo v e r l a yn e t w o r kc o m p l e x i t ya n d p e r f o r m a n c eb e t w e e nd i f f e r e n tt o p o l o g ym o d e l sb a s e do nt h ec o n c e p to fa p p l i c a t i o n l a y e rm u l t i c a s t t h e nw eh a v e a ni n t r o d u c t i o no ft y p i c a la l g o r i t h m s ，i n c l u d i n g s m a l l s c a l em u l t i s o u r c es o l u t i o n s ：e s ma n da l m i ，l a r g e - s c a l es i n g l e s o u r c e s o l u t i o n s ：n i c ea n dz i g z a g ，c o m b i n a t i o no fa p p l i c a t i o nl a y e rm u l t i c a s ta n di p m u l t i c a s t ：h o s tm u l t i c a s t ，u n r e l i a b l em e d i as t r e a m i n gs o l u t i o n sf o rt r a n s i e n c ep e e r s ： p e e r c a s t w ea l s oi n t r o d u c et h er e i n f o r c i n gm e c h a n i s m si m p r o v i n gt h et o p o l o g i c a l c o n s i s t e n c y , l i k et h eh i l b e r tc o d i n g l t mt e c h n o l o g y , a n dp 4 pt e c h n o l o g y i nt h i sp a p e r , o u rm a j o rw o r ki sf i r s tt h ed e s i g no ft h ep 4 pb a s e dp e e r c a s t m u l t i c a s ta l g o r i t h mn a m e dp p c ，i n c l u d i n gt h ep r i m i t i v e sa n dt o p o l o g ym a i n t e n a n c e p o l i c i e sp r o p o s e db yp p c t h e n w es t u d yt h ea b i l i t yo fp p ci ns i m u l a t i o nt e s t ，w h i c h p e r f o r m a n c ei sm e a s u r e db yp a c k e td e l a y s ，p a c k e tl o s sa n dr e s p o n s et i m e ，a n dm a k e c o m p a r i s o nw i t hp e e r c a s t e x p e r i m e n tr e s u l t s h o w st h a tp p cp o l i c i e sp e r f o r m c o m p a r a b l yi nm o s ts c e n a r i o s a tl a s tw em a i n l yf o c u so nt h ed e s i g na n di m p l e m e n t a t i o no fl i v em e d i a s t r e a m i n gf r a m e w o r kb a s e do np p cm o d e l t h i sf r a m e w o r kc o n s i s t so fr o o ts e r v e r , a p p t r a c k e r , m e n us e r v e r , s o u r c es e r v e r , a n dc l i e n t t h ef r a m e w o r ka l s oi n c l u d e st h e t r a n s p o r tp r o t o c o l ，m e s s a g ee x c h a n g i n gf l o w , a n dt h ef i n i t es t a t em a c h i n eo fc l i e n t t h ef r a m e w o r ka n dp o l i c i e sd i s c u s s e di nt h i sp a p e rc a na l s ob ea p p l i e di n d a t a d e l i v e r ya p p l i c a t i o n sw i t hr e n d e z v o u sp o i n ts u c ha sv i d e o a u d i oc o n f e r e n c ea n df i l e d i s t r i b u t i o n k e yw o r d s ：p e e r - t o p e e rn e t w o r k ，a p p l i c a t i o nl a y e rm u l t i c a s t ，p e e r c a s t ，p 4 p i i i 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 学位论文使用授权说明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其它方法 导师签名 日期：铷口雾厂月z 乙i t o 幸i套 位 驾 学 臣形觥勿 中山人学硕? i ：毕业论文基于p 4 p 的心用层组播框架的研究j 实现 1 1 研究背景 第1 章引言 互联网的发展使得高速、实时的流媒体应用大量涌现，实时流媒体应用已经 成为了i n t e r n e t 流量的重要组成部分。i r e s e a r c h 一份关于中国p 2 p 流媒体的 研究报告指出，2 0 0 6 年中国的p 2 p 流媒体用户量有四千万，预计到2 0 1 0 年中国 的p 2 p 流媒体用户量将超越1 5 亿，其中日均使用用户数量占用户量的4 0 。流 媒体应用的发展使得对组播模式的需求大量增加。 组播模式可以使用传统的c l i e n t s e r v e r 模式，通过在服务器和客户端之间 建立多条单播连接来实现。但是所需要的单播连接将会大量消耗网络资源，增加 数据冗余和服务器负担，同时服务器的带宽与处理能力也成为流媒体用户规模增 长的瓶颈。因此，需要对组播模式进行更高效的实现。 b ( a b b ) d ( d ) 图1 1 三种不同的组播方式 ( a ) 网络拓扑结构；( b ) 单播；( c ) i p 组播； ( d ) 应用层组播 d 中山人学硕i ：毕业论文基于p 4 p 的应用层组播框架的研究j 实现 由e n ds y s t e mm u l t i c a s t “1 给出图1 - 1 。其中图1 - 1 ( a ) 给出的是一个网络物 理拓扑，其中参与组播的主机是a ，b ，c 和d ，r 和r 。是路由器。连接上的数字 代表连接的代价( 比如传输延迟，丢包率等) ，由此可以看出，r 。到r ：的连接是 昂贵的骨干连接，而其他连接是代价较小的本地连接。主机a 是数据源，需要发 送数据到其他主机。图1 - 1 ( b ) 给出的是通过传统c s 模式实现的组播。其中数 据源a 首先需要将数据复制成三个相同的拷贝，再分别发送到其他节点。从图中 可以看出它到r 。的连接上有很大的数据冗余，而且r 到r ：的昂贵连接上也有数 据冗余。随着用户规模的增长，服务器的性能以及带宽将成为整个组播系统的瓶 颈。 针对流媒体应用发展对组播模式的需求，i p 组播技术瞳1 应运而生。如图1 - 1 ( c ) 所示，主机a 只需要发送一份数据到r ”不需要对数据进行复制。对数据的复制 和转发工作交由路由器负责完成并最终发送到其他节点，这样在消除连接中数据 冗余的同时也大幅度降低数据源的负担；同时数据的复制和转发工作被分发到各 路由器中进行，使得服务器不再是用户规模增长的瓶颈。由于路由器对组播功能 的支持，构建i p 组播网络所需要的链路数量也大量减少盼1 。 i p 组播的特点h 1 如下： 1 ) 源可以在任意时刻发送数据包，只需在数据包中包含相关的信息，无需 注册，也无需考虑传输的可靠性、拥塞控制和q o s 保证等因素。 2 ) 一个组可以拥有任意数量的源，而每个组只需要一个组播地址。 3 ) 节点可以任意的加入或离开一个组播组，无需与某个组播组管理者协商。 i p 组播所实现的组播模式能有效的降低网络和服务器的负载，提高网络资源 的利用效率。自i p 组播标准晴3 发布以来，不断有相应的i p 组播协议发布，关于 i p 组播的研究也一直在进行。但是，i p 组播的发展和推广仍然存在很多尚未解 决的问题： 1 ) 扩展性差；i p 组播要求所有的路由器都支持，并为每个组播组保存状态。 这个要求不但破坏i p 层“无状态”的原则和初衷，而且给i p 层引入了更大的复 杂度和扩展限制。 2 ) 缺乏地址分配机制；i p 组播需要一个扩展性强的地址分配机制，以便节 点能快速的发现并加入组播组。但是，组播组的地址是一个介于2 2 4 0 0 0 和 中山人学硕i ：毕业论文基于p 4 p 的应用层组播框架的研究j 实现 2 3 9 2 5 5 2 5 5 2 5 5 之间的3 2 位数字，不包含任何地理位置或网络拓扑上的意义。 3 ) 安全机制存在问题；由于接入控制的缺乏使其容易受到分布式拒绝服务 的攻击。而且在i p 组播中任何主机都可以向一个组播地址发送数据，而组播组 中的节点无法对数据源进行选择。 4 ) 尽力发送的缺陷；i p 组播是一种“尽力发送 的服务，难以提供可靠性、 拥塞控制和流控制等服务。 由于i p 组播在技术和策略上都存在着难以解决的问题，使其无法在全球范 围内推广。因此有研究者提出将组播功能转移到更上层的应用层实现，通过应用 层组播1 ( a p p l i c a t i o nl a y e rm u l t i c a s t ) 解决i p 组播在推广中遇到的问题。 如图i - i ( d ) 所示，应用层组播通过主机之间的单播连接在应用层上构造覆盖 网络，从而实现组播功能。参与组播的主机通过覆盖网络共享数据，所有数据都 在主机上进行复制和转发，并在单播连接中传输。由于组播数据是通过单播连接 传输的，因此组播的q o s 保证能通过单播连接实现。相比i p 组播，在应用层组 播中主机需要额外的实现数据复制和转发的功能，同时链路中的冗余依然存在， 部分节点的传输延迟甚至还增大了( 如图卜1 ( d ) 的节点d ) 。但相比由传统c s 模式所实现的组播，链路中的冗余已经大幅度的降低，而且能避免数据传输在昂 贵的骨干链路上的冗余。 b db ( b ) d 图i - 2 低效的覆盖网络 在应用层组播中数据的传输是通过应用层上的覆盖网络而实现的，因此覆盖 网络的效率直接影响着组播的性能。传统c s 模式实现的组播可以看作是一种星 型拓扑的覆盖网络，不过这是一种低效的覆盖网络，无法有效利用网络资源和降 低服务器的负担。图i - 2 所示的也是低效的覆盖网络：主机之间的单播连接多次 占用昂贵骨干链路，在增大数据传输代价的同时，也降低了组播性能，加重i s p 3 中山大学顾十毕业论文基于p 4 p 的应用层纽播框架的研究与实现 在网络维护上的负担。 为了构造高效的覆盖网络，解决覆盖网络的拓扑一致性问题，本文使用了p 4 p 技术对覆盖网络进行优化。p 4 p 口1 ( p r o a c t i v en e t w o r kp r o v i d e rp a r t i c i p a t i o n f o rp 2 p ) 技术的原理在于让i s p 参与到覆盖网络的构造和管理中，i s p 提供一 个i t r a c k e r 接口，将节点的i p 地址匹配成和一个和物理网络位置信息相关的元 组，节点根据元组提供的信息对覆盖网络进行优化。通过优化提高覆盖网络的拓 扑一致性，从而减少单播连接对骨干网络的使用，提高覆盖网络的组播性能，降 低i s p 在网络维护上的负担。 1 2 本文的主要工作和研究意义 本文首先通过当前流媒体应用的统计情况，对组播模式的需求增加进行了分 析。本文同时分析了组播技术的传统实现方案，包括c s 模式和i p 组播技术， 以其它们在技术框架和扩展性上的缺陷。在此基础在引入应用层组播方案，并对 其性能和传统的组播方案进行对比和分析。 同时，本文对主流的应用层组播模型进行对比和分析，主要分析重点在于网 状拓扑模型和树状拓扑模型在可扩展性，鲁棒新和各项组播性能上的差异。接下 来本文就两种覆盖网络模型在不同应用场合下的经典算法进行介绍和分析，包括 小规模多源组播算法( e s m 和a l m i ) ，大规模单源组播方案( n i c e 和z i g z a g ) ， 应用层组播和i p 组播结合的方案( h o s tm u l t i c a s t ) ，以及适应节点稳定性不足 的组播方案( p e e r c a s t ) 。同时本文也就应用层组播在拓扑一致性上的增强机制 进行介绍和分析，包括希尔伯特编码，l t m 技术以及p 4 p 技术。 本文的主要工作体现在一下几个方面。 1 ) 本文基于p 4 p 技术设计了p e e r c a s t 的改进算法p p c 应用层组播算法。算 法对实现组播树构建和维护的原语机制进行重新定义，同时在p 4 p 技术的基础上 重新设计组播树的拓扑管理策略，并在此基础上引入超级点管理策略，对组播树 的结构和性能进行进一步的优化。 2 ) 对新设计的p p c 应用层组播算法就组播性能进行测试。测试的主要性能 指标分别是算法的丢包率，传输延迟和响应时间；测试所使用的工具是b r i t e 4 中山大学顾： 二毕业论文 基于p 4 p 的应用层组播框架的研究与实现 和p e e r s i m ，通过测试结果的分析，总结出p p c 算法在各项组播性能上相比 p e e r c a s t 算法都有改善。 3 ) 对p p c 组播算法进行框架和传输协议上的设计和实现。p p c 算法的框架包 括根节点服务器，a p p t r a c k e r ，节目列表服务器，数据源服务器和客户端。传输 协议，信令交换流程和客户端状态机的设计参考了r f c 3 2 6 1 的s i p 协议和 r f c 3 5 8 8 的d i a m e t e r 协议。 本文的主要研究意义如下所述： 1 ) 引入p 4 p 技术框架，并将其作为覆盖网络拓扑一致性的增强机制；相比 其他拓扑一致性的解决方案，p 4 p 技术在提高覆盖网络拓扑一致性的同时，也减 少了对骨干网络的使用，从而降低了i s p 在网络维护上的成本。 2 ) 结合p 4 p 技术设计改进p e e r c a s t 算法，对算法原语以及组播树的维护策 略进行重新设计。应用层组播算法p e e r c a s t 能有效的降低节点稳定性不足对覆 盖网络的影响，但同时覆盖网络的设计没有考虑到和底层物理网络保持一致，因 此需要相应的增强机制提高覆盖网络的拓扑一致性。 3 ) 引入超节点策略对p e e r c a s t 拓扑维护策略进行优化。传统p e e r c a s t 算 法中，节点间完全对等，其覆盖网络的异构性问题没有很好的解决。因此，改进 p e e r c a s t 算法引入了超节点策略，将处理能力强，稳定性高的节点作为超节点 放置在组播树的上层，从而提高覆盖网络的稳定性。 4 ) 对基于p 4 p 技术的p e e r c a s t 组播算法进行实现，包括根节点服务器， a p p t r a c k e r ，节目列表服务器，数据源服务器和客户端。系统具有良好的可扩展 性，同时能方便的对各种系统性能的数据进行收集。 5 ) 本文所研究的算法不仅能应用在流媒体直播的应用上，对于许多需要集 中进行数据分发的场合( 如视频会议和文件分发) 都有重要的应用意义。 1 3 论文的组织结构 本文一共分为六章，主要对应用层组播的体系结构，各种典型的组播算法方 案以及针对拓扑一致性的增强机制进行介绍和分析。同时提出了基于p 4 p 技术的 p e e r c a s t 应用层组播算法，并进行设计和实现。文章各章的组织如下： 中山人学硕i ：毕业论文 基于p 4 p 的应用层纽播框架的研究与实现 第l 章为引言部分，主要介绍论文的选题背景，研究意义，以及论文主要工 作和创新之处。 第2 章主要介绍应用层组播的体系结构，拓扑网络的分类( 网状拓扑和树状 拓扑) ，并结合实例对各种应用层组播算法进行介绍和分析，对在不同应用场合 下提出的应用层组播算法进行对比分析。同时本章针对应用层组播关于拓扑一致 性问题的解决方案和技术，并对具体的技术实例进行介绍和分析，介绍了p 4 p 技术的框架以及其相对于其他技术方案的优势。 第3 章对基于p 4 p 技术的p e e r c a s t 应用层组播算法相关的原语以及组播树 的各种维护策略进行设计，根据i t r a c k e r 提供的元组数据对原有的p e e r c a s t 组播原语和拓扑维护策略进行优化。 第4 章提出了应用层组播的主要性能指标( 传输延迟，丢包率和响应时i n ) ， 利用p e e r s i m 工具设计实验场景，对基于p 4 p 的p e e r c a s t 算法进行模拟实验测 试，同时将其结果和原有的p e e r c a s t 算法进行对比分析。 第5 章对整个基于p 4 p 技术的p e e r c a s t 组播算法的系统架构进行设计和实 现，包括各个服务器，客户端，传输协议和状态转换图等。 第6 章是对全文的总结，并且对进一步的研究工作做出展望。 6 中山大学硕上毕业论文基于p 4 p 的应用层组播框架的研究j 实现 第2 章应用层组播算法的相关研究 应用层组播的提出是为了解决i p 组播在技术，策略和推广上出现的问题。 应用层组播以其基于应用层上所构造的覆盖网络，有效的实现了组播功能，并解 决了地址分配，安全机制，q o s 保证等i p 组播所无法解决的问题。但是，由于 组播功能的实现被转移到更上层的应用层，因此在组播性能上还是有所牺牲( 如 额外的传输延迟，主机负担的增加等) 。当前很多相关研究都围绕着如何提高应 用层组播的性能、改善其缺陷而进行的。本章主要介绍了应用层组播的体系结构， 以及针对不同应用场合的各种典型组播算法实例进行介绍和分析。 2 1 应用层组播的体系结构 应用层组播的实现是基于应用层上所构建的覆盖网络，数据的复制和转发在 主机中进行，并通过主机间的连接进行传输。在i p 组播中，数据的复制和转发 是在路由器中进行的，应用层组播将这项功能交由主机去实现阳1 ，使得路由器不 需要为组播而支持额外的功能。 图2 - 1 应用层组播覆盖网络示例 应用层组播中的覆盖网络是指由节点在应用层上自组织而成，架构在底层物 理网络上的逻辑网络。如图2 - 1 所示，虚线以上部分是主机自组织而成的覆盖网 络，而虚线以下则是物理网络拓扑。主机之间通过连接构造出组播树，每一条主 机之间的连接都对应于底层网络的一条单播连接。主机同时是数据的接收者和分 7 中山人学硕i ：毕业论文 幕于p 4 p 的应用层纽播框架的研究j 实现 发者，在接收到数据的同时也将它们转发到其他主机上。应用层组播的覆盖网络 主要有两种构造方式四1 ：网状拓扑和树状拓扑。这两种覆盖网络在构造和维护上 都不同，因而在组播性能上也有很大的差异。 2 1 1 基于网状拓扑的覆盖网络模型 在网状拓扑的应用层组播算法中，覆盖网络的构造主要基于对一个m 维坐标 空问的划分，由一个主机获取其中一个划分的区域。在m 维坐标空问中每个主机 所获得的区域都由一个m 维坐标标识，这个坐标就是主机在覆盖网络中的逻辑地 址。根据覆盖网络中相邻区域距离的差异，网状拓扑网络有规则和不规则之分。 如图2 - 2 所示，在规则的网状拓扑中，任意两个相邻区域之间的距离是一致的。 而不规则的网状拓扑中的距离是随机的，没有气定规律。 53 l 42 ( a )( b ) 图2 - 2 网状拓扑示例 ( a ) 规则网状拓扑( b ) 不规则网状拓扑 组播算法e n ds y s t e mm u l t i c a s t ，a l m i m 1 和c a n b a s e dm u l t i c a s t 2 1 都是 典型的基于网状覆盖网络的应用层组播算法，参与组播的主机构建覆盖网络后， 以其为基础生成组播路径以实现组播。由于组播路径是基于覆盖网络而生成的， 因此节点问一般会有多条组播路径，不会因为某个节点的退出或失效而导致覆盖 网络的分裂，从而使得覆盖网络具有比较好的鲁棒性。n a r a d a 和a l m i 所使用的 覆盖网络是基于以节点连接延迟为边的连通图，并以此为基础构造最小生成树作 为组播路径。c a n - b a s e dm u l t i c a s t 的覆盖网络一般是基于对二维坐标空间的划 分，并通过改进的贪心算法实现流媒体数据的传输。但是，由于节点之间存在着 8 中山人学硕 ：毕业论文基于p 4 p 的应用层组播框架的研究与实现 冗余连接，因此需要采取一定的算法来避免组播路径中环路n 3 1 的出现。 2 1 2 基于树状拓扑的覆盖网络模型 在图2 - 1 所给出的覆盖网络就是基于树状拓扑的覆盖网络。这类覆盖网络是 一个无环图，每一个节点间只有一条连接，不会出现环路。同时组播树深度的增 长是和节点规模增长的对数成正比，因此即使是叶子节点也不会出现太大的传输 延迟。这些优势使得算法的设计和实现都比较简单，组播性能也比较好。但是也 因为树状拓扑的覆盖网络是一个无环图，因此任意节点的退出和失效都会使得覆 盖网络分裂，需要采取一定的措施保持其鲁棒性( 如备份节点，多树策略和超节 点策略等) 。 树状拓扑的覆盖网络分为共享树和源树两种。应用层组播协议y o i d 1 就是典 型的使用共享树作为组播树构建策略的算法。在共享树中所有组播的数据都会先 发送到组播树的根节点，再由根节点负责将数据分发到其他节点。由于所有数据 源都共享一棵组播树，因此不需要为每个数据源都构建相应的组播树。虽然组播 树构建和维护的成本降低了，但是由于所有数据都需要发送到根节点，使得根节 点容易成为组播性能的瓶颈，而且并不是每个数据源都能达到最优的组播效率。 因此，共享树拓扑在应用层组播中使用得比较少。 应用层组播算法n i c e n 5 引，z i g z a g m l 和p e e r c a s t 埔1 都是使用源树拓扑的典 型实例，每个数据源都为自己构造一个组播树，以实现高效的数据路由和组播性 能。但是由于每个数据源都需要构造一棵组播树，因此需要为所有组播树维护相 应的状态信息，大量增加覆盖网络的维护开销。p e e r c a s t 是单源的组播算法， 而n i c e 和z i g z a g 算法的设计保证所有数据的组播路径都基于同一棵组播树，减 少组播树的维护开销。相对于共享树而言，源树具有一定的优势，因为源树能为 每个数据源的组播进行优化，同时在经过优化后能降低组播树的维护成本( 如 n i c e ) 。而且源树不会加大根节点的负担，适合主机处理能力相对不足的情况。 网状拓扑和树状拓扑两种覆盖网络之间的区别主要在于节点之间连接数量 的不同，两者的特性和组播性能也不同。基于网状拓扑的覆盖网络能获得较好的 9 中山人学硕i ：毕业论文 基于p 4 p 的心用层组橘框架的研究与实现 鲁棒性，但同时组播性能较低，扩展性也较差。而基于树状拓扑的覆盖网络则简 化了网络结构和算法设计，整体组播性能上比网状拓扑的覆盖网络好：但同时覆 盖网络容易分裂，鲁棒性较差。两种拓扑都有其对应的算法，需要针对不同的需 求和应用场合选择合适的算法。 2 2 应用层组播算法的典型实例 在应用层组播的相关研究中，最早出现的协议是2 0 0 0 年的n a r a d a 口引，通过 测试和实践证明了应用层组播的可行性。在此之后，针对不同应用场合需求的各 种应用层组播算法不断涌现，针对各种组播性能( 传输延迟，丢包率和覆盖网络 鲁棒性等) 的研究也越来越多。应用层组播算法就其应用场合可以分为小规模组 播方案，大规模组播方案和混合式方案等。 在接下来要介绍的应用层组播算法中，n a r a d a 和a l m i 都是小规模的组播方 案，而n i c e ，z i g z a g ，y o i d 和c a n - b a s e dm u l t i c a s t 则是大规模的组播方案。 h o s tm u l t i c a s t 乜叫是i p 组播和应用层组播混合的组播方案，而p e e r c a s t 则是适 应节点稳定性不足的组播方案。 2 2 1 终端系统组播算法e n ds y s t e mm u l t i c a s t 组播算法e n ds y s t e mm u l t i c a s t 中提出了应用层组播协议n a r a d a ，在节点 之间的连通图上构建组播网络。其拓扑网络构造过程如下： 1 ) 将所有组播成员连接成一个连通图( 网状拓扑) 2 ) 根据各个数据源为根在连通图上构建最小生成树，通过生成树中的路径 分发数据。 如图2 - 3 所示，参与组播的主机a ，b ，c 和d 首先构造出一个连通图，节点 之间的连线表示节点间连接的延迟。当数据源a 需要分发流媒体数据的时候，以 节点a 为根所构造出的最小生成树如图2 - 3 ( b ) 所示。并以所获得的最小生成树 作为组播路径。 1 0 中山大学硕i ：毕业论文基于p 4 p 的应用层组播框架的研究j j 实现 bdb d ( a )( b ) 图2 - 3e n ds y s t e mm u l t i e a s t 组播网络构造示例 在上图所示的组播网络中，链路上的数据冗余依然存在，部分节点( 如节点 d ) 和数据源的连接延迟相比i p 组播也增大了，但是n a r a d a 构造最小生成树的 方法类似于i p 组播协议d v r m p 胫，同时节点之间的连接有效的避免了对骨干网 络的使用，因此在所有节点的处理能力以及连接延迟相当时候，算法可以获得近 似于i p 组播的组播性能。 每个数据源在分发数据之间都会在覆盖网络中构造以该节点为根的最小生 成树。不同数据源的数据组播在不同的组播树中进行，这样在针对不同数据源进 行优化的同时，也避免了因某个节点的失效而导致覆盖网络分裂。但是为了对组 播树进行维护和优化，所有节点都需要维护其他节点的状态数据，路由信息等， 并定期更新，从而对组播树进行优化。由于节点之间需要不断的通信以测量传输 延迟，交换状态信息，并检测节点的离开或失效，在组播树维护上产生了大量的 开销，同时也要求节点具有比较高的稳定性。因此，n a r a d a 协议的扩展性较差， 只适合于节点规模较小且稳定性强的组播应用，如视频会议。 2 2 2 具有管理节点机制的a l m i 组播算法a l m i ( a p p l i c a t i o nl a y e rm u l t i c a s ti n f r a s t r u c t u r e ) 类似于 n a r a d a 协议，也是适用于规模较小且节点稳定性高的组播应用。它和n a r a d a 协 议最大的区别在于组播网络由管理节点( s e s s i o nc o n t r o l l e r ) 和会话节点 ( m e m b e r ) 组成。管理节点负责向会话节点发送管理信令，构建并维护组播网络。 会话节点参与流媒体数据的分发，其流媒体分发所需的最小生成树由管理节点根 据各个节点的状态而构造。如图2 - 4 所示。 中山大学硕一i ：毕业论文基于p 4 p 的应用层纰播框架的研究j 实现 图2 - 4 a l m l 架构不例 管理节点完成组播树的构造之后，向所有会话节点发送管理信令，通知会话 节点所在组播树的父节点。会话节点收到信令后和相应的父节点建立连接，从而 加入到组播网络中。 在流媒体数据组播中，会话节点的加入，离开和失效由管理节点进行监控， 同时根据各个节点状态和连接延迟的变化，定期向会话节点发送控制信令，更新 组播树的结构。由于使用了管理节点对会话进行统一的管理，有效的降低了组播 网络在维护上的开销，但是也使得管理节点的性能成为了组播网络的瓶颈，而且 一旦管理节点失效将导致整个组播网络的崩溃。同时组播树的构造是统一进行 的，无法根据不同的数据源进行优化。和n a r a d a 一样，a l m i 在组播树的维护成 本上也是随着组播成员的增加而线性增长，因此极大的限制了a l m i 算法的可扩 展性。 2 2 3 基于c a n 的组播算法c a n - b a s e dm u l t i c a s t c a n b a s e dm u l t i c a s t 是通过对c a n ( c o n t e n ta d d r e s s a b l en e t w o r k ) 进行 扩展而实现的应用层组播算法。不同于e n ds y s t e mm u l t i c a s t 和a l m i ，c a n 的 覆盖网络的构造方式是将一个m 维的坐标空间进行划分，使得每个节点获得其中 的一个区域。如图2 5 所示，c a n 所划分的空间是一个2 维的坐标空间，图中任 意两个区域之间的距离不相等，属于不规则的覆盖网络。 在这样的覆盖网络中，路由算法的设计非常的简单高效，只需要根据贪心算 1 2 中山人学硕l 毕业论文 基于p 4 p 的应用层组播框架的研究。j 实现 法的原则将数据发送到和目标节点所在区域坐标相近的区域就可以了。在图 2 5 ( a ) 中，区域1 的节点需要发送消息到坐标为( x ，y ) 的区域，它只需要将消息 发送到和目的区域较近的区域4 ，再转发到目的区域。而且即使出现节点失效也 能在短时间内找到新的路由路径进行数据传输。 当有节点需要加入到网络中的时候，该节点会向某个坐标发送请求。该坐标 所属区域接收请求，并将区域分成两部分。一部分为原来管理该区域的节点所有， 一部分分给新加入的节点，并通知相邻区域修改状态信息。同样道理，当有节点 需要离开网络的时候，会把它所拥有的区域合并到相邻区域中，并通知其他邻居 区域修改状态信息。 62 3l5 i l 1 r 4 j ， z ( x ，y ) ( a ) 一 6 + 2一卜 + i 4 -一卜 _ - 3 _l 一7 -5 卜一一卜_ i 卜 4 一 li _ 一卜 士 i _一 4 - ( b ) 图2 5c a n b a s e dm u l t i c a s t 不例 ( a ) 数据路由( b ) 区域分割和流媒体数据组播 在c a n 上进行流媒体组播非常简单，流媒体数据源只需要根据贪心算法，将 数据沿着不同的维分发就可以了。如图2 - 5 所示，流媒体数据分别沿着x 轴和y 轴传输。每个节点收到流媒体数据之后，将数据转发到还没收到数据的邻居节点 所在的区域。如果c a n 的覆盖网络设计和地址分配机制能有效反映节点底层物理 网络信息，那么覆盖网络将获得较好的拓扑一致性，同时组播性能也大为提高。 c a n b a s e dm u l t i c a s t 具有很好的扩展性，适用于大规模多源的流媒体组播应用 上。但是由于在贪心算法的使用上会产生冗余数据( 部分区域会重复接收到流媒 体数据) ，覆盖网络的设计并不一定能反映底层物理网络的特性，因此算法的组 中山人学硕：j ：毕业论文基于p 4 p 的应用层纽播框架的研究与实现 播性能仍有提升的空间。 2 2 4 基于源树拓扑的y o i d y o i d 属于早期的应用层组播算法，其协议y m t p 由a c i r i 研究中心在2 0 0 0 年提出。y o i d 所使用的覆盖网络结构是共享树，因此在流媒体组播过程中，流 媒体数据首先被传送到根节点再分发到各个节点；这导致根节点容易成为组播性 能的瓶颈。同时，y o i d 的算法设计比较复杂，在运行过程中需要将节点同时组 织成网状网和共享树，因此y o i d 算法的组播性能较低。 ( a )( b ) 图2 - 6 共享组播树示例 ( a ) y o i d 共享组播树( b ) h o s tm u l t i c a s t 组捅树 2 2 5 混合式组播算法h o s tm u l t i c a s t h o s tm u l t i c a s t 将应用层组播和i p 组播相结合，是一种混合式的应用层组 播算法。算法在可以进行i p 组播的组播岛中进行i p 组播，在不能进行i p 组播 的网段之间进行应用层组播。在每个可以进行i p 组播的组播岛内部，指定一个 节点作为组播岛的代表，通过在各个代表节点之间的连接生成组播树，把所有使 用i p 组播的组播岛连接起来。在h o s tm u l t i c a s t 中，组播岛的代表节点所构成 的组播树是一棵共享树，因此组播效率较低。 1 4 中山人学硕e 毕业论文 基于p 4 p 的庶用层纽播框架的研究与实现 2 2 6 基于层次化分群思想的n i c e 应用层组播算法n i c e 利用了分层( l a y e r ) 和分群( c l u s t e r ) 的思想，把 参与组播的节点构造成一棵层次化的组播树。算法在构造组播树的时候，首先将 所有节点放置在最低一层，并将该层的节点分成若干个群，每个群包含k 到3 k 1 个节点( k 是一个随机常数) ；在每个群中选出一个节点作为领导，负责将组播 数据发送到该群里的其他及节点。底层的分群操作完毕之后，每个群的领导节点 构成了上一层的节点，递归的对上一层进行分群、选择群领导的操作，直到最上 一层只有一个节点，完成层次化组播树的构造工作。 i 一一一一一一一一一一一一一： 第o 瑶筇l 层 a 第2 1 2 - 图2 7n i c e 层次化组播树的构建 如图2 - 7 所示，在开始构造组播树的时候，算法将所有节点都放置在第0 层； 完成了分群操作之后，节点a ，b 和c 成为了它们所在群的领导节点，并成为了 第1 层的成员节点。在第二层的分群操作中，所有节点都被分在同一个群，并选 择节点a 作为领导节点，成为第2 层的成员节点。由于第二层只有一个节点a ， 因此不需要再进行分群的操作，组播树的构造也就此完成。 在层次化的组播树中，大部分节点都位于最低的一层，一般只和群内的其他 节点通讯。领导节点负责把接收到的组播数据分发给群内的各个节点。在组播过 程中，流媒体数据首先从数据源节点传输到所属群的领导节点，并由领导节点分 发给群中的其他节点。然后该群的领导节点将数据传交由它在上一层所在群的群 领导进行分发。由于大部分节点位于底层，只有少量节点负责组播数据的路由， 中山人学顾i ：毕业论文基于p 4 p 的应用层纽播框架的研究1 i 实现 n i c e 这种层次化的组播树能获得较好的组播性能。 ll 图2 - 8n i c e 数据组播过程 如图2 8 ( a ) 所示，数据源节点c 需要发送数据到其他节点。由于节点c 是它 所在群的领导节点，所以节点c 首先将数据发送到它所在群的其他节点，然后将 数据发送到它在更上一层中所在的群的领导节点a 。节点a 收到数据后，首先将 数据分发给群中的其他节点( 节点b ) ，然后在下一层的群中分发数据；而节点b 收到数据后也是类似的过程。图2 8 ( b ) 也是类似的过程，只是数据源节点e 本 身不是该群的领导节点，需要先将数据发送给该群的领导节点a 。 n i c e 拥有特殊的分层分群的结构，扩展性比其他协议好。同时节点只和同一 个群的节点通讯，因此n i c e 的组播效率很高( 所有的信令传输的最大时间消耗 是0 ( kl o g 。n ) ，其中k 是群体的规模，n 是整个组播网络的规模) ，同时不同数 据源能使用相同的组播树，因此能扩展到多源应用中。但是n i c e 算法对