（通信与信息系统专业论文）kod多播技术与steiner树启发式算法.pdf

摘要 摘要 随着多播技术的日渐成熟，多播技术的应用也受到广泛关注由于k o d 系统具 有在单位时间内曲目被重复点播的频率较高、终端相互之间的网络带宽比较充裕等特 点，因此应用多播技术比较适合基于多播路由与s t e i n e r 树之问存在的对应关系，本 文确定了k o d 视频多播和s t e i n e r 树启发式算法作为本文的研究重点文中介绍了多 播视频路由技术；给出了s t e i n e r 树问题定义，并简要叙述了其精确求解算法、典型的 启发式算法和贪心算法 本文将c h a i n i n g 多播技术应用到k o d 系统1 1 i ，设计实现了相应的多播路由启发 式算法基于k o d 系统的特点，分析了流服务器和客户端中各个模块的作用以及 内容制作中的码率控制。分析了应用层多搐在k o d 系统中的优势，并较为详细地叙 述了流服务器直接提供客户端流服务和通过r t s p 重定向技术实现间接服务两种情况 下的通信流程介绍了c h a i n i n g 多播技术及其与p 2 p 技术的关系，设计了基于c h a i n i n g 多播思想的路由启发式算法并将该算法和r t s p 重定向技术相结合应用于k o d 系 统，试验证明取得了较好的效果 本文概括了典型启发式算法的框架，并在此基础上分别设计了基于路径中跳数和 顶点度数的s t e i n e r 树的启发式算法，使每次添加的路径尽可能得到了重用。并针对每 种算法，均举出图例说明了所设计的算法能求出最优解( 最小s t e i n e r 树) ，而原来的 算法得不到最优解，证明了所设计算法的正确性和优越性并还简单分析了这些算法 的最坏性能比的上界 本文完成了几种组合启发式算法的最坏性能比的分析。常用的肩发式算法运行时 间少、易于实现、求解质量较高，但不同启发式算法之问又具有不可比较性的特点， 因此研究它们相互组合起来的性能具有一定的理论和实践意义。通过研究我们发现组 合后启发式算法的性能上界是各个算法性能上界中最小的一个：组合启发式算法的上 界是紧的：并且组合扁发式算法确保了所求得的解是各个算法f ，最优的一个，保证了 解的质量，弥补了仅用单个启发式算法求得的解的质量无法保证的不足。 本文分别研究分析了相对贪心算法( r g a ) 和k 损失收缩贪心算法( k l c a ) 的下 上海交通大学博士学位论文 k o d 多播技术与s t e i n 口树启发式算法 界目前s t e i n e r 树闯题的最新研究进展都是基于一个简单的贪心算法框架由于已知 的相对贪，f i , 算法最坏性能比的下界1 3 3 3 和! 3 8 5 的图例非常复杂，本文构造了一个算 法下界为i 3 3 3 的更加简单直观的图例证明 本文还设计了一个新图例，分析证明了该算法下界至少为1 2 2 6 ，提高了当前k - 损失收缩贪心算法最坏性能比的下界1 2 本文最后设计了改进的相对贪，f i , 算法，该算法将相对贪心算法和k 期失收缩贪心 算法融为一体并在假设收缩引理成立的条件下初步分析了该算法的上界为1 4 3 8 ， 改进了当前s t e i n e r 树问题的近似算法的最坏性能比的上界1 5 5 最后，在总结全文的基础上，对下一步研究提出了建议和展望 关键词：多播s t e i n e r 树启发式算法贪心算法 l l a b s t r a c t t h e a p p l i c a t i o n sb a s e do rt h em u l t i c a s tt h n o i o g yg e tm o r ea n dm o r ea t t e n t i o n , w h i l e t h et e c h n o l o g yp r o g r e s s e s t h ek o d ( k a r ao ko nd e m a n d ) s y s t e mi ss u i t a b l et oa p p l yt h e m u l t i c a s tt e c h n o l o g yb e c a u s et h ec o n t e n ti nk o dh a sn l o r ec h a n c et o s h a r ea m o n gt h e t e r m i n a l st h a no t h e ra p p l i c a t i o n sa tt h es a m et i m e m o r e o v e r , t h en e t w o r kw i d t ha m o n gt h e t e r m i n a l si sw i d e c o n s i d e r i n gt h er e l a t i o nb e t w e e nt h em u i t i c a s tr o u t i n ga n ds t e i n o rt r e e , t h et h e s i sp o i n t so u tt h ek e yp o i n t so ft h ed i s s e r t a t i o na r et h ev i d e om u i t i c a s ti nk o d s y s t e m , a n dt h eh e u r i s t k st os t e i n e rt r e e t h et h e s i si n t r o d u c e st h ev i d e om u i t i c a s tr o u t i n g t e c h n o l o g y , s t e i n e rt r e ed e f i n i t i o n , a n ds e v e r a lc u f f e n tw i d e l y - u s e dh e u r i s t i c s t h et h e s i sa p p l i e st h ec h a i n i n gm u l t i c a s ti d e at ot h ek o ds y s t e m , d e s i g n sa n d i m p l e m e n tt h eh e r i s t i ca l g o r i t h mb a s e do nc h a i n i n gi d e a a c c o r d i n gt ot h ek o ds y s t e m t r a i t s 。i ta l s oa r 盟l y z e dt h em o d u l e si nt h es t r e a m i n gs e r v e ra n dc l i e n t ，鼬w e l l 够t h er a t e c o n t r o lf o rt h ec o n t e n tp r o d u c e t h ea d v a n t a g e so ft h ea p p l i c a t i o nl a y e rm u l t i c a s ta l ea l s o s h o w e di nk o d a p p l i c a t i o n t h er t s pc o m m u n i c a t i o no p e r a t i o np r o c e s s e sa l es h o w e df o r b o t ht h ed i r e c ts e r v i c ec a s ea n dt h er e d i r e c ts e r v i c ec a 辩i ta l s oi n t r o d u c e st h ec h a i n i n g m u l t i c a a ta n di t sr e l a t i o nw i t hc u f f e n tp 2 pt e c h n o l o g ) t h eh e u r i s t i ca l g o r i t h mb a s e do n c h a i n i n gi si m p l e m e n t e di nk o ds y s t e mw i t ht h er t s pr e d i r e c t i o n a tl a s tt h ee x p e r i m e n t s s h o wi tw o r k sw e l l t h et h e s i sg e n e r a l i z e st h ef r a m e w o r ko fh e u r i s t i c s i no r d e rt or e - u s et h ee d g e si i lt h e s e l e c t e dp a t ha sm a n ya sp o s s i b l e ，i td e s i g n ss e v e r a ln e wh e u r i s t i c s ，b a s e do nt h en u m b e ro f h o pa n dt h en u m b e ro fv e r t e xd e g r e ei nt h ep a t hr e s p e c t i v e l y m o r e o v e r , i td e s i g n st h e s a m p l eg r a p hf o re v e r yh e u r i s i t i cw h e r et h em o d i f i e dh e u r i s i t i cb a s e do nh o po rv e r t e x d e g r e ec a ng e tt h eo p t i m a ls o l u t i o n ( t h em i n i u ms t e i n c rt r e e ) ，w h i l et h ep r i m a r yo n ec a n t a c h i e v et h eo p t i m a ls o l u t i o n t h em o d i f i e dh e u r i s t i c sp r o v et ob ec o r r e c ta n db e t t e rt h a nt h e p r i m a r yo n e s t h eu p p e rb o u n d so ft h e i rw o r s t - c a s ep e r f o r m a n c er a t i o sa r ea l s op r e s e n t e d f o rt h es t e i n e rt r e ep r o b l e m t h et h e s i si n v e s t i g a t e st h ec o m b i n e dh e u r i s t i c sa n dt h e i rw o r s t - c a s ep e r f o r m a n c e r a t i o s t h ew i d e l yu s e dh e u r i s t i c sn e e dl e s sr u n n i n gt i m ea n da 他e a s i l yi m p l e m e n t e d t h e i r d 晌肿n c e sa r ei n c o m p a r a b l ee a c ho t h e r , s oi ti sn e e d e dt oi n v e s t i g a t et h ep e r f o r m a n c eo f t h e i rc o m b i n e dh e u r i s t i c sf r o mt h ea c a d e m i cv i e w t h et h e s i sp o i n t so u tt h eu p p e rb o u n do f 上海交通大学博士学位论文k o d 多播技术与s t c i r 树启发式算法 t h ew o r 蛀- c a s cp e r f o r m a n c er a t i of o rt h ec o m b i n e dh e u r g t i ei st h el e a s t ( o r o n co f a l l t h eu p p e rb o u n d so f t h eh e u r i s t i c si nt h ec o m b i n e dh e u r i s i t i e t h eu p p e rb o u n da l s ol 啪v c s t ob et i g h tf o re v e r yc o m b i n e dh e u r i s i t i e f u r t h e r m o r e t h ec o m b i n e dh e u r i s t i cc a n g , u a r a n t c et h es o l u t i o ni st h eb e s to n ca m o n ga l lt h es o l u t i o n st ot h eh e u r i s i t i e si n t l _ 峙 c o m b i n e x lh e u r i s t i c w h i c hs c c u f l e st h es o l u t i o nq u a l i t y , a n d 佗l t ”v e st h er i s ki n t r o d u e , e db y j u 舛a p p l y i i i gas i n g l eh e u r i s t i c t h et h e s i si n v e s t i g a t e st h el o w e rb o u n d so ft h er e l a t i v eg r e e d ya l g o r i t h ma n dk - l o s s c o n t l 批ta l g o r i t h m t h el a t e s tr e s e a r c hp r o g r e s sf o r t h es t e i n e rt r c cp r o b l e mi sb a s e do na s i m p l eg r e e d ya l g o r i t h mf r a m e w o r k t h eg r a p h su s e df o rp r o v i n gt h el o w e rb o u n d1 3 3 3 a n d1 3 8 5 a v e r yc o m p l i c a t e d as i m p l e rg r a p hi so r e s e n t l ，w h o s e l o w e rb o u n d i s i 3 3 3 t h et h e s i sd e s i g n san 哪g r a p hf o rk - l o s sc o n t r a c ta l g o r i t h ma n dp r o v e si t si o w c r b o u n d i s1 2 2 6a t l e a s t w h i l e t h e c u r r c r l tb c s t l o w e rb o u n d i s i 2 t h et h e s i sa l s od e s i g n sam o d i f i e dr e l a t i v eg r e e d ) , a l g o r i t h m , w h i d ai n t c g r a t 船t h e r e l a t i v eg r e e d ya i g o r i t h ma n dk - l o s sc o n t t 扯ta l g o r i t h m , a n dp r o v e si t st t p o e rb o u n di s 1 4 3 6u n d e rt h ea s s u m p t i o nt h a tt h ec o n t r a c tt h e o r e mi sr i g h tf o rt l 砖k - l o s sc o n t l a d a i g o r i t h m , w l a i l ce , , r r e m l yt h ek n o w nu p p e rb o u n do ft h ea p p r o x i m a t i o na l g o r i t h mf o rt l 鹭 s t c i n e rt 嘴p r o b l e mi s1 5 5 f i n a l l y , t h ed i s s e r t a t i o ns u n i $ u pt h eo v e r a l lw o r k s ，a n dg i v c ss o n i cr e s e a r c hp r o p o s a l s o f t h ek e y p o i n t so i lt h ei s s u ei nt h ec o m i n gs t a g e k e yw o r d ：m u l t l e a s t , s t c i n c rt r e e ，h e u r i s t i c s ，g r e x , d ya l g o r i t h m n 符号说叨 符号说明 g ：无向图g = ( 矿，e ，c ) ； y ：图的顶点集； e ：图的边集； 以，c ， ，：边的距离、长度、费用、权重函数： d 瞎( v ) ：顶点v y 的度数； d y ：基本顶点集： s ；矿一z ：可能的s t e i n e r 顶点集； 勺：边( f ，d e 的非负费用( 或边权重、边距离) ； d e ：图g 中顶点f 和之间的最短路费用； d 亿r ) = r a i n d e l j ：图g 中顶点，和子图t ；( 巧，b ) 之问的最短路费 用： j p ( ，力：图g 中顶点f 和j 之问的最短路； ，( f ，d ：顶点，和子图t = ( 咋，屏) 之问的最短路； p ( f _ ，) ，p 4 ( j ，d ：图g lj 顶点f 和，( 子图t = ( ，b ) ) 之问满足一定条 件的路径： i 丁l - 巳e r c o ) ：子图r 的边费用之和； 7 0 = r a i n i t i t r l ，兀为问题的可行解集j a b b r e v l j 啦i o n a d h a d h f c h c h r d a h f c 1 1 s h k 。l c a k m 旧 k o d m p h m r g a n a t v e p d h p m s t p 3 1 h r g a s c h s n 蛆1 2 t h 3 t h a b b r e v l a t i o n m i n i m u ma v e r a g ed i s t a n c eh e u r i s t i c m i n i m u ma v e r a g ed i s t a n c eh e u r i s t i cw i t hf u l lc o n n e c t i o n c o n t r a c t i o nh e u r i s t i c r e v i s e dc o n t r a c t i o nh e u r i s t i c d u a ia s c e n th e u r i s t i c f u l lc o m p o n e n t s i t e r a t e d1 s t e i n e rh e u r i s t i c k - l o s sc o n t r a c t i n ga l g o r i t h m k o u ，m a r k o w s k ya n db e r m a n ( o rs t h m i n i m u ms p a n n i n gt r e e h e u r i s t i c ，s d i s t g - - s h o r t e s td i s t a n c eg r a p h ，d n h - - d i s t a n c en e t w o r k h e u r i s t m k a r ao ko od e m a n d m i n i m u mp a t hh e u r i s t i c ，o rc h i n s - - c h e a p e s ti n s e r t i o n m o d i f i e dr e l a t i v eg r e e d ya l g o r k h m ( o ra p j n s ) a r b i t r a r yi n s e r t i o n p r i m a l d u a ih e u r i s t i c m i n i m u ms p a n n i n gt r e ea n dp r u n i n g m i n i m u mp a t ha n dm i n i m u m3 - t u p l eh e u r i s t i c ，o rc h r n s - 3 - - - c h c a p e s t i n s e r t i o nw i t h3 - c o n n e c t e dc o m p o n e n t s r e l a t i v eg r e e d ya l g o r i t h m s e tc o v e r i n gh e u r i s t i c s h o r t e s tp a t h s m i n i m u m2 - t u p l eh e u r i s t i c m i n i m u m3 - t u p l eh e u r i s t i c 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 明的法律结果由本人承担。 学位论文作者签名：艺趿 日期：五”7 年3 月f 日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 保密口，在 年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上方框内打“” 学位论文作者签名：，= ! 、，觇 日期：加啼7 月厂日 指导教师签名：砀渺 眺叼年弓月厂日 第一章绪论 1 1引言 第一章绪论 随着多播技术的日渐成熟，以及i p 网和a t m 阿对多播服务的支持【i l c 2 l ，基于多 播技术的应用也受到了学术界和工业界的广泛关注由于k o d ( k mo k o nd e m a n d ) 系统的曲目在单位时问内被重复点播的频率较高、终端之问相互的网络带宽较充裕。 因此应用多播较为适合通过多播，选择较好的路由可以使系统的网络带宽的利用 效率和整体性能大大提高 网络多播路由问题与s t e i n e r 树问题相对应，而s t e i n e r 树问题是n p ( n o l p d e t e 删n i s d cp o l ”o | r i i a i ) 难的组合最优化问题唑s t e i n c r 树问题的研究主要是设计较好的 近似算法。近年来，随着欧几里德s t e i n c r 比的g i l b e r t p o l a k 猜想【4 】、更好近似算法的 存在性 4 h 1 0 1 和多项式时问近似策略( p t a s ) 的存在性等许多公开问题相继得以解 决使得s t e i n e r 问题及其变种问题成为国际上非常活跃的研究热点之一 ：本章首先介绍了k o d 系统及其特点，并给出了本文的研究重点然后具体介绍 了多播视频路由技术和该技术与图论中s t e i n c r 树之问的对应关系。最后给出s t e i n e r 树问题的定义，并简要叙述了其精确求解算法及些特例，以及一些典型的启发式算 法和贪心算法1 1 2 】门 1 2k o d 系统及其特点 1 2 1 流媒体技术简介【1 4 】 在网络上传送多媒体信息日前主要有下载和流式传输两种方案由于视音文件数 据量大，再加上网络带宽的限制，下载常常要花数分钟甚至数小时。而流式传输方式 下，流式媒体在播放前并不下载整个文件，只将开始的部分内容存入内存，流式媒体 的数据流随时传送随时播放。 流式传输有顺序流式传输( p r o g r e s s i v es t r e a m i n g ) 和实时流式传输( r h 肌e = r e a m i n g ) 两种方式。顺序流式传输是顺序下载，在下载文件的同时用户可观看在线媒 体。由于标准的m t p 服务器可发送这种形式的文件，也不需要其他特殊协议它经 上海交通大学博士学位论文 k o d 多播技术与s t e i n e v 树启发式算法 常被称作h r r p 流式传输顺序流式文件易于管理，但不支持现场直播，严格地说是 一种点播技术 实时流式传输与顺序流式传输不同他需要专用的流媒体服务器与传输协议实 时流式传输总是实时传送，特别适合现场事件实时流式传输必须匹配连接带宽这 意味着图像质量会因网络速度降低而变差。实时流式传输允许你对媒体发送进行更多 级别的控制，因而系统设置，管理比标准h t t p 服务器更复杂 一般说来，如视频为实时广播，可使用流式传输媒体服务器，应用如r t s p 的实 时协议，即为实时流式传输。如使用h t t p 服务器文件即通过顺序流发送流式文 件也支持在播放前完全下载到硬盘 由于互联网以包为单位进行断续的异步传输，流媒体文件在传输中要被分解为许 多包而网络是动态变化的，各个包选择的路由可能不尽相同，所以到达客户端的时 间延迟也就不等为此，使用缓存系统来弥补延迟和抖动的影响，并保证数据包的顺 序正确，从而使媒体数据能连续输出，不会因为网络暂时拥塞使播放出现停顿 流式传输的过程一般是这样的：用户选择某一流媒体服务后，w e b 浏览器与w 曲 服务器之问使用h t t p 厂r c p 交换控制信息，以便把需要传输的实时数据从原始信息中 检索出来；然后客户机上的w e b 浏览器启动a vh e i p c r 程序，使用h 1 r p 从w e b 服 务器检索相关参数对h e l p e r 程序初始化这些参数可能包括目录信息、a v 数据的编 码类型或与a v 检索相关的服务器地址。 实现流式传输般都需要专用服务器和播放器 1 2 2 常见的、的d 系统1 1 4 l l n l e 】m e t i n t r a n e t 上使用较多的流媒体技术主要有r e a ln e t w o r k s 公司的r e a l s y s t e m ，m i c r o s o f t 公司的w i n d o w s m e d i a t e c h n o l o g y 和a p p l e 公司的q u i c k t i m e - 它 们是流媒体传输系统的主流技术，在这里做个简单介绍 i r e a n e t w o r k s 公司的r e a l s y s t e m p e a n e t w o r k s 公司是世界领先的网上流式视音频解决方案的提供者，提供从制作 端、服务器端到客户端的所有产占占它的客户端播放器r e a l p i a y e r 的全球注册人数已 经超过了1 6 亿人。r e a l n e t w o r k s 公司最新的网上流式视音频解决方案叫r e a l s y s t e m i q ，它容易安装，在高低带宽均可提供良好的视音频质置 2 微软公司的w i n d o w sm e d i a 2 第一章绪论 w i n d o w s m e d i a 的前身是n e t s h o w 产品，随着流媒体的广泛应用，微软公司推出 了整套的流媒体制作，发布和播放产品，其服务器端的w i n d o w sm e d i a s c r v e r 产品在 w n d o w s n ts e r v e rp a c k4 上可以安装并且集成在w i n d o w s2 0 0 0s e r v e r 中w i n d o w s m e d i a 产品的一大特点是其制作、发布和播放软件与w i n d o w sn t 2 0 0 0 g x 集成在一 起，不需要额外购买制作端与播放器的视音频质量都上佳，而且易于使用 3 苹果公司的q u i c k t i m e q u i c k t i m e 是a p p l e 公司面向专业视频领域开发的多媒体技术平台，支持几乎所 有主流的个人计算平台是数字媒体领域事实上的工业标准其最新版本是q u i c k t u n e4 ，支持开放标准 r r r p 、r t p 、r t s p 、协议和模块化a p ，对于使用m a co s x 的用户来说是一个比较理想的流视频方案 1 2 jk o d 系统的特点 k o d ( k a r ao ko ni ) c m a n d ) 是指用在卡拉o kl i | 的点歌系统，相对于通用的v o d 系统，k o d 是一个专用的系统k o d 系统较通用的v o d 系统具有以下特点： 1 终端相互之问的网络距离和网络带宽不同 通用v o d 系统一般在广域网中，终端在网络中也较为分散终端相互之间的网 络带宽不确定；而k o d 系统的终端一般较集中甚至就在一个局域网中，其终端之 间的网络路由距离比较短( 甚至经常就接在一个交换机上) ，终端相互之问的网络带宽 很充裕 2 对系统延时要求不同 通用v o d 的用户系统即点即看，对系统的延时要求比较高，一般为数秒到数十 秒；而k o d 系统的用户一般提前就选择了较多曲同因此给系统较多的调度和准备 的时间。 3 内容长度不同 通用v o d 系统的内容一般是影片，影片长度在半小时到两小时的比较多；而k o d 系统的内容一般比较短，大多数的曲目内容的长度在五分钟左右。 4 曲目单位时间内被重复点播的频率不同 k o d 系统由于用户密度很大，曲目在单位时间内被重复点播的频率很高，甚至 在同一时间点播同一曲目的几率也非常高：而通用v o d 系统由于影片比较长，且用 户比较分散，影片在单位时间内被重复点播的频率相对要小很多 上海交通大学博士学位论文k o d 多插技术与s t e i n e r 树启发式算法 5 应_ h j 需求不同 k o d 系统一般要具有随时呼口q 服务、鼓掌等功能：而通用v o d 系统一般不需要 这些功能 6 数据码率不同 k o d 系统的内容的数据码率比较高，比如m p e g - ic i f i 的码率就达l 1 8 m b p s 而且一般用d l 格式比较好m p e g 2f u l l - d i 、m p e g - 4f u l i - d i 的码率分别达到 3 - 1 5 m u s ，2 - 1 5 m b p s ；即使是最新的h 2 6 4 压缩技术，f u u - d i 的码率至少也要 i 5 - 5 m b p s 才能获得比较好的效果而通用v o d 系统片源的码率一般在3 s 4 k b p s - - 2 m b p s 由于k o d 系统的以上特点，尤其是终端相互之问的网络距离短，带宽充裕，曲 目重复点插的频率高的特点。特别适合采用c h a i n i n g 多播技术【1 5 j ，充分发挥每个终靖 的作用本文就是研究视频多播技术如何在k o d 系统中的应用，以发挥k o d 系统的 特点。在此基础上。本文还将着重讨论多播路由的理论模型一- - s t e i n c r 树的求解，设 计分析了s t c i n e r 树若干启发式算法和性能 1 3多播视频路由网络模型和s t e i n e r 树 从应用层来区分，视频服务可以分为广播( b r o a d c a s t ) 和点播( v k l e o0 1 1d e m a n d ) 两种而从数据传输方式上看，可以分为多播( m u n c a s d 和单播( u n i c a s t ) 单播是 通常所说的一台主机到另台主机的访问是单点到单点的通信方式；多播，也称组 播是一台主机向被分配到同一组( 可以不是同子网) 的主机发送数据是点到多点 的通信方式【h 2 0 1 为了正确把信息送到多播组。必须为它们寻找路由，信息按选择的路由传送。由 于多播组有多个目的节点，因此多播路由也比单播路由复杂许多多播路由算法是本 文的研究重点 1 t 1 实现多播路由选择的方式0 6 1 在通信网络上实现多播通信的方式有很多种归纳起来，主要有以下几种： 扩散( f l o o d i n g ) 方式：信源把信息发送到所有的出链路上，每个网络节点都接 收并转发该信息。最终信息被发送到整个网络，但是只有多插组成员才能接 收它。这种方法虽然比较简单、可靠，但是它非常浪费网络带宽资源，而且 第一章绪论 容易造成网络拥塞。 分别寻址方式：即用点到点通信来支持多点通信应用这是人们最早在分组 通信网络上实现多播通信应用的方式。信源分别向每个接收者发送信息有 多少个接收者，信源就要将相同的信息发送多少次。这种方式除了浪费网络 带宽外还增加了源的负担，并造成接收者信息接收不同步 多目的地寻址方式：源使用可变长度的分组头来发送信息分组的目的地址 域内有多个目的地址( 即接收者的地址) 虽然源只需发送一次分组，但接收 者的数目有限且增加了带宽和路由器的负担。且与已有网络的兼容性差 基于生成树的转发方式：构造一棵覆盖信源和接收者多搔路由树，信源只需 要发送一次数据，然后通过多播树来转发。数据在树的分叉处被复制，直至 每个接收者。显然，这个方案在传递信息的过程中，尽可能共享链路，因此 节省了网络资源，并减轻了源的负担而且它还有可能使接收者实时、同步 地接收信息，对于支持多媒体通信非常有利。 比较上述方案可以发现。基于生成树的转发方式是实现多播通信的一种比较有效 的解决方案多播树的构造是解决多播问题关键一步 而在网络连通图中寻找连接一个源节点和一组日的节点的多播树，使得信息通过 这个多播树从源节点传送到所有的目的节点的代价最小，最终就对应到在连通图中求 s t e i n c r 埘。 1 3 2 多播路由算法的分类l 6 1 多播路由算法可以从不同的角度、不同的准则来分类： 按是否允许网络成员随时加入或离开多播组分为静态路由算法和动态路由算 法。静态多播路由算法中多播组成员是同定的路由计算一次性完成，并 且在一次连接过程中多播成员和路由树都不发生改变。而动态多播路由算法 则允许组成员动态加入或离开多播树在次连接- ”般会发牛改变。 按是否有q o s 约束分为无约束算法和有约束算法。许多现有的算法是为非实 时网络设计的无约束多播路由算法，它们往往只试图优化树的费用，但实时 应用对q o s 提出要求，有约束的多播路由算法通常是在给定q o s 约束的条件 下使树的费用最小 按是否由一个节点集l t | 运算或分布式运算分为集- l 式和分布式算法集中式 上海交通大学博士学位论文 k o d 多播技术与s t c i n c r 树启发式算法 算法往往简单，快速，但是由一个节点维护整个网络的状态，其开销有可能 会非常大并且当网络大时，搜集整个网络的状态会变得很困难但是在许 多情况下，这些算法可以作为其它算法比较的工具，具有很强的理论意义， 吸引着广大研究者去深入研究在分布式算法中，网络中的每个节点都参与 运算，这些节点只掌握网络的部分信息，通过节点简相互交换信息来计算路 由分布式算法相对于集巾式算法较复杂且速度慢，但是它有一个显著的优 点：就是任何节点都不用保持整个网络的状态到目前为止，集中式算法的研 究较多，分布式算法的研究较少 实际上，一种算法可以同时属于以上一种或几种分类方法，如某种多搔路由算法 可以是集中式静态无约束算法 诸多学者都对以上的各种类型的路由算法进行了研究，但是大多数算法还是在求 s t e i n e r 树的基本思想为出发点傲的改进，直至今日研究如何求s t c i n c r 树，如何分 析算法性能，仍然是多播路由算法中极其重要的课题。也是本文的研究重点 1 4s t e i n e r 树问题及其研究现状 1 4 1 定义 。 假定有一无向图g = ( y ，e c ) 。它由个顶点的非空集矿。连接顶点顶的m 条边的 集e ，边的费用( 或长度，、距离d 。权重w ，后面除特别说明外，均指同一函致) 函数c ：e 一足组成。有一顶点子集d 矿，目的是寻找图g 的子图g d ，使得d 的任 一对顶点之间存在一条路，并且g 。的距离和最小，即。c o ) 最小，该问题简记为 卵( s t c i n c rp r o b l e m ) 假设n 爿y i ，m 爿e i ，p 爿d l ：同时，为符号简便，顶点 矿= 1 , 2 ，1 ) ，d = l ，2 ，p ) 在图g 中，顶点v e y 的关联边数称为v 的度数。记为d e g g ( v ) ，简记为d e g ( v ) 不同项点与边的交替序列称为路。如果路的第个顶点与最后一个顶点相同，其余顶 点不同，则叫做罔。没有圈的幽称为森林如果v i , j v 在图g 中存在一条路，则称 图g 是连通图，否则称为非连通圈。没有圈的连通图称为树 图h = ，f ，c ，) 称为图g = ( y ，e ，c ) 的子图，如果s 矿。，e 并且 y e e f ，印0 ) = c 0 ) 如果s = v 则日称为支撑子图：如果s s v ，则日称为支撑 6 第一帝绪论 的子图；如果s 是v 的一个子集，则s 的导出子图是g 的个子图，其顶点集为s ， 边集f ； ( f ，) e e i ，e s ，e 毋 每个非连通图能分裂成最大顶点数的导出连通子图，称为g 的成分 设 墨巩表示图g 的顶点集矿的一个划分，边集万( 研= ( 力e e l i e s ，仨毋称 为只亏之间的切边集 如果图g 的每对顶点都相邻，则g 称为完全图如果图g = ( 矿，e ，d 中签c y ， 使得= 艿( $ ，则g 称为二部图 对于g = ( 矿，e 力中任寇边p = u ，d ，它的距离c ( 力也记作c ，图g 的距离 e ( o d # - 。嘶) 如果图g = ( y ，e ，o 是完全圈，c ( e ) o , v e e e 并且。u s c , j + c i ，v i , j ，l e v ，刖 圈称为满足三角不等式 图g = ，e ，c ) 中两个顶点f ，j 矿之间的最小距离略记为( f ，力，或讯d 路 尼( f d 的费用记为几g d 或m 力顶点，e 矿和顶点子集矿y 之问的最小距离路 记为屹( f 矿) 或尸( f 形) 一个再露的矩阵一= ( j 妫称为图g 的距离矩阵。一个完全图4 ( g ) = ( y ，墓- ，毋 称为图g 的距离图 收缩图g 的边p = ( f ，_ ，) ，则对圈g = ( 矿，e c ) 进行如下处理： 关联，的边使其关联“ 项点，从图g 中移去，如果，是顶点，则在收缩图巾顶点，被当作顶点； 关联i 的环从图g 中移去，如果i 有一对平行边，则距离较大的边从图g 中 移去 收缩图g 的边子集f e ，则依次对边进行收缩。 1 4 2 多项式可解和归约 如果1 d 仁l ，则g 。由一个顶点组成。 如果i d 2 ，则g 。归约到求解展短路问题，该问题有多项式时间求法( 如 d i j k m m t + 盈1 ) 。 如果j d 疗，则g 。归约到求图g 的最小生成树，这种问题可由k r u s k a l 算法【2 1 u 矧 上海交通大学博士学位论文 k o d 多播技术与s t e i n e r 树启发式算法 或p r j i l l 算法【2 u 2 2 1 求解 晰m c 一2 3 l 歹i j 出了七种归约，这些归约方法经常能将较大s t e i n c r 树问题归约到更小 s t e i n e r 树问惠。 因此，本文假设g = ( l e c ) 是连通图，且c ( 力 0 ，v p e e ，3 s p s n - i 1 4 3 动态规划算法 d r e y f u s - w a g n e r 2 4 的动态规划算法( 1 9 7 2 ) 是求解s t e i n e r 最小树的常用精确算