（系统工程专业论文）计算机通信网组播路由算法的研究.pdf

国防科学技术大学研究生院学位论文 摘要 近年来出现的多媒体通信与分布式环境下协同工作促使系统设计者们为这些应用提 供相应的通信支持。在这种环境下普遍采用的一种方式是组播通信( 一对多或者多对多) 。 路由是组播通信中的关键问题之一。组播路由优化的目标是在满足时延约束的条件下网 络代价最小化，在一般的情况下，这是一个n p 完全问题。目前存在的启发式算法一般时 间复杂度比较高，而简单容易且利于分布式实现的算法还处于研究之中。到目前为止， 还没有出现好的算法能合理地平衡网络代价与网络时延。在本论文中，一个组播路由综 合优化的概念被提出，这使得网络代价与时延都能在某种程度上获得优化。优化网络代 价将减少通信过程消耗的网络资源，而优化网络时延将减少从源点到目的节点的时间。 具体提出了一个链路选择函数，使用这个选择函数的算法能够在组播通信中实现综合优 化，而以前没有出现过类似的算法。算法中设置有一个可调参数，能够调节网络代价与 网络时延之间的优化程度。此算法已在许多随机网络模型上进行了模拟实验，证明它具 有好的性能。这个算法时间复杂度低，容易分布式实现。 关键词：服务质量，组播路由，链路选择函数，时延 国防科学技术大学研究生院学位论文 a b s t r a c t t h er e c e n te m e r g e n c eo fm u l t i m e d i ac o m m u n i c a t i o na n dc o i l a b o r a t i v ew o r ki nd i s t r i b u t e d e n v i r o n m e n t sp r o v i d e sa ni n c e n t i v et os y s t e md e s i g n e r st oi n c l u d ec o m m u n i c a t i o ns u p p o r tf u r t h e s ea p p l i c a t i o n s ap r e v a l e n tp a t t e r ni ns u c he n v i r o n m e n t si sm u l t i c a s t ( o n e - t o - m a n yo rm a n y t o - m a n y ) c o m m u n i c a t i o n r o u t i n gi so n eo f t h ek e y p r o b l e m s t om u l t i c a s tc o m m u n i c a t i o n t h e o b j e c t i v eo f m u l t i c a s tr o u t i n go p t i m i z a t i o n i st om i n i m i z et h en e t w o r kc o s tw i t h d e l a y c o n s t r a i n e d f i n d i n gam u l t i c a s tr o u t i n gt r e ew i t hm i n i m i z e dn e t w o r kc o s ti sk n o w n t ob ea nn p c o m p l e t e p r o b l e mi n t h em o s tg e n e r a lc a s e me x i s t i n gh e u r i s t i c sh a v eh i g ht i m ec o m p l e x i t y t h e h e n r i s t i c sw i t h s i m p l e ，e a s ya n d d i s t r i b u t e di m p l e m e n t a t i o n sa r eu n d e r r e s e a r c h u p t on o w , t h e r e i sn ob a l a n c e dm e t h o db e t w e e no p t i m i z a t i o no f n e t w o r kc o s ta n dd e l a y y e t i n t h i sp a p e r , a c o n c e p t o f i n t e r g a t eo p t i m i z a t i o no f m u l t i c a s tr o u t i n g i sp u tf o r w a r d ，i nw h i c hb o t hn e t w o r kc o s ta n d d e l a y a r eo p t i m i z e di nac e r t a i nd e g r e e o p t i m i z a t i o no f t h en e t w o r kc o s tc a nr e d u c en e t w o r kr e s o u r c e s c o n s u m e d b yc o m m u n i c a t i o n , w h i l eo p t i m i z a t i o n o f t h e d e l a y c a nr e d u c et h e d e l a y f r o ms o u r c et o r e c e i v e r s a ne d g es e l e c t i o nf u n c t i o ni sa l s op u tf o r w a r d 。w h i c hc 越a c c o m p l i s hi n t e g r a t e d o p t i m i z a t i o no f m u l t i c a s tr o u t i n gt h e r ew a sn e v e ra na l g o r i t h mt h a th a dt h es a m ep e r f o r m a n c e b e f o r e a np a r a m e t e ri ss e ti n 也ea l g o r i t h m , w h i c hc a na d j u s to p t i m i z a t i o nl e v e lb e t w e e n o p t i m i z a t i o no f n e t w o r kc o s ta n do p t i m i z a t i o no fn e t w o r kd e l a y t h ea l g o r i t h mi ss i m u l a t e di n m a n y r a n d o mn e t w o r km o d e l s ，a n di sp r o v e dt h a ti th a sb e t t e rp e r f o r m a n c et h a ne x i s t i n gh e n r i s t i c s ， t h i sa l g o r i t h mh a sl o wt i m ec o m p l e x i t y ，a n dc a na l s ob ei m p l e m e n t e de a s i l ya n di nd i s t r i b u t e d f a s h i o n k e y w o r d sq o $ ，i t l u i t i c a s tr o u t i n g e d g e s o i e c t i o nf u n c t i o n d e l a y 独创性声明 x s 1 9 譬3 ， 本人声晦新量交的学位论文薏我本人在寻萍稽导下避彳亍的研究工律及瑕褥 的研究成暴尽我所知，酴了文申特掰加滋标注和袭浠静蟪方辩，论文牵不包舍 其他入已缀发表和撰写迁蹲骈究赢来，巍不包含秀获褥落掰稃擎技寒大学或箕宅 教育机构的学位或证书而使糟过的褚粹与我一两翼作翡潜恚霜本研究所彀酶任 何贡献均器在论文中作了髓确薛j 毛磺并表示谢意 学位论文题茸：篮差狃显篮塑堑疆整巍差溘煎盈衰 学位论文作者签名：氆；鸯甜期：氓年酸舟f 文器 学位论文版权使用授权书 本人完全了解国防科学技束大学有荧保留、使用学位论文昀规定本人授权 国防科学技术大学可以保留并自匿家有关部门或帆构送突论文的复印停和电子 文挡，允许论文搜查阏和借阏；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制簪段保存、汇编学位论文 ( 保密学位论文雀解密后遣用本授权书) 学位论文题目：盐差扭通篮匿缦擅整啦篓遗数瑟殛 ， 学位论文律者签名：毯烫日期：年，文月，文日 作者指导教师签名：避 日期：少d l 。年脬月p 日 一一 国防科学技术大学研究生院学位论文 第一章绪论 本章首先阐述组播路由的基本概念与分类及难点所在，同时对组播的应用进行简单 的介绍，然后对目前的研究现状及困境进行说明，接着给出本文所做的工作，最后是论 文的组织结构。 1 1 组播路由简介 1 1 1 什么是组播路由 随着i n t e r n e t 与多媒体技术的快速发展，视频点播、远程教育等应用也蓬勃出现， 这使得q o s 组播技术迅速发展并获得了广泛的关注 1 。q o s 组播是一种允许一个或多个 发送者( 组播源) 发送单一的数据包到多个接收者( 一次的，同时的) 的网络技术，但它 同时要保证应用的性能要求。组播源把数据包发送到特定组播组，而只有属于该组播组 的地址才能接收到数据包。组播可以大大的节省网络带宽，因为无论有多少个目标地址， 在整个网络的任何一条链路上只传送单一的数据包。图1 1 1 至图1 1 3 为基于三种可 能通讯方式的数据传递过程。从所示图的工作方式可以看出： 广播( b r o a d c a s t ) 传输：是指在子网内广播数据包，所有在子网内部的主机都将收 到这些数据包。广播意味着网络向子网主机都投递一份数据包，不论这些主机是否乐于 接收该数据包。然而广播的使用范围非常小，只在本地子网内有效，因为路由器会封锁 广播通信。广播传输增加非接收者的开销。 单播( u n i c a s t ) 传输：在发送者和每一接收者之间需要单独的数据信道。如果一台 主机同时给很少量的接收者传输数据，一般没有什么问题。但如果有大量主机希望获得 数据包的同一份拷贝时却很难实现。这将导致发送者负担沉重、延迟长、网络拥塞；为 保证一定的服务质量需增加硬件和带宽。 组播( m u l t i c a s t ) 传输：它提高了数据传送效率。减少了主干网出现拥塞的可能性。 组播组中的主机可以是在同一个物理网络，也可以来自不同的物理网络( 如果有组播路 由器的支持) 。 1 1 2 组播路由的难点 作为组播通信的重要组成部分，组播路由问题始终得到人们最广泛的关注，但与单 播路由不同的是，组播路由的目标是寻找一系列从源节点出发并最终到达所有目标节点 的路径，通常，它采用两种结构，环型结构和树型结构，但是由于后者可以提高大约2 5 的资源利用率【1 】，因此，当前的组播路由就是在网络中建立一棵组播树。这相当于图论中 的s t e i n e r 树问题，所谓s t e i n e r 树是指连接网络中部分节点的一棵树。 近年来，由于多媒体数据，信息的介入，受限s t e i n e r 树问题已经成为组播路由问 题研究的焦点口。 ，传统的最短路径路由算法面临着巨大的挑战，多媒体信息的实时传输 以其数据量巨大和具有严格的时延限制以便用户可以比较平滑地接收视频、音频数据为 其主要特点，所以对于这些多媒体应用来说仅仅生成到达所有目标节点的路径是远远不 够的，还要保证所有的路径都必须满足相关应用的时延限制，有时还必须满足其它的服 务质量请求q o s 。例如在远程会议中，只有所有用户的时延间隔在一定范围内，才会保持 基本的同步，否则，将会丧失那和“面对面”的效果【2 1 】，s t e i n e r 树问题作为个n p 完 全问题，一直是路由问题中研究的难点，而当前需要考虑q o s 请求的s t e i n e r 树问题更 加因其算法计算量巨大而难以处理。 第l 页 圈i 1 i 广播方式 圈1 1 2 单播方式 第2 页 国防科学技术大学研究生院学位论文 图i 1 3 组播方式 1 1 3 组播路由算法的分类 从不同的角度，组播路由算法可以有多种分类的方法。 集中式与分布式：集中式算法要求计算节点知道所有的网络状态信息，而分布式 算法则只要求计算节点知道部分信息，可以看出，在广域网上布署一个集中式算法是有 困难的，因此，寻求分布式的求解算法是非常重要的。 静态型与动态型：所谓的静态型是指在多播树生成以后就不再发生变化了，显然 这对于大部分应用来说是不适合的，而动态型则与此相反，在会话阶段，它允许节点动 态地加入或者离开，这符合实际的需求，但同时也给算法带来了新的问题。 源基树与共享树型：解决组播路由问题的算法大致可分两类；一类算法称为源基 树算法，该算法为组中每一个发送者建立一棵以发送者所在子网为根的组搔树，源基树 算法只适用于广播业务，另一类算法则为组内所有发送者与接收者建立一棵共享树，这 类算法适用于会议型业务( 如计算机会议) ，会议型业务具有以下特征：( 1 ) 既有1 - t o - n 型传输，也有m - t o n 型传输；( 2 ) 对信息传送的时延有严格要求；( 3 ) 数据量大，且 媒体多样要求不同的处理；( 4 ) 在改变发言者时要求进行快速的路由切换。 理想的目标是设计出分布式的、动态的、共享型的时间复杂度低的、受时延约束的、 代价尽可能小的组播树，这当然具有相当大的难度，而且到目前为止也还没有出现如此 完善的算法。 1 1 4 组播协议简介 目前已经提出多种组播路由协议，可以简略地分为源基型，包括d v m i 妒、m o s p f 、p i m d m 等：和核基型，包括p i m - s g 、o b t 等，这些协议大多依赖于当前的最短路径算法。其中d v m r p 是组播实验网m b o n e 中所采用的协议，它与单播路由协议r i p 相类似，也是依赖于距离 第3 页 国防科学技术大学研究生院学位论文 矢量的交换，而组播树的建立则使用反向路径转发算法r p f 。m o s p f 协议是对o s p f 协议 的扩充，它利用所得到的链路状态信息建立一棵以发送源为根的组播树。p i m d m 协议类 似于d 、r m r p 协议，但是它需要一个单播路由协议以提供单播路由信息。而p i m s m 及c b t 建立的则是共享树，它们都存在一个类似核心点的概念，组播信息是通过核心点所转发 的。 1 1 5 组播应用简介 有大量的应用在本质上需要组播通信及协作，例如视频会议、远程教育、分布式数 据库、多人连机游戏及分布式仿真、网络广播服务等等。这些多样的应用需要底层的系 统提供各种支持，这些支持包括带宽需求、时延要求、可靠性保证、多发送源的要求、 可扩展性的需求、动态请求。表1 1 1 是一个简单的总结。 多源扩展性动态带宽要求时延要求可靠性 视频会议 a 1 1s m a l ll o wm e d i u mc r i t i c a ln o 远程教育 o n eo r f e wm e d i u m1 0 wm e d i u m c r i t i c a ln 0 分布式缓 f e wo ra 1 1m e d i u ml o wh i g hn o n - c r i c i t a l y e s 存更新 多人游戏 a 1 1 l a r g eh i g h l o wc r i t i c a l y e s 分布式仿 a 1 1l a r g e l o w h i g hd e p e n d sy e s 真 p 2 pf e w h u g eh i g h l o wn o n - c r i t i c a l y e s 网络电视 0 n e h u g eh i g hh i g h c r i t i c a ln o 1 2 研究现状及困境 1 2 1 研究现状 自从1 9 8 8 年s t e v ed e e r i n g 在他的博士论文“在一种数据报网络里的组播”中正式 提出了网络层组播的概念后，组播技术获得了飞速的发展，众多的研究学者提出了各种 相关算法，林林总总，难以一言以概之，主要的一些如下。 1 9 9 3 年，k u m p e l l a 等晦1 首次提出了带时延约束的组播路由求解问题并给出了相应的 算法，同时将其推广到分布式环境，但是此算法的时间复杂度高，而且在分布式的环境 下易于阻塞。1 9 9 5 年，s u n 等提出c d k s 算法【l ”，此算法通过一个合并过程来保证时延的 要求，它的综合性能较好，但是由于存在合并的过程，使其难于在分布式的环境下部署。 1 9 9 7 年，r o u s k a s 等嘲首次提出了带时延及时延抖动约束的算法，但此算法并没有考虑对 代价的优化，同时复杂度也相当高。1 9 9 8 年p a r s a 等提出b s m a 算法“，此算法是目前所 提出的算法中性能最好的一个，当然可以预料到，此算法的复杂度也是相当高的，同时 算法本身也很复杂。2 0 0 0 年，l e e 等【6 1 提出一种目的节点驱动的组播路由算法，但在此算 法中考虑的是平均时延，并不能保证实时环境下对时延的要求。 目前所提出的组播路由算法由于以上的种种原因并不适合在现实的环境中部署，事 实上目前所提出的一些组播协议d v r p 、m o s p f 、p i m 等中使用的仍是基于求解最短路径 的算法。 第4 页 国防科学技术大学研究生院学位论文 7 2 2 目前的困境 虽然目前基于s t e i n c r 树的组播路由算法的研究已经进行了相当一段时间，但仍然离 现实的应用有一段距离，从实际情况来看，目前的组播协议仍然是基于最短路径算法的。 目前组播路由算法的困境主要体现在： 首先是算法复杂，一些算法时间的阶数为三次方以上如b s m a 算法，有的算法甚至 还是指数时间的如k p p 算法，复杂性的另外一个方面是算法本身结构的复杂，算法过于 复杂将导致实现上的困难，特别是在分布式的条件下。 另一个方面是由于时延约束的存在，目前的一些算法仍然脱离不了最短路径算法， 有的算法在时延无法满足时就用最短路径来代替；而有的算法则是在最短路径树的基础 上进行改造，以减小代价。 三是一些不依赖于最短路径的算法由于求解路由过程的阻塞发生，将导致回溯或试 探等过程的出现，这又是我们所不希望看到的，因为回溯过程不但导致运行时间变长， 而且会带来无法预见性，这在分布式的情况下是无法容忍的。 1 3 本文所做的工作 从以上的分析中可以看出，目前的组播路由算法并不适合于投入现实的运行，因此 本文将针对这一现状提出新的、现实可行的组播路由算法及其分布式实现。针对目前组 播路由算法的一些不足之处，本文主要进行了以下方面的工作： 首先对基于链路选择函数的组播路由算法进行了比较详细的讨论，总结出目前所提 出的一些链路选择函数并对之合理的分类，讨论了此类算法的优缺点及链路选择函数的 选取的一些准则。 二是针对目前的组播路由算法的不足提出了一种简单有效的，能很好的平衡代价与 时延的链路选择函数及使用此函数的集中式算法，此函数不但能够调节代价与时延，并 且在时延约束苛刻的条件下可以以简单的方式达到最短时延，同时保持较小的代价。 三是进一步以此为基础提出了一个分布式算法，此算法可以最大限度的减小运行时 的路由阻塞，同时它也具有简单、易于实现与部署的特点。 四是编制了网络实验集成环境，并在其上进行仿真实验，将此函数与目前存在的 些算法进行了比较，证实此函数确实具有以上的优点。 1 4 论文结构 本文的以下部分是这样安排的： 第二章首先提出本文中使用的网络模型，然后对一些目前提出的带时延约束以 及不带时延约束的组播路由算法进行了分析与介绍，并指出它们的优缺点。 第三章中对基于链路选择函数的组播路由算法迸行了比较集中的讨论，同时总 结出目前的链路选择函数的分类表，最后重点分析了一个属于此类的k p p 算法。 第四章中在总结前人工作的基础上提出了本文的链路选择函数及使用此函数的 集中式算法，并对此链路选择函数进行了分析与评价，指出此链路选择函数可 以达到最短时延，同时具有较小的代价。 第五章则将此链路选择函数运用于分布式的环境，解决目前的算法在时延约束 条件下路由阻塞的困境，并给出了相应的分布式算法。 第5 页 国防科学技术大学研究生院学位论文 第六章为实验分析部分，这一章在本文开发的网络实验集成环境下进行了实验 评测，将本文的算法与目前所提出的一些性能较优的算法进行比较，以获得相 关的实验数据。 第七章对本文所作的工作进行总结，指出研究中存在的不足和今后的工作方向。 国防科学技术大学研究生院学位论文 第二章计算机通信网的组播路由算法 时延受限组播树的求解是一个n p 问题，因此对于规模大一点的网络只能用近似算法 来求近优解，目前主要有两大类，一类是启发式算法，本论文将主要讨论这类算法，另 一类是诸如遗传算法，神经网络，蚂蚁算法等之类的算法。但对于规模较小的网络，求 最优解还是可行的，因此本章也给出了一个求最优解的方法，当然，它是指数时间的。 2 1 网络模型 首先我们必须明确如下两个概念： ( 1 ) 网络总代价：在多播路由计算过程中，由于多播机制自身的特点，其业务流只 在分叉节点处进行复制，而在公用路径上能做到资源共享，因此网络的总代价应为所构 造的生成树的所有边的代价之总和，而非源点到所有目的点的代价的总和。 ( 2 ) 网络时延：在多播生成树中，网络时延指的是从源点到各目的点时延中的最大 值。此外也必须考虑到这样一个现象，在很多实时应用过程中，往往存在一个时间限制， 并不需要我们到每个目的地的路径最短时延，但必须保证从源点到任一端点的时延都不 超过一个界限。 从而，此问题即变为给定一个多播源点和一系列目的点，要求在满足任一源点到目 的点时延均不超过一时延上限t 的条件下，求出一棵总代价最小的s t e i n e r 树，本文中将 其记为c s t ，代表受限s t e i n e r 树之意。其可模型化为一图论问题，网络相当于一简单无 向连通图僻 ；v 为图中点的集合，代表多播通信的所有端点，并指定其中的某点 s 为源点，e 为图中所有边的集合，代表实际通信过程中的所有链路。对于g 中的每一条 边o ，j ) e ，均对应两个正实数加权值c o s t ( i ，j ) 或简记为c g ，) 、如纫，( f ，_ ，) 或简记为 d ( f ，) 。c o s t ( t ，) 定义了边( f ，) 的代价，其值与该边的资源使用情况有关。沈匆( f ，_ ，) 定 义了边o ，) 的信息传送延时，该延时包括排队延时、传输延时和交换延时等。组播路由 问题可描述为在图g 中寻找一棵包含发送源及所有接收节点的c s t 树 ，= ( 巧，e t ) ，仃g ) 。 并满足网络总代价最小化：m i n ( c o s t ( ) ) 及网络时延约束条件： 如矗矽o ，) 的疆小生成树，毽该算法丝毫没有考虑时延静因素，每次逸铎的最，j 、代价边 并不一定满足时延t 的要求。 2 。2 。3s p h 算法 最短路径启发式算法( s p h ) 【t 轴“产生栩当好的结巢并且有许多变体，s p h 初始化组 援树为某一组搔成员( 一般为滚点) ，然后最近的缀捶成员被加入到组攘越上，加入路径 是该点到缎播树的最短路径，当所有成员均加入副树上艏，算法终艟 产生的鳃还可以遴一步改进，对予解中的节点求出一个圈，黪出圈的最小生成樾， 再剪去最小生成树的非组播叶节点，就可以得到一个改进的解，这个改进方式也_ 对以同 撵运惩予s p h 算法夔变傣孛。 基本s p h 算法描述如下： l 、耪始纯予挺彳兔组撩涿患； 2 、连接子树t 及与其相距最近的还未造上的某一组播节点； 3 、魏栗干审还不含有掰有缀播节赢，转羁第2 步。 4 、进一步改进 ( 1 ) 设圈g 为斑t 中节点辱出的g 之子圈，令u 为g7 的最夺生成树； ( 2 ) 修剪去u 中非组播叶节点。 s p h 算法的运行时间为0 ( z 抒) ，z 为组精节点数。 2 2 4k m b 算法 l 【姆算法“3 1 求解一个邋优s t e i n e r 奉睡，由三步组成：构逡一个闲包圈，在闭包圈上求 一棵最小生成树，再扩展生成树而成为近优s t e i n e r 树。k m b 算法是下文将要提到的k p p 舞法熬基旗。 闭包嘲是一个关于组播点的完全圈，而闭包阔中边的代价即为原图中相应节点问的 最遂路径瓣我徐，然嚣最小生威辩算法鼓疲翔到翅包强上，再将疑小生成撼上的选用骚 繁# 页 国防科学技术大学研究生院学位论文 图中相应的最短路径代替，即求得近优s t e i n e r 树，偶尔会有扩展的结果不是树，而是 带有环路的图，这些环路能够被再一次运用最小生成树算法而消除，一个k m b 算法的实 例见图2 2 1 。 在这例子中，图( a ) 中的s t e i n e r 树必须跨越点a ，b 与d ，闭包图表示于( b ) 中， 边的代价为相应节点在原图中的最短路径代价，因此，边肋有代价5 ，因为b 与d 间的 最短路径为5 ( 沿着b c ，c d ) 最后，闭包图上的最小生成树被构造出来，在本例中可以 是闭包图中的任意两条边，在此，我们选择边a d 与a b ，扩展后的近优s t e i n e r 树见图( c ) ， 最优s t e i n e r 树显示于图( d ) 有代价为9 。 e e a 【a ， a 8 b e b ( b a 图2 2 1k m b 算法实例 8 国防科学技术大学研究生院学位论文 2 3 带时延约束的组播路由算法 带时延约束的组播路由算法往往更能够满足现实的要求，特别是对于一些具有实时 要求的应用来说。但是任何事情都是有代价的，此类算法往往更复杂，而且计算复杂性 也比较高。到目前为止，已经提出一些此类算法，在此论文中选择了几个最具有代表性 及特点的算法论述如下。 2 3 1b s m a 算法 b s m a 算法“钔首先在给定的源点与目的节点之间计算一棵最短时延树，然后它在不破 坏时延约束的条件下，迭代地用不在树上的低代价超级边去替换已经在树上的超级边( 超 级边是树上两个分支点之间的一条路径，它或是位于两个组播点之间，或是位于一个分 支点与一个组播点之间) ，直到树的总代价不能进一步削减为止，b s m a 使用k 阶最短路径 算法去发现低代价超级边，它的复杂度为o ( k n 3 l o g n ) ，在大的稠密的网络中k 值也许非常 大，它很难达到可以接受的运行时间，b s i a 总是发现棵c s t 树，如果它存在的话，因 为它开始于一棵最短时延路径树( l d 树) ，在运行b s 凇算法时，可以折衷树的代价来获 得快的运行速度，这或者通过减少阶数k ，或者通过限制超级边替换的数量来达到。 虽然b s m a 算法的时间复杂度比较高，可是它却能获得最好结果的近优解“。 2 3 2d d m c 算法 在文献【1 6 l 中，作者提出了一种目标节点驱动的组播路由算法( d d m c ) ，这个算法同 时基于最短路径树与最小生成树，但对于通过目的节点的路由有一个偏重，这使得它的 代价比最短路径树要小，而且时间复杂度相同。 此算法在下一章中还有介绍。 2 3 3c d k s 算法 e 1 ) k s 算法“73 是一个综合性能比较均衡的算法，一方面，它的时间复杂性不高，另一 方面，它的解的质量基本还可以接受，算法主要步骤如下： 1 、尝试去计算一棵低价生成树t i = ( v 。，e 。) ，它以源点为根，同时跨越尽可能多的 目的节点，计算中使用d i j k s t r a 的最短路径算法，但产生的每条路径均满足时延约束。 2 、计算一棵最短时延路径树t ，= ( v 2 ，e 2 ) ，它跨越所有t l 中没有包含的目的节点。 3 、组合t l 与t 2 而得到一棵多播树。 注意在组合t ，与t 。时也许会产生环路，图2 3 1 表示了这样一个例子，因为t 。必须 被包含在结果树中，当环路出现时，t ，中的一些边必须被移去，当t ，与t 2 所含的边有一 个公共点时，环路很容易被检测到，例如，考虑边t l 中的边e 1 2 与t 。中的边e 2 0 这两条 边均含有节点5 ，在此时，边e 1 2 必须被移去，注意边e l l 也必须被移去，因此在移去 边e 1 2 原节点4 成为一个非组播叶节点，在最坏的情况下，t 。中所有边必须被移去。 此算法具有时间复杂性0 ( 秆) 。 第1 0 页 国防科学技术大学研究生院学位论文 + c o ：m h i n i ：n g i1 勰坩一i2 f la l h is * ：3 6 8 图2 3 1c d k s 算法中环路的消除 2 3 4d v m a 算法 r o u s k a s 和b a l d i n e 提出了一个集中式的满足时延及时延抖动限制的组播路由算法 d v m a c ”，算法首先找到最短延迟路径树中一个距离源节点s 最远的目标节点。，并以s 到 达的k 条最短路径中的一条路径作为初始多播树，然后再逐渐向初始多播树中加入剩余 的目标节点，这一算法的时间复杂度为o ( k l m n 4 ) ，其中m 为多播组中目标节点的个数，n 为网络节点个数，k 、l 为算法中与最短路径相关的两个变量。由此可见d v m a 的计算复杂 度是比较高的，通过d v m a 难以有效地进行多播路由，同时经过分析发现，在d v m a 算法中， 初始多播树一经选定，如果在路径p ( s ，d ) 上存在不满足时延抖动约束条件的目标节 点，那么这些目标节点与节点。之间时延抖动的最大值 占。= n 均x d ( s ，m ) 一d ( s ，w ) 噱v m ，p 0 ，w ) v m 即是固定的，因此将6 黼x 作为尚待 加入的目标节点所需要满足抖动限制的下限条件，可以大大缩小搜索范围，进而降低算 法的计算复杂度，同时由于在算法中没有考虑多播树的代价，d v 姒所得到的结果并不是 满足时延及时延抖动约束条件的最小代价多播树，因此算法的代价性能也不是很好。 2 3 5d d v b m 算法 l o w 和l e e 提出了另一种分布式的算法d d v b m 【3 】，其计算复杂度为0 ( n 3 ) ，其中n 为 网络的节点个数，与d v m a 不同，d d v b m 解决的是满足时延及时延抖动限制的s t e i n e r 树 问题，在d d v b m 算法中，如果结果树不满足时延抖动限制，需要把已经生成的多播树中 的所有目标节点统统删除，以便建立棵辅助的s t e i n e r 节点树，然后通过一种一边建 立边删除环路的方法( c y c l em a k e - a n d b r e a k ) 来协调延迟及其抖动之间的关系，最 终使得每条路径在满足时延限制的同时，也尽量保证彼此之间的时延抖动最小，但是由 于算法中忽略了多播组中的目标节点也可以作为中间节点转发分组，所以在计算辅助 s t e i n e r 节点树时，有可能无法建立连接源节点与所有s t e i n e r 节点的多播树，从而导致 算法无法继续执行。同时d d v b m 选择了下文中将要提到的链路选择函数f 。( u ，v ) 来建立初 始多播树k ，但由于f c ( u ，v ) 本身的原因，在某些特殊的情况下，可能根本无法找到满足 时延约束的初始多播树t o ，因此其正确性有待重新估价。 第l l 页 国防科学技术大学研究生院学位论文 2 4 求解最优受限组播树的算法 2 4 1 算法描述 考虑到c s t 问题是n p 完全的，任何寻找最优c s t 的方法都会是指数时间的，这儿给 出一个方法来求解最优c s t 。 基本思想是系统地枚举图中的生成树，如果仔细考虑，相当多的生成树能够被剪除 掉，或者是由于代价太大，或者是破坏了时延约束。 这个方法来自于k i r c h o f f 的方法【l “，即枚举图中的所有生成树，对于一棵生成树， 图中的每条边或者在树上，或者不在，我们可以递归地生成原图的予图，一个子图具有 某条边e ，而另一个子图没有，然后在这些子图上考虑生成树，在包含边e 的子图中，这 条边属于生成树，然后这个子图再产生的其它子图都将具有边e ，显然一些子图不会被考 虑，因为产生了环路，另一些也不会被考虑，因为他们产生生成森林而不是生成树，最 终，当足够的边被选择后，生成子图将递减到一棵生成树。 我们通过图2 4 1 中的例子解释生成树是如何产生的，通过增加或减少一条边而生 成的两个子图将被示于它们的母图下面，具有这条边的子图显示在右边，且此边用粗黑 线显示，没有这条边的图显示于左边，此边用点线表示，注意由于几个原因，在没有查 看所有边的情况下，搜索过程能停止在任何的边上，这个例子表示了4 个可能的原因去 削减搜索，表示在标注了s t o p l 到s t o p 8 的8 个叶节点上，这个枚举策略可以通过5 个 检查减少搜索时间： 非连接图：树不能被构造，因为一些目的节点与源点不连通，看s t o p 4 ，7 ，8 。 破坏路径延迟：任何子树有一条路径的延迟超过了约束时间属这种情况，并且任 何含有这棵子树的生成树要被避免，见s t o p 5 。 代价太大：任何子树若代价超过了讫今为止所发现的最低代价就属于这种情况， 且任何含有这棵子树的生成树要避免，见s t o p 6 。 点聚集：任何子树跨越了所有目的节点是足够的，所有含有这样子树的生成树因 此不重要，既然我们不需要跨越图中所有节点，当目的节点集已被包含时我们可以削减 搜索，见s t o p l 。 生成环路：任何子图若有环路将不可能是生成树的一部分。 2 4 2 求解最优c s t 的伪码 木 t h ev a r i a b l e s m i n t r e e w e i g h t2m i n i m u mc o s to ft r e ef o u n dd u r i n gt h er e c u r s i o n p a t h d e l a y v = p a t hd e l a yf r o ms t ovi nt h et r e eb e i n gc o n s t r u c t e d d os o m ei n i t i a l i z a t i o na n ds t a r tt h er e c u r s i o n 木 a 11 t r e e s ( g ) b e g i n m i n t r e e w e i g h t = 0 ： p a t h d e l a y s = 0 ： s t a r ts p a n n i n gt r e ew i t ho n en o d ec o v e r e d s p a n ( 1 ) ： e n d t h ev a r i a b l e s 第1 2 页 t h i s t r e e w e i g h t2c o s to ft h ec r r r e n tt r e ei nt h er e c u r s i o n c o s t v ，w = c o s to fe d g e ( v ，w ) d e l a y v ，们= d e l a yo ne d g e ( y ，w ) n n o d e s = n u m b e ro fn o d e si ng = ivj 木s e a r c hf o rt h es p a n n i n gt r e ew h e nnn o d e sh a v ea l r e a d yb e e nc o v e r e d 木 s p a n ( n ) b e g i n i f ( n lvi ) t h e n t r e es h o u l db ec h e a p e ra n dc o v e ra 1 1t h ed e s t i n a t i o n s i f ( t h i s t r e e w e i g h t ( m i n t r e e w e i g h ta n da i i n o d e s c o v e r e d ( ) ) t h e n b e g i n r e m e m b e rt h i st r e e ： m i n t r e e w e i g h t = t h i s t r e e w e i g h t ： m a r ka sb e s tt r e es of a r e n d e l s e b e g i n ( v ，w ) = g e t n e w e d g e0 ：胁p i c kan e wc a n d i d a t ee d g e i f ( n on e we d g ef o u n d ) s p a n ( n n o d e s ) j | s t o pr e c u r s i o n ；i g n o r et h i sb r a n c h | e l s e b e g i n t h i s t r e e w e i g h t + = c o s t v ，w ：au p d a t et r e ec o s t 木 捧s e tu pp a t hd e l a y 卑 p a t h d e l a y w = p a t h d e l a y v + d e l a yi v ，w ： i f ( wi sad e s t i n a t i o na n da 1 i n o d e s c o v e r e d 0 ) 丰s t o pr e c u r s i o n ，a 1 1t h ed e s t i n a t i o n sh a v eb e e nc o v e r e d s p a n ( n n o d e s ) ： e l s e 拯c o n t i n u er e c u r s i o n n o t en + ln o d e sa r ec o v e r e d 年f s p a n ( n + 1 ) ： t h i s t r e e w e i g h t 一= c o s t v ，w ： d e l e t e ( v ，w ) f r o mt h eg r a p h ： p a t h d e l a y - 】= 0 ： 木f i n ds p a n n i n gt r e ei ng r a p hw i t h o u t ( v ，w ) s p a n ( n ) ： e n d e n d e n d 2 4 3 算法的时间复杂性 在最坏的情况下，在子图选择中也许会发生最后一个子图含有最优c s t 的情况，考 虑到在一个完全子图中，生成树总数为0 ( n ”) ，这个枚举过程将耗费指数时间。 第1 3 页 国防科学技术大学研究生院学位论文 图2 4 1 形成生成树示例 第1 4 页 国防科学技术大学研究生院学位论文 第三章基于链路选择函数的组播路由算法 基于链路选择函数的路由算法，其实在前面描述过的算法中已经出现过了，如基于 d i j k s t r a 的l d 、l c 、m s t 、k p p 、d d m c 、c d k s 等算法均属于此类，其中d i j k s t r a 算法与 p r i m 的m s t 算法可以说是最早出现也最为著名的两个此类算法。 这类算法的基本框架是一致的，区别在于它们各自的不同的链路选择函数，事实上， 在本论文的实验代码中，这几个函数均是在同一个子过程中实现的，只是用分支语句去 选择执行各自不同的链路选择函数。在本章中将对链路选择函数的有关问题进行一些比 较集中的阐述，同时，也描述本文提出的链路选择函数。 3 i 链路选择函数综述 3 1 1 与搜索的类似关系 基于链路选择函数的路由算法与问题求解中的搜索过程是十分相似的，网络图相当 于搜索的状态空间，链路选择函数本质就是一种代价函数，在搜索前进的过程中是依据 代价函数为其指引方向的，而且它们所求解的般都是最优化问题。 3 ，1 2 分类 、 对于时延约束组播路由问题目前提出的链路选择函数有多种，它们有的基于单一测 度如代价c o s t 或时延d e l a y ，有的则是基于由某些单一测度构成的综合测度，有的对测 度进行累积有的则不，当然也有一些更复杂的，比如，有的是进行有条件累积，有的甚 至还考虑到剩余时延或节点的度数。表3 i 1 是对链路选择函数的一个简单分类与总结。 直接 累积( 带为有条件) 测度 d e l a yl d c o s tp r i m m s tl c ，d d m c ( + ) c o s tk = i , k p p 之c d 占。 k - - 爿 , k p p 之c la d c ( ) 1 + 舭 c o s t万 d d v b m r a 一一 巧c o s t c o s t a e l a y l 一 k = l , p r i m l o g c o s t k l o g 占 e s f k 注：6 为剩余时延，且它也具有某种累积性质 表示此种组合没有含义 3 1 3 链路选择函数合理性 我们如何能够合理的为启发算法挑选选择函数呢? 两个因素影响我们的决定，首先 这个函数应该容易计算，第二