（运筹学与控制论专业论文）支持qos的组播路由算法的研究.pdf

1 一 at h e s i si no p e r a t i o n a lr e s e a r c ha n d c y b e r n e t i c s r e s e a r c ho nq o s - - b a s e dm u l t i c a s tr o u t i n g a l g o r i t h m b yl i a n gh o n gy i n g s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rz h e n gl i a nw e n o r t he a s t e r nu n i v e r s i t y j u l y2 0 0 8 !_ll，-， 、1_l， 独创性声明 本人声明，所呈交的学位论文是在导帅的指导f 完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚 挚的谢意。 学位论文储签名：驿钮鲧 签字e l 期：切d 7 l l r 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ， 。 作者和导师同意网上交流的时间为作者获得学位后： 半年口一年口一年半口两年口 学位论文作者签名 签字日期 ：靴瓢 ：训7 、r 导师签名：聚电僻 签字日期：1 伊秒鬈，z 。 ，。，0i 东北大学硕士学位论文摘要 支持q o s 的组播路由算法的研究 摘要 随着i n t e m e t 的迅速普及与发展，产生了很多新的应用。这些应用在为用户服务的 同时也引入了带宽的急剧消耗和网络拥塞等问题，为缓解网络瓶颈，人们提出了i p 组 播技术。组播的核心问题在于组播路由的确定，由于网络特别庞大，拓扑结构、流量不 断动态变化，使得组播路由问题变得非常重要而困难。组成员的动态加入和退出、q o s 信息的参与、网络分层路由的需要都为组播路由问题的解决制造了重重障碍。网络路由 既要满足用户不同应用的要求，又要能尽量提高网络整体资源的利用率。 本文共有六章，内容简介如下： 第l 章介绍了关于组播的相关内容，包括组播的发展背景、研究现状，并介绍了本 课题的研究意义、来源等内容。 第2 章介绍组播的核心路由问题，包括组播路由算法和实际网络应用的组播路由协 议，并介绍两种组播树机制。 第3 章介绍了网络业务的o o s 定义和其数学描述，在此基础上介绍带q o s 的部分 组播路由算法和协议以及几种i e t f 为实现q o s 所提出的网络体系结构。 第4 章提出了一种分布式、多q o s 约束的组播路由算法( m r m q ) 。在m r m q 中， 采用了分布式计算方式来解决多q o s 约束的n p 一完全问题。由m r m q 构造的组播树不 仅能够满足带宽和延迟的要求，而且能够最大可能地满足带宽和延迟的要求，且具有最 优( 或近优) 的整体代价。实验结果表明，该算法具有较高的路由成功率和适度的消息负 载，生成的组播树具有很低的网络代价。但该算法只适用于平面网络。 第5 章针对平面路由难于适用不断扩展的大规模网络的问题，提出一种分层路由 结构。本章具体分析了层次网络结构和树构造过程，并结合层次网络结构特点提出了一 种层次组播路由算法( h m r ) ，该算法具有扩展性，适用于大规模网络。实验结果表明， 层次组播路由算法的运行速度比平面路由算法快，同时减少了算法的时间复杂度和存储 空间。但组播树的性能有所降低。 第6 章给出了本文的总结，并对下一步的工作作了展望。 关键词q o s 组播路由；多q o s 约束；带宽时延约束；层次路由 _ 一 ， r e s e a c r c ho nq o s - - b a s e dm u l t i c a s t r o u t i n ga l g o r i t h m a bs t r a c t w i t ht h ep o p u l a r i t ya n dd e v e l o p m e n to fi n t e m e t ，t h e r ea p p e a rm a n yn e wa p p l i c a t i o n s t h e s em u l t i m e d i ac o m m u n i c a t i o n sh a v et h eo n e t o - m a n yc h a r a c t e r i s t i c ，w h i c hr e s u l ti n b a n d w i d t hc o n s u m ea n dc o n g e s t i o n t h e r e f o r e ，i pm u l t i c a s tt e c h o n l o g yw a sp r o p o s e dt o r e s o l v et h e b o t t l e n e c kp r o b l e mo fi n t e r n e t t h ek e yo fm u l t i c a s ti sh o wt od e t e r m i n ea n e f f i c i e n tm u l t i c a s tr o u t i n g a st h en e t w o r km a yv e r yb i g , a n dt h et o p o l o g i c a ls t r u c t u r ea n d l a r g ea m o u n t s o ft r a f f i ca r ec h a n g i n gc o n t i n u o u s l y , t h em u t l i c a s tr o u t i n gp r o b l e mi sb e c o m i n g v e r yi m p o r t a n ta n dd i f f i c u l t d y n a m i cj o i n i n ga n dl e a v i n go fm e m b e r , t h ep a r t i c i p a t i o no f q o si n f o r m a t i o n ，a n dt h en e e do fn e t w o r kh i e r a r c h i c a lr o u t i n ga r et h eo b s t a c l e st os o l v e m u l t i c a s tr o u t i n gp r o b l e m n e t w o r kr o u t i n gn o t o n l yh a v et os a t i s f yt h en e e do fu s e r s d i f f e r e n ta p p l i c a t i o n ，b u ta l s od e v e l o pt h e r e s o u r c e e f f i c i e n c yo f w h o l en e t w o r k t h et h e s i si sd i v i d e di n t os i xc h a p t e r s ： c h a p t e r1b r i e f l yi n t r o d u c e st h ec o r r e s p o n dc o n t e n to fm u l t i c a s t ，i n c l u d i n gd e v e l o p i n g b a c k g r o u n do fm u l t i c a s tr o u t i n g , r e s e a r c hs t a t u s ，m u l t i c a s tr o u t i n ga l g o r i t h m s ，m u l t i c a s tr o u t i n gp r o t o c o l sa n dt h er e l a t i v ec o n c e p t so fm u l t i c a s tt r e e ，i ta l s oi n t r o d u c e s t h es o u r c ea n dm e a n i n go f t h i st h e s i s c h a p t e r2i n t r o d u c e st h ed e v e l o p m e n ta n da p p l i c a t i o n so fm u l t i c a s t t h es e c o n dp a r t p r e s e n t e dt w ok i n d s o fm u l t i c a s tr o u t i n ga l g o r i t h m ，a n dt h ep o p u l a rm u l t i c a s t r o u t i n g p r o t o c 0 1 i nc h a p t e r3 ，i np o i n to fq o sc o n s t r a i n t s ，w ed e s c r i b e dt h ed e f i n i t i o n ，m a t h e m a t i cm o d e l ， s u m m a r i z e dt h ei n t e r n a t i o n a lq o s - b a s e dm u l t i c a s tr o u t i n ga l g o r i t h m sa n dp r o t o c o l si nr e c e n t y e a r s i nc h a p t e r4 ，ad i s t r i b u t e dm u l t i c a s tr o u t i n ga l g o r i t h mw i t hm u l t i p l eq o sc o n s t r a i n t s ， w h i c hs o l v e st h en p c o m p l e t ep r o b l e mi nm a n n e ro fad i s t r i b u t e dc o m p u t a t i o ni sp r e s e n t e di n m r m q t h em u l t i c a s tt r e eb ym r m qc o n s t r u c t e dc a nn o to n l ym e e tt h er e q u i r e m e n t so f b a n d w i d t ha n dd e l a y , b u ta l s ot ot h em a x i m u me x t e n tp o s s i b l et om e e tt h er e q u i r e m e n t so f b a n d w i d t ha n dd e l a y , a n dw i t ht h eo p t i m a l ( o rn e a ro p t i m a l ) o ft h eo v e r a l lc o s t e x p e r i m e n t a l r e s u l t ss h o wt h a tm r m qi ta c h i e v e sah i 曲r o u t i n gs u c c e s sr a t i ow i t ham o d e s tm e s s a g el o a d ， a n dg e n e r a t e dm u l t i c a s tt r e ew i t hav e r yl o wc o s tn e t w o r k i nc h a p t e r5 ，f o rt h ep r o b l e mt h a tf i a tr o u t i n gi sd i f f i c u l tt os u i tf o rt h eg r e a tn e t w o r ks p r e a d i n g ，a h i e r a r c h i c a lr o u t i n gs t r u c t u r ei sp r o p o s e d t h eh i e r a r c h i c a ln e t w o r ks t r u c t u r ea n dt h ep r o c e s so f c o n s t r u c t i n gt r e ea l ea n a l y z e d ，ad y n a m i ch i e r a r c h i c a lm u l t i c a s ta l g o r i t h mi sp r o p o s e db a s e do nt h e i r v c h a r a c t e r i s t i c i th a st h es c a b i l i t ya n ds u i tf o rg r e a tn e t w o r k e x p e r i m e n t a lr e s u l t ss h o wh m r i sm o r e e 币c i 朗tt h a nd f m ra n dr c d u c 髂t h ec o m p l e x i t yo ft i m ea n ds t o r a g es p a c e b u tt h ep e r f o r m a n c eo f m u l t i c a s tt r e eb e c o m e1 0 w e r c h a p t e r6s u m m a r i z e st h i st h e s i s ，i na d d i t i o n ，s u g g e s t i o n s f o rf u t u r er e s e a r c ha r eg w e n k e y w o r d s ：q o s b a s e d m u l t i c a s tr o u t i n g ，m u l t i p l eq o sc o n s t r a i n t s ，d e l a y - b a n d w i d t h c o n s t r a i n e d h i e r a r c h i c a lr o u t i n g v l ，i 东北大学硕士学位论文 独创性声明 摘要 a b s t r a c t 第l 章绪论 1 1 研究背景 1 2q o s 路由研究现状 1 3q o s 路由研究面临的问题 1 4 研究意义 1 5 研究内容 1 6 本文的主要结构 第2 章组播路由 2 1 组播简介 2 2 组播路由的理论基础 2 3 组播路由实现技术 2 3 1 组播路由算法 2 3 2 组播路由协议 2 4 小结 第3 章q o s 约束的组播路由 3 1 概述 3 2q o s 约束的数学模型 3 3q o s 度量及特征 3 3 1q o s 度量一 3 3 2q o s 度量特征一 3 4q o s 约束组播路由算法和协议 3 4 1q o s 约束组播路由算法 3 4 2q o s 约束组播路由协议一 3 4q o s 组播的网络体系结构 3 5 小结 第4 章一种支持多q o s 约束的组播路由算法2 7 4 1 算法提出的背景2 7 4 2 网络模型2 7 4 3 路由算法2 8 4 3 1 基本思想一2 8 4 3 2 路由过程2 9 4 4 算法复杂性3 1 4 5 仿真实验3l 4 5 1 仿真环境一3 1 4 5 2 实验结果3 2 4 6 ，j 、结3 3 第5 章一种支持q o s 的层次组播路由算法3 5 5 1 算法提出的背景3 5 5 2 网络模型3 6 5 2 1 层次网络模型3 6 东北大学硕士学位论文 目录 5 2 2q o s 组播路由模型3 6 5 3 层次组播树的结构和构造过程3 6 5 3 1 层次网络结构3 6 5 3 2 层次组播树构造过程3 7 5 4 层次组播路由算法( h m r ) 3 9 5 5 实验仿真4 0 5 6 ，j 、结4 3 第6 章结论4 5 6 1 工作总结4 5 6 2 进一步工作研究4 5 参考文献4 7 致谢51 v l l l 东北大学硕士学位论文第1 章绪论 1 1 研究背景 第1 章绪论 近年来，在高性能网络上传输实时多媒体业务的需求同益高涨。随着i n t e m e t 规模 的不断增大，各种各样的网络服务争相涌现，先进的多媒体系统层出不穷。由于实时业 务对网络的传输时延，延时抖动等特性比较敏感，当网络上有突发性高的f t p 或者含有 图像文件的h 1 v r p 等业务时，实时业务就会受到很大影响，另一方面，多媒体业务占去 了大量的带宽，这样，现有的网络要保证的关键业务就难以得到可靠的传输。解决这些 问题的最简单的办法是增大带宽，但由于代价高昂，所以并不十分可行。于是各种服务 质量( q o s ，q u a l i t yo f s e r v i c e ) 技术应运而生，它们通过对数据包进行排队，对某些特定的 数据包赋予较高的优先级等方式，来满足各种业务的q o s 需求。在城域网或i n t e r n e t 中， 采用单播方式将相同的数据包发送给网络中的多个而不是全部接收者时，由于需要复制 分组给每一个接收端点，随着接收者数量的增多，需要发出的包数也会线形增加，这使 得发送主机、路由设备及带宽资源总体负担很重，效率受到极大影响。随着多点电视会 议、群组通信应用等需求的增长，为了缓解网络瓶颈，人们提出增加互连带宽、改变网 络流量结构组播技术等方案。其中组播技术既能很好的缓解各种应用对网络带宽的需 求，同时避免了对网络结构进行大规模颠覆性改变所可能带来的耗费。 组播技术可以将信息从一个源同时发送给网络上一组接收者，实现了点到多点和多 点到多点的通信。信息只在需要时进行复制分发复制信息少，节省网络资源。使用i p 组播技术传输信息能从本质上减少新型应用对网络带宽的需求，在有限带宽的网络中， 有效利用网络资源是很重要的。 由于互联网络特别庞大，拓扑结构复杂，网络流量处于不断的动态变化中，使得组 播技术中的组播路由问题变得非常困难，然而组播路由对于组播传输又是特别的关键。 而且新型网络应用中对网络传输的q o s 要求，也对组播路由问题的解决造成了不小的障 碍。网络路由既要满足用户不同应用的要求，又要能尽量提高网络整体资源的利用率。 虽然组播技术在经过一定时间的发展后，很多研究人员及网络专家提出了大量有价值的 组播路由算法和协议上的解决办法。但是由于算法过于复杂及不能适应实际网络需要等 原因，并没有在实际网络环境中得到广泛应用。应用促使组播路由算法与各种路由相关 协议紧密地结合起来，充分发挥组播路由的优势。 东北大学硕士学位论文第1 章绪论 1 2q o s 路由研究现状 i e t f 提出的i n t s e r v 体系结构在文献【l 】中给出，将其框架划分为综合服务模型和参 考实现框架两大部分。在服务层次上，除了原来的尽力而为服务外，i n t s e r v 还以每个流 为基础，提供了两种端到端的面向实时传输的服务：质量保证服务和可控负载型服务。 i n t s e r v 依靠资源预留协议r s v p 提供q o s 协商机制，逐节点地建立或拆除每个数据流 的路径状态和资源预留软状态( s o f ts t a t e ) ；依靠接纳控l j ( a d m i s s i o nc o n t r 0 1 ) 决定链路或节 点是否有足够的资源满足用户的资源预留请求；依靠传输控l j ( t r a f f i cc o n t r 0 1 ) 将i p 分组 分成不同的传输流，并根据每个流的状态对分组的传输实施q o s 路由、传输调度 ( s c h e d u l i n g ) 等控制。i n t s e r v 是基于流的( 单独的或聚集的) 状态相关的体系结构，依赖于 每个流( f l o w ) 的状态和对每个流的管理。这种实现机制一方面是i n t s e r v 能够提供较状态 无关的体系结构，具有更高的灵活性和更好的服务级别保证服务，但同时也导致了 i n t s e r v 的可扩展性问题和鲁棒性问题，后果是实现复杂，难以应用。另外，i n t s e r v 的 实现必须依赖r s v p ，而目前只有少量的主机产生r s v p 信令，虽然其数量预计会大幅 度增长，但许多应用却从不产生r s v p 信令，这也更增大了实现的难度。 区分服务体系结构d i f f s e r v 是在i n t s e r v 发展遭遇巨大障碍时产生的，其目标在于 简单有效，以满足实际应用对可扩展性的要求，实现途径是： ( 1 ) 简化网络内部节点的服务机制。在内部节点只进行简单的调度转发，而流状态信 息的保存与流监控机制的实现等只在边界节点进行，内部节点是状态无关的。 ( 2 ) 简化网络内部节点的服务对象。采用聚集传输控制，服务对象是流聚集( s t r e a m a g g r e g a t e ) 而非单流，单流信息只在网络边界保存和处理1 4 1 。 具体而言，边界节点根据用户的流规定( p r o f i l e ) 和资源预留信息将进入网络的单流 分类、整形、聚合为不同的流聚集，这种聚集信息存储在每个l p 包头d s ( d i f f e r e n t i a t e d s e r v i c e s ) 标记域( f i e l d ) 中，称为d s 标记( d i f f e r e n t i a t e ds e r v i c e sc o d e p o i n t ，d s c p ) ；内部节点 在调度转发i p 包时根据包头的d s c p 选择特定质量的调度转发服务，其外特性称为逐 点行为( p e r - h o p - b e h a v i o r , p h b ) 。网络边界对单流作分类聚合，网络内部对聚集流提供特 定质量的调度转发服务，这两个过程通过i p 包头内的d s c p 协同起来。 d i f f s e r v 提供的是相对粗糙的q o s 划分，没有处理单个流( p e r - f l o w ) 的复杂性， 有很好的可扩展性。但是d i f f s e r v 注重的是如何划分业务量和快速传输，它运行的仍然 是传统的尽最大努力服务的路由算法，不能保证端到端的q o s 需求。 r f c 3 0 31 2 】定义了m p l s 多协议标签交换体系。m p l s 是对第二层a t m 标记交换和 第三层路由选择的有机结合，工作在网络层和数据链路层之削3 1 。m p l s 既实现了a t m 东北大学硕士学位论文第1 章绪论 的面向连接、简单高速交换、q o s 保证、流量管理、流量工程，又实现了l p 的灵活性、 有效性和可扩展性等优点。 m p l s 分离了传统选路的“控制”和“转发”两个部分的功能。m p l s 域中标记边缘路 由器l e r 将进入m p l s 域的分组进行快速分类，并映射到转发等价类f e c 。核心标记 交换路由器l s r ，能迅速处理分组上的标记，并对己打上标记的分组进行快速转发。从 f e c 得到的标记通过标记分配协议l d p 在m p l s 网络中建立一条标记交换路径l s p ， 打上标记的分组就沿着路径l s p 传送。与a t mp v i p v c 一样，标记只具有本地意义， 多个标记可以嵌套构成标记栈，可以实现现实路由和层次化路由。由于使用基于标记的 转发，不仅省去了每到一个节点都要到第三层查找路由表的过程，使分组转发的速率大 大加快，而且还能使网络上的通信量负载更加平衡。 如何将q o s 路f l d ( q o s - - b a s e dr o u t i n g ，q o s r ) 应用到d i f f s e r v 和m p l s 等体系结构 也是一个热门的研究领域。为了更好地保证服务质量，最近又提出了一种新的路由机制， 称为q o s 服务路i 土t ( q o ss e r v i c er o u t i n g ，q o s s r ) 。这样，传统的q o s 路由被归类为q o s 数据路o d ( q o sd a t ar o u t i n g ，q o s d r ) 。 q o s s r 主要基于以下两个假设： ( 1 ) 大多数多媒体服务由一些更小的子服务组成，即服务是可组合的。这样，可以按 一定顺序依次应用多个服务来完成传送一个复杂服务的目的。 ( 2 ) 多媒体服务可以由网络的某个特定的地点提供。这样就可以在网络的一些特定 的地点设置代理，每个代理都有自己的容量和带宽限制，从而构造一个覆盖多媒体服务 的代理服务网络。于是问题就变成寻找一条路径，这条路径包含按一定顺序排列的所有 必须的服务。 文献【4 】提出了q o s s r 的关键步骤：( 1 ) 详述服务需求；( 2 ) 构造覆盖代理网络；( 3 ) 将服务需求映射到代理网络；( 4 ) 设计路由算法。 q o s s r 不同于q o s d r ，q o s d r 主要描述网络层的q o s 路由，而q o s s r 则工作在 应用层，是服务传送网络( s e r v i c ed e l i v e r yn e t w o r k ，s d n ) 的重要组件。二者都能被应用 到i e t f 提出的i n t s e r v 、d i 腮e r v 、m p l s 等网络体系结构中。 1 3q o s 路由研究面临的问题 q o s 路由的主要目标有： ( 1 ) 动态选择可行路径，为每个可接受的q o s 业务流提供服务质量保证。q o s 路由 能从多个可能的选择中，选出最可能满足数据流需求的路径。 东北大学硕士学位论文第1 章绪论 ( 2 ) 最优化全局资源利用率。q o s 路由策略通过增大网络吞吐量，有效提高网络资 源利用率，这也是网络优化管理的基本目的。 ( 3 ) 对性能影响尽量小。在网络负载过重等情况下，路由算法应有较强的鲁棒性保 证网络的良好性能，提供较高的吞吐量。 当前i n t e m e t 路由协议，如o s p f 、r p i ，都使用最短路径路由，只优化一个度量， 如时延或跳数。这些路由协议使用当前的最短路径发送数据到目的地，被称为“机会主 义”路由协议。而那些具有可接受但非最优代价的可选路径却不能用来传输通信业务。 q o s 路由必须从三个基本方面改进当前的路由模式： ( 1 ) 为了使用综合服务业务支持通信传输，必须能计算节点对之间的多条路由。这 里的综合服务( i n t e g r a t e ds e r v i c e ，i s ) 在文献 1 】中定义，包括最大努力服务，实时服务和控 制链路共享服务。 ( 2 ) 在当前的机会主义路由协议工作模式下，即使原来的路径满足当前业务的服务 需求，一旦找到更好的路径，通信业务就改变传输路径，在新的当前最优路径上传输业 务。如果路由算法的计算与网络资源( 如可用带宽) 之间有很大联系，则当网络状态变化 比较频繁时，传输路由就会产生很大的振动，在可选路径之间来回变换。另外，这样也 会增大终端用户之间的时延抖动。 ( 3 ) 当前最优路径路由算法不支持可选路由，如果最优路径不能满足一个数据流的 传输要求，即使存在一条更合适的路径，算法也不会选择这条路径来传输。 因此q o s 路由算法的设计是一个很复杂的问题，一个有效的o o s 路由算法必须考 虑诸多因素，具体体现在以下几个方面： ( 1 ) 算法的复杂度。复杂度涉及到解决一个问题或执行一个算法所需的最少资源， 包括时间复杂度和空间复杂度。时间复杂度是q o s r 首先要面对的最重要问题。由于多 约束q o s 路由问题具有n p 性质，传统的最优算法无法在多项式时间内求得最优解，其 时间复杂度往往随问题规模的增加而以指数速度增加，因此解决q o s 路由问题多用启发 式算法。启发式算法是一种技术，这种技术使得在可接受的计算费用内去寻找最好的解， 但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法阐述所得解同最优 解的近似程度。在获得解的最优程度和计算时间、占用空问之间有一个权衡，目的是要 花费尽量少的时间和空间获得尽量优的解。 ( 2 ) 算法的可扩展性。现有的路由算法大多不具备很好的可扩展性，计算时间往往 随着网络规模的增大而以指数速度增加，不能应用到实际的大规模网络中。通过网络状 态聚集能够以对数缩减信息量，相应的分层路由可以通过限制每层内节点的数量使用源 - 4 东北大学硕士学位论文第1 章绪论 路由方式，从而很好地解决可扩展性问题。但这同时又引入了新的问题：如何聚集状态 信息、如何基于聚集状态设计良好的启发式算法。目前所设计的状态信息聚集方法会丢 失大量可用信息，严重影响了q o s r 算法的性能；同时，所设计的启发式算法也往往是 基于全局状态源路由策略的。此外，由于很多q o s 问题的精确求解复杂度都是n p c 的， 冈此需要设计快速、有效的启发式算法。 ( 3 ) 非精确路由信息问题。网络状态的彳i 断变化、网络的分层体系结构和网络信息 聚合都会导致路由信息的非精确性。非精确路由信息可能会使路由选择失败，重新进行 路由计算和发送预约信令，从而增大网络丌销和业务时延。分布式路由中，不准确的路 由信息还可能导致环路。一种解决方案是合理设计路由信息更新方法。路由信息的更新 直接关系到每个节点保留信息的准确性。信息更新越频繁，节点获得的信息准确性越高， 但同时引入的信息开销也越大。合理的路由信息更新策略能够有效均衡信息准确性与路 由开销，同时也可以为路由算法性能与算法可实现性找到合适的折中点。另外一种方法 是概率模型求解。按照度量参数取值的概率选择一条具有最大可能性的路径，可以克服 信息不准确性为选路带来的影响。 ( 4 ) q o s 路由与尽最大努力服务路由的共存问题。文献 5 】对这个问题进行了讨论。 将q o s r 融入到当前这种尽力发送的路由体系结构中，原有的尽力发送业务将受到巨大 冲击。今后的网络应该是q o s r 和尽力发送相结合的1 6 】。网络的路由目标是最大化资源 效用，这包括尽可能地接纳更多的q o s 连接请求，同时最大化尽力发送业务的吞吐量和 相应速度。由于这两者是矛盾的，因此二者融入的过程会产生很多问题。例如，在有资 源预留的链路空闲时，没有资源预留的链路却可能由于尽力发送业务而造成拥塞。这种 拥塞的链路仍然有可能因为尚未预留资源而接受q o s 请求。此外，q o s r 算法必须与其 他网络组件结合才能提供q o s 保证，包括状态收集、资源预留、分组调度等，因此可以 考虑这种结合过程对q o s r 算法和其他网络组件的简化。 ( 5 ) 多路路由与重路由。多路路由有两种解释：第一，在多条可能的路径上同时探 测可行路径，如何与资源预留相结合尚无定论【7 j 。第二，网络提供多条从源到目的的路 径，并将这些路径并行复用起来( 如增加带宽) 而对用户业务透明，这是一种多路复用的 路由方式。然而，其主要问题是多条路径之问如何同步，以及如何避免分组的延迟抖动、 乱序等博j 。由于网络资源和可行路径分配的不合理，因而在某些情况下需要重新路由。 重路由在网络资源不足时进行，能够有效地重新分配网络资源，但由于存在状态保存、 同步和丌销等问题，使重路由变得困难。 ( 6 ) 算法实现问题。假定我们已经解决了算法的复杂度问题，仍然有两点需要考虑： 东北大学硕士学位论文第1 章绪论 第一，不同的通信业务有不同的度量，所以路由器对每一个新接入的通信业务必须能应 用相应的算法；第二，大多数的路由算法都假定在计算之前已经获得了足够的路由信息， 即假定路由协议已经获得了这些信息。但在实际网络中，对多约束路由，频繁的在网络 中传输多个度量的路由信息将会极大地增加网络负荷。 1 4 研究意义 相比传统的互联网络，现今的网络中承载着多种多样的网络服务，如视频点播，远 程分布控制、视频会议等，这些实时业务要求通信网络能够提供端到端的服务质量保证， 以满足端用户对服务品质的要求。传统路由机制根据最短路径算法，求解在给定的某个 代价准则下的路径，不能很好地支持实时q o s 通信的要求。为了支持此类应用，需要 寻求更有效的层次组播路由算法根据网络服务的发展和需要，着眼网络的发展趋势，组 播q o s 技术具有很强的竞争力，可以满足广大网络用户和网络供应商的新要求，具有很 强的研究价值和应用前景。 研究基于i n t e r n e t 的q o s 路由算法，能获得较好的网络服务质量和较高的网络资源 利用率。基于组播的音频视频流媒体应用如晚会和音乐会的实况转播、i p 网络视频会 议、远程教学等都是l p 组播的重要应用领域。基于i p 组播技术还可以开发聊天组、交 互式仿真、大众游戏等应用。随着i n t e r n e t ，移动i n t e r n e t 等高性能网络技术的不断发展 演进，基于q o s 的组播路由协议的设计理论与方法的研究，已经成为网络领域的一类重 要的课题。 1 5 研究内容 1 讨论了q o s 路由技术的发展背景，归纳和分析当前q o s 路由算法研究和面临的 情况，指明了其中一些有待进一步研究的问题； 2 提出了一种分布式、多q o s 约束的组播路由算法。在算法中，采用了分布式计算 方式来化解多q o s 约束的n p 完全问题。实验结果表明，该算法具有较高的路由成功率 和适度的消息负载。 3 针对大规模网络中q o s 组播路由的扩展性问题，提出一种分层路由结构，具体 分析了层次网络结构和树构造过程，并结合层次网络结构特点提出了一种动态层次组播 路由算法，该算法具有扩展性，适用于大规模网络。 东北大学硕士学位论文 第1 章绪论 1 6 本文的主要结构 本文具体内容安排如下： 第一章介绍了q o s 组播路由问题的研究背景、研究现状、意义和面临的问题，列出 了本文的主要研究内容和组织结构。 第二章介绍组搔的核心路由问题，包括组播路由算法和实际网络应片j 的组播路由协 议。 第三章介绍网络业务的q o s 定义和其数学描述，在此基础上介绍带q o s 的部分组 播路由算法和协议以及几种i e t f 为实现q o s 所提出的网络体系结构。 第四章提出了一种分布式、多q o s 约束的多播路由算法。在算法中，采用了分布式 计算方式来解决多q o s 约束的n p 完全问题。 第五章针对大规模网络中q o s 组播路由的扩展性问题，提出一种分层路由结构，具 体分析了层次网络结构和树构造过程，并结合层次网络结构特点提出了一种动态层次组 播路由算法。 第六章总结全文，归纳和总结了组播技术在网络上的实际应用问题，并对以后的发 展研究方向提出一些建议。 东北大学硕士学位论文第2 章组播路由 第2 章组播路由 对于实际应用的组播技术来说，涉及到的研究内容很多，包括支持组播的网络体系 结构，组播通信的安全可靠，组播选路，组播协议的实现等，但是其中最关键的是组播 选路路由和相应的网络组播协议。本章将对组播的一些关键问题进行介绍和分析。 2 1 组播简介 组播( m u l t i c a s t ) ，也称多播，它允许一个或多个发送者发送数据包加入到同一组内 的多个接收者，数据在需要的分支点进行复制分发，只有属于该组播组的主机才能接收 到数据包。在相同的发送者，接收者和发送信息量的情况下，与单播相比，组播网络中 需要传输的复制信息少，提高了数据传送效率，节省网络资源，能够从本质上减少对整 个网络的带宽要求，同时减少了主干网络上出现传输拥塞的可能性，优化了网络性能。 l p 组播( i pm u l t i c a s t ) 是标准i p 协议的扩展，在i e t f 的r f c i1 1 2 中这个概念的 定义是“组群的i p 数据报的播送”【9 】。普通i p 通信是在一个发送者和一个接收者间进 行的，l p 组播能同时向大量接收者发送信息，是一种用于i n t e r n e t 的扩展i p 网际协议。 利用这个协议，应用程序可以传递一份信息给一个组地址( 也称多点地址) ，所有属于 这个小组的成员都能收到这个消息。这样就大大减少了网上的传输量，节省了网络带宽 和处理量。由于典型的m p e g 2 视频信息流需要大约1 - 5 m b p s 的带宽才能使影像流畅、 逼真，因此用i p 组播来发送视频信息流是一种明智的选择。 组播技术包括很多方面的内容，但最核心的是如何建立发送者到接收者的传输路径 问题，即组播的选路路由问题。设计或选取合适的组播选路算法对组播选路的有效实施 非常重要。所有组播选路方法都应该提供一种传播成员信息的机制，以及转发数据报时 使用该信息的方式。组播设计应该代表选路通信量超载和低效数据传输之问的一种折 衷。群组成员信息必须通过互联网进行传播。而一般来讲，因为成员关系会迅速改变， 从给定路由器可得的信息是不完整的，因此选路可能滞后于变化。一方面，如果群组成 员信息没有迅速传播，组播路由器将不能做出最佳决策。另一方面，如果组播选路方法 把每个成员关系变化都通知给每个路由器，产生的通信量就会让互联网无法承受，对于 互联网来说就是场灾难。 历时多年的发展，有关组播选路问题提出了很多的算法，并且形成了一些比较完善 的组播网络协议体系，包括组播主机和网络的交互协议、组播路由协议、组播地址管理 协议等。由于互联网络上还存在大量不支持组播的传输设备，1 9 9 2 年研究者丌发了 m b o n e ( i n t e r n e t 组播主干) ，对组播网络体系和运行其上的应用系统进行实际网络测试， 东北大学硕士学位论文第2 章组播路由 取得了显著的成绩，同时也证明了组播技术在互联网络上的实用性。随着网络技术的发 展和人们需求的增长，现在支持组播技术的网络设备越来越普遍，相信组播技术将会全 面的应用于互联网络。 2 2 组播路由的理论基础 实现组播技术首要是要建立从组播源到组播成员的一系列传输路径，信息从组播源 开始，沿着构造的路径在路径分叉节点处复制分发，最终传送到所有的接收者。这样的 机制节约了信息传输过程中所耗费的网络资源，减少了信息到达接收者的延迟。所以说 构造这样的路径对组播信息传输来说是至关重要的，但是怎样构造合适的路径昵? 将实际复杂的网络结构简化为抽象的数学模型有助于解决这一问题，这里介绍经典 的三种模型： 1 最短路径模型 当我们试图确定网络中一个或多个节点对间最短、最便宜、或最可靠路径时，就产 生了最短路径问题。最短路径问题占据了网络技术的大多数最显著的核心问题。许多网 络问题最终转换为最短路径模型。 在最短路径问题中，我们给出一个有向图g = ( v ，e ) ，其中v 是节点集，e 是边集。 每条边e e 有一个权c 。权可以有下面的意义：距离、代价、时问、处罚、丢失等。 考虑节点对v l 和v k ，一条路径p = v i e i v 2 e 2 v k _ l e k l v t ，v i v ，e i e ，w 是这条 路径上权的和，即： k l w ( p ) = c 岛( 2 1 ) i - - i 最短路径问题是找到由v l 开始到v k 结束的