基于相交多路径的组播主动式恢复方案*

王肖楠，程东年，张建辉

（国家数字交换系统工程技术研究中心，河南 郑州 450002）

网络的一个重要问题是可生存性(survivability)。可生存性是指系统在攻击、故障、意外事件影响下能够及时完成任务的能力。网络的可生存性又称为网络快速恢复能力，用于描述一个网络在应对节点或链路失效时的性能。有两类方法可以提供网络的快速恢复能力。一种方法称为被动式(reactive)恢复，又称为按需(on-demand)恢复，当网络中检测到故障时，绕过故障的链路/节点，重新寻找新的路由来完成服务的恢复[1]。该方案的主要缺点是恢复延迟漫长，不利于很多即时通信。另一种方法是主动式(preactive)恢复，它预先计算两条不相交的路径，一条被指定为主路径,另一条是备用路径[1]。当主路径因其中的链路或节点故障而失效时，备份路径被激活，自动成为新的主路径。对比于被动式恢复方法，该方法能够减少恢复时间，但在很多情况下，它需要执行复杂的恢复操作和花费较多的网络资源。

组播是一种一对多的传输方式，需要将数据同时从源发送到一组目的主机。设计组播通信的快速恢复方案更富有挑战性，因为一个链路/节点的失效将会影响到很多组播目的主机。许多文献都提出了针对单一节点/链路失效提供保护的组播主动式恢复方案，这些方案要求计算从数据源到目的地的不相交的多条路径。目前广泛受到关注的两种保护方案是：局部保护方案和组播组保护方案。两者的保护范围不同，前者是按照单播主动式故障恢复方案将多播树中源节点列目的节点的路径抽取出来，并分别为它们建立保护路径；后者则是通过计算两个链路不相交组播树，其中一个作为主要的组播树，而另一个作为备份组播树，以整个组播树为保护对象。

以上两种方案均存在不足：局部保护方案需要较高的维护与管理代价，而且可能出现路由环路；组播组保护方案近年来研究得比较多，然而,找到两个链路/节点不相交的两棵组播树在大型组播通信中是很困难的，甚至是不可能实现的。

针对现有方案中不相交的多路径构建成功率低下的不足，本文提出一种基于相交多路径的组播主动式恢复方案。该方案通过为组播树中的节点备份父节点的方式，使得各个组播组成员通过多条相交路径连接到组播源。当发生故障时，路由可以快速地切换到未受故障影响的父节点，进而完成组播路由的快速恢复。

1 背景和相关工作

虽然目前对组播通信的故障恢复的文献中很少提及，但其必将成为未来通信网络的一个重要部分。在常规的组播中，数据流分布在整个树结构上，一个故障就会影响到故障点下游的所有组成员。目前组播主动式恢复方案的研究中，有些借鉴单播中链路恢复和路径恢复的方案，应用于保护组播树中的源到每个目的地的路径[2,3],有些利用冗余树[4]或者双树[1]方案。图1给出四种主要的组播主动式恢复方案的实例。图中，S是源节点，实心的节点是组播组成员。粗实线代表缺省树中的链路，虚线代表在备用路径的链路。不同类型的箭头表示数据流在缺省树或激活后的备用路径中的传输方向。

WU C等[2,3]研究了链路保护和路径保护方案。在链路保护中，每条链路的两个端节点之间设置了一个备用路由。在路径保护中，为每个目的地计算一条备用路由，该路径与组播树中从数据源到目的地的路径是节点不相交的。

图1(c)给出了一个简单的“冗余树”(redundant tree)方案[4]的例子。“冗余树”方案要求网络拓扑结构是一种双连通图，即任何两个节点之间至少有两条节点不相交或者链路不相交的路径。如果缺省树和备用树只是链路不相交，则它是一棵链路不相交的备用树；否则，称其为节点不相交备用树。“冗余树”方案提出的算法可以计算两棵不相交的组播树，使得消除网络中任何节点 (链路)，目的节点都可通过至少一棵树连接源点。因此，冗余树方案可以恢复缺省树中出现的任何链路或节点的故障，并可恢复不止一个故障。

在更近的研究中,FEI A等人提出 “双树”(“dual tree”)方案[1]。第二棵树是为有容错需求的组成员建立的备用树，而不是为了单独保护组播树中每一个链路或组成员。图1(d)就是一个节点不相交备用树的示意图。

2 基于相交多路径的组播主动式恢复方案

2.1 方案的动机

上文描述了现有的组播主动式恢复方案，在管理开销和网络连通性要求方面对它们进行深入的比较，如表1所示。

表1 现有组播主动式恢复方案对比

对每条链路/路径单独进行保护的局部保护方法会增加管理开销。换句话说，它们在每个组播组中单独计算和维护每一条链路、路径的备份路由。当检测到网络故障时，备份路由也需要单独的链路/路径的维护和激活，包括备份路由的计算成本和恢复开销(由备份路由激活时的信息交流引起的)。因此，当网络中有大量的组播组时，维护和激活成本变得很高。

以组播组为单位进行保护的方案在管理开销上少于局部保护方法，但却对网络连通性有特殊要求。现实的网络并不能保证为双连通网络，因此，不相关双树的构建存在失败的可能性。本研究在节点个数为100、平均节点度为4～5的随机网络拓扑 （随机拓扑的产生见第3节）的仿真中，针对不同的组播规模，分别对构建链路不相关和节点不相关的两棵组播树进行了100次试验。从仿真结果（如图2所示）可以看出，构建两棵不相关的组播树的成功率极为低下：组成员数目为5时，链路不相关双树的平均构建成功率仅为53%，随着组成员数目的增加，平均构建成功率逐渐下降，当组成员数目为30时已降为7%；节点不相关双树的情况更为严峻，平均构建成功率均低于链路不相关双树，组成员数目为30时，节点不相关双树几乎无法构建成功。虽然成功构建不相关双树可以为组播组提供100%的保护，然而，一旦构建失败，依靠不相关双树的快速自愈方案的保护能力瞬间下降为0%。

现代网络可以不再将保护方式限制于两个极端的情况：0%保护或100%保护。事实上，应通过某些共享的链路建立从数据源到目的地的多条路径来提供保护[5]。如果在这些路径中的不相交链路中有一个链路故障，则方案为组播通信提供了保护；如果由于网络拓扑的极端情况而无法找出不相交路径，方案就不能为其中共享链路的故障提供保护。因此，基于相交多路径的组播路由可以有效地适应网络拓扑，为组播通信提供最大限度的保护。

2.2 方案的描述

针对不相关双树构建成功率低下的问题，本文提出一种基于相交多路径的组播主动式恢复方案。该方案在同一时刻为组播树中每个节点尽可能提供两个父节点（连接不同的邻居节点并且使用不同的物理连接）用于接受组播数据。通过这种方式，各个目的地通过多条相交路径连接到组播源，降低了网络连通性的要求。另外，节点可以在路由故障时本地处理，非常快速地将数据流切换到仍然可用的父节点进行接收。这种本地的处理比任何需要多种原理和多种信息交换的分布式处理要快速许多。

图3为基于相交路径的组播路由的一个例子。假设H1是组播通信的数据源；H2和H3是两个目的主机。图中粗线表示本方案建立的相交多路径。由于网络拓扑的限制，有的目的主机(如 H2)可以得到100%保护，有的主机(如H3)只能得到部分保护。可以看出，相交多路径保证了构建成功率并为组播路由提供一定程度的保护。

本方案包括相交多路径构建算法与恢复消息处理算法两部分。组播通信中所用的组播树和备份路径的计算采用本方案中的相交多路径构建算法；当组播树中的路由发生故障时,备用路径的激活采用恢复处理算法。

2.2.1 相交多路径构建算法

相交多路径构建算法为树中节点提供两个父节点，其中一个作为缺省父节点，另一个作为备用父节点。通过这种方式构建组播源到各个组成员的多条相交路径。对于每个组播组(Si，Gi)，其中，Si为组播源，Gi为组播组成员集合，相交多路径构建算法由节点Si采用集中式计算，伪代码描述如下：

算法1相交多路径构建算法

(1)initialize

{初始化集合 Ni(Si)，记录所有与 Si直连的节点；初始化链路集合 R(Si)、节点集合 L(Si)并置为空；}

(2)for网络中不在Ni(Si)中的每个节点Ai(除去组播源Si)

{检查Ai是否和 Ni(Si)中两个或两个以上的节点直连；}

(3)if yes

{随机选择其中一个节点作为 Ai的缺省父节点，另选择一个节点作为Ai的备用父节点,将链路加入到R(Si)，并将节点加入到 L(Si)；}

(4)else

{检查Ai是否属于 Gi;}

(5)if yes

{将 Ni(Si)中与 Ai直连的节点作为 Ai的父节点，将链路加入到 R(Si)，并将节点加入到 L(Si)；}

end if

end if

(6)repeat step2

{重复 step2，直到 Gi中所有节点都在 L(Si)中；}

(7)delete useless node

{检查Ni(Si)中节点是否存在无下游节点且本身不属于 Gi的节点;}

(8)if yes

{将节点从Ni(Si)中移出，并将与之相连的链路从 R(Si)中移出;}

end if

2.2.2 恢复消息处理算法

当组播树中的路由发生故障时，恢复消息处理算法由检测到故障的子节点发起，创建恢复消息激活备用父节点。收到恢复消息的节点依次激活备用父节点，直到再次连接到组播树中。伪代码描述如下：

算法2恢复消息处理算法

(1)if检测到与父节点的通信故障

{切换备用父节点为新的缺省父节点，并向备用父节点发送恢复消息Restore_message((Si,Gi),address)，其中address为本节点地址}

end if

(2)if收到Restore_message((Si,Gi),address)

{检查本节点是否处于(Si,Gi)的组播树中；}

(3)if yes

{将address加入到本节点的子节点集合中，不再向备用父节点发送恢复消息；}

(4)else

{将address加入到本节点的子节点集合中，将备用父节点设置为缺省父节点，并向备用父节点发送恢复消息 Restore_message((Si,Gi),address),此处 address设置为本节点地址；}

end if

end if

算法可以处理节点故障：节点的故障可以表示为与之直连的链路全部发生故障的情形，受到影响的子节点不需要判断故障类型，而只需要通过备用的父节点激活备用路径，恢复后的路由自然绕过了故障的节点。

3 仿真与性能分析

本文致力于组播路由快速恢复方案的研究，关注方案下述几个方面的性能：首先是快速，从检测到故障到备份路径被激活的时间称作故障恢复时间[2]。很显然，恢复时间越短就意味着通信更少的中断。其次需要关注的是组播树的代价，包括缺省树的代价和恢复后组播树的代价两个部分。缺省树的代价反映组播传输的性能，决定本方案是否可行；恢复后的组播树一般比原来组播树有一定代价的增加，代价的增加反映了恢复的质量。因此，以平均恢复时间、缺省组播树的代价、恢复后组播树的代价这三个重要度量作为评估标准，将本方案与现有的方案进行仿真对比。

现有的组播主动式恢复方案与本文提出的相交多路径方案均是基于路径备份的思想。在本方案中，备用路径通过节点维护备用父节点的方式构建，当检测到故障时，恢复消息一次激活各个备用父节点进而激活整个路径，恢复的时间涉及到每个节点的消息处理和父节点配置。正因如此，在仿真中，用恢复信息激活备用路径时通过的节点数量来衡量恢复时间。仿真中，每条链路的代价被配置为1，这样组播树的代价就是树中链路的总个数。

本方案使用参考文献[6]的方法产生随机网络。首先在30×30的网格中随机选择 100个网络节点；然后根据概率 p(u,v)=λexp(-d(u,v)/ρL)选择两个节点 u和 v之间是否直连；其中，d(u,v)是 u和v的几何距离，·g是任意两个节点之间的最大距离，λ和ρ是常数（0<λ，ρ<1）。在随机网络中，选定 λ=1.5 和 ρ=0.3，平均节点度在4和5之间。

[1]已对链路/路径保护方案和“双树”方案在故障恢复时间和故障恢复后组播树的代价增加两方面进行了性能比较。在随机网络中的仿真结果表明“双树”方案优于链路/路径保护方案。因此，在本文中，除了相交多路径方案以外，还对在第1节介绍的另外2种方案进行了仿真：“冗余树”方案和“双树”方案。在仿真实验中，随机生成一个组播组，它由随机选择的一个组播源节点和多个组播组成员节点构成。三种方案各自计算缺省组播树和备用路径，记录缺省树的代价。另外，随机选择组播树中的一个链路作为故障链路，应用三种方案的恢复过程。恢复完成后，记录恢复时间和恢复后组播树的代价。笔者进行了100次重复实验，将所关注的3个度量取平均值进行比较。

图4显示出网络中不同组播规模下的平均恢复时间。其中，“冗余树”方案的平均恢复时间最长，它反映了端到端的路径备份会显著延长激活备份路径的过程，因为故障点首先要通知所有故障点下的目的节点，然后才进行重新连接。本方案平均恢复时间稍短于“双树”方案，原因是本方案在出现故障时进行本地处理，直接发起备用路径的激活过程，而“双树”方案要对故障点以下的部分中间路由器和组播组目的节点进行操作。从需要操作的节点的数量来说，本方案远小于其他两种方案，因此，恢复操作所需的时间也就非常小。另外，从图4中可以看出，本方案和“双树”方案的平均恢复时间会随着组播规模的增加而降低，但是“冗余树”方案则不会。原因是更密集的组播组会帮助前两者发现备用路径，而不会帮助“冗余树”方案。

图5显示了缺省组播树代价的对比。“冗余树”方案和“双树”方案的缺省树均是最短路径树，因此本方案的缺省树代价略高于前两者。图6显示了恢复后组播树代价的对比。在单故障的情况下，三种方案恢复后的组播树都未产生较大的代价增加。综合考虑上述三个度量标准，可以看出，本方案优于“冗余树”方案和“双树”方案。

在本文中，探讨了组播路由快速恢复的问题，讨论了现有的几种组播主动式恢复方案并分析了它们的优缺点。现有的方案大都基于不相交多路径来建立备用路由，然而不相交多路径却存在构建成功率低的问题，一旦网络拓扑无法满足不相交多路径的构建，则整个方案无法对组播通信提供保护。本文提出了自己的组播路由方案，即基于相交多路径的组播主动式恢复方案。在此方案中，组播树中的节点维护主备两个父节点，使得各个目的地通过多条相交路径连接到组播源。另外，节点在路由故障时本地处理，快速地将数据流切换到仍然可用的备用父节点。仿真结果表明，该方案构建的组播树以及故障恢复后的组播树代价均与现有方案相当，但是可以提供更短的恢复时间。

参考文献

[1]FEI A,CUI J,GERLA M,et al.A dual-tree scheme for fault-tolerant multicast[C].IEEE ICC 2001,2001,3(6):690-694.

[2]WU C,LEE W,CHU W.A new preplanned self-healing scheme for mu lticast ATM network[C].IEEE ICCT′96,1996,2(5):888-891.

[3]WU C,LEE W,HOU Y.Back-up VP preplanning strategies for survivable multicast ATM networks[C].IEEE ICC′97,1997,1(6):267-271.

[4]MEDARD M,FINN S,BARRY R,et al.Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs[J].IEEE/ACM Transactions on Networking,Oct.1999,7(5):641-652.

[5]WANG Jian Ping,YANG Mei,YANG Bin,et al.Dualhoming based scalable partial multicast protection[J].IEEE Trans.Computers,Sep.2006,55(9):1130-1140.

[6]WAXMAN B M.Routing of multipoint connections[J].IEEE J.Select.Areas Commun,1988,6(9):1617-1622.