（计算机应用技术专业论文）pbil进化算法在qos组播路由中的应用研究.pdf

南京邮电大学硕士研究生学位论文摘要 摘要 组播是一点到多点的信息传送方式。随着分布式多媒体应用需求的不断提高，如视频 点播、多媒体会议等，这些应用不仅是涉及多个用户，而且对服务质量( q o s ，q u a l i t yo f s e r v i c e ) 有着一定的要求。具有q o s 约束的组播路由问题已被证明是n p 完全问题。 目前许多研究者在单约束( 特别是时延约束) 组播路由中取得了较好成果，但对于多 q o s 约束组播路由方面的研究相对较少。本文研究了具有时延、时延抖动、带宽和包丢失 率约束的组播路由问题，提出了使用一种新型优化算法p b i l ( p o p u l a t i o n b a s e d i n c r e m e n t a ll e a r n i n g ) 进化算法来求解多q o s 约束组播路由。在按路径编码阶段，使 用了一种深度优先搜索算法求解备选路径集，使得其中的路径都能满足时延、时延抖动和 包丢失率约束。本文的组播路由算法实施简单，时间复杂度较低，仿真实验表明了它具有 较快的收敛速度，同时能以较大的概率收敛到最优解。 本文还提出了对基本的p b i l 进化算法进行改进，在获取每代最优个体时引入了局部 搜索算法k 一邻域交换法，对每代最优个体的基因位按取值的优秀程度采用不同的学习概率 修正系数，并且在算法中引入一个恒定的平均概率矢量来指导产生种群的一部分个体。将 改进的算法应用于求解多q o s 约束的组播路由问题，在仿真实验中与基本的算法进行了比 较，结果表明改进的算法具有更高的搜索效率和更好全局收敛性能。 关键词：组播路由q o s 约束p b i l 进化算法组播树 塑室堕皇查兰堡主堑窒生堂垡垒苎 垒堕! 竺! a b s t r a c t m u l t i c a s ti sas o u r c en o d es e n d st h es a l t l em e s s a g et oag r o u po fd e s t i n a t i o nn o d e s i nt h e i n c r e a s i n gd e m a n d so fd i s t r i b u t e d m u l t i m e d i aa p p l i c a t i o n s ，s u c ha sv i d e oo nd e m a n d ， m u l t i m e d i ac o n f e r e n c e ，t h e s ed on o to n l yi n v o l v em u l t i u s e r , b u ta ls on e e dae f f i c i e n ta n d e f f e c t i v es u p p o r to fq u a l i t yo fs e r v i c e ( q o s ) q o sm u l t i c a s tr o u t i n gh a sb e e np r o v e dt ob ea n p c o m p l e t ep r o b l e m p r e s e n t l y , m a n yr e s e a r c h e r sh a v es t u d i e dt h es i n g l e c o n s t r a i n e dm u l t i c a s tp r o b l e m s ， e s p e c i a l l yt h ed e l a y c o n s t r a i n t b u tt h em u l t i p l ec o n s t r a i n e dm u l t i c a s tp r o b l e m sh a v eb e e ns u c h l e s ss t u d i e d i nt h i sp a p e r , w es t u d yt h em u l t i p l e - c o n s t r a i n tm u l t i c a s tr o u t i n gp r o b l e m ，w h i c hi s t of i n dt h el e a s t c o s tm u l t i c a s t i n gt r e ew i t ht h ec o n s t r a i n t so f d e l a y , d e l a yj i t t e r , b a n d w i d t ha n d p a c k e t l o s s w ep r o p o s eu s i n gan e wo p t i m i z a t i o na l g o r i t h mp b i l ( p o p u l a t i o n - b a s e d i n c r e m e n t a ll e a r n i n g ) a l g o r i t h mt os o l v et h i sp r o b l e m i nt h ep a t hc o d i n gs t a g e ，w ep r o p o s ea d e e p - f i r s ts e a r c h i n ga l g o r i t h mt of i n dt h ep a t h sw i t hd e l a y , d e l a yj i t t e ra n dp a c k e t - l o s s c o n s t r a i n t s t h en e wr o u t i n ga l g o r i t h mh a sal o wc o m p l e x i t yo ft i m e ，c a nb ee a s i l yp u ti n p r a c t i c e t h es i m u l a t i o nr e s u l t ss h o wt h a ti tc o n v e r g e sq u i c k l y , a n da l s oh a sah i g hp r o b a b i l i t y t oo b t a i nt h eo p t i m i z a t i o ns o l u t i o n b e s i d e s ，w em a k es o m ei m p r o v e m e n to nb a s i cp b i la l g o r i t h m i nt h ea c q u i r i n go fb e s t i n d i v i d u a lo fag e n e r a t i o n ，k n e i g h b o r h o o de x c h a n g ei su s e d w h e nu s i n gt h eb e s ti n d i v i d u a lt o u p d a t et h es t u d yp r o b a b i l i t y ，d i f f e r e n tl e a r n i n gr a t e sa r eu s e df o rt h o s eg e n e so ft h eb e s t i n d i v i d u a l ac o a s ta v e r a g ep r o b a b i l i t yv e c t o ri sa l s oi n t r o d u c e di n t ot h ep b i la l g o r i t h m i nt h e s i m u l a t i o n so fa p p l i c a t i o ni nm u l t i p l e c o n s t r a i n tm u l t i c a s tr o u t i n g ，t h ei m p r o v e da l g o r i t h mi s p r o v e dt oh a v eah i g h e rs e a r c h i n ge f f i c i e n c ya n dab e t t e rc o n v e r g ec a p a c i t y k e yw o r d s ：m u l t i c a s tr o u t i n g ，q o sc o n s t r a i n t s ，p b i la l g o r i t h m ，m u l t i c a s tt r e e 南京邮电大学 硕士学位论文摘要 学科、专业：工学计算机应用技术 研究方向：计算机控制技术 作 者：2 0 0 3 级研究生王赞指导教师壬熊莹 题目：p b i l 进化算法在q o s 组播路由中的应用研究 英文题目：q o sm u h i c a s tr o u t i n gw i t hp b i la l g o r i t h m 主题词：组播路由q o s 约束p b i l 进化算法组播树 k e y w o r d s ： m u l t i c a s tr o u t i n g q o sc o n s t r a i n t s p b i la l g o r i t h m m u l t i c a s tt r e e 南京邮电大学硕士研究生学位论文 缩略语表 a t m b s c c b t d m d v m r p f e c g a i e t f i s p l e r l s p l s r m p l s n p o s p f p b i l p i m q o s p m e a r s v p s l a s m v c v c c 缩略语表 a s y n c h r o n o u st r a n s m i s s i o nm o d e 异步传输模式 b i t - b a s e ds i m u l a t e dc r o s s 基于基因位的模拟交叉 c o r e - b a s e dt r e e有核树 d e n s e m o d e 密集模式 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 距离矢量组播路由协议 f o r w a r de q u i v a l e n c ec l a s s转发等价类 g e n e t i ca l g o r i t h m 遗传算法 i n t e r n e te n g i n e e r i n gt a s kf o r c e 互联网工程任务组 i n t e r n e ts e r v i c ep r o v i d e r互联网服务提供商 l a b e le d g er o u t e r 标签边缘路由器 l a b e ls w it c hp a t h 标签交换路径 l a b e ls w i t c hr o u t e r 标签交换路由器 m u l t i p r o t o c o ll a b e ls w i t c h i n g 多协议标记交换 n o n d e t e r m i n i s t i cp o l y n o m i a l 非确定性的多项式 o p e ns h o r t e s t p a t hf i r s t开放最短路径优先 p o p u l a t i o n b a s e di n c r e m e n t a ll e a r n i n g基于群体的增量学习 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 协议独立组播 q u a l i t yo fs e r v i c e服务质量 p r o b a b i l i s t i cm o d e l i n ge v o l u t i o n a r ya l g o r i t h m 概率分析进化算法 r e s o u r c e r e s e r v a ti0 np r o t o c o l 资源预留协议 s e r v i c el e v e la g r e e m e n t 业务级别协定 s p a r s e m o d e稀疏模式 v i r t u a lc i r c u i t 虚电路 v i r t u a lc h a n n e lc o n n e c t i o n 虚信道连接 v 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名： 量燮1 3 期：圣女6 ，i ：l q 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：量整导师签名：烂日期：鎏巫主山 南京邮电大学硕士研究生学位论文 日u 雷 近年来，随着通信技术和交换技术的飞速发展，特别是i n t e r n e t 、移动计算和分布式 计算的迅速普及，大量新型的多媒体应用如视频会议、视频点播、远程医疗及远程教学等 越来越广泛，建立一种良好的数据转发机制或通信策略尤为重要。基于这种需要，组播技 术已被应用于多媒体传输中。组播通信将信息从源节点同时向多个目的地址发送，能显著 的减少冗余信息的传递和降低网络资源的消耗。同时，这些分布式多媒体应用还对网络服 务质量提出了许多新要求，比如时延、时延抖动、链路的带宽和节点的包丢失率等。因此， 为了寻求数据的组播路径，过去简单的点对点路由算法已不能满足要求，需要针对组播的 特点设计专门的组播路由算法，找到满足业务o o s 要求的源节点到目的节点的路径。 具有q o s 约束的组播路由问题可以归结为带约束的s t e i n e r 树问题，己被证明是n p 完全 问题，即最优算法无法在多项式时间内完成，因而很多启发式的智能优化算法被应用到该 问题的求解中。 遗传算法( g a ，g e n e t i ca l g o r i t h m ) 是模拟生物进化过程的智能优化算法，适用于 在复杂而庞大的搜索空间中寻找最有解或次优解，目前已被较多地用来计算组播路由。文 献 1 1 将遗传算法用于多o o s 约束的组播路由问题，采用了一种二进制编码的机制使得算 法的编码、解码过程复杂，并且算法的搜索空间随着网络规模增大而急剧增大，算法效率 低。文献 1 8 采用了直观的树型编码，有效克服了前者的不足但是复杂的交叉、变异算 子，导致算法的复杂度很高。文献 2 0 2 2 采用整数队列组成的染色体编码，每个基因代 表了一条从源点到目的节点的路径，是一种较好的编码方式，但是在编码阶段为了求解满 足要求的路径集，使用了具有较高时间复杂度的算法。 b a l u j a ，s 提出了一种基于群体的增量学习( p b i l ) 进化算法，有效结合了简单遗传算 法和竞争学习算法的特点，将进化过程视为学习过程，用学习所获得的知识( 体现为一种 学习概率) 来指导产生后代群体，这种概率是整个进化过程的信息积累，用它来指导产生 的后代将会更加优秀，并且脱离了基于问题而设计的遗传交叉、变异算子，因而在许多问 题中得到成功应用。文献 2 7 ，2 8 将p b i l 进化算法应用于o o s 组播路由问题的求解，但是都 仅能考虑了时延约束条件。 本文使用p b i l 进化算法来解决具有多o o s 约束的组播路由问题，提出了具体的求解 方法，考虑了时延、时延抖动、带宽和包丢失率的约束条件。文中使用了按路径编码的方 式，在编码阶段为了求解备选路径集提出了一种深度优先搜索算法，可以找出源节点与目 的节点之间满足时延、时延抖动和包丢失率约束的路径。基于p b i l 进化算法的多q o s 约 南京邮电大学硕士研究生学位论文前言 束组播路由算法编码简单，易于实旋，仿真实验结果表明它具有较快的收敛速度，同时能 以较大的概率收敛到最优解，是非常有效的。本文还对基本的p b i l 进化算法提出了改进： 在获取每代最优个体时使用局部搜索算法k 一邻域交换法，并对每代最优个体的基因位按取 值的优秀程度采用不同的学习概率修正系数，提高了算法的搜索效率和收敛速度：还引入 了一个恒定的平均概率矢量来指导产生种群的一部分个体，提高了算法的全局收敛性。将 改进的p b l 进化算法应用于q o s 组播路由问题，在仿真实验中与基本的p b i l 进化算法进 行比较，结果表明了改进算法的有效性。 本文的章节安排如下： 第一章主要介绍了与组播通信相关的基本知识。 第二章主要阐述了i p 网络的q o s 及q o s 组播路由问题的基本概念，定义o o s 组播路由问 题的数学模型。 第三章首先介绍t p b i l 进化算法的产生背景及原理，然后将其应用于求解具有多q o s 约束的组播路由问题，并通过仿真实验与基于遗传算法的组播路由算法在性 能上进行了比较和分析。 第四章对基本的p b i l 进化算法进行了改进，提高了算法的搜索效率和全局收敛性。 将改进的算法应用于求解多q o s 约束组播路由问题，仿真实验结果表明了改进 算法的有效性。 第五章对全文内容进行总结归纳，对进一步研究工作进行展望。 南京邮电大学硕士研究生学位论文 第一章组播通信概述 第一章组播通信概述 光纤通信和交换技术的进步大大提高了计算机网络的传输速率，许多新型的通信业务 大量涌现，如电视会议、视频点播、邮件群发、网络游戏、远程教学等。这类业务一般涉 及多个用户，并且对带宽等网络资源的消耗极大。组播( m u l t i c a s t ) 作为优化带宽的一种 重要手段而受到越来越多的关注。 1 1 组播的工作原理 组播( m u l t i c a s t ) 是一种允许一个或多个发送者( 源节点) 同时向多个接收者( 目 的节点) 传输同一份数据包的通信方式。组播源节点把数据包发送到特定的组播组，只有 属于该组播组的地址才能接收到数据包。因为无论有多少个目标地址，在整个网络的任何 一条链路上只传送单一的数据包，所以组播提高了数据传输速率，极大的节省了网络带宽。 常用的通信方式还有另外两种：单播和广播。图1 卜l 图1 卜3 显示了基于这三种通 信方式的网络结构和数据传递过程。 单播( u n i c a s t ) 是指传统的点到点通信方式，在发送者和每一个接收者之间都需要 单独的数据通道。如果一台主机同时给少量的接收者传输数据，一般没什么问题，但如果 有大量的主机希望获得数据包的同一份拷贝时却很难实现，这将导致发送者负担过重、延 迟长、网络拥塞，而且为了保证一定的服务质量还需增加硬件和带宽。 广播( b r o a d c a s t ) 是指在i p 子网内广播数据包，所有在子网内的主机都将收到这些 数据包。广播意味着网络向子网中的所有主机都投递一份数据包，不论这些主机是否乐于 接收该数据包。然而广播的使用范围非常小，只在本地子网内有效，因为路由器会封锁广 播通信；同时广播传输增加了非接收者的开销，即判断是否为自己所需数据包花费的时间 等。 图1 i - 1 单播通信方式的数据传递过程 南京邮电大学硕士研究生学位论文 第一章组播通信概述 图1 卜2 组播通信方式的数据传递过程 图1 1 - 3 广播通信方式的数据传递过程 1 2 组播通信的实现方式 目前网络对组播的支持主要是通过建立是一棵连接源节点和多个目的节点的组播树 来实现的，信息以并行方式沿树枝发送到不同目的节点，降低了传输时延；而且信息只需 在树的分叉处进行复制，这样网络中需要传送的复制信息最少，节省了网络资源。组播树 有两种基本类型：有源树和共享树。 1 2 1 有源树 有源树是组播树最简单的一种形式，有源树的根是组播信息流的来源，有源树的分支 形成了通过网络到达接收站点的分布树( 如图1 2 卜1 、1 2 卜2 ) 。 有源树也有两种形式：一种是最短路径树，它以最短路径贯穿网络，即从源节点到所 有目的节点都是通过最短路，因此被称为最短路径树( s p t ：s h o r t e s tp a t ht r e e ) 。最短 路径树保证了从源节点到每个目的节点为最短路。但全树的费用并不一定是最优的，这里 树的费用是指树中边的费用( c o s t ：这里的费用是一个广义上的费用，它可以根据距离、 信道带宽、平均通信量、通信开销、队列平均长度、测量到的时延和其他一些因素的函数 而计算出来的) 之和。 4 堕室塑皇查兰堡主塑窒生兰垡望兰 兰二童望塑望笪! ! 生 图12 卜1 主机a 的有源树 图1 2 ，卜2 主机b 的有源树 为达到全树的费用最优，因此有第二种形式的有源树，即覆盖所有组播成员的一棵最 优s t e i n e r 树。s t e i n e r 树问题是从图论中引申出来的一个优化问题：在一个连通图中，给 定一个节点子集，要求在图中找到棵覆盖给定节点子集的费用最小的生成树。s t e i n e r 南京邮电大学硕士研究生学位论文 第一章组播通信概述 树的总费用最小，但是从源节点到每个目的节点不一定是最短路。在网络中的每个节点( 实 际是路由器) 都具有组播功能时，求解费用最小的组播树问题与s t e i n e r 树问题是等价的。 如果组中有多个节点存在组播需求，需要为每个节点分别建立一棵以该节点为根的组播 树。这会增加网络管理的开销。 1 2 2 共享树 组播树的另一种形式是共享树( c b t ：c o r e b a s e dt r e e ) 。这里，每个组只计算一棵生 成树其树根( 核心) 靠近组播组的中间部位，要发一个组播消息，主机先将它发往核心， 再由核心沿着生成树发送消息( 如图1 2 2 ) 。采用这种方式，只需要为组播组维护一棵 生成树，能够降低存储开销，但付出的代价是生成的组播树对某些组播源来说可能不是最 优的，从而导致时延增加。还有，共享树可能会将来自多个组播源的流量聚集在靠近核的 部分链路上，造成网络拥塞，降低服务质量。 1 3 组播路由协议 图l _ 2 2 共享树 为了实现组播通信，就必须建立支持组播的路由协议，根据网络中组播成员的分布和 使用的不同，组播路由协议分为两类：密集模式路由协议( d m ) 和稀疏模式路由协议( s m ) 。 6 南京邮电大学硕士研究生学位论文 第一章组播通信概述 1 3 1 密集模式路由协议( d m ) 蹴( d e n s e m o d e ) 路由协议通常用于组播成员较为集中、数量较多、且有足够带宽的网 路环境，比如公司或园区的局域网。因此，蹦路由协议用定期广播组播报文的方法维护组 播分布树。d m 协议只使用源分布树( s p t ) ，组播流量被广播到网络中所有的组播路由器。 蹦路由协议有：b v m r p ，m o s p f ，p i m d m 。 一、距离向量组播路由协议( d v m r p ) d v m r p ：距离向量组播路由协议( 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 0 1 ) 。 这是一种基于距离向量算法的组播路由协议。耳前已基本上被p i m 和s p f 所取代。d v m r p 是m b o n e 呻1 上广泛运用的组播路由协议，它采用距离向量算法。在m b o n e 上采用隧道 ( t u n n e l i n g ) 技术，使组播通信得以在支持组播的子网之间实现。由于m b o n e 的飞速发展， 由d v m r p 而导致的大量路由控制分组定期在网络中的扩散开销限制了网络规模的发展。为 此提出了分层d v m r p ( h i e r a r c h i c a ld v m r p ) ，按照区域分割的方式对m b o n e 进行多层管理， 区域内组播可以按照任何协议进行，而区域之间的组播由边界路由器在d v m r p 协议下进行。 由于采用组播协议的层次叠加，减少了路由控制信息开销。 二、组播开放式最短路由优先协议( m o s p f ) m o s p f ：组播o s p f 协议( m u l t i c a s to p e ns h o r t e s tp a t hf i r s t ) 。m o s p f 是利用点到点 的链路状态数据库，以o s p fv 2 为基础的组播路由协议。由于o s p f 应用d i j k s t r a 算法进行 路由选择，因此每个节点都要保存全网的拓扑信息。所有节点对网络的看法是一致的，它 不需发送任何分组，节点就可根据全网链路状态表计算组中每个信源的组播树，而且各节 点对该树的看法一致。因此，链路利用率比d v m r p 高。为了减少计算量，m o s p f n 以按需执 行算法，即只有当一个节点收到一个信源关于某个组播组的第一个分组时，才执行算法。 这种做法的缺点是对第一个分组带来较大时延。m o s p f 的最大优点是享有o s p f 对网络拓扑 的变动快速反应能力。然而这个能力是以路由器c p u 资源的巨大消耗为基础的。而且随着 网络中组数量的增加，这种消耗也在迅速增加。 三、协议无关组播协议一密集模式( p i m d m ) p i m d m ：协议无关组播协议一密集模式( 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 d e n s e m o d e ) 。它不需要单独的组播协议，利用路由器上单播路由协议的路由表作反向路 径转发检查，由此获得组播分布树。相比于另外两种协议，p i m d m 的开销要小很多，它用 于组播源和目的节点非常靠近、接收者数量大于发送者数量并且组播流量比较大的环境中 效果很好。 南京邮电大学硕士研究生学位论文第一章组播通信概述 1 3 2 稀疏模式路由协议( s m ) 在网路中稀疏分布、网络也没有充足带宽的情况，如广域网环境，可以使用s m ( s p a r s e m o d e ) 路由协议。因此，s m 路由协议采用选择性的建立和维护分布树的方式，由 空树开始，仅当有成员显式的请求加入分布树才做出修改。s m 路由协议有：p i m s m 和c b t 。 一、有核树组播路由协议( c b t ) c b t ：基于中心的分布树协议( c o r e b a s e dt r e e s ) 。协议由以一个中心的路由器为根 构造一个共享分布树，所有的组播流量都经由这个中心路由器转发。 二、协议无关组播协议一稀疏模式( p i m s m ) p i m - s m ：协议无关组播协议一稀疏模式。工作原理与p i m - d m 类似，但专门针对稀疏环 境优化。适用于组播组中接收者较少、间歇性组播流量的情况。不同于p i m d m 的广播方式， p i m - s m 定义了一个集合点( r p ) ，所有的接收者在r p 注册，组播分组由r p 转发给接收者。 三、a t m 网络条件下的对组播路由的支持协议 a t m 论坛定义了a t m 对组播的支持。当前a t m 标准没有对组地址进行规范，信源必须知 道所有组成员的地址，建立点到多点虚电路( v c ) ，成员的加入和离开由信源管理，因而点 到多点v c 不能提供对大多数组通信需求的灵活支持。a t m 论坛给出了两种支持组播的建议 模式，v c 网络模式是建立从信源到组中所有成员的点到多点v c ，当成员的加入和离开之后 需要重建v c 。组播服务器模式指选择一个服务器作为代理，组内每个信源与组播服务器建 立点到点v c 连接。由组播服务器向一个组中的所有信宿建立组播服务器点到多点v c 。组播 服务器接收组中所有信源的数据，交织之后发送到相应点到多点v c 上。v c 网络的通量性能 比组播服务器要好，延迟小，但组播服务器更适合于对组成员的动态管理。 另外一种s m a r t 模式采用了共享a t m 组播树由文献 7 提出，协议通过对给定多点应 用分配一至多个多点到多点a t m 虚通道连接( v c c ) ，构造组播树实现多点间通信。 对于组播的研究早在8 0 年代就已经开始，有许多组播路由协议已经投入使用，像p i m 、 m b g p ( m u l t i c a s tb o r d e rg a t e w a yp r o t o c 0 1 ) 以及d v m r p 等协议的应用都比较广泛。但是目 前还没有一种可靠的组播协议己经具备了处理大范围的组分发、发送者要求的反馈或各种 类型使用路由器应用的能力。 1 4 组播路由算法 为了进行有效的组播通信，确定组播路由是非常关键的。组播路由算法就是用来确定 8 南京邮电大学硕士研究生学位论文第一章组播通信概述 组播树。组播树是通过在每个路由器设置路由表建立的，路由表上给出了为使信息传送到 组成员，此路由器应该选择那个邻接节点。由于网络的动态变化，每个路由器的路由表也 需要定期更新。此外路由表的设置要保证不能有回路的产生。下面对组播路由算法进行介 绍。 1 4 1s t e i n e t 树算法和o b t 算法 根据组播树构造方式的不同，组播路由算法可分为两种：s t e i n e r 树算法和c b t 算法。 在构造组播树时，一般以树的“费用”作为评价组播树性能的标准。组播树的费用是指树 中所有节点和链路费用的总和。这里节点和链路的费用是一个广义的费用，它可以指链路 上的时延、可用资源、带宽、价格等等。在实际应用中，一般要求确定的路由要有效利用 网络资源，为此要求组播树的费用最，j 、。在网络中寻找覆盖给定节点集合的费用最小的生 成树问题在数学上被称为s t e i n e r 树问题，这是一个n p 完全问题，即一般来说，最优算法 无法在多项式时间内完成。因此，需要寻求有效的启发式算法，降低算法难度。在性能上 逼近理论算法。目前，s t e i n e r 树问题的启发式智能算法很多，它们都可用来求解代价最 小组播树，是组播路由算法的一个重要研究方向。 中心树算法是近年来提出的构造组播树的一种新方法，它首先e h w a l l 提出”1 ，以选定 中心为树根，其他组成员按照最短路的原则与中心建立连接，构造成为一棵由所有发送节 点共享的树，c b t 不具备广播特性，即数据只发向明确发出加入组请求的节点，避免了广 播式算法运行时大量无效分组的扩散。由于构造和管理多中, 心c b t 的复杂性，该方法目前 还没有成熟的结论。 1 4 2 静态路由算法和动态路由算法 根据组播树是否随着网络拓扑变化，组播路由算法有静态和动态之分。静态组播路由 算法针对初始组播成员构造一棵组播树，它不能根据当前实际传输量和拓扑变化来做拓扑 选择，而是按初始设计好的路由传送。但真实网络中存在许多动态变化，如网络拓扑结构 的变化，组成员的变化等。因此动态组播路由算法显得非常重要。构造适应组成员动态变 化的算法有三种方式：一种是构造一棵性能优化的初始组播树，成员变化之后对树采取最 小的变化，如文献 8 中的算法，成员的加入通过建立节点到树的最短路由完成；成员的 离开仅删除树叶节点，如果删除产生一个非成员树叶，该算法删除该节点，直到不存在非 成员树叶。另一种是成员变更后，对整个组重新进行路由确定，这将对组中原来成员通信 南京邮电太学硕士研究生学位论文第一章组插通信概述 产生干扰，当成员的变换剧烈时，这种方法是不实用的。文献 9 给出了一种改进算法， 首先节点的加入和离开仿照前面第一种方式实现，但在树的局部范围内，考察节点的加入 和离开对树的累计损伤，当这种累计损伤超过一定限制条件时，在局部范围内重新优化路 由，通过改变限制条件达到树的优化和计算时间、复杂性之间的平衡。第三种是构造一棵 富于弹性变化的次优树，即最短路径树，每个组成员之间相互独立选择最短路由，因此树 的性能不会受到组动态变化的影响。 1 4 ，3 集中式算法和分布式算法 根据组播树的实现方式，组播路由算法又可分为集中式路由和分布式算路由。集中式 组播路由在掌握整个网络的拓扑结构后，确定组播路由。集中式组播路由一般都是源路由 算法( s o u r c e - b a s e dr o u t i n g ) ，即源节点通过某个链路协议获得完整的网络拓扑结构信息， 进行路由的计算。分布式路由不需要每个组成员掌握整个网络的拓扑，每个组成员在只具 有局部信息条件下就可参与路由的确定，这对大型网络的组播路由是十分有利的。 1 5 本章小结 本章首先介绍了组播的工作原理和组播通信的实现具体方式，然后介绍了两大类常用 的组播路由协议，最后分析了已有的组播路由算法，并对其按三种方法进行了分类。 1 0 南京邮电大学硕士研究生学位论文第二章q o s 组播路由问题 第二章q o s 组播路由问题 q o s 组播路由问题涉及了两个方面的问题，一是i p 网络中的组播通信，包括组播通信 的工作原理、路由技术等，这些我们己经在第一章中作了介绍：二是i p 网络中的服务质 量( q o s ) ，我们在本章中将作简要介绍。此外，我们还需要一些网络的相关定义以便对o o s 组播路由的数学模型的建立进行研究，为以后的仿真和测试建立了一个可靠、可行的数学 模型。 2 1i p 网络的服务质量 服务质量( q u a l i t yo fs e r v i c e ，q o s ) 是一种抽象概念，用于说明网络服务的“良好” 程度。在“r f c 2 3 8 6 ”m 1 中定义了：服务质量是“网络在传输流数据时必须满足的一系列 服务需求”。这里，数据流指的是“从源地址到目的地址以一定的服务质量进行传输( 单 播和组播) 的数据流”。由于不同的应用对网络性能的要求不同，对网络所提供的服务质 量期望值也不同。这种期望值可以用一种统一的q o s 概念来描述。在不同应用系统中，q o s 参数集的定义方法可能是不同的，经常使用吞吐量、差错率、端到端延时、延时抖动等网 络性能参数来定义q o s 。比如，对连续媒体传输来说，端到端延时和延时抖动是两个比较 关键的性能参数。多媒体应用，特别是交互式多媒体通信应用对延迟又有严格的限制，不 能超过人所能忍受的极限，否则将会严重地影响服务质量。同样，延时抖动也必须维持在 严格的界限内，否则将会严重地影响人对语音和图像信息的识别。 在早期的计算机网络及分组交换网络中，网络一般只为业务提供“尽力而为” ( b e s t e f f o r t ) 的服务，在这样的网络系统中，所有业务共享并抢占网络资源，业务之间 并没有明确的区分，随着技术的发展。人们发现单一的服务类型并不能满足未来业务的发 展需要，于是提出了服务质量的概念，其出发点是网络区分对待有不同要求的业务。 i n t e r n e t 工程任务组( i n t e r n e te n g i n e e r i n gt a s kf o r c e ，i e t f ) 及许多网络设备厂商提 出了多种解决方案i p 网络中的各种q o s 技术便应运而生。 2 1 1o o s 的分类 服务质量o o s 最早出现于通信领域，用来描述数据传输链路的速率、可靠性等技术特 性。开始时，它只应用于网络底层协议，对上层应用而言是透明的，这对于早期时间要求 不强的应用而言是可以接受的。前面，我们己经介绍了服务质量的基本概念，这里介绍一 塑曼些皇查堂堡主堡至兰堂垡笙苎 下q o s 的分类。 第二章q o s 组播路由问题 通常来说，q o s 可以根据不同的分类标准分为以下两类： 一、从q o s 的严格程度来分类： 1 确定型( d e t e r m i n i s t i c ) q o s 承诺 在通信过程中，提供q o s “硬”保证，确保通信各方协商好的各q o s 参数值，不允许有 任何违背，否则可能会造成严重后果。这类服务一般用于硬实时应用。例如，远程医疗诊 断这样的分布式多媒体应用，就需要这类服务来支持诸如患者的x 射线影像数据的实时无 差错传送。 2 统计型( s t a t i s t i c a l ) q o s 承诺 在通信过程中，提供q o s “软”保证，允许对通信各方协商好的各q o s 参数值有一定比 例的违约，适合于软实时应用。例如，对于分布式多媒体信息点播服务中的影片点播来说t 用户通常可以容忍一定数量的比特错和帧丢失。 3 尽全力型( b e s t e f f o r t ) q o s 承诺 与数据报服务同义，不提供任何o o s 保证。目前由于带宽的限制，广域网( 如i n t e r n e t ) 中的分布式多媒体服务多属于这类服务。 二、从服务质量的实现层次来分类： 通常，不同的应用对q o s 的要求是不同的，不同的q o s 应当通过不同的q o s 参数来描述， 并且用户能够适应这些q o s 参数来定量或定性地说明各自所需的q o s 。在一个多媒体通信系 统中，通常采用层次化的q o s 参数体系结构来定义说明q o s 参数，整个i n t e r n e t 从实现服务 的角度可分成四个主要层面，参见图2 1 1 。 应片j 层则根据镞要，选择不同豹l p 服务类登， 应用层 实现面向用户的q o s 传输层提供可选择和定义的q o s 参数 q i p 网络通过建立同样的q ! o s 服务模型。屏蔽 o 网络层 s 物理嘲络的细节，实现蕊向应用的q o s 服务 数据链路层 圈2 1 ，1q o s 的分层模型 下面将q o s 这种分类方式中的各个层次作详细的介绍。 南京邮电大学硕士研究生学位论文 第二章q o s 组播路由问题 应用层 应用层q o s 参数是面向端用户的，应当采用直观、形象的表达方式来描述不同的q o s ， 供端用户选择。例如，通过播放不同的演示质量的音频视频片断作为可选择的q o s 参数， 或者将不同的音频视频的传输速率分成若干等级，每个等级代表不同的q o s 参数，并通过 可视化方式提供给用户选择。 传输层 传输层协议主要提供端到端的、面向连接的数据传输服务。通常，这种面向连接的服 务能够保证数据传输的正确性和顺序性，但以较大的网络带宽和延迟开销为代价。传输层 q o s 必须支持q o s 的传输层协议提供可选择和定义的q o s 参数。传输层q o s 参数主要有：吞吐 量、端到端延时、端到端延时抖动、分组差错率和传输优先级等等。国际标准化组织( i s o ) 在1 9 8 6 年颁布的i s o o s i8 0 7 2 标准中明确地定义了传输层参数： 建立连接延迟：用户发出连接请求到接收到连接确认之间的时间间隔； 建立连接失败率：在最大建立连接延迟内不能建立连接的可能性； 吞吐量：每秒接收的用户数据字节数； 传输延迟：发送方发出数据到接收方接收到该数据所经历的时间间隔； 固有差错率：在取样时间段内丢失和出错的信息数占总信息数的比率； 传输失败率：在数据传输阶段因各种原因所造成失败的信息占总信息数的比率； 释放连接延迟：一方发出释放请求到对方执行释放之间的时间间隔： 保护：用于说明建立安全连接需求的参数，如没有窃听或修改： 优先级：规定在该连接上传输的优先级； 弹性：用于说明传输层自动终结的可能性。 i s o o s i 定义的o o s 参数是针对传输层面向连接传输服务的，大部分q o s 参数用于数据传 输阶段。由于该标准制订的时间较早，没有过多地考虑实时多媒体应用的问题，因此在该 标准中没有定义延时抖动等实时应用特有的指标。 网络层 网络层协议主要提供路由选择和数据报转发服务。通常这种服务是无连接的，通过中 间点( 路由器) 的“存储一转发”机制来实现。在数据报转发过程中，路由器将会产生延时 ( 如排队等待转发) 、延时抖动( 选择不同的路由) 、分组丢失及差错等。网络层q o s 同样也 要由支持s 的网络层协议提供可选择和定义的q o s 参数，如吞吐量、延时、延时抖动、分 组丢失率和差错率等。 网络层协议主要是i p 协议。其中i p v 6 可以通过报头中优先级和流标识字段支持q o s 。 南京邮电大学硕士研究生学位论文第二章q o s 组播路由问题 一些连接型网络层协议，如r s v p 等可以较好地支持q o s ，其q o s 参数通过保证服务( g s ) 和被 控负载服务( c l s ) 两个q o s 类来定义。它们都要求路由器也必须具备相应的支持能力，为所 承诺的q o s 保留资源( 如带宽、缓冲区等) 。 数据链路层 数据链路层协议主要实现对物理介质的访问控制功能，也就是解决如何利用介质传输 数据问题，与网络类型密切相关，并不是所有网络都支持q o s ，即使支持q o s 的网络其支持 程度也不尽相同。各种e t h e r n e t 都不支持q o s 。t o k e n r i n g ，f d d i 和i o o v g - a n y l a n 等是通 过介质访问优先级定义q o s 参数的。a t m 网络能够较充分地支持q o s ，它是一种面向连接的 网络，在建立虚连接时可以使用一组q o s 参数来定义q o s 。 国际电信联盟( i t u ) 制定了有关a t m 网络q o s 参数，它允许用户指定如下的参数： 峰值信元速率( p c r ) ：用户发送信元的最大瞬间速率； 长期承受信元速率( s c r ) ：经过一个长时期测量到的平均信元速率；