（运筹学与控制论专业论文）基于服务质量的组播路由算法研究.pdf

1 l t i c a s t s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rz h e n g l i a n w e i n o r t h e a s t e r nu n i v e r s i t y j a n u a r y2 0 0 8 【0l ? 漕 ? l 本人 的研究成 的研究成 作的同志 = 亡巴 息。 本学 文的规定 磁盘，允 或部分内 ( 如作者 学位论文 签字日期 _ ， ， 东北大学硕士学位论文摘要 基于服务质量的组播路由算法研究 摘要 随着网络技术的发展及其应用领域的不断扩大，当前的网络能支持越来越多的实时 多媒体应用，为了支持这些多媒体应用，组播通信网络也正在逐渐广泛应用。同时，许 多多媒体业务对时延、时延抖动、带宽以及网络代价等也提出了越来越高的要求，需要 当前的网络具有q o s ( 服务质量) 支持能力。时延与代价是组播研究中一对非常重要又 相互矛盾的q o s 参数，追求到每个目的节点的最小时延不利于优化组播路由树的总体 代价，而优化组播树总的代价又很难满足每个目的节点到源都有满足时延约束的路径。 一个好的组播算法通常要在组播树的总体代价与信息源到各目的节点时延之间做出权 衡。论文针对受时延约束组播路由问题设计了三种简单、快速、易于实现且满足用户 q o s 需求的组播路由算法。 论文首先分析了受时延约束的组播路由问题及相关算法，基于网络模型提出了一种 受时延约束的组播路由算法d c m r a ，该算法每次将到达组播树的代价较小，且满足端 到端时延约束的成员节点及其相应路径加入到组播树，直到所有的成员加入到组播树上 为止。在寻找路径的过程中使用了新提出的n d u r 算法，该算法在保证满足时延约束 的同时尽量减小对最小代价路径的破坏，达到了优化代价的目的。 然后将禁忌搜索算法引入到组播路由问题中来，利用该方法灵活、简单、搜索能力 强的特点，提出了一种基于中继节点变换的禁忌搜索算法t s n s m r a 来解决时延约束 组播路由问题。本算法提出了节点重要度的概念，使得通过变换中继节点得到的邻域解 集规模适中同时质量较高，进行迭代后可以得到高质量的解。 最后，由于在实际组播应用中，通常面临着组播成员的动态变化的问题，论文借鉴 了贪婪算法的思想，提出一个基于k 条最短路径算法的时延约束动态组播路由算法 d d m p 。算法为申请加入的节点寻找一条满足时延约束，同时使当前树新增代价较小的 路径。算法中共享费用的提出，给予了包含树上节点的路径一定的优先权，这样可以在 保证时延的条件下实现更多链路的共享，优化组播树的代价。 关键词：组播路由；服务质量；时延约束；最小代价；禁忌搜索；动态路由 i i l 、。 j 矿 东北大学硕士学位论文 a b s t r a c t r e s e a r c ho nq o sb a s e dm u l t i c a s t r o u t i n ga l g o r i t h m s a bs t r a c t w i t ht h ed e v e l o p m e n to fn e t w o r kt e c h n o l o g ya n de x t e n s i o no fi t sa p p l i c a t i o na r e a , t h e n e t w o r kn o w a d a y sc a ns u p p o r tm o r ea n dm o r em u l t i m e d i aa p p l i c a t i o n so nt h es a m et i m e ，i n o r d e rt os u p p o r tt h e s ea p p l i c a t i o n s ，m u l t i c a s tc o m m u n i c a t i o nn e t w o r ki sa p p l y i n gw i d e l y m e a n w h i l e ，m a n ym u l t i m e d i as e r v i c e sb r i n gf o r w a r dh i g h e rr e q u i r e m e n t so nd e l a y , d e l a y v a r i a t i o n ，b a n d w i d t h ，c o s t ，a n ds oo n ，w h i c hm e a n st h a tt h ec u r r e n tn e t w o r km u s th a v et h e q o s ( q u a l i t yo fs e r v i c e ) s u p p o r tc a p a b i l i t y d e l a ya n dc o s ta r et w oi m p o r t a n tb u tc o n t r a r y p a r a m e t e r s ，p u r s u e se a c hn o d e sl e a s td e l a yi sn o tb e n e f i tf o rt h ec o s to p t i m i z a t i o nw h i l et h e l e a s tc o s tm u l t i c a s tt r e ei sh a r dt o s a t i s f yt h ed e l a yo ft h er o u t ef r o ms o u r c et oe v e r y 。d e s t i n a t i o n u s u a l l y , ag o o dm u l t i c a s ta l g o r i t h mm u s tm a k eab a l a n c eb e t w e e nt r e e st o t a l c o s ta n dd e s t i n a t i o n sd e l a y s ot h i st h e s i ss t u d i e so nt h eq o s - b a s e dm u l t i c a s tr o u t i n g p r o b l e ma n dd e s i g n st h r e em u l t i c a s tr o u t i n ga l g o r i t h m sc h a r a c t e r i s t i co ff l e x i b l e ，s p e e d i n e s s ， e a s yt oi m p l e m e n ta n dm e e tt h en e e d so fc u s t o m e r s q o sr e q u i r e m e n t s f i r s t ，m u l t i c a s tr o u t i n gp r o b l e mw i t hd e l a yc o n s t r a i n ta n di t sr e l e v a n ta l g o r i t h mi s a n a l y z e d ，t h e nan e wa l g o r i t h md c m r aa b o u td e l a yc o n s t r a i n ti sp r o p o s e d t h i sa l g o r i t h m p u tt h ed e s t i n a t i o nw h i c ht h ec o s ti sb e t t e r , t h ed e l a yi ss u i tt h ed e l a yc o n s t r a i n ta n di t s r e l e v a n tr o u t ei n t ot h et r e e ，u n t i la l lt h em e m b e rd e s t i n a t i o n sa r eo nt h et r e e i np r o c e s so f ， f i n d i n gt h er o u t e ，an e wa l g o r i t h mn d u r i su s e d ，t h i sa l g o r i t h mr e d u c e st h ed e s t r u c t i o nt o t h ec o s tl e a s tr o u t ea sf a ra sp o s s i b l ew h e ng u a r a n t e et h ed e l a yc o n s t r a i n t t h i sa l g o r i t h mc a n a c h i e v et h eo p t i m a lc o s t t h e nt a b us e a r c hi si m p o r t e di n t om u l t i c a s tr o u t i n gi s s u e m a k i n gt h eu s eo fi t sf l e x i b l e ， e a s ya n ds t r o n gs e a r c h i n gc h a r a c t e r , at a b us e a r c ha l g o r i t h mt s n s m r ab a s e do ns t e i n e r n o d e sc h a n g e dt od e a lw i t hd e l a yc o n s t r a i n tm u l t i c a s tr o u t i n gi sp r o m o t e d t h i sa l g o r i t h m p r o p o s e st h ec o n c e p to fn o d ei m p o r t a n td e g r e e ，m a k i n gt h en e i g h b o r h o o d ss c a l ei sm o d e r a t e a n dt h eq u a l i t yi sh i g h e r a f t e ri t e r a t i o n s ，t h i sa l g o r i t h mc a no b t a i nb e t t e rm u l t i c a s tt r e e i i i 东北大学硕士学位论文 a b s t r a c t u s u a l l y , i te n c o u n t e r sd y n a m i cg r o u pm e m b e r s h i pi np r a c t i c a lm u l t i c a s ta p p l i c a t i c n s a d o p t i n gt h ei d e ao fg r e e d ya l g o r i t h m ，t h i st h e s i sp r e s e n t sad e l a yc o n s t r a i n td y n a m i c m u l t i c a s tr o u t i n ga l g o r i t h md d m p , b a s e do nk - s h o r t e s tp a t h s ，f i n d sap a t hf o rt h en o d e w h i c h a p p l yf o rj o i ni nt h et r e e a tt h es a m et i m e ，t h i sp a t hm a k e sc u r r e n tt r e e 。a d d i n gc o s tl o w e r s h a r e c o s t i n t r o d u c t i o ng i v e sc e r t a i np r i o r i t i e st ot h er o u t e sw h i c hc o n t a i n i n gt h en o d e si n t h et r e e i nt h i sc a s e ，i nt h ec o n d i t i o no fa s s u r i n gd e l a y , m o r el i n k ss h a r i n gc a nb er e a l i z e d a n dt h ec o s to fm u l t i c a s tt r e ec a nb er e d u c e d k e yw o r d s ：m u l t i c a s tr o u t i n g ；q u a l i t yo fs e r v i c e ；d e l a yc o n s t r a i n t ；l e a s tc o s t ；t a b us e a r c h ； d y n a m i cr o u t i n g i v 东北大学硕士学位论文 目录 目录 独创性声明i 中文摘要i i a b s t r a c t i i i 第一章绪论1 1 1 课题研究的背景及意义1 1 2 组播路由技术介绍1 1 2 1 网络数据传输方式l 1 2 2 组播路由的基本概念2 1 3 组播路由技术的发展现状4 1 4 论文研究内容和组织结构一5 1 4 1 论文研究内容5 1 4 2 论文的组织结构6 第二章q o s 组播路由研究基础7 2 1 概述7 2 2 服务质量的定义及其约束7 2 2 1 服务质量的定义7 2 2 2 组播路由问题的q o s 约束8 2 3q o s 组播路由的网络模型9 2 4 现有组播路由算法1 0 2 4 1 组播路由算法的分类1 0 2 4 2 组播路由典型算法11 2 5q o s 约束组播路由算法研究难点和几个亟待解决的问题1 3 2 5 1q o s 路由中研究的主要难点1 3 2 5 2q o s 组播路由算法研究中几个亟待解决的问题1 3 2 6n p 问题介绍1 4 2 7 本章小结1 5 第三章一种时延约束组播路由算法1 6 v 东北大学硕士学位论文 目录 3 1 时延约束组播路由问题描述1 6 3 2 相关算法介绍16 3 3 时延约束组播路由算法d c m r a 1 8 3 3 1 算法基本思想1 8 3 3 2d c m r a 算法实现需要解决的问题1 9 3 3 3d c m r a 算法的具体描述一2 l 3 4 算法分析2 2 3 4 1 算法正确性分析2 2 3 4 2 算法复杂度分析2 3 3 5 仿真实验及结果2 4 3 6 本章小结2 5 第四章基于禁忌搜索的时延约束组播路由算法2 6 4 1 禁忌搜索算法2 6 4 2 已有的基于禁忌搜索算法解决组播路由问题的算法2 7 4 3 中继节点变换的禁忌搜索算法2 8 4 3 1 算法的基本思想2 8 4 3 2 初始解的生成一2 8 4 3 3 邻域解集的生成2 9 4 3 4 候选节点的选取3 0 4 3 5 参数k 的确定3 0 4 3 6 禁忌表与禁忌长度31 4 3 7 解禁准则。31 4 3 8 终止规则31 4 4 算法伪代码3 2 4 5 算法分析3 4 4 6 仿真实验及结果3 4 4 7 本章小结3 6 第五章有时延约束的动态组播路由算法3 7 5 1 动态组播路由算法的分类3 7 v i 东北大学硕士学位论文目录 5 1 1 不重组的动态组播路由算法3 7 5 1 2 重组的动态组播路由算法3 8 5 2 已有的动态组播路由算法3 9 5 3 有时延约束的动态最小代价组播路由问题4 0 5 4 时延约束动态组播路由算法d d m p 4 0 5 4 1 算法基本思想4 0 5 4 2 算法中用到的几个概念4 1 5 4 3 算法过程描述4 2 5 5 算法分析4 3 5 5 1 算法正确性分析4 3 5 5 2 算法复杂度分析4 4 5 6 本章小结4 5 第六章结束语4 6 6 1 论文的主要工作4 6 6 2 论文的不足和未来的研究方向4 7 参考文献4 8 致谢一5 2 v i i t i 东北大学硕士学位论文 第一章绪论 第一章绪论弟一早三百了匕 1 1 课题研究的背景及意义 传统的分组交换网络，如i n t e r n e t ，是面向非实时的数据通信而设计的，主要是为 了优化整个网络的数据吞吐量并保证数据通信的可靠性。而随着移动i n t e m e t ，全光 i n t e r n e t 和3 di n t e r n e t 等高性能网络技术的发展及其应用领域的不断扩大，新兴了大量 的多媒体应用，如网络视频会议、多媒体远程教育、网络游戏等等均涉及多个用户参与， 这不仅需要消耗大量的网络资源，而且视频、音频语音、动画等多媒体业务不但对网络 有很高的带宽要求，而且要求信息传输的低时延和低代价等。 为满足上述需要，服务质量( q u a l i t yo fs e r v i c e ，q o s ) 和组播( m u l t i c a s t ) 的概念随 之出现。q o s 是网络在传输数据流时要满足的一系列服务请求，具体可以量化为带宽、 时延、时延抖动、丢包率、吞吐量等性能指标。此处的服务具体是指数据包( 流) 经过 若干网络节点所接收到的传输服务，强调端到端或网络边界到边界的整体性。q o s 反映 了网络元素在保证信息传输和满足服务要求方面的能力。而组播( 也称多播) 则是一种 允许一个或多个发送者( 组播源) 发送单一的数据包到多个接收者的网络技术。实现组 播通信的关键是如何确定组播路由，即如何找到满足某些条件的组播树。但是当前 i n t e m e t 中的路由算法主要是保证基本的连通性，路由协议是基于单一度量( m e t r i c ) 优化， 难以满足多样的q o s 需求，而近年来的研究表明，路由算法对实现网络的服务质量保 证起到了非常关键的作用，同时也是平衡网络负载，控制网络拥塞以及充分利用网络资 源的重要保证。简单地讲，q o s 路由就是要寻找满足特定q o s 要求的一条路由路径( q o s 单播路由) 或一棵组播树( q o s 组播路由) ，其目的是在路由建立的过程中为网络应用 提供q o s 服务，并可以优化网络资源，提高网络资源的利用率。 1 2 组播路由技术介绍 1 2 1 网络数据传输方式 数据包在网络中传输一般有三种方式：单播( u n i c a s o 、组播( m u l t i c a s t ) 和广播 东北大学硕士学位论丈第一章绪论 ( b )( c ) 图1 1 数据包在网络中传输的三种方式( a ) 单播( b ) 组播( c ) 广播 f i g 1 1t h r e et r a n s m i tm e t h o d si nn e t w o r k ( a ) u n i c a s t ( b ) m u l t i c a s t ( c ) b r o a d c a s t 1 2 2 组播路由的基本概念 1 组播源节点 2 东北大学硕士学位论文 第一章绪论 组播源节点是指发起组播通信的节点，在“点对多点”通信模式中，一次通信业务 中只有一个组播源节点；在“多点对多点”的通信模式中，一次通信业务中可以有多个 组播源节点。 2 组播目的节点 组播目的节点是指组播通信的接收者。通常，在一次组播通信中会有多个组播目的 节点，组播目的节点又可叫做组播节点。 3 组播组 组播组即组播目的节点集合，是将参与组播的多个目的节点组成一个组播组，每个 目的节点称为组播组成员或成员节点。 4 组播树及其分类 组播树是指包含组播源节点、所有的组播目的节点及使它们之间有效连通的链路的 集合，因为可以看成是以组播源节点为根，各目的节点为叶子节点的树状结构，所以形 象地称之为组播树。一般来说，组播树有三种类型：洪泛法、有源树和共享树。 洪泛法( f l o o d i n g ) 不构造所谓的分布树，只是向前传送组播路由，算法简单。基本 原理为：当组播路由器收到发往某个组播地址的数据包后，首先判断是否是首次收到该 数据包，如果是首次收到，那么将其转发到所有接口上，以确保其最终能到达所有接收 者；如果不是首次收到，则将该数据包抛弃。洪泛法需要维护一个最近通过的数据包列 表，但并不需要维护路由表，它适合于对组播需求比较高的场合，并且能做到即使传输 出现错误，只要还存在一条到接收者的链路，则所有接收者都能接收到组播数据包【2 】。 通常认为洪泛法不适合用于i n t e m e t ，这是因为它不考虑链路的状态，并且产生大量的 拷贝数据包。而且，对于高速网络而言，最近通过的数据包列表将会很长，将耗费相当 大的内存，尽管它不会对相同的数据包进行二次转发，但有可能对相同数据包接收多次。 有源树是组播树中最简单的一种形式，也称为基于信源的树或最短路径树( s p t ， s h o r t e s tp a t ht r e e ) 。它是以组播源为根构造的从根到所有接收者路径都最短的分布树。 如果组中有多个组播源，则必须为每个组播源构造一棵组播树。有源树的优点是：有利 于网络中数据流量的均衡，由于从组播源到每个接收者的路径最短，所以端到端的时延 最小，有利于流量大、时延性能要求高的实时多媒体应用。它的缺点是：要为每个组播 源构造自己的分布树，这样，当数据流量不大时，构造有源树的开销相对较大。 共享树是指为每个组播组选定一个共用的根节点( 汇合点或核心) ，以该点为根建 3 东北大学硕士学位论文第一章绪论 立的组播树。同一组播组的组播源首先将数据单播到根节点，然后再由根节点向其它成 员转发。最具代表性的两种共享树是s t e i n e r 树和有核树( c b t ，c o r eb a s e dt r e e ) 。s t e i n e r 树是总代价最小的分布树，有核树是由根到所有组成员的最短路径合并而成的树。共享 树在路由器所需存储的状态信息的数量和路由树的总代价两个方面具有较好的性能。当 组的规模较大，而每个成员的数据发送率较低时，使用共享树比较合适。当通信量较大 时，使用共享树将导致流量集中，以及根会成为瓶颈。目前的研究主要集中在有源树和 共享树这两种类型的组播树上，如何在网络中为源节点和所有目的节点合理地构建一棵 组播树的问题，就是组播路由算法要研究的主要内容。 5 组播路由 组播路由就是组播源把数据包沿着网络路由发送到特定组播组，而只有属于该组播 组的地址才能接收到数据包。组播可以大大的节省网络带宽，因为无论有多少个目标地 址，在整个网络的任何一条链路上只传送单一的数据包。 6 组播路由算法 组播路由算法就是要根据网络拓扑结构和链路状态，在满足约束条件下建立一种结 构来实现目标函数的优化，使网络费用最小。而解决组播路由的有效办法就是建立组播 树。因为第一，信息可以沿着树的分支并行的传到各目的节点。第二，信息只在树的分 支处进行复制，从而使复制的份数尽可能的少。 1 3 组播路由技术的发展现状 1 9 8 8 年s t e v ed e e r i n g 在他的博士论文数据报互连网络中的组播路由中正式提 出了网络层组播的概念，奠定了组播网络体系结构和路由协议的基础。这之后，支持组 播的路由协议和基于组播的应用得到学术和业界的大力支持，从而掀起了组播实践的高 潮，众多的研究学者提出了各种相关算法，主要的一些如下： 1 9 9 3 年，k o m p e l l a 等【4 1 首次提出了带时延约束的组播路由求解问题并给出了相应 的算法，同时将其推广到分布式环境，但是此算法时间复杂度高，而且在分布式的环境 下易于阻塞。1 9 9 5 年，s u n 等提出c d k s 算法，此算法通过一个合并过程来保证时延 的要求，它的综合性能较好，但是由于存在合并的过程，使其难于在分布式的环境下部 署。1 9 9 7 年，r o u s k a s 等首次提出了带时延及时延抖动约束的算法，但此算法并没有 考虑对代价的优化，同时复杂度也相当高。1 9 9 8 年p a r a s 等提出了b s m a 算法【6 】，此 4 东北大学硕士学位论文第一章绪论 算法是目前比较好的算法之一，但时间复杂度也是相当高的，同时算法本身也很复杂。 2 0 0 0 年，l e e 等【7 1 提出一种目的节点驱动的组播路由算法，但在此算法中考虑的是平 均时延，并不能保证实时环境下对时延的要求。近年来，国内外许多学者开始利用神经 网络、蚁群算法、遗传算法等启发式智能算法来解决问题，并取得了一定的成果。其中 蚁群优化算法以其健壮性和并行性、灵活性、搜寻过程不需要人工干预以及求解精确度 高的特点，得到了广泛应用，但此算法在进行大规模优化时，初期收敛速度慢，收敛时 间过长，易陷入局部最优解，这是蚁群算法的最为突出的缺陷。组播路由技术已经历了 近二十年的发展，但这个研究领域仍然非常热门，因为还有很多问题悬而未决。 另外在网络迅速膨胀的今天，网络研究人员一方面要不断思考新的网络协议和算 法，为网络发展做前瞻性的基础研究；另一方面也要研究如何利用和整合现有的网络资 源，使网络达到最高效能。无论是哪一方面都需要对新的网络方案进行验证和分析，期 望总是在现实的网络中达到这个目的是不现实的，仅仅进行理论分析也不能转化为成 果，网络仿真无疑提供了一个方便、高效的验证和分析方法。网络仿真是使用计算机技 术构造网络拓扑，实现网络协议模拟的网络行为。它能获取特定的网络特性参数，进而 可对网络性能进行研究和分析，达到改善网络运行状况的目的。然而现有的网络仿真软 件的路由仿真功能都存在一定的局限性，不能很好地实现对真实的网络状态与非精确状 态信息的模拟，而且大多数仿真软件也很少支持q o s 路由。因此，研制出一套不仅能 模拟出真实的网络状态和非精确的状态信息，而且能支持q o s 路由的动态路由仿真系 统也是网络路由研究中必不可少的关键步骤。 1 4 论文研究内容和组织结构 1 4 1 论文研究内容 从以上的分析中可以看出，基于q o s 的组播路由算法的研究对网络理论和应用都 有重大意义，是该领域重要的研究内容之一。然而目前的组播路由算法并不适合于投入 现实的运行，因此本文针对这一现状提出了新的、可行的组播路由算法。 本文研究满足时延约束代价优化的组播路由问题，在分析与本课题相关内容的研究 现状及存在问题的基础上，我们明确了本文的主要研究目标，研究内容归纳如下： 1 对目前存在的组播路由算法进行深入研究与分析，建立支持q o s 的组播路由问 5 东北大学硕士学位论文第一章绪论 题的网络模型。 2 对基于时延约束的组播路由问题进行研究，提出了一种满足时延约束的组播路 由算法，并优化了组播树的代价。 3 对一种启发式算法禁忌搜索算法进行了分析，提出了一种基于禁忌搜索算法的 时延约束代价最小组播路由算法。 4 基于支持动态组播在组播路由中的重要性，对时延约束代价最小的动态组播路 由问题进行研究，提出了一种满足时延约束的动态组播路由算法。 5 设计实现了仿真实验环境，并对算法进行了仿真实验以及正确性证明和复杂性 分析。 1 4 2 论文的组织结构 在研究的过程中，首先提出问题，建立数学模型，并提出相应的算法，然后对算法 进行仿真和分析，最后得出结论。 全文共分六章： 第一章是绪论，首先介绍了组播路由的一些基本概念，然后介绍了组播路由的发展 现状以及本文的研究内容和组织结构。 第二章是q o s 组播路由的研究基础，介绍了q o s 的概念以及q o s 约束，提出了 q o s 组播路由的网络模型，之后介绍了现有的比较经典的组播路由算法，最后简要介绍 了n p 问题。 第三章首先描述了时延约束组播路由问题，然后简要的介绍了现有的时延约束组播 路由算法，提出了一种解决这种问题的一个新的算法d c m r a 。 第四章提出了基于禁忌搜索算法的组播路由算法，用来解决时延约束组播路由问 题，并优化了网络费用。 第五章首先介绍了动态算法的分类及现有的一些动态算法，然后提出了动态时延约 束路由问题，最后提出了一种解决这个问题的新算法d d m p 。 第六章是对全文的总结，指出研究中存在的不足和今后的研究方向。 6 东北大学硕士学位论文第二章q o s 组播路由研究基础 2 1 概述 第二章q o s 组播路由研究基础 路由包含两个基本功能：一是搜集网络的状态信息并不断更新；二是根据所搜集的 信息计算可行路径。q o s 的概念用来刻画服务提供者与用户间用数量或质量来定义的性 能约定，一次连接的服务质量由一系列条件给出，如带宽约束、时延约束、抖动约束等。 q o s 组播路由的基本任务是为连接寻找有足够资源、能满足q o s 要求的一棵树。q o s 路由不同于尽力而为的路由，因为q o s 路由通常是面向连接、有资源预留功能，而后 者有可能是面向连接的，也可能是无连接的，根据当前获得的资源不同，服务质量方面 也有所不同。并且与传统的“尽力而为”的路由选择相比，服务质量选路不仅关心信源 到信宿的连通性，而且关心路由是否能够满足业务所提出的各种服务质量要求( 比如时 延约束、带宽约束、可靠性要求等) 。因此，服务质量选路需要同时考虑业务需求和网 络当前的可用资源状况，这包括两个方面：一是网络状态信，f f , ( l k 女n 可用资源) 的管理， 涉及到选择哪些网络状态信息来表述网络以方便于服务质量选路，如何保证网络节点保 留信息的准确性( 信息的准确性影响着服务质量选路算法的有效性) 以及状态信息的更 新等；二是利用获得的网络状态信息，使用选路算法计算相应的路由。 所谓基于q o s 的组播路由算法就是按照某种路由策略，利用网络状态信息来构造 一棵包含所有组播成员的组播路由树，以确定数据包的传送路径，同时满足各种q o s 要求，实现网络资源的优化。从网络用户的角度来看，基于q o s 的组播路由算法首先 应满足用户的q o s 需求，即寻找一条端到端的，满足各种条件的传输路径。同时，从 网络工程师的角度来看，基于q o s 的组播路由算法应能够有效地选择传输路径，从而 保证网络的最大吞吐量。不仅如此，大多数应用还要求组播能有效的支持成员的动态加 入与退出，期望成员加入组时成功率要高，时延要短。 2 2 服务质量的定义及其约束 2 2 1 服务质量的定义 服务质量，是网络传输业务流时业务流对网络服务的要求集合，其中业务流是指与 7 东北大学硕士学位论文第二章o o s 组播路由研究基础 特定q o s 相关的从源到目的地的分组流【8 1 ，其中网络服务的需求大致包含下列可度量 参数： 1 时延( d e l a y ) ：也称为延迟，在组播树中，网络时延指的是从源节点到目的节点时 延中的最大值。时延要求一般以时延上界的形式给出，网络通过服务质量控制保证媒体 流的传输不超过时延上界。 2 带宽( b a n d w i d t h ) ：是指在一定特定的时间内网络所能传送的比特数。 3 时延抖动( d e l a yj i t t e r ) ：指媒体流各单元之间的时间差异。时延抖动对时间相关 媒体来说是一项极重要的传输性能参数。 4 丢包率( p a c k e tl o s sr a t e ) ：在网络中传输数据包时丢弃数据包的最高比率，数据包 丢失一般是由网络拥塞引起的。 5 网络总代价( c o s t ) ：一般用来表示信息传输时所消耗的资源或资金。在组播路由 计算过程中，由于其业务流只在分叉点处进行复制，而在公用路径上能做到资源共享， 因此网络的总代价为所构造的生成树的所有边的代价总和。 2 2 2 组播路由问题的q o s 约束 网络在传输相应的数据业务时，必须满足时延、时延抖动、网络代价等要求。q o s 需求可以通过一个约束集来描述，包括链路约束和树约束两大类： 1 链路约束：是在进行链路选择时对链路使用的限制，链路约束定义了从源节点 到目的节点的每一条链路的约束，是对路由选择所使用的链路的一种限制。例如，带宽 约束，要求链路上的带宽必须大于或等于某个预定义的值。 2 树约束：( 1 ) 对组播树上从源节点到目的节点的每条路径上的综合性能的约束。 如从源节点到每个目的节点的路径时延。( 2 ) 对从同一源节点到任意两个目的节点的路径 上的性能差异的约束，如从一源节点到任意两个接收端的时延抖动。 依据组播树约束及其相应的链路量度，树约束又可分为以下三类【9 】( m ( 1 ) 为链路， 的度量) ： 加型树约束：对任一路径弓( “，y ) = 伽，f ，k ，1 ，) ，若m ( u ，y ) = m ( u ，i ) - k m ( i ，j ) + ( 七， ，) ，则称该树约束为加型。例如，实时应用中端到端的最大时延约束就是对组播树 上由源节点至目的节点所经过的所有链路时延的总和的约束。 8 东北大学硕士学位论文第二章q o s 组播路由研究基础 乘型树约束：对任一路径p a u ，1 ，) = 伽，i ，k ，) ，若m ( u ， ，) = m ( u ，i ) x m ( i ，j ) m ( k ，v ) ，则称该树约束为乘型。例如，路径的可靠性约束就是对组播树上e h 源节点至目 的节点所经过的所有链路可靠性乘积的约束。 凹型树约束：对任一路径g ( u ，v ) = 缸，i ，k ，v ) ，若m ( u ，v ) = m i n m ( u ，f ) ，m ( i ，) m ( k ，1 ，) ) 则称该树约束为凹型。例如，应用对路径带宽的要求，它等于组播树上由源 节点至目的节点所经过的所有链路的可使用带宽中最小的链路带宽。 2 3q o s 组播路由的网络模型 就组播而言，网络通常表示成一个带权图g ( v ，e ) ，其中v 代表节点的集合，e 代 表连接节点的链路集合。i v i 和蚓分别代表节点的数量和链路的数量。为了不失一般性， 我们只考虑任意一对有序节点之间最多只有一条链路的有向图，链路用( “，v ) 来表示， 关联每条链路的参数就是该链路的q o s 度量。 假设组播会话的源节点为50 v ) ，msv p ) 是组通信中的一组节点集，我们称 m 为目的节点集，也称为组播组，m 中的每个节点m m 称为组成员，i m l 表示目的 节点集的大小。组播树丁是g 的子图，是根为s 并包含目的节点集合m 的一棵树，用 r ( 巧，屏) 表示，其中v ，易量e ，t 中存在由源节点s 到每个目的节点m m 的一 条路径，用p ( s ，所) 表示。假设对于任意一条链路e e ，关联代价、时延、带宽及丢包 率四种q o s 度量函数，则组播树丁( ，屏) 存在下列关系： c o s t ( p ( s ，小) ) = c o s t ( e ) ，v m m e p ( s ，m ) d e l a y ( p ( s ，m ) ) = d e l a y ( e ) ，v m m e p ( s ，m ) w i d t h ( p ( s ，朋) ) = m i n w i d t h ( e ) ，e p ( s ，小) ) ，v m m p a c k e t l o s s ( p ( s ，m ) ) = 1 - 兀( 1 - p a c k e t l o s s ( e ) ) ，v 朋m e p ( s ，m ) 由此，给出如下定义： 定义2 1 组播树丁的代价c o s t 定义为组播树中所有链路的代价和，即 9 ( 2 1 ) ( 2 2 ) ( 2 3 ) ( 2 4 ) 东北大学硕士学位论文 第二章q o s 组播路由研究基础 c o s t ( t ) = c o s t ( e ) 。 f e 易 即 ( 2 5 ) 定义2 2 组播树丁的时延d e l a y 定义为由源节点s 到各目的节点路径时延的最大值， d e l a y ( r ) = m a x 唧( 州) d e l a y ( p ) ) 2 v m 。a 。m x d e l a y ( p ( s ，聊) ) ) ， v ，2 m ( 2 6 ) 定义2 3 给定带权图g ( v ，e ) ，源节点s ，目的节点集m ，q o s 约束集c 以及优化 目标函数0 。q o s 组播路由就是以网络拓扑结构和网络状态为基础，构建一棵组播树r ， 包含源节点和所有目的节点，并且满足给定的约束条件c 以及优化目标函数d 。 2 4 现有组播路由算法 2 4 1 组播路由算法的分类 组播路由算法可以根据不同的角度和准则来分类： 1 算法按照网络状态信息维护的方式和路径的搜索方式可以分为集中式原路由算 法和分布式路由算法【1 0 】。 ( 1 ) 集中式源路由 源路由中，每一个节点维护着完整的全局信息，包括网络拓扑结构和每一条链路的 状态信息，最优路径的计算基于这些全局信息在源节点进行。源路由采用集中处理的方 式，因此在发出路由请求时，可以立即获得预先存在的路由信息，无需在网络的各个节 点之问进行信息交换，避免了分布式计算中死锁检测，分布计算终止检测等问题，并且 可以保证计算出来的路径不出现回路。但原路由也有如下四个缺点：会聚信息量大。 由于每一个节点都需要维护整个网络的状态信息，所以网络中会聚的信息量很大，因而 导致网络的整体效率也相应降低。状态信息不精确。由于整个网络的大量状态信息 需要会聚到每一个节点，而会聚需要一定的时间，导致节点所使用的网络状态信息并不 能精确地反映网络的实时状态。源点的计算量大。节点接收到会聚的网络信息之后， 需要启动一个最短路径算法，根据整个网络的拓扑信息来计算本节点到所有其它节点的 最短路径，据此生成路由表，这样的计算在每一个节点都要进行一次，计算量非常大。 具有可扩展问题。由于每个路由器的存储量是有限的，因此随着网络规模扩大，支 持源路由的路由器所维护的网络状态信息量也随之增大，对于大规模的网络，路由器的 1 0 东北大学硕士学位论文 第二章q o s 组播路由研