（计算机应用技术专业论文）启发式多约束qos组播路由算法研究.pdf

启发式多约束q o s 组播路由算法研究 摘要 近来i n t e m e t 上有越来越多的q o s 要求的组播应用的涌现，如视频会议、网 络音频视频广播、远程教育、软件更新等，这加速了网络对可扩展的有效的组 播通信方式支持的需要。与单播通信方式比较起来，组播在点到多点的数据传输 方面更有效，在传统的单播通信方式中，源需要向每个接收者单独传送一份数据 的拷贝，一个数据流就有可能占用了不必要的很大一部分的带宽，如果接收者成 千上万，网络拥塞发生的可能性就大大增高。而在组播通信方式中，主干链路上 只有一个数据的拷贝，路由器只在分枝处进行数据包的复制，所以大大节省了带 宽。 实现组播重要的一环是组播路径的确立，与单播传输路径不同的是组播数据 传输的拓扑是一棵组播树，而构建组播树是组播路由的任务，考虑到现在越来越 多的多媒体应用要求有q o s 保证，所以如何构建一棵组播树使其满足相应用户 的q o s 要求成为组播研究领域的一个很大的挑战。许多研究者正致力于q o s 组 播路由算法和协议的研究和设计，q o s 组播路由已经成为近年来的一个热点研究 领域。 在q o s 组播路由中，寻找多约束可行路径问题已经被证明是n p 完全问题。 c m s t 问题使服务路径领域受到越来越多的关注，但是针对多重附加约束的多点 路由却没有得到太多的进展，尽管大量正在形成的应运软件对此提出了需求。在 这篇论文中，我们提出了一种构建组播树的启发式算法，h m c m c 来解决这个问 题。h m c m c 有着低时间复杂度，它的基本思路就是逐步建立一种多点路由，这 需要建立在关于多约束组播路由最新研究的基础上。仿真结果表明，与以往算法 相比，该算法在消息开销、连接成功率和连接建立时间等性能指标方面都有较好 的改善。 关键词：o o s 路由，多约束组播路由，多约束最小s t e i n e r 树，多路径约束 问题 t h er e s e a r c ho nh e u r i s t i cm u l t i c o n s t r a i n e d q o s m u i t i c a s tr o u t i n ga l g o r i t h m a b s t r a c t t h er e c e n tp r o l i f e r a t i o no fq o s a w a r eg r o u pa p p l i c a t i o n so v e rt h ei n t e m e t s u c h a sv i d e oc o n f e r e n c i n g ，n e w sd i s t r i b u t i o n s ，d i s t a n c el e a r n i n g ，s o f t w a r eu p g r a d i n ge t c ， h a sa c c e l e r a t e dt h en e e df o rs c a l a b l ea n de f f i c i e n tm u l t i c a s ts u p p o r t m u l t i c a s ti sa m o r ee f f i c i e n t t r a n s p o r tm e c h a n i s mt h a n u n i c a s to n p o i n t - t o m u l t i p o i n t d a t a t r a n s m i t t i n g i nt h et r a d i t i o n a lu n i c a s tt h es o u r c en e e dt os e n da ni n d i v i d u a lc o p yo f t h es a m ed a t at oe a c hr e c e i v e r ，s oas i n g l es t r e a mm a yu n n e c e s s a r i l yr e q u i r eal a r g e p o r t i o no ft h ea v a i l a b l en e t w o r kb a n d w i d t l l i ft h e r ea r et h o u s a n d so fr e c e i v e r s i t m a y b eg i v er i s et on e t w o r kc o n g e s t i o n w h i l ei nt h em u l t i c a s tt h e r ei so n l yo n ec o p y o ft h es a m ed a t ao nt h em a i np a t hl i n k sa n dt h er o u t e r sm a k ec o p i e so n l yo nt h e b r a n c h e s s oi tu s e st h el e a s tn e t w o r kb a n d w i d t h 1 1 1 em u l t i c a s td a t at r a n s p o r t i n gt o p o l o g yi sam u l t i c a s tt r e ea n dn o w a d a y sm o r e a n dm o r em u l t i m e d i aa p p l i c a t i o n sr e q u i r eq o sg u a r a n t e e s ，s oh o wt ob u i l dam u l t i c a s t t r e et h a tm e e tt h e + c o r r e s p o n d i n gq o sc o n s t r a i n t sh a se m e r g e da so n eo ft h eb i g g e s t c h a l l e n g e si nt h ef i e l do fm u l t i c a s tr e s e a r c h m a n yr e s e a r c h e r sh a v eb e e nh e a v i l y i n v o l v e di ns t u d y i n ga n dd e s i g n i n gq o sm u l t i c a s tr o u t i n ga l g o r i t h m sa n dp r o t o c o l s q o sm u l t i c a s tr o u t i n gh a sb e e nat o p i co fi n t e n s er e s e a r c ha n dd e v e l o p m e n te f f o r t s o v e rt h ep a s tc o u p l eo fy e a r s t of i n daf e a s i b l ep a t ht h a tm e e tm u l t i c o n s t r a i n t si san p c o m p l e t ep r o b l e m w e p r o p o s ea na l g o r i t h mo p p o s e dt ot h es i t u a t i o nt h a tt h ec o n s t r a i n e dm i n i m u ms t e i n e r t r e e ( c m s t ) p r o b l e mh a sb e e na t t r a c t i n gm u c ha t t e n t i o ni nq u a l i t yo fs e r v i c e ( q o s ) r o u t i n ga r e a , l i t t l ew o r kh a sb e e nd o n eo nm u l t i c a s tr o u t i n gs u b j e c tt om u l t i p l e a d d i t i v ec o n s t r a i n t se v e nt h o u g ht h i si sr e q u i r e db ym a n ye m e r g i n ga p p l i c a t i o n s i n m i sp a p e r ，w ep r o p o s eah e u r i s t i ch m c m ct of i n df e a s i b l es o l u t i o n st ot h i sp r o b l e m h m c m ch a sap r o v a b l yl o wt i m ec o m p l e x i t y a n di t sb a s i ci d e ai st oc o n s t r u c ta m u l t i c a s tt r e es t e p - b v s t e p ，w h i c hi sd o n ee s s e n t i a l l yb a s e do nt h el a t e s tr e s e a r c h r e s u l t so nm u l t i c o n s t r a i n e dm u l t i c a s tr o u t i n g c o m p u t e rs i m u l a t i o n sd e m o n s t r a t et h a t h m c m cc a l la c h i e v eah i 。g hs u c c e s sr a t i oo ff i n d i n gf e a s i b l es o l u t i o n s k e y w o r d s ：q o sr o u t i n g ，m u l t i c o n s t r a i n e dm u l t i c a s tr o u t i n g ，m u l t i c o n s t r a i n e d m i n i m u ms t e i n e rt r e e ，m u l t i - p a t hc o n s t r a i n e dp r o b l e m 原创性声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名： 盈骘三 日期： 跏g 岁l ) 关于学位论文使用权的说明 本人完全了解中北大学有关保管、使用学位论文的规定，其中包 括：学校有权保管、并向有关部门送交学位论文的原件与复印件； 学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的，复 制赠送和交换学位论文；学校可以公布学位论文的全部或部分内容 ( 保密学位论文在解密后遵守此规定) 。 签名：盘够 日期 沁f 乡l ) 导师签名：公隼独日期：塑星：笪：f 中北大学学位论文 1 1 研究背景 第1 章绪论 近年来，随着i n t e r n e t 的飞速发展，基于i n t e r a c t 的应用已经深入到我们社会生活方 方面面，从商务到通信，从教育到娱乐。同时还产生了许多新的应用，其中不少是高宽 需求的多媒体应用，如网络视频会议、网络音频视频广播、a o d o d 、股市行情发布、 媒体远程教育、c s c w 协同计算、远程会诊，在线信息恢复以及p e e r - t o p e e r ( p 2 p ) 文件 共享等。这就带来了带宽的急剧消耗和网络拥塞问题，人们陆续提出多种解决方案：增 加网络带宽；服务器的分散与集群以改变网络流量结构，减轻主干网瓶颈压力；采用组 播技术等。相比较而言，组播技术有独特的优势在此模型下，数据可以经由一共享 链路到达不同的接收者，不管接收者数目多少，在任意分支上只传递单一组播副本。因 为减少了网络间传输的信息量也就相当于增加了带宽，所以组播能从根本上保证其它用 户的q o s 要求。同时，为支持语音、视频以及数据操作等应用的不同服务要求，网络核 心需要区分不同的通信要求，并为之提供最合适的服务。但因特网现有的传输模式仍为 单一的尽量传递( b e s t e f f o r t ) 服务，无法满足多媒体应用和各种用户对网络传输质量 的不同要求。因此，以减少带宽损耗、提高网络资源利用率为目的的，为用户提供更高 服务质量( q o s ) 的路由算法研究目前极具活力。 1 2 研究现状 在目前研究的领域中，网络通信主要有两种模型：单播通信模型和组播通信模型。 在单播通信模型中，数据包的发送者和接收者是一对一的，所以这些数据包是通过网络 沿着单一的路径从源主机传送到目的主机的。但在组播通信模型中，组播源要向某一组 播地址传递数据包，而这一组播地址代表着一组主机，所以发送者和接收者是一对多的 关系( 或多对多的关系，如果有多个发送者的话) 。为了将组播源的数据包发送给所有 中北大学学位论文 的接收者，单一路径已经不能满足要求，所以采用组播分布树来描述组播数据在网络里 经过的路径。 ， 组播分布树有四种基本类型：洪泛法、有源树、核心树和s t e i n e r 树。 l 、洪泛法( f l o o d i n g ) 这是最简单的向前传送组播路由算法，并不构造所谓的分布树。其基本原理如下： 当组播路由器收到发往某个组播地址的数据包后，首先判断是否是首次收到该数据包， 如果是首次收到，那么将其转发到所有接口上，以确保其最终能到达所有接收者；如果 不是首次收到，则抛弃该数据包。 洪泛法的实现关键是“首次收到”的检测。这需要维护一个最近通过的数据包列表， 但无需维护路由表。它适合于对组播需求比较高的场合，并且能做到即使传输出现错误， 只要还存在一条到接收者的链路，则所有接收者都能接收到组播数据包。然而，洪泛法 不适合用于i n t e r n e t ，因为它不考虑链路状态，并且产生大量的拷贝数据包。此外，对 于高速网络而言，“首次收到”列表将会很长，占用相当大的内存，尽管它能保证不对 相同的数据包进行二次转发，但不能保证对相同数据包只接收一次。 2 、有源树 有源树也称为基于信源的树或最短路径树( s h o r t e s tp a t ht r e e ，s p t ) 。它是以组播 源为根构造的从根到所有接收者路径都最短的分布树。如果组中有多个组播源，则必须 为每个组播源构造一棵组播树。由于不同组播源发出的数据包被分散到各自分离的组播 树上，因此采用s p t 有利于网路中数据流量的均衡。同时，因为从组播源到每个接收者 的路径最短，所以端到端( e n d t o e n d ) 的时延性能较好，有利于流量大、时延性能要 求高的实施媒体应用。s p t 的缺点是：要为每个组播源构造各自的分布树，这样的话， 当数据流量不大时，构造s p t 的开销相对较大。 共享树也称r p 树( i 冲t ) ，是指为每个组播组选定一个共用根( 汇合点r p 或核心) ， 以r p 为根建立的组播树。同一组播组的组播源将所要发送的组播数据单播到r p ，再由 r p 向其它成员转发。目前，讨论最多同时也是最具代表性的两种共享树是s t e i n e r 树和 核心树( c b t ) 。 3 、s t e i n e r 树 s t e i n e r 树是总代价最小的分布树，它使连接特定图中特定组的成员所需要的链路数 - 2 中北大学学位论文 目最少。若考虑资源总量被大量的组使用的情况，那么使用资源较少最终就会减少产生 拥塞的风险。s t e i n e r 树相当不稳定，树的形状随组中成员关系的改变而改变，且对大型 网络缺少通用的解决方案。所以s t e i n e r 树只是一种理论模型，而非实用工具。目前， 出现了许多s t e i n e r 树的次优启发式生成算法。 4 、核心树 核心树是由根到所有组成员的最短路径合并而成的树。a b a l l a r d i e 在1 9 9 7 年9 月 的基于核的组播路由体系结构( c o r eb a s e dt r e e s ( c b t ) m u l t i c a s tr o u t i n g a r c h i t e c t u r e ) ( r f c 2 1 8 i 和r f c 2 2 0 1 1 2 1 ) q b 介绍了核心树。 共享树在路由器所需存储状态信息的数量和路由树的总代价两个方面具有较好的 性能。当组的规模较大，而每个成员的数据发送率较低时，使用共享树比较适合。但当 通信量大时，使用共享树将导致流量集中及r p 附近的瓶颈。 许多研究者对o o s 组播路由问题进行了研究，取得了很大的成果，对于多q o s 约束 路径的寻路问题，大概可以分为两种解决方式：一是将它转化为单约束路径问题，利用 现有单约束路径的寻路方法解决；二是保持它为多约束路径问题，寻求新的求解方法。 对于第一种方式可以利用复合权值的方法，即将多约束q o s 参数利用某个函数复合成一 个复合权值，这样就把多q o s 约束路径问题转化为单一q o s 约束路径的寻路问题，然后 可以利用这个复合权值采用d i j s k t r a 算法求得新成员加入组播树的可行路径。这种方 式的优点就是消息复杂度低，节点与节点之间不需要传递大量的消息报文，但是其计算 复杂度较高。本文采取的正是这一基本方法 而第二种方式不需要很多的计算过程，其计算复杂度明显降低，但是代价就是网络 节点之间需要传递大量的控制报文，其多约束可行路径的搜索可分为三种方式：单路径 寻路方式、多路径寻路方式和混合寻路方式。单路径寻路方式，顾名思义，就是提供一 条单一的路径将新成员连接到组播树上，它们的基本思想就是扩展请求消息中携带的信 息使它包含q o s 参数，请求消息沿着向组播树的根或者组播树的核心路由器的方向进行 单播路由，直到到达一个树上节点为止，然后由这个树上节点来进行允许控制检查，即 由树上节点根据目前的网路资源使用情况和路径的q o s 参数信息来决定是否可以接受当 前的连接请求。仅当允许控制检查成功，树上节点才可以沿着请求消息的反向路径来确 认这个加入请求，即建立起新成员和组播树之间的连接。尽管单路径寻路方式耗费很低， - 3 中北大学学位论文 但是在网络负载严重的情况下，它的性能不好。因为单播路径作为唯一的候选路径，在 资源比较紧缺的情况下满足所有的q o s 要求的可能性较低。 多路径路由方式提供多条路径供新成员选择，然后确定其中最能满足其要求的一条 路径将新成员连接到树上，其中y a m b l 协议和q o s m i c h 一协议都属于这种方式。1 9 9 7 年， c a r l b e r gka n dc r o w c r o f tj 提出了y a m 协议，y a m 协议的s p a n n i n g j o i n 方法是较早 尝试采用接收者发起的基于泛播技术的多路径q o s 组播路由协议。该协议使新成员节点 采用反向路径转发r p f 技术广播加入请求报文( j o i n _ r e p o r t ) 以寻找树上节点。当一 个新成员想加入组播树的时候，它向它指定的默认路由器发送加入请求，然后这个路由 器采用反向路径转发r p f 技术向它所有的邻居节点泛洪加入请求，直到遇到一个树上节 点为止。当一个树上节点收到请求报文的时候，这个树上节点沿着单播路径向请求者发 送应答报文a c k ，应答报文沿途收集q o s 信息，而这些应答消息所经过的路径就成为请 求者加入到组播树的候选路径。a c k 报文在传输过程中，会在其传输的路径上为路径建 立临时状态。请求者可能会收到多个应答消息，在它进行最终的连接建立请求之前，它 可以从几个候选路径当中选取一条最好的路径作为将新成员连接到组播树的最终路径 来进行连接建立。但是在y a m 协议中，如果新成员距离组播树比较远时，s p a n n i n g - j o i n 方法需要连续广播加入请求报文，直至遇到在树节点为止，这种方法会明显增加网络带 宽开销，对网络造成的冲击比较大。另外s p a n n i n g - j o i n 方法并不是一个真正的q o s 路 由协议，因为它的单播候选路径实质上是最短路径，选路过程本身并非按q o s 请求来进 行，但是它所开创的多路径搜索解决方法给人以诸多启发。 q o s m i c 协议是对y a m 协议的一个改进，它为了进一步降低协议的开销，将路径的搜 索分为两个部分：本地搜索( 1 0 c a ls e a r c h ) 和树搜索( m u l t i c a s tt r e es e a r c h ) 。本 地搜索原理类似于y a m 协议的s p a n n i n g - j o i n 方法，差别只在搜索的范围变小，这通常 通过限定请求消息的t t l 值来实现，而t t l 究竟设为多少合适，如果t t l 值设置过小， 则不容易找到临域内的树上节点，如果t t l 值设置过大，则又不能有效的降低洪泛的开 销，经实验证明将t t l 值设为2 会得到比较好的性能。当本地搜索不能找到树上节点时， 协议就采用树搜索。树搜索要求新成员节点发送一个树搜索报文( m - j o i n ) 到指定的管 理节点( d e s i g n e d m a n a g e rn o d e ，d b l n ) ，d m n 在组播树中选择一个树上节点子集，这个 子集中的节点随后向新成员发送投标报文( b i d ) 。这些b i d 报文所经历的路径是由单播 4 中北大学学位论文 路由协议决定的，它们构成候选路径。b i d 报文在向新成员发送时会沿途收集所经路径 的q o s 信息，当一个新成员收到多个b i d 报文时，新成员会根据各自候选路径的q o s 信 息选择一条最能满足新成员o o s 要求的候选路径将自己连接到组播树上。q o s m i c 协议的 可伸缩性比y a m 协议好，因为它并不需要在整个网络泛播搜索报文，泛播技术只是被用 于局部搜索。q o s m i c 协议的精髓在于组播树搜索，在组播树内选择合适的树上节点，并 通过这些节点发送单播b i d 报文，所有这些操作被限制在组播树的范围内，没有涉及到 全部网络。但是q o s m i c 协议仍然有几个缺陷：首先如何选择d m n 以及由此而引起的通 讯量增加是一个不能忽视的问题，其次，d m n 要想在组播树中选择一个树上节点子集， 需要一个前提，就是它必须事先知道所有树上节点的信息。由于组播的动态性，传播这 些成员关系信息无论对树上节点还是对d m n 都是一个不小的负担，这种机制使协议复杂 化了。第三，一个显而易见的问题是随着群组数量和每个群组当中的成员节点数量的增 加，d m n 需要存储的信息量与群组数和每个群组的成员数之乘积成正比。第四，d m n 在 组播树中选择一个树上节点子集的机制实现困难，而且需要优化。y a m 是基于连通性而 没有q o s 意识，所以导致了过大的路由耗费，q o s m i c 仅仅是减轻了而没有根本消除盲目 泛洪，而且当树非常大时，树搜索因为耗费太大效率也不高。多路径寻路方式较单路径 寻路方式在支持q o s ，提高连接成功率、缩短加入时间等方面有较大优势，但它的控制 报文开销较大。所以在多路径寻路方式中重点是寻找有效的方法降低这种开销，多路径 寻路方式在q o s 寻路方面是更有前途的一种方式，一些学者基于理论和实验分析，也倾 向于发展多路径寻路方式。 前面所谈到的两种寻路方式都使用一种单一的寻路方式，要么是单路径寻路，要么 是多路径寻路，下面介绍一种方式它综合应用了这两种方式的优缺点，形成混合寻路方 式。q m r p 协议即使用混合寻路方式，它首先使用单路径寻路方式，然后在必要的时候再 切换到多路径寻路方式。q m r p 协议是一个为非可加性度量例如带宽而设的具有q o s 意识 的的组播路由协议。q m r p 的寻路过程为：先采用单路径( s p r ) 搜索，如果失败，搜索 退回到失败点的前趋节点并转而采用多路径搜索。一个新成员节点想加入组播树时，它 通过会话目录( s e s s i o nd i r e c t o r y ) 获得共享组播树的核( c o r e ) 或者源根树的源节 点地址，然后沿着到核或源节点的单播路径发送请求报文( j o i n _ r e q ) ，j o i n r e q 报文 携带了目标节点的q o s 要求，在它被发往核或源去的过程中它会检查到当前节点的部分 5 - 中北大学学位论文 路径是否满足0 0 s 要求。如果某个中间节点不能满足o o s 要求，搜索就退回到失败节点 的上一个节点并启动一个基于泛播的多路径搜索过程，即前驱节点向它所有的邻居节点 ( 除了发送请求包和拒绝请求包的邻居节点) 发送请求包，这些请求包每一个都独立的 再使用各自的单播路径向源或核进行单播路由，在路由的过程中，如果再遇到资源不够 的节点，可以再通知其前驱节点进行扩展分支，每个分支再沿着单播路径进行路由，一 直重复，直到遇到。一个树上节点为止。这样，就形成了一棵以请求者为根以一些树上节 点为叶的多路搜索树，每个叶子沿着搜索树回送应答包，在回送过程中将不需要的树枝 剪掉，为每个请求者只留下一个分支加入到组播树上。q m r p 协议采用单路径与多路径搜 索相结合的方法，在保证搜索成功率的同时，进一步降低了协议的开销。可以看出q m r p 协议对非可加性o o s 度量如带宽有很好的支持，但是对于像延迟这样的可加性0 0 s 度量 来说，它的效用取决于单路径搜索的状况。如果单路径搜索形成的部分路径具有较高的 延迟，则多路径搜索失败的概率会很大，所以q m r p 协议并不能很好地支持像延迟这样 的可加性0 0 s ( a d d i t i v e0 0 s ) 度量。 通过上述的分析可以看出不同的解决方式都有自己的优缺点，针对第一种方式，考 虑到不同的应用有不同的q o s 约束集合，我们针对其中一种情况提出一种算法，满足应 用的时延和时延差异约束限制，并且保证建树耗费不能过大。而对于第二种方式，其可 行路径的搜索方式中多路径搜索相对于单路搜索更有前途，很多研究者也倾向于使用多 路径搜索来寻找可行路径。在多路径搜索中，y a m 协议的s p a n n i n g - j o i n 没有考虑如何 限制泛播通信量，而q o s m i c 协议试图通过局部搜索和树搜索、q m r p 协议试图通过单 路径与多路径搜索的结合来降低这种开销，但是它们都为此而引入了新的问题。q m r p 协议虽然将单路径搜索与多路径搜索有机的结合起来，在保证连接成功率的同时降低了 协议开销，但是q m r p 协议并不能支持可加性q o s 度量，这是它的一个非常大的缺陷。 我们提出一种新的q o s 组播路由协议，它将局部搜索、源搜索，单路径搜索与多路径搜 索有机的结合在一起，使得协议在连接建立时间、消息开销、连接成功率等性能指标方 面作了较好的改善。 6 中北大学学位论文 1 3 本文的内容及主要工作 本文首先针对第一种解决方式，利用复合权值的方法求解一种多约束路径的寻路问 题，提出了一种启发式多约束受限q o s 组播树( h m c m c ) 算法。基本思路是，首先用 m c m s t ( c o n s t r a i n e dm i n i m u ms t e i n e rt r e e 受限最d x s t e i n e r 树) 问题的可行性解决方式找 到一个可行性的树，然后通过一个合理的路径传播，把剩下的目的结点包含进来，在这 过程中我采取了m c p ( m u l t i c o n s t r a i n e dp a t h 多约束路径) 启发法。 我所采用的这种启发法的基本步骤是建立在对多约束单播路由的最新研究的基础 上的。仿真结果显示出，这种启发法方法只要存在，找到一个合理的组播树的成功率较 简单多约束组播路由算法要高。本文的研究内容组织如下： 第l 章引出了组播的概念，介绍了组播问题的研究背景以及研究现状。 第2 章着重探讨了组播路由中的相关问题。首先给出了组播的概念，并阐述了组 播的工作原理，接着给出了常用的几种组播路由协议，介绍了密集模式协议( d m ) 、稀 疏模式路由协议( s m ) 、因特网组管理协议( i g m p ) 、链路状态协议( m o s p f ) 匹t 种协议的 基本原理。然后介绍了组播路由算法，把组播路由算法分为集中式与分布式组播路由算 法，动态与静态组播路由算法并分别进行了阐述，最后给出了组播路由算法的设计原则。 第3 章里，引入q o s 概念，给出q o s 度量的种类，q o s 网络模型以及q o s 路由的 相关问题。之后对q o s 组播路由问题进行了分类，并列举了国内外的单q o s 约束组播 路由算法和多q o s 约束组播路由算法。 第4 章是本文的重点部分，阐述了h m c m c 算法的基本思路，详细列出了m c m s t 问题和m c p 问题的解决算法， 第5 章介绍了网络仿真机制及其必要性，对现有的常用网络仿真软件进行了分析和 比较，介绍了o p n e t 和n s 2 两种实网络模拟器。并用o p n e t 软件对算法进行了仿真， 列出了组播组大小、边的权值分布、约束条件个数对性能指标的影响。仿真结果表明， 与以往算法相比，本算法连接建立时间短，并在消息开销和连接成功率之间作出了较好 的折衷。 第6 章对论文作了总结，提出了算法的不足和将来的研究方向。 - 7 - 中北大学学位论文 第2 章组播路由原理及其协议算法 为进行有效的组播通信，确定组播路由是非常关键的。由于组播组中有多个目的结 点，因此组播路由也比单播路由复杂许多。组播路由算法是本文的研究重点。使用组播 路由算法来确定路由，是在收集网络中相关状态信息的基础上完成。网络的状态信息包 括网络的拓扑结构、链路和路由器的负载程度、链路和路由器的失效和有效、网络中路 由器的类别( 是否具有组播功能) 等。这些信息的收集是由组播路由协议( m u l t i c a s tr o u t i n g p r o t o c 0 1 ) 来完成的。本节简要介绍几个实际应用中的组播路由协议，并对设计组播路由 算法和协议时应考虑的因素进行分析。 2 1 组播路由 组播是一种允许一个或多个发送者( 组播源) 发送单一的数据包到多个接收者( 一 次的，同时的) 的网络技术。组播源把数据包发送到特定组播组，而只有属于该组播组 的地址才能接收到数据包。组播可以大大的节省网络带宽，因为无论有多少个目标地址， 在整个网络的任何一条链路上只传送单一的数据包。除了组播通信方式，计算机网络中 常用的通信方式还有单播通信方式和广播通信方式。从图2 1 中，我们可以看出三种通 信方式的工作原理以及它们的不同点： 8 中北大学学位论文 图2 1 a 单播方式 图2 1 b 组播方式 图2 1 c 广播方式 l 、单播( u n i c a s t ) 传输：在发送者和每一接收者之间需要单独的数据信道。如果 9 中北大学学位论文 一台主机同时给很少量的接收者传输数据，一般没有什么问题。但如果有大量主机希望 获得数据包的同一份拷贝时需要重复发送多次此数据包，这将导致发送者负担沉重、延 迟长、网络拥塞；为保证一定的服务质量需增加硬件和带宽。 2 、广播( b r o a d c a s t ) 传输：是指在i p 子网内广播数据包，所有在子网内部的主机 都将收到这些数据包。广播意味着网络向子网主机都投递一份数据包，不论这些主机是 否愿意接收该数据包。广播的使用范围非常小，只在本地子网内有效，因为路由器会封 锁广播通信。由此可见，广播传输会增加非接收者的开销。 3 、组播传输：它提高了数据传送的效率，减少了主干网的带宽要求以及主干网出 现拥塞的可能性。组播组中的主机可以是在同一个物理网络中，也可以来自不同的物理 网络( 如果不同网络之间的路由器支持组播通信方式的话) 。 2 2 组播工作原理 组播数据的分发是靠组播树来实现的，而组播树的构建是组播路由的任务。组播路 由是比较复杂的问题。首先，组播通信组地址不具有层次性，不含有组成员位置或标识 的任何信息；其次，在多个结点之间计算路由，本身也增加了计算的复杂性；另外参加 组播通信的用户可以动态更新，组成员的更新和网络拓扑的变化等给组播路由的建立和 维护带来的困难。目前常用的组播协议大体可以被分为密集模式和稀疏模式两大类。每 种模式都有自己自身的工作原理和适用范围。 在密集模式( d m ) 中，数据包利用泛洪( 它不依赖任何路由信息，在泛洪过程中， 数据包被传输到除发送该数据包接口之外的所有接口) 机制流向每个路由器的所有网络 接口。网络中的任何一个路由器都知道每个目前活动的发送者的组地址和每个数据源地 址。在这种情况下，数据包有可能会发往不感兴趣的接收者。另外，路由器还要为这些 不必要的结点保存相关信息，因此，只有在多数主机对数据感兴趣，并且有足够的带宽 支持控制消息流的情况下，d m 模式才能发挥较好的作用。而对于大型或具有冗余功能 的网络而言，d m 模式并非是一种理想的组播实现方式。d m 模式常用的路由协议有 p i m d m ( 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 ，稠密模式独立组播路由协议1 ， - 1 0 中北大学学位论文 d v m r p ( 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 ，距离向量组播路由协议) 以及 m o s p f ( 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 ，开放式最短路径优先组播路由协议) 等。 稀疏模式( s m ) 解决了网络中只有少量用户时的洪泛问题，并针对少数用户的情况 进行了组播优化，使得无论是对网络部分还是对全部用户，都能进行高效的数据传输， 因此受到了网络界的推崇。s m 模式所使用的组播路由协议有c b t ( c o r e b a s e dt r e e ，核 树) 组播路由协议和p i m s m ( 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 s p a r s em o d e ，稀疏模式独立 组播路由协议) 等，最常用的是p i m s m 、c b t 协议的基本目标就是减少网络中路由器 的组播状态，从而提供组播的扩展性。它为每个组构建了一棵所有组成员都拥有的双向 共享树，不论源在哪里，整个组的组播流量都在同一棵树上被发送和接收。由于c b t 存在维护困难等方面的原因，直到目前还没有实际应用。 2 3 组播路由协议 组播路由协议用于发现组播组，建立组播路由表或组播树，进行组播数据包传送。 和单播路由协议一样，组播路由也包含路由表的生成和维护两部分。在一个组播会话中， 转发组播数据包的所有路由器结点集合其实就形成了一个组播树，组播路由实质上就是 组播树生成和维护的过程。组播路由器运行组播路由协议，确定数据包的发送路径，以 便在网络上传送组播数据包。可以从很多角度对现有的组播路由协议进行分类，其中一 种是将组播协议细分为以下两个基本类： 2 3 1 密集模式协议( d m ) 密集模式协议总是假定在子网上有接收者，用定期广播组播报文的方法维护组播分 布树，组播信息一开始就被扩散到网络的所有站点，这对于接收者较多的网络来说，效 率较高，因此被称为密集模式协议。密集模式协议有p i m d m ，d v m r p 等。 1 、协议无关组播路由协议( p r o t o c o li n d e p e n d e n tm u l t i c a s t ，p i m ) p i m 设计的出发点在于在广域网范围内同时支持共享树与有源树，并能完成两者之 中北大学学位论文 间的灵活转换，因而集中了两者的优点同时也避免了它们的缺点。在组员密集时以广播 形式传输数据，然后从树上删除不存在接收结点的分支；而组员分布稀疏时，构造共享 树传送，避免分组的广播开销。相应p i m 有两种模式：稀疏模式( s p a r s em o d e ，s m ) 网和密集模式( d e n s em o d e ，d m ) 【7 1 。p i m d m 是指组播组所覆盖的区域内，具有该组用 户的子网数量在子网总数中占很高的比例。p i m d m 基本上与d v m r p 相同，属于数据 驱动型协议，但协议只是直接使用点到点路由算法给出的路由表转发数据。 2 、距离向量组播路由协议( 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 ) ： d v m r p 2 4 是第一个得到广泛使用的组播路由协议，在接收者密集时的效率较高， 它在m b o n e 上被广泛使用。d v m r p 采用路由信息的方式为每个源网络根据最优度量建 立一个组播转发树，并在m b o n e 上采用隧道技术，使组播通信得以在支持组播的子网 之间实现。由于m b o n e 的飞速发展，由d v m r p 带来的大量路由控制分组定期地在网 络中扩散的开销限制了网络规模的发展，为此还提出了分层d v m r p 。d v m r p 也有一 些不足之处，首先是它需要经常进行洪泛，将组播信息发送到网络上的每一点，即使没 有接收者的情况也是一样，这样大大地浪费了网络的带宽；其次它会在路由器中存储大 量的组播转发信息，占用了宝贵的路由器资源。 密集模式协议的显著特征是周期性的扩散和剪枝现象。 ( 1 ) 扩散和剪枝 扩散又称洪泛( f l o o d i n g ) ，这是最简单的向前传送组播路由算法，并不构造所谓的分 布树。其基本原理如下：当组播路由器收到发往某个组播地址的数据包后，首先判断是 否是首次收到该数据包，如果是首次收到，那么将其转发到所有接口上，以确保其最终 能到达所有接收者；如果不是首次收到，则抛弃该数据包。 将组播消息扩散到网络中的每一个点就要伴随着相关资源的消耗( 带宽、路由器、 c p u 等) 。因此，为了避免宝贵的网络资源被无谓地消耗，如果某个接口上的子网没有 组播信息的接收者，路由器就要向上游发送返回到源组播转发树的剪枝消息，以防止组 播信息继续发送到该子网。这种机制的结果就是没有组播信息接收者的子网分支从组播 转发树被剪枝。 剪枝有一个时间限制，即超过一定的时间后，路由器会使接口回到转发状态，并开 始在该接口重新接受组播信息。 - 1 2 中北大学学位论文 ( 2 ) 嫁接 为了提高协议的效率，当子网上出现新的组播信息接收者时，大多数的密集模式协 议能快速的把一起剪枝掉的分支嫁接回组播转发树。例如，当先前被剪枝的组播转发树 分支上的一个新接受站点加入组播组的时候，路由器一检测到这一新的接收站点，立即 向上游发送嫁接信息。当上游路由器收到嫁接信号时，该路由器立即把收到的嫁接信息 的接口设置成转发状态以便组播信息流向下游路由器，最终能够被该接收站点接收，这 样路由器就不用等到先前的剪枝超时就能收到组播信息，从而提高了协议的运行效率。 2 3 2 稀疏模式路由协议( s m ) 稀疏模式协议总是假定在子网上没有组播信息的接收者，缺省地不向网络中转发组 播信息，除非有一个显式的加入机制来专门申请，否则组播信息就不传送到接收站点。 当网路稀疏分布、网络也没有充足带宽的情况，如广域网环境，可以使用s m 路由协议。 s m 路由协议采用选择性的建立和维护分布树的方式，由空树开始，仅当成员显式的请 求加入分布树才做出修改。s m 路由协议有：p i m s m 6 】和c b t 8 1 。 在稀疏模式网络里，如果组播转发树的分支不能从下游周期性的接收到加入消息， 即假定下游不再有对该组播信息感兴趣的接收者，该分支就要在超时的时候被删除，从 而阻止信息向该分支流动，一些协议( 如p i m s m ) 通过周期性的向组播转发树重新发送 加入消息来更新分支以达到更新的目的。在稀疏模式协议里，当组播组信息不再被需要 时，剪枝信息被发送到组播 转发树上，此举允许通过显式加入消息建立的组播转发树分支在不再需要时再次被 剪枝。例如，如果叶路由器检测到它的接口上不再有对特定的组播组感兴趣的主机( 或 下游组播路由器) ，路由器就要向组播转发树中它的上游发送剪枝消息以便切断不需要 的组播组的信息流。不等待稀疏模式组播转发树分支超时，而马上发送剪枝信息大大缩 短了网络的等待时间。 1 3 - 中北大学学位论文 2 4 组播路由算法 实现组播路由最普遍的方法是构造源结点到组目的结点的树形路由结构，信息可 以沿着这棵树决定的路径并行发送，减少了信息传递的延时；而且信息复制仅在树权处 进行，可以节省网络带宽资源，降低网络负载。迄今为止，树建立实际上还在使用一些 基本的算法。其中d i j k s t r a 算法b e l l m a n f o r d 算法、f l o y d 算法、动态规划方法是针对 最短路径问题提出的；贪心算法、p r i m 算法、破圈法、k r u s k a l 算法是基本的最小生成 树算法；p m s t 算法、k m b 算法是基于最小生成树算法，经剪枝生成s t e i n e r 树的启发 式算法；n a i v e 算法、s p h 算法、s p h z 算法、k s p h 算法、a d