（管理科学与工程专业论文）qos组播路由问题研究.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声 明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：二是呔硼 导师签字： 学位论文版权使用授权书 髹o - 月牝 j 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堂 蕉j 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名；珠执确 签字日期：2 0 0 岁年5 月7 日 导师签字：彩9 ，明z 签字日期：2 0 0年1 月9 臼 山东师范大学硕士学位论文 摘要 近来i n t e r n e t 上越来越多有q o s 要求的组应用的涌现，如视频会议、网络音频视 频广播、远程教育、软件更新等，这加速了网络对可扩展的有效的组播通信方式支持的 需要。与单播通信方式比较起来，组播在点到多点的数据传输方面更有效，在传统的单 播通信方式中，源需要向每个接收者单独传送一份数据的拷贝，一个数据流就有可能占 用了不必要的很大一部分的带宽，如果接收者成千上万，网络拥塞发生的可能性就大大 增高。而在组播通信方式中，主干链路上只有一个数据的拷贝，路由器只在分枝处进行 数据包的复制，所以大大节省了带宽。 实现组播重要的一环是组播路径的确立，与单播传输路径不同的是组播数据传输的 拓扑是一棵组播树，而构建组播树是组播路由的任务，考虑到现在越来越多多媒体应用 要求有q o s 保证，所以如何构建一棵组播树使其满足相应用户的q o s 要求成为组播研究 领域的一个很大的挑战。许多研究者正致力于q o s 组播路由算法和协议的研究和设计， q o s 组播路由已经成为近年来的一个热点研究领域。 本文第1 章首先介绍了组播的基本知识，分析了组播路由的原理，在此基础上，为 了满足应用的q o s 要求，探讨了q o s 组播路由的相关工作，并分析了当前该领域中存在 的问题。 第2 章着重探讨了q 0 s 组播路由中的相关问题。首先介绍了组播树的类型以及各种 类型的特点，接着给出了当前常用的几种组播路由协议并将它们分为两类，最后引入q o s 概念，给出q o s 度量的种类，q o s 网络模型以及q o s 路由的相关问题。 在q o s 组播路由中，寻找多约束可行路径问题已经被证明是n p 完全问题。第3 章提 出了一个构建组播树的启发式算法，该算法基于两点：基于复合权值的d i j k s t r a 算法和 核心树的思想，该算法建立的组播树不仅能满足用户的时延和时延差异限制的要求，并 且能够保证构建组播树的耗费较小。 近年来，除了单路径寻路方式外，多路径寻路方式和混合寻路方式得到了越来越多 的关注。在第4 章里，我们分析和比较y - - 种寻路方式的优缺点，并在此基础上提出了 一种新的q o s 组播路由算法q o s m r a ，该算法综合应用了单路径寻路、多路径寻路、局部 搜索以及源搜索方式，使其与同类算法相比连接建立的时间较短，并且在消息开销和连 接成功率之间也作了较好的折衷。 为了验证算法的合理性和有效性，本文在第5 章中对q o s m r a 进行了仿真实验来评价 算法多方面的性能，仿真结果表明，与以往算法相比，该算法在消息开销、连接成功率 和连接建立时间等性能指标方面都有较好的改善。 n s 是目前国际上应用广泛的网络仿真软件，在分析和评价网络性能方面发挥了重要 山东师范大学硕士学位论文 作用，本文所有实验均是在n s 中进行仿真分析的。 本文在q o s 组播路由算法方面进行了探讨，希望能够对q o s 组播路由问题的研究发 展起一定的推动作用。 关键词：服务质量，组播，路由，算法，协议 分类号：t p 3 9 3 4 山东师范大学硕士学位论文 r e s e a r c h e so n q o sm u l t l c a s tr o u t i n gp r o b l e m s 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 嬲 v i d e o c 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 s a 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 sam o r ee f f i d e n t t r a n s p o r tm e c h a n i s mt h a nu n i c a s to np o i n t - t o - m u l t i p o i n t sd a t at r a n s m i t t i n g i nt h et r a d i t i o n a l u 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 ft 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 e s t r e a mm a yu n n e c e s s a r i l yr e q u i r ea l a r g ep 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 h ，i ft h e r e a r et h o u s a n d so fr e c e i v e r s ，i tm 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 t t h e r ei so n l yo n ec o p yo 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 y o nt h eb 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 t h 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 ea n dm o r e m 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 tt 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 tc h a l l e n g e si nt h ef i e l d o f m 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 yi n v o l v e di ns t u d y i n ga n dd e s i g n i n g o 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 f i 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 so v e rt h ep a s tc o u p l eo fy e a r s i nt h i sp a p e r , c h a p t e r1g i v e sag e n e r a li n t r o d u c t i o no nq o sm u l t i c a s tr o u t i n g f i r s tt h e p r e l i m i n a r yk n o w l e d g eo fm u l t i c a s ti si n t r o d u c e d ，a n dt h e nt h em u l t i c a s tr o u t i n gi sa n a l y z e d a n di no r d e rt om e e tq o sc o n s t r a i n t s ，w ea l s od i s c u s st h er e s e a r c hw o r kr e l a t e dt oq o s m u l t i c a s tm u t i n g f i n a l l ye x i s t i n gp r o b l e m si nc u r r e n tq o sm u l t i c a s tr o u t i n ga r ep r o p o s e d c h a p t e r2f o c u s e so nt h ep r o b l e m so fq o sm u l t i c a s tr o u t i n g f i r s tt h et y p e so fm u l t i c a s t t r e ea n dt h ec h a r a c t e r i s t i c so fe a c ht y p ea r ed e s c r i b e d t h e nw ei n t r o d u c es e v e r a lm u l t i c a s t m u t i n gp r o t o c o l st h a ta r ei nc o m m o n u s ea n dc l a s s i f yt h e mi n t ot w ok i n d s f i n a l l y , t h ec o n c e p t o fq o si si n t r o d u c e da n do nt h i sp o i n t ，w es t a t et h eq o sd e f i n i t i o n ，o o sm e t r i c s ，q o sn e t w o r k m o d e la n do o sr o u t i n gp r o b l e m i nq o sm u l t i c a s tr o u t i n g , 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 sa n p c o m p l e t ep r o b l e m i nc h a p t e r3 ，w ep r o p o s ea na l g o r i t h mf o rd e l a ya n dd e l a yv a r i a t i o nl e s s c o s tm u l t i c a s tt r e ep r o b l e mw h i c hb a s e so nt w oi d e a s ：d i j k s t r aa l g o r i t h mo nm i x e dw e i g h ta n d c o r eb a s e dt r e e i nr e c e n ty e a r s ，m u l t i - p a t hr o u t i n ga n dm i x e d p a t hr o u t i n gb e s i d e ss i n g l e p a t hr o u t i n g h a v er e c e i v e dm o r ea n dm o r ea t t e n t i o n i nc h a p t e r4w ea n a l y z ea n dc o m p a r et h et h r e er o u t i n g m e t h o d sa n db a s e do nw h i c hw ep u tf o r w a r dan e wa l g o r i t h mf o rq o sm u l t i c a s tr o u t i n g q o s m r at h a tm a k e su s eo fl o c a ls e a r c h ，s o u r c es e a r c h ，s i n g l e p a t hr o u t i n ga n dm u l t i p a t h 5 山东师范大学硕士学位论文 r o u t i n g i tm a k e sg o o dt r a d e o f fb e t w e e nm e s s a g eo v e r h e a da n ds u c c e s sr a t i oa n d i t sc o n n e c t i o n c o n s t r u c t i o nl i m ei sm u c hs h 0 1 t e l w ea l s op r e s e n tan u m b e ro fs i m u l a t i o n st od e m o n s t r a t ea n de v a l u a t et h ee f f i c i e n c ya n d p e r f o r m a n c eo fq o s m r a i n c h a p t e r5 ，i n c l u d i n ga n a l y s i s o nt h em e s s a g eo v e r h e a d ，t h e s u c c e s sr a t i oa n dt h ec o n n e c t i o nc o n s t r u c t i o nt i m e t h es i m u l a t i o nr e s u l t ss h o wt h a tq o s m r a r e a c h e st h ed e s i g ng o a lo ft h ea l g o r i t h m n si so l eo ft h em o s tp o p u l a rn e t w o r ks i m u l a t o r si nt h ew o r l d ，w h i c hi su s e df o r a n a l y z i n ga n de v a l u a t i n gn e t w o r kp e r f o r m a n c e s ，s ow ec h o o s en sa so u rs i m u l a t o rt o o lt o s u p p o r ta l le x p e r i m e n t si nt h i sp a p e r i naw o r d ，t h i sp a p e rd o e ss o m er e s e a r c h e si nt h eo o sm u l t i c a s tr o u t i n gf i e l d w eh o p ei t c o u l dp r o m o t et h ed e v e l o p m e n to fq o sm u l t i c a s tr o u t i n gp r o b l e mi nac e r t a i ne x t e n t k e y w o r d s q o s ，m u l t i c a s t , r o u t i n g , a l g o r i t h m ，p r o t o c o l c l a s s i f i c a t i o n ：t p 3 9 3 6 山东师范大学硕士学位论文 1 1 研究背景 第1 章绪论 近年来，随着计算机网络技术的不断发展，在其上的应用逐渐趋于多样化，例如网 络视频会议、网络音频视频广播、a o d v o d 、股市行情发布、多媒体远程教育、c s c w 协同计算、远程会诊，在线信息恢复，软件或代理缓存更新等，这其中不乏一些高带宽 的点到多点的通信应用，虽然近年来通信网络带宽和处理能力都得到了很大的提高，但 是相对于这些应用的发展速度来说，仍然有些力不从心。组播是一种将数据分发到大量 接收者的通信方式，而这些应用本身的特点也决定了组播是其一种有效的解决方式，与 使用多个单播连接相比，组播会话可以大大减小数据源和网络的传输代价。在组播网络 中，即使用户数量成倍增长，主干带宽不需要随之增加，这个优点使它成为当前网络技 术中的研究热点之。 1 1 1 组播的工作原理 组播是一种允许一个或多个发送者( 组播源) 发送单一的数据包到多个接收者( 一 次的，同时的) 的网络技术。组播源把数据包发送到特定组播组，而只有属于该组播组 的地址才能接收到数据包。组播可以大大的节省网络带宽，因为无论有多少个目标地址， 在整个网络的任何一条链路上只传送单一的数据包。除了组播通信方式，计算机网络中 常用的通信方式还有单播通信方式和广播通信方式。从图1 1 中，我们可以看出三种通 信方式的工作原理以及它们的不同点： 单播( u n i c a s t ) 传输：在发送者和每一接收者之间需要单独的数据信道。如果一台 主机同时给很少量的接收者传输数据，一般没有什么闯题。但如果有大量主机希望获得 数据包的同一份拷贝时需要重复发送多次此数据包，这将导致发送者负担沉重、延迟长、 网络拥塞：为保证一定的服务质量需增加硬件和带宽。 广播( b r o a d c a s t ) 传输：是指在m 子网内广播数据包，所有在子网内部的主机都将 收到这些数据包。广播意味着网络向子网主机都投递一份数据包，不论这些主机是否愿 意接收该数据包。广播的使用范围非常小，只在本地子网内有效，因为路由器会封锁广 播通信。由此可见，广播传输会增加非接收者的开销。 组播传输：它提高了数据传送的效率，减少了主干网的带宽要求以及主干网出现拥 塞的可能性。组播组中的主机可以是在同一个物理网络中，也可以来自不同的物理网络 ( 如果不同网络之间的路由器支持组播通信方式的话) 。 山东师范大学硕士学位论文 图1 - 1 a 单播方式 图1 1 b 组播方式 图1 1 c 广播方式 1 1 2 组播通信的实现方案 在单播通信模型中，数据包的发送者和接收者是一对一的，所以这些数据包是通过 网络沿着单一的路径从源主机传送到目的主机的。但在组播通信模型中，组播源要向某 一组播地址传递数据包，而这一组播地址代表着一组主机，所以发送者和接收者是一对 多的关系( 或多对多的关系，如果有多个发送者的话) 。为了将组播源的数据包发送给所 有的接收者，单一路径已经不能满足要求，所以采用组播分布树来描述组播数据在网络 里经过的路径。 组播分布树有四种基本类型：洪泛法、有源树、核心树和s l e i n e r 树。 一、洪泛法( f l o o d i n g ) 这是最简单的向前传送组播路由算法，并不构造所谓的分布树。其基本原理如下： 当组播路由器收到发往某个组播地址的数据包后，首先判断是否是首次收到该数据包， 如果是首次收到，那么将其转发到所有接口上，以确保其最终能到达所有接收者；如果 不是首次收到，则抛弃该数据包。 8 山东师范大学硕士学位论文 洪泛法的实现关键是“首次收到”的检测。这需要维护个最近通过的数据包列表， 但无需维护路由表。它适合于对组播需求比较高的场合，并且能做到即使传输出现错误， 只要还存在一条到接收者的链路，则所有接收者都能接收到组播数据包。然而，洪泛法 不适合用于i n t e r n e t ，因为它不考虑链路状态，并产生大量的拷贝数据包。此外，对于高 速网络而言，“首次收到”列表将会很长，占用相当大的内存，尽管它能保证不对相同的 数据包进行二次转发，但不能保证对相同数据包只接收一次。 二、有源树 有源树叶称为基于信源的树或最短路径树( s h o r t e s tp a t ht r e e ，s e t ) 。它是以组播源 为根构造的从根到所有接收者路径都最短的分布树。如果组中有多个组播源，则必须为 每个组播源构造一棵组播树。由于不同组播源发出的数据包被分散到各自分离的组播树 上，因此采用s p t 有利于网路中数据流量的均衡。同时，因为从组播源到每个接收者的 路径最短，所以端到端( e n d t o e n d ) 的时延性能较好，有利于流量大、时延性能要求高 的实施媒体应用。s p t 的缺点是：要为每个组播源构造各自的分布树，这样的话，但数 据流量不大时，构造s p t 的开销相对较大。 三、共享树 共享树也称r p 树( r p t ) ，是指为每个组播组选定一个共用根( 汇合点r p 或核心) ， 以r p 为根建立的组播树。同一组播组的组播源将所要发送的组播数据单播到r p ，再由 r p 向其它成员转发。目前，讨论最多同时也是最具代表性的两种共享树是s t e i n e r 树和 核心树( c b t ) 。 s t e i n e r 树是总代价最小的分布树，它使连接特定图中特定组的成员所需要的链路数目 最少。若考虑资源总量被大量的组使用的情况，那么使用资源较少最终就会减少产生拥 塞的风险。s t e i n e r 树相当不稳定，树的形状随组中成员关系的改变而改变，且对大型网 络缺少通用的解决方案。所以s t e i n e r 树只是一种理论模型，而非实用工具。目前，出现 了许多s t e i n e r 树的次优启发式生成算法。 核心树是由根到所有组成员的最短路径合并而成的树。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 ga r c h i t e c t u r e ) 0 理c 2 1 8 9 “4 和r f c 2 2 0 1 ”) 中介绍了核心树。 共享树在路由器所需存储的状态信息的数量和路由树的总代价两个方面具有较好的 性能。当组的规模较大，而每个成员的数据发送率较低时，使用共享树比较适合。但当 通信量大时，使用共享树将导致流量集中及( i 冲) 附近的瓶颈。 1 ，1 3 组播路由 组播数据的分发是靠组播树来实现的，而组播树的构建是组播路由的任务。组播路 由是比较复杂的问题。首先，组播通信组地址不具有层次性，不含有组成员位置或标识 的任何信息；在多个节点之间计算路由，本身也增加了计算的复杂性；另外参加组播通 信的用户可以动态更新，组成员的更新和网络拓扑的变化等给组播路由的建立和维护带 9 山东师范大学硕士学位论文 来的困难。目前常用的组播协议大体可以被分为密集模式和稀疏模式两大类。每种模式 都有自己自身的工作原理和适用范围。 在密集模式( d m ) 中，数据包利用泛洪f 它不依赖任何路由信息，在泛洪过程中， 数据包被传输到除发送该数据包接口之外的所有接口) 机制流向每个路由器的所有网络 接口。网络中的任何一个路由器都知道每个目前活动的发送者的组地址和每个数据源地 址。在这种情况下，数据包有可能会发往不感兴趣的接收者。另外，路由器还要为这些 不必要的节点保存相关信息，因此，只有在多数主机对数据感兴趣，并且有足够的带宽 支持控制消息流的情况下，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 ，稠密模式独立组播路由协议) ， d v m r p ( d i s t a n c ev e c t o r m u l t i c a s t r o u t i n gp r o t o c o l ，距离向量组播路由协议1 以及 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 e o l - 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 存在维 护困难等方面的原因，直到目前还没有实际应用。 1 1 4o o s 组播路由 显然，上述组播路由只注重单纯的组播树的建立，强调其连通性，并没有考虑到该 组播树的q o s 要求，而许多组播应用对q o s 是有要求的，例如文件分发业务要求分组丢 失率尽可能的低，即它看重的是可靠性而并不是很关心传输延迟如何；视频会议等实时 多媒体业务为了最终效果的流畅则更看重延迟和抖动，如果所建的组播树不满足o o s 要 求，那么即使建立起了组播树，这棵组播树也是不可用的。这就要求网络能够区别对待 各种业务并对他们提供不同的服务质量，其中q o s 组播路由是其中的一个解决方案，成 为近年来的研究热点问题。 1 1 5 相关工作 许多研究者对q o s 组播路由问题进行了研究，取得了很大的成果，而对于其一般情 况多q o s 约束路径的寻路问题，大概可以分为两种解决方式：一是将它转化为单约 束路径问题，利用现有单约束路径的寻路方法解决；二是保持它为多约束路径问题，寻 求新的求解方法。对于第一种方式可以利用复合权值的方法，即将多约束q o s 参数利用 1 0 山东师范大学硕士学位论文 某个函数复合成一个复合权值，这样就把多q o s 约束路径问题转化为单一q o s 约束路径 的寻路问题，然后可以利用这个复合权值采用d i j s k t r a 算法求得新成员加入组播树的可行 路径。这种方式的优点就是消息复杂度低，节点与节点之间不需要传递大量的消息报文， 但是其计算复杂度较高。 而第二种方式不需要很多的计算过程，其计算复杂度明显降低，但是代价就是网络 节点之间需要传递大量的控制报文，其多约束可行路径的搜索可分为三种方式：单路径 寻路方式、多路径寻路方式和混合寻路方式。单路径寻路方式，顾名思义，就是提供一 条单一的路径将新成员连接到组播树上，它们的基本思想就是扩展请求消息中携带的信 息使它包含q o s 参数，请求消息沿着向组播树的根或者组播树的核心路由器的方向进行 单播路由，直到到达一个树上节点为止，然后由这个树上节点来进行允许控制检查，即 由树上节点根据目前的网路资源使用情况和路径的o o s 参数信息来决定是否可以接受当 前的连接请求。仅当允许控制检查成功，树上节点才可以沿着请求消息的反向路径来确 认这个加入请求，即建立起新成员和组播树之间的连接。尽管单路径寻路方式耗费很低， 但是在网络负载严重的情况下，它的性能不好。因为单播路径作为唯一的候选路径，在 资源比较紧缺的情况下满足所有的o o s 要求的可能性较低。 多路径路由方式提供多条路径供新成员选择，然后确定其中最能满足其要求的一条 连路径将新成员连接到树上，其中y a m 嘲协议和q o s m i c 跚列协议都属于这种方式。1 9 9 7 年，c a r l b e r gka n dc r o w c r o f tj 提出了y 埘协议，y a m 协议的s p a n n i n g j o i n 方法是 较早尝试采用接收者发起的基于泛播技术的多路径q o s 组播路由协议。该协议使新成员 节点采用反向路径转发r p f 技术广播加入请求报文( 3 0 i n )报文以寻找树上节点。_req 当一个新成员想加入组播树的时候，它向它指定的默认路由器发送加入请求，然后这个 路由器采用反向路径转发r p f 技术向它所有的邻居节点泛洪加入请求，直到遇到一个树 上节点为止。当一个树上节点收到请求报文j o i n - r e q 的时候，这个树上节点沿着单播路 径向请求者发送应答报文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 j n g - j o i n 方法并不是一个 真正的q o s 路由协议，因为它的单播候选路径实质上是最短路径，选路过程本身并非按 q o s 请求来进行，但是它所开创的多路径搜索解决方法给人以诸多启发。 q o s l i i 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 ：y 法，差别只在搜索的范围变小，这通常通过限 定请求消息的t t l 值来实现，而t t l 究竟设为多少合适，如果t t l 值设置过小，则不容易找 到临域内的树上节点，如果t t l 值设置过大，则又不能有效的降低洪泛的开销，经实验证 1 1 山东师范大学硕士学位论文 明将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 洲) ，d m n 在组播树中选择_ 个树上节点子集，这个子集中的节点随后 向新成员发送投标报文( b i d ) 。这些b i d 报文所经历的路径是由单播路由协议决定的，它 们构成候选路径。b i d 报文在向新成员发送时会沿途收集所经路径的o o s 信息，当个新 成员收到多个b i d 报文时，新成员会根据各自候选路径的q o s 信息选择一条最能满足新成 员o o s 要求的候选路径将自己连接到组播树上。q o s m i c 协议的可伸缩性比y a m 协议好，因为 它并不需要在整个网络泛播搜索报文，泛播技术只是被用于局部搜索。o 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 ，提高连接成功率、缩短加入时间等方 面有较大优势，但它的控制报文开销较大。所以在多路径寻路方式中重点是寻找有效的 方法降低这种开销，多路径寻路方式在o o s 寻路方面是更有前途的一种方式，一些学者 基于理论和实验分析，也倾向于发展多路径寻路方式。 前面所谈到的两种寻路方式都使用一种单一的寻路方式，要么是单路径寻路，要么 是多路径寻路，下面介绍一种方式它综合应用了这两种方式的优缺点，形成混合寻路方 式。q m r p 协议啪3 即使用混合寻路方式，它首先使用单路径寻路方式，然后在必要的时候 再切换到多路径寻路方式。q m r p 协议是一个为非可加性度量例如带宽而设的具有q o s 意 识的的组播路由协议。q m r p 的寻路过程为：先采用单路径( s p r ) 搜索，如果失败，搜索 退回到失败点的前趋节点并转而采用多路径搜索。一个新成员节点想加入组播树时，它 通过会话目录( s e s s i o r ld i r e c t o r y ) 获得共享组播树的核( c o r e ) 或者源根树的源节点 地址，然后沿着到核或源节点的单播路径发送请求报文( j o i nr e q ) ，j o i n r e q 报文携带 了目标节点的q o s 要求，在它被发往核或源去的过程中它会检查到当前节点的部分路径 是否满足o o s 要求。如果某个中间节点不能满足o o s 要求，搜索就退回到失败节点的上 一个节点并启动一个基于泛播的多路径搜索过程，即前驱节点向它所有的邻居节点( 除 了发送请求包和拒绝请求包的邻居节点) 发送请求包，这些请求包每一个都独立的再使 用各自的单播路径向源或核进行单播路由，在路由的过程中，如果再遇到资源不够的节 点，可以再通知其前驱节点进行扩展分支，每个分支再沿着单播路径进行路由，一直重 1 2 山东师范大学硕士学位论文 复，直到遇到一个树上节点为止。这样，就形成了一棵以请求者为根以一些树上节点为 叶的多路搜索树，每个叶子沿着搜索树回送应答包，在回送过程中将不需要的树枝剪掉， 为每个请求者只留下一个分支加入到组播树上。q m r p 协议采用单路径与多路径搜索相结 合的方法，在保证搜索成功率的同时，进一步降低了协议的开销。可以看出q m r p 协议对 非可加性q o s 度量如带宽有很好的支持，但是对于像延迟这样的可加性q o s 度量来说， 它的效用取决于单路径搜索的状况。如果单路径搜索形成的部分路径具有较高的延迟， 则多路径搜索失败的概率会很大，所以q m r p 协议并不能很好地支持像延迟这样的可加性 q o s ( a d d i t i v eq o s ) 度量。 1 2 问题提出 通过上述的分析可以看出不同的解决方式都有自己的优缺点，针对第一种方式，考 虑到不同的应用有不同的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 慷p 协议并不能支持可加性o o s 度量，这是它的一个非常大的缺陷。我们提出一种 新的q 0 s 组播路由协议，它将局部搜索、源搜索，单路径搜索与多路径搜索有机的结合 在起，使得协议在连接建立时间、消息开销、连接成功率等性能指标方面作了较好的 改善。 1 3 本文的内容及主要工作 本文首先针对第一种解决方式，利用复合权值的方法求解一种多约束路径的寻路问 题，提出了一种有时延和时延约束限制的较小耗费组播树算法。然后又针对第二种解决 方式中当前q 0 s 组播路由的三种寻路方式，分析比较了各算法存在的问题，结合各协议 算法的优缺点对其进行了改进，提出了一种新的q o s 组播路由算法，并在网络模拟器n s ( n e t w o r ks i m u l a t o r ) 上对该算法进行了性能分析，实验结果表明该算法连接建立时间 短，并在消息开销和连接成功率等方面都有较好的改善，显示出了令人满意的结果。 本文的研究内容组织如下： 第2 章着重探讨了o o s 组播路由中的相关问题。首先介绍了组播树的类型以及各种 类型的特点，接着给出了当前常用的几种组播路由协议并将它们分为两类，最后引入o o s 概念，给出o o s 度量的种类，。o s 网络模型以及q o s 路由的相关问题。 第3 章采用第一种解决方式，将多q o s 约束路径的寻路问题转化为单约束路径寻路 山东师范大学硕士学位论文 问题，并针对一种应用的q o s 约束集合，提出了一种满足时延和时延差异限制的较小耗 费组播树算法，该算法基于两点：基于复合权值的d i j k s t r a 算法和核心树思想。 第4 章里，我们针对第二种解决方式分析和比较了三种寻路方式的优缺点，并在此 基础上提出了一种新的q o s 组播路由算法q o s m r a ，该算法综合应用了单路径寻路、多路 径寻路、局部搜索以及源搜索方式，力求在算法的一些重要性能指标上作出改善。 第5 章介绍了对q o s m r a 算法进行网络仿真实验与分析的结果。仿真实验在网络模拟 器n s 2 上进行，对算法进行仿真实验来评价算法在消息开销和连接成功率等方面的性能。 仿真结果表明，与以往算法相比，本算法连接建立时间短，并在消息开销和连接成功率 之间作出了较好的折衷。 1 4 山东师范大学硕士学位论文 第2 章0 0 $ 组播路由问题研究 近年来，随着信息技术的迅猛发展，互联网产生了很多新的应用，特别是在高带宽 需求的多媒体上的应用，如视频点播、网络会议等。传统的数据通信均采用单播或广播 技术，造成主机与网络资源的过度浪费，带来了带宽的急尉消耗和网络拥挤问题。为了 缓解网络瓶颈，人们提出一些解决方案，如增加网络带宽，改变网络流量结构，组播技 术等等，其中，组播技术有其独特的优越性：在组播网络中，即使用户数量成倍增长， 主干带宽也不需要随之增加，从而成为通行的网络技术之一。 组播数据包的传送路径是由组播路由来决定的，组播路由是比较复杂的问题，首先， 组播通信组地址不具有层次性，不含有组成员位置或标识的任何信息；在多个节点之间 计算路由，本身也增加了计算的复杂性；另外参加组播通信的用户可以动态更新，组成 员的更新和网络拓扑的变化等给组播路由的建立和维护带来了困难，它较单播路由来说 更为困难，这主要集中在组播转发机制上。首先，由于路由器需要将进入的组播数据流 在多个端口上转发，因此路由器在转发前必须检查多个端口。这就需要存储群组成员的 相关信息，即组播路由表；第二，对于一个群组，它的每个成员都有可能是源端。如果 为每一个源节点都建立一个组播树的话，组播转发表的表项将是一个( 源，组) 对，因此， 组播路由表的大小将正比于互联网中的网络数与群组数的乘积( 单播路由表正比于互联 网中的网络数) ；第三在单播路由中，只有当网络拓扑结构发生改变或者设备出现故障时， 才会发生路由改变，而组播则不同，不仅网络拓扑结构发生改变或者设备出现故障时组 播路由会改变，更重要的是应用程序加入或退出一个群组就会引起路由的变化；换句话 说，组播路由是一个更加动态化的问题。总之，所有组播路由方法都要提供一种传播成 员信息的机制，同时提供利用这些信息以转发组播数据包的方法。而解决组播路由问题 最常用、最有效的方法是建树，其原因有二：1 ) 信息可以沿着树的分枝并行的传到各个 目的节点；2 ) 信息只在树的分枝处进行复制，从而使复制的份数尽量少。随着越来越多 组播应用对o o s 的要求，组播树不但要把信息送到所有的目的