（计算机应用技术专业论文）基于遗传算法的qos组播路由算法的研究与实现.pdf

东北大学硕士学位论文摘要 基于遗传算法的q o s 组播路由算法的研究与实现 摘要 随着网络技术的飞速发展，各种实时和多媒体业务得到了越来越广泛的应用。一方 面，这些业务大多采用组播来降低网络负载，提高网络资源的利用率；另一方面，这些 业务都是一些实时性很强的业务，需要提供q o s 保障。 在满足q o s 的条件下，寻找将分组发送到一个组播组中所有成员的路径的过程称为 q o s 组播路由。研究表明，q o s 组播路由问题是一个n p 完全问题，这使得它与传统的 路由过程不同，难以用经典的最短路径优先算法求解。以前，许多研究都集中在采用启 发式算法来求解该问题，然而由于这些算法都具有较高的时间复杂度而不能满足实际应 用的需要。 本文采用基于遗传算法的q o s 组播路由算法来求解该问题。遗传算法是一种新型的 优化算法，已经广泛应用于解决各种具有n p 难度的问题。本算法通过改进遗传算法的 结构，使其避免陷入局部极值的能力大大增强；采用树型结构编码策略，既减少了编码 空间，又省略了解码操作；采用多点交叉，提高了交叉策略的性能；对强成长的个体进 行变异操作，即能让多个个体进行局部搜索，形成多点爬山，不仅避免了陷入局部最优， 而且加快了收敛速度。 本文重点讨论使用遗传算法解决q o s 组播路由问题。首先介绍组播的概念，现存的 组播路由算法和主要的组播路由协议；其次介绍q o s 组播概念，并提出q o s 组播路由 的数学模型；然后在分析相关启发式算法和遗传算法的基础上，提出一种基于遗传算法 的q o s 组播路由算法，并通过c 语言实现；最后，通过实例对该算法的可行性和有效 性进行验证。 关键词：组播；组播路由；q o s 遗传算法 一一 东北大学硕士学位论文 a b s t r a e t r e s e a r c ha n di m p l e m e n t a t i o no fg a - b a s e dq o sm u l t i c a s t r o u t i n ga l g o r i t h m a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h en e t w o r kt e c h n o l o g y , m o r ea n dm o r er e a l t i m e m u l t i m e d i aa p p l i c a t i o nc o m e si n t ob e i n gi nt h ei n t e m e t o nt h eo n eh a n d ，t h e s en e ws e r v i c e s r e q u i r et h es u p p o r to fm u l t i c a s tc o m m u n i c a t i o nt or e d u c et h et r a f f i ci nt h en e t w o r k o nt h e o t h e rh a n d ，t h e r em u s tb eaq o s ( q u a l i t yo fs e r v i c e ) g u a r a n t e e dm e c h a n i s mf o rt h e s e r e a l - t i m es e r v i c e s 1 1 1 eq o sm u l t i c a s tr o u t i n gi ss e a r c h i n gt h ep a t h sf o rt r a n s m i s s i o np a c k e t st oa l lm e m b e r s i nam u l t i c a s t g r o u pw i t hq o sc o n s t r a i n e d e s t a b l i s h i n gs u c h m u l t i c a s tr o u t i n gi sa n p - c o m p l e t ei s s u ew h i c hc a nn o tb es o l v e db yt h ec l a s s i c a ls h o r t e s tp a t hf i r s ta l g o r i t h m t h u s ，m o s tp r e v i o u sr e s e a r c h e r sh a v ef o c u s e do nd e v e l o p i n gh e u r i s t i ca l g o r i t h m s h o w e v e r , t h e s eh e u r i s t i ca l g o r i t h m sh a v eh i g hc o m p u t a t i o nc o m p l e x i t y , s ot h e yc a l ln o tm e e tt h e d e m a n do f p r a c t i c a l i t y t h i st h e s i sf o c u s e so nt h ea l g o r i t h m st oc o n s l r u c tm u l t i c a s tr o u t i n gt r e ew i t hq o s r e q u i r e m e n t s aq o sm u l t i c a s tr o u t i n ga l g o r i t h mb a s e do ng e n e t i ca l g o r i t h mi sp r e s e n t e d ，i n w h i c ht h eg as t r u c t u r ei sm o d i f i e di no r d e rn o tt ot r a pi nl o c a lo p t i m i z a t i o n ，t r e e - c o d i n g s c h e m eb yw h i c ha n yd a t as t m c t u r eo ft h et r e ec a nd e s c r i b et h ec h r o m o s o m es t r u c t u r ej s a d o p t e d t oo m i t st h ec o d i n ga n dd e c o d i n gp r o c e s s ，t h em u l t i - p o i n tc r o s s o v e fc a r ti m p r o v et h e t h ep e r f o r m a n c eo ft h ec r o s s o v e ro p e r a t i o n ，t h em u t a t i o no p e r a t i o nf o rt h es t r o n g d e v e l o p i n g i n d i v i d u a l sc a na c h i e v et h ef a s tc o n v e r g e n c ea n da v o i dl o c a lo p t i m i z a t i o nb ym e a l s e a r c ho f m o r ei n d i v i d u a l s n 蝣t h e s i sm a i n l yd i s c u s s e st h eq o sm u l t i c a s tr o u t i n gb a s e do ng a f i r s t , t h e c o n c e p t i o n , a l g o r i t h m ，p r o t o c o la n dt h em o d e lo fq o sm u l t i c a s tr o u t i n ga r ei n t r o d u c e d ，t h e c o r r e l a t i v eh e u r i s t i c a l g o r i t h m sa n dg aa r ed i s c u s s e d t h e n ，aq o sm u l t i c a s tr o u t i n g a l g o r i t h mb a s e do ng a i sp r o p o s e da n di m p l e m e n t e db yt u r b oc a tl a s t ，t h ef e a s i b i l i t yo f t h i s a l g o r i t h mi si l l u s t r a t e db ys i m u l a t i o n k e y w o r d s ：m u l t i c a s t ；m u l t i c a s tr o u t i n g ；q o s ；g e n e t i ca l g o r i t h m 一i 一 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名：舒曩守 签字e t 期：2 。印辱j 闩2 0 日 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 一研荷铷签名：勘7 签字日期渊绷曰签字日靴唧，厶 东北大学硕士学位论文第一章绪论 第一章绪论弟一早三百t 匕 本章主要对课题的来源、产生背景、国内外现状以及存在问题加以描述，最后介绍 本文的内容安排。 1 1 课题的来源与背景 随着网络技术的飞速发展，许多诸如视频会议、推送技术、大规模协作计算、为用 户群进行软件升级，网络代理、镜像和高速缓存站点等多媒体应用，都依赖于从一个主 机向多个主机或者从多个主机向多个主机发送同一信息的能力，而在i n t e m e t 上分发信 息的主机的数目可能达数十万台，发送信息需要更高的带宽，并且大大的超出了单播的 能力，因而需要一种最大限度的利用现有带宽的技术p 组播技术。 i p 组播作为一种新技术，其研究领域非常广泛，主要包括组播路由算法和协议、可 靠组播、安全组播、基于主机的组播以及组播应用等。传统i n t e r a c t 主要用于数据通讯， i p 分组的传输采用尽力而为( b e s t e f f o r t ) 的模式。在这种单一的服务模式下，用户只对传 输的可靠性有严格的要求，而对延时和延时抖动的要求比较宽松。然而，随着宽带网络 技术的发展而出现的各种实时和多媒体业务往往都对延时和延时抖动等网络参数提出 了比较严格的要求，并且这些业务大多采用组播来提高对网络资源的利用率。而目前的 各种组播路由协议都是基于b e s t e f f o r t 服务模式的。也就是说，这些路由协议在进行路 由选择时都没有考虑业务所需要的q o s 约束。因此，如何解决带q o s 约束的组播路由 问题已经成为多媒体信息传输的一项关键技术。 由于q o s 请求带有多个约束条件，包括：带宽、延时、延时抖动和丢包率。而这种 多约束条件下的组播路由问题是n p 完全问题。对这类问题，传统的路由算法都难以求 解，采用启发式算法的效率不高，特别是在网络节点和链路数量增加的时候，其算法的 时间代价会急剧增加。 近代科学技术发展的特点之一是生命科学与工程科学的相互交叉、相互渗透和相互 促进。，遗传算法( g e n e t i c a l g o r i t h m s ，g a ) 的发展正体现了科学发展的这一特征和趋势。 由于遗传算法的整体搜索策略和优化计算是不依赖于梯度信息，所以它的应用范围非常 广泛，尤其适合于处理传统搜索方法难以解决的高度复杂的非线性问题。路由选择实际 上是一个优化问题，传统的启发式算法难以求解并且计算复杂度高，适合使用遗传算法 来求解。 一卜一 东北大学硕士学位论文 第一章绪论 1 2 组播概述 组播技术是t c p i p 传送方式的一种，t c p i p 有三种传输方式：单播、组播、广播。 传统的i p 通信是在一个源口主机和一个目标i p 主机之间( 单播) 或者一个源i p 主机和网 络中所有的口主机之间( 广播) 进行的。要将信息发送给网络中的多个而非所有口主机， 采用传统的妒通信技术只有两种方法可以选择：采用广播方式或者采用单播方式由源 i p 主机分别向网络中的多个目标口主机单播发送口包。广播方式会将信息发送给不需 要的i p 主机而浪费带宽，而且可能的路由回环会引起广播风暴。单播方式由于i p 包的 重复发送会浪费掉大量带宽，同时也增加了服务器的负载。可见，传统的p 技术不能 有效地解决单点发送多点接收的问题，而i p 组播却很好的解决了这个问题。 i p 组播是指在口网络中数据包以尽力而为传送的形式发送到所有网络节点的某个 确定子集，这个子集称为组播组。i p 组播的基本思想是源m 主机只发送一份数据，然 后经过路由器或交换机拷贝发送数据到一个或多个接收者。即允许源伊主机向网络上 所有主机的一部分( 子集) 发送i p 分组，只有该子集内的主机( 目标主机) 可以接收该分组， 而网络中其他i p 主机不能收到该分组。这种逻辑上的子集就是组播组，用d 类i p 地址 ( 2 4 4 0 0 0 - - 2 3 9 2 5 5 2 5 5 2 5 5 ) 来标识。i p 组播技术有效地解决了业务中的单点发送多点接 收，多点发送多点接收的问题，实现了p 网络中点到多点高效数据传输，有效地节约 了带宽，降低了网络负载。 伊组播路由网络克服了利用单播通信模型传递组播信息带来的带宽瓶颈，减少了发 送相同数据到多个接收者的通信费用，节省了网络带宽和资源，时延小，具有可升级性。 但在提高带宽利用率的同时，还需要考虑服务质量的其他方面，如吞吐量、延迟、抖动、 丢包率等，才能更好地满足多媒体业务的需要。 1 3 遗传算法概述 遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，它将生物 进化原理与计算机科学结合起来，开辟了一个全新的领域，在6 0 年代初期由美国密歇 根大学的j h o l l a n d 教授。1 提出。其主要特点是群体搜索策略和群体中个体之间的信息 交换，搜索不依赖于梯度信息。它的应用范围非常广泛，尤其适用于处理传统搜索方法 难于解决的复杂和非线性问题，在组合优化、自适应控制、模式识别、机器学习、规划 策略、信息处理和人工生命等领域的应用中展示出优越性和魅力，是2 1 世纪有关智能 计算的关键技术之一嘲。遗传算法的基本思想来源于遗传进化，主要是借助于生物进化 一2 一 彖北大学硕士学位论文第一章绪论 机制与遗传学原理，按照自然选择和适者生存的原则，利用简单的编码技术和繁殖机制， 模拟自然界生物群体优胜劣汰的进化过程，实现对复杂问题的求解。应用遗传算法进行 问题求解时要解决三个方面的问题，即：首先将待研究问题的解用某种编码方式( 如二 进制编码等) 表示成染色体，并随机生成初始群体，然后是适应度函数的设计，即以群 体中个体的适应度函数值为依据，淘汰部分后代，值高的染色体被选中的概率高，最后 是对个体执行选择、交叉和变异三种基本遗传算子操作以及控制参数的设定，使群体中 的个体不断进化并逐渐逼近问题的最优解。 遗传算法与传统的算法具有很多不同之处，但是主要的特点表现在下述几个方面： ( 1 ) 智能性：遗传算法的智能性包括自组织、自适应和自学习等方面。应用遗传算 法计算求解问题时，在确定了编码方案、适应度函数及遗传算子以后，算法将利用计算 过程中获得的信息自行组织搜索。 ( 2 ) 本质并行性：遗传算法的本质并行性表现在两个方面，一是遗传算法是内在并 行的，可以让多台计算机各自进行独立种群的计算，等到运算结束时才进行比较，选取 最佳个体。二是遗传算法的内涵并行性，由于遗传算法采用种群的方式组织搜索，从而 它可以同时搜索解空间的多个区域，并相互交流信息，这使得遗传算法能够以较小的计 算获得较大的收益。 ( 3 ) 过程性：遗传算法通过自然选择和遗传操作等自组织行为来增强群体的适应性， 算法模拟的是一个过程，算法的实施也是一个过程。在这个过程中，算法本身无法判定 个体处在解空间的位置，因此需要人为干预才能终止。 t ( 4 ) 多解性：遗传算法是采用群体的方式组织搜索。它从多个点出发，通过这些点 的内部结构的调整和重组来形成新的点。因而每次都将提供多个近似解，这对多目标搜 索或有需要多个近似解作为参照的情况下是非常有用的。 ( 5 ) 不确定性：遗传算法的不确定性是伴随其随机性而来的。遗传算法的主要步骤 都含有随机因素。从而在算法的演化过程中，事件的发生与否带有很大的不确定性。 ( 6 ) 非定向性：自然选择和生物繁殖这种非定向机制是遗传算法的关键。它没有确 定的迭代方程也不依靠梯度下降法似的爬山策略，而是用调整群体的内部结构的方法来 增强其对环境的适应度，以使问题得到解决。 ( 7 ) 整体优化：传统的优化方法，一般采用的是梯度下降的爬山策略，从而使得多 峰函数的情形容易陷入局部最优。而遗传算法能同时在解空间的多个区域内进行搜索， 并且能以较大的概率跳出局部最优，找出整体最优。 一3 一 东北大学硕士学位论文 第一章绪论 1 4 国内外现状及存在问题 多约束条件下的组播路由问题是n p 完全问题“1 ，对这类问题，采用传统的路由算 法难以求解，这就使得它成为宽带礤技术的一个难点。有不少学者对这个问题进行了 深入研究，但是许多研究都集中在采用启发式的搜索算法来求解一棵完全满足q o s 约束 的组播树阳】。 、( 1 ) k o m p e l l a 等人“提出了带时延约束的组播路由问题，并且给出了相应的算法 ( k p p 算法1 ，同时将其推广到分布式环境，但是此算法的时间复杂度相当高，而且在分 布式环境下易于阻塞。 ( 2 ) s u n 等人m 提出c d k s 算法，该算法通过一个合并过程来保证试验的要求，它的 复杂度不高，并且得到的组播树费用较小，仅次于k p p 算法和b s m a 算法，综合性能 较好，但是由于存在合并的过程，使其难于在分布式环境下部署。 ( 3 ) g e r o g e 等人嘲提出了带时延约束及时延抖动约束的算法，但该算法并没有考虑 对代价的优化，而且其复杂度也相当高。 由于启发式算法存在效率不高，特别是随着网络节点和链路数量的增加，其时间复 杂度也随之急剧增加，近年来一些学者采用遗传算法来解决此问题。 ( 1 ) r a v i k u m a r 等人“2 1 针对延时约束费用最小的组搔路由闯题，提出了一种遗传算 法，但该算法容易陷入未成熟收敛，而且文中也没有提出任何措施来抑制算法未成熟收 敛现象，算法的精度不好。 ( 2 ) 何小燕等人“”提出一种通用的遗传算法，但是这个算法采用n x n 的一维二迸制 编码机制( n 为网路节点数) ，这种编码模式使得算法编码和解码过程复杂，并且算法的 搜索空间随着网路规模的增大而急剧增大，算法效率不高。 ( 3 ) s u n 等人“”对e s b e n s e n 等人“”提出的算法进行了扩展，提出一种求解延时约束 费用最小的组播问题的遗传算法，但是在其解码过程需要解决另一个n p 完全问题( 一种 确定性的时延约束费用最小组播路由算法) ，大大提高了算法的复杂度，而且它假定所 有组播终点的延时相同，这也大大限制了算法的应用范围。 以上算法的主要问题在于没有针对问题的特点来进行编码，导致编码和解码过程复 杂，大大提高了算法的复杂度；算法出现早熟现象，影响算法的精度。 针对以上问题，本文提出一种基于遗传算法的q o s 组播路由算法，该算法改进遗传 算法的结构，使其避免陷入局部极值的能力大大增强；采用树型结构编码策略，既减少 了编码空间，又省略了解码操作；采用多点交叉，提高了交叉策略的性能：对强成长个 4 东北大学硕士学位论文第一章绪论 体进行变异操作，能让多个个体进行局部搜索，形成多点爬山，不仅避免了陷入局部最 优，而且加快了收效速度。 1 5 本论文的内容安排 本文的内容安排如下： 第一章绪论，本章主要对课题的来源、产生背景、国内外现状以及存在问题加以描 述，并介绍了本文所作的主要工作和本文的内容安排。 第二章o o s 组播路由，本章主要对组播技术所涉及的基础理论加以综述，包括组播 路由技术，组播路由算法，组播路由协议，带q o s 约束的组播路由模型等问题。 第三章基于遗传算法的q o s 组播路由算法，本章首先介绍并分析现存的一些关于求 解q o s 组播路由问题的启发式算法和遗传算法，在此基础上提出了一种新的基于遗传算 法的q o s 组播路由算法。 第四章仿真软件的设计，本章主要介绍了网络拓扑的存储、相关数据结构，以及主 要的功能模块。 第五章仿真实验，本章主要对本文提出的算法进行了仿真实验和性能分析，并与一 些目前性能较优的算法进行了比较。 。 第六章结论，总结全文，提出需要改进的问题并给出解决办法。 一) 一 东北大学硕士擘住论文第二章q o s 组播路由 第二章q o s 组播路由 标准i n t e m e t 协议的网络提供尽力而为( b e s t - e f f o r t ) 的数据传输。当越来越多的主机 连入到i n t e m e t 时候，对网络服务的需求也就超过了网络的承载能力，由此产生网络性 能的逐渐恶化，进而造成传输延时的变化( 抖动) ，甚至引起分组丢失，这就给对传输延 时对有实时要求的应用( 例如：传送多媒体信息) 带来了问题。 为了提供能够满足要求的服务，必须制订有关服务质量水平的规定，来区分具有严 格延时要求的业务和能容忍延时、抖动和分组丢失的业务。这就是服务质量( q o s ) “州”3 。 q o s 的目标是要提供一些可预测性的质量级别，以及控制超过目前m 网络最大服务能 力的服务。 本章对q o s 组播技术所涉及的基础理论加以综述，包括组播路由技术，组播路由算 法，组播路由协议，带q o s 约束的组播路由模型等问题。 2 1 组播路由技术 2 1 1i n t e m e t 组播模型 i p 组播是指一个m 报文向一个“主机组”的传送，这个包含零个或多个主机的主 机组由一个单独的m 地址标识。主机组地址也称为“组播地址”，或者d 类地址。除了 目的地址部分，组播报文与普通报文没有区别，网络尽力传送组播报文但是并不保证一 定送达。 主机组的成员可以动态变化，主机有权选择加入或者退出某个主机组。主机可以加 入多个主机组，也可以向自己没有加入的主机组发送数据。主机组有两种：永久组和临 时组。永久组的m 地址是固定的，由i n t e m e t 管理机构分配，是保留地址。临时组的地 址则使用除永久组地址外的非保留d 类地址。网络上传输组播数据报时是通过组播路由 器进行的，组播路由器可以和网关一起，也可以和网关分离。主机在传输坤组播数据 报时将它作为本地网络组播进行，本地网络组播向直接相邻的主机传送数据报。如果数 据报的口生存期大于1 ，组播路由器负责转发此数据报到组内的其它成员所在的网络。 在m 生存期内能够达到的网络上，相应的组播路由器进行本地组播完成全部的组播过 程。 2 1 2 组播地址 1 东北大学硕士学位论文g - 章q o s 组播路由 在组播通信中，我们需要两种地址：一个i p 组播地址和一个e t h e m e t 组播地址。其 中，i p 组播地址标识一个组播组。由于所有i p 数据分组都封装在e t h e m e t 帧中，所以 还需要一个组播e t h e m e t 地址。为使组播正常工作，主机应能同时接收单播和组播数据， 这意味着主机需要多个口和e t h e m e t 地址。 口地址方案专门为组播划出一个地址范围，在i p v 4 中为d 类地址，范围从2 2 4 0 0 0 到2 3 9 2 5 5 2 5 5 2 5 5 。如前所述，部分d 类地址被保留，用作永久组的地址，这段地 址从2 2 4 0 0 0 - 2 2 4 0 0 2 5 5 。组播路由器不会转发目的地址以2 2 4 0 0 开头的组播数据报。 临时主机组的组播地址由网络管理员选择，他需要保证这个地址在一定的范围内没有其 他的主机组在使用这个组播地址。 2 1 3 组播原理 组播是指将一个分组传向一个“主机组”的所有成员，如图2 1 所示。 。 图2 i 组播原理图 f i g 2 1t h e p r i n c i p l ed i a g r a m o f m u l t i c a s t s e r v e r 是组播服务器，主机h o s t l h o s t 3 都属于一个组播组，r 1 r 5 都是支持组播的 路由器，如果s e r v e r 要向组播组成员发送组播，其过程如下： ( 1 ) h o s t l - h o s t 3 分别通过向本地的组播路由器r 3 r 5 发送i g m p 消息来加入到组播 组中。这些本地路由器收到该消息后就知道它所连接的本地网络中有属于该组播组的成 员，于是将该组播组加入到组播组成员表中； 一8 一 东北大学硕士学位论文第二章o o s 组播路由 ( 2 ) 组播路由器r 1 - r 5 通过某种组播路由协议来构建一棵通往各组播成员的组播生 成树； ( 3 ) 当s e l w e r 要向该组成员发送组播数据报时，组播路由器沿组播生成树转发组播 分组。 图2 2 一棵组播生成树 f 追2 2a m u l f i c a s tt r e e 例如，如果生成树如图2 2 所示，则组播分组首先由s e r v e r 发往r l ，r 1 再将分组 转发给r 2 。然后r 2 将分组复制为三份，分别发往r 3 - r 5 。最后r 3 和r 5 根据存储的 组播组成员表，知道本地网络上具有该组播组的成员，于是将分组发往本地网络，本地 网络中的组播组成员就可接收到组播分组。 2 2 组播路由算法 2 2 1 组播路由算法简介 组播路由算法就是要生成一棵能够向所有组成员转发组播分组的生成树。路由计算 只在组播路由器之间进行。在没有q o s 约束的条件下，组播树的生成算法主要考虑到网 络的连通性和最短路径问题。 最简单的组播路由算法可采用一种称为逆向路径转发( r e v e r s ep a t hf o r w a r d ，r p f ) 的广播路由技术，该算法的过程描述如下： ( 1 ) 与组播源相连的组播路由器在收到一个分组后，将该分组从除与组播源相连的 端口外的其余所有端口转发出去。例如图2 1 中，路由器r 1 在收到s e r v e r 的组播分组 后，将分组分别发往r 2 ，r 3 ，r 5 。 ( 2 ) 网络中的路由器在收到一个组播分组后，首先检查该分组是否已经收到过，如 果没有，再将该分组从除接收端外的其余端口转发出去。例如r 2 在收到r 1 来的分组 后，由于它没有从其它地方收到过该分组，则将该分组发往r 3 ，r 4 和r 5 。 一9 一 东北大学硕士学位论文第二章q o s 组播路由 ( 3 ) 如果一个组播路由器己经从某一端口收到过该分组，则只需简单地丢弃该分组。 例如r 3 如果在收到r 2 来的分组前已经收到过从r l 来的分组，则r 3 将丢弃r 2 来的 分组。 显然这种采用广播方式的路由技术只能解决生成树的连通性问题，而不能得到一棵 优化的组播树，这样就无法充分地利用网络资源。 在采用基于源的组播路由协议的网络中，例如采用d v i v l p ，m o s p f 和p i m - d m 组 播路由协议。组播树的生成是通过从组播源出发，采用经典的b e l l m a n - f o r d 或d i j k s t r a 算法来计算到每个目的节点的最短路径，然后根据到每个目的节点的路径来构建一棵组 播树。在b e l l m a n f o r d 算法的d v m p 和p i m - d m 中，组播树的生成采用了广播裁剪协 议，即首先生成一棵与网络中所有节点相连通的生成树，然后用广播裁剪协议裁剪掉那 些不包含组成员的叶子节点。而在采用d i j k s t r a 算法的m o s p f 中，计算得到的生成树 的叶子节点从一开始就只包含组成员。 。 在这些基于源的组播路由算法中，得到的生成树并不是一棵最优的生成树。如果要 得到一棵覆盖网络中所有节点的最优生成树，可以采用p r i m 最小代价生成树算法。然 而，往往并不是网络中所有的节点都包含有组成员。在带有约束条件的情况下，求解一 棵最优的组播生成树的问题称为s t e i n e r 树问题。研究表明，该问题是一个n p 完全问题。 2 2 2 组播路由算法的分类 为进行有效的组播通信，确定组播路由是非常关键的，组播路由算法就是用来确定 组播树的。组播树是通过在每个路由器设置路由表来建立的，路由表上给出为使信息送 到组播组成员，此路由器应该选择哪个邻接节点的信息。由于网络的动态变化，每个路 由器的路由表也需要定期更新，此外路由表的设置还要保证不能有回路的产生。组播路 由算法可以从不同的角度和不同的准则进行分类。 ( 1 ) 静态算法和动态算法 组播路由算法按照是否允许网络成员随时加入或离开组播组，可以分为静态路由算 法和动态路由算法两类。静态组播路由算法针对初始的组播组成员构造一棵组播树，这 时候组播组成员和组播树都是固定的，它不能根据当前实际传输量和拓扑结构的变化来 做拓扑选择，而是按照先前构造好的组播路由进行传输，它的路由修改需经过一定时间 的运行后才能进行。 但是真实网络中存在许多动态的变化，例如网络拓扑结构的变化，组播组成员的变 一1 0 东北大学硕士学位论文第二章q o s 组播路由 化等，所畈动态组播路由算法显得非常的重要，它允许组播组成员可以动态加入或离开。 ( 2 ) 集中式和分布式组播路由算法 组播路由算法按照其实现方式，又可以分为集中式和分布式算法。集中式路由算法 是由节点在掌握了整个网络的拓扑结构后确定组播路由，集中式组播路由算法一般都是 源路由算法c s o u r c e o r o o t e ar o u t i n g ) ，即源节点通过某个链路协议获得完整的网络拓扑信 息，进行路由的计算。而分布式算法则不需要每个组成员掌握整个网络的拓扑信息，每 个组成员在只具有局部信息的条件下就可参与路由的确定。i 这两种算法各有其优缺点，集中式算法往往简单快速，但是由于一个节点需要维护 整个网络的状态，其开销可能比较大，而分布式算法相对于集中式算法较复杂并且速度 较慢，但是它有一个显著的优点，就是任何节点都不需要保持整个网络的状态。 ( 3 ) 有约束和无约束的组播路由算法 按照是否有q o s 约束，组播路由算法可以分为无约束组播路由算法和有约束组播路 由算法。许多现有的算法是为非实时网络设计的无约束组播路由算法，它们往往只试图 优化树的费用，两有约束的组播路由算法通常是在给定q o s 约束的条件下使组播树的费 用最小。 ( 4 ) 分层组播路由算法 随着网络规模的扩大，路由器的路由表也成比例增大，增大的表格不仅占用路由器 的内存，而且需要更多的c p u 时间来扫描表格，以及更大的带宽来发送关于表格的状 态报告。在某一时刻，网络可能会增大到不可能让每一个路由器都给出到其它每一个路 由器的路径表项，为此出现了分层路由选择( h i e r a r c h i c a lr o u t i n g ) 机制，分层路由算法是 将网络按照不同的等级划分成不同的层次，每个路由器只知道在自己的区域内怎样选择 路由和如何将分组发送到目的端的全部细节，而并不知道其他区域的内部结构。采用分 层路由算法有许多优点： 由于采用分层的方法，项层的节点数大大减少，由此减少了路由表的搜索时间。 而且每一层节点内部的路由表只在内部有效，因此路由表的计算量也大大减少。 每一层的节点只保存当前层的状态信息，与上下层都没有关系，从而减少了对 内存的需求量。 每一层的节点只在同一层内进行节点状态信息的交换，从而降低了信息的传输 量，节省了网络资源。同时，本层节点内部状态信息的交换被限制在节点内，不会扩散 到其他的节点。 一1 1 一 东北大学硕士学位论文 第二章q o s 组播路由 在每一个节点所代表的一个区域内，所采用的路由协议和路由算法与别的区域 无关，也就是说，不同的区域可以采用不同的路由协议和算法。 当然，分层路由机制也有其缺点： 分层的处理、区域的划分，会导致网络状态信息的不准确和不及时。 网络状态信息的不准确，会导致无法提供最优化的路径，降低寻径的性能。要 进行分层寻径，必须先确定好网络的层次，网络层次的构造基本上有两种：一种是以主 干为核心的两层结构，另一种是不依赖主干的多层综构。对于多层结构的构造，有自上 而下的t o p d o w n “”方法和自下而上的b o t t o m u p “”方法。 2 2 3s p f 路由算法 网络层的主要功能就是将分组从源端经选定的路径发送到目的端，这一过程称为分 组的路由。它可分为三个阶段：路由信息的收集，即收集必需的网络拓扑信息以建立正 确的路由。例如链路状态算法中采用扩散链路状态分组来得到整个网络的拓扑结构：路 由计算，即根据收集的信息计算路由。例如链路状态算法采用d i j k s t r a 算法来计算从本 路由器到其它路由器的最短路径；根据计算得到的路由转发分组。 在提供q o s 的网络中，同样要面临这路由选择问题。并且目前仍然采用传统的路由 协议中应用到的s p f ( s h o r t e s t p a t h f i r s t ) 路由算法：距离矢量路由算法和链路状态路由算 法。 ( 1 ) 距离矢量路由算法 距离矢量路由算法又称为b e l l m a n - f o r d 算法，它通过路由器协作完成分布式计算任 务。其过程描述如下： 在每个节点上保持两个向量d 和s 。其中日为节点i 的距离向量， 口= 4 。，面：，丸 ，吒表示节点i 到节点j 的距离的当前估计值；s 为节点i 的后继节 点向量，s = ，丑：， ，勺表示从节点i 到节点j 的当前路由中节点i 的后继节点。 每隔一定时间，各节点与它的相邻节点交换它们的距离向量。然后根据收到的全 部距离向量来修改本节点的距离向量和后继节点向量。对任一节点k ，按以下的方法进 行修改； 矗2 m i n l d 9 + 吒j ，f - 1 ，2 ，l ； ( 2 1 ) 2 i ，其中i 使得上面的 + 呜 为最小 一1 2 东北大学硕士学位论文第二章q o s 组播路由 距离矢量路由算法的主要优点在于简单、容易实现，适合于路由聚集。但其存在慢 收敛和无穷计算问题。r i p ( r o u t i n g i n f o r m a t i o np r o t o c 0 1 ) 和b g p ( b o r d e rg a t e w a y p r o t o c 0 1 ) 等单播路由选择协议，以及d v m r p 组播路由协议都采用了该算法。 ( 2 ) 链路状态路由算法 与距离矢量算法不同，链路状态路由算法首先通过路由信息搜集来建立链路状态数 据库。这个数据库是一个分布到各节点的冗余分布式数据库，它提供了关于每个节点的 信息。根据这些信息路由器可以构建一张关于整个网络的拓扑图。利用这个网络拓扑图， 各节点可以独立的计算出到其它节点的最短路径。 路由信息的搜集通过邻居节点发现、链路代价测量和链路状态分组的发布三个过程 来完成；而路由计算则采用d o s 订a 算法来实现，其计算过程如下： 假设s e t 表示顶点的集合，用矩阵c o s t 表示带权网络拓扑图，c o s t ，门表示链 路o ，) 的权值。若o ，力不存在，则c o s t i ，j = o o 。s 为己经找到的从节点v 出发的最短 路径的终点集合，它的初始状态为n u l l 。那么，从v 出发到网络上其它节点y 可能到 达的最短路径长度的初始值为：d i s t i 】- e o s t v ，i 】； 选择，使得d 妇f 【刀= 始n 威s f 【f 】 。一就是当前求得的从v 出发的最短路径的终 点。令s = s u j ； 修改从v 出发到集合s e t - s 上其它顶点u 的可达的最短路径长度。如果 d i s t j + c o s t j ，k 】 r 1 r 2 - r 4 h o s t 2 ；组成员收到r s v pp a t h 消息后，沿逆向发送资源预留请求。例如h o s t 2 收到p a t h 消息后，它将沿h o s t 2 - r 4 r 2 r 1 - s e r v e r 进行资源预留； ( 4 ) 最后当s c w e i 收到各组成员的资源预留消息后，开始发送组播分组，这些分组 将沿组播树转发。 一1 8 东北大学硕士学住论文 第二章q o s 组播路由 图2 3 带q o s 参数的网络拓扑图 f i g ，2 3t h en e t w o r kt o p o l o g yw i t hq o sp a r a m e t e r s 图2 4 一棵满足q o s 要求的组播树 f i g 2 4am u m c a s tt r e ew i t hq o sc o n s t r a i n s 2 4 3q o s 组播路由的数学模型 一个q o s 网络可用强连通的有向图g = ( v ，e ) 表示，其中非空顶点集合v 表示网络 中的节点集，对于任一网络节点v v ，具有如下q o s 属性：延时( 比奶，( v ) ) ，延时抖动 ( f i t t e r ( v ) ) ，丢包率( p a c k e t l o s s r a t e ( v ) ) 。有向边集合e 表示网络中的链路集，对于任 一条链路口e ，具有如下q o s 属性： 宽( b a n d w i d t h ( e ) ) ， 时( d e l a y ( e ) ) ，延时抖动 ( f i t t e r ( e ) ) 。弓( s ，d ) 为组播树r ( s ，m ) 上从源点s 到目的节点d 的路由路径，具有如下 1 9 东北大学硕士学住论文第二章q o s 组播路由 q o s 属性：带宽( b a n d w i t h t h ( p r ( s ，d ) ) ) ，延时( 沈 秒( p t ( s ，d ) ) ) ，延时抖动( j i t t e r ( p r ( s ，d ) ) ) ， 丢包率( 朋c 妇f l o s s r a t e ( p z ( s ，d ) ) ) 。并且具有如下性质“”： b a n d w i t h t h ( p r ( s ，d ) ) = m i n b a n d w i d t h ( e ) ，e 弓( j ，d ) ( 2 4 ) d e l a y ( e a s ，d ) ) = d e l a y ( e ) + d e l a y ( v ) ( 2 5 ) “片( j d )v e t ( s 。* ) j i t t e r ( p z ( s ，砌= f i t t e r ( e ) + f i t t e r ( e ) ( 2 6 ) 。6 斥“田 r ( ) p a c k e t l o s s r a t e ( p r ( s ，d ) ) = l 一兀( 1 _ p a c k e t l o s s r a t e ( e ) ) ( 2 7 ) 睫片( 。t d ) 因此q o s 组播路由问题可定义为：对于给定的网络g 三( v ，e ) ，源节点s ( s y ) ， 组播目的节点集d = 4 ，吐，以) ( 一v ，f - l ，2 ，栉) ，q o s 约束条件 q o s r e q = b a n d w i t h ，d e 枷，j i t t e r ，p a c k e t l o s s r a t e ，。寻找一棵组播m u l t i c a s t t r e e ， 满足如下条件： ( 1 ) m u l t i c a s tt r e e 是网络g 的一棵生成树； ( 2 ) m u l t i c a s tt r e e 的根是节点s ； ( 3 ) 所有的目的节点d = 反，吐，以) 都是在m u l t i c a s t t r e e 中； ( 4 ) m u l t i c a s t t r e e 的所有叶子节点属于组播目的节点集d ； ( 5 ) 从根s 到任意目的节点一的路径册以 ，都同时满足如下q o s 约束条件： m i n ( b a n d w i t h ( p a t h , d ) ) b a n d w i t h m a x ( d e l a y ( p a t h , , ) ) 出协 m a x ( j i t t e r ( p a t h , d ) ) j i t t e r m a x ( p a c k e t l o s s r a t e ( p a t h , , ) ) p a 。k e t 一蛔一r a t e ( 2 8 ) 2 5 小结 本章主要讨论了组播路由技术，其中包括i n t e r a c t 组播模型、组播