（控制理论与控制工程专业论文）带度约束的qos组播路由算法研究.pdf

人迮理i ：人学硕+ 学位论文 摘要 随着i n t e m e t 的迅速普及发展，视频会议、远程教育等大量新兴多媒体实时性业务 的应用越来越多，但是传统的c s 模式的流媒体服务系统的服务质量受服务器性能和服 务器端带宽资源限制。为了解决该问题，p 2 p 技术应运而生，使用p 2 p 技术，可以很好 地解决现有流媒体传输中遇到的服务器处理能力不足、网络带宽压力过重等一系列问 题。p 2 p 网络中的q o s 组播路由问题成为越来越重要的研究课题。 论文通过研究组播路由技术和算法，发现度约束在组播路由问题中的重要性，在此 基础上，通过分析满意优化理论及相关的一些关键问题，建立了带有度约束的q o s 组播 路由问题的数学模型，它是在考虑了带宽、时延、时延抖动、丢包率等约束条件的基础 上，将性能指标的满意度评价函数作为优化目标，寻找一棵满足节点度约束条件的组播 树。针对启发式搜索算法的缺点，鉴于带有度约束的q o s 组播路由问题的复杂性，引入 适合求解此类复杂的非线性n p 完全问题的遗传算法。在前面的研究基础之上，提出一 种解决该问题的遗传算法，采用二维矩阵编码方案，在包含连接信息的同时，还直观显 示了组播树中节点度的信息，非常便于判断路由器是否满足转发能力限制：采用保持父 代个体相同链路的交叉策略，避免非法个体产生，在交叉运算过程中，二维矩阵编码方 案便于寻找相同链路；另外针对q o s 组播路由算法对实时性要求较高，只要得到的组播 树满足q o s 约束条件即可的要求，算法的终止条件是群体中存在一棵符合q o s 约束条 件的组播树。最后对考虑度约束和不考虑度约束的q o s 组播路由问题做了对比研究，并 对在这两种情况下得到的组播树进行分析比较，证明了考虑度约束条件的重要性。 通过仿真实验可以看出算法不仅能求得满足多约束要求的解，而且性能较好，收敛 速度较快，具有较小的时间复杂度，适用于大规模的p 2 p 网络开发环境。算法重点在解 决组播路由选择问题，因此在带有q o s 约束并对实时性要求又较高的路由选择场合都可 以应用。 关键词：组播路由；遗传算法；满意优化；度约束；二维矩阵编码 人连理i ：人学硕十学位论文 r e s e a r c ho nd e g r e e - c o n s t r a i n e dq o sm u l t i c a s tr o u t i n ga l g o r i t h m a b s t r a c t a st h er a p i dd e v e l o p m e n to ft h ei m e m e t ，t h e r ef i r em o r ea n dm o r en e w a p p l i c a t i o n so f m u l t i m e d i ar e a l t i m eb u s i n e s ss u c ha sv i d e oc o n f e r e n c e ，r e m o t ee d u c a t i o ne t c b u tt h e q u a l i t yo fs e r v i c eo ft r a d i t i o n a lm e d i as t r e a m i n gs e r v i c es y s t e mw h i c hi s m a d eo f c l i e n t s e r v i c em o d e li sc o n s t r a i n e db yt h ep e r f o r m a n c ea n db a n d w i d t ho fs e r v i c e f o rs o l v i n g t h i sp r o b l e m ，p 2 pe m e r g e sa st h et i m e sr e q u i r e p 2 pc a nw e l ls o l v e st h ee x i s t i n gp r o b l e m s s u c ha sl a c ko ft h es e r v e r sp r o c e s s i n ga b i l i t y ，o v e r w e i g h to fn e t w o r kb a n d w i d t hi nm e d i a s t r e a m i n gt r a n s p o r t ，a n ds oo n t h eq o sm u l t i c a s tr o u t i n gi np 2 pn e t w o r kb e c o m e sm u c h m o r ei m p o r t a n tr e s e a r c ht o p i c t h i sp a p e rf i n d st h ei m p o r t a n c eo fd e g r e ec o n s t r a i n ti nm u l t i c a s tr o u t i n gb ys t u d i n g m u l t i c a s tr o u t i n gt e c h n o l o g ya n da l g o r i t h m o nt h i sb a s i s ，i tp r o p o s e st h em a t h e m a t i cm o d e l o fd e g r e e c o n s t r a i n e dm u l t i c a s tr o u t i n gp r o b l e mb ya n a l y z i n gs a t i s f a c t o r yo p t i m i z a t i o nt h e o r y a n ds o m ed e p e n d e n tk e yp r o b l e m s t h em o d e lc o n s i d e r sc o n s t r a i n t so fb a n d w i d t h ，d e l a y ， d e l a yj i t t e ra n dp a c k e tl o s sr a t e i t so p t i m a lg o a li ss a t i s f a c t i o ne v a l u a t i o nf u n c t i o no ft h e p e r f o r m a n c ea n dt os e e kam u l t i c a s tt r e ew h i c hm e e t st h ed e g r e e - c o n s t r a i n t i nt h el i g h to ft h e d i s a d v a n t a g eo fh e u r i s t i cs e a r c ha l g o r i t h m ，a n dt h ec o m p l e x i t yo fq o sm u l t i c a s tr o u t i n g p r o b l e mw i t hd e g r e e - c o n s t r a i n t ，t h ep a p e ri n t r o d u c e sg e n e t i ca l g o r i t h m ，w h i c hi sg o o df o r s o l v i n gt h i sk i n do fc o m p l e xc l a s sd i s t i n c t i o nn p c o m p l e t ep r o b l e m o nt h i sb a s i s ，t h ep a p e r p r o p o s e sag e n e t i ca l g o t i r h mw h i c hi s s u e st h e2 - d i m e n s i o n a lc o d i n gm e t h o d s ot h e c h r o m o s o m ec o n t a i n i n gt h ec o n n e c t i o ni n f o r m a t i o nc a n d i s p l a yt h en o d e sd e g r e ei n f o r m a t i o n d i r e c t l y ，w h i c hi su s e f u lt oj u d g ew h e t h e rt h er o u t e rc a ns a t i s f yt h ec o n s t r a i n to ft r a n s m i t t i n g a b i l i t y t h e g e n e t i ca l g o r i t h mu s e st h es t r a t e g yo fh o l d i n gt h es a m el i n ko fp a r e m c h r o m o s o m et oa v o i dt h ep r o d u c t i o no fi l l e g a li n d i v i d u a l ，a n dt h e2 - d i m e n s i o n a lc o d i n g m e t h o di se a s yt os e a r c ht h es a m ep a t h i na d d i t i o n , b e c a u s et h e r ei sh i g hr e q u i r e m e n to f r e a l t i m ei nq o sm u l t i c a s tr o u t i n ga l g o r i t h m ，t h ea l g o r i t h m st e r m i n a t i o nc o n d i t i o ni st h a t t h e r ei sam u l t i c a s tt r e ei nt h ep o p u l a t i o na c c o r d i n g 谢mq o sc o n s t r a i n tc o n d i t i o n i nt h ee n d ， t h ec o m p a r i s o no ft h em u l t i c a s tt r e eb e t w e e nt h em o d e lw i t hd e g r e e c o n s t r a i n ta n dt h em o d e l w i t h o u td e g r e e - c o n s t r a i n tp r o v e st h ei m p o r t a n c eo fc o n s i d e r i n gt h ed e g r e e c o n s t r a i n t i nt h es i m u l a t i o ne x p e r i m e n t ，i tc a nb es e e nt h a tt h ea l g o r i t h mc a nn o to n l yg e tt h e s o l u t i o nw h i c hs a t i s f i e st h ec o n s t r a i n t s ，b u ta l s ot h es o l u t i o ni sg o o dp e r f o r m a n c ew i t hf a s t c o n v e r g e n c es p e e d t h ea l g o r i t h mp o s s e s s e ss m a l l e rt i m ec o m p l e x i t y ，a n di ss u i t a b l ef o r d e v e l o p m e n te n v i r o n m e n to fl a r g es c a l ep 2 pn e t w o r k t h ea l g o r i t h ms t r e s s e so nt h ep r o b l e m 带度约求的q o s 宴艮播路由算法研究 o fm u l t i c a s tr o u t i n g ，s oi tc a l lb eu s e di nt h er o u t i n gw h i c hi sd e g r e e c o n s t r a i n e da n dw i t h h i g hr e q u i r e m e n to fr e a l t i m e k e y w o r d s ：m u l t i c a s t r o u t i n g ；g e n e t i ca l g o r i t h m ；s a t i s f a c t o r yo p t i m i z a t i o n ； d e g r e e c o n s t r a i n e d ；2 - d i m e n s i o n a lc o d i n g i v - 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：弛基鸯日期：卫迹：笸：丝 人连理i ：人学硕十研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定 ，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名：妇。垡龟 导师签名：勇爰乐u 大连理工大学硕士学位论文 1绪论 1 1 研究背景及意义 随着高速网络技术和多媒体技术的飞速发展，人们提出了越来越多的包括多媒体通 信在内的综合服务要求。传统的分组交换网络，如i n t e r n e t ，是面向非实时的数据通信 设计的，采用的t c p i p 协议主要是为了优化整个网络的数据吞吐量并保证数据通信的 可靠性，传输时延不是关键。而当今分布式多媒体应用，如视频会议、视频点播、i p 可 视电话、远程教育、虚拟现实等，不仅包括文本数据信息，还包括语音、图形、图像、 视频、动画等多媒体信息。 传统的多媒体服务系统主要采用d s ( c l i e n t s e r v e r ) 模式，服务器以单播的方式与每 个用户建立连接。由于多媒体服务具有高带宽、持续时间长等特点，随着用户数量的快 速增加，服务器端的带宽资源很快就会被耗尽，成为整个系统的瓶颈。为了解决传统 c s 模式存在的阉题，p 2 p ( p e e rt op e e r ，点对点网络) 技术应运两生疆l 。p 2 p 就是通过直 接交换实现计算机资源和信息的共享和交流。p 2 p 网络不依靠任何服务器提供服务，每 个节点既是服务器又是客户机，并且每个节点是平等的。p 2 p 网络克服了服务器瓶颈， 使得服务器的沉重负担分布到网络中的各台机器上。当其中一台机器瘫痪的时候，网络 能很快恢复稳定。p 2 p 网络以其简单性、可扩展性和强健性等特点正在流媒体服务领域 逐步流行。例如，当前流行的q q 直播、p p l i v e 、p p s t r e a m 和c o o l s t r e a m i n g 等流媒体 服务应用软件都应用了p 2 p 技术【2 j 。 刚络应用的扩展，要求网络既能传送“尽力丽为( b e s t - e f f o r t ) ”的服务，也能传送有 一定服务质量( q o s ，q u a l i t yo f s e r v i c e ) 要求的实时多媒体业务。而传统的尽力而为的传 输方式只能使各种数据流在网络中平均地分享网络资源且巍沿多条路径传输，丽不能满 足有q o s 要求的实时多媒体业务传送的需要。因此，对q o s 约束的组播路由算法的研 究就逐步开展起来。 具有q o s 约束的组播路由算法，就是按照某种路由策略，利用网络状态信息来构造 一棵包含所有组播成员的组播路由树，以确定数据包的传送路径，同时满足各种q o s 需求，实现网络资源的优化。扶瞒络用户的角度来看，基于q o s 的组播路由算法首先应 满足用户的q o s 需求，即寻找一条端到端的、满足各种条件的传输路径。从服务提供商 的危度来看，基于q o s 的组播路宙算法应能最优化地使用网络资源。 尽管q o s 组播路由问题已成为网络研究领域的热点问题，但是有效解决这一问题仍 存在一些困难p j ： 带度约束的o o s 组播路由算法研究 ( 1 ) 实时多媒体业务对带宽、时延、时延抖动、丢包率、吞吐量、可靠性和传输费 用等有不同的需求，这样的具有多个不相关度量的q o s 组播路由问题是一个n p 完全问 题。 ( 2 ) 路由算法最终要成为组播路由协议的一部分，因此需要考虑一些实际的因素， 如链路状态的收集与更新、网络拓扑结构和成员的变化、组播树的维护和扩展等，最后 还要加上q o s 约束，会使协议的设计变得更加复杂。 ( 3 ) 在实际的网络通信中，并不是每个节点都可以向与其邻接的所有节点发送信 息，各个网络节点的多播能力是受到限制的，因为这样可以减少节点复制信息的数量， 缩短处理信息的时间，有助子保证网络的传输速度，还可以平衡各个节点的负载。这就 引入了度约束( d e g r e e c o n s t r a i n e d ) 问题f 4 】，通过对网络节点给定度约束来限制节点的组 播能力。因此，有度约束的q o s 组播路由问题在网络通信中具有重要意义，应考虑如何 以最小的代价来收集或者维护与带有度约束的q o s 相关的状态。 综上所述，对满足q o s 约束的组播路由算法的研究对网络理论和应用的发展都有着 重大的推动作用。因此，对此领域的研究有很强的理论意义和应用价值。 1 2 组播路由算法的研究现状 为进行有效的组播通信，确定组播路由是非常关键的，组播路由算法就是用来确定 组播树。组播树是通过在每个路由器设置路由表建立的，路由表上给出了信息传送的组 成员，以及此路由器应选择哪个邻接点。由于网络的动态变化，每个路由器的路由表也 需要定期更新。此外路由表的设置要保证不能有回路的产生。下面对组播路由算法进行 介绍。 1 2 1s t ein e r 树算法和c b t 算法 在构造组播树时，一般用树的“费用”来衡量组播树的好坏，组播树的费用是指树 中所有链路费用的总和。这里链路的费用是一个广义的费用，它可以指链路上的延迟、 可用资源、带宽和价格等。在实际应用中，一般要求确定的路由要有效利用网络资源， 为此要求组播树的费用最小。在网络中寻找覆盖给定节点集合的费用最小的生成树问 题，在数学上被称为s t e i n e r 树问题，这是一个n p 完全问趔5 1 ，即一般来说，最优算法 无法在多项式时间内完成。因此，需要寻求有效的启发式算法，降低算法难度，而在性 能上逼近理论最优。目前求解s t e i n e r 树问题的启发式算法很多【6 】，它们都可以用来求解 费用最小组播树。为此s t o n e r 树理论是求解费用最小组播树算法的理论基础，也是组 播算法的一个重要研究方向。 大连理工大学硕士学位论文 中心树算法是近来提出的构造组播树的新方法。它首先由b a l l a r d i e 在文献【7 】中提 出，以选定中心为根，c b t ( c o r e - b a s e dt r e e ) 不具备广播特性，即数据只发向明确发出 加入组请求的节点，避免了广播式算法运行时大量无效分组的扩散。由于动态优化选择 树中心的算法无法在多项式时闻内完成，一种简单可行的算法是在接受成员之中选择次 优中心。文献 8 】在分析了多种确定中心算法的基础上，给出了几种分布式优化选择中心 的窟发式算法，它们应用蜀部网络拓扑知识计算出一系列备用中心，以降低中心失败带 来的影响。此外，采用多中心c b t ，也可有效抑制中心失败的影响，但由于构造和管理 多中心c b t 的复杂性，闯题还没有成熟的结论。 1 2 2 静态和动态组播路由算法 组援路由算法有静态和动态之分，静态组播路漱算法针对初始组播组成员构造一棵 组播树。它不能根据当前实际( 实测或估测) 传输量和拓扑变化来做拓扑选择，而是按初 始设计好的路由传送，它的路由修改经过一定运行质才能进行。但是真实网络中存在许 多动态变化，如网络拓羚结构的变化，组成员的变化等，因此动态组播路由算法显得非 常重要。构造适应组成员动态变化的算法有三种方式：一种是构造一棵性能优化的初始 组播树，成员变纯之后对树采取最小的变化，如文献【鲷中的算法，成员的加入通过建立 节点到树的最短路由完成；成员的离开仅删除树叶节点，如果删除后产生一个非成员树 叶，该算法删除该节点，直到不存在非成员树叶。另一种是成员变更后，对整个组重新 进行路由，这将对组中原来成员通信产生干扰( 数据分组顺序打乱) ，当成员的变化剧烈 时，这种方法是不实用的。文献 1 0 】给出了一种改进算法，酋先节点的加入和离开仿照 前面第一种方式实现，但在树的局部范围内，考察节点的加入和离开对树的累计损伤， 当这种累计损伤超过一定门限时，在局部范围内重新优化路由，通过改变门限值达到树 的优化和计算时间、复杂性之间的平衡。第三种是构造一棵富于弹性变化的次优树，即 最短路径树，每个组成员之间相互独立选择最短路由，因此树的性能不受组动态变化的 影响。 1 2 3 集中式和分布式组播路由算法 组播路由算法按其实现方式，又分为集中式和分布式算法。集中式路由算法是由节 点在掌握整个网络的拓扑后，确定组播路由。集中式组播路由一般都是源路由算法 ( s o u r c e r o o t e dr o u t i n g ) ，即源节点通过某个链路协议获得完整的网络拓扑信息，进行路 由的计算。而分布式算法不需要每个组成员掌握整个网络的拓扑，每个组成员在只具有 局部信息条件下就可参与路由的确定。 带度约束的q o s 组播路由算法研究 以上两种算法各有其优缺点，集中式算法往往简单快速，但是由于每一个节点在确 定路由之前要收集全网的拓扑信息，其开销可能比较大；而分布式算法相对于集中式算 法较复杂并且速度较慢，但它有一个显著的优点，就是任何节点都不需要保存整个网络 的状态，适合大型网络路由的确定。文献 1 1 对分布式组播路由算法进行了研究。 1 2 40 0 s 组播路由算法 随着网络技术的迅速发展，交互式会议电视、分布式网络对战游戏、协同文档编辑、 视频点播、网络电话、远程实时医疗等已经开始应用，这些应用涉及到网络q o s 问题【l 引。 q o s ( q u a n l i t yo f s e r v i c e ) 包括许多方面，例如端到端时延、端到端时延抖动、路径带宽、 路径中的数据丢失率等。 对于组播q o s 路由问题，一般有两种q o s 要求，即最优化( o p t i m i z a t i o n ) 和给定某 个约束( c o n s t r a i n t ) 。这些要求的组合就形成了用户对网络提出的各种q o s 要求。如要 求组播树中源节点到各个组成员的时延要不高于时延约束，且组播树的费用要求最小， 这就是组播的路径时延受限和组播树优化的组合。组播q o s 路由问题中研究最多的是受 限组播路由问题，也称为q o s 组播路由问题【l3 1 ，即满足带宽、时延等约束条件下的费 用最小组播路由问题i 1 4 , 1 5 j 。 1 2 5 分层组播路由算法 随着网络规模的扩大，必须对网络进行分层，由此也带来分层组播路由问题【l6 。在 分层网络中，节点按区域分成子层，然后子层再汇聚成更高层的组，形成一种等级结构。 采用分层路由算法有许多集中式算法无法相比的优点，例如：减少路由表的搜索时间和 内存的需求量，降低信息的传输量，节省了网络资源，在不同的区域可以采用不同路由 协议和算法。分层路由机制在给我们带来好处的同时，也有不利的一面：如导致网络状 态信息的不准确，从而无法提供最优化路径，降低寻优性能。 目前，分层路由算法主要有：容错分层路由算法、基于区域的链路向量算法和基于 分层信息路径的路由算法。要进行分层寻优，必须先确定好网络的层次。网络层次的构 造基本上有两种：一种是以主干为核心的两层结构，另一种是不依赖主干的多层结构。 对于多层结构的构造，有自上而下的t o p d o w n 方法和自下而上的b o t t o m u p 方法。 1 3 论文所做的工作 在p 2 p 网络中，由于应用层网络是在下层i p 网络基础设施之上构建的虚拟逻辑网 络，其路由和下层网络的路由通常不一致，这就可能造成应用层组播的时延增加和资源 大连理丁大学硕士学位论文 浪费。这对时延和带宽敏感的实时多媒体应用来说就显得更加突出。如何提供有效的组 播，设计良好的组播路由算法是保证p 2 p 网络应用层组播服务质量的关键。论文主要研 究节点度和网络q o s 都受约束的应用层组播路由算法，主要工作归结如下： ( 1 ) 通过研究组播路由技术和算法，发现节点度约束在组播路由问题中的重要性， 在此基础上，通过分析满意优化理论及相关的一些关键问题，提出了带有度约束的q o s 组播路毒问题的数学模型，它是在考虑了带宽、时延、时延抖动、丢包率等q o s 约束条 件的基础上，将性能指标的满意度评价函数作为优化目标，寻找一棵满足节点度约束条 件的组播树。 ( 2 ) 对网络节点的度约束闯题进行分析，发现带有度约束的q o s 组播路由问题在网 络通信中具有重要意义。针对启发式搜索算法的不足，提出了一种遗传算法，该算法在 构建过程中考虑了度的约束，优化平衡网络负载；并且在拓扑优化策略中尽可能复用已 用的转发路径，从而有效的减少了转发时延和重复分组。 ( 3 ) 利用r n e t 嬲络拓扑生成算法生成一个符合实际网络的霹络模型，并进行仿真 实验。实验结果表明，论文提出的针对带度约束的q o s 组播路由问题的遗传算法具有较 好的收敛性，与文献 4 7 1 q b 的常规遗传算法相比在优化组播树的网络资源方面表现出了 较好的性能。另外，也对考虑度约束和不考虑度约束两种情况状态下得到组播树进行对 比分析研究，证明了考虑度约束的重要性。 1 4 论文的组织结构 论文结构组织如下： 第一章“绪论”，介绍了论文的研究背景及意义，在概述了组播路由算法的研究现 状后，说明了论文所做的主要工作。 第二章“组播路由技术 ，分耩了组播路由技术的发震背景，解释了组播树的概念， 并详细的研究了组播路由协议，为下一步的研究打下基础。 第三章“带度约束的q o s 组播路由闷题描述”，首先阐述了几个在带有度约束的 q o s 组播路由问题中所涉及的概念，并引入满意优化理论建立该问题的数学模型，接下 来详细描述了一系列提供近似解的基于s t e i n e r 树的启发式算法。尽管启发式搜索算法 是一种简单有效的路由选择机制，僵当前提出的组播路由算法多局限于单纯的启发式搜 索思想，没有提出新的搜索方法。 第四章“求解带度约束的q o s 组播路豳闯题的遗传算法，针对带有度约束的q o s 组播路由问题，提出一种遗传算法，详细阐述了遗传算法每个步骤的设计方案。编码采 用二维矩阵编码方案，采用该编码方案的个体在包含连接信息的同时，还直观显示了组 带度约束的q o s 组播路由算法研究 播树中节点度的信息，非常便于判断路由器是否满足转发能力限制。另外该遗传算法采 用了保持父代个体相同链路的交叉策略，避免非法个体的产生，在交叉运算过程中，论 文提出的二维矩阵编码方案便于寻找相同链路。接下来详细描述了算法设计中所需要用 到的相关算法，并都加以编程实现。最后给出一个网络拓扑模型，利用论文提出的遗传 算法，分别对不同约束条件下的q o s 组播路由问题进行计算，将得到的实验结果进行对 比分析，发现考虑度约束条件的重要性和必要性。 第五章“仿真实验结果及其分析”，首先给出r n e t 网络拓扑图生成算法，并利用 该算法生成一个符合现实网络要求的p 2 p 网络拓扑模型，然后详细描述了论文提出的针 对带度约束的q o s 组播路由问题的遗传算法的运算结果，并对算法进行了性能分析，验 证了论文提出的遗传算法性能优于文献 4 7 中的常规遗传算法，以及算法的收敛性。 最后“结论”，总结全文的工作，并对未来工作提出设想。 人连理工大学硕士学位论文 2 组播路由技术 2 1 组播路由技术的发展背景 当代社会已进入信息时代，网络技术在飞速发展，当自订通信网络带宽和处理能力的 提高使网络能够提供更多的多媒体业务，也使得支持“点到多点”或“多点到多点”的 通信方式成为网络支持多媒体业务的必要形式，即一个或多个发送者( 源节点) 将数据发 送到多个接收者( 目的节点) 。一般说来，有三种不同的通信方式可以实现： 单播( u n i c a s t ) 传输：在发送者和每一接收者之间需要单独的数据信道。如果一台主 机同时给很少量的接收者传输数据，一般没有什么问题。但如果有大量主机希望获得数 据包的同一份拷贝时将很难实现，因为这将导致发送者负担沉重、时延增加以及造成网 络拥塞等问题，而且为了保证一定的服务质量还需要增加硬件和带宽。 削湍涪一蝎 图2 1 单播通信方式示意图 f i g 2 1 t h es c h e m a t i cd i a g r a mo fu n i c a s t 广播( b r o a d c a s t ) 传输：是指在整个i p 子网内广播数据包，所有在子网内部的主机 都将收到这些数据包。广播意味着网络向子网主机都投递一份数据包，不论这些主机是 否乐于接收该数据包。然而广播的使用范围非常小，只在本地子网内有效，因为路由器 会封锁广播通信；同时广播传输增加了非接收者的开销，浪费了网络资源。 组播( m u l t i c a s t ) 传输：是指一个或多个发送者( 组播源节点) 一次地、同时地发送单 一的数据包到多个接收者。参与组播的多个接收者( 目的节点) 组成了一个组播组 ( m u l t i c a s tg r o u p ) ，每个接收者也称为组播组成员。组播源将数据包发送到特定组播组， 而只有属于该组播组地址的节点才能接收到数据包。由于无论有多少个目的地址，在整 个网络的任何一条链路上只传送单一的数据包，凶此组播大大节省了网络带宽，提高了 凰 带度约束的q o s 组播路睁1 算法研究 数据传送效率，减少了主干网的带宽要求以及主干网出现拥塞的可能性。由图2 1 和图 2 3 可以看出组播通信和单播通信的区别。 源主机 非目的主机 目的主机非目的主机 图2 2 广播通信方式示意图 图2 3 细橘通信方i = 示意图 f i g 2 3 t h es c h e m a t i cd i a g r a mo f m u l t i c a s t 2 2 组播转发树 在i p 单播中，信息通过网络沿着单一路径从源主机向目标主机传递，但是，在i p 组播中，组播源向某一组地址传递数据包，而这一地址却代表一个主机组。源丰机向任 一被组播组地址表示的主机组传递消息，i p 组播路由器必须知道包的来源，而不是目的 地( j 单播相反) ，为了向所有接收站点传递组播信息，一般采用组播转发树描述i p 组 播在例络巾经过的路径，简单的说就是数据从源主机到接收者的传输流的路径。组播转 发树一般可分为两种类型【3 j ：有源树和共享树。 需 t 豆 一 t l 置 一 t j 置 一 i 大连理工大学硕士学位论文 2 。2 1 逆向路径转发 所有的i p 组播路由协议都利用逆向路径转发( r p f ，r e v e r s ep a t hf o r w a r d i n g ) 作为 决定是否转发或丢弃从某个接口上接收到的组播信息包的主要机制。当组播信息包到达 路由器时，路由器对信息包迸彳亍r p f 检查，进行如下工作： ( 1 ) 路由器检查接收到的组播信息包源地址，以确定此信息包的端口是否是该节点 到该维播源的最短路径上的端墨。 ( 2 ) 如果信息包是在可返回源站点的端口上到达，则r p f 检查成功，信息包被转发。 ( 3 ) 如果r p f 检查失败，丢弃该信息包。 2 2 2 有源树 组播转发树最简单和最常见的形式是有源树，有源树也称为基于信源的树或最短路 径树( s p t ，s h o r t e s tp a t ht r e e ) 。它是以组播源为根构造的从根到所有接收者路径都最短 的转发树。如果组中有多个组播源，则必须为每个组播源构造一棵组播树。出于不同组 播源发描的数据包被分散到各自分离的组播树上，因此采用s p t 有利于网络中数据流量 的均衡。同时，因为从组播源到每个接收者的路径最短，所以端到端( e n d t o e n d ) 的时 延性能较好，有利于流量大、时延性能要求较高的实时媒体应用。s p t 莳缺点是：要为 每个组播源构造各自的分布树，当数据流量不大时，构造s p t 的开销相对较大。 构造s p t 有多种算法，当前i n t e m e t 上常用的算法包括r p f 和d i j k s t r a 算法。 d i j k s t r a 算法的基本想法是每一次将距离信源最近的节点加入到树上，构造一棵生 成树，然后将非组成员叶节点删除，该算法暗含的要求是源主机必须具备所有目的站点 的地址信息。d i j k s t r a 算法实现简单，算法中各个节点采用全部拓扑信息来计算从源节 点到目的节点的最短路径，并保证不会产生环路。但算法集中执行，需要全网拓扑， 次性耗时长，大量信源同时发送数据时c p u 受载重，所得的组播树的费用也较高。 2 2 3 共享树 固有源树用组播源律为根不同，共享树是用放在网络上的某些可选择点作为共享树 的单独的公用根。这个根通常被称为汇合点( r p ，r e n d e z v o u sp o i n t ) ，因此共享树也称 r p 树( 叮，r e n d e z v o u sp o i n tt r e e ) 。与有源树不同，弼一组播组的组播源不是直接囱 网络中发送组播信息包，而是将所要组播的数据单播到共享树中的根( r p r ，r e n d e z v o u s p o i n tr o o t ) ，再如r p r 向网络中其他成员转发组播信息。由于共享树只允许组播信息经 过共享树 t 的根发送到接收站点，因此，组播信息的源主机必须采取一些方法使共 享树的根首先得到消息，以便使得组播信息能转发到共享树。其中一种方法就是与s p t 相结合，把信息流弓| 到跟，再转发到共享树。即从源主机到船t 的根，以及从r p r 的 带度约束的q o s 组播路由算法研究 根到组播信息的接收者，都是采用最短路径树。目前，讨论最多同时也是最具代表性的 两种共享树是s t e i n e r 树和有核树( c b t ，c o r e b a s e dt r e e ) 。 共享树在路由器所需存储的状态信息的数量和路由树的总代价两个方面具有较好 的性能。当组播组的规模较大，而每个成员的数据发送率较低时，使用共享树比较适合。 但当通信量大时，使用共享树将导致流量集中及根附近的瓶颈的问题。 2 2 4 共享树与有源树的比较 与有源组播树相比，共享组播树有以下优点： ( 1 ) 建立和维护一棵共享树的开销小得多。对于共享组播算法来说，当有新的源节 点加入时，不需要再对信源和组播成员建立一棵基于源的组播树，而只需要把源节点本 身登记到己存在的共享组播树上即可。类似地，当需要增加一个目的节点时，只需要将 节点本身登记连接到共享树上即可。 ( 2 ) 使用共享树方式时，任何一个源节点无需为组播任务保存组播会话的成员列 表。类似地，对于任何一个目的节点，也无需保留源节点的列表。 另一方面，共享组播树的缺点也显而易见。 ( 1 ) 高度的流量集中特性。由于来自不同源节点的业务流共享同一棵树，给定组播 任务的所有流量都将集中在共享组播树的树枝上，从统计特征上看不像有源树那样平均 分布，导致树枝上的链路流量高度集中。 ( 2 ) 共享树的端到端时延性能比同样情况下的有源树方式要差很多( 图2 4 给出了 这种端到端时延性能差别情况的例子) 。在图2 4 ( 1 ) 的网络实例中，源节点和目的节点 均为m ，m ，m ，每条边的时延为1 。图2 4 ( 2 ) 是一棵共享树，其最大时延为2 。图 2 4 ( 3 ) 是三棵有源树，它们的最大时延仅为1 。 构造共享树和构造有源树有许多相似的地方，但最重要的一点区别在于：构造共享 树首先需要选择一个组播中心。严格意义上讲，共享树并非只能有一个中心，但是选定 一个节点为其中心便于管理和操作。例如，一旦选定一个组播中心，可以安排组播中心 负责接纳新的目的节点的加入，或者作为联系所有源节点和目的节点的控制中心。所以， 实际应用中使用共享组播方式的路由算法和协议大都指定一个中心，只不过允许使用动 态的中心，或者采用选择中心的方法。 找出最优共享树是非常困难的，因此，研究学者在对共享树问题的研究时，总是将 该问题划分为两个子问题进行研究，即中心选择问题( c e n t e rs e l e c t i o np r o b l e m ) 和路由选 大连理工大学硕士学位论文 择问题( r o u t es e l e c t i o np r o b l e m ) 。大多数共享树构造算法首先选择一个节点作为中心， 然后基于该中心构造共享组播树，这两类子问题可以独立进行研究。 1 )网络实例 2 )共享树 3 )有源树 图2 4 共享树与有源树的端到端时延性能 f i g 2 4d e l a yp e r f o r m a n c eo fs h a r et r e ea n ds o u r c et r e e 2 3 组播路由协议 为进行有效的组播通信，确定组播路由是非常关键的。由于组播组中有多个目的节 点，因此组播路由也比单播路由复杂许多。组播路由算法是论文的研究重点。使用组播 路由算法来确定路由，是在收集网络中相关状态信息的基础上完成。网络的状态信息包 括网络的拓扑结构、链路和路由器的负载程度、链路和路由器的失效和有效、网络中路 由器的类别( 是否具有组播功能) 等。这些信息的收集是由组播路由协议( m u l t i c a s t r o u t i n gp r o t o c 0 1 ) 来完成的。本节简要介绍几个实际应用中的组播路由协议，并对设计 组播路由算法和协议时应考虑的因素进行分析。 带度约束的q o s 组播路由算法研究 组播路由协议用于发现组播组，建立组播路由表或组播树，进行组播数据包传送。 和单播路由协议一样，组播路由也包含路由表的生成和维护两部分。在一个组播会话中， 转发组播数据包的所有路由器节点集合其实就形成了一个组播树，组播路由实质上就是 组播树生成和维护的过程。组播路由器运行组播路由协议，确定数据包的发送路径，以 便在网络上传送组播数据包。可以从很多角度对现有的组播路由协议进行分类，其中一 种是将组播协议细分为以下三个基本类【l7 1 。 2 3 1 密集模式协议 密集模式协议( d m ，d e n s em o d e ) 总是假定在子网上有接收者，用定期广播组播报 文的方法维护组播分布树，组播信息一开始就被扩散到网络的所有站点，这对于接收者 较多的网络来说，效率较高，因此被称为密集模式协议。密集模式协议有p i m d m ， d v m r p 等。 ( 1 ) 协议无关组播路由协议( p r o t o c o li n d e p e n d e n tm u l t i c a s t ，p i m ) p i m 设计的出发点在于在广域网范围内同时支持共享树与有源树，并能完成两者之 间的灵活转换，因而集中了两者的优点同时避免了它们的缺点。在组员密集时以广播形 式传输数据，然后从树上删除不存在接收节点的分支；而组员分布稀疏时，构造共享树 传送，避免分组的广播开销。相应p i m 有两种模式：稀疏模式( s p a r s em o d e ，s m ) 1 8 j 和密集模式( d e n s em o d e ，d m ) 1 9 j 。 p i m d m 是指组播组所覆盖的区域内，具有该组用户的子网数量在子网总数中占很 高的比例。p i m d m 基本上与d v m r p 相同，属于数据驱动型协议，但协议只是直接使 用点到点路由算法给出的路由表转发数据。 ( 2 ) 距离向量组播路由协议( d i s t a n c ev e c t o rm u l t i c a s tr o u t i n gp r o t o c o l ，d v m r p ) d v m r p 2 0 】是第一个得到广泛使用的组播路由协议，在接收者密集时的效率较高， 它在m b o n e 上被广泛使用。d v m r p 采用路由信息的方式为每个源网络根据最优度量建 立一个组播转发树，并在m b o n e 上采用隧道技术，使组播通信得以在支持组播的子网 之间实现。由于m b o n e 的飞速发展，由d v m r p 带来的大量路由控制分组定期地在网 络中扩散的开销限制了网络规模的发展，为此还提出了分层d v m r p 。d v m r p 也有一 些不足之处，首先是它需要经常进行洪泛，将组播信息发送到网络上的每一点，即使没 有接收者的情况也是一样，这样极大地浪费了网络的带宽；其次它会在路由器中存储大 量的组播转发信息，占用了宝贵的路由器资源。 密集模式协议的显著特征是周期性的