（计算机应用技术专业论文）覆盖网络多播路由协议及算法的研究.pdf

摘要 摘要 随着计算机网络的不断发展，互联网已经成为了人类社会主流一个重要组成部分。人们希望互联网 能够不断地提供应用所需的各种网络服务特别是，以视频会议、视频点播、远程教育等为代表的新型 多媒体多播应用的大量涌现，对多播通信服务提出了迫切的需求 基于覆盏网络思想的覆盖多播技术是由端系统而不是核心路由器实现多播通信的所有功能，与球多 播相比，其最大的优势在于无需改变下层网络基础设施，易于部署。这体现了下一代网络服务的研究重 点正在从网络层向应用层跃迁的趋势。如何提供满足应用需求的覆盏多播路由是其研究的核心内容。 本论文主要针对覆盖多播的路由协议及算法等相关问题展开研究，其中，多媒体应用的q o s 需求以 及网络环境的异构性是本文关注的重点。我们首先提出了通用的覆盖多播网络模型，对覆盖多播中的路 由优化问题进行了系统分类，并对当前主要的覆盖多播路由的协议和算法进行了全面的比较和分析，为 本论文建立系统理论框架和指明研究方向。在此基础上，我们分别从覆盖多播的集中式路由算法、分布 式路由协议和原型系统等几方面开展了研究工作。 在集中式算法方面，提出了一种新的基于度约束延时综合和应用层拓扑优化双重策略的最小延时覆 盖多播树生成算法一度延时紧凑树算法( d d c t ) ，改进了多播树的性能；针对实时多媒体应用对带宽需 求的异构性，采用分层的带宽分配策略，提出了一个异构环境下构造最小延时覆盖多播树的启发式算法 一分层的紧凑树算法( l ( 了) 该算法能有效地降低多播树的高度和网络资源使用量。 在分布式协议方面，提出了一个新的分布式、树优先的覆盖多播路由协议b o w c a s t 。该协议采用简 单、灵活的单向延时探测技术，能很好地适应非对称链路延时环境：面向实时多媒体多播应用，提出了 一个支持异构q o s 需求的分布式、树优先的覆盖多播路由协议q o s 覆盖多播树协议( q o m t p ) ，并研 究了其局部优化算法。该协议能获得较高的节点接纳率，并保持较小的平均接入代价 在原型系统方面，研究并实现了一个新的基于代理服务器的覆盖多播系统一服务可定制的覆盖多播 系统( s c o m s ) 该系统采用了新的体系结构框架将结构化p 2 p 路由和树优先的覆盖多播路由构造方 法相结合，具有良好的可扩展性、高效的q o s 覆盖多播路由和灵活的服务定制能力。 本论文的研究成果可为覆盖多播路由协议和算法的研究提供新的理论方法和思路，也可以应用于实 际的覆盖多播系统中，具有较高的理论价值和较好的应用前景 关键词：网络服务，覆盖多播，路由算法，路由协议，q o s ，异构性 分类号：t p 3 9 3 东南人学博i 学位论史 a b s t r a c t w i t ht 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 k ，i n t e r n s 4h a sb e e nb e c o m i n ga l li m p o r t a n tp a r to ft h em e a n s t r e a m i n go fh u m a nb e i n g p e o p l eh o p ei n t e r a c te o n l dp r o v i d ea l lk i n d so fn e t w o r ks e r v i c e st h ea p p l i c a t i o n s n e e d e s p e c i a l l y , t h ee m e r g e n c eo fm a n yn e wm u l t i m e d i ag r o u pa p p l i c a t i o n s ，s u c ha sv i d e oc o n f e r e n c i n g ， v i d e o - o n - d e m a n da n dd i s t a n c el e a r n i n g ，r e q u i r em u l t l c a s tc o m m u n j c a t i o ns e r v i c ei m m i n e n t l y b a s e do nt h ec o n c e p to fo v e r l a yn e t w o r k ，i no v e r l a ym u l t i c a s t ，e n ds y s t e m sp e r f o r ma l lm u l t i c a s t c o m m u n i c a t i o nf i m c t i o n a h t i e si n s t e a do fi pr ；d u t e r s c o m p a r e dw i t hi pm u l t i c a s t ，t h eg r e a t e s ta d v a n t a g eo f o v e r l a ym u l t i e a s ti si tn e e d n tc h a n g et h el o w e rn e t w o r ki n f i a s t r u c t u r e ，a n dc a l lb ed e p l o y e de a s i l y o v e r l a y m u l t i e a s te m b o d i e st h et r e n dt h a tt h ee m p h a s i so fn e t w o r k - r v i c er e s e a r c hi ss h i r i n gf r o mn e t w o r kt o a p p h c a t i o nl a y e ri nt h en e x tg e n e r a t i o nh i m m e t ，a n di t sc o r ep r o b l e mi sh o w t ob u i l do v e r l a ym u l t i c a s tr o u t i n g s a t i s f i e db ya p p l i c a t i o n s h l “st h e s i s ，o v e r l a ym u l t i e a s tr o u t i n gp r o t o c o l sa n da l g o r i t h m sw i t ho t h e rr e l a t e dp r o b l e m sa s t u d i e d ， w h e r et h eq o sr e q u i r e m e n t so fm u l t i m e d i aa p p l i c a t i o na n dh e t e r o g e n e i t yo fn e t w o r ka r ef o c u s e d f 缸n y a g e n e r a lo v e r l a ym u l t i c a s tn e t w o r km o d e li sp r o p o s e d ，a n dt h er o u t i l l go p t m m lp r o b l e m si no v e r l a ym u l t i c a s ta t e c l a s s i f i e d t h e ns o l n er e c e n ti m p o r t a n to v e r l a ym u l t i c a s tr o u t i n gp r o t o c o l sa n da l g o r i t h m sa r ef u l l ya n a l y z e da n d d i s c u s s e d t h e s ec o n s t r u c tt h et h e o r yf r a t u e w o r ka n dp o i n to u tt h es t u d yd i r e c t t o no ft h i st h e s i s b a s e d0 nt h e a b o v ew o r k , o u rr e s e a r c ho l io v e r l a ym u l t i e a s ti sp e r f o r m e di nt h ef o l l o w i n ga s p e c t s ，w h i c hi n c l u d ec e n t r a l m e d r o u 衄ga l g o r i t h m s ，d i s t r i b u t e dr o u t i n gp r o t o c o l sa n ds y s t e mp r o t o t y p e i nt h es t u d yo fc e n t r a l i z e dr o u 缸ga l g o d t l m e b a s e d b o t hd e g r e ec o n s t r a i n t s - d e l a yi n t e g r a t i o na n d a p p l i c a t i o nl a y e rt o p o l o g yo p t i m u ms t r a t e g i e s ，an e wm i n i l n u md e l a yo v e r l a ym u l t i e a s tt r e eb u i l d i n ga l g o r i t h m c a l l e dd e g r e e d e l a yc o m p a c tt r e e d c t ) i sp r o p o s e dt oi m p r o v et h er o u t i n gp e r f o r m a n c e ；t os e t t l et h e h e t e r o g a n e i t yo fb a n d w l d t hr e q u i r e db yr e a l - t i m em u l t u n e d ma p p l i c a t i o n , a d o p t i n gt h es t r a t e g yo fl a y e r e d b d w i d t i la l l o c a t i o n , ah e u r i s t i cr o u t i n ga l g o r i t h mc a l l e dl a y e r e dc o m p a c tt r e e di sp r o p o s e dt ob u d da m i n i n l u u ld e l a yo v e r l a ym u l t i e a s tt r e ei nh e t e r o g e n e o u sc o n d i t i o n 1 1 l cl c rc o u l dr e d u c eb o t hh o p sa n dn e t w o f k r e s o u r c eu s a g eo f t h et r e ee f f e c t i v e l y i nt h es t u a yo fd i s t r i b u t e dr o u t i n gp r o t o c o l s ，ai l e wd i s t r i b u t e dt r e e - f i r s to v e r l a ym u l t i c a s tp r o t o c o lc a l l e d b o w c a s ti sp r o p o s e d a d o p t i n gas i m p l ea n df l e x i b l eo n e - w a yd e l a yp r o b em e t h o d ，b o w c a s tc a na d a p tt h e a s y m m e t r i cl i n kd e l a ye n v i r o n m e n tw e l l ；t os u p p o r th e t e r o g e n e o u sq o s 代= q i 越托m 即曲o fm a l - t i m em u l t i m e d i a m u l t i c a s ta p p h c a t i o n s an e wq o so v e r l a ym u l t i e a s tr o u 缸gp r o t o c o lc a l l e dq o s a w a r eo v e r l a ym u l t a c a s tt r e e p r o t o c o l ( q o m t p ) i sp r o p o s e d ，a n di t sl o c a lo p t i m u ma l g o r i t h mi ss t u d i e d ，t o o q o m t pc a nr e d u c et h en e t w o r k r e s o u r c eu s a g eo f m e m b e r so nt h et r e ea sw e l la sa c h i e v eai n g h e ra d m i s s i o nr a t eo f m e n a b e r s i np r o t o t y p e ，an e wp r o x y - b a s e do v e r l a ym u l t i c a s ts y s t e mc a l l e ds e r v i c ec u s t o m i z a b l eo v e r l a ym u l t i c a s t s y s t e m ( s c o m s ) i ss t u d t e da n di m p l u m e n t e x lc o m b i n i n gd h t - b a s e dp 2 pa n dt r e e - f i r s to v e r l a ym u l t i c a s t r o u t i i l gp r o t o c o l s ，s c o m sc a l ln o to n l yk e e ph i g hs c a l a b i h t y , b u ta l s op r o v i d ee f f i c i e n tq o so v e r l a ym u l t i c a s t r o u 幽ga n df l e x i b l ec a p a b i l i t yo f s e r v i c ee n s t o m i z a t i o n t h er e s e a r c hc o n c l u s i o n so ft h i st h e s i sc o u l dn o to n l yp r o v i d en e wt h e o r e t i c a lm e t h o da n di d e nt os t u d y o v e r l a ym u l t l c a s tm u t i n gp r o t o c o l sa n da l g o r i t h m s ，b u ta l s ob ea p p l i e di np r a c t i c a lo v e r l a ym u l t i e a s ts y s t e m , t h e r e f o r e ，h a v eh i 【g ht h e o r e t a e a lv a l u ea n dw i d ea p p l i e df u m g r o a n d k e y w o r d s ：n e t w o r k e r l d c e o v e r l a ym u l t l e a s t , r o u t i n g a l g o r i t h m , r o u t i n gp r o t e t o l ，q o s ，h e t e r o g e n i t y i i 目录及索弓 论文插图索引 1 1 互联网协议栈的沙漏模型2 1 2 覆盖多播路由示意图5 1 3i p 多播和覆盖多播路由比较示意图6 2 1 覆盖多擂网络模型示意图1 2 2 2 覆盖多播系统结构分类示意图1 4 2 3 覆盖多播路由构造方式分类示意图1 5 2 4 覆盖多播树局部拓扑结构调整示意图2 0 2 5 不同范围的节点交换操作示意图2 l 3 1 覆盖多播路由拓扑优化示意图2 9 3 2d d c t 算法伪代码。3 0 3 3 节点只分布在桩域中时，路由性能指标与n 的关系曲线图3 2 3 4 节点任意分布时，路由性能指标与的关系曲线图。3 3 图4 1l c t 算法伪代码4 1 图4 2 树的高度4 3 图4 3 树的相对半径“ 图4 4 树的相对代价4 5 图5 1b o w 技术工作过程示意图4 9 图5 2 节点加入算法5 1 图5 3 a r d p 与的关系曲线( 脓不同值) 5 5 图5 4 m l s 与n 的关系曲线( 脓不同值) 5 5 图5 5r c o s t 与n 的关系曲线( 脓不同值) 5 5 图5 6 a c o 与n 的关系曲线( 鹏【不同值) 5 5 图5 7 a r d p 与的关系曲线( 岛，岛取不同值) 5 6 图5 8m l s 与n 的关系曲线( 5 l ，岛取不同值) 。5 6 图5 9r c o s t 与n 的关系曲线( 两，昆取不同值) 5 7 图5 1 0 a c o 与n 的关系曲线( s l ，s 2 取不同值) 5 7 l 图图图图图图图圈图图图图 自：南人学磷j 一学位论义 图6 1 节点加入算法伪代码 图6 2 不同优化策略影响多播树构造的实例 ，6 4 6 1 ； 图6 3 覆盖多播端系统节点的p 厂r 网描述6 9 图6 4 端系统节点的o n - o f f 模型6 9 图6 5 节点接纳率v s 延时上限( 度约束情况下，静态节点模型) 7 2 图6 6 平均代价v s 延时上限( 度约束情况下，静态节点模型) 7 2 图6 7 节点接纳率v s 延时上限( 度约束情况下，动态节点模型) 7 3 图6 8 节点接纳率v s 延时上限( 异构带宽情况下，静态节点模型) 7 4 图6 9 平均代价v s 延时上限( 异构带宽情况下，静态节点模型) 7 4 图6 1 0 节点接纳率v s 延时上限( 异构带宽情况下，动态节点模型) 7 5 图6 1 1 平均代价v s 延时上限( 异构带宽情况下，动态节点模型) 7 5 图7 1s c o m s 体系结构示意图8 0 图7 2s c o m s 的组成结构图8 l 图7 3i n s a 参考模型与s c o m s 系统的组成结构比较图8 2 图7 4 一个多搔组选项的例子8 5 图7 5s c o m s 的总体实现框架图8 8 图7 6j m f 的媒体流端到端数据传输9 2 图7 7 覆盖网络拓扑实验结果图9 3 图7 8 不同服务需求的客户端的视频流回放9 4 图7 9 平均带宽v s 跳数9 5 图7 1 0 平均帧速率v s 跳数。9 5 图7 1 1 平均带宽v s 星型数一9 5 图7 1 2 平均帧速率v s 星型数。9 5 v i i i 目录及素q 论文表格索引 表1 1 几种典型多播应用的特点比较3 表2 1 覆盖多播路由问题分类表。1 4 表2 2 覆盖多播路由协议和算法的分类比较表2 4 表3 1d d c t 算法的性能优化率( d m 。采用不同的取值模型) 3 4 表7 1 用户连接注册表9 l 表7 2 组应用注册表9 l 表7 3 组管理信息表9 2 i x 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示了谢意。 研究生签名：兰鳖e t期：型：竺垆 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子 文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查 阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：兰鳖 导师签名 第一章绪论 1 1 研究背景 第一章绪论 1 1 1 覆盖网络技术的兴起 自从1 9 6 9 年美国的a r p a 和英国n p l 首次建成分组交换计算机网络以来，以互联网为 代表的计算机网络已经从最初的面向国防或者科研的单一应用的网络发展成为当前全球以 及各个国家的信息基础设施。特别是，1 9 8 9 年w e b 技术的发明，使得互联网得到空前的发 展，并广泛应用于商业领域。截至2 0 0 4 年底，互联网的结点数已达到几百万，有超过l 亿 台主机连接到互联网上，互联网的用户数也突破了7 8 亿 随着互联网技术的发展，新型应用的大量涌现，特别是以电信应用为标志的互联网商业 化趋势，人们对互联网及其应用提出了更高的要求，如大规模可扩展能力、服务质量保证、 多播支持、移动性支持、商业模型、安全保证、可信性、可靠性、可管理性等等。这些要求 归纳起来可分为服务定制、资源控制和用户管理三大类问题【1 1 。同时，互联网的商业化必然 导致互联网的社会化。如今，互联网已经不再是一项单纯的技术，它已经成为了人类社会主 流的一个重要组成部分，互联网最初的建设者和使用者的共同理想目标已不再现实。社会的 各方在参与互联网的建设时，往往有着各自不同的、相互对立利益，并且为此而相互争斗。 d d c l a r k 称之为“扭斗”( t u s s l e ) ( 2 1 。“扭斗”将对互联网的技术走向产生深远的影响，必 须将工程技术和社会科学方法综合起来，才能解决问题。 上述新的情况都是当时互联网的设计者们所始料未及的。最初的互联网采用简单的互联 网体系结构原则和模型，其中，最著名就是“边缘论”( e n d - t o - e n d a r g u m e n t ) 1 3 1 和“沙漏模 型”( h o u r g l a s sm o d e l ) ( 4 1 。“边缘论”强调核心网络简单、端系统复杂的设计思想，以最大 程度她提高互联网体系结构的可扩展性和鲁棒性。“沙漏模型”则是“边缘论”在互联网协 议栈实现上的具体表现形式。在该模型中，互联网协议栈的各层协议根据其复杂程度形成一 时间沙漏形状，如图1 1c a ) 所示。该沙漏中间腰部的网络层采用单一的i p 协议，向下可 以集成各种链路层和物理层通信技术，向上通过传输层协议( t c p 和u d p ) 可以支持丰富 的应用。这一结构具有很强的可扩展性、灵活性和网络互联能力，是最初的互联网得以迅猛 东南大学博- 上学位论史 发展的技术源动力。但是，正是由于展初的设计过于简单，现有的互联网已越来越不能满足 人们日益增长的服务需求。因此，现有的互联网有必要向下代且联网进行演进。 应用层 传输层 一 层 链路层 物理屡 ( a ) 初始设计思想( b ) 网络通信鲍观点( c ) 应用服务的观点 图1 1 互联网协议栈的沙漏模型 关于下一代互联网的发展思路，主要存在有两种观点： ( 1 ) 网络通信的观点 通过增强和扩展核心网络的功能，由网络层直接提供用户所需的各种服务。为此，i e i f 提出了一系列解决方案，如集成服务”、区分服务体系结构1 6 ，标记交换协议 7 1 、i p 多播协 议”、口移动协议【9 垮。但是，这一观点会增加核心网的复杂性，如图1 1 ( b ) 所示，使沙 漏的腰部变粗，破坏了互联网的简单性原则，降低了其可扩展性和灵活性。同时，由于用户 需求的多样性，使“一次定制，随处可用”( o n es i z ef i ta 1 1 ) 的理想技术几乎无法实现。另 外，对网络通信基础设施的改造代价非常巨大，而没有一定规模的投入，网络服务供应商 ( i s p ) 叉很难吸引足够的用户数并盈利，这就进入了“先有鸡还是先有蛋”( c h t c k e na n d e g g s ) 的怪圈。事实上，在互联网中部署q o s 和m 多播的失败就是对“网络通信的观点” 的置疑“。 ( 2 ) 应用服务的观点 相对于网络通信的观点，从应用层( 端系统) 的角度来解决网络层没有很好解决的问题。 如图1 1 ( c ) 所示，在应用服务的观点中，各种新型服务在应用层实现，这就使得在满足用 户需求的同时，保持网络核心的简单性成为可能。根据这一观点，目前，基于应用层技术的 覆盖( o v e r l a y ) 网络技术正迅速兴起，已提出了一系列服务解决方案，包括：服务质量“1 【、 多播2 2 1 1 2 ”、移动 1 3 】【、内容分发 1 5 1 【1 6 1 、网络存储1 7 、大规模分布对象定位1 9 l i 2 0 l 和事件 服务2 1 1 等覆盖网络是由端系统( 主机或服务器) 在下层网络基础设施之上构建的能提供 特定服务的虚拟网络，其最大的优势是无需改变下层网络通信基础设施，可快速、经济、灵 活地部署，同时，也为互联网中“扭斗”问题的解决提供了新的灵活手段【2 】 2 第一章绪论 综上所述，我们看到，互联网的服务提供方式正在从网络层向应用层、从核心路由器向 端系统迁移。这一新的趋势必将对下一代互联网的研究与发展产生深远的影响。显然，覆盖 网络是实现这种转变的关键技术方向，而覆盖多播又是其中的关键服务之一本论文主要针 对覆盖多播，就其如何适应技术和应用的发展开展研究。 1 1 2 多播通信 在各种网络服务中，多播( m u l t i c a s t ) 通信服务一直占有重要的地位不同于单播 ( u n i c a s t ) 通信发送者需要向各个接收者单独发送数据报文，在多播通信中发送者只需要 向所有接受者发送一个原始数据报文，该报文的拷贝由具有多播功能的中间系统完成，并最 终转发给各个接收者。因此，多播通信能节省大量的网络通信资源，并提高通信效率，这使 其成为了支持以实时多媒体应用为代表的下一代新型多播应用( 如：视频会议、视频点播、 远程教育、网络电视等) 的关键技术之一。 然而，新型多播应用的种类非常之多，它们在多播组的规模、组内数据发送源的数量、 组成员的动态性、以及对带宽和延时要求等方面存在着很大的差异。表1 1 给出了几种典型 多播应用的特点比较2 3 1 1 2 ”。由此可见，如何适应不同应用的差异，满足它们的需求，是多 播通信面临的新课题。 表1 1 几种典型多播应用的特点比较 应用多播数据谭 组规模 带寅延时组成员动态性 视频会议多小 士 小低 远程教育单、少 中 中小低 网络电视( i p t v ) 重 大大小高 视频点播( v o d ) 苴 大大小高 多方游戏多中、大中小高 在线股票新闻 苴 大小小高 分布式仿真单、少 由 大视情况低 分布式w e b 缓存更新单、少 中 大大低 东南大学博j 学位论文 1 1 3i p 多播 由于初始的i p 协议是面向点到点的单播通信设计的，伊多播的思想就是通过对口协议 进行扩展，使核心网络( 路由器) 支持多播功能，实现多播通信服务。i p 多播模型最早是 由s d e e r i n g 在1 9 8 8 年提出的脚在其博士论文中，s d e e r i n g 提出了一个开放、动态和无 连接的多播服务模型基于该模型，通过d 类多播地址，任何人任何时间都可以创建、加 入和离开多播组并通过多播组发送和接收数据。随后，人们开始着手构建m 多播实验床一 m b o n e l 2 日。并于1 9 9 2 年4 月在s a nd i e g o 召开的i e t f 大会上，通过m b o n e 首次实现了广 域网上的口多播音频数据传输实验 2 7 1 。在接下来的十年中，人们对p 多捶技术进行了大量 的研究。这一研究过程大致可分为两各阶段：1 9 9 2 1 9 9 7 年为p 多播域内协议的研究阶段， 提出了一系列疋多播路由协议( 如：d v m r p f 2 s j 、m o s p f j 2 9 j 、p i m d m 3 0 j 、c b t p ”、p i m s m l 3 2 j 等) ；1 9 9 7 年以后为m 多播域间协议的研究阶段，提出了为全网部署口多播的多播域间路 由、多播地址管理、多播源发现等协议和方案( 如：m b g p 3 ”，m d s p 3 4 1 ，m a s c b g m p t 3 s l ， m a a a o s l 、g l o p l 3 7 j 等) 。 尽管人们在m 多播方面倾注了大量时间和精力，但是m 多播在全互联网上的部署并未 取得成功。究其原因，可以发现m 多播同时面临着技术和经济的双重困境”】。 ( 1 ) m 多播在技术方面的问题 可扩展性问题：护多播需要路由器保存每个多播组的状态，且采用平面结构的d 类地 址。这将增加互联网核心的复杂性，限制了系统的可扩展性 组管理问愿：由于采用了开放的服务模型，口多播缺少组创建和成员接纳控制机制。 潜在的“恶意节点”很容易加入多播组。并进行攻击 地址管理闯题：缺乏灵活、可扩展的分布式多播地址分配机制。多播节点难以发现可用 的地址，其容易产生地址冲突。 域问路由问题：缺少成熟、有效的域间多播路由协议，阻碍了口多播在全网的部署。 q o s 问题：多播应用需求的多样性以及多播技术本身的复杂性使得在有限的计算能力 下，路由器将无法满足所有需求。 安全问题：为穿越防火墙而采用的隧道技术等变通方案，必然带来一些潜在的安全漏洞。 ( 2 ) 礤多播在经济方面的问题 部署代价问题：球多播的部署需要改造现有的路由器，考虑到互联网的规模，这将造 成巨大的代价，难以全面部署。 4 第一审绍论 商用模型问题：完善的i p 多播服务的商业和计费模型尚未建立，互联网服务提供商 ( i s p ) 缺少部署i p 多播服务所需的足够的“竞争压力”和“盈利动力”。 礤多插的部署问题已经成为制约互联网及其新型应用发展的关键因素之一。为了打破 目前的僵局，必须改变研究思路，寻找口多播的替代方案。 1 1 4 覆盖多播 为避免网络层实现多播的困难，近年来，研究人员希望在应用层直接解决口多播面临 的问题，因而提出了覆盖多播的概念1 3 9 】。覆盖多播的思想是由端系统而不是核心路由器实 现多播通信的所有功能( 如组管理、成员管理、分组复制和转发等) ，下层网络只需提供基 本的端到端单播传输服务。因此，覆盖多播也称被为应用层多播或端系统多播。 接收者 _ 了路由嚣 。端系统 一物理链路 覆盖链路 净物理路径 图1 2 覆盖多播路由示意图 图1 2 为覆盖多播路由的示意图。由图可见，端系统节点通过覆盖链路构成了上层的覆 盖多播树，数据源节点将沿着该覆盖多播树向数据接收节点发送数据，而每个非叶子接收者 在接收数据的同时还要向其孩子节点继续转发不同于口多播，在覆盖多播中，上述多播 功能都是由参与多播组的端系统节点完成的。而下层m 网络只要完成端到端的单播通信功 能，即保证每条覆盖链路所对应的一条下层物理路径的通信即可 覆盖多播的思想与互联网体系结构所遵循的“边缘论”和“沙漏模型”等设计原则是一 致的，这就为解决疋多播的难题提供了新的技术手段和可能。覆盖多播的主要优势在于： 可部署性：覆盖多播只要求下层网络支持单播通信功能，而这正是当前互联网的基本服 务之一。因此，覆盖多播无需改变现有的m 网络基础设施，能以很小的代价，在全互 联网范围内部署，这也是覆盖多播较口多播的最大优势所在。 可扩展性：覆盖多播无需在路由器上维护多播组的状态，保持了核心网络功能的简单性 5 东南人学博士学位论文 特点，使网络能支持大量的多播组。 灵活性：利用端系统灵活的计算能力，覆盖多播还易于实现可靠、q o s 、安全、计费以 及服务定制等高层功能。 覆盖多播的上述优势也充分展现了其广阔的商业化前景。 但是，覆盖多播这种依靠端系统来提供多播通信的新型服务模式，也会带来一些新的问 题有待进一步解决，主要包括如下： ( 1 ) 数据传输路由的性能问题 翠尸翼尸 萨形飞昏 泸衫、 ( ) 墙系统 口略由器 物理链路 多播路由 (a)ip多播(b)覆盖多播 图1 3 碑多播和覆盖多播路由比较示意图 由于覆盖多播网络是在下层球网络之上构建的虚拟的、逻辑的网络，这就可能在妒层 形成重复分组和重复路径，从而增加覆盖多播路由的传输延时和占用带宽。图1 3 给出了m 多播和覆盖多播路由的比较示意图。其中端系统a 为数据源节点，b 、c 、d 为目的节点， 假设所有物理链路的延时相等。从图中可以看出。对于m 多播，每个数据分组在物理链路 上只转发一次，且能沿最短路径到达目的；而对于覆盖多捶，则在物理路径a 1 3 上出现了 重复分组( 增加了带宽占用量) ，在物理路径3 - 2 - b 上形成了重复路径( 增加了d 的接收延 时) 。由此可知，覆盖多播路由的性能通常不及口多播。这问题对于大多数新型应用，特 别是对于延时和带宽敏感的实时多媒体应用，就显得尤为突出。 为了评价覆盖多播路由的质量。通常采用以下性能评价指标【3 9 】； 拉伸( s t r e t c h ) ：也称为相对延时惩罚( r e l a t w ed e l a yp e n a l t y ) 是指从源节点到某个 目的节点之间沿覆盖多播路径的延时与沿网络层单播最短路径的延时之比。例如，图 1 3 中。在m 多播情况下，节点d 的s u e t c h = l ；而在覆盖多播情况下，节点d 的s t r e t c h = 2 s t r e t c h 表征了覆盖多播路由在延时方面的额外付出。对于覆盖多播，通常s t r e t c h 1 压力( s t r e s s ) 是指构成覆盖多播路由的某一网络物理链路上的重复分组数。例如，图 1 3 中，m 多播路由的最大s t r e s s = l ，而覆盖多播路由的最大s u e s s = 2 s t r e s s 表征了覆 盖多播路由在带宽方面的额外付出。对于覆盖多播，通常s t r e s s l ，而m 多播s t r e s s 总是1 。 6 第一章绪论 代价( c o s t ) ：是指覆盖多播路由的嘲络资源使_ j 量，即构成多橘路由的所有物理网络 链路的延时和使h j 带宽( 或s t r e s s ) 的乘积之和。c o s t 表征了覆盖多播路由在延时和带 宽方面综合性能。 ( 2 ) 端系统的动态性问题 在m 多播中，一个端系统节点的退出多播组( 或失效) 并不会影响其他端系统继续接 收多播数据。而在覆盖多播中，一个端系统节点的退出( 或失效) ，就有可能使覆盖多播树 发生分裂。为了使其它节点不至于因一个节点离开多搔组而中断通信，覆盖多播路由必须进 行修复和重构。因此，端系统的动态性对覆盖多播路由的影响较大。而且，这一问题将由于 端系统的稳定性远低于路由器而变得更加显著。 ( 3 ) 系统环境的异构性问题 随着互联网技术和应用的发展，网络环境异构性日益显著。在覆盖多播中，异构性主要 表现在以下方面：首先是物理网络的异构性，如：不同的网络带宽、非对称的网络链路延时 等；其次是端系统的异构性。包括：端系统的处理能力、输入偷出带宽等的不同等；最后， 应用的q o s 需求也存在着很大的差异。这些异构性将大大增加覆盖多播路由控制的难度。 ( 4 ) 控制开销问题 控制开销是指覆盖多播路由协议和算法为了构造和维护路由所需的空间和时间代价，如 协议的状态维护开销、算法的时间复杂度等。控制开销是覆盖多播路由协议和算法可扩展性 的重要表征之一。在路由性能和控制开销之间进行平衡是覆盖多播路由协议和算法首先要考 虑的关键问题。 由上分析，可以发现覆盖多播面l | 笛的主要问题都与多播路由有密切联系，而多播路由正 是大多数新型多播应用所关心的。因此，如何有效地构造满足应用需求的覆盖多播路由已成 为当前覆盖多播研究的热点之一。在这方面，目前虽己提出了一系列覆盖多播路由协议和算 法( 我们将在第二章对这些协议和算法进行全面的分析和比较) ，但是，仍有许多问题有待 解决本文的研究工作将紧密围绕这一方向展开。 1 2 论文研究目标及内容 本论文主要针对覆盖多播的路由进行研究，其目标是提出满足应用q o s 需求的，具有 良好可扩展性的，适应动态、异构环境的高性能覆盖多播路由协议和算法，为覆盖多播技术 的研究和应用提供新的、更为有效和可用的解决方案。 7 东南大学博i 学位论文 由于覆盖多播所面临的问题非常复杂，为了实现研究目标，我们必须从统一的体系构架 出发，对所研究的问题域进行全面的认识和分析，从中找到关键的研究切入点。在此基础上， 分别从集中式路由算法和分布式路由协议两方面展开研究。其中，集中式路由算法主要研究 典型覆盖多播路由问题的启发式算法，以发现新的高效优化策略，并为后面的研究提供性能 优化的参考；分布式路由协议的研究将从可扩展性和动态性入手，研究覆盖多播路由协议的 关键机制和优化策略，从而全面实现本论文的研究目标。最后，在以上理论研究的基础上， 我们还研究并实现了相应的覆盖多播网络应用原型系统。本论文的主要内容包括四个方面： ( 1 ) 覆盖多播网络模型的研究 目前覆盖多播路由的研究还缺乏统一的网络模型，这对系统地分析和解决相关研究中问 题不利。本论文借鉴口多播网络模型研究的已有成果，同时充分考虑端系统和下层网络的 特点，研究适应异构网络环境的、通用的覆盖多播网络模型。该模型能为覆盖多播路由的研 究提供一个统一的问题描述和分析的理论框架，有助于发现当前覆盖多播路由协议和算法研 究中的问题和不足，为我们今后的研究工作指明新的方向。 ( 2 ) 集中式覆盖多播路由算法的研究 研究表明，覆盖多播中的路由优化问题大多具有“n p 完全”( n p - c o m p l e t e ) 的复杂度。 解决这些优化问题本身就是一件非常困难的任务。虽然存在着状态维护开销大等缺点，集中 式路由算法仍是解决上述问题的擐直接、有效的手段之一本论文在已有的集中式覆盖多播 路由算法( 如紧凑树算法等) 的基础之上，通过采用新的启发式优化策略，研究并提出性能 更好的路由算法。进一步，我们考虑到端系统对媒体流带宽需求的异构性，研究并提出了在 异构环境下的覆盖多播路由算法。 ( 3 ) 分布式覆盖多播路由协议的研究 为了提高覆盖多播路由算法的可扩展性和动态适应能力，本论文继续开展分布式覆盖多 播路由协议的研究。在研究中，我们采用每个端系