基于相交多路径的组播主动式恢复方案
摘 要:提出了基于相交多路径的组播主动式恢复方案。该方案通过为树中节点提供备用父节点的方式，计算组播源到各个组成员的多条相交路径来代替不相交双树。相交多路径保证了构建成功率并为组播路由提供一定程度的保护。仿真结果表明,该方案构建的组播树以及故障恢复后组播树的代价均与现有方案相当，但是提供的故障恢复时间与现有方案相比显著缩短。
关键词:组播; 相交多路径; 主动式恢复
网络的一个重要问题是可生存性(survivability)。可生存性是指系统在攻击、故障、意外事件影响下能够及时完成任务的能力。网络的可生存性又称为网络快速恢复能力，用于描述一个网络在应对节点或链路失效时的性能。有两类方法可以提供网络的快速恢复能力。一种方法称为被动式(reactive)恢复，又称为按需(on-demand)恢复，当网络中检测到故障时，绕过故障的链路/节点，重新寻找新的路由来完成服务的恢复[1]。该方案的主要缺点是恢复延迟漫长，不利于很多即时通信。另一种方法是主动式(preactive)恢复，它预先计算两条不相交的路径，一条被指定为主路径,另一条是备用路径[1]。当主路径因其中的链路或节点故障而失效时，备份路径被激活，自动成为新的主路径。对比于被动式恢复方法，该方法能够减少恢复时间，但在很多情况下，它需要执行复杂的恢复操作和花费较多的网络资源。
组播是一种一对多的传输方式，需要将数据同时从源发送到一组目的主机。设计组播通信的快速恢复方案更富有挑战性，因为一个链路/节点的失效将会影响到很多组播目的主机。许多文献都提出了针对单一节点/链路失效提供保护的组播主动式恢复方案，这些方案要求计算从数据源到目的地的不相交的多条路径。目前广泛受到关注的两种保护方案是：局部保护方案和组播组保护方案。两者的保护范围不同，前者是按照单播主动式故障恢复方案将多播树中源节点列目的节点的路径抽取出来，并分别为它们建立保护路径；后者则是通过计算两个链路不相交组播树，其中一个作为主要的组播树，而另一个作为备份组播树，以整个组播树为保护对象。
以上两种方案均存在不足：局部保护方案需要较高的维护与管理代价，而且可能出现路由环路；组播组保护方案近年来研究得比较多，然而, 找到两个链路/节点不相交的两棵组播树在大型组播通信中是很困难的，甚至是不可能实现的。
针对现有方案中不相交的多路径构建成功率低下的不足，本文提出一种基于相交多路径的组播主动式恢复方案。该方案通过为组播树中的节点备份父节点的方式，使得各个组播组成员通过多条相交路径连接到组播源。当发生故障时，路由可以快速地切换到未受故障影响的父节点，进而完成组播路由的快速恢复。
1 背景和相关工作
虽然目前对组播通信的故障恢复的文献中很少提及，但其必将成为未来通信网络的一个重要部分。在常规的组播中，数据流分布在整个树结构上，一个故障就会影响到故障点下游的所有组成员。目前组播主动式恢复方案的研究中，有些借鉴单播中链路恢复和路径恢复的方案，应用于保护组播树中的源到每个目的地的路径[2,3],有些利用冗余树[4]或者双树[1]方案。图1给出四种主要的组播主动式恢复方案的实例。图中，S是源节点，实心的节点是组播组成员。粗实线代表缺省树中的链路，虚线代表在备用路径的链路。不同类型的箭头表示数据流在缺省树或激活后的备用路径中的传输方向。
WU C等[2,3]研究了链路保护和路径保护方案。在链路保护中，每条链路的两个端节点之间设置了一个备用路由。在路径保护中，为每个目的地计算一条备用路由，该路径与组播树中从数据源到目的地的路径是节点不相交的。
图1(c)给出了一个简单的“冗余树”(redundant tree)方案[4]的例子。“冗余树”方案要求网络拓扑结构是一种双连通图，即任何两个节点之间至少有两条节点不相交或者链路不相交的路径。如果缺省树和备用树只是链路不相交，则它是一棵链路不相交的备用树；否则，称其为节点不相交备用树。“冗余树”方案提出的算法可以计算两棵不相交的组播树，使得消除网络中任何节点(链路)，目的节点都可通过至少一棵树连接源点。因此，冗余树方案可以恢复缺省树中出现的任何链路或节点的故障，并可恢复不止一个故障。
