（计算机软件与理论专业论文）基于遗传算法的qos组播路由算法.pdf

华东师范大学硕士学位论文 摘要 随着币断增欧的分布式多媒体应用的需求，以及i n t e r n e t 上商业化应用的飞速发展， 对网络的服务质量( q o s ：q u a l i t yo f s e r v i c e ) 提出了更高的要求，高效的q o s 支持变得越 米越重要。i e t f 已经提出了许多服务模型和机制米满足对q o s 的需求，q o s 路由 ( q o s b a s e dr o u l i n g ) 就是其中的关键技术之一。 编播是指将同一信息从源结点传送到网络中多个结点( 不一定是网络中所有结点) 。实 现纲播的一般方式是建立组播树，组播树的优点在于：首先，信息以并行方式沿着树枝发送 到不同的组播终点从而降低了信息传递的时延；其次，信息的复制只在树的分支处进行， 冈此网络中需要传送的复制信息量最少，能够节约网络带宽资源，降低网络负载，减少拥塞， 所以纠播成为目前研究最多、应用最广的网络信息传输方式。组播路由算法主要用来建立一 棵性能良好的组播树，并使它能够满足各种业务的服务质量需求。本文主要研究就是o o s 绢播路由算法，即建立满足媒体传输服务质量需求的纽播树。 本文首充分析了组播和组播路由选择技术的原理，随后介绍了遗传算法的基本思想和运 行过程。组播路由算法通常采用启发式技术，但仿真结果表明，这些启发式算法要么太复杂 而旋以求解，要么太费时而不能实际应用。 遗传算法则是近几年提山的一种模拟生物界自然选择和遗传机制，具有简单高效、高度 并行、随机和白适应的新型最优化搜索算法，非常适用r 纽播路由。本文在总结了别人的工 作的前提r ，对带宽、延时，延时抖动和包丢失率约束以及费用最小的q o s 组播路由问题进 行分析，抽象出o o s 组播路由模型的基础上，提出了一种新的基于遗传算法的q o s 组播路由 算法。该算法具有以f 特点： 预处理机制，这样简化了算法设计的难度，同时也优化了算法的性能，减少了算法搜索 的空间； 树型结构编码，这样就可以用树的任何一种数据结构来描述算法中染色体的结构，既减 少_ 厂编码空间，也省略了解码操作； 启发式初始种群生成和交叉策略，该交叉策率采用了启发式方法，兼顾了各种0 0 s 度量， 使后代能尽革继承好的性能( 满足q o s 约束且费用较小) ，加快了算法收敛的速度； 指导性变异过程，有效的改善了算法的性能，既有利于算法跳出局部最优解，也有利于 算法向性能好的方向转化( 满足q o s 约束且费用较小) 。 而且仿真结果也表明该算法快速有效，并且在性能和效率方面都要优于文中提到的其它 现存的算法。 关键词：组播，组播路由，q o s ，遗传算法 华东师范大学硕士学位论文 a b s t r a e t a sar e s u l to ft h ee m e r g e n c eo fm a n yk i n d so fh i g h - s p e e dc o n a m u n i c a t i o n s y s t e m sa n di n c r e a s i n gd e m a n do fd i s t r i b u t e dm u l t i m e d i aa p p l i c a t i o n s ，e 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 ) h a sb e c o m em o r ea n dm o r ee s s e n t i a l m a n ys e r v i c em o d e l sa n dm e c h a n i s m sh a v eb e e np u tf o r w a r db yi e t ft om e e t i n g q o sr e q u i r e m e n t ， m u l t i c a s ts e r v i c ei sak e yo n eo ft h e ma n di sb e c o m i n gak e y r e q u i r e m e n to fc o m p u t e rn e t w o r ks u p p o s i n gm u l t i m e d i aa p p l i c a t i o n m u l t i c a s t i n gc o n s i s t so fc o n c u r r e n t l ys e n d i n gt h es a m ei n f o r m a t i o nf r o mas o u r c e t oas u b s e to fa l lp o s s i b l ed e s t i n a t i o n si nac o m p u t e rn e t w o r k m u l t i c a s tu t i l i z e sat r e e d e l i v e r ys t r u c t u r e o nw h i c hd a t ap a c k e t sa r ed u p l i c a t e do n l ya tf b r kn o d e sa n da r e f o r w a r d e do n l yo n c eo v e re a c hl i n k t h i sa p p r o a c hm a k e sm u l t i c a s tr e s o u r c e e f f i c i e n t i nd e l i v e r i n gd a t at oa g r o u po fm e m b e rs i m u l t a n e o u s l ya n dc a r ls c a l ew e l lt os u p p o r t v e r yl a r g em u l t i c a s tg r o u pt h i sd i s s e r t a t i o nf o c u s e so nt h ea l g o r i t h m st oc o n s t r u c t l o wc o s tm u l t i c a s tr o u t i n gt r e ew i t hq o sr e q u i r e m e n t s t h i sd i s s e r t a t i o n a n a l y s e st h ep r i n c i p l eo fm u l t i c a s t a n dm u l t i c a s t r o u t i n g t e c h n o l o g yg e n e r a l l ym u l t i c a s tr o u t i n ga l g o r i t h m su s eh e u r i s t i ct e c h n o l o g y , b u tt h e s i m u l a t i o nr e s u l th a ss h o w nt h a tm o s to ft h ep r o p o s e dh e u r i s t i ca l g o r i t h me i t h e rw o r k t o os l o w l yo rc a n n o tc o m p u t ed e l a y c o n s t r a i n e dm u l t i c a s tt r e e sw i t hl o wc o s t s f o rt h i sr e a s o n ，m e t h o d sb a s e do ng e n e t i cc o m p u t a t i o nm a yb eo fg r e a th e l p i n t h i sd i s s e r t a t i o n ，w es t u d yt h eb a n d w i d t h ，d e l a y ，d e l a yj i t t e r ，a n dp a c k e tl o s s c o n s t r a i n e dl e a s t c o s tm u l t i c a s tr o u t i n gp r o b l e m ，a n dp r o p o s ean e wh e u r i s t i cg e n e t i c a l g o r i t h m t h ea l g o r i t h mh a st h ef o l l o w i n gc h a r a c t e r i s t i c s ： t h ep r e p r o c e s s i n g b yw h i c hw ec a ng r e a t l ys i m p l i f i e st h eq o sm u l f i c a s tr o u t i n g p r o b l e m ，o p t i m i z e st h ep e r f o r m a n c eo ft h eg e n e t i ca l g o r i t h ma n dd e c r e a s e st h es e a r c h s p a c e ； t h et r e es t r u c t u r ec o d i n gm e t h o d ，b yw h i c hw ec a nu s ea n yd a t as t r u c t u r eo ft h e t r e et od 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 e ，a n do m i t st h ec o d i n ga n dd e c o d i n g p r o c e s s ； t h eh e u r i s t i cc r o s s o v e rt e c h n i q u e ，i t ，i nw h i c hq o sm e t r i c sa r ec o n s i d e r e d ，c a n s p e e d su pt h ea l g o r i t h mc o n v e r g e n c ea n dd e l i v e r st h eg o o dc h a r a c t e r i s t i c st ot h e o f f s p r i n g t h ei n s t r u c t i o n a lm u t a t i o no p e r a t i o n b yw h i c hw ec a ni m p r o v et h ep e r f o r m a n c e i i 华东师范大学硕士学位论文 o ft h eg e n e t i ca l g o r i t h mb e c a u s ei ti se f f e c t i v et oc o n v e r tt h ea l g o r i t h mf r o mal o c a l o p t i m a lp o i n ti n t og o o ds t a t e f i n a l l yw ec o n d u c ts i m u l a t i o ns t u d i e st oe v a l u a t eo l j ra l g o r i t h m sa n ds t r a t e g i e s a n dc o m p a r ew i t ho t h e rs i m i l a ro rr e l a t e da p p r o a c h e s ，a n dw es e ei m p r o v e do r c o m p a r a b l ep e r f o r m a n c ei nm o s tc a s e s k e yw o r d s ：m u l t i c a s t i n g ，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 i i 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究 成果。据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经 发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在 文中作了明确说明并表示谢意。 作者签名：鲢日期：銎墅生! 兰：兰 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有 权将学位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要 汇编出版。保密的学位论文在解密后适用本规定。 学位论文作者签名：弓g 己蒺 导师签名 毒 日期：至盟绝垡：2 二日期： 鱼竺圭 o r i g i n a l i t yn o t i c e i np r e s e n t i n gt h i st h e s i si np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o rt h em a s t e r sd e g r e ea t e a s tc h i n an o r m a lu n i v e r s i t y ，1w a r r a n tt h a tt h i st h e s i si s o r i g i n a la n da n yo ft h et e c h n i q u e s p r e s e n t e di nt h et h e s i sh a v eb e e nf i g u r e do u tb ym e an yo ft h er e f e r e n c e st ot h ec o p y r i g h t ， t r a d e m a r k ，p a t e n t ，s t a t u t o r yr i g h t ，o rp r o p r i e t yr i g h to fo t h e r sh a v eb e e ne x p l i c i t l ya c k n o w l e d g e d a n di n c l u d e di nt h er e f e f e n c e ss e c t i o na tt h ee n do f t h i st h e s i s s i g n a t u r e ： c o p y r i g h tn o t i c e fh e r e i na g r e et h a tt h el i b r a r yo fe c n us h a l lm a k ei t sc o p i e sf r e e l ya v a i l a b l ef o ri n s p e c t i o n 【f u r t h e ra g r e et h a te x t e n s i v ec o p y i n go f t h et h e s i si sa l l o w a b l eo n l yf o rs c h o i a r l yp u r p o s e s ，i n p a r t i c u l a r , s t o l i n gt h ec o n t e n to f t h i st h e s i si n t or e l e v a n td a t a b a s e s ，a sw e l la sc o m p i l i n ga n d p u b l i s h i n gt h et i t l ea n da b s t r a c to f t h i st h e s i s ，c o n s i s t e n tw i t h ”f a i ru s e a sp r e s c r i b e di nt h e c o p y r i g h tl a wo f t h ep e o p l e sr e p u b l i co f c h i n a s i g n a t u r e ： 华东师范大学硕士学位论文 第一章绪论 本章主要对组播技术的产生背景、发展历史、技术优点以及其应用前景加以描述，最后 介绍了本文所作的主要工作以及本文的内容安排。 1 1 组播产生的背景 在电子通信时代的早期就有点对点和点对多点的通信电话电报就是较为典型的点对点 通信，而无限收音机和电视机实现了本地多点通信，长途多点通信直到通信卫星应用后才得 以实现，但只是在主干网上。这些多点通信只是从源向接受者发送数据，几乎没有接受者的 反馈信息，所以从本质上说还是非常简单。 如今社会已经进入信息时代，毫无疑问i n t e r a c t 将成为信息社会的主要传播媒体。随 着计算机网络技术飞速发展，网络功能日益强大，网络用户的数量急剧增加，而且各种各样 的网络服务争相涌现，许多实时和多媒体应用例如视频会议、远程教学、大规模协作计算、 数据分发和网络游戏等成为信息传送的主要组成部分。这些新型应用都依赖于从一个主机向 多个主机或者从多个主机向多个主机发送同一信息的能力，并且在i n t e r n e t 上分发的数目 可能达到数十万台。 组播是一种允许单个或多个发送者( 组播源) 发送单一的数据到多个接收者( 一次，同 时) 的网络技术。组播源把数据发送到特定的组播组，只有属于该组播组的成员才能接收到 该数据，冈此可以大大的节省网络带宽，而网络带宽正是制约实时和多媒体应用发展的主要 瓶颈，所以组播技术成为研究和应用的热点，成为解决带宽瓶颈的法宝。 1 2 网络的数据传输方式 数据要从发送者发送到接收者，首先需要确定传输路由。不同的通信方式，其确定传输 路由的方法也不同，如今计算机网络的通信方式主要有以f 几种： i ) 单播( u n i c a s t ：p o i n tt op o i n t ) ，点对点的通信方式。 2 ) 组播( m u l t i c a s t ：p o i n tt om u l t i p o i n t ) 点对多点的通信方式。 3 ) 广播( b r o a d c a s t ：p o i n t t oa l lp o i n t ) ，点对所有点的通信方式。 单播传输：在发送者和每一个接收者之间实现点对点的连接，因此如果一个发送者需要 同时为多个接收者传输相同的数据时，必须为每一个接收者发送一份相同的数据拷贝，这将 导致发送者的负担沉重、延迟长以及造成网络拥塞，而且为了保证一定的服务质量需要增加 硬件和带宽。单播通信一般采用d i j k s t r a 提出的最短路径算法( s h o r t e s td a t ha l g o r i t h m ) 或 华东师范大学硕士学位论文 b e l h n a n f o r d 算法建立发送者和每一个接收者之间的数据通道。对于传统的w e b 应用 ( h t t p 、f t p 和e m a i l 等数据业务) 来说，服务器可以为每一个用户建立一个单独的连 接，即采用单播通信。单播数据传输过程如图1 1 所示： 图1 i 单播方式 组播传输：在发送者和多个接收者之间实现点对多点的网络连接。如果一个发送者需要 同时为多个接收者发送相同的数据，只需发送份数据，这样就提高了数据传送效率，减少 了土干网络对带宽的要求以及出现拥塞的可能性。组播数据传输过程如图1 2 所示： 图1 2 绢播方式 j 。播传输：是指在整个子网内广播数据。所有在子网内的主机都将收到该数据，而不管 这些主机是否需要该数据。广播通信很容易引起网络拥塞，而且会增加1 接收者的开销，一 2 华东师范大学硕士学位论文 股路由器都会禁止广播通信，因此广播的应用范围非常小，只能在本地子网内有效。广播数 据传输过程如图1 3 所示： 1 4 组播的发展历史 图1 3 广播方式 在8 0 年代早期，组播主要限制在局域网环境，许多局域网技术如以太网和令牌环网等 对组播提供较好的支持，这也就是说，通过桥扩展局域网和互联网都不支持组播。直到8 0 年代后期，在研究了开放最短路径优先( o s p f ) 协议莆嚼由信息协议( r i p ) 等i p 路由协 议之后，s t e v ed e e r i n g 在他的博士论文中指出基丁数据包的互联网单播机制完全可以扩展 刚术支持组播，奠定了组播的网络体系结构和路由协议的基础，该文也成为i n t e m e t 组管 理协议( i g m p ) 的原型。 随后组播主干网( m b o n e ；m u l t i c a s t b o n e ) 1 2 1 问世，并且i e t f ( i n t e m e t e n g i n e e r i n g t a s k f o r c e ) 在1 9 9 2 年3 月利用它成功举行了一次网络会议从这以后组播技术引起了人们的广 泛关注，并对它的各方面进行了深入的研究。 1 9 9 4 年3 月，形成了对o s p f 协议的扩展协议m o s p f ： 1 9 9 6 年11 月，出现了对于基于u n l 3 0 3 1 的a t m 组播网络支持协议： 1 9 9 7 年9 月，有核树( c b t v 2 ) 组播路由体系结构形成： 1 9 9 7 年11 月，互联网组管理协议i g m p v 2 得到i e t f 的批准，成为标准： 1 9 9 8 年7 月，在制定l p v 6 地址体系标准是，确定i p v 6 组播地址分配方案，这位组播技 术在f 一代i n t e m e t 上的应用做出了必要的准备： 1 9 9 9 年1 0 月，互联网管理协议i g m p v 3 得到i e t f 的批准成为标准。 1 5 组播技术的优点 组播技术的优点主要体现在以下几个方面：带宽、服务器负载和网络负载。 带宽 华东师范大学硕士学位论文 应用组播技术分发信息可以从本质上减少对整个网络带宽的需求。如果一个发送者给多 个接收者同时发送相同的数据，单播传输方式需要在发送者和每一个接收者之间实现点对点 的网络连接，并且需要为每一个接收者发送一份数据的拷贝，所以带宽需求将随着接收者的 增加而增加。而组播技术则不同，发送者只需发送一份数据，数据只在交叉处进行复制，这 样每条链路上只有一份数据拷贝在传输，所以带宽需求不会随着接收者的增加而增加。 2 服务器负载 如前所述，单播传输方式需要为每一个接收者发送一份数据拷贝，因此当接收者数目增 加，服务器的负载也增加。而组播只需发送一份数据拷贝，服务器的负载不会随着接收者数 目的增加而增加。 3 网络负载 当将相同的数据传送到多个接收者时，很明显组播对带宽的需求少，减少了网络出现拥 塞的可能性，这样就降低了网络的负载。 1 6 组播技术的的应用前景 由tc f 捅技术具有“一次发送，多点传输”、节省带宽以及按组播组接收数据的优点和 特性，因此组播技术在网络环境中有着十分广泛的应f e | = j ，f 面予以介绍。 ( 1 ) 数据分发：数据分发主要利用组播技术“一次分发，多点传输”的特性，数据中 心利用组播技术，只需一次就可以将数据发送到多个目的地址，这样就省去了重复传输的工 作量。为保证数据的可靠传输，在传输数据的时候要使剧像文件传输协议( f t p ) 一样的组 播文件传输协议( m f t p ) 。 ( 2 ) 实时数据传播：向大量的主机组传输实时数据是使组播技术深受欢迎的一个应用 领域。一个典型的例子是将股票信息实时发送到交易火厅的工作站。 ( 3 ) 游戏k r i 仿真：组播可以用于有大量参与者的游戏和仿真，参与的p c 机或工作站 只需进入组播组，就可以开始发送和接受游戏及仿真数据，通过不同的组播组可以将游戏加 入者分为不同的游戏空间。 ( 4 ) 多媒体应用：多媒体是当前组播技术的最重要的应用领域，随着宽带网络技术和 多媒体技术的发展，利f i ； j 网络来传输多媒体数据越来越普遍，例如多媒体会议系统，视频点 播( v o d ) 系统等。 4 华东师范大学硕士学位论文 1 7 本文的主要工作 随着宽带网络技术的发展出现了各种实时和多媒体应用，它们对q o s 都提出了较高 的要求，并且这些应用大多可以采用组播技术来提高对网络资源的利用率，因此如何解决带 q o s 约束的组播路由问题已成为多媒体信息传输的一项关键技术。 多约束条件下的组播路由问题是n p 完全问题【3 1 ，对这类问题，采用传统的路由算法难 以求解，这就使得它成为宽带i p 技术的一个难点。近年来有不少学者对这个问题进行了深 入研究，但是许多研究都集中在采用启发式的搜索算法来求解一棵完全满足q o s 约束的组 播树【4 “】，主要有如下一些： 1 9 9 3 年，k o m p e l l a 等【4 l 首次提出了带时延约束的绢播路由问题，并且给出了相应的算 法( k p p 算法) 同时将其推广到分布式环境，但是此算法的时间复杂度相当高，而且在分 布式环境r 易于阻塞。 t 9 9 5 年，z h u 等【6 】提出了b s m a 算法，此算法是目前所提出的算法中求得组播树的费 用晟小的一个，但是该算法的复杂度相当高，同时算法本身也很复杂。 1 9 9 5 年，s u n 等7 1 提出c d k s 算法，该算法通过一个合并过程来保证试验的要求，它的 复杂度不高，并且得到的组播树费用较小，仅次于甲算法和b s m a 算法，综合性能较好， 但是由于存在合并的过程，使其难于在分布式环境下部署。 1 9 9 7 年，g e r o g e 等1 首次提出了带时延约束及时近抖动约束的算法，但该算法并没有 考虑对代价的优化而且其复杂度也相当高。 由上所述，启发式算法的效率不是很高，特别是随着网络结点和链路数量的增加其计 算时间代价也随之急剧增加。s a l a m a 等 9 1 对这些启发式算法进行了仿真试验，研究结果也证 明了这一点。 遗传算法是近年来提出的一种新型的优化算法，它具有并行搜索、群体寻优、自适应等 特点，已经广泛应用于解决各种具有n p 完全问题。 对t - q o s 组播路由问题，近年来一些学者采用遗传算法来解决此问题，提出了一些算 法，主要有下面一些： 1 9 9 5 年，r a v i k u m a r 等【l 目针对延时约束费用最小的组播路由问题，提出了一种遗传算 法，但该算法容易陷入未成熟收敛，而且文中也没有提出任何措施来抑制算法束成熟收敛现 象算法的精度不好。 1 9 9 9 锑1 2 0 0 0 年，x i a n g 等和何小燕等1 分别提出了一种通用的遗传算法，但是这 两个算法都采用n x n 的一维二进制编码机制( 其中n 为网络结点数) ，这种编码模式使 得算法编码、解码过程复杂，并且算法的搜索空间随网络规模的增大而急剧增大，算法效率 很低。 1 9 9 9 年，s u n 等【” x i j - e s b e n s e n 等 1 4 魄出的算法进行了扩展，提出一种求解延时约束费 华东师范大学硕士学位论文 川最小的组播问题的遗传算法，但是在其解码过程需要解决另一个n p 完全问题( 一种确定 性的时延约束费用最小组橘路由算法【”】) ，大大提高了算法的复杂度，而且它假定所有组 捕终点的延时相同，这也大大限制了算法的应用范围。 1 9 9 9 年，z h a n g 等“1 对于延时约束费用最小的组播问题提出一种遗传算法，但与文献 1 3 一样，假定所有组播终点的延时相同，这大大限制了算法的应用范围。 2 0 0 1 年，千应征等【”1 对文献 1 2 提出的算法进行了改进，针对带宽时延约束费用最 小的壬斤播路由问题提出了一种效率较高的遗传算法但其交叉和变异算法还是过于复杂。 本文的所作的主要工作是： 在总结了别人所作的工作的基础上，本文研究了带宽、延时、延时抖动和包丢失率约束 以及费用最小的q o s 组播路由，并且针对该问题给出了q o s 组播路由模型，随后提出了一种 新的基丁遗传算法的q o s 组播路由算法。该算法有以一f 主要特点： ( i ) 采用预处理机制，有效地减少了算法编码空间和搜索空间，显著地提高了算法的搜 索效率： ( 2 ) 采用树型结构编码机制，简化了编码操作，省略了复杂的解码过科： ( 3 ) 启发式初始种群生成和交叉策略，加快了算法收敛的速度； ( 4 ) 指导性交异过程，既能使算法迅速地跳出局部最优解，也能使算法向性能好的方向 转化，进而达到全局最优解。 在第六章中我们对本文提出的算法进行了仿真实现，并与目前所提出的一些性能较优的 算法【6 _ ” ”1 进行了比较，结果也表明，本算法快速有效，并且性能和效率都优于其它现存 算法。 1 8 本论文的内容安排 本文的内容安排如下： 第一章绪论，主要对组播技术的产生背景、发展历史、技术优点以及其应用前景加以 描述井介绍了本文所作的主要 作和本文的内容安排。 第二章组播路由选择技术基础，主要对组播技术所涉及的基础理论加以综述，包括组 播地址、组播路由选择方式、组播路由算法以及组播路由协议。 第三章遗传算法基本原理，本章主要介绍遗传算法的基本原理和方法，包括编码方法、 群体设定、适应度函数和遗传操作等问题。 第四章相关算法及研究现状，主要介绍了一些现存的q o s 组播路由问题的相关启发式 算法和遗传算法，总结了别人所做的工作。 第五章本文提出的基于遗传算法的组播路由算法，针对q o s 组播路由问题，给出了带 宽、i 正时、延时抖动和包丢失率约束以及费用最小的q o s 组播路由模型并在此基础上提出 了一种新的启发式遗传算法。 6 华东师范大学硕士学位论文 第六章实验仿真和研究，对本文提出的算法进行了仿真实验和性能分析，并将本文算 法! _ 目前所提出的一些性能较优的算法进行了比较。 7 华东师范大学硕士学位论文 第二章组播路由技术原理 本荦主要对组播技术所涉及的理论加以综述，包括组播地址、组播路由选择方式、组播 路由掉法以及组播路由协议。 2 1 组播地址 绢橘地自l 不像单播地自 那样唯一的标示单个主机，而是指定了一个士机组。在i p 地址 方案中专为组播划分了一个地址范围，在i p v 4 中为d 类地址，范围从2 2 4 o ，o o 到 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 ，用于 局域网路由器不转发属于此范围的i p 包) 、预留组橘地址( 2 2 4 0 1 0 2 3 8 2 5 5 2 5 5 2 5 5 ， 川r 全球范围或网络协议) 、管理权限组播地址( 2 3 90 00 2 3 9 2 5 5 2 5 5 2 5 5 ，组织内部使用， 州丁限制组播范围) ：在i p v 6 中把组播地址扩展为1 2 8 位，扩展后的地蚍除了增大了表示范 闱外还为组播地址提供了许多新的标示功能，丰富了地址的内容。图2i 为i p v 4 和i p v 6 的组播地址格式，图2 2 为i p v 6 中特殊域的定义。 i p v 4 组播地自e 格式 b i t012343 1 1 1 10 组标示符 i p v 6 组播地址格式 b i t 078i l1 2151 61 2 7 图2 ，1 i p 组播地址格式 华东师范大学硕士学位论文 域值含义 0 0 0 0 永久组播地址 f l a g s o 0 0 1动态组播地址 0 0 0 l 本地结点 0 0 1 0 本地链路 0 1 0 l 本地网点 s c o d e 1 0 0 0本地组织 1 l l o 全局组播地址 其他保留或来指定 2 2 组播路由选择方式 图22 i p v 6 中的特殊城定义 由于一个组播组的成员可以分布在互联网的任何角落所以为了止绸播源发出的数据能 到达绢播组的所有成员，组播路由的选择方法十分重要。目前组播路由方式主要有扩散方式、 分圳寻址方式、多目的地寻址方式和基于生成树的转发方式，下面将分别讨论各种方式的原 理和优缺点。 1 扩散方式 扩散方式是最简单的组播路由选择方式，其基本原理如下：发送者把组播数据发送到所 有的出链路，每个网络结点接收到组播数据后，首先检商组播数据是否是第一次收到，如果 是第一次收到，就将组播数据发送到本机的所有接口上( 除了收到组播数据的接口) ，否则 就丢弃它，最终组播数据被发送到整个网络。由于采用上述传输方式，因此即使组播数据出 现传输错误，只要还存在一条到接收者的链路，接收者也都能收到组播数据。但由于组播数 据被发送到整个网络，然而只有组播成员才接收它，并且要对组播数据进行“首次收到”检 测，这需要维护一个最近通过的数据列表，对于高速网络而言，“首次收到”列表将会很长， i i 川相肖火的内存，因此这种方法虽然简单、可靠，但是它非常浪费网络带宽资源，而且容 易造成网络拥塞。 2 分别寻址方式 9 华东师范大学硕士学位论文 分别寻址方式的基本原理如f ：采用点到点的通信方式来支持多点通信应用，这也是人 们最早在分组通信网络上实现组播通信应用的方式。发送者向每个接收者分别发送数据，有 多少个接收者，发送者就要将相同的数据发送多少次，这种方式除了浪费网络带宽外，还增 加了发送者的负担，并且造成接收者信息接收不同步。 3 多目的地寻自h 方式 多目的地寻址方式的基本原理如下：发送者使用可变长度的分组头来发送数据，分组的 目的地址域内有多个目的地址( 即接收者的地址) 。采用这种方式，虽然发送者只需发送一 次分组，但接收者的数目有限而且增加了带宽和路由器的负担，并且其与已有网络的兼容性 非常差。 4 基与生成树的转发方式 基与生成树的转发方式的基本原理如下；构造一颗覆盖发送者和接收者的组播路由树， 发送者只需要发送一次数据。然后通过组播树来转发，数据以并行的方式沿着树枝发送到不 同的接收者，而且数据只在树的分叉处被复制，直至每一个接收者。显然，这种方式在传递 信息的过程中，尽可能共享链路，使网络传送的信息最少。因此节省了网络带宽资源，提高 了每次组播通信时的资源利用率，减少了发生网络拥塞的可能性，降低了网络负载。并且减 轻了发送者的负担，而且它降低了数据传输的时延，有利于使接收者实时、同步的接收信息， 所以对于组播路由问题常采用这种转发方式。 一般组播路由树有两种类型【i ”，一种是有源树，另一种是共享树。有源树的根是组播 信息流的来源，有源树的分枝形成了通过网络到达接收站点的分布树。有源树也有两种形式， 一种是最短路径树( s p t ：s h o r t e s t p a t h t r e e ) ，它以最短路径贯穿网络，即从源结点到所有 组播组成员的路径都为最短路径。虽然最短路径树保证了从源结点到每个组播组成员的路径 都为最短路径，但是全树的费用并不一定是最优的，这里树的费用是指树中所有边的费用 ( c o s t ：这里的费用是一个广义的费用，它可以根据距离、信道带宽、平均通信量、通信开 销、队列平均长度、测量到的时延和其他一些因素的函数计算出来的费用) 之和。为了 达到全树的费用最优，因此有了第二种形式的有源树，即覆盖所有组成员的一颗最优s t e i n e r 树”，s t e i n e r 树问题是从图论中引申出来的一个优化问题：在一个连通图中，给定一个结 点子集，要求在图中找到一棵覆盖给定结点子集的费用最小的生成树。s t e i n e r 树的总费用 最小，但是从源结点到每个组成员的路径不一定是最短路径。 有源树必须为每一个组播源构建一棵组播树，由于不同的组播源发出的数据包被分散到 各自分离的组播树上，因此采用有源树有利于网络中数据流量的均衡，所以有源树有利于流 量大、时延性能要求较高的实时多媒体应用。有源树的缺点是：要为每一个组播源构建各自 1 0 华东师范大学硕士学位论文 的分布树这样的话，当数据流量不大时，构建有源树的开销相对较人。 另一种形式的组播路由树是共享树或中心树( c b t ：c o r e b a s e dt r e e ) i 皿。j ，每个组只 计算一棵生成树，其树根( 核心) 靠近组播组的中间部位，要发一个组播消息，主机先将它 发往核心，再由核心沿着生成树发送消息到其他的成员。 可以看出，与有源树相比，共享树可以减少它的计算和存储开销，但是一般共享树的费 用比有源树要大2 倍以上，而且如果核心是组播成员的话，其代价会达到有源树的3 倍以上， 并且共享树还存在核心的选取和维护较为困难的问题口。 2 3 组播路由算法 为进行有效的组播通信，确定组播路由是非常关键的，组播路由算法就是用来确定组播 树的。组播树是通过在每个路由器设置路由表来建立的，路由表上给出为使信息送到组播组 成员，此路由器应该选择哪个邻接结点的信息。由于网络的动态变化，每个路由器的路由表 也需要定期更新，此外路由表的设置还要保证不能有回路的产生口”。组播路由算法可以从 不同的角度和不同的准则进行分类。 1 静态算法和动态算法 组播路由算法按照是否允许网络成员随肘加入或离开组播组，可以分为静态路由算法和 动态路由算法两类。静态组播路由算法针对初始的组播组成员构造一棵组播树，这时候组播 组成员和组播树固定下来它不能根据当前实际( 实测或估测) 传输量和拓扑结构的变化来 做拓扑选择，而是按照先前构造好的组播路由进行传输，它的路由修改需经过一定时间的运 行屙才能进行。 但是真实网络中存在许多动态的变化，例如网络拓扑结构的变化，组播组成员的变化等， 所以动态组播路由算法显得非常的重要，它允许组播组成员可以动态加入或离开。构造适应 组成员动态变化的算法有三种方式：一种是构造一棵性能优化的初始组播树，组播组成员变 化之后对树采取最小的变化，例如成员的加入通过建立结点到组播树的最短路由来完成，成 员离开时仅删除该结点，如果删除产生一个非成员的树叶结点，则删除该非成员树叶结点， 重复该步骤。直到不存在非成员树叶结点为止。 第二种方式是组播组成员发生变更后，对整个组播绍重新计算组播路由，也可以采用一 种改进的方法，首先结点加入和离开仿照第一种方式实现，但是在树的局部范围内，考察结 点的加入和离开对树的累计损伤，当这种累计损伤超过一定的门限时，在局部范围内重新优 化路由，可以通过改变门限值来达到树的优化、计算时间和复杂性之间的平衡。 第三种是构造一棵富于弹性变化的次优树，即最短路径树，每个组成员之间互相独立的 选择最短路由，因此树的性能不受组成员动态变化的影响。 华东师范大学硕士学位论文 2 集中式和分布式组播路由算法 组播路由算法按照其实现方式，又可以分为集中式和分布式算法。集中式路由算法是由 结点在掌握了整个网络的拓扑结构后确定组播路由，集中式组播路由算法一般都是源路由算 法( s o u r c e ，r o o t e dr o u t i n g ) ，即源结点通过某个链路协议获得完整的网络拓扑信息，进行路 由的计算。而分布式算法则不需要每个组成员掌握整个网络的拓扑信息每个组成员在只具 有局部信息的条件下就可参与路由的确定。 这两种算法各有其优缺点，集中式算法往往简单快速，但是由于一个结点需要维护整个 网络的状态，其开销可能比较大，而分布式算法相对于集中式算法较复杂并且速度较慢，但 是它有一个显著的优点，就是任何结点都不需要保持整个网络的状态。 3 无约束和有约束组播路由算法 按照是否有q o s 约束，组播路由算法可以分为无约束组播路由算法和有约束组播路由 算法。许多现有的算法是为非实时网络设计的无约束组播路由算法，它们往往只试图优化树 的费用，但是实时和多媒体应用对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 ) 机制，分层路由算法是将网络按照不 同的等级划分成不同的层次，每个路由器只知道在自己的区域内怎样选择路由和如何将分组 发送到目的端的全部细节，而并不知道其他区域的内部结构。采用分层路由算法有许多集中 式算法无法比拟的优点，例如： ( i ) 由于采用分层的方法，顶层的结点数大大减少，由此减少了路由表的搜索时间。 而且每一层结点内部的路由表只在内部有效，因此路由表的计算量也大大减少。 ( 2 ) 每一层的结点只保存当前层的状态信息与上下层都没有关系，从而减少了对内 存的需求量。 ( 3 ) 每一层的结点只在同一层内进行结点状态信息的交换，从而降低了信息的传输量， 节省了网络资源。同时，本层结点内部状态信息的交换被限制在结点内，不会扩散到其他的 结点。 华东师范大学硕士学位论文 ( 4 ) 在每一个结点所代表的个区域内，所采用的路由协议和路由算法与别的区域无 关，也就是说，不同的区域可以采用不同的路由协议和算法。 当然，分层路由机制也有其缺点，例如： ( 1 ) 分层的处理，区域的划分，这会导致网络状态信息的不准确和不及时。 ( 2 ) 网络状态信息的不准确，会导致无法提供最优化的路径，降低寻径的性能。 要进行分层寻径，必须先确定好网络的层次。网络层次的构造基本上有两种；一种是以 主干为核心的两层结构另一种是不依赖主干的多层结构。对于多层结构的构造，有自上而 p 的t o p d o w n 方法【2 7 】和自下而上的b o t t o m u d 方法【2 b j 。 2 4 组播路由协议