（通信与信息系统专业论文）组播路由及故障恢复机制研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 网络中以点到多点为特征的应用如，视频点播、视频会议、网络集体游戏等需要消 耗大量的网络带宽，这些应用迫切需要有效的组播技术的支持。组播路由是组播技术 的核心课题，而组播通信中的节点或链路故障将会给组播下游节点带来灾难性的影响， 因此组播路由及组播故障恢复是许多研究者所关注的焦点。 单播网络中的不相交多路径路由技术可以提高网络的健壮性，实现网络的负载均 衡。本文通过对不相交多路径路由技术中的s i i i l c t 算法进行了仔细的分析和研究，并 根据其特征将其应用的组播环境中，提出了几种组播路由方案和组播故障恢复方案， 具体如下： 第一，提出了一种基于s i m c t 的组播路由方案，方案中首先根据s i m c t 算法建立 反向颜色树，然后通过颜色树中相邻两节点间的简单报文交互，实现组播通信树的快 速组建； 第二，对于s i i i l c t 组播路由方案的得到的组播树过于臃肿的缺点，有目的性的提 出了一种改进的s i i l l c t 组播路由方案，可以实现组播成员的动态加入或离开，减少了 组播路由中的冗余开销： 第三，为了提高路由方案在网络环境中的健壮性，又有针对性的提出了两种故障解 决方案，分布式故障恢复方案和集中式恢复方案。通过仿真分析发现，这两种方案都 可以有效的恢复组播通信中单节点或链路的故障问题，且两种方案各有其优缺点。 关键词：s i m c t ：颜色树；组播树；故障恢复；仿真 西南交通大学硕士研究生学位论文第| f 页 a b s t r a c t h lt l l ei n t e n l e t ，t 量l e 他a r em 锄ya p p i i c a t i o 璐跚c h 勰v o d ，v i d e 0c o n 衔髓c e 锄dn e t 、) l ，o r k g 锄e sh a v eo n e t 0 一m a l l yc h a r a c t 谢s t i ca n d 唧i r em u c hb a n d w i d t l l ，t l l e s ea p p l i c a t i o n sn e e d m u l t i c a s tt e c l l i l o l o g yt 0 跚p p o r ti i i i m i n 肌t l ym u l t i c 鹊tr o u t i n gi sm ei m p o r t 觚tt a s ko f m u l t i c 弱tt e d m o l o g y ，锄do n c em er 1 0 d eo rl i l l l 【f 缸l u r ci nm u l t i c a s tt r e e ，a l lt l l ed o w nr 1 0 d e s o f l e 筋l u w i l lb r e a ku p ，s o 廿1 et e d m o l o g yo fm u l t i c 弱t u t i n g 锄df a u l t 一心c 0 v e 叮h a y c b e c 0 m et l l ef o c 郴o fa t t e n t i o nf o rm 锄yr e s e a r c h 瓯 d i s j o i n t 舢l t i - p a t l lr o u t i l l gc 弛i m p r 0 v et 1 1 er o b u s t i l 销s 锄dl o a db a l 肌c i i l go fm ei p n e t 、) l ，o r k ，t l l i sp a p 盯f o c 憾o n l es i l n c ta l g o r i t l 蚰，w l l i c hi so n eo ft l l ed i s j o i n tm u i t i - p a m r o u t i n ga 1 9 0 r i t h m ，的m 肌a l y s i s 锄dr 船e 删lo fs i m c ta 1 9 0 r i m m ，w ei n 仃d d u 圮 a p p r o a c ht 0m u l t i c 嬲t 印p l i c a t i o n ，w ep r o p o s es o m es c h e m 豁o fm u l t i c 嬲tm 砸n g 锄d f a u l t r c c 0 v e r y 1 ed e t a j l 勰f a l l o w ： f i r s t l y ，w ep m p o s e dam u l t i c 嬲tr o u t i i l gs c h 锄eb 嬲c do ns i n l c t i i it h j ss c h 锄e ，代e 瑙e c o l o r 酣仃i sb u i l tf i r s t l y ，m 删u l l t i c 勰tf o r w 羽仃c ec 姐b ec o n s 仃u c t e db ys 即d i n gs i l l l p l e m 销s a g eb e t w e 抑on e i 曲b o rn o d 髂i nt l l ec o l o r e d 纽 s e c o n d l y ，w ep r o p o s e dap e n i n ts c h 锄争“l v 龇l c e ds i m c t m u l t i c 嬲tr o u 廿n gs c h 锄e t 0r 骼0 1 v et l l ep r o b l 咖吐l a tt l l es i m c tm u l t i c 酗tr o u t 垴gs c h 锄eh a v em u c h 同岫d 锄c y h l l i ss c h 锄e ，m u l t i c a s tg r o u pm 锄b e 璐c a nj o i na n dl e a v et l l em m t i c 弱t 缸- e ed y n 锄i c a l l y ，肌d t i l er e d u r l d 肌c yo fm em u l t i c 嬲t 仃c 趴b e 孕c a t l yr e d u c e d t h i r d l 弘t 0i i l l p r 0 v et l l er o b 郴n l 鼯so ft l l em u l t i c 弱tr o u t i n gn e “阳r k ，w ep r o p o s e d 柳o f i a u i t 一陀c o v e r ) ，s c h 咖e sp e n i n 饥t l 州i s t r i b u t e df a u l t 托c 0 v e r y 觚dc e n t r a l i z e df - a u l t 他c 0 v e r y s i m u l a t i o ns h o w st l l a tt l l es i n g l en o d eo rl i n kf 撕l u r eo fm u l t i c 嬲tf 0 刑a r d 仃c a nb e 砌v e r e de 仃e 鲥v e l y ，锄dt t l e 柳os c h 锄e sh a v et l l e i ra d v 觚t a g e 锄dd i s a d v 孤t a g e k e y w o r d s ：s i m c t ；c 0 l o r e d 廿c e ；i n u l t i c 嬲t 仃；f a u l t - r e c 0 v e d ，；s i m u l a t i o n 西南交通大学硕士研究生学位论文第1 页 1 1 课题研究背景及意义 第1 章绪论 随着互联网的迅速发展和普及，用户规模不断扩大，带宽需求越来越高，同时人们 对网络上的各种应用如，视频点播、远程教学、远程会议、股票交易、网络交互式游 戏、远程虚拟现实、在线拍卖、分布式交互模拟等分布式的需求也越来越显著。而这 些应用都有一些显著特点： 不同位置的应用可以属于一个组或不同的组，独立的应用可以在任意时间自由 的加入或离开一个组或多个组； 一个组内的任意成员无需保存本组的成员数量和成员地址信息等： 组成员可以向组内其它成员发送数据，非组内成员也可向组内成员发送数据； 向一个组内发送数据，只需要发送一份数据报文即可； 组内成员相互发送数据，组外成员无法接收到数据。 这些特点使得传统的单播和广播已不能很好的支持这些应用，因为单播会占用较多 的带宽资源，对于大规模的通信而言，会有较大的网络负载，而且通过单播方式通信 各网络成员需保存其它通信成员的信息如口地址等，那么所述应用不适合采用单播方 式实现；如果采用广播方式，就会有大量的主机接收到与自己无关的数据，浪费大量 的网络带宽资源。 这种情况下，组播通信方式的应用就显得越来越重要。所谓组播，就是一种一个或 多个源节点将数据以副本形式发送到特定的一组或多组接收者的通信方式和网络技术 【l 】。通过组播通信方式，源节点只需要发送一份数据报文，经过组播分发树中路由器的 复制和转发，将数据报文发送到一组或多组目的节点。与单播通信方式相比，组播极 大的减轻了网络负载，同时减少了网络资源的消耗。 自s t e v ed e 舐n g 博士1 9 8 8 年首先提出组播的网络体系结构以来，随着网络的不 断发展，组播受到越来越多的重视【2 】【3 1 。目前，组播已经成为一个非常大的研究领域， 包括组播路由，组播故障恢复，可靠组播，安全组播，应用层组播等。其中，组播路 西南交通大学硕士研究生学位论文第2 页 由和组播故障恢复作为组播的重要研究领域，国际上许多研究者已经对此做了大量的 研究【4 1 0 】【1 5 砌】【4 0 4 2 】。本文通过一种新的方式，即通过颜色树的方式对组播路由和组播故 障恢复问题展开研究。 1 2 本文的结构安排 本文首先介绍了组播应用的重要性，通过对传统组播路由和故障恢复技术的研究和 分析，在现有技术方案的基础上，提出了新的组播路由方案和组播故障恢复技术方案， 然后对方案性能的优越性及方案的有效性进行了仿真分析。全文结构安排如下： 第一章绪论部分阐述了课题的研究背景及意义： 第二章简要介绍了组播技术中的几种组播分布树方案，并对其所支持的组播路由协 议做了相关说明； 第三章对现有的组播保护技术进行研究和分析，并指出了各技术方案的优缺点； 第四章详细介绍了一种不相交多路径路由算法s i m c t 算法： 第五章通过对s i m c t 算法的研究和分析，根据算法组建的反向颜色树，提出了一 种s 妇c t 组播分布树方案。根据s i m c t 组播分布树方案的缺点，又提出了一种改进的 s i m c t 组播分布树方案； 第六章根据第五章中所提出的两种组播分布树方案的特点，有针对性的提出了两种 故障恢复方案，基于反向颜色树的分布式恢复方案和基于反向颜色树的集中式恢复方 案。同时对这两种恢复方案的单节点保护和多节点保护功能进行了举例论述； 第七章对本文所提出的组播路由方案和故障恢复方案进行了性能仿真分析。 西南交通大学硕士研究生学位论文第3 页 第2 章组播技术 在单播通信方式中，数据报文沿着网络中的单一路径从源主机向目的主机传送，但 是在组播通信方式中，组播源主机为了向所有组成员传递信息，m 组播路由建立一个 从组播源主机到所有接收组成员的无环数据传输路径。组播分布树则用来描述i p 组播 在网络中经过的路径，而组播路由协议则通过信令交互完成组播分布树的构建。 2 1 组播分布树 组播分布树一般分为几种类型：洪泛法，有源树，共享树。 2 1 1 洪泛法 洪泛法是最简单组播路由算法，也叫扩散算法。此算法不构造组播树，其实施过程 如下： 1 ) 具有组播功能的路由器收到从源主机到组播组成员的数据报文； 2 ) 组播路由器判断是否是第一次收到该数据报文； 3 ) 如果组播路由器是第一次收到该数据报文，则将其转发至除该报文接收接口之 外的所有其它接口上，确保其能到达所有的组播组接收成员； 4 ) 如果不是首次收到该报文，则丢弃该组播报文。 洪泛法只需要组播路由器维护一个最近收到的组播报文列表，而不需要维护组播路 由表项。这种方法适用于对组播应用较多的环境中，通过洪泛法的组播数据传输，只 要网络中存在一条到组播接收成员的链路，则组播接收成员就能收到数据报文。但是 洪泛法会产生非常多的组播复制报文，很容易导致网络拥塞，不适用于广域网络中。 洪泛法的网络示意图如图2 1 所示。 西南交通大学硕士研究生学位论文第4 页 2 1 2 有源树 主 主机b ( 接收器)主机c ( 接收器) 图2 1 洪泛法 有源树以最短路径贯穿网络，所以也被称为最短路径树( s p t ) 。有源树的根是组 播信息的来源，有源树的分枝形成了通过网络到达接收站点的分布树。有多少个组播 源就要构造过少棵组播树，其构造过程如下： 1 ) 首先，计算组播源节点与组成员各节点的最短路径； 2 ) 在最短路径链路上复制组播报文，网络中其余链路上则不再复制报文： 3 ) 为每个组成员节点构造一棵最短路径树。 最短路径树易于从单播路由表中计算得到，可有效实现分布式组播通信；同时不同 的组播源节点发送的组播报文被分散到各自的组播树中，有利于网络的负载均衡。但 是，每个组播源节点构造一棵有源树，组播路由器需要为每个源节点维护相关的组播 信息，需要较大的开销。有源树的网络示意图如图2 2 所示( 其中( a ) 为主机a 的s p t ； ( b ) 为主机b 的s p t ) 。 西南交通大学硕士研究生学位论文第5 页 主 主 主机b ( 接收器)主机c ( 接收器) 主机b ( 源)主机c ( 接收器) 2 1 3 共享树 图2 2 有源树 和有源树使用源节点作为信息来源不同，共享树使用网络中的某些节点作为公用 根，该公用跟被称为汇聚点( 1 冲) 或核心。以i 冲为根建立组播树，相同组播组的源 节点将组播信息单播至汇聚点，再有汇聚点将组播信息通过组播树发送到各组播接收 成员。其实现过程如下所示： 1 ) 选择一个组播路由器作为汇聚点l 心； 2 ) 组成员节点向汇聚点l 冲发送加入信息报文； 3 ) 中间组播路由器节点收到加入信息报文，将接收接口标记为属于该组播组的树： 4 ) 如果组播路由器第一次收到该加入信息报文，就向l 冲方向继续转发该信息； 如果组播路由器已是树中成员，则只需再标记一次该接收接口属于该组播组； 5 ) 组播源节点将组播数据单播发送到i 心，再由l 冲通过组建的组播树分发数据报 文至各组播组接收成员。 与有源树相比，只需为每个组播组建立一棵组播共享树，而不是为每个组播组建立 一棵树，适用于大规模的网络或者组播组成员分布较为稀疏的组播环境中。共享树的 西南交通大学硕士研究生学位论文第6 页 网络示意图如图2 3 所示。 主 主机b ( 接收器)主机c ( 接收器) 2 2 组播路由协议 图2 3 共享树 ) 单播可以将数据源端直接路由至目的接收端，而组播中的组播组地址则是虚拟的， 组播应用程序将组播数据发送一组接收成员，而不是单单传给某一目的地址。组播路 由协议建立一个从组播源端到多个接收成员的无环数据传输路径。组播路由器通过不 同的组播路由协议建立多种不同的组播分发树，根据网络的实际情况，组播路由方式 有密集模式和稀疏模式，相应的组播路由协议分为两大类：密集模式协议和稀疏模式 协议。 2 2 1 密集模式路由协议 密集模式中，假设网络中的每个子网中存在至少一个组播组成员，密集模式路由协 议采用洪泛法的方式将数据报文“推”到网络中的所有路由器接口，网络中的任何路由 器节点都知道所有活动的组播源地址与相应的组地址。密集模式路由协议采用这种向 网络所有节点“推”送数据的方式，浪费大量的网络带宽资源，同时增加路由器c p u 的 消耗。为了较少这种相伴的网络资源的消耗，密集模式路由协议通过剪枝的方式，对 西南交通大学硕士研究生学位论文第7 页 没有组播接收成员的分枝进行剪枝操作，只保留有接收成员的分枝。同时，为了使已 经剪枝掉的分枝中有接收需求的接收点可以接收组播数据报文，剪掉的分枝可以周期 性的恢复成接收状态。这种周期性的扩散和剪枝现象是密集模式路由协议的特征。通 常，密集模式路由协议下的组播数据转发路径是以组播源为根节点，组接收成员为叶 子节点的有源树。典型的密集模式路由协议有：p i m d m 【l l 】( 协议无关组播的密集模 式) 、d r p 【1 2 】( 距离向量组播路由协议) 、m o s p f 【1 3 1 。 密集模式协议中的p i m d m ( 协议无关组播密集模式协议) 的工作机制如下： 1 ) 邻居发现 在p m 域中，路由器周期性地向所有p i m 路由器( 2 2 4 0 o 1 3 ) 以组播方式发送 h e l l o 报文，以发现p 蹦邻居，维护各路由器之间的p i m 邻居关系，从而构建和维 护s p t 。 2 ) 构建s p t 图2 4p i m d m 应用示意图 组播源s 要向组g 发送业务报文，初始时，组播报文扩散至网络中的各个角落，每 个路由器收到组播业务报文后，通过对该报文进行r p f 检查，创建相应的( s ，g ) 表 西南交通大学硕士研究生学位论文第8 页 项记录报文的输入接口，将其它接口作为输出接口，并将组播报文扩散至所有输出接 口。如图2 4 所示，路由器c 将会收到上游路由器a ，b 的业务报文，但是只能有一 个输入接口，路由器会根据单播到源的耗费选择耗费值最小的作为输入接口，另一个 则向上游路由器发送剪枝报文。 当路由器发现自己没有下游接收者时，将会向上游节点发送剪枝报文，通知上游路 由器节点删除相应的( s ，g ) 表项中对应的输出接口，并不再向该路由器发送组播报 文。如图4 中路由器i 发现没有下游接受者，则向上游路由器节点e 发送剪枝报文，e 收到剪枝报文后剪出相应的接口。e 剪枝之后，发现已无下游接收者，继续向上游发 起剪枝请求。剪枝过程由叶子路由器发起，剪出网络中无组播接收者的多余分枝，一 直持续到p 蹦d m 域中只剩下必要的分枝，这些分枝共同构成s p t 。 3 ) 嫁接 当被剪枝的路由器节点出现组播组成员时，为了减少该节点恢复成转发状态所需要 的时间，p i m d m 使用嫁接的方式向上游路由器节点发送嫁接报文，恢复其组播转发 功能。 4 ) 断言 在一个网段内如果存在多台组播路由器，则相同的组播报文会被重复发送至此网段 内。为了避开这种多次接收相同报文的情况，需要有断言机制来选择唯一的组播数据 转发路由器。如图4 中，路由器e 可能接收到来自路由器c 和路由器d 的组播扩散业 务报文，会出现数据冗余。路由器c 和d 之间需要进行一场断言过程，以选出唯一的 组播转发路由器。断言比较规则如下： 到组播数据源的单播路由的优先级较高者获胜； 如优先级相同，则到组播源的度量值较小者获胜； 优先级和度量值都相同者，口地址较大者获胜。 2 2 2 稀疏模式路由协议 西南交通大学硕士研究生学位论文第9 页 稀疏模式组播假设网络中的组播成员稀疏分布，且所有成员都不需要接收组播数 据，只有明确指定接收的组播成员才会转发组播数据。这种模式下的组播组用户不一 定很少，分布范围却可能很广。 稀疏模式组播路由协议选择一个组播数据汇聚点( r p ) 作为组播分发树的公用根， r p 向全网通告自己的地址信息。如果用户想要接收组播数据，则必须向汇聚点发送加 入报文，通过“拉”的方式接收组播数据，加入报文经过的路径就变成了共享树的分枝。 组播源端通过单播方式将组播数据发送到r p ，组播数据到达l 强后组播数据报文被复 制沿着共享树分发到网络中的组播成员接受者。同时，为了避免共享树中的分枝由于 没有更新而被删除，稀疏模式组播路由协议通过周期性的发送加入报文来维护组播分 发树。典型的稀疏模式组播路由协议是稀疏模式下的协议无关组播( p i m s m ) 4 1 。 稀疏模式下的协议无关组播p m s m 通过建立组播分发树来转发组播数据报文，通 过显式的加砧剪枝机制来完成组播分发树的建立和维护。 图2 5p i m s m 应用示意图 如图2 5 中，当d r 路由器直连的网络中有组g 的成员时，d r 向着l 冲方向发送 加入报文加入组播共享树( 图标l 所示) ，组播加入报文向上游发送过程中，沿途路由 器建立组播转发状态( 图标2 所示) 。 西南交通大学硕士研究生学位论文第10 页 组播源向组成员发送数据时，将数据封装在注册消息内，并有d r 路由器单播至 皿( 图标5 所示) ，l 冲收到注册消息后解封装成数据包沿共享树发送至各组播组成员。 之后l 冲可以朝着组播源方向发送特定的加入消息，加入这个源的最短路径树( 图标3 、 4 所示) ，这样组播源的数据将不加封装的发送至l 冲。 西南交通大学硕士研究生学位论文第11 页 第3 章组播保护算法 组播数据通过组播分发树传送到各组接收成员，树中的节点或链路发生故障后，将 会影响其下游所有接收成员的正常通信，因此组播通信的故障保护方法复杂与单播通 信的故障保护方法。按照备用路径的建立与故障发生时间的关系，通常可以将组播路 由保护方法分为主动式和被动式方法。被动式是在故障发生后，由故障检测节点检测 到故障后，利用可用的资源建立备用路径，已经有许多路由协议使用了这种方式 【1 1 】【1 2 】【1 3 】【1 哪不需要提前预留网络资源，减少了网络资源的开销，但是其恢复时间相对较 长。对于主动式方法的研究较岁1 5 】【16 】【1 7 1 ，这种方式在网络节点故障前，为工作路径预 先建立备份路径，故障发生后可快速恢复，对网络通信有较好的保护。这里主要介绍 主动式方法中的链路保护、路径保护、双树保护、双森林保护和冗余树保护等组播保 护方法。 3 1 链路保护和路径保护 链路保护方法【1 5 1 中为每两个节点间的链路预先建立一条备份的链路，如果组播通 信树中链路出现故障，故障检测节点通过本地恢复，将组播数据绕过故障链路送到故 障链路的下游节点。如图3 1 中所示，为保护节点1 到节点4 之间的链路( 1 _ 4 ) ，建 立了一条备份链路( 1 _ 3 _ 6 _ 4 ) 。当链路( 1 _ 4 ) 发生故障失效后，节点l 检测到故 障后，激活备份链路( 1 3 6 _ 4 ) 将组播数据绕过故障链路，通过节点3 ，6 发送到 节点4 。 西南交通大学硕士研究生学位论文第12 页 3 3 图3 1 链路保护 s2 图3 2 路径保护 路径保护方法是为每个组播组成员建立一条从源端到目的端的备用路径，这条路径 与组播树中从组播源到目的端的路径是不相交的。如组播树中链路或节点发生故障后， 有故障节点的下游节点检测到故障后，通知下游各组播成员组播通信失败的消息，各 下游组播成员将激活预先建立的到源端的备份路径，从而恢复组播通信。如图3 2 示 例，为了保护组播成员节点6 ，建立了一条从源端到节点6 的备份路径( s _ 9 _ 6 ) ，此 备份路径与从组播源到节点6 的路径( s _ l - 4 _ 6 ) 是不相交的。当组播树中链路( 1 _ 4 ) 发生故障，节点4 检测到故障后，将失败消息通知给下游节点6 ，节点6 激活备用路径 西南交通大学硕士研究生学位论文第13 页 ( s 一9 6 ) ，组播数源将数据从( s 一9 6 ) 发送到节点6 ，从而绕过故障链路。 3 2 双树保护 双树保护算法 1 7 】区别与链路保护和路径保护方法，这种方法通过连接组播树中的 叶子节点，而不连接主树上的任何内部节点或链路来建立一棵次级树。双树方案要求 其网络拓扑是双向连接的，且在任意两个节点间有至少两条节点不相交或链路不相交 的路径。双树保护算法如下： 1 ) 正常组播通信时，组播数据流量通过主树传送，主树上的叶子节点叫主叶： 2 ) 如果主树上的一个节点x 检测到它的双亲节点故障或者其连接双亲节点的链路 故障，则将所有主叶节点划分为两组：受故障影响的节点划到组a g ，未收故障影响的 节点划入组n g ； 3 ) 选择一个组a g 中节点y ，此节点与组n g 中一节点通过次级树有链路连接( 或 通过其它中间节点连接) 。节点y 通过路径p 连接组n g 中节点z ； 4 ) 节点x 发送一个重配置消息到它的孩子节点，并更新它的父节点为孩子节点。 重配置消息沿主树路径一直发送到节点y ，每个收到重配置消息的节点都将更新其父 节点为其孩子节点。重配置消息沿着路径p 一直发送到节点z ，对应的状态也被保存 在中间节点。 双树保护结构如图3 3 所示，实线代表组播主树路径，虚线代表次级保护树路径， 所有的链路都是双向的，箭头代表组播树的方向。假设链路( 2 _ 5 ) 发生故障，节点5 检测到故障发生，将节点7 ，8 划入到受影响的组a g ，节点3 ，6 划入未受影响的组 n g 。受影响组a g 中节点7 通过路径( 7 _ 9 6 ) 连接到未受影响组n g 中节点6 ，重 配置消息从( 5 _ 7 _ 9 _ 6 ) 发送到节点6 。故障恢复后如图3 4 所示，到节点5 的组播 路径变成了( 6 9 7 _ 5 ) ，节点8 仍是节点5 的孩子节点。 西南交通大学硕士研究生学位论文第14 页 s 图3 3 双树结构示例 图3 _ 4 双树保护恢复后的组播树 双树保护算法可以有效的保护单链路故障，对于单节点故障则不能很好的保护。如 图3 5 所示如节点a 发生故障，节点c 和节点d 检测到故障发生，各自使用双树保护 算法进行故障恢复，节点d 计算a g 中的受影响节点为d ，n g 中未受影响的节点为b 、 e 、f ，选择a g 节点d 沿( d f ) 发送重配置消息到n g 中节点f 。节点c 使用双树 保护算法，计算a g 中的受影响节点为e 、f ，n g 中未受影响的节点为b 、d ，只有选 择节点f 沿路径( f d ) 发送重配置消息至n g 中节点d ，从而导致组播成员节点d 、 e 、f 无法与组播源s 连接。 西南交通大学硕士研究生学位论文第15 页 3 3 双森林保护 图3 5 节点故障下的双树保护 d 双树保护算法对节点故障不能提供很好的保护，对此，文献【1 8 】提出了改进的双森 林保护算法。同双树保护算法一样，双森林保护算法通过连接非主组播树内部链路或 节点来构建保护路径，而且保护路径可以不相互连接，用一个森林来保护组播通信。 双森林保护算法中，故障检测节点x 检测到上游故障后，将组成员分为三部分： 受故障影响的组成员节点a g 一以节点x 为根的组成员节点；可能受故障影响的组 成员节点p g 一以x 父节点为根且不属于a g 的组成员节点；未受故障影响的组成员 节点n g 一其余节点。 算法l 节点x 检测到故障发生 1 ) d e d u e t s ( x ，t p ，a gp gn g ) 节点x 检测到故障发生，推导出相应主树t p 的a g 、p g 、n g ； 2 ) d c d u c o h l pp a m ( f d ，a 1 3 lp 1 3 ln qb p ) 寻找属于双森林f d 且连接a g 和n g 的最短路径b p ；如果此路径不存在，则寻找 一条连接a g 到p g 的最短路径作为b p 的一部分；如果找不到任何路径，就将b p 设为 西南交通大学硕士研究生学位论文第16 页 无穷大； 3 ) 如果b p 为无穷大，则双森林恢复失败，返回； 4 ) s p l i l j a c k u p j ，a t h ( p gb p ) 如果b p 包括p g 中的节点，将连接a g 节点到紧邻的p g 节点的最短子路径分配给 b p ；如果b p 不包括p g 中的节点，则不做任何动作。 5 ) e x 仃锄i t i 骼c b p ，e 1 ，e 2 ) 最短路径b p 一端的节点定义为e l ，另一端为e 2 ； 6 ) c r e a t e j 己f i g - j 1 1 e s s a g e ( x t p ，b p ，u n s 曲 创建配置信息。主树t p 上从节点x 到e l 的所有节点加入到重配置消息歹! j 表r - m s g 中，后续从e l 到e 2 的节点也被加入到r _ m s g 中； 7 ) s e i l d r o n f i g _ j i l e s s a g e ( x r _ m s g ) 发送重配置消息。将r m s g 发送到节点x 的重配置列表中的后继节点跚c “x ， r - m s g ) ； 8 ) p a i i “x ，t p ) 卜跚c c ( x ，r j m s g ) r _ m s g 列表中节点x 的后继节点变为新的主树t p 中的父节点； 9 ) d e l c h i l d ( x ，t p ，姒似x ，r _ 卫s g ) ) 将节点x 孩子列表中的跚c “x ，s 曲删掉。 算法2 节点y 接收到重配置消息 1 ) 如果节点y 不为e 2 ，发送配置消息到其后继节点s u c c ( x ，r - m s g ) ，并将叭c c ( x ，r - m s g ) 转为节点y 的父节点，删除节点y 的孩子节点跚c “x ，r _ m s g ) 选项； 西南交通大学硕士研究生学位论文第17 页 2 ) 主树t p 中，节点y 的原双亲节点变为y 的孩子节点。 故障前的双森林保护结构示例如图3 6 所示。假如节点a 发生故障，其下游节点c 和d 将检测到故障。节点d 检测到故障后，将d 划分到a g ，e 和f 划分到p g ，b 划 分到n g ，假设节点d 先于节点c 执行保护算法，则执行算法后的组播流量示意图如 图3 7 ( a ) 所示。节点c 检测到故障后，将e 、f 划分到a g ，d 划分到p g ，b 划分 到n g ，最终的执行双森林保护算法后的组播流示意图如图3 7 ( b ) 所示。 图3 - 6 故障前的双森林保护结构示例图 ( i ) d 执行算法盾c 检测到故障前 3 4 冗余树保护 图3 7 执行双森林保护算法后组播流示例图 冗余树保护算、法【1 6 】中除了在网络中组建一棵从组播源到所有组播接收成员的主树 外，还需要预先组建一棵从组播源到组成员的备份冗余树，且备份冗余树与主组播树 是路径不相交的。冗余树算法要求网络须是2 连接的，即从一网络节点到另一网络节 西南交通大学硕士研究生学位论文第18 页 点至少有两条通过不同节点的路径。冗余树算法如下： 1 ) 在网络中搜索一个任意的环路径( 毋1 ， ，j ) ，勉。将( 岛y 厶场，j ) 中节 点放入集合n 1 中，路径j 一，广，也_ 一v 七加入到蓝树b l u e 中，路径 j _ 附_ j 叶_ v ，加入到红树r c d 中，且为各节点分配权值 胗y 一 1 ， 1 ，m d ； 2 ) 如果n l 包括网络中所有节点，算法终止； 3 ) 选择一个路径( 五c 锡，c 砂) ，贬l 。节点x 与y 为属于集合n l 中不同的节点， 将节点( 五c j ，锄叫) 按顺序放入集合n l 中，路径x c j _ q _ _ “加入到 蓝树b l u e 中，路径尸钳一作j _ _ c j 加入到红树r e d 中，为各节点分配权值 1 ，似 ，和 1 ，m ，m 砌倒，菇砌倒为集合n l 中小于节点x 权值的最大 值权值。 4 ) 转到步骤2 ) 。 图3 8 冗余树算法示例图 冗余树保护算法通过搜索路径将网络中所有节点连接起来，适用于组播数据传输， 使组播源发送的数据可以到达网络中的各个节点。冗余树算法中组建两棵颜色树，b l u e 和同树，将其中一棵作为主组播树，另一棵作为备份组播树，当主组播树上链路或节 点发生故障时，组播数据将沿备份树转发到组播接收成员。冗余树算法示例如图3 8 所示，图中标号为 1 ) 的路径为首次搜索的一个环，将路径口_ 6 一c 一扣p 巾g 加入 蓝树，路径口_ p 卢p _ 扣c _ 6 加入红树：标号为 2 的路径为搜索的一条路径，通 西南交通大学硕士研究生学位论文第19 页 过算法将路径口_ j j l 加入蓝树，路径6 加入红树。图中蓝色标识为b l u e 树，红色标 识为r e d 树。 这种冗余树算法的路径搜索，使整个网络中的所有节点都包括进来，对于组播应用 来说，组建的组播分发树太过冗余，因此文献【1 9 1 2 0 】中提出了一种改进的冗余树算法， 路径搜索过程中，只要搜索的节点将所有组成员接收节点全都包括，那么就结束搜索， 这种方法节省了算法运行的时间，同时组建的组播通行树相对来说不再那么冗余。还 有一些工作2 1 】【2 2 】【2 3 】【2 4 】，对于冗余算法进行了q o s 约束，在算法中加入带宽、延时、 开销等相关条件，来建立冗余保护树。 西南交通大学硕士研究生学位论文第2 0 页 第4 章不相交多路径路由算法s i m c t 算法 在网络中使用不相交多路径路由可以提高网络的健壮性【2 5 1 ，使网络负载均衡【2 6 1 ， 减少网络拥塞【2 7 1 ，提高网络的安全性【2 9 】和能量的有效性【2 8 1 。在网络拓扑环境中，通常 从一个源节点到一个目的节点可以有多条路径，如果有足够的网络资源这些路径可共 享同一链路或节点，但是为了提高网络数据传输的可靠性和避免共享链路或节点的失 败，这些路径则应该是节点或链路不相交的。 对于节点或链路不相交的多路径路由的研究已做了大量工作【3 0 】【3 l 3 9 1 ，多路径路由 【3 5 】【3 6 】【3 7 】【3 8 】多用来对网络中节点或链路失败进行保护，以其中一条路径做为主路径，其 余路径作为备用路径，如果主路径中链路或节点发生故障，则数据将会通过备用路径 传输，节点或链路不相交的多路径路由则要求主路径和备用路径是不相交的。颜色树 是一种使用最小的路由表项开销和查询时间实现节点或链路不相交的多路径路由方法 【3 2 】【3 3 】【3 4 3 9 1 。颜色树方法中，网络中的每个节点都有两个到目的节点的最优邻居：红色 ( 同) 和蓝色( b l u e ) ，在源节点数据报文被标记为这两种颜色中的一种，中间节点通 过识别接收数据报文中的颜色标记，将数据报文转发到标记颜色相应的邻居节点。通 过这种多路劲路由方法，网络可以视为以目的节点为根节点的两棵树( 红树和蓝树) ， 并且任意源节点通过两棵树到目的节点的路径是节点或链路不相交的。网络中每个节 点都可以视作一个目的节点，用颜色树方法可以使网络任意点到点都有不相交的多路 径路由。 为了提高网络的健壮性，文献【3 3 1 中提出了一种基于颜色树的多路径路由算法 s h c t 算法，算法要求网络须是2 连接的，即点到点之间至少有两条通过不同节 点的路径。s i m c t 算法分为三个阶段： 1 ) 从网络中一节点出发，采用d f s 深度优先搜索方法搜索路径，并为每个贯穿的 节点分发d f s 索引号和计算其全局低点值； 2 ) 为网络中节点进行逻辑分层； 3 ) 为每个节点选择最优的两个邻居，即左转发节点( b l u e ) 和右转发节点( r 酣) 。 不相交的多路径路由分为节点不相交和链路不相交，此处只介绍通过s i m c t 算法 西南交通大学硕士研究生学位论文第2 1 页 建立的节点不相交路由。节点不相交的定义如下： 如果从节点s 到节点d 的r e d 树路径穿过节点i ，那么从节点s 到节点d 的b l u e 路径则不会穿过节点i ，如协) 和v f r p ，d ) ，则 4 1 分发d f s 索引号 f p 三j ( f 仨p 三) s i m c t 算法的第一阶段是为网络中的各节点分发d f s 索引号和计算节点的全局低 点值。这里的全局低点值的定义是指节点x 通过贯穿一系列的节点所能达到的d f s 索 引值最小的节点的索引号，即g l p v ( x ) = i i l i n ( d f s 索引号) ，到达全局低点通过的节点中， 除最后一跳外，其余d f s 序号是递增的。具体算法伪代码如图4 _ 2 所示，算法中所使 用的符号如图4 1 所示。 c 0链路x y 的开销 a 扮0 一节点x 的d f s 序号 p 扫吵 节点x 的d f s 路径上的双亲节点 鲥融，似节点x 的全局低点值 g 勿一0 眇节点x 的全局低点邻居 鲥p 俐节点x 到达低点的最短距离跳数 p d f 西一节点x 的势值 榭 分配给节点x 的层 伽似节点x 的左转发节点 咖似节点x 的右转发节点 图4 1s i i n c t 算法中使用的符号 西南交通大学硕士研究生学位论文第2 2 页 d f s ( p a r 饥t ，n ，c u n d f s ) i fd f s ( n ) 0 陀t i l mc u r r d f s ： d f s ( n 户c u r r d f s ；d f s p a 托n t ( n ) = = p a 托n t ； 盯d 6 = 删删f 计l ； f o r e v e 叮n e i g l l b o r i p a 姗t o f n d o ： 3 a c u 玎d f 婷d f s ( n ，i ，c l l 盯d f s ) ； 3 b i 足d f s ( i ) d f s ( n ) ) a n d ( d f s ( i ) d f s ( n ) ) a n d ( g l p v ( i ) d f s ( n ) ) 锄d ( g l p “i 户g l p v ( n ) ) 锄d ( g l p d ( i ) g l p d ( n ) c n i ) 3 d i g l l m ( n 户i ；g l p d ( n 产g l p d ( i ) 。h c n i ； 4 玎e t i l mc u n - d f s ： 图4 _ 2 分发d f s 序号和计算全局低点值算法 如图4 3 ( a ) 所示为一个网络拓扑示例图，以其中一节点d 为目的节点执行算法的 第一步，即进行d f s 全局搜索，分发d f s 索引号和计算全局低点值。得到如图4 - 3 ( b ) 所示，图中实线表示d f s 搜索路径，节点上的标号为d f s 索引号，括号里的值为每个 节点的全局低点值。如2 ( 1 ) 表示此节点的d f s 索引号为2 ，全局低点值为l ，从此节点 到达全局低点的路径为( 2 3 _ 4 一1 ) ；同样地，8 ( 4 ) 表示此节点d f s 索引号为8 ，全 局低点值为4 ，到其全局低点路径为( 8 _ 4 ) 。 ( i ) 网络拓扑示例 4 ( i 双4 ( b ) d f s 索引号和脚p v 值 图4 3 网络拓扑示例和分发d f s 索引号 4 2 网络节点的逻辑分层 西南交通大学硕士研究生学位论文第2 3 页 算法的第二个阶段是为网络节点进行逻辑分层，将节点划分为o d d 层和e v 层。 为了限制每一层节点的全局低点值，此处定义一个势值( p o t 饥t i a l ) 术语即同一层节 点的全局低点值的上限。节点x 的势值表示为p o t ( x ) ，根据全局低点值g l p v ( x ) 和势值 p o t ( x ) 的关系为网络节点进行逻辑分层。 势值计算规则如下： 倒黜 酬戈) 由于g l p v ( 2 ) = l ，将节点2 划分为紧邻节点l 的e 、，铋层，势值p o t ( 2 ) = l ，并转 发自己的势值到孩子节点3 ；因g l p v ( 3 ) = l ，哲p v ( 4 ) = 1 ，将节点3 、4 划分到与 节点2 相同的e v 肌层，节点4 转发自己的势值p o t ( 4 ) = l 到孩子节点5 。 g l p v ( 5 ) = 2 p o t ( 4 ) = l ，根据分层规则，将节点5 划分到节点4 所在层的下一层( o d d 层) ，势值p o t ( 5 ) = 4 ；g l p v ( 6 ) = 3 g l p v ( 7 ) = 4 p o t ( 5 ) = 4 ，节点7 划到节点5 的下一层e v 饥层，势值p o t ( 7 ) = 5 ； 西南交通大学硕士研究生学位论文第2 4 页 g l p v ( 8 ) = 4 节点9 划分到o d d 层( g l p v ( 9 ) = 7 之p o t ( 8 ) = 5 ) ，节点1 0 、1 l 划分到与节点9 相同 的o d d 层。 g l p v ( 1 2 ) = 8 p o t ( 1 1 ) = 8 ，节点1 2 划分到e v 层。 根据上述逻辑分层，图4 3 示例中的网络节点最终的分层结果如图4 4 所示。 4 3 选择转发节点 图“网络节点的逻辑分层 8 算法的第三阶段是为网络中的每个节点选择到根节点( 目的节点) 的左转发节点 ( b l u e ) 和右转发节点( 川) ，即选择最优的两个邻居节点。 如节点x 在e v 饥层，那么节点x 的左右转发节点为 蜘= 反功咖= 咖( 习( 4 ) 如果节点x 在o d d 层，贝u 有 ( 5 ) 式( 4 ) 与式( 5 ) 中l f i l ( x ) 为节点x 的左转发节点，而( x ) 为节点x 的右转发节点，g i p n ( x ) 一 一 一 一 一 一 西南交通大学硕士研究生学位论文第2 5 页 为节点x 到其全局低点路径中x 的邻居节点，p ( x ) 为d f s 路径上节点x 的父节点。 图4 5 左转发树( b l u c 树) 图4 6 右转发树( r e d 树)