（计算机应用技术专业论文）应用层网络中多约束的组播路由算法研究.pdf

硕士学位论文 摘要 随着计算机网络技术和多媒体技术的发展， n t e r n e t 正在成为许多实时多媒体 应用的重要载体，如音视频会议、网络直播、网络游戏等。这些需要高带宽低时 延的应用对组播通信服务提出了迫切要求。由于技术和经济方面的原因，直到现 在，全网范围内的i p 组播服务尚未完全部署。在i p 组播无法满足这些应用需求 的情况下，研究人员开始考虑利用i n t e r n e t 端用户的网络资源，在应用层直接提 供组播服务，于是提出了应用层组播的概念。 应用层组播服务的思想是由端系统而不是路由器实现组播通信的所有功能， 其最大的优势在无须改变现有的i p 网络结构，不需要底层网络的支持并且部署简 单。应用层组播路由与传统的i p 组播路由不同，这是因为应用层网络是一个虚拟 逻辑网络，其路由和下层网络的路由通常不一致，这就可能造成应用层组播的时 延增加和资源浪费。由于端系统主机的转发能力有限，这就引入了度的限制。如 何提供有效的组播，设计良好的组播路由算法是应用层组播研究的关键之一，也 是本文的研究重点。 首先，本文有效的分析了度受限的最小直径生成树算法一c t 算法，并提出了 改进的c t 算法。新算法在构造组播树的过程中，考虑了c t 算法未作考虑的结点 度平衡分配的问题。采用策略函数迭代的选择使生成树直径最短的路径，从而有 效的减少了网络中的转发时延和同一条链路的重复分组数量，同时使用拓扑优化 策略，得到优化的组播树。实验结果表明，新算法构造的组播树和c t 算法构造的 组播树相比，链路压力低1 0 到3 0 ，而相对直径惩罚仅大4 到1 1 ，但它的 相对平均距离惩罚却又几乎相同。达到了平衡了网络负载但并没有牺牲组播树的 传输时延的目的。 其次，在实时多媒体应用中，为保证服务质量，接受端要求信息在一个时延 延迟允许的范围内到达，这就引入了时延受限的应用层组播路由问题。针对这个 问题本文提出了一种基于禁忌搜索的应用层组播路由算法t s l d r b 。算法利用禁 忌搜索来搜寻满足时延限制的组播生成树，并对该方法的特性进行了研究分析。 实验结果表明，t s l d r b 算法具有较好的收敛性，且在生成树半径和剩余度平衡之 间具有较好的性能。 最后，根据目前工作中的问题，提出了进一步的研究工作。 关键词：应用层组播；时延约束；度平衡；禁忌搜索 应用层网络中多约柬的组播路由算法 a b s t r a c t a st h ed e v e l o p m e n to fc o m p u t e rn e t w o r kt e c h n o l o g ya n dm u l t i m e d i at e c h n o l o g y ， i n t e r n e ti sb e c o m i n gi m p o r t a n tc a r r i e ro fm a n yr e a l t i m em u l t i m e d i aa p p l i c a t i o n s is u c ha s t h ea u d i o v i d e oc o n f e r e n e i n g , o i l l i n el i v eb r o a d c a s t i n ga n dm u l t i p a r t yg a m e s t h e s e a p p l i c a t i o n sw h i c hn e e dh i g hb a n d w i d t ha n dl o wl a t e n c yp u tf o r w a r de x i g e n tr e q u i r e m e n t o ng r o u pc o m m u n i c a t i o n b e c a u s eo fs o m et e c h n o l o g ya n de c o n o m yi s s u e s ，i pm u l t i c a s t s e r v i c e a m o n gt h e w h o l en e t w o r kh a v e n tb e e nd e p l o y e dc o m p l e t e l y u n d e rt h e c i r c u m s t a n c et h a ti pm u l t i c a s tc a n n o ts a t i s f yt h e s ea p p l i c a t i o nr e q u i r e m e n t ，r e s e a r c h e r s b e g i nt oc o n s i d e ru t i l i z i n gn e t w o r kr e s o u r c e so fi n t e r n e te n du s e rt op r o v i d em u l t i c a s t s e r v i c ed i r e c t l yi nt h e a p p l i c a t i o nl e v e l ，t h e r e f o r e ，t h e n o t i o n o fa p p l i c a t i o n - l e v e l m u l t i c a s th a sb e e np u tf o r w a r d t h ei d e ao fa p p l i c a t i o n l e v e lm u l t i c a s ts e r v i c ei st h a ta l lm u l t i c a s tf u n c t i o n sa r e i m p l e m e n t e di ne n dh o s t si n s t e a do fr o u t e r s t h ep r i m a r ya d v a n t a g ei st h a ti pn e t w o r k a r c h i t e c t u r en e e dn o tt ob ec h a n g e d ，s u p p o r to fl o w e rl e v e ln e t w o r ki sn o tr e q u i r e d a n dt h ed e p l o y m e n ti ss i m p l e a p p l i c a t i o n l e v e lm u l t i c a s tr o u t i n gi sd i f f e r e n tf r o m t r a d i t i o n a li pm u l t i c a s tr o u t i n g t h ea p p l i c a t i o n l e v e ln e t w o r ki sav i r t u a ll o g i c n e t w o r k ，i t sr o u t i n gd i f f e r sf r o mt h en e t w o r ki nl o w e rl e v e l ，t h u sm a yr e s u l ti nt h e l a t e n c yi n c r e a s i n ga n dr e s o u r c ew a s t i n go ft h ea p p l i c a t i o n - l e v e lm u l t i c a s t b e c a u s eo f t h el i m i t e dt r a n s m i t t i n gc a p a b i l i t yo ft h ee n dh o s t s ，l i m i t e dd e g r e ei si n t r o d u c e d h o w t op r o v i d ee f f e c t i v em u l t i c a s ta n dd e s i g ng o o dm u l t i c a s tr o u t i n ga l g o r i t h ma r et h ek e y p o i n t so ft h ea p p l i c a t i o n l e v e lm u l t i c a s tr e s e a r c h ，a n da l s ot h ef o c u so ft h i sp a p e r f i r s t ，t h i sp a p e ra n a l y z e sd e g r e e c o n s t r a i n tm i n i m u md i a m e t e rs p a n n i n gt r e e a l g o r i t h m t h ec ta l g o r i t h m ，a n dp r o p o s e st h ei m p r o v e dc ta l g o r i t h m i nt h e p r o c e s so fc o n s t r u c t i n gm u l t i c a s tt r e e ，t h en e wa l g o r i t h mc o n s i d e r st h eb a l a n c e a b l e d i s t r i b u t i o no fn o d ed e g r e ew h i c ht h ec ta l g o r i t h md o e s n tt a k ei n t oc o n s i d e r a t i o n b yu s i n gs t r a t e g yf u n c t i o n ，t h i sa l g o r i t h mi t e r a t i v e l yc h o o s e st h ep a t hw h i c h m a k e s d i a m e t e ro ft h es p a n n i n gt r e et h es h o r t e s t ，t h u sd e c r e a s e st h et r a n s m i t t i n gl a t e n c yo f t h en e t w o r ka n dt h en u m b e ro fr e p e a t e dg r o u p i n gi nt h es a m el i n kp a t h a tt h em e a n t i m e ，i tu s e st h et o p o l o g yo p t i m i z a t i o ns t r a t e g yt og e tt h eo p t i m a lm u l t i c a s tt r e e e x p e r i m e n t ss h o wt h a tt h i sa l g o r i t h mh a sr e a c h e dt h ed e m a n do fd e g r e eb a l a n c ea n d k e p tt h ep e r f o r m a n c eo ft i m ed e l a y t h e n ，i n t h er e a l t i m em u l t i m e d i a a p p l i c a t i o n ，t h e r e c e i v e r r e q u e s t t h a t i n f o r m a t i o ns h o u l db ea r r i v e dw i t h i no n ed e l a yi no r d e rt og u a r a n t e et h eq u a l i t yo f s e r v i c e t h u s ，t h ed e l a y l i m t i e da p p l i c a t i o n l e v e lm u l t i c a s tr o u t i n gp r o b l e mi s i n t r o d u c e d a i m i n ga tt h i sp r o b l e m ，t h i sp a p e rp r o p o s e sa ne f f i c i e n ta l g o r i t h m t h e 硕士学位论文 t s l d r ba l g o r i t h mb a s e do nt a b us e a r c h t h i sa l g o r i t h mm a k e su s eo ft h et a b u s e a r c ht os e a r c hf o rt h em u l t i c a s ts p a n n i n gt r e ew h i c hs a t i s f i e st h ed e l a yr e s t r i c t i o n a n da n a l y z e st h ec h a r a c t e r i s t i co ft h i sm e t h o d e x p e r i m e n t ss h o wt h a tt s l d r b a l g o r i t h mn o to n l yh a st h ea d v a n t a g eo fl o wt i m ec o m p l e x i t yb u ta l s og u a r a n t e et h e p e r f o r m a n c eo fa l g o r i t h m a tl a s t w ep u tf o r w a r dt h ef u t u r er e s e a r c hw o r kb a s e do nt h ee x i s t e dp r o b l e m si n 一一 r e c e n tw o r k w ew i l lc o n s i d e rc o n s t r u c t i n gm u l t i c a s tt r e ef r o mb o t h a s p e c t s o f d i s t r i b u t i o ne n v i r o n m e n ta n dd y n a m i cm a n a g e m e n t k e yw o r d s ：a p p l i c a t i o n l e v e lm u l t i c a s t ；d e l a y l i m i t e d ；d e g r e eb a l a n c e ；t a b us e a r c h t l 应用层网络中多约束的组播路由算法 插图索引 图1 1 lp 组播的体系结构2 图1 2n s 结构图6 图1 3n s 中的部分类图7 图2 1 应用层组播。一1 1 图2 2 应用层组播体系结构1 2 图2 3m e s h 网实例1 3 圉2 4y o i d 树的构遗1 4 图2 5 三层结构示意图1 5 图2 6n i c e 中的结点组织1 6 图3 1 组播路由参数的平衡2 0 图4 1c t 算法的缺陷2 6 图4 2o c t 算法实例2 8 图4 _ 3t r a n s i t s t u b 网络拓扑模型2 9 图4 4 树的相对直径惩罚和结点数目3 1 图4 5 树的相对平均直径惩罚和结点数目3 l 图4 6 树的平均链路压力和节点数目3 2 图5 1 邻域结构的设计3 5 图5 2o c t 伪代码3 7 图5 3 迭代次数与生成树的关系3 8 图5 4 结点数目和生成树半径的关系3 9 图5 5 结点数目和负载均衡方差的关系3 9 i v 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名： l 嗡丑一 日期：护6 年 厶月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“4 ”) 作者签名： 导师签名： 日期： 日期： p 6 年 d 年 0 月 年月 日 ? 日 硕士学位论文 第1 章引言 随着网络技术的发展，通信网络进入2 0 世纪9 0 年代后，向着综合业务的方 向发展，在i n t e r n e t 上产生了许多新的应用，如网络视频会议、音视频广播、 分布式数据更新、计算机协同计算、多媒体远程教育等，这类应用都具有一对多， 多对多的通信特点，同时要求网络提供服务质量保证。 传统的i p 组播方案是为一对多，多对多的通信模型而设计的，然而由于i p 组播部署面临很多问题，包括技术性问题和i p 组播方案所带来的市场问题，导 致从9 0 年代初至今，i p 组播一直没能在i n t e r n e t 上得到广泛应用。在i p 组播 难以部署，无法满足这些新应用的需求的情况下，需要寻求新的方案和技术来实 现组播通讯，满足应用的需求。于是，人们提出了应用层组播。本文主要讨论如何 构建应用层组播树问题。 1 1i p 组播技术概述 在i p 网络上，主机的通信方式有两种：单播、组播。单播是在一个发送器和 一个接收器之间的通信，它是一对一的通信。但是，某些过程有时需要将相同的报 文同时发送给大量的接收器，这就是组播。即一对多的通信。组播具有许多应用。 例如，股票价格的变动要同时通知许多经纪人，或者旅行的取消也会同时通知许 多旅游代理，其他一些应用如远程学习和点播电视等。 i p 组播( i pm u l t i c a s t ) 是对标准网络层协议的扩展。它通过使用特定的i p 组播地址，按照最大投递的原则，将i p 数据报传输到一个组播组( m u l t i c o s t g r o u p ) 的主机集合。 1 1 1i p 组播概念 标准i p 组播业务模型定义了主机和路由器应有的功能机制和上层所看到的 组播业务的形式。主机组( h o s tg r o u p ) 是i p 组播概念的核心，多个主机组成主机 组，用一个i p 组播地址标识，即每个组播组对应一个组播地址。以组地址为目的 地址的组播数据以i p 数据报的b e s t e f f o r t 方式转发到主机组的各个主桃。组播 路由器承担组播数据的寻路和转发控制功能，这些路由器及链路在网络中形成了 一个控制组播数据传送的逻辑结构，称为组播转发结构( d e i v e r ys t r u c t u r e ) ， 这种结构一般是树形的结构，称为转发树，在转发树上的组播路由器接收、复制、 转发组播数据。 源主机只向组播组地址发送一份数据，这个组播组中的所有接收者都可接收 应用层网络中多约束的组播路由算法 到同样的数据拷贝，并且只有组播组内的主机( 目标主机) 可以接收该数据，网络 中其它主机不能收到。组播使得数据沿着转发树向目的节点分发，不在分发路径 上的节点无须参与路由，i p 组播避免了在链路上传输重复报文，从而节约了网络 资源，可实现高效的组播通讯。 1 1 2i p 组播的体系结构 篓鋈鋈寨囊i 垂薹薹i 蓬鬻_ _ | _ 蔓鎏i 冀i 。j j w r t p ， # ： 、豳“m u l “。c “a s 。 m d c p ， 舯，m a 骶 g d p r t c p l 】a n a t 辫蓄 g l o p t c f 量j i i 。 誊j u d p 懋耩； 【g m p l ； 叠 菪+ p i m s mp i md mm o s f f o s p f r i p ， 罄 董 d v m r p e i g r p： p d p e 1 g r p o s p f m s d p ，b o m p 日o p 攀m b g p ( b o p 4 + ) ； 图i 1i p 组播的体系结构 图1 1 给出了当前i p 组播的体系结构”1 ，体系结构自上而下分为四个层次。 最低层为域间路由层，实现跨域的组播路由，采用的协议有m s d p 0 1 和b g m p 。 上一层为域内路由层，实现域内的组播路由即通常说的组播路由协议，目前的组 播路由协议组主要有d v m r p ”1 ( 距离向量路由协议) 、m o s p f “3 ( 开放式组播路径优先 协议) 、c b t ”1 ( 有核树) 、p i m 一明阳1 ( 独立组播路由协议密集模式) 、p i m s m 9 3 ( 独 立组播路由协议稀疏模式) 等。第三层是主机一路由器之间的协议i g m p “”( 组管理 协议) ，组播路由器通过i g m p 协议为其每个端口都维护一张主机组成员表，并定期 的探询表中的主机组的成员，以确定该主机组是否仍然存在。最上层是主机服务 层，包括了组播地址分配机制，组播会话目录协议，实时传输协议，可靠组播等。 1 2i p 组播协议 在i p 组播通讯中需要完成两个方面的基本工作：组播成员如何加入组播组以 及如何将组播信息路由到每个接收者。这样就产生了两类基本的协议：组管理协 议和组播路由协议。 2 硕士学位论文 1 2 1 组管理协议 i g m p r f c 2 2 3 6 【i ”用于主机与边缘组播路由器之间。主机使用i g m p 协议通知 本地的边缘组播路由器，希望加入该组。组播路由器通过i g m p 协议来维护一个组 播成员列表，并且定期发送“成员询问”消息来探寻表中的各个成员是否仍然存 在。 ( 1 ) 加入组播组 当一个主机想加入某一个组播组时，它通过“成员资格报告”消息通知它所 在的i p 子网的组播路由器，同时将自己的i p 模块做相应的准备，以便开始接受来 自该组播组传来的数据。如果这台主机是它所在的i p 子网中的第一台加入该组播 组的主机，通过路由信息的交换，组播路由器加入组播生成树。 ( 2 ) 退出组播组 当主机离开某一个组播组时，它将自行退出。组播路由器定时使用“成员资 格查询”消息向i p 子网中的所有主机的组地址( 2 2 4 0 0 1 ) 查询，如果某一组播 组在i p 中已经没有任何成员那么组播路由协议在确认这一事件后，将不再在子网 中转发该组播组的数据，同时，通过路由信息交换，从特定的组播组分布树中删 除相应的组播路由器。 1 2 2 组播路由协议 组播路由协议的目的是要构建组播分发树。数据包根据这棵路由树从发送端 转发到树上其它所有的路由器上。实际上，i n t e r n e t 采用两类路由协议：密集模 式协议( 如d v m r p 、m o s p f 、p i m - d m ) 和稀疏模式协议( 如c b t 、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 ( 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 g p r o t o c 0 1 ) r f c l 0 7 5 。1 是第一个在m b o n e 上得到普遍使用的组播路由协议，适用 于单个独立系统的内部网关协议。它在r i p 协议的基础上扩充了支持组播的功能。 但与r i p 协议不同的是r i p 根据路由表前向转发数据，而d v m r p 则是基于反向路径转 发( r e v e r s ep a t hf o r w a r d i n g ，f r p ) 结合泛洪与剪枝( f l o o da n dp r u n e ) 技术 构建基于数据源的组播树。d v m r p 协议首先通过发送探测消息来进行邻居发现，之 后通过路由交换来进行单播寻径和确定上下游依赖关系。反向路径广播保证构造 的组播树中不会出现环路，并且源到每个接受者都是最短路径。由于需要保存大 量的组播路由状态信息使得当网络规模扩大时路由表聚合时间过长，因此d v m r p 不适合网络规模较大且实时性要求较高的环境，只适用于少量的接受者分散的处 于组播源周围的网络。 2 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 ( m u l t i c a s to p e ns h o r t e s tp a t h f i r s t ) r f c l 5 8 4 “1 是o s p f 协议的一种基于链路状态的路由机制的扩展，o s p f 可以使 用不同类型的单一链路状态度量( 如时延或经过的h o p 数) 来表示路径的代价。 m o s p f 使用新的链路状态通告l s a ( l i n ks t a t eh d e r t i s e m e n t ) 记录类型一“组 成员”对o s p f 的数据库进行补充。使用这种方式，m o s p f 路由器可以执行反向路 径检查并且可以进行加入和剪枝计算。由于m o s p f 路由器必须维持一份最新的整 个域内路由拓扑结构和接受者位置的完整信息来构造有源树，当组播组数量和组 播组源节点数量都非常大时，m o s p f 实现的路由算法的复杂度较高。由于当组成 员发生变化时，m o s p f 将向区域内的所有路由器发布l s a 更新。导致所有组播树 的路由器都要更新自己的路由状态。如果组成员变化频繁，m o s p f 将会发送大量 的l s a 更新并触发大量的路由计算。因此，m o s p f 的扩展性并不好。 3 c b t ( c o r eb a s e dt r e e ) 核心树协议c b t ( c o r eb a s e dt r e e ) r p c 2 2 0 1 r f c 2 1 8 9 j ”的基本目标是 减少网络中路由器的组播状态以提供组播的可扩展性。c b t 为每个组播组建立一棵 以某个核心路由器为根的双向共享树。当某个路由器所在子网或其下游子网中有 主机加入组播组时，此路由器与该组播组的核心路由器先取得联系，以核心路由 器为根按最短路径建立组播树。当一个非组播组成员的源节点发送分组时，分组 将向着核心节点的方向进行转发至到达某个已经在树中的节点。从这个节点开始， 分组将被转发到组播组中的所有端口，除了收到分组的那个端口。而且并不是所 有的分组都需要通过核心节点进行转发。这特点可以降低核心节点对数据转发 的影响。因为实现c b t 的路由器只需要为每一个组维护一个状态项而不需要为每个 组中的每个源节点都维护状态项，这样可以节省大量的保存状态的空间。当然， c b t 的不足是共享树更容易使流量集中到某几条链路上。 4 p i 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 ) 协议 协议无关组播协议p i m ( p r o t o c o li n d e p e n d b n tm u l t i c a s t ) r f c 2 3 6 2 0 1 由 i d m r ( 域间组播路由) 工作组设计的，p i m 不依赖某一特定单播路由协议，它可利 用各种单播路由协议建立的单播路由表完成反向路径转发( r p f ) 检查功能，而不 是维护一个分离的组播路由表实现转发。由于p i m 无需收发组播路由更新，所以与 其它组播路由协议相比，p i m 开销降低了许多。 设计p i g 的目的是在广域网内同时支持共享路由树和特定数据源路由树，并能 完成二者之间的灵活转换，因而集中了二者优点的同时避免了它们的缺点，提高 了组播效率。在组成员稀疏时，采用p i m s m 构造共享树传递，避免分组的广播开 销；在组成员密集时，采用p i m d m 以广播形式传递数据，然后从树上删除不存在 接收节点的分支。 4 硕士学位论文 1 3i p 组播路由主要算法 路由算法可分为三类：源路由算法、分布式路由算法和分级路由算法。源 路由算法假定每个节点了解整个网络的全局状态。全局状态用链路状态协议通过 广播获得，或用距离向量协议，邻接点周期性交换距离向量获得。当要发送信息 时，源节点决定了整条路径。而分布式路由算法假定每个节点只了解它的邻接点 的情况，即网络局部状态。根据路径的要求，决定下一跳走向哪里。分级路由算 法假定网络节点分级，每个节点了解聚合的全局状态，即自己所在范围内的情况， 而对远处的上级节点只了解大致情况。即每一物理节点保持聚合的网络影像。本 文研究具有约束的组播路由算法，下面对其中比较经典的一些算法作简要介绍。 1 最短路径树m ， 最短路径树是从源节点到所有接收节点的每条路径上链路权值之和最小的组 播树。如果所有的链路的权值都表1 ，则为最小跳树。如果权值代表链路延时，则 为最小时延树。可以用最短路径树算法解决树约束问题。 2 最小生成树n 2 ， - 最小生成树是指覆盖所有组成员且权值最小的组播树，其主要算法为p r i m 算 法。在p r i m 算法中，从任意一个根节点开始构造整棵树，直到其扩展到所有节点。 在每一步，己连接的选择节焦与未选择节点的权值最小的边被加入到树中。算法采 用了贪婪策略，因为在树的增长过程中，每次选择的边都是使树权值增加最小的 边。最小生成树算法可用来解决树最优化问题。 3 s t e i n e r 1 基于s t e i n e r 树的问题致力于使组播树的总代价最小，这已经证明了是一个 n p c o m p l e t e “问题。如果组播树包含了树中所有节点，s t e i n e r 树问题转化为最 小生成树问题。无约束条件的s t e i n e r 树算法可用来解决树最优化闯题然而他们 却无法满足端到端基础上的约束条件，因此它们不能很好地满足带有此类要求的 应用。例k m b “”算法是具有代表性的s t e i n e r 树算法，它解决了基于时间约束的 s t e i n e r 树问题的路由选择。该算法能够保证在多项式时间内找到合适解。 4 约束s t e i n e r 1 树 s t e i n e r 树问题可以扩展到包括其它的链路约束。例如延时、延时抖动或者 它们的组合。通常这些问题是n p c o m p l e t e 的，所以也需要采用启发式算法解决。 目前求解有度约束的组播路由问题中性能较好的是s p h m ，算法。其基本思想是：从 只包括源节点的子图开始，寻找与之距离最近且不违反度约束的一个目的节点，用 最短路径将两节点相连，同时将最短路径上的节点也加入图中，然后再找下一个与 子图距离最近的且不违反度约束的目的节点，将其加入，如此直到所有的目的节点 全部加入到树中。 应用层网络中多约束的组播路由算法 5 最大带宽树 最大带宽树是指到每个目的节点的带宽都最大的组播树。文献 1 6 给出了一 个类似d i j k s t r a 的算法的分配分层压缩数据的最短带宽组播树算法。 1 4 实验平台：网络模拟器n s 一2 随着互联网的快速成长发展出许多新的网络协议。在早期，当新的算法或 协议设计完成时，研究人员多借用实验或数学建模的方式，来验证其正确性及性 能。但现在的网络环境越来越复杂，构建一个实验环境交得相当昂贵，而且这个 环境很可能不能运用在下个实验中，更不能为全球研究人员共享；而以数学建模 的方式常常因复杂度过高而难以分析，所以将新的算法以模拟的方式来验证，是 目前较常用的方法。 另一种情况是，在要架设一个新的网络环境之前，必须事先评估网络的拓扑 及带宽是否能满足需求，这时也需要有一套网络模拟软件，事先模拟各种不同的 网络环境，作为决策的参考。 目前已有许多的网络模拟器，商业软件有o p n e t “”，b o n e s “”，c o m n e t i i i “， 尤其o p n e t 的支持度相当广泛，几乎包含所有现行网络标准，但需要百万元以上， 非常昂贵。n s “”开放源码，可以任意的增加修改自己想要的功能，所以研究人员 一般都使用n s 作为模拟平台，并且将最新的研究成果提供给n s ，所以n s 版本 的更新速度很快，它包含有许多最新提出的协议，很适合研究工作的开展。 1 4 1n s 结构 n s t w 包括t c l t k ，o t c l ，t c l c l 软件。其中t c l 是一个开放脚本语言，用来对 n s 进行编程；t k 是t c l 的图形界面开发工具，可帮助用户在图形环境下开发图形界 面：o t c l 是基于t c l t k 的面向对象扩展，有自己的类层次结构：n s 为本软件包的核 心，是面向对象的仿真器，用c + + 编写，以o t c l 解释器作为前段：t c l c l 则提供n s 和o t c l 的接口，使对象和变量出现在两种语言中，他们之间的关系如图1 2 所示。 e v e n ts c h e d u l e rn s - 2 t c l c l o t c l 善萝 刁 鸯沣 l c c + + 图1 2 n s 结构图 n s 是一个面向对象的仿真器，由编译和解释两个层次组成，编译层次包括c 6 硕士学位论文 + + 类库，而解释层包括对应的o t c l 类，一些比较底层的工作，例如事件的处理、 分组的转发，这些事情需要较高的处理速度，而且一旦完成就很少需要修改，所 以使用c + + 是最佳的选择。另一方面，在做实验时，常需要设定不同的网络环境、 动态调整协议的参数，这些事情使用像o t c l 这类的解释性脚本语言将会有较佳的 弹性。 图1 3n s 中的部分类图 图1 3 是n s 中的部分类图，t c l 类包含了用c 十+ 代码访问解释程序的方法。 t c l o b j e c t 类是为反映在经过编译的分层中的仿真器对象服务的基本类。 t c l c l a s s 类定义了经过解释的类分层和用户用来示例t c l o b j e c t 的方法。 t c l c o m m a n d 类用来定义解释程序简单的全局命令。e m b e b e d 类包括了装入更高层 内置命令的方法。这些命令使得配置仿真变的更加容易。最后是i n s t v a r 类包含 了访问像o t c l 实例变量一样的c 十+ 成员变量的方法。基类c o n n e c t o r 派生出许多 子类，s n o o p q u e u e 监视队列的到达，发出，丢弃和统计数据及平均值，q u e u e 中 包含各种队列调度算法，d e l a y 设置队列的延时，在a g e n t 中生成各种代理，来 实现相应的协议或者其它模型的仿真，如t c p 代理和在t c p 基础之上的各种代理， 如：t c p r e n o 、t c p n e w r e n o 、t c p v e g a s 、t c p s a c k l 等。t r a c e 中用来跟踪各种 仿真数据，记录单个包在队列或链路的到达e n q ) 、离开( d r o p ) 、使用t r a c e a l l 将每个包的情况记录下来。 1 4 2n s 模拟方法 n s 支持单播和组播的传输模式，支持t c p 、s r m 、r t p 、u d p 等传输协议，支 持d r o p t a i l 、r e o 、 r i o 、 f q 、p i 等队列管理模式，用户可以在任意层扩展自 己的功能和编制新的协议。而且可以编写各种t c l 脚本来对各种协议和算法进行 仿真和模拟，可以对协议的一些变量进行跟踪，对队列和流进行跟踪和监视。 应用层网络中多约束的组播路由算法 运行仿真之前，首先要分析设计仿真的哪一个层次一个是基于o t c l 编程的 配置、构造层次，利用n s 已有的网络仿真元素实现仿真，无需对n s 本身进行修改， 只要编写o t c l 仿真脚本。另外一个层次是c + + 和o t c l 编程的编译、配置层次，如 果n s 中没有所需的仿真元素，n s 提供让用户自己建立新的协议和修改协议的技术 其实现的步骤为设计协议细节实现，把新的协议代码生成新的n s ，生成t c l 脚本来 运行n s 仿真，对运行的结果实现分析和评价。 o t c l 脚本的实现过程： ( 1 ) 生成仿真器并建立网络拓扑结构，并且根据需要确定基本的链路特点，如 延时，带宽和队列参数等。 ( 2 ) 建立协议代理，包括端节点的协议绑定和通信量模型的建立。 ( 3 ) 对节点的参数进行配置，根据仿真的具体要求对节点进行代理，路由协议 的初始化等。 ( 4 ) 建立跟踪或者监视模型，把仿真结果输出并存到指定的文件之中，然后编 写a u k 代码，用来得到需要的数据。 ( 5 ) 设置仿真时间，运行仿真，处理结果。 n s 作为一种具有强大功能的网络仿真工具，和现存的多种仿真工具相比较，它 在可控制性，可扩展性和可视性有很大优点。因此，我们的研究基于该平台，所有 的实验都是在最新的版本n s a l l i n o n e 一2 2 8 上完成。 1 5 本文工作及结构 由于应用层网络是在下层i p 网络基础设施之上构建的虚拟逻辑网络，其路由 和下层网络的路由通常不一致，这就可能造成应用层组播的时延增加和资源浪费。 这对时延和带宽敏感的实时多媒体应用来说就显得更加突出。如何提供有效的组 播，设计良好的组播路由算法是保证应用层组播服务质量的关键。因此本文主要 研究度和时延都受约束的应用层组播路由算法，主要工作归结如下： ( 1 ) 分析了i p 组播的工作原理、组播路由协议，结合组播路由的研究现状， 深入分析了i p 组播不能广泛开展的主要原因。 ( 2 ) 对度受限的最小直径生成树算法一c t 算法进行分析，发现该算法在构建生 成树时并没有考虑结点度的平衡。针对c t 算法的不足，提出了度平衡的 最小直径生成树算法一o c t 算法该算法在构建过程中考虑平衡度分配， 优化平衡网络负载；并且在拓扑优化策略中尽可能复用已用的转发路径， 从而有效的减少了转发时延和重复分组。 ( 3 ) 基于时延限制的组播路由在多媒体流中的重要性，提出了基于禁忌搜索的 应用层组播路由算法，该算法在度平衡的情况下选择满足时延限制的组播 树。实验结果表明，该算法具有较好的收敛性，和同类算法相比在优化组 硕士学位论文 播树的网络资源方面表现出了较好的性能。 ( 4 ) 利用网络模拟器n s 一2 进行仿真模拟，并评估实验结果。 文章结构组织如下： 第一章“引言”，介绍组播技术及其发展概况和本文所做的主要工作。 第二章“应用层组播思想及实现策略”，首先详细论述了应用层组播设计思 想，接着对应用层组播的实现策略进行了分类，介绍了几种典型的组播策略的实现 方法及特点，最后简单介绍了应用层组播的研究现状。 第三章“应用层组播路由问题描述”，详细论述了应用层组播路由模型和主 要的性能参数，研究了应用层组播中度和时延都受约束的路由问题，证明了此问题是 n p c o m p l e t e 的。从而为后续研究和探讨本文提出了组播路由策略方法奠定了一 定的理论基础。 第四章“基于时延和度约束的应用层组播路由”，分析了度受限的最小直径 生成树算法( c t ) ，并对其进行了改进，提出了度平衡的最小直径生成树算法一 o c t 算法。通过实例和仿真实验对算法进行分析和性能比较。 第五章“基于禁忌搜索的多约束的应用层组播路由”，研究时延受限的应用层 组播组播路由问题，提出一种基于禁忌搜索的应用层组播路由算法：进行了相应的数学 分析与证明，并通过仿真模拟实验进一步对算法进行分析和性能比较。 最后为“结论”，总结全文的工作，并对未来工作提出设想。 壁里星塑堑皇耋! 堡竺堡塑堕妻塞鎏 第2 章应用屡组播思想及实现策略 2 1 前言 随着i n t e r n e z 的飞速发展，需要点到多点或者多点到多点的群组通信应用也 越来越多，这包括音频视频会议、w e b 缓存更新、文件分发以及在线游戏等。而 这些群组通信业务都特别需要i p 组播的支持，但是从目前的应用现状来看，尽管 经过了1 0 多年的发展，i p 组播并没有取得预期成功。综合分析，我们可匕l 找出其 中的原因“1 ： ( 1 ) i p 组播体系结构缺乏可扩展性。路由器需要为每个活动的