（通信与信息系统专业论文）支持服务质量的实时多播路由算法研究.pdf

摘要y5 7 8 8 8 6随着i n t e r n e t 中多媒体应用如远程视频会议、视频点播等的迅猛发展，能有效节省网络带宽的多播技术成为广泛研究的热点，其研究内容涉及多播技术的诸多方面。本文主要研究支持服务质量或称为基于多度量的实时多播路由算法方面的关键问题。本文在较系统和完整地综述前人在多播路由研究现状的基础上，分析现有多播路由代价模型中代价含义的模糊性，讨论该代价模型的不足，指出具有加性的代价( c o s t ) 不能确切反映网络本质特性，尤其不能反映路径带宽的凹性( c o n c a v e ) 。已有基于代价的算法不能直接适应多播应用，需要新的更为细致的模型和算法，同时分析指出可用带宽模型将能准确地反映多播网络的实际情况。本文基于该可用带宽模型，同时考虑另外两个重要的实时度量：时延和结点间时延差别，提出基于最大可用带宽、时延和结点问时延差别受限的实时多播路( b d v m r ) l u q 题及其有效的启发式算法，包括基于源结点的、支持分布的和支持动态的b d v m r 算法，并在高速宽带路由器上完成基于可用带宽的p i m s m 协议设计方案及实现。最后讨论支持服务质量的多播路由算法的发展方向和介绍下一步研究工作。本文的主要创新之处体现如下：( 1 ) 提出基于可用带宽模型、时延和结点间时延差别受限的实时多播路由( b d v m r ) 问题并证明其n p 完全性，并分别提出基于b d v m r 问题的源路由、支持分布和支持动态的有效实时多播路由启发式算法。提出基于可用带宽模型的支持服务质量的实时多播路由源结点启发式算法。该算法采用可用带宽代替代价作为主要度量，并满足实时多播中二个重要约束度量：时延和结点间时延差别。同时基于此三个度量，本文提出二种新的具有多项式复杂性的实时多播路由算法并比较其性能。本算法通过分析得到每路径时延和二约束度量之间的关系，有效降低涉及时延和结点间时延差别此类问题的复杂性。提出基于可用带宽模型的支持服务质量的实时多播路由分布式启发式算法。该算法同时考虑带宽、时延和结点间时延差别，将可用带宽因素代替代价用于选择函数，通过采用每路径时延和二约束度量之间的关系( 对中继结点和目标结点有区别) ，从而有效降低分布式算法的收敛时间；该启发式算法包括对错误终结的处理并具有多项式复杂性。提出基于可用带宽模型的支持服务质量的实时多播路由动态启发式算法。该动态算法同时考虑带宽、时延和结点间时延差别，采用基于时延和结点间时延差别的中心点算法确定虚拟中心，采用受时延约束的尽可能大可用带宽路径算法来连接多播源与虚拟中心，以保证关键路径受网络拥塞的影响尽可能小。由于算法的预处理过程预先考虑时延和结点间时延差别约束，故能达到与静态算法尽可能接近的时延性能：由于该动态算法采用类似有核树的思想，具有可扩展性好的优点，并有较好的鲁棒性。该算法的在线动态过程具有较小的时间复杂性。( 2 ) 本文提出无环路的第k 条最大可用带宽路径算法。由于具有凹性的带宽和具有加性的代价存在本质的区别，第k 条最大可用带宽路径算法不能通过简单修改第k 条最短路径算法得到。本文结合二个新定义的路径操作和修改的二重扫除算法完成第k 条最大可用带宽路径算法，并给出实例加以说明，最后证明其正确性、无环性和具有多项式复杂性。该算法解决了基于带宽度量的路由算法中一类很基本的问题一一第k 条最大可用带宽路径问题，具有较大的理论意义；因算法采用能反映网络实时特性的“可用带宽”作为路由算法度量，能直接保证网络带宽资源利用的最优而具有较大的实际意义。( 3 ) 基于可用带宽模型的多播路由协议在高速宽带路由器上的实现。在高速宽带路由器a v i a 上完成一种采用反映网络本质特性度量的与协议无关多播稀疏模式( p i m s m ) 方案的设计和实现。该实现采用度量收集模块得到反映实际网络状况的带宽，并以之为度量运用到路由算法中，从而使该方案构建的多播树能达到网络带宽资源利用的最优化。本文旨在深入研究支持服务质量( 基于多度量) 的实时多播路由算法和适合多播网络实际情况的多播路由协议。课题背景是国家教育部高等学校骨干教师资助基金课题“碑网络上基于区分服务的q o s 实现机制”和国际合作项目“高速宽带路由器声认的研制与开发”项目。关键词：多播路由服务质量可用带宽时延结点间时延差别高速宽带路由器l ia b s t r a c tw i t ht h ep r o l i f e r a t i o no fm u l t i m e d i aa p p l i c a t i o ni nt h ei n t e m e t ，s u c ha sr e m o t ev i d e o c o n f e r e n c e ，v i d e o o n d e m a n d ，m u l t i c a s tt e c h n o l o g i e st h a tc a l le f f e c t i v e l ys a v en e t w o r kb a n d w i d t hb e c o m et h eh o ts p o t sa n dh a v eb e e ns t u d i e de x t e n s i v e l y t h e r ea r em a n ya s p e c t st o w a r d sm n l t i c a s t ，i n c l u d i n gm u l t i c a s tr o u t i n g ，m u l t i c a s tc o n g e s t i o nc o n t r o l ，q o sm u l t i c a s t ，r e l i a b l em u l t i c a s t ，h e t e r o g e n e o u sm u l t i c a s t ，w i r e l e s sm u l t i c a s ta n ds oo n t h i sd i s s e r t a t i o nf o c u s e so nt h ea s p e c t so fq o s ( o rc a l l e dm u l t i m e t r i c ) r e a l - t i m em u l t i c a s tr o u t i n ga l g o r i t h m s t h em a i nc o n t e n t so ft h ed i s s e r t a t i o na r ea sf o l l o w s f i r s t ，t h ep r e v i o u sr e s e a r c hw o r ko fm u l t i c a s tr o u t i n ga r es u r v e y e dc o m p a r a t i v e l ys y s t e m a t i c a l l ya n dc o m p l e t e l y b a s e do na b o v es u r v e y , t h ea m b i g u i t yo fc o s ti nm e t r i cm o d e lo fm u l t i c a s tr o u t i n gi sa n a l y z e da n di ti sp o i n t e do u tt h a tt h e r ea r ed r a w b a c k si nt h ec o s tm e t r i cm o d e l ，t h a ti s ，t h ea d d i t i v ec o s tc a n n o tr e p r e s e n tt h ee s s e n t i a lc h a r a c t e r i s t i c so fr e a ln e t w o r k s ，e s p e c i a l l yf o rc o n c a v eb a n d w i d t h t h u s ，t h ec o s t o p t i m a la l g o r i t h m sc a n n o td i r e c t l yg u a r a n t e et h eo p t i m a lu s a g eo fn e t w o r kb a n d w i d t h t h e r e b y , n o v e lm e t r i cm o d e la n dc o r r e s p o n d i n ga l g o r i t h m ss h o u l db ep r o p o s e d o nt h eo t h e rh a n d ，a v a i l a b l eb a n d w i d t hm e t r i cm o d e li sa n a l y z e dt ob eag o o ds u b s t i t u t i o nb e c a u s ea v a i l a b l eb a n d w i d t hi sag o o dr e p r e s e n t a t i v eo fr e a ln e t w o r k s n e x t ，t h ep r o b l e mo fb d v m r ( a v a i l a b l eb a n d w i d t h b a s e dd e l a ya n dd e l a yv a r i a t i o n c o n s t r a i n e dr e a l t i m em u l t i c a s tr o u t i n g ) i sa d d r e s s e da n dt h r e ec o r r e s p o n d i n gh e u r i s t i ca l g o r i t h m sa r ep r e s e n t e d t h ea l g o r i t h m sp r o p o s e df o rb d v m rt h a ta r eb a s e do nm e t r i cm o d e lo fa v a i l a b l eb a n d w i d t hi n e l u d es o u r c e b a s e d d i s t r i b u t e da n dd y n a m i ch e u r i s t i c s t h e nap i m - s mp r o t o c o ls c h e m eb a s e do na v a i l a b l e - b a n d w i d t hm o d e li sd e s i g n e da n di m p l e m e n t e do nt h ep l a t f o r mo f h i - s p e e db r o a d b a n dr o u t e r a tl a s t ，d e v e l o p m e n td i r e c t i o n so f m u l t i c a s tr o u t i n ga l g o r i t h m sa r ed i s c u s s e da n dt h ef u r t h e rw o r ka r ei n 订o d u c e d j t h eo r i g i n a lc o n t r i b u t i o n so f t h ed i s s e r t a t i o na r ea sf o l l o w s ( 1 ) t h ep r o b l e mo fa v a i l a b l eb a n d w i d t h b a s e dd e l a ya n dd e l a yv a r i a t i o n - e o n s 订a l n e dr e a l t i m em u l t i c a s tr o u t i n g ( b d v m r ) i sa d d r e s s e da n dp r o v e dt ob en p c o m p l e t e f u r t h e r m o r e ，t h r e ek i n d so fc o r r e s p o n d i n ge f f e c t i v eh e u r i s t i ca l g o r i t h m sa r ew o r k e do u t ，i n c l u d i n gs o u r c e - b a s e d ，d i s t r i b u t e da n dd y n a m i ca l g o r i t h m s ：t w os o o r c e b a s e dh e u r i s t i ca l g o r i t h m sb a s e do na v a i l a b l eb a n d w i d t hm e t r i cm o d e la r ep r o p o s e df o rq o ss e n s i t i v er e a l - t i m em u l t i c a s tr o u t i n g b d v m rp r o b l e m t h et w oa l g o r i t h m st a k et h r e em e t r i c si n t oc o n s i d e r a t i o na tt h es a m et i m e t h e yu s ea v a i l a b l eb a n d w i d t hi n s t e a do fc o s ta sp r i m a r ym e t r i ca n ds a t i s f yt h ec o n s t r a i n t so ft w os i g n i f i c a n tm e t r i c s ：d e l a ya n dd e l a yv a r i a t i o n m o r e o v e r , t h e yc a ne f f e c t i v e l yd e c r e a s et h ec o m p l e x i t yo fa l g o r i t h m sc o n c e r n e dw i t hd e l a ya n dd e l a yv a r i a t i o ni nt h a tt h er e l a t i o n s h i pb e t w e e nt h ep a t hd e l a ya n dt h et w oc o n s t r a i n t si sa n a l y z e da n da t t a i n e d ad i s t r i b u t e dh e u r i s t i ca l g o r i t h mb a s e do na v a i l a b l eb a n d w i d t hm e t r i cm o d e li sp r o p o s e df o rq o ss e n s i t i v er e a l t i m em u l t i c a s tr o u t i n g b d v m rp r o b l e m t h en o v e la l g o r i t h mt a k e sa v a i l a b l eb a n d w i d t h ，d e l a ya n dd e l a yv a r i a t i o ni n t oc o n s i d e r a t i o n f u r t h e r m o r e ，i ti n t r o d u c e sb a n d w i d t hi n s t e a do fc o s ti n t os e l e c t i o nf u n c t i o ni na d d i t i o nt od e l a y t h ea l g o r i t h mc u t sd o w nt h ec o n v e r g i n gt i m et h r o u g ht h er e l a t i o n s h i pb e t w e e np e rp a t hd e l a ya n dt w ob o u n d e dm e t r i c s a d d i t i o n a l l y , t h ep r e s e n t e da l g o r i t h mw i l la l s od e a lw i t h f a l s et e r m i n a t i o n f i n a l l y ，t h eh e u r i s t i ch a sp o l y n o m i a lc o m p l e x i t y ad y n a m i ch e u r i s t i ca l g o r i t h mb a s e do na v a i l a b l eb a n d w i d t hm e t r i cm o d e li sp r o p o s e df o rq o ss e n s i t i v er e a l t i m em u l t i c a s tr o u t i n g b d v m rp r o b l e m t h ea l g o r i t h mc o n s i d e r sa v a i l a b l eb a n d w i d t h ，d e l a ya n dd e l a yv a r i a t i o ni nt h em e a nt i m e i tc o n s i s t so ft w op a r t s i nt h ef i r s tp a r t ，t h ev i r t u a lc e n t e ri sd e t e r m i n e db yf a c t o r so fd e l a ya n dd e l a yv a r i a t i o n ，a n dt h e nt h ec e n t e ri sc o n n e c t e dt ot h es o u r c en o d eb yd e l a y - b o u n d e dk w i d e s ta v a i l a b l eb a n d w i d t hp a t ha l g o r i t h mt om a k et h ei n f l u e n c et ot h ek e yp a t ha sl i t t l ea sp o s s i b l e b yv i r t u eo fi d e ao fc o r e b a s e dt r e e ，t h i sa l g o r i t h mh a sg o o ds c a l a b i l i t ya n dr o b u s t n e s s t h es e c o n dp a r ti so n l i n ep r o c e s so f j o i n i n ga n dl e a v i n ga n di th a ss m a l lt i m ec o m p l e x i t y( 2 ) an o v e ll o o p l e s sk - w i d e s ta v a i l a b l eb a n d w i d t hi sp r o p o s e d i nc o n s i d e r a t i o no fe s s e n t i a ld i f f e r e n c eb e t w e e na d d i t i v ec o s ta n dc o n c a v eb a n d w i d t h ，t h en o v e la l g o r i t h mc a n n o tb es i m p l ya t t a i n e df r o mm o d i f i e dk - s h o r t e s tp a t ha l g o r i t h m t h i sp a p e rd e f i n e st w on e wp a t ho p e r a t i o n sa n dt a k e sa d v a n t a g eo fm o d i f i e dd o u b l es w e e pa l g o r i t h mt oc o n s t r u c tk - w i d e s ta v a i l a b l eb a n d w i d t hp a t h s t h e r e a f t e r , a ni l l u s t r a t i o no fa l g o r i t h mi sg i v e n a tl a s t ，c o r r e c t n e s sa n dl o o p l e s s n e s so ft h ea l g o r i t h ma r ep r o v e da sw e l la si t sp o l y n o m i a lc o m p l e x i t yt h ek - w i d e s ta v a i l a b l eb a n d w i d t ha l g o r i t h mi so fg r e a tt h e o r e t i c a ls i g n i f i c a n c ei nt h a ti ts o l v e sak i n do ff u n d a m e n t a lr o u t i n gp r o b l e m st h a ta d o p tb a n d w i d t ha st h ep r i m em e t r i c f u r t h e r m o r e ，i th a sg r e a tp r a c t i c a ls i g n i f i c a n c ef o rt h er e a s o nt h a ti tc a ng u a r a n t e et h eo p t i m a lu s a g eo fn e t w o r kb a n d w i d t hr e s o u r c e sb yv i r t u eo f t h ea d o p t i o no f a v a i l a b l eb a n d w i d t hm e t r i c ( 3 ) a v a i l a b l eb a n d w i d t h b a s e dm u l t i c a s tr o u t i n gp r o t o c o li si m p l e m e n t e do nh i g h s p e e db r o a d b a n dr o u t e r a v i a o na v i a ，a na v a i l a b l eb a n d w i d t h b a s e dp i m s mi sd e s i g n e da n di m p l e m e n t e d t h es c h e m ea d o p t sam e t r i cc o l l e c t o rt oc o l l e c ti n f o r m a t i o no fb a n d w i d t ha n dt a k e si ta st h em e t r i co ft h er o u t i n ga l g o r i t h m t h e r e f o r e ，t h er e s u l t a n tt r e eo ft h i ss c h e m ec a nb ec o n s t r u c t e da c c o r d i n gt ot h er e a l t i m es t a t u ss ot h a ti tc a nm a k eg o o du s eo f n e t w o r kb a n d w i d t hr e s o u r s e s t h ea i mo ft h i sd i s s e r t a t i o ni st os t u d yq o s ( o rc a l l e dm u l t i m e t r i c ) r e a l t i m em u l t i c a s tr o u t i n gp r o b l e m si nd e p t ha n dd e s i g nt h ec o r r e s p o n d i n gm u l t i c a s tp r o t o c o l st h a ta r em o r es u i t a b l et ot h er e a ln e t w o r k s t h eb a c k g r o u n do ft h ed i s s e r t a t i o ni sb a s e do nt h ep r o j e c to f i pq o si m p l e m e n t a t i o nm e c h a n i s mo nd i f f - s e r vn e t w o r k a n dt h ep r o j e c to fd e s i g na n dd e v e l o p m e n to f h i - s p e e db r o a d b a n dr o u t e r - a v i a k e yw o r d s ：m u l t i c a s tr o u t i n gq u a l i t yo fs e r v i c ea v a i l a b l eb a n d w i d t hd e l a yi n t e r - d e s t i n a t i o nd e l a yv a r i a t i o nh i s p e e db r o a d b a n dr o u t e rv1 绪言1 1 研究背景随着i n t e r a c t 上多媒体业务的迅猛发展，如视频会议、视频点播( v o d ) 、远程多媒体教学和网络实时游戏等，为使i n t e m e t 有效利用现有带宽以支持众多高带宽消耗的业务，多播( m u l t i c a s t ) w 1 2 1 技术应运而生。多播与单播存在本质上的不同，它不象单播每传送给一个用户就复制一份，多播仅在需要的网络结点处才被复制。假设一个信息源有n 个用户，若采用单播技术，浚信息源需要传送n 份，而若采用多播技术该信息源就只需传送一份，多播数据包会在相应的网络结点处被自动复制成所需要的n 份，从而有效节省了宝贵的网络带宽资源。在网络结点上很重要的网络设备就是路由器，为使路由器支持多播，首先要解决的问题之一是多播路由1 3 - 2 4 1 问题。当前主要的多播路由协议包括d v m r p l 25 1 ，m o s p f l 2 6 - 2 7 ，p i m d m 28 1 ，p i m s m t 2 9 - 3 0 ，c b t 3 ”，m b g p m s d p l 32 1 ，b g m p 3 3 1 等，其中的核心之一就是路由算法，合理高效的路由算法能有效地避免网络拥塞从而达到有效地利用网络资源的目的。另外，由于有相当大一部分多媒体业务的实时特性决定了实时多播路由是研究的重点和热点，而且由于实时多播路由所需满足的要求往往不止一个，支持服务质量或称为多度量的多播路由 ”- 4 习是研究的重中之重。图内外学者已经做出了大量的研究工作，提出了大量的启发式算法，但由于该类问题常常是n p 完全性问题，仍然存在许多值得不断优化和尚未解决的问题，从理论上可以不断提出更接近最优解的启发式算法。本博士论文的研究目的是旨在深入研究支持服务质量( 即多度量) 的多播路由算法和适合多播实际情况的多播路由协议。本文的课题背景是：( 1 ) 国家教育部高等学校骨干教师资助基金课题“坤网络上基于区分服务的q o s 实现机制”；( 2 ) 与c o m b r i o 公司合作的“高速宽带路由器a v l a 的研制与开发”项目。1 2 多播路由算法研究现状及存在的问题关于多播路由算法，国内外学者做了大量的研究工作和相应的文献o “”，但仍然存在尚未解决的问题。本节将系统和全面地对前人做过的工作进行综述和总结，并分析和讨论存在的问题。常见的多播路由算法 2 2 - 2 3 1 主要包括洪泛( f 1 0 0 d i n g ) 算法、分发树( s p a n n i n gt r e e s )算法、逆向路径广播( r o b ，r e v e r s ep a t hb r o a d c a s t i n g ) 算法】、截短的逆向路径广播( t r p b t r u n c a t e dr e v e r s ep a t hb r o a d c a s t i n g ) 算法、逆向路径多播( r p m ，r e v e r s ep a t hm u l t i c a s t ) 算法【4 5 和有核树( c b t , c o r eb a s e dt r e e s ) 算法。其中r p b ，r p m 被用于如d v m r p 25 1 、p i m d m 2 8 1 等常用多播路由协议中的逆向路径转发r p f ( r e v e r s ep a t hf o r w a r d i n g ) 机制。从路由算法的度量个数上来分，多播路由问题主要可分二类：单度量多播路由和多度量( 受限) 多播路由，后者因能满足多媒体网络应用的多种要求，又可称为支持服务质量的多播路由问题。下文着重从度量个数不同的角度来进行综述，尤其重点综述支持服务质量的多播路由问题。1 2 1 单度量多播路由算法多播路由算法的主要度量 4 6 4 8 1 包括代价、带宽、时延、结点问时延差别( v a r i a t i o n ) 、丢包率、跳数和结点度t 4 9 1 等。按性质可将之分为三类陋4 8 1 ：( 1 ) 加性( a d d i t i v e ) 度量，如代价、时延、时延差别等；( 2 ) 乘。陛( m u l t i p l i c a t i v e ) 度量，如丢包率：f 3 1 凹l 生( c o n e a v e ) 度量，如带宽，即路径总带宽是所有链路带宽中最小值。对采用加性单度量的多播路由算法 5 0 - 6 0 1 主要包括：( 1 ) 最短路径树( s p t , s h o r t e s tp a t ht r e e ) 算法，该算法可以采用经典d i j k s t r a 算法 5 0 - 6 1 1 和b e l l m a n f o r d 算法 5 0 - 6 0 1 解决：若求所有点对问最短路径5 0 - 6 0 1 可采用f l o y d 算法和d a n t z i g 算法：( 2 ) 最小分发树( m st ，m i n i m u ms p a n n i n gt r e e ) 算法f 5 0 - 6 0 ，该算法保证网络中所有结点的总代价最低，其经典算法分别是p r i m 算法和k r u s k a l 算法；( 3 ) 最小s t e i n e r 树( s m t ，s t e i n e rm i n i m u m t r e e ) 算法6 2 - 7 1 ，要求网络中组成员的接收者的总代价最小，该问题被证明是n p 完全性问题 7 2 - 7 4 。关于s m t 的研究已相当多，较完整的综述文献可参考 6 6 - 6 7 。对该问题经典且有效的算法是k m b 算法 6 ”。s m t 的常见算法还包括二类：s p h ( s h o r t e s tp a t hh e u r i s t i c ) 和a d h ( a v e r a g ed i s t a n c eh e u r i s t i c ) 7 0 1 。s p h 有许多改进型 4 9 , 7 1 ，但其基本思想是类似的。事实上，s m t 是s p t 和m s t 的一般形式：当s m t 中的组成员数等于网络中所有结点数时，即是m s t 算法；当s m t 中仅有二个结点时，s m t 简化为s p t 。针对采用乘性单度量的路由算法，如丢失率p i ，可以利用对数l o g p ，将之转化为加性度量。在采用凹性单度量( 可用带宽) 的多播路由算法中，最基本的是基于源路由的最大可用带宽路径算法，可通过修改最短路径算法得到75 1 ，即将d i j k s t r a 算法中求极小值运算和加法运算分别用求极大值和求极小值运算代替。s h a c h a r n 7 6 1 提出一个类似的算法构建最大可用带宽树来分发多级的分层数据。文献7 7 1 n 提出基于分布式的最大可用带宽路径算法，该算法基于修改的分布式b e l l m a n f o r d 算法，即将分布式b e l l m a n - f o r d 算法中求极小值和加法运算分别用求极大值和求极小值运算代替。最近发表的一篇文章7 8 1 中提出并证明最大生成树和最大带宽路径之间的联系，并采用修改的k r u s k a l 算法来构建最大带宽路径。1 2 2 支持服务质量的多播路由算法因为多媒体的实时性要求多播路由算法的度量往往不止一个，我们把这类多播路由问题称之为支持服务质量的多播路由问题，该类问题经常是n p 完全性问题 7 2 - 7 4 1 ，所以常采用启发式算法。本节将从多度量的不同组合的角度详细综述支持服务质量的多播路由问题。本节出现的符号中，n 表示网络总结点数，i i 1 表示目标结点数，e 表示网络中链路数。( 1 ) 双度量! 重岱盆歪啮延!该组合即是时延受限s m t 问题，即采用双度量，要求在满足时延约束的条件下对组成员生成的多播树总代价最小。在此方面的研究较早也较多，主要算法包括k p p 7 引，c a o 8 们，b s m a 8 1 1 ，c d k s 82 1 ，s c 8 3 埽口m s c 8 4 1 等。k p p ( 由k o m p e l l a ，p a s q u a l e 和p o l y z o s 共同给出) 假设链路上时延和时延约束为整数，k p p 先采用二种选择函数计算时延受限的闭 ( c l o s u r e ) ：if c ( v ，w ) = 最( u w )i 矗( v ，”= 昂( v ，w ) a 一( p ( v ) + p d ( v ，w ) 其中p c ( v w ) 是满足时延约束条件的从结点v 到w 的最短路径中具有最小时延的路径代价，v d ( v , w ) n 是相应p c ( v , w ) 的路径时延，p ( v ) 为源结点到v 的路径时延，然后采用p r i m 算法计算最小分发树，最后展开该树f 后二步同k m b ) 。k p p 算法的时间复杂性为o ( a n 3 ) 。c a o ( c o n s t r a i n e da d a p t i v eo r d e r i n g ) 算法 8 0 1 是w i d y o n o 提出的四个c s t ( c o n s t r a i n e ds t e i n e rt r e e ) 启发式算法中性能最好的一个。c a o 采用c b f ( c o n s t r a i n e db e l l m a n f o r d ) 查找受限最小代价路径，构建多播树时每次只加入一个满足条件的组成员，在w i d y o n o 论文中并未给出c a o 算法复杂性的准确结果，但指出在某些情况下，运行时间呈指数上升。b s m a ( b o u n d e ds h o r t e s tm u l t i c a s ta l g o r i t h m ) 8 1 】首先计算最小时延树( u ) t 1 ，然后在保证不破坏时延约束的条件下用更小代价边去替换l d t 中的超j 2 2 ( s u p e r e d g e ) ，反复执行上述操作直到总代价不再减少为止，其中查找更小代价边采用第k 条最短路径算法。b s m a 时间复杂性是o o m 3 l o g n ) 。c d k s ( c o n s t r a i n e dd u k s t r a ) 算法1 8 2 1 首先采用d i j k s t r a 建最小代价树l c t ，若有路径不满足时延约束，再采用d i j k s t r a 建最小时延树l d t ，并将二树合并。c d k s 算法时间复杂性是o ( n 2 ) 。s c ( s e m i c o n s t r a i n e d ) 8 3 1 采用源到其它所有结点的最大时延为内部时延约束，然后构建不超过此内部约束广播树，最后删去非多播目标结点。m s c ( m o d i f i e ds e m i - c o n s t r a i n e d ) 8 4 1 是对s c 的性能改进，二者的时间复杂性均为o ( n 2 ) 。d l m r 算法 8 5 ，采用时延受限的m c t h 算法8 5 1 ，其中m c t h 选择结点时不是采用距源结点具有最短路径的点，而是距当前树具有最短路径的点。d l m r 的时间复杂性为o ( ( m + 5 2 ) n 2 m 2 n ) 。4文献 8 6 1 提出二种分布式时延受限的s m t 多播路由算法：采用类似p r i m 的最小分发树分布式算法，并采用二种不同选择函数【8 6 ：肛f c ( v ，小糍如- 篙譬! ) _ i ，d ( v ) + d ( v ，w ) 其中d e l a y ( s ，砂是s 到u 的路径时延；a 是时延约束：上倒是链路丢包率。最后，在构建多播树时首先选择满足时延约束的具有最小距离函数值的结点加入。该算法时间复杂性为o ( n 2 ) 。堡路焦岱俭：吐堑塑盟堑差型；浚算法d v c s p ”5 1 采用类似前述的d c s p 9 9 1 的标记结构和复制技术，来寻找满足时延和时延差别的具有最小代价路径的多播树。其时间复杂性为o ( t 2 m 1 ，当t m 2 n 2 ；或为o ( t n 2 ) ，当t m 2 n 2 ，( 1 三ta a ) 。( 3 ) 多度量堕岱硷：瞳延：结直间吐堑差别! 玉鱼奎塑卫旦萤宜!文献【1 1 6 1 借助遗传算法并行搜索和群体寻优的优点，设计基于树的总代价、时延、结点间时延差别、丢包率和可用带宽五个互不相关度量的多播路由算法，仿真结果说明该算法快速有效。其对可用带宽的处理是在算法开始之前删除可用带宽小于所需传输带宽的链路。i 仝加：邕度量!文献1 提出一个有效的自适应满足i 个加性度量的多播路由算法m a m c r a ，该算法由s a m c r a “8 1 单播算法基础上修改而来，也基于三个概念：路径长度的非线性测量、第k 条最短路径和非优先路径原理。m a m c r a 基本思想是利用d i j k s t r a找到所有最短路径，然后在不破坏约束的前提下逐步优化多播树的路径长度。其时问复杂性为o ( k n l o g k n + k 2 i e + n m 2 ) 。k 由文献中提供的函数给出。随着度量个数的增多，常规算法的复杂性将呈指数上升。此时，若将神经网络 1 1 9 - 1 2 1 】、遗传理论【1 2 2 1 2 4 1 和基因算法1 2 5 。1 2 卅运用于多播路由算法将会显现较大的优势。另外，文献【1 2 7 - 1 2 9 1 提出采用随机神经网络( 心m ，r a n d o m n e u r a l n e t w o r k ) n = 较大提升所生成s t e i n e r 树的性能。总之，基于神经网络和遗传理论的多播路出算法将是一个值得深入研究的方向。1 2 3 存在的问题从以上多播路由算法的综述中可以看到，以代价为度量的多播路由算法得到较为广泛和深入的研究。由于代价属加性度量，虽然乘性度量可以转化为加性度量，但具有凹性的度量如带宽却无法直接转化为代价3 0 1 。一般地，采用二种方法 13 0 1 可以将可用带宽转化为代价以采用s t e i n e r 算法：一种是将路径上每一链路的可用带宽( a b ，) 的倒数之和表示为总代价，即：c o s t l = l a b l + l a b 2 + ；或是将路径上每一链路的可用带宽的和的倒数表示为总代价，即：c o s t 2 = l ( a b l + a b 2 + ) 。但二种方法均未能反映网络实际的带宽状况。假设网络中从结点s 到t 存在二条路径a 和b ，其中路径a 由二条链路组成，其可用带宽分别为a o m h z 和8 m h z ，路径b 也由二条链路组成，其可用带宽均为1 0 m h z 。则关于二条路径的比较如表1 - 1 所示。从表中可以看到，若采用基于c o s t l或c o s t 2 的代价度量模型，则路径a 优于路径b ，因为其总代价较小。而根据实际的网络知识，我们知道路径b 要优于路径a ，这是由于路径b 的瓶颈带宽为1 0 m h z而路径a 的仅为8 m h z 。表1 - 1 可用带宽与代价的转化路径a路径be c o s t l1 ( 4 0 + 8 ) = 1 4 81 “1 0 + 1 0 ) = 1 2 0c o s t 21 4 0 + 1 8 = 3 2 01 1 0 + 1 1 0 - - 4 2 0从上述例子中可知，基于代价模型的算法无法直接运用于带宽度量，而且代价最优算法并不能保证带