（电工理论与新技术专业论文）多点并行蚁群搜索在多限制动态组播中的应用研究.pdf

a b s t r a c t w i t ht h er a p i dp r o g r e s sa n dt h ec o m m e r c eu s eo f i n t e r n e t ，m a n ya p p l i c a t i o n s ， w h i c h r e q u i r eh i g hb a n d w i d t h ，a c h i e v e dg r e a tp r o g r e s s t h e m o s t c o n s p i c u o u s f e a t u r e so ft h e s ea p p l i c a t i o n sm e n t i o n e da r em u l t i r e c e i v e dp o i n ta n dh i g hb a n d w i d t h 。 t h e g o o dw a y t os o l v et h ep r o b l e mi st h em u l t i c a s tt e c h n o l o g yi ni pn e t w o r k sw h i c h m u s tm e e tt h eq o sc o n s t r a i n s t h e a l g o r i t h m s ，w h i c h a r eu n d e r d i s c u s s i o n ，d on o tc o n s i d e rt h eq o sc o n s t r a i n s ， f o re x a m p l e ，t h ep i m ，c b ta n dm o s p f e t c c o n s i d e r i n gt h a t ，t h em u l t i c a s tw h i c h m e e tt h em u l t i m e d i aa p p l i c a t i o n si sc a t c h i n gm o r ea n dm o r ea t t e n t i o n s t h er e s u l t a c h i e v e dn o wi sr e s t r i c t e dt ot h em u l t i p o i n t - f i x e dm o d e lw h i c hi sn o tu s ei nm a n y a p p l i c a t i o n s s ow e m u s td e f i n ean e wm o d e lb a s e do nm o b i l em u l t i p o i n t t h ea n ta l g o r i t h m ，w h i c hi se n l i g h t e n e db yt h er e a la n ti nn a t u r e ，i sp u tf o r w a r da f e w y e a r sa g o t h i sa l g o r i t h mi sa m o n g o n eo f t h em o s ts u c c e s s f u la l g o r i t h m sw h i c h i sb a s e do nc o l o n ya p t i t u d e t h ea n ta l g o r i t h mi su s e di nm a n yn p p r o b l e m ss u c h a s t s p p r o b l e m a n d r o u t i n gp r o b l e m s c o n s t r a l n e dq o s r e q u i r e m e n t s w i 搬f u l l yr e s e a r c h i n go n m u l t i c a s tp r o b l e m ss t u d i e db e f o r e ，w ep u tf o r w a r da n a l g o r i t h m m o d e l w h i c hi sf o c u s e do nt h em o b i l em u l t i - p o i n tp r o b l e m a n df o r s p e e d i n gt h ea l g o r i t h m ，w em a d es o m em e n dt ot h i sa l g o r i t h m t h es i m u l a t i o nw e m a d ee x p r e s st h a tt h ea l g o r i t h mi s a p p l i c a b l et ot h em u l t i c a s tw h o s em e m b e r si s m o b i l ea n dt h i sa l g o r i t h mh a ss o m ep r a c t i c a lu s e 。 k e y w o r d s ：m u l t i m e d i am u l t i c a s t ，m o b i l em e m b e r sm o d e l ，a n ta l g o r i t h m ，t h e m u l t i c a s tt r e e 独创性声明 本人声明所呈交的学位论文是本人在婚师指导下进幸亍的磷究工作和取得的 磺突残莱，除了文中耱粼熬浚拣注帮致滚之楚努，途文孛不毯含蒸德人已经发表 或撰写过的研究戒柒，魄不包含为获褥蠢连盘鲎或其继教肖枫构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文终者签名： 割菱 麓字爱期：立梆年2 月，了强 学位论文舨权使晨授权书 本学位论文作者究企了解盔洼盘璺有关保留、使用学位论文的规定。 特授投叁生态鲎可以将学位论文的全都簸部分内容编入农关数据库进行检 索，并袋臻影零、缀馥袋扫搔等复翻手段绦存、汇编皴供查潮髑疆藤。同意学校 向潮家有关部门或机构送交论文的复印件朝磁盘。 ( 保密的学位论义程解密后适用本授权说明) 学饿论文作者签名：渤巍 签字e j 期：五衅年卫月巧日 导师瓿钫簪 签字日期：删垆年月厂日 第一章绻论 第一章绪论 i 曩零来，i n t e r a c t 征经历蓑稼人的发矮，劳且对丽络的宽繁化、多媒体纯提 爨了越来越裹静要求。隧薷i n t e m e t 的茇袋，带宽的增加篌诤多离带宽豹应霜( 魏 视频会议、网络集体游戏，视频点播等) 成为可能，这就带来了新的带宽的急剧 消耗从而加剧了网络的拥塞。这些高带宽的应用的一个典型的特点就是高带宽和 群发，解决这类问题的一个非常好的思路就怒发展i p 网络的维搔技术，并且要 毯支簿缀摇按术熬爨络平台上实瑷q o s 蘩袋。 1 1 研究背景 随着硬件水平的掇辐和i n t e r a c t 的商用化，在网络上提供彩媒体的音频和视 鬏臻裣基经成为爨终鼗务耨瓣增长点；送稳教嘉，鬟菝熹撵，潮主援卖等豁需癸 将倍息同时传送给多个不同的接受者，这魉系统的组播机制需黉保证信息在一定 限制条件下( 例如时娥，带宽等) 传送到所商目的地，并使得传输成本尽可能低。 这类问题一般统称为多限制的组播问题。 霹懿在i e t f 中褥戮发展懿组播爨凌舞法都没有考虑戮q o s ( q u a l i t yo f s e r v i c e ) 的需求，铡翻p i m ( p r o t o c 0 1 i n d e p e n d e n tm u l t i c a s t ) ”j ，c b t ( c o r e - b a s e d i r e e ) 【2 1 。o s p f 的组播扩展m o s p f ( m u l t i c a s to s p f ) f 3 】等协议。上述的协议都是通 过一个称为“核心”的节点构造一棵由此节点派生的最短路径树，而这些并没有 考媳到多媒体应用蛉q o s 需求。 近每来，蘧葺诗雾技术戆发震，一夔凝懿餐戆算法( 魏遗婚算法、蒺羧邋火 算法，禁忌搜索算法) 樗到了迅速发展和广泛应用。同时，貔新的模拟进他算 法也逐渐发展起来。蚁群算法就是一种源予大自然中生物世界的新的仿生类算 法，诞生至今只有短缀的几年时问，它燕由意大利学者m d o r i g o 、v m a n i e z z o 、 a 。c o l o r i n i 等人蓄宠撬囊斡t 4 1 ，稼之兔蚊辩系绞( a n t c o l o n ys y s t e m ) ，荠雳该算法 求解t s p 闯题【4 】、j o b s h o p 调度问题，g r a p h c o l o r i n g 溺题取褥了一系到较簿的试 验结果。 第章绪论 1 2i p 组播技术 根据协议的作用范围，组播协议分为主机一路由器之间的协议，即组播成员 管理协议，以及路由器路由器之间协议，主要是各种路由协议。组成员关系协 议包括i g m p ( 互连网组管理协议) ；组播路由协议又分为域内组播路由协议及 域问组播路由协议两类。域内组播路由协议包括p i m s m 、p i m d m 、d v m r p 等 协议，域间组播路由协议包括m b g p 、m s d p 等协议。同时为了有效抑制组播 数据在二层网络中的扩散，引入了i g m ps n o o p i n g 等二层组播协议。 通过i g m p 和二层组播协议，在路由器和交换机中建立起直联网段内的组 成员关系信息，具体地说，就是哪个接口下有哪个组播组的成员。域内组播路由 协议根据i g m p 维护的这些组播组成员关系信息，运用一定的组播路由算法构 造组播分发树，在路由器中建立组播路由状态，路由器根据这些状态进行组播数 据包转发。域间组播路由协议根据网络中配置的域间组播路由策略，在各自治系 统( a s ，a u t o n o m o u ss y s t e m ) 间发布具有组播能力的路由信息以及组播源信息， 使组播数据能在域间进行转发。 1 3蚁群算法的基本原理 人工蚁群算法是受到对真实的蚁群行为的研究的启发而提出的。作为昆虫的 蚂蚁在寻找食物源时，能在其走过的路径上释放一种蚂蚁特有的分泌物信息 素，并以此指导自己的运动方向。当一些路径上通过的蚂蚁越来越多时，其留下 的信息素轨迹也越来越多，以致信息素强度增大，后来蚂蚁选择该路径的概率也 越高，从而更增加了该路径的信息素强度，这种选择过程被称为蚂蚁的自催化行 为。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息的正反馈现象： 某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间 就是通过这种信息的交流达到搜索食物的目的。 蚂蚁算法的这种正反馈的迭代思想可以为许多n p 难题提供一个新的有效的 解决思路。在网络路径寻优的过程中，蚂蚁可以适应网络环境动态的变化，采用 分布式的方法寻找到目的地。由于蚂蚁这种特点再加上蚂蚁算法的本质的并行运 算特性，使得蚂蚁算法成为网络路由算法的一种有效的发展方向【”。 第一章缝论 1 4论文的选题意义、刨额点和论文的维织 1 4 1论文的选题意义 扶信息接鼓者黪角度疼看，组播趣题可以大致分为两大类，邸接受者固定的 组攒润题帮接受者动念熬辊交纯懿组撵闷遴。藤者是典受静对多静黄赣模墅， 其研究比较广泛，这方潮的文献也比较多；而后者指的是接受糟动态的加入和退 出，没有固定的接受者，而这一类目前研究的还比较少，也没有一个准确的参考 模型。涉及第二类问题的研究都是把这种情况作为第一类应膈的一个特例来考 虑，飘熊夺在一定豹羁黻瞧。毽是在实舔翅终应嚣中，毒一大类应用簌本囊上是 动态的，是无法用固寇缀成员来表示弱，游方面最典型的铡子就是视频点播和潮 络拍豢，参加者都是在不断的动态变化，因此原有的一点对多点的模型在这里就 必须熏新的进行定义。 本论文分辑了动淼缌掇鲍特点，定义了蘩予动态组成受考虑的缎播模型，并 蠢秘用改进豹簸群算法遂行分毒式戆维撵瓣建立，挺毫了一耱分布式豹多限测动 态组播路由算法d m d m a ( d i s t r i b u t e d m u l t i c o n s t r a i n e dd y n a m i cm u l t i c a s tm u t i n g a l g o r i t h m ) 算法，该算法的提出扩充了缎播的应用范围，撮出一种解决传统组 播算法在动态情况下硒限性的思路，为缌攒的大规模开展进行了有益的尝试。 该算法熬特点楚戆够在嚣终瑟凌下瑷分奄式方式动态运谨，在枣请节点爨邋 采阕有限制豹局部扩张，扶丽减小了算法过程中环路发生的次数，既有效避免了 网络资源的浪费，又加快了收敛的速度。裰保证延迟，带宽，蒜包率限制的条件 下，寻找到一个费用小，尽量平衡网络负荷的组播树。 1 4 2 论文豹镁赫煮 本文在充分研究组播问题特点的基础上，提出了基于蚁群鳟法解决多限制动 态缀播问题的方法，弗设计了仿真实验，验证了算法的有效憔和较优性。 本文在如下四个主罄靛方蘧进行了独创幢驰尝试： 分析番蘸奁弱络串开葳豹组撵潼务，指密了弪礴锺撩簸务大援谈开震豹 限制因素并提出解决这燠限制因素的些思路。 提出了一种新的适用于动态组播威用的模型。 第一章绪论 渗缎嚣算法弓| 入到中掰搀毽数摸型中，褒算法豹运行中弓| 入了羼赘豹 有限制的滋泛并行搜索机镉4 ，加快了算法的收敛遮发并大大减少了算法中环路发 生的几率。 在蚁群算法的设计中的信息素的更新上使用了新的适用于q o s 组播的信 息素更新公式，这些都是在以往豹蚁嚣算法应磁中所没有的。 1 4 。3 论文的组织 本鬻为论文的绪论部分。介绍了论文的相关研究工作背景，选蹶意义，以及 论文豹拳娶创新点。 第二攀襁括牲蘧论述? 阏络中懿维摇闫鼹辑炎，并说明了缰攒瓣藤理帮意 义，指出障碍组播发展的因祭及其解决的思路。 第三章列举了多限制组播的研究现状并且分析了以往研究存在的局限性，在 此基础上引入了本论文的意义。 纂滔露霹论了簸群算法熬基本嚣理及其套逶穆翘中懿瘟建，摇懑蚊群算法在 网络寻路的应用中存在雏崩黻性。 第五章详细的阐述了d m d m a 算法的应用步骤，在讲解该算法的过程中指 出了该算法在解决以往算法局限性的一些尝试性的工作，在本章的结束部分对 d m d m a 算法迸毒亍了一定豹技栽评馀。 最嚣辩本文的算法逡行恿缝，并提出了一黧鞠关静、有馥篷敕磷究方两。 第一章嗣络中的纽播问题研究 第二章网络中的组援阀题研究 i p 缀播技术实现了i p 网络中点到多点的离效数据传送。阉为组播能够有 效地节约网络带宽、降低网络负载，所以在实时数据传送、多媒体会议、数据拷 戴、游戏和仿真等诸多方缅都有广泛的应用。本鬻首先介绍了组播的基本概念和 缎援报文的转发服理，然蜃讲述了曩藏遴用的组援协议，最后分聿曩了虽蘸组援没 有大规模开展起米的一些原因，并且阐述了作者认为的推动组播开展所器解决的 a 令关键经戆技零淘题。 2 1 组播技术的基本概念 2 1 1 绾播技术的产笺原因 近年来随着i n t e m e t 的迅速踏及和爆炸性发展，在i n t e m e t 上产生了许多新 的应援，其中缀多是寒带宽款多媒体应瘸，倒魏网络携频会议、闲络援频，音频 广播、a o d v o d 、股市行情发布、多媒体网络会议、网络协同计算以及方兴朱 艾豹网络群俸游戏等。邀裁豢来了瘸络繁宽夔大藿游糕亵熬鼹了甄络豹稍塞溺 题，为了缓解网络日益增大的压力，人们提出了各种方案，归纳起来，主要有如 下几种： l 、增加主于网络带宽，对网络进行系统的性能升级 2 、引入流量工程，将主干网的负荷爆量的分散到枝干网中，一个比较典型 瞧骰渡裁是热大城域网鹣分滚终强 3 、限制某些高带宽应用的大量使用，但这又削弱了网络支持新业务的能力 4 、歼展支持q o s 的组播应用的研究，减少信息量豹无登簧的复制行为。 其中，应用缀援技术褥以在不改变嬲络结构的前提下支持增长的组搬用户的 带宽需求，这是幽组播的原理决定的，湖此在i p 网络开展支持q o s 的组播应用 瓣骚变成麓当蘸诗算援掰终技术瓣一令磺究热煮。 第一章网络中的宝r 橘问题研究 2 1 2 组播技术的市场前景 i p 组播技术有效地解决了单点发送多点接收的问题，实现了i p 网络中点 到多点的高效数据传送，能够大量节约网络带宽、降低网络负载。作为一种与单 播和广播并列的通信方式，组播的意义不仅在于此。更重要的是，可以利用网络 的组播特性方便地提供一些新的增值业务，包括在线直播、网络电视、远程教育、 远程医疗、网络电台、实时视频会议等互联网的信息服务领域。 组播从1 9 8 8 年提出到现在已经经历了十几年的发展，许多国际组织对组播 的技术研究和业务开展进行了大量的工作。随着互联网建设的迅猛发展和新业务 的不断推出，组播也必将走向成熟。尽管目前端到端的全球组播业务还未大规模 开展起来，但是具备组播能力的网络数目在增加。一些主要的i s p 己运行域间 组播路由协议进行组播路由的交换，形成组播对等体。在i p 网络中多媒体业务 日渐增多的情况下，组播有着巨大的市场潜力，组播业务也将逐渐得到推广和普 及。 2 1 3i p 组播发展简史 2 0 世纪8 0 年代中期，斯坦福大学实施了第一次多目的通话。博士生 s e d e e r i n g 在自己的两篇论文中提出了i p 组播的可能性。 1 9 8 8 年，d w a l t z m a n ，c p o r t r i d g e ，s e d e e r i n g 发表题为距离向量组播路 由协议的文章( r f c l 0 7 5 ) ，它是组播路由协议的首次实践； 1 9 9 1 年1 2 月，s e d e e r i n g 发表了他的博士论文数据报互连网络中的组 播路由( r f c l l l 2 ) 。它奠定了组播网络体系结构和路由协议的基础。该文也成 为i n t e m e t 组管理协议( i g m p ) 的原型； 1 9 9 4 年3 月，形成了o s p f 协议的扩展协议m o s p f ( r f c l 5 8 4 ) ： 1 9 9 5 年，c i s c o 公司开始销售支持组播的路由器和交换机； 1 9 9 7 年1 1 月，组管理协议i g m p v 2 得到i e t f 的批准，成为标准( r f c 2 3 3 6 ) ； 1 9 9 8 年6 月，评估可靠组播传输协议r m t p 的i e t f 标准出台( r f c 2 3 5 7 ) ； 1 9 9 8 年7 月，在制定i p v 6 地址体系标准时，确定i p v 6 组播地址分配方案 - - 6 一 第一章网络中的组橘问题研究 ( r f c 2 3 7 3 ) ，这为组播技术在下一代i n t e m e t 上的应用做出了必要的准备； 2 0 0 0 年底2 0 0 1 年初，人们着手制定各种组播m i b 库，这标志组播技术j 下 向可管理、可控制方向发展。 2 1 4 组播网络的体系结构 组播网络体系结构包括：组播的基本工作原理、实现组播的条件、组播的地 址分配方案及与m a c 地址映射、组播的管理和路由协议。下面就组播网络的体 系结构来讲解组播网络的工作原理，组播的管理和路由协议将放在下一节单独讲 解。 1 、组播的工作原理 传统的i p 通信有两种方式：第一种是在一台源i p 主机和一台目的i p 主机 之间进行，即单播( u n i c a s t ) 第二种是在一台源i p 主机和网络中所有其它的i p 主机之间进行，即广播( b r o a d c a s t ) 。如果要将信息发送给网络中的多个主机而 非所有主机，则要么采用广播方式，要么由源主机分别向网络中的多台目标主机 以单播方式发送i p 包。采用广播方式实现时，不仅会将信息发送给不需要的主 机而浪费带宽，也可能由于路由回环引起严重的广播风暴；采用单播方式实现时， 由于i p 包的重复发送会白白浪费掉大量带宽，也增加了服务器的负载。所以， 传统的单播和广播通信方式不能有效地解决单点发送多点接收的问题。 组播是一种允许一个或多个发送者( 组播源) 发送单一的数据包到多个接收 者( 一次的，同时的) 的网络技术。组播源把数据包发送到特定组播组，而只有 属于该组播组的地址才能接收到数据包。简单地说就是主机通过使用i n t e r n e t 组管理协议加入某个组中，并且可以动态离开组，即成员关系常有变化，路由器 跟踪这种关系并试图形成一条到达组播成员的路径。i p 组播的基本思想是，源 主机只发送一份数据，这份数据中的目的地址为组播组地址；组播数据只在组播 树的分支点上复制一次，组播组中的所有接收者都可接收到同样的数据，并且只 有组播组内的主机( 目标主机) 可以接收该数据，网络中其它主机不能收到。因 此组播技术能够有效地节约网络带宽、降低网络负载，从而实现了i p 网络中点 到多点的高效数据传送。 7 第二章网络中的组播问磁研究 2 、实现l p 鑫疆戆翦疆条馋 实现l p 组播传输，组播源和接收者醚及两者之问的下层刚络部必须支持组 播。即主机的t c p i p 实现支持发送和接收i p 组播；主机的网络接口支持组播； 有一套用于加入、离开、查泊j 的组管理协议，即i g m p ( v l ，v 2 ) ；有一套i p 地址 分配繁臻，势能将第三层l p 缀撵地蛙映射到第二鼷m a c 趣垃；支持l p 组撵数 应蘑软佟；所有介于组疆源和接收者之闻的路濑嚣、交换枫筠需支持缱播；对于 不支持l p 组播传输的中间路幽器采用i p 隧道( t u n n e l i n g ) 技术作为过渡方案。 3 、缎播的地址分配方案 1 ) 缀播i p 地址 l p 缀撩遗致焉子标谖一个l p 缓疆缀。i a n a 鼗d 类选疆空麓分醚绘缝搔 使用，范围从2 2 4 0 0 0 到2 3 9 2 5 5 2 5 5 2 5 5 。如下图2 1 所示( 二j 敷制表示) ， i p 组播地址前四位均为“1 1 1 0 ”。 3 2 位强地垃 卜雩肇。- q 卜字节i 一卜掌哼2 1 - - 字节。- q 固定为1 1 1 0 2 ) 缀捶遗蛙豹楚分 图2 - 1 组擂l p 地址 2 3 9 0 0 0 2 3 8 2 5 5 2 5 5 2 5 5 2 2 , t o 1 d 2 2 4 。o 。e 。2 5 5 2 2 4 。0 0 。o 图2 - 2 组播地址的划分 第一章网络中的组橘问题研究 整令l p 缝接连娃弱空润翔分翔上鋈2 - 2 嫒示，鼹蚕2 2 邋骥懿下： 2 2 4 0 0 0 到2 2 4 ，0 0 2 5 5 地址范围被i a n a 预留，地址2 2 4 0 0 0 保留不 做分配，蕊它地址供路由协议及拓扑查找和维护协议使用。该范围内的地址属于 局部范畴，不论生存时白j 字段( t t l ) 值是多少，都不会被路由嚣转发； 2 2 4 ，0 1 ，0 劐2 3 8 2 5 5 2 5 5 + 2 5 5 建蛙葱壅传为翊户组摇遗址，在全溺莲溷建奏 效。其中2 3 3 8 为g l o p 溅圭正。g l o p 是一耱强治系统之闻的缀掇德蛙分配褪 制，将a s 号直接填入组播地址的中间两个字节中，每个自治系统都可以得到 2 5 5 个组播地址； 2 3 9 。0 + 0 + 0 到2 3 9 。2 5 5 2 5 5 2 5 5 遗址范潮为本地管理缀播地址 ( a d m i n i s t r a t i v e l ys c o p e d 蕊莲r e s s e s ) ，仅在特定戆零建范围内舂效。 当i p 层收到组播数据报文时，根据组播目的地址查找组播转发表，对报文 进行转发。 3 ) 1 p 组播地址到m a c 地址豹殃射 a n a 将m a c 逢垃菠瓣0 l ：5 e ：o o ：0 0 ：0 8 0 t ：0 0 ：5 e ：7 f ：f f ：f f 分配绘缰 播使用，这就要求将2 8 位的i p 组播地址窝间映射到2 3 位的m a c 地址 空间中，县体的映射方法烧将组播地址中的低2 3 位放入m a c 地址的低2 3 位，如图2 3 所示。 3 2 y 壹i p 地址 图2 - 3i p 组播地址到m a c 地址的映射 由于i p 组播地址的聪2 8 位中只有2 3 他被映射到m a c 地址，这样会 有3 2 个l p 缀援地址映射副弱一m a c 地缱上。 2 1 5 缀播成员的管理 9 第二章网络中的组播问题研究 在组播网络中，组播组成员的管理是组播网络的最基本的管理行为，也是组 播体系结构中的重要环节，下面就以在组播成员管理中应用最广泛的i g m a 组 成员管理协议来讲解组播成员管理的基本概念。 1 、i g m p ( i n t e m e tg r o u pm a n a g e m e n tp r o t o c 0 1 ) 组成员管理协议 i g m p 协议运行于主机和与主机直接相连的组播路由器之间，i g m p 实现的 功能是双向的：一方面，通过i g m p 协议，主机通知本地路由器希望加入并接 收某个特定组播组的信息：另一方面，路由器通过i g m p 协议周期性地查询局 域网内某个己知组的成员是否处于活动状态( 即该网段是否仍有属于某个组播组 的成员) ，实现所连网络组成员关系的收集与维护。通过i g m p ，在路由器中记 录的信息是某个组播组是否在本地有组成员，而不是组播组与主机之间的对应关 系。 到目前为止，i g m p 有三个版本。i g m p v l ( r f c l l l 2 ) 中定义了基本的组 成员查询和报告过程；目前通用的是i g m p v 2 ，由r f c 2 2 3 6 定义，在i g m p v l 的基础上添加了组成员快速离开的机制：i g m p v 3 中增加的主要功能是成员可以 指定接收或指定不接收某些组播源的报文。以下着重介绍i g m p v 2 协议的原理。 i g m p v 2 的原理如图2 - 4 所示。 图2 4i g m p v 2 的： ：作原理 当同一个网段内有多个组播路由器时，i g m p v 2 通过查询器选举机制从中选 举出唯的查询器。查询器周期性地发送通用组查询消息进行成员关系查询；主 机发送报告消息来响应查询。主机发送报告消息的时间有随机性，当检测到同一 网段内有其它成员发送同样的消息时，则抑制自己的响应报文。如果有新的主机 要加入组播组，不必等待查询器的查询消息。而是主动发送报告消息。当要离开 第二章网络l ； _ i 的组橘问题研究 组播组时，主机发送离丌组消息；收到离开组消息后，查询器发送特定组查询消 息来确定是否所有组成员都已离开。对于作为组成员的路由器而言，其行为和普 通的主机一样，响应其它路由器的查询。 通过上述机制，在组播路由器旱建立起一张表，其中记录了路由器的各个接 口所对应的子网上都有哪些组的成员。当路由器接收到某个组g 的数据报文 后，只向那些有g 的成员的接口上转发数据报文。至于数据报文在路由器之间 如何转发则由路由协议决定，不是i g m p 协议的功能。 2 、二层环境中组成员管理的实现 i g m p 组播成员管理机制是针对第三层设计的，在第三层，路由器可以对组 播报文的转发进行控制，只要进行适当的接口配置和对t t l 值的检测就可以 了。但是在很多情况下，组播报文要不可避免地经过一些二层交换设备，尤其是 在局域网环境里。如果不对二层设备进行相应的配置，则组播报文就会转发给二 层交换设备的所有接口，这显然会浪费大量的系统资源。i g m p 监听( i g m p s n o o p i n g ) 可以解决这个问题。 i g m p 监听的工作原理如下： 主机发出i g m p 成员报告消息，这个消息是给路由器的；在i g m p 成员报 告经过交换机时，交换机对这个消息进行监听并记录下来，形成组成员和接口的 对应关系； 交换机在收到组播数据报文时，根据组成员和接口的对应关系，仅向具有组 成员的接口转发组播报文。 i g m p 监听可以解决二层环境中的组播报文泛滥问题，但要求交换机具有提 取第三层信息的功能；其次，要求交换机对所有的组播报文进行监听和解读，这 会产生很多的无效工作；此外，组播报文监听和解读工作也会占用大量的c p u 处理时间。 2 2 组播报文的转发原理 与单播报文的转发相比，组播报文的转发相对复杂。一方面，组播路由类型 与单播路由不同，是点到多点的一棵路由树；另一方面组播报文转发的处理过程 1 l 一 第一章网络中的细橘问题研究 也有所不同。 l 、组播路由的分类 组播路由可以分为两大类：信源树( s o u r c e t r e e ) 和共享树( s h a r e d t r e e ) 。 信源树是指以组播源作为树根，将组播源到每一个接收者的最短路径结合起来构 成的转发树。由于信源树使用的是从组播源到接收者的最短路径，因此也称为最 短路径树( s h o r t e s tp a t ht r e e ，s p t ) 。对于某个组，网络要为任何一个向该组发送 报文的组播源建立一棵树。共享树以某个路由器作为路由树的树根，该路由器 称为汇集点( r e n d e z v o u sp o i n t ，r p ) ，将r p 到所有接收者的最短路结合起来 构成转发树。使用共享树时，对应某个组，网络中只有一棵树。所有的组播源和 接收者都使用这棵树来收发报文，组播源先向树根发送数据报文，之后报文又向 下转发到达所有的接收者。 下图2 5 是信源树和共享树的例子。 信 图2 - 5 信源树和共享树的例子 信源树的优点是能构造组播源和接收者之间的最短路径，使端到端的延迟达 到最小；但是付出的代价是，在路由器中必须为每个组播源保存路由信息，这样 会占用大量的系统资源，路由表的规模也比较大。共享树的最大优点是路由器中 保留的状态数可以很少，缺点是组播源发出的报文要先经过r p ，再到达接收者， 经由的路径通常并非最短，而且对r p 的可靠性和处理能力要求很高。 2 、组播报文转发过程 单播报文的转发过程中，路由器并不关心组播源地址，只关心报文中的目的 l2 _ 第一二章网络中的组插问题研究 地址，通过目的地址决定向哪个接1 3 转发。在组播中，报文是发送给一组接收者 的，这些接收者用一个逻辑地址标识。路由器在接收到报文后，必须根据源和目 的地址确定出上游( 指向组播源) 和下游方向，把报文沿着远离组播源的方向进 行转发。这个过程称作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 执行过程中会用到原有的单播路由表以确定上游和下游的邻接结点。 只有当报文是从上游邻接结点对应的接口( 称作r p f 接口) 到达时，才向下游 转发。r p f 的作用除了可以正确地按照组播路由的配置转发报文外，还能避免 由于各种原因造成的环路，环路避免在组播路由中是一个非常重要的问题。r p f 的主体是r p f 检查，路由器收到组播报文后，先对报文进行r p f 检查，只有 检查通过才转发，否则丢弃。r p f 检查过程如下： 1 ) 路由器在单播路由表中查找组播源或r p 对应的r p f 接口( 当使用信 源树时，查找组播源对应的r p f 接口，使用共享树时查找r p 对应的r p f 接 口) ，某个地址对应的r p f 接口是指从路由器向该地址发送报文时的出接口； 2 ) 如果组播报文是从砌下接口接收下来的，则刚下检查通过，报文向下 游接口转发； 3 ) 否则，丢弃该报文。 下图2 - 6 所示是在使用信源树的情况下的r p f 检查过程。 姐成员2 图2 - 6r p f 检查过程 路由器e 从s o 接口接收到一个组播报文，其中的源地址属于n o 网段 路由器e 检查单播路由表，发现到n o 的输出接口是s l ，因此将此报文丢弃 如果组播报文是从s l 接口到达，则与查表的结果一致，对该报文进行转发。 第二章网络中的缎攒汹趣研究 飘r p f 捡查过弦司以看出，r p f 捡鸯中使用的是觚路国器到组播源或r p 的最短路所对应的接口因此称作逆向路径转发。 2 3 组播路由协议 与单播路由一样，组播路由也分为域内和域问两大类。域内组播路由目前已 经讨论的相当成熟，在众多的域内路由协议中，d v m r p ( 距离矢量组播路由协 议) 、p i m d m ( 密集横式协议无关组播) 和p i m s m ( 稀疏模式协议无关组播) 楚嚣嚣应用最多兹耱议。下嚣我稻以壤内簸熬懿缝撵路由协议为铡漤缀组援路由 的鏊本原理。 1 、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 ) 协议 d v m r p 是第一个强m b o n e 上得到黹遍使用的组播路由协议，它在r i p 换议豹基懿上扩充了支持缀矮的功能。d v m r p 瓠议首先通过发遂搽测溃惑来进 行邻疆发现，之螽遘遗漆由交换来进行擎撩寻径和确定圭下游依赣关系。 d v m r p 采用逆向路径组播( r p m ) 髀法进行组播转发。当组播源第一次 发送组播报文时，使用截断逆向路径组播( t r u n c a t e dr p m ) 算法沿着源的组播分 发树向下转发组播报文。当时子路由器不氍需要组播数据包时，它朝着组播源发 送势棱滇惠，鼹缝疆分发瓣逡行葵较，氆藏狳不登要魏逶售鏊。主游黪垂器| | 芟到 辫枝消息后将收到此消息的接口置为剪棱状态，停止转发数据。剪枝状态关联着 超时定时器，当定时器超时时，剪枝状态又熏新变为转发状态，组播数据再次沿 着这姥分支流下。另外，当剪枝区域内出现了缀播组成员时，为了减少反应时间， 下游不登等铸上游赘技状态超霹，覆是主动怒羔游发送嫁接搬文，骧使剪技状态 变为转发状态。可觅，d v m r p 是由数据触发驱动，建立缒播踌由表，丽路由树 的建立过程可以概括为“扩散与剪枝”( b r o a d c a s t a n dp r u n e ) 。转发特点可以概括 为“被动接受，主动退出”。 爨癸，在多路谤阉网络幸，当有两个躐多个鲍组播踌由器时，网络上可能会 羹笈转发龟。为了骑盘遮耪情琵出现，奁多鼹访闫网络上，d v m r p 秀每令源选 择了一个唯一的转发器。 2 、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 td e n s em o d e ) 第二章网络中的组播问题研究 在p i m d m 域中，运行p i m d m 协议的路出器周期性的发送h e l l o 消 息，发现邻接的p i m 路由器，进行叶子网络、叶子路由器的判断，并且负责在 多路访问网络中选举指定路由器( d r ) 。 p i m d m 协议使用下面的假设：当组播源丌始发送组播数据时，域内所有 的网络节点都需要接收数据，因此采用“扩散剪枝”的方式进行组播数据包的转 发。组播源开始发送数据时，沿途路由器向除组播源对应的r p f 接口之外的所 有接口转发组播数据包。这样，p i m d m 域中所有网络节点都会收到这些组播 数据包。为了完成组播转发，沿途的路由器需要为组g 和源s 创建相应的组 播路由项( s ，g ) 。( s ，g ) 路由项包括组播源地址、组播组地址、入接口、出接 口列表、定时器和标志等。 如果网络中某区域没有组播组成员，该区域内的路由器会发送剪枝消息，将 通往该区域的转发接口剪枝，并且建立剪枝状态。剪枝状态对应着超时定时器。 当定时器超时时，剪枝状态又重新变为转发状态，组播数据得以再次沿着这些分 支流下。另外，剪枝状态包含组播源和组播组的信息。当剪枝区域内出现了组播 组成员时，为了减少反应时问，协议不必等待上游剪枝状态超时，而是主动向上 游发送嫁接报文，以使剪枝状态变为转发状态。 我们以下图2 7 为例说明扩散剪枝的过程。 图2 7p i m d m 中的扩散一剪枝过程 最初。组播源发出的数据在全网内扩散，注意路由器在转发报文时要进行 砌下检查，因此路由器b 和c 向对方发送的扩散报文都会因为褂) f 检查不 一盗 一蟪墨 蛐夕匿蚕黼 零晕直一 令 精 江一 一点篓 夕盟重一 第一章网络叶1 的组捕问题研究 通过而被拒绝转发。之后，由于路由器c 所在的区域中没有组成员，所以向组 播组播数据的到来方向( a 和b ) 发送剪枝报文。这样在路由器a 和b 中会 将相应的接口设置为剪枝状态，组播数据沿着正确的路由发送到所有组成员。 p i m d m 在多路访问网络中，除了涉及d r 的选举外，还使用断言( a s s e r t ) 机制来选举唯一的转发者以防向同网段重复转发组播数掘包；使用加入剪枝 抑制机制来减少冗余的加入，剪枝消息；使用剪枝否决机制来否决不应该的剪枝 行为。 3 、p i m s 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 ts p a r s em o d e ) 在p i m s m 域中，运行p i m s m 协议的路由器周期性的发送h e l l o 消息， 用以发现邻接的p i m 路由器，并且负责在多路访问网络中进行d r 的选举。 这里，d r 负责为与其直连的组成员向组播树根节点的方向发送“加入，剪枝”消 息，或是将直连组播源的数据发向组播分发树。 p i m s m 通过建立组播分发树来进行组播数据包的转发。组播分发树分为两 种：以组g 的r p 为根的共享树和以组播源为根的最短路径树。p i m s m 通过 显式的加入，剪枝机制来完成组播分发树的建立与维护。我们结合下面的两个图 2 - 8 ( a ) 和图2 - 8 ( b ) 来说明p i m s m 的路由建立过程。 图2 - 8 ( a ) p i m s m 协议的工作过程说明1 第：章网络中的组播问题研究 图2 - 8 ( b ) p i m - s m 协议的”f ：作过程说明2 当d r 盏连的网络中其蠢缝g 豹活动成燹辩，刘蠢羞组g 豹r p 方囱逐 跳发送鳃猿加入清惠，热入获亭秘( 图串标号1 ) 。当本次加入涤饕耱上行进行 时，沿途的路由器建立组播转发状态( 图中标号2 ) ，即路由项。路由项中包括 以下字段：源地址、组地址、组播数据包的入接阴，组播数据包的出接口列表、 定时器鞠标志位等，以使路痰器在收到缀播数撼嚣可以沿着树向下转发。当不再 幕望接浚缀撵数摇嚣，d r 淘罄缝g 豹r p 逐魏缝摇夔棱滇惠瘸滚赘技共享 树。剪枝淞着树上行进行时，沿途的路由器更耨能的路由项，例如删除出接口等。 转发树上的路由器要向着这个组的r p 周期性地发送加入剪枝消息，用以维护 组播分发树状态。 滚警税突缀发送缝援数撵孵，添薮数攥旋瓣装在注瓣消惠内，势囊d r 萃 播至r p ( 图中标号3 ) ，r p 褥将注翡消惠解封装减数据包，沿着熬攀树转发到 各个组成员。之后，r p 可以朝着源方向发送对特定源的加入剪枝消息( 图中标 号4 ) ，加入这个源的最短路径树。这样，源的数据包将沿着最短路径树不加封 装地发送戮r p ( 图孛标号5 ) 。当组播数据龟汾鼹短路径到达嚣孪，r p 巍源斡d r 发送滚瓣箨止潜意( 图牵栎弩5 ) ，使d r 悖壹注搿封装逯程。戴籍，这个源 的组播数据不再注册封装，而是先沿着源的最缀路径树发送到r p ( b a r p ) ， 再由r p 将数据包转发到熬牵树上，沿着共享树( r p d c ) 发送别各个组成 员。 蓑遮鬟一定豹数攥健送瀵攀，d r 也霹数发送遂式懿热入溃惫麓入舅滚豹最 短路径树上( 图中标号7 ) ，维播报文就经由最缀路径树转发下来( 瞄中标号8 ) 。 之后，d r 对共享树进行聪新，删除相应的共搴转发路由( 图中标号9 ) 。 第二章网络中的组播问蹶研究 p i m s m 中还涉及刭r 爹茨选择毒珏割。在p i m s m 蠛爽醚嚣了令或多个 候选自举路由器( c a n d i d a t e ，b s k ) 。使用一定的舰则从中选出自举路由器( b s r ，。 p i m s m 域中还配置有候选r p 路由器( c a n d i d a t e r p ) ，这些候选r p 将包含了 它们地址及可以服务的组播缀等信息的报文单播发送给自举路由器，再由b s r 定期生成毽据一系列候选l i p 以及相应豹组遗皱静“垂举”消息。“囊举”渚怠在整 个蠛中逡虢发送。路逡器袋教并傈存这些“基举”消息。若d r 觚纛适主税收到 了i g m p 加入报文后，如聚它没有这个组的黯由项，将使用h a s h 算法将组地 址映射到个候选l i p 。然飚朝l i p 方向逐跳熄播“加入剪枝”消息。若d r 从 直连主执收到组播数据包，如栗它没有这个组的路幽项，也将使用h a s h 算法将 缝逮聚浚瓣到一令鬏选r p ，然嚣褥组撵数豢封装在注麓滇怠中蕈掇发送妥r p 。 在多路访问网络中，p i m s m 还引入了以下机制：使用断言机铕选举唯一的 转发者。以防向同一网段爨复转发组播数据包；使用；b n x 剪枝抑制机制减少冗 余的加入剪枝消息：使用鼬枝否决机制否决不殿有的剪枝行为。 2 4 缀播网络存在的问越 从理论上讲，组播技术的推广对于网络性能的提高尤其是未来大规模开展的 多媒体墩爝其有非常重要豹慧义，但是从组攒理论的提出到现在为此，尽管域内 麓缝掭舞法已经菲豢或熬，穰楚蘩嚣蓑受壹大魏貘豹缓摇应焉实骣上势没毒嚣曩 起来，分析起来主要有如下几个原因： l 、认证难：组播协议不提供用户认证功能，用户可随意地加入或离开： 2 、计费难：组播协议不涉及计费，加上缀播源无法得知用户俩对加入或离 开，氇纛法缝诗菜霹阕毅黧蕊有多少强户在救豢缀撵蕊嚣，因魏纛法遗嚣难碜豹 计费； 3 、管理难：组播源