（计算机应用技术专业论文）分布式多路径qos组播路由算法与协议研究.pdf

摘要 随着i n t e r n e t 的迅速发展，群组通信特别是计算机视频会议、网络音视频 广播、股市行情发布、远程教育、计算机支持的协同工作( c s c w ) 、分布式交 互仿真等大量兴起。这些新型应用大大推进了社会信息化进程。组播技术正是这 些应用的重要基础。组播不同于单播和广播，它将分组发送到一个指定的主机集 合，即通信群组。组播的最大特点在于，在组播网络中即使用户数成倍增长，主 干带宽也无需随之增加。因此组播成为当前网络技术研究的热点。组播技术研究 主要涉及组播路由算法与协议、群组成员关系管理、组播地址分配、接纳控制和 组播应用等问题。 本文首先研究了5 组播路由问题的一般性描述，评述了国内外关于s 组播路由算法和协议的研究进展，对现存算法和协议进行了分类，研究了组 播路由算法与协议的联系及区别。接着，讨论了s 组播路由算法与协议设 计的基本目标，分析了组播路由算法与协议问题的复杂性，研究了o o s 组播 路由算法与协议性能评价的主要指标以及模拟仿真方法的有效性。本文的主 体部分重点研究o o s 组播路由算法和协议、接纳控制和多媒体应用等方面的问 题。 1 ) 首次将局部存储结构引入q o s 组播路由，使路由器只存储其两层邻居节 点的可达性信息以及链路的q o s 状态信息，以减少路由器存储开销，提高协议 的规模伸缩性；利用这些信息，节点能够更加智能化地转发加入探测报文 j o i n _ p r o b e 。针对组播的需要，设计了一套数据结构和组播树构造算法，从而提 出了一种新的支持o o s 特性的多路径组播路由协议q m o b f 。分析表明，基于受 限泛播技术的组播路由协议具有节点存储开销小、呼叫接收成功率高、伸缩性好 等特点。 2 ) 研究了s 组播路由的综合优化问题，提出了一种综合性启发式函数， 该函数能够有效使组播树的延时、带宽和网络代价特性都得到一定程度的优化， 并有效地运用到q m o b f 协议中。 3 ) 研究了一种结合集中式算法与分布式算法优点的多路径启发式q 0 s 组播 路由协议，试图进一步降低控制报文开销并获得较高的呼叫成功率。算法依赖单 播路由协议o s p f 的链路状态广告报文( l i n k s t a t ea d v e r t i s e m e n t ，l s a ) 传播链 路的代价状态信息。该协议能够有效支持延时和带宽受限的代价优化组播树构 造，具有控制报文开销小、可伸缩性好、呼叫成功率高等特点。 第l 页 4 ) 研究了多路径q o s 组播路由协议q m o b f 与接纳控制相融合的方案， 该方案面向支持负载受控服务、有保证服务和尽力而为服务的综合网络结 构，并使用延时和带宽作为接纳参数。由于q m o b f 协议能够有效地支持延 时和带宽受限的代价优化组播树构造，并具有无环选路、呼叫接收成功率高、 可伸缩性好等特点，因此在q m o b f 算法中集成接纳控制机制将有助于该协 议的进一步发展。 5 ) 在组播应用上，本文针对传统面向连接的传输结构存在连接多、复杂度 高、伸缩性差等诸多问题，提出了一个基于源根组播的视频会议系统设计原则， 它使系统结构得到简化，可靠性、易用性和规模伸缩性得到提高。本文提出了一 个基于源根组播的会议系统模型，并开发出一个功能强大的多点视频会议系统。 关键词网络服务质量，组播路由算法，协议，性能评价，组播路由综合优化 组播应用，多点视频会议系统 第n 页 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h e i n t e m e t ，g r o u pc o m m u n i c a t i o na p p l i c a t i o n s s u c ha s v i d e o c o n f e r e n c i n g ，n e t w o r k a u d i o v i d e o b r o a d c a s t i n g ，s t o c k i n f o r m a t i o n d i s t r i b u t i o n ，r e m o t ee d u c a t i o n ，c s cw a n dd i s t r i b u t e di n t e r a c t i v es i m u l a t i o n ，e t c ，a y e e m e r g i n g a l lt h e s ea p p l i c a t i o n sr e l yo nm u l t i c a s tt e c h n o l o g y m u l t i c a s ti sd i f f e r e n t f r o mu n i c a s ta n db r o a d c a s ti nt h a ti td i s t r i b u t e sp a c k e t st oa s p e c i f i cs e to f h o s t sa sa g r o u p t h em o s ts i g n i f i c a n tc h a r a c t e ro f m u l t i c a s ti st h a ti t sc o n s u m p t i o no fn e t w o r k r e s o u r c e sd o e sn o ti n c r e a s ew i t ht h en u m b e ro fh o s t s s om u l t i c a s ti sav e r yh o ta r e a o fn e t w o r kt e c h n o l o g ya n da t t r a c t sa t t e n t i o n so fm a n yr e s e a r c h e r s m u l t i c a s th a s m a n yr e s e a r c h i n g d i r e c t i o n ss u c ha s r o u t i n ga l g o r i t h m s a n d p r o t o c o l s ，g r o u p m e m b e r s h i pm a n a g e m e n t ，m u l t i c a s t a d d r e s s a l l o c a t i o n , a d m i s s i o nc o n t r o l a n d m u l t i c a s ta p p l i c a t i o n s ，e t c t h i st h e s i sf i r s ts t u d i e st h eg e n e r a ld e s c r i p t i o no f q o s m u l t i c a s tr o u t i n gp r o b l e m ， g i v e s a s u r v e y o fm u l t i c a s t r o u t i n ga l g o r i t h m s a n d p r o t o c o l s ，d i v i d e se x i s t i n g a l g o r i t h m sa n dp r o t o c o l si n t os o m ec l a s s e s ，a n dd i s c u s s e s t h ec o m p l e x i t yo fm u l t i c a s t r o u t i n g i t a l s os t u d i e st h es t a n d a r d so ft h ep e r f o r m a n c ee v a l u a t i o no fm u l t i c a s t r o u t i n ga l g o r i t h m sa n dp r o t o c o l sa n d s i m u l a t i o nm e t h o d s t h em a i nb o d yo ft h i sa r t i c l es t u d i e sq o sm u l t i c a s tr o u t i n g a l g o r i t h m sa n d p r o t o c o l s i ta l s os t u d i e sa d m i s s i o n c o n t r o la n dm u l t i c a s t a p p l i c a t i o n s 1 ) w ed e e p l ys t u d y an e w t y p eo f q o s m u l t i c a s ta l g o r i t h mb a s e do nb o u n d e d f l o o d i n g t e c h n i q u e t h i sa r t i c l ep r o p o s e s an o v e lq o s - a w a r em u l f i c a s t m u t i n gp r o t o c o la i m i n g a ta l l e v i a t i n gt h em e m o r yo v e r h e a do ft h er o u t e r sf o rs e t t i n gu pm u l t i c a s tt r e e sa n d i m p r o v i n gs c a l a b i l i t yo f t h ep r o t o c 0 1 i no u rs c h e m e ，e v e r yn o d en e e d st om a i n t a i na t w o l e v e lf o r w a r d i n gt a b l ew h i c hc o n t a i n si n f o r m a t i o na b o u ti t si m m e d i a t e n e i g h b o r s ( r o u t e r sr e a c h a b l ei no n eh o p ) a n di t ss e c o n d d e g r e en e i g h b o r s ( n e i g h b o r so fa n i m m e d i a t eo n e ) b ym e a n so ft h ei n f o r m a t i o na b o u tt h es e c o n d d e g r e en e i g h b o r s ，a r o u t e rc a nf o r w a r d j o i n _ p r o b em e s s a g e si n t e l l i g e n t l yi n s t e a do ff l o o d i n gt h e mb l i n d l y o u r p r o t o c o la l s ou t i l i z e sm u l t i - p a t hs e a r c h i n gt oi n c r e a s et h ep r o b a b i l i t yo ff i n d i n g f e a s i b l eb r a n c h e sw h e nc o n n e c t i n gan e wn o d et ot h em u l t i c a s tt r e e t h ep a p e r d e s c r i b e st h ed e t a i l so ft h ed a t as t r u c t u r e so ft h ep r o t o c o la n dt h ea l g o r i t h mo f b u i l d i n gad i s t r i b u t i o nt r e e i ts h o w s t h ee f f e c t i v e n e s so ft h i sp r o p o s e dp r o t o c o lb y 第1 i i 页 e v a l u a t i n gt h ep r o t o c o l sp e r f o r m a n c ei nt e r m so fa v e r a g ec a l la c c e p t a n c er a t i oa n d a v e r a g ec o n t r o lm e s s a g eo v e r h e a dt h r o u g hs i m u l a t i o n 2 ) t h ea r t i c l ea l s os t u d i e sa l li n t e g r a t e do p t i m i z a t i o no fm u l t i c a s tr o u t ea n di t s a l g o r i t h m ，a n dp r o p o s e sav e r ye f l q c i e n ti n t e g r a t e dh e u r i s t i cf u n c t i o nw h i c hc a r lb e u s e dt oo p t i m i z em u l t i c a s td e l a y , b a n d w i d t ha n dn e t w o r kc o s tt os o m ee x t e n t t h e f u n c t i o ni sc o m b i n e di n t ot h ep r o p o s e d p r o t o c o lq m o b e 3 ) w es t u d ya n o t h e rs t y l eo fq o sm u t i c a s tp r o t o c o lm a d eb yi n t e g r a t i n g t h e c e n t r a l i z e dm e t h o d sa n dt h ed i s t r i b u t e do n e si no r d e rt or e d u c et h ea v e r a g ec o n t r o l m e s s a g e o v e r h e a da n d k e e p ah i g hc a l la c c e p t e ds u c a ) e s sr a t i o o u rp r o p o s e dp r o t o c o l h a sg o tt h e d e s i g nd e s t i n a t i o n 4 ) t h i st h e s i sr e s e a r c h e st h em e c h a n i s mo fi n t e g r a t i n go u rq m o b f w i t ha l la d m i s s i o n c o n t r o l a l g o r i t h m u s i n gd e l a ya n db a n d w i d t ha s t h e p a r a m e t e r s w ed e v e l o p a 1 1 a d m i s s i o nc o n t r o lc r i t e r i o nw h i c hc a nb eu s e di nt h er e d u c e ds e r v i c e s e ta r c h i t e c t u r e s u p p o r t i n gl o a d - c o n t r o l l e ds e r v i c e ，g u a r a n t e e ds e r v i c ea n db e s t - e f f o r ts e r v i c e o u r q m o b fp r o t o c o lc a nd e v e l o pf u l l e rb a s e d0 1 1t h i sw o r kb e c a u s et h ep r o t o c o ln e e d s a na d m i s s i o nc o n t r o lm e c h a n i s m 5 ) a p p l i c a t i o nb a s e do f fn e t w o r km u l t i c a s tt e c h n i q u ei sa l s os t u d i e di n t h i st h e s i s r e c o g n i z i n gt r a d i t i o n a lc o m m u n i c a t i o nm o d e l so fv i d e o c o n f e r e n c i n gs y s t e m sh a v e m a n yd i s a d v a n t a g e ss u c ha sm a n yc o n n e c t i o n s ，h i 曲c o m p l e x i t ya n dl o ws c a l a b i l i t y , w e p r o p o s ean e wv i d e o c o n f e r e n c i n gd e s i g nr u l et h a tc a ne n a b l ev i d e o c o n f e r e n c i n g s y s t e ms i m p l e r , m o r ef e a s i b l e ，r o b u s ta n ds c a l a b l e w eh a v ed e v e l o p e d a l li pm u l t i c a s t v i d e o c o n f e r e n c i n gb a s e do nm i c r o s o f t st a p i ，av e r yp o w e r f u lt o o lf o rd e v e l o p i n g h 3 2 3a n di pm u l t i c a s tv i d e o c o n f e r e n c i n g t h i sa r t i c l ei n t r o d u c e st h ea r c h i t e c t u r eo f o u ri pm u l t i c a s tc o n f e r e n c i n ga n dt h er e a l i z a t i o n t e c h n i q u e so f t h es y s t e m k e yw o r d sq u a l i t yo fs e r v i c e ，m u l t i c a s t a l g o r i t h m ，p r o t o c o l ，p e r f o r m a n c e e v a l u a t i o n ，m u l t i c a s tr o u t i n gi n t e g r a t e do p t i m i z a t i o n ，m u l d c a s ta p p l i c a t i o n ， m u l t i - p o i n tv i d e o c o i f f e r e n c i n g 第1 v 页 原创性声明 本人声明，所呈交的学位沦文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含他人已经发表或撰写过的研究成果，也不包含 为获得中南大学或其他单位的学位或证书而使用过的材料。与我共同 工作的同志对本研究的贡献均已在论文中作了明确说明。 作者签名：三薹堡垒日期：型年月二z 日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以采用复印、缩印或其他手段保存学位论文； 学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名妻塑翩签名衅吼型年月皇日 博士学位论文 第一章绪论 第一章绪论 组播技术在未来的因特网中将扮演十分关键的角色1 】【纠。组播技术的研究内 容非常丰富，涉及路由算法与协议、成员关系管理、地址分配、接纳控制和应用 等。本文主要研究o o s 组播路由算法和协议、接纳控制和应用。本章介绍q o s 组播路由问题的背景，讨论q o s 组播路由问题的一般描述；评述国内外关于 q o s 组播路由算法和协议的研究进展；最后介绍本文的研究内容和全文结构。 1 1 引言 q o s 组播路由问题是网络服务质量( q u a l i t y - o f - s e r v i c e ，q o s ) 问题与组 播路由( m u l t i c a s tr o u t i n g ) 问题的融合。众所周知，伴随包交换网络上多媒 体应用的兴起，用户对网络的q o s 要求越来越强烈。人们认识到，由于传统 的尽力而为( b e s t e f f o r t ) 机制的网络无法向多媒体通信应用提供带宽、延时、 延时抖动、丢包率等方面的有保证的服务，从而使得包交换网络上的实时多 媒体通信面临新的挑战。 发展面向连接的、有保证服务( g u a r a n t e e ds e r v i c e ) 的传输结构是下一 代高速广域网的必然趋势p j 。q o s 这个概念表达了网络服务提供商和应用之 间就服务数量和质量达成的合约。应用为了获得网络的有保证服务，必须描 述其通信量的q o s 请求，这表现为一系列的约束条件，包括带宽、延时、延 时抖动、丢包率、缓冲区大小等限制i l ”j 。在网络方面，对于应用的q o s 请 求，它需要一个接纳控制机制，这个机制在获得了应用的q o s 描述、当前网 络状态信息后，依据事先确定的接纳准则，对应用的q o s 请求做出接纳决策。 如果当前网络具有足够的资源来分配给应用，并确保新通信量的注入不会破 坏已有通信量的服务质量，则接纳成功 如果当前网络没有足够的资源分配 给应用，则需要进行q o s 协商，以便调整应用的q o s 请求并再次进行接纳控 制，或者拒绝服务【l ”1 。 为了积极推进q o s 网络系统结构的研究，i e t f ( 因特网工程委员会) 从 上世纪9 0 年代以来先后定义了若干o o s 服务模型，如提供a o s 服务保证和 负载控制服务的综合服务结构( i n t e g r a t e d s e r v i c e a r c h i t e c t u r e ，彤4 】) 、为单 播和组播传输提供面向接收者的固定式或共享式资源预留解决方案的资源 预留协议r s v p t 5 】【6 1 1 1 3 3 1 、为避免每流状态( p e r f l o ws t a t e ) 的巨大开销而提出 第1 页 博士学位论文 第一章结论 的基于包标记和轻量级路由器支持的区分服务结构( d s a ) 【7 l f l 3 4 】等。 与此同时，由美国斯坦福大学& d e e r i n g 在2 0 世纪8 0 年代后期提出的 i p 组播传输结构【8 1 1 9 】也得到了极大重视。组播试图将源端数据流的单一副本 通过网络( 互联网) 传送到一组接收者，目的是减少网络不必要的带宽开销。 组播技术的关键是如何建立由路由器节点和链路组成的组播树( m u l t i c a s t t r e e ) ，正是依靠组播树，源端只需要产生并发送一个数据流，通过组播路由 器的复制和转发，数据流被传送到一组接收者。与利用多个单播( u n i c a s t ) 将数据流传送给一组接收者相比，组播极大地减少了网络资源的消耗，同时 也大大减轻了源主机负担【8 】，组播的有效性得到越来越多的理论和实践的支 持【1 们。 q o s 和组播技术最初是分别被研究的。但是，近年来研究人员发现，由 于像r s v p 这样的协议或服务依赖于底层的单播或组播路由协议，因此当路 由协议所确定的路径或组播树没有足够的资源用来支持r s v p 协议进行资源 预留时，r s v p 的预留就告失败，从而不得不重新选路并再次尝试预留或者 拒绝服务。所以，如果希望r s v p 在确定路由或组播树时就能够进行资源分 配，那就需要发展直接支持q o s 的路由算法和协议，即q o s 驱动( q o s - d r i v e n ) 的组播路由。q o s 驱动的组播路由考虑到相关o o s 限制性参数，它以寻找最 佳的支持q o s 请求的组播树为目标，并企图实现最有效的网络资源利用。类 似地，在区分服务结构中，每个域的带宽分配器也必须负责为邻域之间的服 务等级协商，以便建立相应的服务配置。因此带宽分配器也必然受到建立适 当路由的域内或域间路由协议的影响。所以，有必要让带宽分配器提供满足 一定q o s 要求的路径或组播树，这也是非常必要的。 i 嵌入式实时应用 fi 时间敏感的音视频应用i 啪郴描意商h 悬与篡篡 士信号士数据 i 接纳控制 il 传输协议 l 孟! ：一厂主= = = ： 上 网络软件层 q o s 驱动的ii 资源预留 fi 单播，组播路由r 1 自适应管理r + 盛时链路调度器 图卜1q o s 服务组件及其关系 第2 页 博士学位论文 第一章绪论 图1 - 1 表示了提供q o s 服务所需要的几种技术及其相互关系。这个模型 表达了研究人员关于提供q o s 服务的网络结构的基本结论，即q 0 s 服务需要 几类必不可少的技术相互结合，即q o s 的定义和描述、q o s 驱动的( 也称 q o s 受限的) 单播和组播路由协议、共享链路上包调度算法以及资源分配策 略、资源预留和管理技术等。 现在，大部分研究人员趋同这样的看法，即在未来以q o s 为中心的高速 互联网中，q o s 组播服务是必不可少的构件【1 2 】【1 3 】。正因为如此，q o s 组播成 为近年非常热门的研究领域。图1 1 中的粗线框是本文研究涉及的部分。 1 2 q o s 组播路由问题描述 1 2 1 网络模型 诚如文献【1 4 】所言，在分层描述的网络结构中，对于为每个数据流所建 立的路径而言，由于数据传输是有方向的，相关路径的可用带宽在不同方向 上不相同：而从传输层往上，对等实体间建立的连接代表了一条从源节点到 目的节点的逻辑链路，具有明确的方向性，因此采用有向图来描述网络可以 适应面向连接的网络控制。 设互联网是一个有向图g = ry ，e j ，y 是节点( 顶点) 集合，e 是链路 ( 边) 集合。g 的一条链路可表示为一个二元组( v ，u ) ，其中v ，1 , 1e v 。 一条链路是有向的，是指对于任意节点u 、v y ，如果存在一条从节点村到 v 的链路e = h ，v 土则必存在链路e = “，“ 通常e 口。每个节点 “e 矿具有5 个属性：入度、出度、度数( 入度与出度之和) 、端口吞吐率或 容量g 以及端口缓冲空间大小蜕。每条边e 矿具有3 个属性；长度l e 、媒 体传播速率押和误码率e r 。 为了建立一个通用的支持q o s 路由和接纳控制的网络模型，有必要分析延 时等q o s 参数的构成。在包交换网络中，网络延时是指源端到目标端的延时， 它是两个端点之间的链路与节点延时的总和。文献 1 5 8 讨论了多媒体通信网络 性能需求的定量分析。一般认为，网络延时由下列4 部分组成： 1 ) 节点处理延时或者称交换延时( p r o c e s s i n g a e t a y ) ，它是指节点把从输 入端口进入的包送到输出端口缓冲区所消耗的时间。 2 ) 排队延时( q u e u e i n g d e l a y ) ，即数据在输出端口缓冲区中等待被送到输 出链路上的时间。 第3 页 博士学位论文第一章绪论 3 ) 传输延时( t r a n s m i s s i o n a e l a y ) ，即数据被传输到输出链路上的时间。 4 ) 传播延时( p r o p a g a t i o n d e t a y ) ，信号在电缆、光纤或无线电传输介质 中传播的时间，这是一个与电磁波传输速度、传输介质、传输距离相关的时间。 当传输介质和距离给定以后，传播延时就是一个确定的数据。 为了配合q o s 组播路由的需要，我们给每条链路赋予三个相关的函数。 定义1 1 ：可用带宽函数b “) 是指，对于垤“，v ) e ，v 、“n 存在一个 映射占如j ：e ，其中是正实数集，它表示链路口上从“到v 方向上的可用带宽。 定义l 一2 ：延时函数d e “j 是指。对于坛“，v je e ，v 、“e v ，存在一个映射 d ，：e 嘏+ ，其中是正实数集，它表示链路e 上从”到v 方向上的延时，包括传 播延时和传输延时。 定义1 - 3 ：代价函数c p “j 是指，对于弛“，v jee ，v ，“e y ，存在一个映 射c 凫j ? e 娘+ ，其中r ? 是正实数集它表示链路e 上从h 到v 方向上的链路使用代 价或者费用。 值得注意的是，由于网络的非对称性，通常b “j 口“) ，c e “j # c e n d e “j d e “ 对称网络可以看成为不对称网络的一个特例。 以往大部分q o s 组播路由算法都是建立在一个简化网络模型基础上的， 它们的主要特点是忽略延时组成中一个或几个因素。例如，文献 1 5 】的网络 模型认为在网络延时的4 个组成中，节点的处理延时( 或者称交换延时) 相 对排队延时、传输延时和传播延时可以忽略不计。有些文献甚至把网络延时 简单归结为链路的传播延时。这些做法在早期链路速度比较低的网络环境 下，忽略网络节点的处理速度能够满足要求。但是对于高速网络和i n t e r n e t 的异构状态，忽略节点处理速度就不能很好地反映网络的实际特性了。 因此，类似定义1 1 、1 2 和1 3 ，我们为每个节点定义3 个函数( 为节 省篇幅，采用筒述方式) ： 延时函数d n 以上p o r + ，包括排队延时和处理延时：代价函数c n “，j v - * r + 、节点丢包率厶“ 弘r + 。 1 2 2 群组模型 群组模型( g r o u pm o d e l ) 也可称组播模型( m u l t i c a s tm o d e l ) ，它表达的 是参与组播通信的群组成员之间的关系特征，即群组特征或群组定义。 定义1 - 4 ：给定一个网络g r y ，e 设是y 的任意子集，即m c v ，m 包含 如下两类节点： 第4 页 博士学位论文第一章绪论 1 ) 源节点s ，即连接源主机的路由器节点； 2 ) 接收者节点r ，即连接成员主机的路由器节点； 且吖满足下列条件： 1 ) 有一个全局唯一标识符g 。女，： 2 ) m 的成员节点可以在任意时刻加入或退出”； 3 ) m 中的成员节点可以是另一个满足此定义的集合m 的成员： 则称m 是网络g 的一个群组。 值得注意的是，本文的群组定义是一个网络层概念，它不失组播群组的 一般特征，同时有利于独立地在网络层设计路由算法和协议，避免讨论主机 使用i g m p 协议【1 6 1 加入路由器问题。本文中网络节点和路由器具有相同的含 义，它们时常混合使用。 下面给出组播树的定义。 定义1 5 ：一个组播树是网络g 的一个子图，它是一个以源节点s 为根井伸展到m 蜘既南 觏员r ( m s ) 托无回礴固强t ( s m ) 或t ( s g m r ) 表示，g 口d r r 为 群组地址。 由于树丁植根于源节点s ，故又称之为源基树( s o u r c e - b a s e d t r e e ) 或源根 树( s o u r c e r o o t e d t r e e ) 。本文仅考虑源根树，不考虑与之相对的共享树( s h a r e d t r e e ) 【l l l 。 1 2 3q o s 组播路由问题定义 在给出q o s 组播路由问题的定义之前，我们先描述若干预备概念。 定义1 - 6 ：树t 岱，g d m ，的一条路径是指从源节点s 到接收节点弓副，的特定 链路( s = ”，v 2 ，h = 碍) 的集合，用p 7 ( s ，弓) 表示树的一条路径，即尸7 ( s ， 毋) = ( s = v l ，v 2 ，2 马) a 路径p 7 ( 马) 的延时定义为从s 到弓的各链路和节点延时之和，用 d e l a y s ，马- ，表示，即有 kk - i d e l a y s ，r j 】= 姚) + d e ( 咖，v i + 1 ) ) ( 1 - 1 ) 路径p 7 体，马) 的带宽定义为从s 到r j 的各链路可用带宽的最小值 用b s ，r j 】表示，即有 研s ，r j 】= m i n 徊0 ( 一，v ，+ ，) ) i f = 1 ，2 ，k ( 1 - 2 ) 第5 页 博士学位论文 第一章绪论 路径p 7 岱，毋，) 的代价定义为从s 到弓的各节点和链路代价之和，用 c o s t s ，财表示，即有 kk - 1 c o s r 【s , r j ) = c n ( v i ) + c e ( e ( v i , v i + 1 ) )( 1 - 3 ) i = 1i = l 最后我们有组攒树的总代价，用t o t a l c o s t 汀) 表示，定义为： t o t a l c o s t ( t ) = c e ( e ( v , ，v f + 1 ) ) ( 1 - 4 ) 蚝， q o s 组播路由问题的一般定义是： 定义1 7 ：对于给定的网络g ，一个组播任务可描述为一个4 元组r = m 9 ，0 ，j ， 其中m 是组播群组：q 是任务r 的服务质量要求，即o o s 约束，一般包括端到端延时限制、 最低带宽要求、延时抖动限制和丢包率等：r 是完成任务r 所需要建立的组播树；d 是一组 对r 进行优化的目标函数。组播路由是指对于给定的网络g 。通过某种算法和相关协议，构 造一个可以完成组播任务f 的组播树l 使丁伸展到吖的所有成员。 本文主要考虑一种称之为延时带宽受限的最小代价树问题( d e l a ya n d b a n d w i d t h c o n s t r a i n e d m i n i m u m c o s t m u l t i c a s tt r e e ，通常称之为延时和带宽 受限的s t e i n e rt r e e ，简记为d b c m t ) 1 1 1 。我们之所以主要考虑延时和带宽 这两个q o s 参数，是因为这两个参数在多媒体网络传输中起主要作用。而象 丢包率( 1 0 s s ) 、缓冲大小( b u f f e r s i z e ) 等这样的指标在资源预留环境下能够 得到有效保证。 d 占蝴问题定义如下。 定义1 8 ：给定网络gr n 昱j ，对于v e e ，存在链路延时函数d e 如) 链路可 用带宽函数b “j ，链路代价函数c en j ，节点延时函数d nr “，和代价函数c n “ 已知源节点s ，接收节点集合r m - s ) 儿对于眈m ，设b a n d w i d t h _ r j 一岱，g m 为 接收节点是所请求的加入源基树t ( s ，瓯m ) 的带宽( 即接收数据的速度，r e c e i v i n g r a t e ) ， 其中g 。折是群组地址；又设d e l a yr j _ ( s ，瓯出一是节点弓所请求的从源端s 到接收节 点马的最小延时。求解d b c m t 问题的目标是构造一个源基树r 岱，g m 使得下列 不等式 d e l a y s ，r d - f d e l a y _ r j _ ( s ，g o 曲 b a n d w i d t h s ，r db a n d w i d t h r j j s ，g o d 0 成立并使t o t a l c o s tr 最小。 第6 页 博士学位论文 第一章绪论 可以证明d b c s t 是p 完全的】。 从以上描述可以看出，q o s 组播路由有两个基本目标： 1 ) 建立能够满足应用q o s 请求的组播树； 2 ) 最有效地利用网络资源。 为了达到这两个目标，支持o o s 路由的网络系统必须具有三方面的功能： 1 ) 获取计算信息：即支持计算q o s 组播树的各种信息： 2 ) 建立组播树：即建立满足接收者的q o s 请求的传输树； 4 ) 维护已建立的组播树。 1 3 国内外研究现状述评 在评述国内外q o s 组播路由问题研究现状之前，首先声明两个基本判断： 1 ) 有必要分析组播路由算法和协议之间的区别。我们知道，算法是建 立组播树的计算过程，指明经过什么样的操作步骤使组播路由器建立起组播 转发表；而协议则是为实现算法所规定的相关数据结构以及交换这些数据的 规程。不同的协议通常会使用不同的算法，例如d v m r p ( v 3 ) 【l ”协议使用 了基于“反向路径转发技术”的r p 材l l 】算法建立组播树，而m o s p # 埔j 协议 则使用最短路径算法计算从源端到目标节点的最短路径，用该路径把目标节 点连接到组播树。但是，不同的协议也可以使用相同或相似的算法，例如 p i m - d m ( 协议无关组播协议密集模式) f j9 】就使用了与d v m r p 相同的r p m 算法。两者的差别在于，p i m - d m 不包括传播常规单播路由信息的工具，而 是假设路由器已经使用了一个常规单播路由协议来计算到每个目的站的最 短路径。可以说p i m - d m 是不带路由更新组件的d v m r p 协议。由此分析可 以看出，算法是更单纯的东西，是协议的核心，算法决定协议的基本特征； 协议是围绕算法而发展的一整套规约，算法与协议密不可分，协议把算法有 机地包含在内，但协议的内容更宽泛，协议更多地关心路由信息收集和维护 问题、群组成员关系管理问题等。基于这一判断，本文的述评从算法和协议 两个方面展开。 2 ) 2 j t 播路由从整体上可分成q o s 敏感掣j ( q o s - s e n s i t i v e ) 1 2 0 1 1 2 1 1 1 2 】和非q o s 敏感( q o s - o b l i v i o u s ) 的【1 7 】【l s 】【1 9 】，但是我们不可能仅仅讨论q o s 敏感的组播 路由算法和协议，因为二者之间存在于丝万缕的联系。事实上很多q o s 组播 路由算法和协议是从非o o s 的路由算法及其协议发展而来的，例如 q o s m o s p f i l 8 】就是m o s p f 的q o s 扩展，等等。因此，述评会同时涉及到两 第7 页 博士学位论文第一章绪论 方面的算法与协议，但是我们将试图指出它们之间的区别。 1 3 1 组播路由算法 由于组播路由是一个权衡各种因素以寻找最优解的过程，因此研究人员 站在不同观点、强调不同需求，提出了各式各样的组播路由算法。在可接触 的文献范围内，我们把散见于各种论文中的算法归纳成如下几种类型。 1 ) 集中算法与分布式算法 集中路由算法( c e n t r a l i z e dr o u t i n ga l g o r i t h m ) 也称显式路由( e x p l i c i t r o u t i n g ) 或源路由( s o u r c er o u t i n g ) 算法【2 3 】【j 6 0 l 。其特点是，源节点计算出 从源端到目标节点的整个组播树。为此，网络中的每个路由器都必需维护一 个全局状态( g l o b a ls t a t e ) 信息库，并且周期性地对其更新。尸，j 棚算法弘刮 是集中式最小生成树算法，它从任意的根节点开始不断扩展树，每一步在部 分树上加入一个代价最小的树外节点直到所有节点均加入生成树。文献 2 5 】 提出的x 胛集中算法得到了较多关注。对于给定的源s 和群组m ，即p 首 先采用动态规划方法计算御u m 上的延时受限闭图g ，接着即尸使用p r i m 算法计算g 上的最小生成树，具体过程是从源开始，找到从在树节点“到非 在树节点v 的延时受限的最小代价路径，每次添加一个非在树节点，直到所 有接收者全部被包括进组播树。采用集中算法的组播协议是m o s p f i “j 。当 一个m o s p f 路由器第一次接收到一个组播数据包时，它就使用d o k s t r a 算 法计算出以该数据报源端为根的最短路径树( s h o r t e s tp a t ht r e e ) 。由于所有 路由器都拥有相同的网络拓扑信息，所以m o s p f 区域内的每个路由器将计 算出相同的组播树。源路由算法的问题在于路由器为存储全局状态而付出的 开销较大，同时它也是计算密集的，但源路由算法可以有效避免环( 1 0 0 p ) 的出现。 分布式算法( d i s t r i b u t e da l g o r i t h m ) 的特点在于组播树计算是由位于不 同网络中的多个路由器协作完成的棒”。p i m - s 材2 6 1 协议所采用的算法是分布 式的。图1 2 说明了p i m - s m 协议所用算法的处理过程。 第8 页 博士学位论文 第一章绪论 圈1 2p i m - s m 协议的分布式