（计算机应用技术专业论文）基于qos的多播路由算法研究(1).pdf

摘要 在计算机网络中，许多多媒体业务如视频点播、视频会议、远程 教学等都需要采用多播通信方式来传送信息，以节省网络资源。随着 网络技术和网络应用的快速发展，这些业务要求网络必须提供保证质 量的服务，而传统的多播只提供尽力传输服务，无法直接满足用户对 网络的不同服务质量( q u a l i t yo f s e i c e ，q o s ) 要求。因此作为支持网络 多媒体业务的关键技术之一，基于q o s 约束的多播路由引起了广泛重 视。如何建立满足0 0 s 约束的性能良好的多播树已成为计算机网络中 研究和开发的热点和难点问题。 本文对基于q o s 约束的多播树的构造问题进行深入研究，针对时 延约束问题，给出了一种改进的静态算法，同时针对多播组成员动态 变化的情况，提出一种新的动态算法，对两种算法都进行了仿真实验。 本文的主要工作如下： 1 本文对大量的基于q o s 的多播路由算法进行调研和总结，尤 其是多约束算法和动态算法，分析了各种算法的复杂度、适用情况和 特点，为后面的工作打下了基础。 2 对已有的一些时延约束算法进行分析，指出其优点和不足之 处，并在快速最小代价树算法的基础上给出一种改进算法，通过动态 修改节点之间的时延，获得了满足时延约束的性能较优的最小代价 树。实验结果表明，该算法时间复杂度很小、代价性能良好。 3 对动态多播路由问题进行研究，分析了已有的一些动态算法， 提出一种新的动态q i 哂多播路由启发式算法。该算法充分考虑路径时 延对多播树总代价的影响，利用前七条最短路径方法和路径选择函数 北京交通大学硕士学位论文 来生成多播树。算法可以在满足时延约束的情况下，快速地找到性能 较好的多播树，同时可以根据网络节点的加入或退出请求来更新多播 树，实现对多播树的动态维护。实验结果表明，该算法代价性能良好、 能够满足多媒体网络的实时性要求。 最后对q o s 多播路由算法今后的研究工作提出了一些设想和看 法。 关键词： 多播路由，服务质量，s t e i n e r 树，时延约束，动态多播 a b s t r a c t m a n ym u l t i m c d i a 印p l i c a t i 伽ss u c ha sv e d i o o n d e m 柚d ，v e d i o c o n f e r e n c e ，l o n 分d i s t a n c ee d u c a t i o n ，e t c ，e c dm u l t i c a s t t ot r 柚s m i t i n f o 姗a t i o ni nn e m o r k i ti sg o o df o rs a v i n gn e t w o r kr e s o l l r c e w i n lt h e s p c e dd e v e l o p r n e n t o fn c 咖r kt e c l l n o l o 盱孤d a p p l i c a t i o n s t h 鹳e m u l t i i n e d i aa p p l i c a t i o n sr c q u i r et h a tn e m o r kp m v i d c sq u a l i t yo fs c r v i c c ( q o s ) b u t 也e 缸a d “i o n a lm u l t i c a s tj u s tp f o v 妯髂“b e s t 幽妒f o r 鼹州i c e nc 锄o tm e e te v e r yk i n d so fq o sf 研d i s t i n c tm u l 由n e d i aa p p c a 瞳i o n st l l a t r e q u e s t ( b s 舡ak e yt e c h n i q u et h a ts u p p o n sm u l t i m e d i aa p p l i c a t i s ， t h eq o sm u l t i c a s tm u t j n gp r o b l e mg e t sm o r ea t t e n t i o n h o wt oc r e a t c m u l t i c a s tt r e c st h a ts a t s f yc o n s l r a i n l sb e m e so n eo ft l l em o s th o t 趾d d i f f i c u l tp r o b l e m so fr e s e a r c hi nn e m o r k t h i st h e s i sc c n t e 墙o nt h ec r e a t i n gp r o b l e mo fm u l t j c a s tt f e e sb a s e do n q o s i tp f e s e n t sa i li m p m v e ds t a t i ca l g o r i t h mf o rd e l a yc 0 璐t r a j n e d p r o b l e m ，p m p o s e sa n e wd y n a m i ca l g o r i t h mf b rd y n a m i cm u l t i c 弱tr o u t j i l g p m b l e m 柚dd o e se x p e r i m e n t sf o rt h et w oa l g o r i t 胁s t h em a i l lr e s e a r c h w o r ka n dr e s u l t sa r ea sf o u o w s ： 1 s u 咖a r i z em a n ym u n i c 器ti o u t i n ga i g o r i t h m sb a s e do n ( b sa n d a i l a i y z et h ec o m p u t a t i o n a lc o m p l e x i t y 趾da p p l i c a b l ec o n d i t i o n so fe a c h a l g o r i t l i m ，e s p e c i a n ya l g o f i l h m s w i t hm o r en l a no n e n s t r a i n t 锄d d y l l 枷i ca l g 嘣t h i n s n i si s 也eb a s i so ft h ef o l l o w i n gw o r k 2 b 鹪c do ns 衄ee x i s t i n ga 1 9 0 血h m s ，t h r o u g hm o d i f y i n gd e l a y s b e t 、j l r e c nn o d e sd y n 锄j c a l l y ，an e wa l g o r i 岫f o r d e l a y - c o n s t 豫i i l e d l l l i n i m 啪c d s tn ci sp r c s e t e d ，w h i c hh 勰i c cc o s tp e r f b n n a n c e 卸dc a n g e td d a y c o n s t r a i n e d | l l i n i m u m c o s t 仃e eq u i d dy ! ! 塞壅夔拦堡主堂鱼堡奎 3 an e wh 即矗s t i ca 1 9 0 r i t h n lf b rd y n a m i cq o sm u m c 雒tr o u t i n gb 嬲c d o n 柚a l y s i s o fd y n 锄i cm u l t i c 雒t 咖t i n gp m b l 锄i sp m p o s e d t h e a l g o 棚mt a l 【e st i l ei n n u e n c eo fp a t l ld e l a yt ot r e cc o s ti n t 0a c c o l l i i t ，柚d m a l 【e su s eo ft h em e t h o d 血d i n gt h c 七s h o n 骼tp a t h s 柚dt h ef l l n c t i o no f s e i e c t i l i g p a t l l t oc r e a t cm u l t i c a s tt r e e w h j l et h ed e l a y0 0 n s 仃a i n ti s s a t i s 6 e d ，t h ca l g o r i t l l n lg e t st h el a wc o s t 眦eq u i c l d y 柚dc 锄u p d a t e m u l t i c a s t 仃c eb 黯e d 曲a i 旧i n 酬d c t i n g 咒q u 洫m 叨t so fn o d c s al a r g c n 岫b e ro fs i m u l a t i o 璐d e m o 璐仃a t ct h a tt h ea l g o r i t l l l i lh a sn i c cc o s t p c r f b m 矾卸dc 矩s a t i s 母t h ef e a lt i l i l er e 驴i r c m e n to f 删咐o r k a tl a s t ，s 嘲e 龉锄m p t i o n s 卸dv i e w so nf i l t l l r er c s e 盯c ho fm u l t i c a s t r o u t i n ga l 鲥岫sb a s e do nq o s 缸ep r o p o s e d k e y w o r d s ：m u l t i s tr o u t i n 岛q i l a l i l yo fs c r v i c c ，s t e i l l c r1 1 r e e ，d e l a y c o n s 砌n t ，d y n a m i cm u l t i c 嬲t 北京交通大学硕士学位论文 y8 7 9 7 0 1 独创性声明 本人声明，所呈交的学位论文是我个人在导师指导 下进行的研究工作及取得的研究成果。尽本人所知，除 了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北 京交通大学或其他教学机构的学位或证书而使用过的 材料。与我一起工作的同志对本研究所做的任何贡献已 在论文中作了明确的说明并表示了谢意。 本人签名：高攻攻 日期：立堕年月日 北京交通大学硕士学位论文 关于论文使用授权的说明 本人完全了解北京交通大学有关保留、使用学位论 文的规定，即：学校有权保留送交论文的复印件，允许 论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。论 文中所有创新和成果归北京交通大学计算机与信息技 术学院所有。未经许可，任何单位和个人不得拷贝。版 权所有，违者必究。 本人签名：壹垂堑 日期：溯年；月扩日 绪论 1绪论 1 。1q o s 多播路由的研究意义 网络上的很多应用，需要将信息从一点传输到多点，若采用传统 的通信方式，将会造成降低网络传输效率、浪费网络资源等问题。因 此，针对该问题提出的多播被广泛应用，以节省网络中的宝贵资源。 随着高速网络和多媒体技术的进一步发展，人们越来越多地提出 了各种各样的服务质量( 0 u a l i t yo fs e r v i c c ，q o s ) 要求。而传统的多播只 提供尽力而为服务，无法满足q o s 需求。因此，基于q o s 的多播路 由引起了广泛重视，研究能满足应用要求的基于q o s 的多播路由算法 是现实而有重要意义的，这种研究对于网络理论和应用的发展将起到 重大的推动作用。 1 1 1 多播路由研究背景 网络中传统的通信模式主要有单播( 点到点传播) 和广播( 一点到 所有点传播) 两种形式。随着通信技术和交换技术的飞速发展，特别 是移动计算和分布式计算的迅速普及，单播和广播这两种通信模式已 不能满足网络通信的需求，由此，产生了多播方式。计算机网络的许 多应用例如视频点播( v o d ) 、视频，音频会议、远程教学、分布式游 戏、计算机支持的协作工作等都需要网络具有多播服务的能力。这些 应用需要消耗大量的网络资源，会造成网络拥挤、传输延肘等问题。 与传统的单播和广播机制相比较，多播可以解决上述应用所要求的网 络利用率高、传输速度快、实时性强等问题，它能显著的节省带宽资 北京交通大学硕士学位论文 源，减轻服务器负荷，并且改善传送数据的质量。多播己被看成是m ，r f ( i n t e m e t 工程任务组) 的一个关键问题。多播能力则是因特网的一个 重要特性。 多播也称组播或组内广播等，是一种实现从源节点同时向多个目 标节点发送信息的通信形式。典型的多播应用包括更新数据库、命令 控制系统、分布式游戏和分布式交互仿真等。多播路由是实现多播通 信的关键技术之一，随着人们对多播兴趣的增加，多播路由技术得到 了深入的研究。目前解决多播路由问题的典型方法是构建覆盖源节点 和目标节点的多播树来传送信息。因为树型路由有两大优点：只在分 支点处才进行包复制，网络中要传递的复胄4 信息少，能节省带宽资源 减少拥塞，降低网络负载；信息并行沿树枝发送到不同目标节点，降 低了信息传递延迟。 1 1 2q o s 多播路由 随着视频会议、视频点播等实时多媒体多播通信需求的增长，要 求多播路由必须具有严格的服务质量保证，主要包括带宽、时延、时 延抖动、代价、丢包率等；与此同时，多播业务也已被用于各种流媒 体应用中，如多播业务主干网已被用于传输实时音频视频新闻、远 程学习及视频会议等信息，服务质量保证对于这些多播业务具有特别 重要的意义。而传统的多播路由，如基于c b t 的路由协议【1 】和协议无 关多播路由协议p i m 【2 j 等，其构造的多播树主要是基于连通性度量， 较适用于提供尽力传输服务，可能难以满足具有服务质量要求的实时 多媒体业务传送的需要。因此，具有q o s 约束的多播路由算法的研究 逐步发展起来。它是以o o s 为中心的网络体系结构中不可缺少的组成 2 绪论 部分，己成为网络研究领域的重要内容和热点问题。 所谓q o s 多播路由就是根据网络中可用资源和网络业务的q o s 要 求，寻找从源节点到多个目的节点的传输路径。一般路由选择由两个 部分组成：一是根据已有的信息为到达业务选择合适的路径并发送数 据包，即寻路过程；二是收集网络状态信息并不断更新消息，也就是 节点问路由信息的交互过程。本文所做的路由算法研究是针对第一个 部分的。 q o s 多播路由的主要目标是：为每个接纳的业务请求找到满足其 服务质量要求的可行的多播树，满足用户的需求；在满足服务质量需 求的情况下，优化全局资源利用率，平衡网络负载，从而最大化网络 接受其他业务请求的能力。q o s 路由算法的选择对q o s 路由的实现起 到决定性作用。 1 2 q o s 多播路由的研究现状 q o s 多播路由就是为多播应用寻找满足各种约束条件的传输路 径。其中有两个基本问题：最优化问题和性能界约束问题。最优化问 题是寻找对应于q o s 度量的最优路径；而性能界约束问题则是寻找大 于q o s 度量或小于q o s 度量的路径，即在满足性能界要求的集合中选 择一个解【3 l 。根据这两个基本问题，q o s 约束可分为时延约束、时延 抖动约束、带宽约束、代价约束等等。下面将根据各种约束条件对基 于0 0 s 约束的多播路由算法的研究现状进行介绍。 1 2 1 单约束多播路由 最短路径树( s h o n e s tp a t ht r e e ，s p r ) 是使多播树上从源节点到 3 北京交遥大学硕士学位论文 目的节点的每条路径上链路权重之和最小，其算法可用来解决树约束 问题；最小代价树( 即s t c i n e r 树) 是使多播树上所有链路的代价总和 最小，其算法可用来解决树最优化问题。 对于s p t 的构造算法，人们在d i i k s 昀算法基础上不断进行改进， 到目前为止，构造s p t 的快速算法的时间复杂度为o 忙佃岫卵) ( 其中n 表示图中节点数目，e 表示图中边的数目一。采用图的链式存储结构， 利用f i b o a c c i 堆构造待发展节点集，就可以在d 0 栅，o i 即) 时间内构造 s p t 。当网络变得足够大时，从源节点到一些目的节点的最短路径常 常不止一条，因而由此构成的s p t 也就不是唯一的，在众多的s p t 中每棵树的总代价也不尽相同。 文献 5 提出目的驱动最短路径树算法d d s p ，它采用d i j k s t m 算 法路径递增的基本思想，并结合d d m c 算法中目的节点共享路径的 方法，来降低所构造s p t 的总代价。文献 6 在d d s p 算法的基础上 通过改进节点的搜索过程，提出了一种快速算法f l s p t ，该算法的时 间复杂度比d d s p 算法更低而且所构造的多播树性能相同。文献 7 同样改进搜索过程，但生成的最小代价树总代价比d d s p 要小。文献 8 提出一种动态算法s b p t ，同样通过目的节点之间共享路径来降低 所构造的s p t 的总代价。该算法添加一个新目的节点的时间复杂度为 。研2 ) ，构造包含小个目的节点的s p t 的时间复杂度为。铆h 2 ) ，时间 复杂度较高而不适合大型网络求解。 基于s l e 抽e r 树的问题致力于使多播树的总代价最小，并且已知是 n p 完全问题，不可能获得多项式时间算法，在可接受的时间内只能 计算得到一棵近似的s t c i n 盯树。针对该问题人们提出了许多求近似最 优解的启发式算法。m p h l 9 j 、k m b 【1 0 1 等算法提供了较好的近似最优解， 4 绪论 但时间复杂度都较高而难于应用于实际路由协议。m p h 是大家讨论较 多的算法，通常把m p h 作为比较s t e i n e r 树算法的一种标准算法。文 献 1 1 在m p h 算法基础上改进，提出局部搜索算法l s m p h ，通过牺 牲多播树性能来提商效率，虽然时间复杂度没有改变但计算效率有一 定提高。文献 1 2 提出的快速算法f m p h ，通过改进m p h 算法的搜 索过程，以增加较少的存储空间为代价，使得时间复杂度降低，而且 其多播树性能与m p h 算法相同。d d m c 算法f 1 3 l 通过使目的节点之问 尽可能共享路径来降低多播树的总代价，其平均性能较m s t h 算法有 较大改进，但仍不如m p h 算法。m a m 算、法【1 4 】在d d m c 算法基础上 进行改进，通过扩大搜索范围，使所构造的多播树总代价比d d m c 更低。 1 2 2 时延和时延抖动多播路由 时延约束是指源节点到每个目的节点的传送时延要在约束范围 内；时延抖动约束是指源节点到每个目的节点的传送时延的差值要在 约束范围内。 k | o m p e l l a 等人于1 9 9 3 年首次提出了一种满足给定端到端时延约束 的多播路由算法【圳，并证明此类问题是n p 完全问题。该算法存在时间 复杂度大和准确度低等问题。b s m a 【1 6 】算法则采用一个切实可行的搜 索优化方法，由最短路径树开始，通过替换树中代价较高的边，迭代 改进时延约束多播树的总代价。上两个算法均有很好的性能，但因时 间复杂度过高而很难应用于实际路由协议。d 埘r 【1 7 j 算法在m c l m 【1 4 j 算法的基础上进行扩展，在构造s t e i n e f 树的过程中，拒绝违反时延限 制的最小代价路径，而选择满足时延限制但可能不是最小代价的路 5 北京交通大学硕士学位论文 径，其生成树的代价接近b s m a 算法产生的多播树，但时间复杂度远 低于b s m a 算法。 g 理en r o u s k 船在1 9 9 7 年首次提出了满足端到端时延及时延抖 动约束的多播路由问题，并提出了一种有效的集中式算法d v m a 【埘。 该算法返回的多播树时延抖动很小，但时闻复杂度很高，为0 枷矿) ， 且代价性能不是很好。文献 1 9 针对d 、礓l 算法的高复杂度，提出一 种快速有效的启发式算法d d v c a 。该算法主要基于共享树中核心路 由器的概念和最小代价路径算法，快速有效地找到满足时延约束和最 小时延抖动的多播树。文献 2 0 中把时延及时延抖动约束的多播路由 问题提升到优化的层次上，证明时延及时延抖动约束的最小代价多播 路出问题是n p 完全问题，继而提出了一种基于动态罚函数法的启发式 遗传算法以求解该问题。文献 2 1 则在d v m a 算法的基础上进行简化 提出s p d v m a 算法，算法的时延抖动比d 、偶i a 算法有所增大，但时 间复杂度比d v m a 有较大降低。 文献 2 2 提出了一种分布式的满足时延及时延抖动的s t e i n e r 树算 法，通过在构造过程中协调时延及时延抖动之间的关系，最终使得每 条路径在满足时延约束的同时，也尽量保证彼此之间的时延抖动最 小。文献e 2 3 提出了d v d m r 算法，通过计算已添加路径的平均时延， 要求所加入的每一条新路径均最接近当前平均时延。随着平均时延的 不断改变，算法最终可以得到时延抖动最小的多播树。文献 2 4 提出 一个关于“多播可达”的限定条件和一个新的最佳链路选择函数，并 以此选择函数为基础提出了一个新的启发式算法d 啪m r a ，用来构 造同时满足时延及时延抖动约束的s t e i n e r 树。文献【2 5 提出了一种改 进的神经网络模型来解决时延约束的多播路由问题。该算法能快速找 6 绪论 到一条可行路由，然而它不能克服易于陷入局部最小的缺陷。文献 2 6 基于最小代价树算法，通过动态修改节点之间的时延，可以快速的获 得满足时延约束的最小代价树，其时间复杂度很小。文献 2 7 提出了 一种动态的启发式算法，该算法可以根据网络节点的加入或退出请求 来更掰多播树，并且充分考虑了路径时延对多播树总代价的影响，获 得多播树性能较好。 1 2 3 有带宽约束的多播路由 文献 2 8 研讨了具有时延和带宽约束的q o s 多播路由问题，提出 了一种具有时延及带宽约束的多播路由算法m r d b c 。该算法通过分 布式方法搜索到多条可行的路径树枝，选择最优( 或近优) 的一条将 新成员连接到多播树上。算法避免了以往算法中大部分的盲目路径搜 索，仅要求网络的局部状态信息，而不要求维护网络的全局状态信息， 同时算法中多播组成员可以动态的加入或退出。文献 2 9 采用从理论 上保证能够收敛到全局最优解的作为邻域搜索算法扩展的模拟退火 方法，提出了一种基于模拟退火的多约束q o s 多播路由算法 s a b d m a 。该算法利用d d v c a 算法1 1 9 l 获得初始解，并在可行解范围 内构造邻域集，通过路径交换策略获得可行的邻域解，不断迭代求解， 最终获得满足约束条件的最小代价多播树。 文献 3 0 基于蚁群系统的自组织能力，提出了一个分布式的动态 q o s 多播路由的算法，即a c s 算法。在该算法中，蚁群从多播组的目 的节点出发进行搜索，将每次迭代选中的符合q o s 约束且具有最小代 价的路径加入到多播树中，多播树分布式地被构造。文献 3 1 提出了 一种基于神经网络和遗传算法的新颖的q o s 多播路由算法，该算法把 7 北京交通大学硕士学位论文 神经网络和遗传算法结合起来，并给出了一种便于进行交叉、变异等 遗传操作的新编码方式，从而克服传统遗传算法中存在的早熟现象， 加快收敛速度。文献 3 2 把b o a 算法中的贝叶斯网络模型结合到强 度p a r e t o 进化算法i i 中，通过构造和学习网络来替代原算法中的交叉 重组和变异等遗传操作，提出了一种能够同时优化带宽和时延等参数 的多目标o o s 多播路由算法。该算法可在不做预处理的情况下把每个 q o s 参数分别作为一个独立的优化目标进行同时优化，能够快速收敛。 1 2 4 有度约束的多播路由 在上述的多播树构造算法中，都假设每个节点可以将信息进行拷 贝并向与其邻接的所有节点发送信息，但实际网络中并非所有节点都 具备多播能力，或者节点的多播能力受限。例如，在现有的网络中， 许多节点不支持多播：同时节点复制信息的数日必然影响节点处理信 息的速度，为保证照个网络的传输速度以及节点的负载平衡，每个节 点的多播能力应有所限制；加之每个节点的存储和处理信息的能力不 同，每个节点只能向与其邻接的其中几个节点传输信息。给每个节点 指定度约束来表示节点的多播能力，解决此类问题称为求解带度约束 的s t e j n e r 树。 b a u e r 等人于1 9 9 5 年提出的s p h 算法【3 3 l 是目前求解带度约束的 多播路由问题中性能较好的s t c i n e r 树。其基本思想是：从只包括源节 点的予图开始，寻找与之距离最近且不违反度约束的一个目的节点， 用最短路径将两节点相连，同时将最短路径上的节点也加入图中，然 后再找下一个与子图距离最近的不违反度约束的目的节点，将其加 入，如此直到所有目的节点全部加入到树中。文献【3 4 】则在分布式带 g 绪论 时延约束的多播路由算法的基础上提出了解决带度约束的多播路由 问题的分布式算法。文献【3 5 】提出了计算机通信网中的一类新问题， 即同时带度约束和时延约束的多播路由问题，并使用l a 伊蛐g e 松弛法 来解决这类问题。 1 3 本文研究的主要内容 在多播路由算法中，可以采取不同的优化准则，第一个准则是端 到端的最小时延，这对于实时会议等多媒体应用来说是至关重要的。 另一个优化目标是尽可能有效的利用网络资源，使网络的代价达到最 小。这个目标对应于两个参量：最小化链路拥塞，最大化利用链路带 宽。一般采用最小化网络代价柬度量网络资源的使用。因此，对具有 端到端时延约束的最小代价树问题进行研究具有非常重要的意义。根 据上节所述，在网络中寻找覆盖多播组成员节点的时延约束最小代价 多播树，是一个n p 完全问题。一般地，n p 完全问题的最优算法无法 在多项式时间内完成，因此，需要寻求有效的启发式算法，降低算法 难度，而从性能上逼近理论算法。此外，目前对多播路由算法的研究 偏重于静态多播算法，动态多播算法相对很少，而实际网络中节点动 态变化的情况是静态算法所不能适应的，需要动态算法加以解决。 本文对以上提出的问题进行了研究，文章首先对0 0 s 多播路由问 题的研究背景和研究现状进行介绍，然后介绍了q o s 多播路由问题的 模型、度量、分类等方面，随后针对时延约束多播路由问题，在已有 的最小代价树算法的基础上给出一种用于时延约束的改进算法，又针 对动态多播路由问题，提出了一种新的满足时延约束的动态多播路由 算法。 9 本文内容安排如下： 第一章简要介绍了o o s 多播路由的研究意义，包括多播路由的研 究背景和发展情况，并对基于q o s 的多播路由算法的研究现状进行了 研究。 第二章介绍了多播路由的一些基础知识，包括0 0 s 多播路由的网 络模型和度量、q o s 多播路由问题的分类以及多播路由树的分类，并 介绍了几个相关的基本算法，它们是其后大多数算法的基础，也是同 类算法分析比较的标准。 第三章首先对时延约束最小代价多播路出问题进行讨论，介绍分 析了一些启发式算法，然后以快速最小代价多播树算法为基础，给出 一种用于时延约束的多播树算法，该算法通过对节点之间的时延进行 动态修改，寻找满足时延限制的最小代价路径，可快速找到满足时延 约束的多播树。 第四章介绍了多播路出中的动态问题，对动态算法进行了介绍分 析，并提出了一种新算法。该算法充分考虑路径时延对多播树总代价 的影响，利用前七条最短路径方法和路径选择函数来生成多播树。算 法可以在满足时延约束的情况下，快速地找到性能较好的多播树，同 时可以根据网络节点的加入或退出请求来更新多播树，实现对多播树 的动态维护。 最后总结全文并展望了进一步的工作。 基于o o s 的多播路由理论介绍 2 基于q o s 的多播路由理论介绍 本章主要介绍q o s 多播路由问题度量及模型，q o s 多播路由问题 的分类，多播路由树的分类，并对几个基本算法进行研究与分析。 2 1 q o s 多播路由问题模型及度量 在分析q o s 路由问题之前，有必要先建立基于q o s 约束的多播 路由网络模型，了解度量的特性及其合成规则。 2 1 1 q o s 多播路由度量 度量在o o s 多播路由问题中起着重要的作用，它不仅定义网络可 以支持的服务质量类型，也定义应用的服务质量请求范围，并且还可 以反映网络的基本特征【3 6 】。通信信息的o o s 请求是通过单度量或组合 度量来量化和提出的，如果信息的q o s 请求不能映射为单度量或组合 度量，那么网络就不能支持该信息的q o s 请求。假设路径 p = ( a ，b ，c ，0 ，k ) ，用m ( a ，b ) 表示对应链路( a ，b ) 的度量，则q o s 路由度量 可分为如下三类： 1 ) 加性度量：m ( p ) = m ( 咖) + m ( b ，c ) + + m a ，k ) 路径的加性度量状态是由该路径上所有链路的特性共同决定的。 加性度量包括时延、时延抖动、代价、端到端路由跳数等。 2 ) 乘性度量：m ( p ) = m ( a ，b ) + m ( b ，c ) m ( i ，k ) 路径上的乘性度量为该路径上所有链路对应度量的乘积。乘性度 量包括连接可靠性( 即成功传输率：1 丢包率) 等。 3 ) 凹性度量：m ( p ) = m i l l ( m ( a ，b ) ，m ( b ，c ) ，m ( j ，k ) ) 北京交通大学硕士学位论文 路径上的凹性度量状态是由传输链路中的瓶颈链路的状态所决 定的。也就是说，一条路径上的某个凹性度量取决于该路径上所有链 路对应于该度量的值中的最小值。凹性度量包括最常用的剩余带宽、 剩余缓存空间和链路速率等。此类度量只与路径上的某个瓶颈链路的 q o s 度量有关。 路由度量还可分为路径约束度量和链路约束度量。由于一条路 径的凹性度量依赖于该路径上瓶颈链路的值，所以凹性度量是链路约 束度量；而路径的加性度量或乘性度量依赖于该路径上的所有链路的 值，所以加性或乘性度量是路径约束度量。这里，各度量之间是不可 互相替代的。例如，在q o s 多播路由算法中，代价常被作为主要的度 量，如著名的s t c i n c r 树问题，但是具有加性的代价度量并不能体现路 径带宽的凹性，即路径的带宽应是路径中所有链路中带宽的最小值。 在具体的设计多播算法的过程中，要根据网络的实际情况和应用 的需求来解决闯题，对算法考虑所有度量的做法是不切实际的。例如， 对于实时传输的多播应用，时延是必须保证的条件，代价则是评价网 络使用效率的标准，都要纳入考虑的范围。而时延抖动、丢包率等可 以不加考虑。 2 1 2 q o s 多播路由模型 设网络用加权无向图g = ( ne ) 来表示，其中y 是网络中所有 节点的集合，每个节点表示主机或路由器；e 为圈g 中边的集合，每 条边为连接网络节点的通信链路，链路上的参数代表链路的当前状 态。用l 川表示网络中的节点数，霉l 表示网络中的链路数。5 为源节 点，d = 纰如如蚶，d c 矿是一个目标节点集，即多播组，m 为多 基于o o s 的多播路由理论介绍 播组中节点的个数。r + 表示正实数集。链路代价函数为c 够：e n ， 时延函数为d ( d ：e r + ) ，时延抖动函数为，：e 确+ ) ，带宽函数为 b 但：e 咖+ ) ；包丢失率函数为：l 仁：v 只+ ) ；设有路径p 仁， 一= n 嘻叫，( n 为距，场为v ) ，表示从节点到节点y 的一条路 径。f 是一个约束集，包括端到端时延，端到端时延抖动、路径带宽、 成功传输率等。 则对于给定的源节点s v ，目标节点集d ，s 和d 组成的多播树 t ( s ，d ) 存在下列关系： 定义1 路径p 的时延为p 上各条链路时延的和： d ( p ) = d “，) ： 定义2路径p 的代价为p 上各条链路代价的和： c ( p ) 一c “y f + 。) ； 定义3 路径p 的时延抖动为p 上各条链路时延抖动的和： ，( p ) = ，n ，) ； 定义4 路径p 的带宽为p 上各条链路带宽的最小值： 曰( p ) am i l l ( b “，b + 。) ) ： 定义5 路径p 的成功传输率为p 上各条链路成功传输率的乘积： 工( p ) 。n ( 1 一工以，u + 1 ) ) ； 定义6 多播树z 毫( 万确夏盖源节点s 和多播组d ，并且r 中每条 路径p 都能满足约束集c 中的一个或多个约柬，r 的总代价为 c 口) 。磊c o ) 。 由此，可以定义q o s 多播路由问题为：网络g d ，多播源节 北京交通大学硕士学位论文 点s 多播目的节点集d 阼扣) ，寻找一棵多播树砸j ) ) 满足时 延约束、时延抖动约束、带宽约束、成功传输率约束、代价约束等约 束中的一个或多个。 2 2q o s 多播路由问题分类 从不同的角度，基于q 0 s 的多播路由问题可以分为不同的类型。 本节将从静态与动态、启发式与智能计算、集中式与分布式等方面进 行介绍。 2 2 1动态算法与静态算法 在实际的网络通信中，q o s 多播路由可以分为静态多播路由和动 态多播路由两种。静态多播路由是针对初始多播组成员来构建多播 树，它不能根据当前实际传输量和多播组成员的变化来做路由选择， 而是按事先设计好的路由传送信息。但是真实网络中存在很多动念变 化，许多多播应用需要网络支持动态多播会话( m u l t i c 髂ts c s s i o n ) ，例 如视频会议和分布式游戏等。这类应用中，用户允许随时加入或退出 多播会话，也就是多播组的成员会频繁的改变。支持这种应用需要改 变已有的多播树来适应组成员的变化。使用静态多播路由不能适应组 成员的这种动态变更，网络资源也得不到有效利用，甚至会导致传送 错误。动态多播路由则会针对组成员的频繁变更，处理组成员加入或 离开之后多播树的更新闯题。它可以实时地选择路由，适应网络的变 化，从而更有效的利用网络资源。 1 9 8 8 年，w 觚m a l l 【卅首先提出了与多播组成员变化相关的动态多 播路由问题，即多播组的成员随时间改变所带来的多播树更新问题， 基于0 0 s 的多播路由理论介绍 动态多播路由逐渐获得人们的注意。目前动态多播路由在国外已是非 常活跃的研究领域，而国内有关这方面的文献相对来说比较少。 2 2 2 启发式算法与智能计算算法 已经证明，多q o s 约束的多播路由问题是一个n p 完全问题。此 外，网络状态信息的不精确性和不确定性对多播路由也有很大的影 响，使问题更难于处理。目前，解决该问题的一般方法是采用启发式 方法或近似算法。 启发式算法搜索的基本原理是【删：对于搜索过程中遇到的每一个 节点，按估价函数计算出它的最佳估计值，然后选出当时估计值的最 小状态节点，并从该节点开始继续搜索。从该执行过程可以看出，每 一个新节点的选择是以当时节点与新节点之间最小估计值为标准，而 不是基于整个问题的最小估计值。因此，一般只能找到局部最优解， 难以找到全局最优解。所以启发式方法有一个明显的缺点，即缺乏全 局观点。另外，启发式方法必须对所解决的问题有较深入的了解，且 复杂、难以并行实现，从而无法在大规模的网络系统中实时地找到满 意的路由。 近年来随着智能计算技术的发展，人们开始把智能计算技术引入 到多约束的多播路由问题的求解之中，如遗传算法、模糊逻辑方法、 神经网络方法等。其中，遗传算法是近几年提出的一种新型优化算法， 它具有并行搜索、自适应群体寻优以及产生一组p a r e t o 最优解集等许 多特点，已广泛应用于解决各种肿完全的问趔3 9 1 。使用遗传算法求解 科学研究和工程技术中各种组合搜索和优化计算问题的这一基本思 想，首先是由美国m i c h i g a n 大学的j h o l l a n d 教授在2 0 世纪6 0 年代初提 北京交通大学硕士学位论文 出，2 0 世纪8 0 年代中期这种思想得到了蓬勃发展。遗传算法的优点在 于其简单性、健壮性、并行性、易于实现等，适用于在复杂而庞大的 搜索空间中寻找最优解，在搜索过程中自动获取和积累有关搜索空间 的知识，自适应地控制搜索过程，不断地缩小搜索空间，从而得到优 化解，甚至最优解【3 8 1 。将遗传算法应用于q o s 多播路由选择，可以使 得q o s 路由选择方法简单、有效。但遗传算法同时也暴露出许多不足 和缺陷，针对其不足，近年来又有许多改进的方法出现，其中之一就 是将基本遗传算法与传统优化方法相结合的混合遗传算法。蚂蚁系统 和蚁群系统则是一种受自然界生物的行为启发而产生的“自然”算法。 具体的说，是对蚂蚁或蚁群的行为及其包含的自然规律的研究中产生 的。文献 3 0 中提到对遗传算法和蚁群算法蚂蚁系统在多约束q o s 多播路由问题方面的应用研究的比较，前者不能适应网络的扩展，即 不能使扩展后的网络利用其扩展前的网络信息，但后者具有可扩展 性。换句话说，当网络的节点数发生变化时，后者在求解q o s 约束的 多播路由问题时能够利用网络变化前的网络信息而不用重新搜索网 络的全部节点。 2 2 3 集中式算法与分布式算法 根据生成多播树的方式，多播路由算法可分为集中式路由和分布 式路由两种。 集中式路由算法采用了集中处理的方式，利用整个网络拓扑结构 和网络状态信息来构造整棵多播树。它需要在网络中的每个节点上都 维持一张有关整个网络状态信息的链路状态表，并且周期性的对其更 新。这种算法一般都是源路由算法( s o u r - r t e d 袱l t i i i g ) ，即源节点通 基于q o s 的多播路由理论介绍 过某个链路协议获得完整的网络拓扑信息，进行路由的计算。集中式 路由算法简单明了、易于实旌，缺点在于首先节点在确定路由之前要 收集全网拓扑信息，这样易造成链路拥塞，有一定的时延；其次节点 要定期更新拓扑信息。以保证不产生回路。 分布式路由算法是基于局部状态信息的，其特点在于多播树的计 算是由位于不同网络中的多个路由器协作完成的，不需要像集中式路 由那样为每个节点都维持一张链路状态表，从而能更好地适应网络规 模的动态变化i 柏1 。其优点如下： 1 ) 算法的执行只限于组成员节点，并不是所有网络节点都参与路 由算法； 2 ) 每个节点只用到局部信息，不需要存在一个存储有整个网络信 息的中心节点； 3 ) 算法所需的通信费用少，并且建立路由的时间短。 而分布式算法的缺点在于容易导致环的出现，且计算复杂度比较 高。 2 2 4 单约束算法与多约束算法 最优化问题和性能界约束问题是q o s 多播路由中的两种最基本的 问题【3 】。所谓最优化问题就是寻找对应于服务质量度量的最优路径， 即在所有的路径中选择对应于度量最好的。而性能界约束问题则是寻 找大于对应服务质量度量( 如带宽) 或小于对应服务质量度量( 如时 延抖动) 的路径，即在满足性能界要求的集合中选择一个解。优化问 题要求最优解，磷约束阔题贝l j 要求解满足要求即可。将这两类问题加 以细分，就得到各种约束问题，下面将根据单约束与多约束分别加以 1 7 北京交通大学硕士学位论文 讨论1 3 ，蚓。 根据单约束条件，q o s 多播路由问题基本上可分为：( 1 ) 链路约 束问题；( 2 ) 树约束问题；( 3 ) 链路最优化问题；( 4 ) 树最优化问题。 ( 1 ) 链路约束问题 所谓链路约束就是对于某种度量，寻找使得其上所有链路的对应 度量都能满足约束条件的路径。链路约束是属于凹性约束的，对于此 类问题可通过从网络拓扑图中删去不合约束要求的链路的方法来解 决。 例如带宽度量链路约束，寻找的路径的瓶颈带宽要超过约束值。 解决该问题的一种方法是把链路约束路由问题简化为链路最优路由 问题，即先寻找瓶颈带宽最大的路径，再检查其是否能满足约束条件。 如果网络中确实存在满足约束条件的路径，那么最优路径一定能满足 约束。另一种方法是拓扑剪枝，即删除带宽小于约束条件的链路，然 后从剪枝后的拓扑图中寻找路径，这样，就能找到一条满足链路约束 度量请求，但不必是最优的链路约束路由。 ( 2 ) 树约束问题 所谓树约束就是指对于某种度量，寻找一棵多播树使得该树上的 每一条路径对应的度量都能满足约束条件。树约束是属于加性约束 的，此类问题可在多项式时间内求解。 例如求具有时延约束的多播树。这是树约束路由问题的一个典型 的例子，即寻找一棵多播树，树上每条路径的时延都被限定在一个要 求值内。该问题可以直接用d j j k s t m 算法或b d l l n a n - f 0 r d 算法来解决， 为约束度量的q o s 请求找到的每一条路径都会小于时延要求。 基于q 0 s 的多播路由理论介绍 ( 3 ) 链路最优化问题 所谓链路最优化就是对于某种度量，寻找所对应的度量在所有找 到的路径中为最优的路径。链路最优化问题也是凹性约束的，对此可 提出来多项式复杂度的方法求解。 例如带宽最优路由，寻找在瓶颈链路上有最大可用带宽的路径。 链路最优化问题可以通过改进d i j k s t r a 算法或b c l l m a n f o r d 算法来解 决。在标准的d 独s 仃a 算法中，选择下一个节点是根据累积的函数值， 把到已有树函数值最小的节点加入到路由树上。可阻修改d i i k s t r a 算法 标准来解决链路最优化路由问题，也就是比较各个节点连接到已有树 的带宽，选择带宽最大的节点加入到树上。 ( 4 ) 树最优化问题 树最优化就是对应于某种度