（计算机应用技术专业论文）基于优先级的应用层平衡组播树算法研究.pdf

南京邮电大学 硕士学位论文摘要 学科、专业：工学计算机应用技术 研究方向：计算机通信与网间互联技术 作者：周佩 指导教师：许建真副教授 题目：基于优先级的应用层平衡组播树算法研究 英文题e l ：p r i o r i t y b a s e db a l a n c e dt r e eb u i h i n ga 塘o r i t h mf o ra l m 主题词：应用层组播；优先级；平衡树；健壮性 k e y w o r d s a p p l i c a t i o n l a y e rm u l t i c a s t ；b a l a n c et r e e ；p r i o r i t y ；r o b u s t 南京邮电大学硕士研究生学位论文摘要 摘要 应用层组播( a p p l i c a t i o nl a y e rm u l t i c a s t ，a l m ) 是在端系统实现组播的一种组播技术， 其数据的转发点是主机通过传统的单播技术来实现各转发点之间的数据传输，该技术不仅 避免了对基础设施的依赖，而且同时又可以充分利用i p 组播已有的布局，其灵活性和可 扩展性得到极大的提高。 本文详细分析了组播树中节点出度对组播树性能的影响，充分论证了其数学模型的健 壮性，并在此的基础之上引入一种基于优先级的平衡应用层组播树算法( p r i o r i t y - b a s e d b a l a u l c e dt r e eb u i l d i n ga l g o r i t h m ，p b t a ) 。其主要特点有： 1 为提高组播树的稳定性和效率，该算法引入动态优先级的概念，对节点的资源、 移动次数、移动概率等做综合评定以生成动态优先级。然后根据节点优先级的大小对 组播树进行构建，从而生成了一种迅速找到最高优先级成员，并使组播域中主节点的 负载处于理想状态的方法。 2 该算法引入一种同时在根节点和r p 节点存储节点信息表的方式，给整个组播域内 的节点信息列表提供备份，以防止组播树中r p 节点的突然失效而导致的组播树结构 较大变化，从而提高组播树的稳定性和缩短组播树重构的时间。 3 为防止组播树结构的不协调，该算法引入平衡的概念，控制组播树的各个节点的 出度不超过常数k ，使树中各节点拥有的子节点数目得到适当控制，以防止因为某些 节点而影响整个组播树的性能，从而使构建的组播树结构相对均衡，提高组播树的数 据转发能力。 在此基础之上，本文采用了一系列的仿真试验对此算法的数学模型进行验证，通过对 组播树的吞吐量和稳定性的分析，并与其他多种组播树构建算法进行比较，实验结果表明 基于基于优先级的平衡应用层组播树算法进行组播树的构建更加快速和有效。 关键词：应用层组播；优先级；平衡树；健壮性 ) 南京邮电大学硕士研究生学位论文 a b s t r a c t a p p l i c a t i o nl a y e rm u l t i c a s t ( a l m ) i sam u l t i c a s tt e c h n o l o g yw h i c hi m p l e m e n t e do nt h e t e r m i n a l so fan e t w o r k d a t at r a n s m i t t e db yt h eh o s t sw h i c hu s i n gt h eu n i c a s tm e t h o d a l mi s d e p e n d e n tf r o mt h eb o t t o mn e t w o r ki n f r a s t r u c t u r e ，b ye m p l o y st h ee x i s t i n gi pm u l t i c a s tt o p o l o g y t h es y s t e m sf l e x i b i l i t ya n de x t e n d i b i l i t yh a v ei n c r e a s e de f f i c i e n t l y , a n di ta l s ob r i n g s c o n v e n i e n c ef o rt h eu p p e rl a y e r s t h i st h e s i sa n a l y s e st h ei n f l u e n c eo ft h ed e g r e eo fam u l t i c a s tt r e ea n dc o n s i d e r st h er o b u s t o ft h em a t h e m a t i cm o d e l ，t h e nt h ea u t h o rp r o p o s e sap r i o r i t y - b a s e db a l a n c e dt r e eb u i l d i n g a l g o r i t h m ( p b t a ) f o ra l m r e s u l t st h et h e s i sh a sg o ta sf o l l o w s ： 1 t h ed y n a m i cp r i o r i t yi si n t r o d u c e dt ot h i sa l g o r i t h mt oi m p r o v et h es t a b i l i t ya n d t r a n s m i s s i o ne f f i c i e n c y t h em o d e lc a l c u l a t e st h eh o s t sr e s o u r c e ，r e m o v ef r e q u e n c ya n d r e m o v ep r o b a b i l i t yt ob u i l dad y n a m i cp r i o r i t y ，t h e n ，b u i l d st h em u l t i c a s tt r e ea c c o r d i n g t ot h ec o m p u t i n gr e s u l t s 2 t h es y s t e mh a sb a c k u pf u n c t i o nt oa l li t sh o s t s w h e nt h e r ei sa na c c i d e n t a li n v a l i d a t i o n t oah o s t ，w h i c hh a sn e g a t i v ei n f l u e n c et ot h es t r u c t u r eo ft h em u l t i c a s tt r e e ，t h es y s t e m a d o p t st h eb a c k u pi n f o r m a t i o nt or e b u i l dt h es t r u c t u r e 3 t h et h e s i sb r i n g st h ec o n c e p t i o no f b a l a n c e t op r e v e n tt h ed i s h a r m o n yo ft h em u l t i c a s t t r e e ，t h i sm e c h a n i s mg u a r a n t e e st h en u m b e ro fe a c hh o s tm a x i m u mo u td e g r e ei sk i n t h i sw a y , t h es y s t e mc a nc o n t r o li t ss u b h o s t ss c a l e ，t om a k es u r el e s st r a f f i cj a md u r i n g t h et r a n s m i s s i o nb e c a u s eo fs o m eh o s t sw h i c hh a v ep o o rp e r f o r m a n c e t h i sc a n e f f i c i e n t l yi m p r o v et h et r a n s m i s s i o nc a p a c i t y s i m u l a t i o n sh a v eb e e nt a k e nt ov a l i d a t e t h em a t h e m a t i c a lm o d e l t h et h r o u g h p u ta n d s t a b i l i t yo ft h em u l t i c a s tt r e eh a v eb e e na n a l y z e da n dc o m p a r e st oo t h e ra l mm o d e l ，s i m u l a t i o n s p r o v e st h i sa l g o r i t h mp r o m i n e n t l yo p t i m i z i n gt h er e s o u r c eu s a g ea n dt h es y s t e ms t a b i l i t y ， t o g e t h e rw i t hb u i l d i n gt h em u l t i c a s tt r e ee f f i c i e n t l y k e y w o r d sa p p l i c a t i o n - l a y e rm u l t i c a s t ；b a l a n c et r e e ；p r i o r i t y ；r o b u s t i i 南京邮电大学硕士研究生学位论文目录 第一章绪论 目录 l 1 1 研究背景与目的1 1 2 本文的主要工作4 1 3 论文的组织结构4 第二章几种常用组播树算法之间的比较。6 2 1 应用层组播的研究现状6 2 1 1 树优先方式6 2 1 2 网优先方式7 2 1 3 层次结构方式9 2 2 三种常用的组播算法简介1 0 2 2 1 随机组播算法1 0 2 2 2 最短路径树算法11 2 2 3 最人带宽算法1 2 2 2 4 三种算法的比较1 2 2 3 应用层组播主要性能评价参数15 2 4 本章小结。1 7 第三章a l m 组播树健壮性分析1 8 3 1 组播树出度的选取18 3 2 健壮性分析2 1 3 3h m t p 协议2 4 3 4 本章小结2 7 第四章p b t a 模型的设计2 8 4 1 问题的提出2 8 4 2p b t a 模型2 8 4 3 模型的拓扑结构3 l i i i ，i 5 2 仿真场景设置及结果分析 5 3 本章小结 第六章总结与展望 致谢 参考文献。 已发表及已录用文章。 i v 南京邮电大学硕士研究生学位论文 第一章 第一章绪论 i n t e i n a 的迅速发展带给了现代人一个全新的世界一网络世界，极大的提高了 的传播速度，丰富了人们的生活，弥补了人们的一部分精神空缺。在人们对网络越 依赖的情况下，人们对网络的要求也越来越高：希望网络内容越来越丰富，速度越 快，视频等越来越清晰等。这就对数据传播的速度和质量要求越来越高，应用层组 着人们的这些要求和渴望越来越受到关注。 1 1 研究背景与目的 随着网络应用的不断增加，越来越多的网络需求同益增长，组播技术在同新月异的 变化着。人们开始喜欢在网上看电视，喜欢共享资源，更加重视视听上的享受。这也为 快速增加的网络硬件环境带来了一定的压力。虽然现在网络带宽能迅速增长，但是还是 不如用户的需求增长得迅速。这需要提高带宽和资源的利用率，减轻网络环境的压力， 稳定良好的网络环境。首先来了解一下通信的几种方式，如图1 1 所示。 通信分为以下几种通信方式：单播( u n i c a s t ) 、任播( a n y c a s t ) 、广播( b r o a d c a s t ) 、组播 ( m u l t i e a s t ) 。 图1 1 几种通信方式 单播( u n i c a s t ) ：在每一对发送者和接收者之间实现点对点网络连接。当一台主机服 塑室坚皇奎堂堡主塑壅生兰垡笙茎蔓二皇堕堡 务器同时只给少量的接收者提供服务，则客户端的q o s 能得到有效的保证。但若有大量 主机希望获得数据包的同一份拷贝却很难实现，这样将导致发送者负担沉重、延迟大、 网络拥塞，并使主机网络有负载过重甚至瘫痪的危险。与此同时，对于服务器、客户端 之间的分发网络，则会引发网络延迟增大、拥塞等诸多问题，为保证一定的服务质量则 必需增加硬件和带宽。 任播( a n y c a s t ) ：网络地址与网络节点之间存在着一对多的关系。每一个节点对应一群 接收节点，但是在任何给定时间，只有其中一个节点可以接收到传送端来的消息。 广播( b r o a d c a s t ) ：是指在i p 子网内广播数据包，所有在子网内的主机都会收到这些 数据包。广播意味着网络向子网内所有主机都投递一份数据包，不论这些主机是否愿意 接收该数据包。但广播的使用范围非常小，只在本地子网内有效，因为路由器会封锁广 播通信。通过发送广播数据包实现多点传送的办法虽最简单，但是这将强制子网内所有 计算机接收该数据包，终端主机只有是否处理的权力，而没有决定是否接收的权力。采 用这种方式发送数据包不仅占用了不需要此数据包的主机处理时间，而且也造成了局域 网带宽的浪费，易诱发网络拥塞。 组播( m u l t i c a s t ) 其特点是能够在网络上提供单点到多点( o n e t o 。m a n y ) 通信以及多 点到多点( m a n y - t o m a n y ) 通信。相对单播、广播来说，组播能更有效地利用网络带宽、 降低网络流量、提高数据传输效率，提高数据传送效率，减少主干网络出现拥塞的可能 性。组播组中的主机可以是在同一个物理网络，也可以来自不同的物理网络。目前的组 播技术主要分为两种：一种是在网络层实现的，即传统的i p 组播；另一种是在应用层实 现的，即应用层组播a l m 。 在现有的网络环境中，组播的应用越来越广泛，例如，视频点播( v i d e o o n d e m a n d ) 、视频会议( v i d e oc o n f e r e n c e ) 、网络直播( l i v es t r e a m i n g ) 、媒体文件分发 ( m e d i af i l ed i s t r i b u t i o n ) ，网络新闻传输协议( 1 m t p ) ，这些应用的特点是服务质量要求 比较高，接受用户多，数据量大，占用带宽比较高。 现在互联网上的组播技术主要有：i p 组播、互联网中继交谈、p s y c 、网络会议、 w w c p 、a l m 等等。 组播作为一点对多点的通信，是众多节省网络带宽的有效方法之一，已经成为引人 瞩目的技术。组播又按照其实现的层次可以分为i p 组播【1 1 和应用层组播【2 1 。 2 南京邮电大学硕士研究生学位论文 第一章绪论 ( a ) i p 组播 ( b ) 应用层组播 口路由器o 终端 图1 2 两种组播传输方式 首先来了解下a l m 与i p 组播的主要区别： 报文转发位置：a l m 数据转发节点为覆盖式网络中的终端主机，但i p 组播的报 文转发须由核心路由器来处理。 网络拓扑的创建：a l m 的是由节点问直连而成的一个虚拟图( 有向或无向图) ， 隐藏了底层的物理网络拓扑。这种覆盖式网络拓扑是可控的，还可利用一些额外 的知识或特定的度量对网络拓扑进行优化。而在i p 组播中，路由器是已经部署 完成的，故网络拓扑难以控制改变。 组成员关系维护：口组播的组成员关系信息分布于组播路由器，而a l m 的成员 关系由系统中的汇聚点集中控制或完全分散于各个节点。 i p 组播核心思想是在路由器上进行数据复制，然后转发给加入组播组的成员。i p 组 播一直以来没有广泛应用，主要是因为其扩展性差，网络管理复杂，实施起来比较负责 以及对高层的应用支持比较差等。 应用层组播技术( a l m ) 是伴随着互联网的发展和多媒体应用的迅速普及而诞生的一 种在终端实现的组播技术。a l m 区别于i p 组播的一点是：a l m 是在端系统实现组播数据 的复制转发。 a l m 的相关技术引起了人们的广泛关注。已经有很多应用层组播模型被提出来，并 且有很好的实用价值。常用的在线观看的视频几乎都是应用的a l m 相关技术。a l m 的应 用如此广泛主要基于a l m 技术的突出的使用性的优点。下面介绍应用层组播的主要优 点： ( 1 ) 易实现：应用层组播能够很快就进入应用，不需要改变现有网络路由器。因此终 端系统的资源可以更加合理的利用起来，提高了系统吞吐率，优化了系统时延。 ( 2 ) 易控制：应用层组播是通过终端系统之间的单播来实现的，而单播在接入控制技 术方面比较成熟，所以差错控制、流控制、拥塞控制等更容易实现。 3 南京邮电大学硕士研究生学位论文第一章绪论 ( 3 ) 易地址分配。 ( 4 ) 易部署：a l m 的应用只需要端系统成员也就是用户终端做一些升级，可以随时部 署，没有了p 组播需要网络设备同意升级和功能扩展的弊端。 应用层组播的缺点： ( 1 ) 低可靠性：终端系统的可靠性比路由器差。 ( 2 ) 可扩展性差：底层的路由信息对应用层组播来说是隐藏起来的，可扩展性不好。 ( 3 ) 传输效率差：应用层组播在数据传输过程中会产生数据冗余，因此应用层组播的 传输效率比i p 组播要差一些。 1 2 本文的主要工作 通过对多种a l m 组播树拓扑结构的研究，本文论述了一种基于优先级的应用层平衡 组播树算法( p r i o r i t y - b a s e db a l a n c e dt r e eb u i l d i n ga l g o r i t h mf o ra l m ) 。为提高组播树的 健壮性，p b t a 使用优先级作为衡量节点优劣的标准，使用优秀节点作为高一层的根节点， 从而构建一个更稳定的平衡组播树算法。 本文的创新点： 将节点的综合素质用优先级体现，并将优先级引入平衡组播树，构建由出度为k 的平 衡组播树，使得网络快速收敛，提高网络的健壮性；再者采用一种同时在根节点和r p 节 点存储节点信息表的方式，防止r p 节点突然失效，提高组播树的稳定性。 1 3 论文的组织结构 论文共分六章。首先，阐述了组播技术a l m 产生的背景和优点，然后，介绍a l m 技 术目前存在的问题，同时提出自己的解决方案，最后，对提出的方案给以论证。具体的 内容做如下安排： 第一章本章节为绪论，简单介绍了组播技术在网络上的应用背景以及i p 组播的问题 和a l m 技术的优势，指出了研究现状，接着阐述了本文要研究和解决的问题以及本论文 的创新点，最后简要介绍论文的组织结构。 第二章首先介绍了几种常用的组播树组织方式，然后介绍了目前通用的应用层组播 树的构建算法主要可以分为随机组播算法、最短路径树算法【i 】、最大带宽算法的等几种； 并比较这几种算法各自的优缺点。最后列举了应用层组播优劣的主要评价参数。 第三章首先介绍a l m 树中出度与组播树性能之间的关系，然后对健壮性分析，组播 4 南京邮电大学硕士研究生学位论文 第一苹绪论 树的健壮性与组播树拓扑结构之间的关系，最后分析组播树健壮性与树的高度，节点的 出度，还有节点的稳定性之间的关系。并介绍h m t p 1 1 算法。 第四章在第三章健壮性分析的结论上论述一种新的a l m 树形结构算法p b t a ，并详 细介绍该模型的主要思想、系统设计、拓扑维护以及传输算法等，最后重点讲述了动态 优先级的建立。 第五章本章节对第四章论述的p b t a 模型进行实验仿真。首先介绍模型参数的含义， 并详细描述通过仿真平台建立模型的过程，最后分析结果并得出结论。 第六章本章节主要总结本文论述的新模型的特点，然后对整篇论文进行总结，提出 还有待解决的问题，并对未来工作进行展望。 5 南京邮电大学硕士研究生学位论文第二章几种常用组播树算法之间的比较 第二章几种常用组播树算法之间的比较 2 1 应用层组播的研究现状 取代i p 组播而在应用层实现的组播技术，能够满足组群用户服务要求，由此产生了 很多优秀的模型，如：h m t p 4 1 ，n i c e 5 1 ，c h o r d 6 1 ，v r i n g 7 ，y o i d 8 1 ，n a r a d a 9 1 ，c a n 1 0 l ， t a g 【1 ，b a y e u x 12 1 ，s c r i b e 1 3 1 ，a l m i 1 4 1 ，s c a t t e r c a s t 【15 1 ，o v e r c a s t 19 1 ，o m n i 2 0 1 ，t m e s h 2 1 1 ， z i g z a g 2 2 1 ，m s t p 2 3 】，m e s h t r e e 2 4 1 ，a n y s e e 2 5 1 ，s w i t c h - t r e e 2 q 等。这些模型拓扑的组织方式主 要分为：树优先方式、网优先方式、层优先方式三种。下面分别阐述这三种方式建立拓扑 结构的过程。 2 1 1 树优先方式 根据节点构建拓扑结构的方式，依照控制协议的分类，可以将树的构建方式分为以 下两种： 1 分布式构建 如t a g 1 1 l 协议，r p 节点仅仅负责保存组成员的全局信息。新成员在节点加入时首先 在r p 节点处注册，然后得到部分或全部成员节点信息，从而启动节点加入过程。每个新 节点自己需要寻找到最优的父节点，即相对来说加入后节点的链路情况应该是最优的。 采用这种新节点加入方式，对于全局节点的控制相对比较简单，构建为组播树的速度也 较快。 2 集中式构建 如a l m i 1 4 1 协议。r p 节点负责保存全组成员的全局信息和启动a n 过程，并负责全 局控制。r p 节点通过与其他节点定期进行交互，获取节点信息及其链路状态信息，从而 计算组播树的各项参数，完成对组播树的构建，控制和维护。用这样的方式构建的r p 树，是一棵全局较优的组播树。但是，如果r p 节点的性能不是足够强大，那么r p 节点可 能会成为整棵组播树进行构建，维护和数据传输等功能的瓶颈。树优先方式中新节点加 入过程如图2 1 所示。 树优先方式是首先根据各个节点的局部信息建立一个共享树，然后，各个成员从覆 盖网寻找非邻接节点，并建立到这些节点之间的链路。y o i d 8 】协议和a l m i 1 4 1 协议都采用 6 南京邮电大学硕士研究生学位论文第二章几种常用组插树算法之间的比较 了树优先算法。 采用树优先方式生成组播树的a l m 传输协议相对比较简单，在这样方式的组播生成 树中，节点收到数据后，只需要向其邻居节点转发数据。这样，控制相对比较简单，有 较好的传输效率；但是，节点之间的连通性较差，容易产生分离和环路，当树深较大 时，数据延时也会比较大。 同时，随着节点的增多，这种缺点会加剧组播树的维护开销、拓扑的频繁改变、数据 传输延时的急剧增加，因此其扩展性较差。 b 、 r _ 、 沙髑? + j ( 二) r p 节点 组成员o新主机 一数据连接 - q l - - - 一二：j 控制信息 2 1 2 网优先方式 图2 1 新成员加入组播树过程示意图 网优先方式是在已有的节点之间建立一个a l m 覆盖网，然后根据计算的各个参数值 形成组播树进而传输数据。这种方式通常采用分布式算法建立覆盖网，从而对组播树进 行优化。 网优先的方式一般只适合节点较少的a l m 应用。虽然网优先方式采用分布式算法使 得组播的拓扑结构的构建速度较快，连通性较好，可以使组播树有足够的链路冗余，但 是由于分布式算法有着较大的额外控制开销，当覆盖网内节点数目较多的时候，额外控 制开销就占据了很大一部分资源。这种方式随着节点数目的增加，系统的资源利用率就 会降低。 网优先协议先在已有的节点之间建立了一个a l m 覆盖网，任意两个节点之间需要存 在多条通路，再通过定义的路由算法在覆盖网上建立一个指定源的组播分发树。组播树 的网络拓扑显示生成，它的建立依赖于覆盖网的拓扑结构和路由算法。因而，覆盖网的 质量还有路由算法的效率直接影响这个组播树的性能。采用网优先方式的a l m 协议有 n a r a d a l 9 、8 c a 仕e r c a l s t 【1 5 】等。 7 、o i 扩 一&，o ， 堕皇坚皇查堂堡主堑壅圭兰篁丝奎茎三兰! ! 堂堂旦丝堡塑簦鎏奎塑丝些墼 下面介绍网优先协议的建立过程。 首先所有的组成员节点建立一个a l m 覆盖网。然后各个节点计算组播树进而传输数 据。每个节点定期和其邻居节点交换信息。如图2 2 ( a ) 所示。图中9 个节点形成了一个网 状拓扑，并建立了一棵组播树。 ( a ) - - 数据流 ( c ) ( b ) ( d ) 新连接 图2 2 网结构变化不葸 如图( b ) 所示，若节点a l 和c l 从网络中离开，则a l 、c l 给r p 节点传送离开信息， 之后r p 节点根据拓扑情况，在节点舢与a 2 之i 日j 建立条链路，保持整个网络的连通 性。 若有新成员b 2 加入，如图( c ) 所示，首先b 2 向i 冲节点注册并声明要加入网络，根 据拓扑等参数计算之后，节点b 2 与节点a 2 ，b o ，c o 之间分别建立连接： b 2 ，b o ) 、 b 2 ， c 2 ) 、 b 2 ，a 2 ) ，保证连接的冗余使得组播树变得更加优化。 如图( d ) 所示，各个节点成员在若干周期后，经过信息的交换，发现节点a 2 和b l 之 间的连接已经不符合较优化的组播树的条件，则两节点直接的连接断开。最后，形成的 覆盖网较优，则在此基础上建构的组播树也是较优的。 南京邮电大学硕士研究生学位论文 第二章几种常用组播树算法之间的比较 2 1 3 层次结构方式 层次结构的方式是在树优先和网优先的基础上的扩展，是一种较为复杂的拓扑结 构，如n i c e 5 1 ，如图2 3 所示，h t g 等协议。层次结构方式引入域代理等概念。 a o 图2 3n i c e 层次结构示意图 采用层次结构的协议需要引入域和代理等概念，有很好的扩展性，可以在不同的域 内选择不同的协议，进行数据控制和传输，域内的成员根据本域内定义的控制协议完成 组播的构建和维护，再根据相应的协议形成组播树，各个域内的代理又可以根据更高层 次的组播协议来构建更高层次的组播树；但是这种协议的复杂程度出现了一些明显的问 题：随着节点层次的增加，整个拓扑结构控制机制变得复杂；层次增加了之后，组播结 构的时延也随之增加。 通过以上的介绍，大致对三种典型的a l m 协议进行了了解。在表2 1 中，列出了三种 协议之间一些参数的比较【1 6 1 。 表2 1 几种典型a l m 协议的比较 协议名称类型 树类型最人路径长度最人子树的度平均控制开销 n a r a d a 网优先指定源无确定上限无确定上限 o ( n ) h m t p ，y o i d 树优先 共享树无确定上限 o ( d )o ( d ) n i c e 层次 指定源 o ( 1 0 9 n )o ( 1 0 9 n ) 常量 注：1 表中n 为组成员数量 2 d 为最人节点度数 3 1 0 9 均是以2 为底 可以看出，网优先协议在节点数量增加的时候，路径长度比较不稳定，平均控制开 9 南京邮电大学硕士研究生学位论文第二章几种常用组播树算法之间的比较 销随着节点数目的增加线性增加，因此不适合节点数量较多的环境。树优先现已的最大 子树的度和平均控制开销和最大节点度数d 有关。层次结构的最大路径长度均和组成员数 量有关，在成员数量增加时有较好的可扩展性，平均控制开销也比较稳定。 网优先协议和树优先协议不能有效的控制数据传输的最大长度，所以不太适合用于 对延时敏感的一些应用。层次结构比较适合于大组播组，高带宽的应用。而树优先协议 能够有效的控制最大子树度的优势让它非常适合高带宽需求的数据传输，其平均控制开 销与域内最大节点数有关，所以在规模不是非常大的组播组环境中的应用，有很好的意 义。 2 2 三种常用的组播算法简介 目前，常用的应用层组播树构建算法主要可分为：随机组播算法、最短路径树算法【引、 最大带宽算法等几种。这几种组播树算法各有优劣和适应情况。这一章主要介绍这几 种算法，并对一些关键参数进行比较。 2 2 1 随机组播算法 随机组播树算法在确定根节点和所要生成的组播树度的参数限制的情况下，用完全随 机的方式生成整棵树的拓扑结构。这是一种相对来说比较简单的组播树建立算法。这种 算法有很好的扩展性，但是组播树的稳定性和占用资源不是很好控制。 该算法的优点是易于实现，无须进行前期的链路测量；缺点是无法避免性能差的链路 和服务能力弱的节点，必然影响服务质量。 组播树的根节点确定之后，各个节点依次运行j o i n 算法，生成整棵组播树。生成过程 的伪代码实现如下： 1 0 南京邮电大学硕士研究生学位论文 第二章几种常用组播树算法之间的比较 算法的实现( 此算法用路径长度作为限制参数) ： 2 2 2 最短路径树算法 最短路径算法【3 】是一种广泛使用的组播树，它重点是求出顶点之间长度最小的一条路 径。它能保证传送时延最小。将节点之间的链路延时作为优化组播树的度量，以每个节点 到根节点路径延时最小作为优化目标。一般来说，越相近的节点之间，链路状况越好，因 而，这种方法有助于提高组播树的吞吐量。因此，该方法在交通、工程以及计算机网络路 由选择方面都有着广泛的应用。该方法主要包括弗洛伊德算法和迪杰斯特拉算法，扩展 的算法有低代价最短路径树的快速算法等。 这种算法的优点是链路时延的测量易于实现，对网络资源消耗小；缺点是链路时延只 能反映吞吐量的一个方面，因此其实际性能有待观察。 实现算法如下： 2 2 4 三种算法的比较 以上大致介绍了随机组播树生成算法、最短路径生成树算法和最大带宽组播树算法 三种算法。下面对这三种算法做进一步的比较。一些随机的组播域中的节点，如图2 4 所 不o 1 2 南京邮电大学硕士研究生学位论文第二章几种常用组播树算法之间的比较 图2 4 组播树节点分布图 假设本组播域中共有6 个节点。节点上的数据表示节点的链路路径长度。节点之间的 带宽如果都是相等的，那么得到的三种组播算法的生成树如图2 5 ，2 6 ，2 7 所示。 从图2 5 ，2 6 ，2 7 可以知道，如果各个节点之间带宽相等，最短路径算法生成树和最 大带宽组播算法生成树的拓扑结构是一样的。 图2 5 随机组播树算法生成树图2 6 最短路径树算法生成树 图2 7 最大带宽缉播树算法生成树 设图中各节点测量出来的带宽如表2 2 所示。 若各个节点之间的带宽不一，则用随机组播算法生出的树的拓扑可能是变化的，而 最短路径算法生成树是固定不变的，如图2 6 、图2 9 所示，但最大带宽组播算法生成的树 就会分别如图2 7 、图2 1 0 所示。 可以得到这样的结论，随机组播树算法可能每次生成的组播树的拓扑结构是不同 的，而且根据节点的情况是动态变化的；最短路径生成树只要节点之间的路径长度不 变，那么树的拓扑结构是不会变化的；而最大带宽组播树算法生成的树的拓扑结构取决 于节点之间的路径长度和节点之问路径的带宽两个因素。在路径长度相同的情况下，选 1 3 ) 乒 南京邮电大学硕士研究生学位论文第二章几种常用组播树算法之间的比较 取带宽较高的路径。 表2 2 各节点的带宽 路径( 节点一节点) 带宽( m b p s ) o 1l 0 26 o 35 1 23 1 - 44 2 3 7 2 _ 44 2 53 3 51 4 56 2 2 图2 8 随机组播树算法生成树图2 9 最短路径树算法生成树 图2 1 0 最人带宽组播树算法生成树 图2 8 、2 9 、2 1 0 里，可以得到三种算法分别生成树的路径带宽如表2 3 所示。 1 4 南京邮电大学硕士研究生学位论文 第二章几种常用组播树算法之间的比较 表2 3 三种组播算法生成树的路径带宽 算法 带宽总和( m b p s ) 路径长度 随机组播树算法 1 5 1 9 最短路径树算法 1 81 0 最人带宽组播树算法 2 21 0 从上表可以看出，最大带宽组播树有最短的路径长度和最大的带宽，是对路径长度和 数据传输带宽要求比较高的网络里面比较好的方案。而这两个参数正好是衡量一个组播 网络优劣的重要两点。 通过对这三种应用层组播树构建算法的分析和对比，得出以下结论： ( 1 ) 随机组播树算法：生成组播树前不需要对网络链路进行测量，对网络资源占用 小；生成的组播树无法根据网络链路状况提高吞吐量；也无法根据网络或者节点的状况 及时调整组播树的结构；组播树稳定性较差；主要应用于消息传递。 ( 2 ) 最短路径树算法：组播树构建的前期只需测量部分网络链路时延，对网络资源占 用较小；相对于对于随机算法来说，数据的吞吐量有一定的提高，但差于最大带宽算 法；组播树稳定性较好；主要应用于实时组播通信。 ( 3 ) 最大带宽组播树算法：生成组播树之前需对部分链路进行带宽测量，前期对网络 带宽等资源消耗最大；但是构建好拓扑结构之后，吞吐量是三种方法中最高的；组播树 稳定性较好；主要应用于基于可扩展编码( s c a l a b l ec o d i n g ) 的流媒体。 综上所述，最大带宽组播树算法在流媒体和占用带宽比较高的应用方面有较好的稳 定性、较大的吞吐量和较好的使用价值。在分析了以上结果之后，p b t a 将在第五章与最 大带宽算法进行比较。 2 3 应用层组播主要性能评价参数 应用层组播算法通常是对于某些应用进行优化，由于各种应用对其要求的各种条件 都有不同的要求，所以各种组播协议的优劣没有固定的评价标准，常用的评价标准【1 8 1 包 括： 1 吞吐量( t h r o u g h p u t ) 此参数用来衡量组播树的数据传输能力，定义为单位时间内传输数据的数量。吞吐量 和带宽是很容易弄混的两个概念。通常，比较倾向于用“吞吐量”来表示一个系统的测试性 能。因为受各种低效率因素的影响，带宽为1 0 m b p s 的链路连接的一对节点可能只会达到 堕室坚皇丕堂堡主堕壅生堂垡笙奎笙三童! ! 登堂旦丝堡丝簦鎏查塑箜些墼 2 m b p s 的吞吐量。所以本文采用吞吐量来衡量组播树的性能。 2 吞吐量方差 为了能更好的体现两种组播树吞吐量的大小的区别，本文特别取用各个时间点取到 的吞吐量的值与本段时间内吞吐量的平均值作方差，从而能更形象的体现出差异。 3 1 冲节点信息表更新次数 r p 节点根据实现功能的不同又可以分为两类：一类只负责简单地存储所有节点信 息，各成员节点定期与其交换信息以获得这个组播组的全局信息；另一类除完成上述功 能外，还要实现对全局的控制功能。一段时间内r p 节点信息表更新的次数能够体现整个 组播树拓扑结构变化的频率，从而体现了整个域内组播节点的稳定性，也就是组播树的 稳定性。 4 带宽( b a n d w i d t h ) 指通信链路上实际使用时占用的带宽。应用层组播会比i p 组播消耗更多的带宽。 可扩展性( s c a l a b i l i t y ) ： 这个参数是在大规模组播算法时重点考虑，本文没有使用这个衡量参数。 5 鲁棒性( r o b u s m e s s ) 应用层组播应提供一定的鲁棒性，并适应不同应用的要求。提出建议：使用泛洪机 制，在系统中增加冗余，提供快速错误发现和修复机制。 6 传输载荷强度( l i n ks t r e s s ) 定义为从源节点到组播组中其它节点，同一数据包在数据传输拓扑上的每条连接路 径上的重复发送份数。对整个数据传输拓扑的连接路径可以计算它的平均传输载荷强度 来衡量它的传输负载指标。该指标可以比较粗略地衡量协议的数据传输效率。 7 组播组维护的开销( c o s 0 包括保存状态信息的数量，组播节点之间为维护组播组的交互信息数量，组播节点 加入、退出、失效等信息在组播组内同步的时间开销等。 8 组播节点的度( d e g r e e ) 主机的资源有限，所以需要限制节点的度。 9 伸展度( s t r e t c h ) 其定义为从数据包源节点到组播组中其它某一节点的经过的路径长度除以直接通过 单播服务所需经过的路径长度的比值。 本文仿真部分主要比较的参数有：用来衡量网络效率的控制开销；用来衡量网络负载 能力的链路压力、链路时延、吞吐量和带宽方差，用来衡量网络稳定性的单位时间内的r p 1 6 南京邮电大学硕士研究生学位论文 节点交换次数。 2 4 本章小结 本章主要介绍了应用层组播的研究现状，三种 一些常用的衡量参数。 1 7 南京邮电大学硕士研究生学位论文第三章a im 组播树健壮性分析 第三章a l m 组播树健壮性分析 上一章主要讨论的是常用的三种组播算法，可知最大带宽组播树算法相对来说是应 用中较好的算法，有着比较高的带宽和最短的路径长度。但在规模比较大的域中，节点 的路径和带宽会时常变化，导致已生成的组播树频繁的变更，组播树就变得不稳定。在链 路长度和带宽都较好的情况下，组播树的健壮性就显得尤为重要。 组播树的健壮性问题可分两类：一类是由组播成员的动态变化引起；另一类是组播成 员不变时由其他原因引起，如网络拥塞等。单点失效1 ) i n g l ep o i n tc ff a i l u r e ) 会导致a l m 树结构分割，引起a l m 组播树的重构。稳定的组播树是数据正常传输的重要保障，虽然 研究者们设计了诸多应用层组播协议，但其中却很少有保障组播树稳定性的有效措施。 因此组播树的健壮性问题一直是组播领域的一个重要研究课题。提高组播树的健壮性具 有很大的现实意义。 因此本章主要讨论组播树健壮性的问题。首先讨论组播树的出度对时延及控制开销 的影响；然后讨论组播树的健壮性影响因素；最后介绍h t m p 2 】模型，此模型也是树优先 组播模型，有着其特有的优点。 3 1 组播树出度的选取 节点拥有的子树数称为该节点的度( d e 蓼e e ) 【2 7 1 ，度为0 的节点称为树的叶子( 1 e a f ) ，其 余的节点称为分支节点( b r a n c h ) 。树中节点最大的度为树的度。 根节点的层次为1 ，其余节点的层次等于其双亲节点的层次加1 。树中节点的最大的 层次称为该树的高度。 在二叉平衡树( a v l 树) 的基础上来进行讨论。它是一种特殊的二叉树，能够有效的控 制树的高度，能够避免产生普通二叉搜索树的“退化”树型。 若树树的高度能够能很好的控制，则生成的组播树的平均控制开销，传输路径路径 长度和带宽都可以很好的控制。 二叉平衡树有如下特征： 它的左、右子树高度之差的绝对值不超过l ； 它的左、右子树都是二叉平衡树。 南京邮电大学硕士研究生学位论文第三章a l m 组播树健壮性分析 ( a ) a v l 树( b ) 非a v l 树 图3 1 a v l 树和非a v l 树 对于二叉平衡树乞是一棵高度为h 的具有最少节点数的a v l 树的节点数目；根据平 衡性要求，它的左右子树的高度必然一棵为h 1 ，另一棵为h - l 或者h - 2 ，并且它的左右子 树可以判定为也是相同高度的二叉平衡树中节点数目最少的，所以可以得到： n o = 0 ，n l = 1 ，n = n 一l + 一2 + 1 ( 3 1 ) 而斐波那契级数的定义为： f o = 0 ，f l = l ，f = f 一