（计算机应用技术专业论文）基于qos的多播路由技术的研究.pdf

白糸i l t l ；i u ，、帧im 究乍学付论文 摘要 摘要 随着i n t e m e t 和通信技术的发展，通信网络带宽和处理能力得以提高，使得网络能提 供更多的多媒体业务，其中许多业务都要求网络具有多播能力，例如音频视频会议、交互 式仿真、多人游戏、分布式数据库等。在网络通信中，若对每个信宿单独发送数据包，则 将会造成网络资源的浪费，增加节点的处理负担，严重时会加剧网络的拥塞。多播通信技 术将同样的数据从一个源节点同时传输给大量的目的节点，从而大大节省了网络带宽，减 少了数据冗余，在一定程度上解决了多媒体通信中的带宽瓶颈问题，将成为未来的一项重 要应用技术。 多播通信技术的核心问题是多播路由选择问题，也就是如何构造一棵从源到所有目的 节点的最小代价连接树，而这棵多播树由多播路由算法决定。目前用于解决q o s 多播路由 的算法有很多种，本文研究了现有的静态和动态时延约束的多播路由算法，分析了其中的 典型算法，比较其复杂度，并指出其优缺点。在对已有算法分析的基础上，本文借鉴了贪 婪算法的思想，结合f l s p t 最短路径算法，分别提出了适合静态和动态时延约束的启发式 多播路由算法，并通过仿真实验与已有的算法进行比较，验证了有效性，表明本文提出的 算法具有较好的性能。 关键词：静态，动态，q o s ，时延约束，多播路由算法 南康妣l l ! 人掌颀j 生学位论文a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e r n e ta n dc o m m u n i c a t i o n s ，t h eb a n d w i d t ha n dt h ea b i l i t yo f n e t w o r kh a v eb e e ni m p r o v e d av a r i e t yo fm u l t i m e d i aa p p l i c a t i o n sc o m ei n t oe x i s t e n c e t h e m o s to fm u l t i m e d i aa p p l i c a t i o n sn e e dt h en e t w o r kt os u p p o r tm u l t i c a s t s u c h 弱a u d i o v i d e o c o n f e r e n c e ，i n t e r a c t i v es i m u l a t i o n ，o n l i n eg a m e s ，d i s t r i b u t e dd a t a b a s ee t c i nt h e c o m m u n i c a t i o n s ，i fas o u r c es e n d sp a c k e t st oe v e r yd e s t i n a t i o ns e p a r a t e l y ，i tw i l lw a s t eam a s so f n e t w o r kr e s o u r c e s ，i n c r e a s et h en o d eb u r d e n ，a n de v e n 妊n gt h en e t w o r kc o n g e s t i o n t h e m u l t i c a s tt e c h n i q u ec a ns e n dt h es a m ed a t at ot h ed i f f e r e n td e s t i n a t i o nn o d es i m u l t a n e o u s l yf r o m o n es o u r c en o d e i tc a ns a v et h eb a n d w i d t ha n dr e d u c ed a t ar e d u n d a n c yi nt h en e t w o r k s oi t s o l v e st h ep r o b l e mo fb a n d w i d t hb o t t l e n e c k si nt h em u l t i m e d i ac o m m u n i c a t i o n s t h em u l t i c a s t t e c h n i q u ew i l lb e c o m ea ni m p o r t a n ta p p l i c a t i o ni nt h ef u t u r e t h ek e yi s s u eo fm u l t i c a s tc o m m u n i c a t i o n si sam u l t i c a s tr o u t i n gp r o b l e m ，i e h o wt o c o n s t r u c tt h el e a s tc o s tt r e ef r o mt h es o u r c en o d et oa l ld e s t i n a t i o nn o d e s 1 1 1 em u l t i c a s tt r e ei s d e t e r m i n e db yt h em u l t i c a s ta l g o r i t h m a tp r e s e n tt h e r ea r em a n yd i f f e r e n ta l g o r i t h m st os o l v e t h eq o so ft h em u l t i c a s tm u t i n g t h i sp a p e rs t u d i e st h es t a t i ca n dd y n a m i cd e l a y c o n s t r a i n e d a l g o r i t h m s ，a n a l y z e st h et y p i c a lr e l a t e da l g o r i t h m s ，c o m p a r e st h e i rc o m p l e x i t y , a n dp o i n t so u t t h e i ra d v a n t a g e sa n dd i s a d v a n t a g e s u s i n gt h ei d e ao f g r e e d ya l g o r i t h ma n df l s p ta l g o r i t h mf o r r e f e r e n c e ，t h i sp a p e rp r o p o s e st h ed e l a y c o n s t r a i n e dh e u r i s t i c r o u t i n ga l g o r i t l m lf o rs t a t i c m u l t i c a s ta n dd y n a m i cm u l t i c a s tr e s p e c t i v e l y b yt h es i m u l a t i o nt e s ta n dt h ec o m p a r i s o n , t h e v a l i d i t yo ft h ed e l a y - c o n s t r a i n e dh e u r i s t i cr o u t i n ga l g o r i t h mh a sb e e nv a l i d a t e d t h er e s u l ts h o w s t h a tt h ei m p r o v e da l g o r i t h mh a st h eg o o dp e r f o r m a n c e k e y w o r d s ：s t a t i c ，d y n a m i c ，q o s ，d e l a y - c o n s t r a i n e d ，m u l t i c a s tr o u t i n ga l g o r i t h m i i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：蜂日期：2 业参 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：夺江蛑 导师签名： 研究生签名：孕江- 烽 导师签名： 南京邮l l ! 人学颧i 研究生学位论文 第一章绪论 第一章绪论 1 1 课题的研究背景 随着i n t e r n e t 规模的不断增大，各种各样的网络服务争相涌现，先进的多媒体系统层出 不穷在高性能网络上传输实时多媒体业务的需求只益高涨。由于实时业务对网络的传输 时延、时延抖动等特性比较敏感，当网络上有突发性高的f t p 或含有图象文件的h t t p 等业 务时，实时业务就会受到很大的影响：另一方面，多媒体业务占去了大量的带宽，这样， 现仃的网络要保证的关键业务就难以得到可靠的传输。解决这些问题的最简单办法就是增 j j l | 惜宽。但是由于代价高昂，所以并不是十分可行的。于是各种服务质量( q u a l i t yo f s e r v i c e ， q o s ) 技术应运而生，它们通过对数据包进行排队，对某些特定的数据包赋予较高的优先 级等方式，来满足各种业务的q o s 需求。在网络中，采用单播方式将相同的数据包发送给 网络中的多个而不是全部接受者时，由于需要复制分组给每一个接受端点，随着接收者数 量的增多，需要发出的数据包数量也会线性增加，这使得发送主机、路由设备及带宽资源 总体负担会很重，效率受到极大影响。随着多点电视会议、群组通信应用等需求的增长， 为提高资源利用率，多播方式日益成为多点通信中普遍采用的传输方式，多播业务对服务 质量的要求也随着应用的发展而越来越明显，支持q o s 的多播路由成为当今研究的一个热 点。 1 2 研究现状 q o s 多播路由就是为多播应用寻找满足各种约束条件的传输路径。其中有两个基本问 题：最优化问题和性能界约束问题。最优化问题是寻找对应于q o s 度量的最优路径，而性 能界约束问题则是寻找大于q o s 度量或小于q o s 度量的路径，即在满足性能界要求的集合 中选择一个解。根据这两个基本问题，q o s 约束可分为时延约束、时延抖动约束、带宽约 束、代价约束等等。 文献【1 】证明同时对两个以上相对独立的参数进行要求限制时，这个问题就是n p 完全问 题，基于多个不相关可加性度量的q o s 多播路由问题是也n p 完全问题。解决n p 完全i 口- j 题有 两种方法：一是求出具有指数复杂度的精确解，二是抓住某个或者某些主要矛盾，通过启 发式算法找出次优解。启发式算法的兴起与计算复杂性理论的形成有着密切的联系，当人 们不满足常规算法求解复杂问题时，现代优化算法开始体现其作用，这些算法主要是解决 优化问题中的难解l 口- j e ，由于这些算法在求解时不依赖于梯度信息，因而特别适用于传统 1 南京龆也人学碳 j 研究生学位论文 第一苹绪论 方法解决不了的大规模复杂问题，很适合解决具有n p 一完全的问题。目前，启发式算法求 解路由的策略一般有源路由、分布式路由和分层路由三种形式。 在基于q o s 的多播路由协议方面，人们在2 0 世纪8 0 年代后期就已提出并开发了多播开 放最短路径优先协议“m o s p f ”、距离向量多播路由协议“d v m r p 和独立多播密集模 式协议“p i m d m ”，它们是己形成多播主干网的重要基础。2 0 世纪9 0 年代初，美国的一 些大学、研究所和公司在i n t e m e t 之上构架了实验性的多播主干网，但对q o s 约束的支持仍 很弱。近来有不少学者做了一定的研究和探索工作，c a r l b e r g 和c r o w c r o f t 提出了y a m 协议 1 3 5 】。不需要全局状态信息并且支持节点的动态加入和离开，但是它仍采用洪泛法来寻找新 成员到多播树的合适路径，因此它的控制消息的代价很大。m f a l o u t s o s ，a b a n e r j e a 和 r p a n k a j 对y a m 协议进行了改进，提出了一种q o s m i c 协议【3 6 1 ，q o s m i c 可在资源预留并在 共享树的基础上按需切换到有q o s 竞争的有源树上，具有较好的可扩展性，但由于它仍属 p i m s m 和c 1 3 t 的变种，因此也存在稀疏型协议固有的缺陷。与一般单播q o s 路由或无q o s 约束的多播路由相比，基于q o s 的多播路由的研究目前在国内外仍处于初步阶段，而且这 方面的研究也大都集中在网络拓扑参数信息是确定的网络环境范围内，对于非确定参数网 络基于q o s 的多播路由协议的设计理论及方法的研究则更少。 基于q o s 的多播路由算法方面，d i j k s t r a 提出了一种基于最短路径树的方法，其基本思 想是从源节点到各目的节点分别计算各自最短路径，并将其组成为以源节点为根的树，该 方法并不能保证所生成的树的总成本最低。还有一些通过在源节点的计算来寻找一个受限 制的s t e i n e r 树的算法，如b s m a 算法【1 6 】，k p p 算法【1 引和d v m a t 2 7 1 算法等等，它们需要网络 中的每个节点都保存全局的网络状态信息以及q o s 参数信息，当网络和多播组很大时算法 的代价很大，并且不适于组成员的动态加入和离开。 在基于q o s 的层次多播路由方面，随着i n t e m e t 规模的迅速扩大，支持q o s 的多播源路 由和分命式路由都面临复杂性过高的问题，因此支持q o s 的层次路由的研究成为新的热点。 层次路由的基本思想是在对网络迸行层次划分后。同层次内部扩散网络原始信息，而层次 之间扩散聚集后的网络信息，从而显著减少路由器维护和交换的信息，解决大规模网络所 带来的可扩展性问题。支持q o s 的层次路由需要解决的问题包括如何根据路由算法的需要 聚集网络信息，如何使得基于该信息与基于平面详细的网络信息进行路由的效率具有可比 性，聚集的信息作为路由算法的输入，简单有效地反映低层网络的特性是非常关键的。许 多学者己在层次多播路由方面做了一些工作，最著名的是m u r t h y 和g a r c i al u n aa c e v e s 的层 次距离向量路由算法。它提供运行在层次上利1 羽d i j k s t r a 最短路径算法的分布式实现： b e h r e n s 平 1 g a r c i at u n aa c e v e 的a l v a 算法，路由器只传播它们实际用来到达任何目的地的 2 南京燃l 也人掌坎 坝究生学位论义 第一章绪论 那些链路的增量信息，所有路由器只维护部分拓扑，然后利用最短路径算法计算是基于部 分拓扑的多播树。 现代优化算法自2 0 世纪8 0 年代初兴起，至今发展迅猛，它包括禁忌搜索( t a b us e a r c h ) ， 模拟退火( s i m u l a t e da n n e a l i n g ) ，遗传算法( g e n e t i ca l g o r i t h m s ) ，神经网络( n e u r a ln e t w o r k ) ， 拉格朗n 松弛算法和蚁群算法。这些算法涉及生物进化、人工智能、数学和物理科学、神 经系统和统计力学等概念，都是以一定的直观基础构造的算法。 尽管目日订已径提出了许多播路由算法和协议，但是现有的算法和协议在目标和机制上 存在很大差异。由于多播路由表现为一个非常动念化的问题，如何设计一个有效的算法以 适应这种动态性仍然有待探索。因此研究高效率、高质量的q o s 多播路由算法和协议，仍 是目前国际上研究的热点和难点之一。 本文在分析已有的多播路由算法的基础上，提出了关于时延和代价约束的启发式算 法，并且通过仿真实验，与己经存在的算法迸行比较，得出了本文提出的算法有更好性能 的结论。 1 3 本文的主要内容 第一章介绍了课题研究的背景，分析了目前的研究现状，说明了本文的主要内容与 组织结构。 第二章介绍了多播通信的工作原理和多播通信的具体实现方式，讨论了两类常用的 多播路由协议。 第三章叙述t q o s 多播路由问题及算法，介绍q o s 的分类和控制模型，着重分析t q o s 多播路由问题，论述了s t e i n e r 树问题及相关的算法。 第四章基于时延和代价约束的s t e i n e r 树，并结合f l s p t 算法，提出了一种满足时延 约束的低代价静态路由启发式算法并进行了仿真实验，表明该算法具有较低时间复杂度 儿树费用适中。 第五章结合贪婪法的思想和f l s p t 算法，提出一种满足时延约束最小代价的动态路 出算法，并进行了仿真实验，表明本文提出的算法可以很好的满足端到端时延约束且成员 数目经常变化的多播应用。 第六章对本文的工作进行总结，并展望进步的研究工作。 南 剐纷乜，、掌豫i j 训究生学位论文 第二章多播路由的理论基础 第二章多播路由的理论基础 2 1 多播路由技术 随着网络技术和通信技术的发展，因特网上的用户数量持续增长，许多新型的通信业 务大量涌现，如电视会议、视频点播、邮件群发、网络游戏、远程教学等。这类业务一般 涉及到多个用户，并且对带宽等网络资源的消耗极大。多播通信是指多个参与者之间的通 价，它的特征足源节点发送信息，多个接收者接受。多播作为优化带宽的一种重要手段而 受到越来越多的关注。 i p 多播是指一个i p 报文向一个“主机组 的传送，这个包含零个或多个主机的主机 组使用一个单独的i p 地址标识。主机组地址也称为多播地址或称为d 类地址。主机组的 成员可以动念变化，主机有权选择加入或者退出某个主机组。主机可以加入多个主机组， 也可以向自己没有加入的主机组发送数据。主机组有永久组和临时组两种。永久组的i p 地址是固定的，由i n t e m e t 管理机构分配，是保留地址。临时组的地址则使用除永久组地 址外的非保留d 类地址。除了目的地址部分，多播报文与普通报文没有区别，网络尽力传 送多播报文，但是并不保证一定送达。网络上传输多播数据报时是通过多播路由器进行的， 多播路由器可以和网关一起，也可以和网关分离。主机在传输i p 多播数据报时将它作为本 地网络多播迸行。本地网络多播向直接相邻的主机传送数据报。如果数据报的i p 生存期大 于l ，多播路由器负责转发此数据报到组内的其他成员所在的网络。在i p 生存期内能够达 到的网络上，相应的多播路由器进行本地多播完成全部的多播过程。 2 1 1 i p 多播地址和多播组 多播通信依赖于i p 多播地址，在i p v 4 中它是一个d 类i p 地址，范围从 2 2 4 0 0 0 2 3 9 2 5 5 2 5 5 2 5 5 ，并被划分为局部链接多播地址、预留多播地址和管理权限多播 地址三类。其中，局部链接多播地址范围在2 2 4 0 0 0 2 2 4 0 0 2 5 5 ，这是为路由协议和其它 用途保留的地址，路由器并不转发属于此范围的i p 包；预留多播地址为2 2 4 0 1 o 2 3 8 2 5 5 2 5 5 2 5 5 。可用于全球范围( 如i n t e r n e t ) 或网络协议；管理权限多播地址为2 3 9 0 0 0 - 2 3 9 2 5 5 2 5 5 2 5 5 ，可供组织内部使用，类似于私有i p 地址，不能用于i n t e m e t ，可限制多播 范围。整个i p 多播地址的空间划分如图2 1 所示。 4 南康衄l l ! ，i 擎颀i j 研究生学位论文第二章多播路由的理论基础 2 3 9 2 5 5 2 5 5 2 2 3 9 0 0 0 图2 1 多播地址划分 i a n a 将m a c 地址范围0 1 ：0 0 ：5 e ：0 0 ：0 0 ：0 0 - 0 1 ：0 0 ：5 e ：7 f ：f f ：f f 分配给多播使用，这样要 求将2 8 位的i p 多播地址空间映射到2 3 位的m a c 地址空间中。i p 多播地址映射为相应的以太 网多播地址，只需将i p 多播地址的低位2 3 比特放到特殊的以太网多播地址0 1 0 0 。5 e 0 0 。o o 0 0 的低位2 3 比特上，如图2 ，2 所示。例如，i p 多播地址2 2 4 0 0 2 则称为以太网多播地址 01 0 0 5 e 0 0 0 0 0 2 。 3 2 位i p 地址 4 8 位m a c 地址 曰巨习曰目日国 图2 2 多播地址到m a c 地址的映射 使用同一个i p 多播地址接收多播数据包的所有主机构成了一个多播组。一个多播组的 成员是随时变动的，一台主机节点可以随时加入或离开多播组，多播组成员的数目和所在 的地理位置也不受限制，一台主机也可以属于几个多播组。此外，不属于某一个多播组的 主机也町以向该多播组发送数据包。 下llfill上 钤 d 2 l 5 0 毯 圳 钌 2 283z 下上 5 ) 掰 咖 n o o 饵 川 挖 l 自一】：i i i i ；i l 学m “学位论女第= 章多捂路由的理论摹础 2 l2 多播路由的优点 一般院柬，有三种不同通信方式可以实现网络信息的传输口】； ( 1 ) 单播( u n i c a s t ) 传输：在发送者和每一个接收者之间需要单独的数据信道。如 果一台主机同时给很少量的接收者传输数据一般没有什么问题。但是如果有大量的主机 希望获得数据包的同一份拷贝时却很难实现，因为这将导致发送者负担沉重、时延增加以 及造成网络捌塞，而且为了保证一定的服务质量还需要增加硬件和带宽。 ( 2 ) 广播( b r o a d c a s t ) 传输是指在整个i p 子网内广播数据包所有在于网内部的 帅【部将收到这些数据包。广播意味着网络子网向主机都投递一份数据包，不管主机是否 愿意接受。然而广播使用范围非常小，只在本地子网内有效，因为路由器会封锁广播通信， 同时广播传输会增加非接收者的开销。 ( 3 ) 多播( m u l t i c a s t ) 传输：是指一个发送者向多个接收者发送一个数据包。接收者 和发送者构成一个多播组将发送者称为多播源，每个接收者称为多播组成员。多播源向 多播组发送数据包，只有属于该多播组的成员才能接受到组内数据包。无论网络规模有多 大l l 多播方式发送的数据包在同一网络链路上都具有唯一性。 图2 3 单檑、广播和多播的区别 通过三种通信方式的比较可知，如果采用多播传输方式，即使用户数量成倍增加，主 干网的带宽也不需要随之增加。这也使得支持“点到多点”或者“多点到多点”的通信方 式成为网络支持多媒体的必要方式，即一个或多个发送者( 源节点) 将数据发送到多个接 6 南京螂电人学硬i 二研究生学位论文 第二章多搔路由的理论基础 收者( 目的节点) 。这样节省了网络带宽，提高了数据传输效率，减少了主干网络发生拥 塞的可能性。 2 1 3 多播通信的实现方案 在单播模型中，数据包通过网络沿着单一路径从源主机向目标主机传递，但是在多播 模型中，多播源向某一组地址传递数据包。而这一地址却代表一个主机组。为了向所有的 接收者传输数据，一般采用多播分柿树描述i p 多播在网络里经过的路径。 多播分柿树有四种基本类型：泛洪法、有源树、核心基干树和s t e i n e r 树。 ( 1 泛洪法( f l o o d i n g ) 这是最简单的向前传送多播路由算法，并不构成所谓的分布树。基本原理是：当多播 路由收到发往某个多播地址的数据包后，首先判断是否是首次收到该数据包，如果是首次 收到，那么将其转发到所有接口上，以确保其最终到达所有接收者；如果不是首次收到， 则抛弃该数据包。 泛洪法的实现关键是“首次收到”的检测。这需要维护一个最近通过的数据包列表， 但无需维护路由表。它适合于对多播需求比较高的场合，并且能做到即使传输出现错误， 只要还存在一条到接收者的链路则所有接收者都能接受到多播数据包。然而，泛洪法不适 合于i n t e m e t ，因为它不考虑链路状态，并产生大量的拷贝数据包。此外，对于高速网络而 言，“首次收到”列表将会很长，占用相当大的存储空间。尽管它能保证不对相同的数据 包进行二次比较，但不能保证对相同数据包只接受一次。 ( 2 ) 有源树 有源树也称为基于信源的树或者最短路径树。它是以多播源为根到所有接收者路径都 最短的分布树。如果组中有多个多播源，则必须为每个多播源构造一颗多播树。由于不同 多播源发出的数据包被分散到各自分离的多播树上，因此采用最短路径树( s h o r t e s tp a t h t r e e ，s p t ) 有利于网路中数据流量的均衡。同时。因为从多播源到每个接收者的路径最短， 所以端到端的时延性能最好，有利于流量大、时延性能要求较高的实时多媒体应用。s p t 的缺点是：要为多播源构造各自的分布树，相对于数据流量不大时，构造s p t 的开销相对 显得较大。 ( 3 ) 共享树 共享树也称为r p 树( r e n d e z v o u sp o i n tt r e e ，r o t ) ，是指每个多播选定一个公用根( 核 心或汇合点r o ) ，以r p 为根来建立多播树。同一多播组的多播源将所要多播的数据单播 到r p ，再有r p 向其他成员转发。目前，讨论最多同时也是最具代表性的两种共享树时 7 南京雌l 【! 人学坝| f 坍究生学位论文 第二章多播路由的理论基础 s t e i n e r 树和核心基干树c b t ( c o r eb a s e dt r e e ) 3 , 4 1 。 共享树在路山器所需存储的状态信息数量和路由树的总代价两个方面具有较好的性 能。当多播组的规模较大，而每个成员的数据发送效率较低时，使用共享树就比较合适。 但当通信量大时，使用共享树将导致流量集中在根的附近而形成瓶颈。 2 2i p 多播路由协议 根据网络中多播组成员的分布，i p 多播路由协议可以分为以下两种基本类型，即密集 模式多播路出协议和稀疏模式多播路由协议【5 ，6 ，7 1 。 图2 4i p 多播路由协议的基本类型 第一种假设多播组成员密集地分布在网络中，也就是说，网络中大多数的子网都至少 包含一个多播组成员，而且网络带宽足够大，这种被称作“密集模式 ( d e n s e m o d e ) 的 多播路由协议依赖于广播技术来将数据“推 向网络中所有的路由器。密集模式路由协议 包括距离向量多播路由协议( d i s t a n c ev e c t o rm u l t i c a s tr o u t i n gp r o t o c o l ，d v m r p ) 、多播 丌放最短路径优先协议( m u l t i c a s to p e ns h o r t e s tp a t hf i r s t ，m o s p f ) 和密集模式独立多播 协议( p r o t o c 0 1 i n d e p e n d e n tm u l t i c a s t d e n s em o d e ，p i m d m ) 等。 南京黼f 【! 入学颀i j f 究生学位论文 第二章多播路由的理论基础 多播路山协议的第二种类型假设多播组成员在网络中是稀疏分散的，并且网络不能提 供足够的传输带宽，立1 i n t e m e t 上通过i s d n 线路连接分散在许多不同地区的大量用户。在这 种情况下，广播就会浪费许多不必要的网络带宽，从而可能导致严重的网络性能问题。于 是稀疏模式多播路由协议必须依赖于具有路由选择能力的技术来建立和维持多播树。稀疏 模式主要有基于核心树的多播协议c b t 和稀疏模式独立多播协议( p r o t o c 0 1 i n d e p e n d e n t m u l t i c a s t s p a r s em o d e ，p i m s m ) 。图2 4 给出了多播协议的基本类型。 2 2 1 密集模式多播路由协议 ( 1 ) 距离向量多播路由协议( d v m r p ) 第一个支持多播功能的路由协议是距离向量多播路由协议。它已经被广泛地应用在多 播骨干网m b o n e 上。d v m r p 为每个发送源和目的主机组构建不同的多播树。每个多播树 都是一个以多播发送源为根，以多播接受目的主机为叶的最小扩展多播树。这个多播树为 发送源和组中每个多播接收者之间提供了一个以“跳数”为单位的最短路径。当发送源要向 多播组中成员发送消息时，多播树就根据这个请求而建立，并且使用“广播和修剪 的技 术来维持这个扩展多播树。 在这样的多播树中发送多播包的具体过程是：当一个路由器接收到一个多播包，它先 检查它的单播路由表来查找到多播组发送源的最短路径的接口，如果这个接口就是多播包 到达的接口，那么路由器就将这个多播组信息记录到它的内部路由表( 指明该组数据包应 该发送的接口) ，并且将这个多播包向除了接受到该数据包的路由器以外的其他临近路由 器继续发送。如果这个多播包到达的接口不是该路由器到发送源的最短路径的接口，那么 这个包就被丢弃。这种机制被称为“反向路径广播 ( r e v e r s e p a t hb r o a d c a s t i n g ) 机制。 对子网中密集分布的多播组来说d v m r p 能够很好的运作，但是对于在范围比较大的区域 上分散分布的多播组来说，周期性的广播行为会导致严重的性能问题。d v m r p 不能支持 大型网络中稀疏分散的多播组。 ( 2 ) 多播开放最短路径优先( m o s p f ) o s p f 是一个单播路由协议，它将数据包在最小费用路径上传送。除了路径中的跳数 以外。其他能够影响路径丌销的网络性能参数还有负载平衡信息、应用程序需要的q o s 等。 m o s p f 是为单播路由多播使用设计的，并依赖o s p f 作为单播路由协议。在一个 o s p f m o s p f 网络中每个路由器都维持一个最新的全网络拓扑结构图。这个“链路状态” 9 南京跳也人学璐il 研究生学位论文 第二章多播路由的理论基础 信息被用来构建多播树。 每个m o s p f 路由器都通过i g m p 协议周期性的收集多播组成员关系信息。这些信息和 链路状念信息被发送到其路由域中的所有其他路由器。路由器将根据它们从临近路由器接 t 1 2i j f | ，j 这些信息更新他们的内部连接状念信息。由于每个路由器都记录着整个网络的拓扑 结构，就能够独立地计算出一个最小丌销扩展树，将多播发送源和多播组成员分别作为树 的根和叶。 ( 3 ) 独立多播密集模式协议( p i m d m ) 独立多播协议( p i m ) 是一种标准的多播路由协议，并能够在i n t e m e t 上提供可扩展的 域间多播路由而不依赖于任何单播协议。p i m 有两种运行模式，一种是密集分布多播组模 式，另一个是稀疏分布多播组模式。前者被称为独立多播密集模式协议( p i m d m ) ，后 者被称为独立多播稀疏模式协议( p i m s m ) 。 p i m d m 类似于d v m r p ，这两个协议都使用了反向路径多播机制来构建多播树。主 要不同在于p i m 完全不依赖于网络中的单播路由协议，而d v m r p 依赖于某个相关的单播路 由协议机制，且p i m d m 比d v m r p 简单。 p i m d m 协议和所有的密集模式路由协议一样也是数据驱动的。但是既然p i m d m 不 依赖于任何单播路由协议，路由器某个接收端口接收到的多播数据包被发送到所有下行接 口直到不需要的分枝从树中被修剪掉。d v m r p 在多播树构建阶段能够使用单播协议提供 的拓扑数据有选择性的向下行发送数据包，p i m d m 则更加倾向于简单性和独立性，甚至 不惜增加数据包复制引起的额外歼销。 2 2 2 稀疏模式多播路由协议 当多播组在网络中集中分布或者网络提供足够大带宽的情况下，密集模式多播路由协 议是一个有效的方法，当多播组成员在广泛区域内稀疏分布时，就需要另一种稀疏模式多 播路由协议将多播流量控制在连接到多播组成员的链路路径上，而不会“泄漏”到不相关 的链路路径上，这样既保证了数据传输的安全，又能够有效地控制网络中的总流量和路由 器的负载。 ( 1 ) 核心树的多播协议( c b t ) c b t 与d v m r p 和m o s p f 为每个( 发送源、目的组) 对构建最短路径树不同的是，c b t l o 南京邮 【! 人学颀i ： i j f 究生学位论文 第二牵多撩路由的理论罨础 协议只构造一个树给多播组中所有成员共享，这个树也就被称为共享树。整个多播组的通 信量都在这个共享树上进行收发而不论发送源有多少或者在什么位置。这种共享树的使用 能够极大的减少路由器中的多播状态信息。 c b t 共享树是以一个核心路由器来构建树的。要加入的路由器发送加入请求给这个核 心路由器。核心路由器接收到加入请求后，沿反向路径返回一个确认，这样就构成了树的 一个分枝。加入请求数据包在被确认之前不需要一直被传送到核心路由器。如果加入请求 包n 渤达核心路i 妇器之前先到达树上的某个路由器，该路由器就接收下这个请求包而不继 续向前发送并确认这个请求包。发送请求的路由器就连接到共享树上了。c b t 将多播流量 集中在最少数量的链路而不是在一个基于发送源的共享树上。集中在核心路由器上的流量 可能会引起多播路由的瓶颈等问题。某些版本的c b t 支持多个多播核心的使用，和单个多 播核心相比，多核心更能达到负载平衡。 ( 2 ) 多播稀疏模式协议( p i m s m ) p i m s m 与c b t 相似，p i m s m 被设计成将多播限制在需要收发的路由器上，围绕一 个被称为集中点( r e n d e z v o u sp o i n t ，r p ) 的路由器构建多播分布树。这个集中点扮演着和 c b t 核心路由器相同的角色，接收者在集中点能查找到新的发送源。但是p i m s m 比c b t 更灵活，c b t 通常是多播组共享树，p i m s m 中的独立接收者可以选择是构建组共享树还 是最短路径树。 p i m s m 协议最初先为多播构建一个组共享树。这个树由连接到集中点的发送者和接 收者共同构建，如同c b t 协议围绕着核心路由器构建的共享树一样。在共享树建立以后， 一个接受者( 实际上是最接近这个接收者的路由器) 可以选择通过最短路径树改变到发送 源的连接。这个操作的过程是通过向发送源发送一个p i m 力h 入请求完成的。一旦从发送源 到接收者的最短路径建立了，通过r p 的外部分枝就被修剪掉了。 2 3 本章小结 本章首先介绍了多播的工作原理，并通过和单播、广播进行比较，说明了多播的优点， 还简要的讨论了多播通信的实现方案。同时还对现有的密集模式多播路由协议和稀疏模式 多播路由协议的性能进行了分析，指出了各个协议的优点和存在的不足。 渤啪k ，也入掌坝 j j 究生学位论文第三章q o s 多播路由及算法 第三章q o s 多播路由及算法 3 1q o s 概述 一般来说，基于存储转发机制的i n t e m e t 只为用户提供了“尽力而为 ( b e s t e f f o r t ) 的服务，不能保证数据包传输的实时性、完整性以及到达的顺序性，不能保证服务的质量， 所以主要应用在文件传送和电子邮件服务。随着i n t e m e t 的飞速发展，人们对于在i n t e m e t 上传输分布式多媒体应用的需求越来越大，用户对不同的分布式多媒体应用有着不同的服 务质量要求，这就要求网络能根据用户的要求分配和调度资源。因此传统的“尽力而为一 转发机制已经不能满足用户的要求。为此，i n t e r n e t 工程任务组( i n t e m e te n g i n e e r i n gt a s k f o r c e ，i e t f ) 也成立了专门的工作小组来研究多媒体服务质量的定义和相关标准p j 。 服务质量( q u a l i t yo f s e r v i c e ，q o s ) 是一种抽象概念，用于说明网络服务的“良好 程度。在r f c 2 3 8 6 中给出了服务质量的定义：服务质量是“网络在传输数据流时必须满足 的一系列服务需求”。这里，数据流指的是“从源地址到目的地址以一定的服务质量进行 传输( 单播和多播) 的数据流”。由于不同的应用对网络性能的要求不同，对网络所提供 的服务质量的期望值也不同。这种期望值可以用一种统一的q o s 概念来描述。在不同应用 系统中，q o s 参数集的定义方法可能是不同的，通常使用吞吐量、差错率、端到端延时、 延时抖动等网络性能参数来定义q o s 。如对连续媒体传输来说，端到端延时和延时抖动是 两个比较关键的性能参数。在多媒体应用，特别是交互式多媒体通信应用中，对延迟又有 严格的限制，不能超过人所能忍受的极限，否则将会严重地影响服务质量。同样，延时抖 动也必须维持在严格的界限内，否则将会严重地影响人对语音和图像信息的识别。 在早期的计算机网络及分组交换网络中，网络一般只为业务提供“尽力而为 的服务， 在这样的网络系统中，所有业务共享并抢占网络资源，业务之间并没有明确的区分，随着 技术的发展，人们发现单一的服务类型并不能满足未来业务的发展需要，于是提出了服务 质量的概念，其出发点是使网络区分对待有不同要求的业务。i e t f 及许多网络设备厂商提 出了多种解决方案，l p 网络中的各种q o s 技术便应运而生。 3 1 1q o s 的分类 服务质量q o s 最早出现于通信领域，用来描述数据传输链路的速率、可靠性等技术特 性。丌始它只应用于网络底层协议，对上层应用而言是透明的，这对于早期的时间要求不 1 2 南京燃l 也久掌硕 f j f 究生学位论文第三章q o s 多播路由及算法 强的应用而言是可以接受的。通常来说，q o s 可以根据不同的分类标准分为以下两类。 ( 1 ) 从q o s 的严格程度来分类 a ) 确定型( d e t e r m i n i s t i c ) q o s 承诺 在通信过程中，提供q o s 的“硬”保证，确保通信各方保证协商好的各q o s 参数值， 不允许有任何违背，否则可能会造成严重后果。这类服务一般用于硬实时应用。例如，远 程医疗诊断这样的分布式多媒体应用，就需要这类服务来支持诸如患者的x 射线影像数据 的实时无差错传送。 b ) 统计型( s t a t i s t i c a l ) q o s 承诺 在通信过程中，提供q o s 的“软保证，允许对通信各方对协商好的各q o s 参数值可 以有一定比例的违约，适合于软实时应用。例如，对于分布式多媒体信息点播服务中的影 片点播来说，用户通常可以容忍一定数量的比特错和帧丢失。 c ) 尽全力型( b e s t e f f o r t ) q o s 承诺 与数据报服务同义，不提供任何q o s 保证。目前由于带宽的限制，广域网( 如i n t e r n e t ) 中的分布式多媒体服务就属于这类服务。 ( 2 ) 从服务质量的实现层次来分类 通常，不同的应用对q o s 的要求是不同的，不同的q o s 应当通过不同的q o s 参数来描述， 并且用户能够应用这些q o s 参数来定量或定性地说明各自所需的q o s 。在一个多媒体通信 系统中，通常采用层次化的q o s 参数体系结构来定义说明q o s 参数，整个i n t e m e t 从实现服 务的角度可分成四个主要层面： a ) 应用层 应用层q o s 参数是面向端用户的，应当采用直观、形象的表达方式来描述不同的q o s ， 供端用户选择。 b ) 传输层 传输层协议主要提供端到端的、面向连接的数据传输服务。通常，这种面向连接的服 务能够保证数据传输的正确性和顺序性，但以较大的网络带宽和延迟开销为代价。传输层 q o s 参数主要有吞吐量、端到端延迟、端到端延迟抖动、分组差错率和传输优先级等。 c ) 网络层 网络层协议主要提供路由选择和数据报转发服务。通常，这种服务无连接的，通过中 i - 日j 点( 路由器) 的“存储一转发 机制来实现。在数据报转发过程中，路由器将会产生延 迟、延迟抖动、分组丢失及差错等。 d ) 数据链路层 1 3 裔室丝垒叁学竺! 皇! 奎竺兰丝鲨兰 墨三兰旦竺! 至塑壁垒垦蔓鎏 _ - - i _ _ _ i _ - - - - _ _ _ - - _ _ _ - - - _ _ _ _ - _ - i _ - _ - _ - _ _ _ l - _ _ _ - _ _ _ _ _ _ _ _ - _ _ - _ _ - - i - _ _ - _ _ _ i _ i _ _ _ - i _ _ _ _ _ _ _ _ _ - 一一 数据链路层协议主要实现对物理介质的访问控制能力，也就是解决如何利用介质传输 数掘问题，与网络类型密切相关，并不是所有网络