基于SimCT 的多播路由及故障恢复研究*

孙 伟 ，罗俊海 ，肖志辉

（1.西南交通大学信息科学与技术学院 成都 610031；2.电子科技大学电子工程学院 成都 611731；3.迈普通信技术股份有限公司 成都610041）

1 引言

随着互联网技术的不断发展和网络规模的不断扩大，多播业务得到越来越多的应用，如VoIP、视频会议、视频点播、远程教育、在线聊天等。具有健壮性的多播系统会有较大的市场需求，对多播系统的保护和故障后的快速恢复技术的研究成为网络路由领域的重要课题[1～3]。这些技术目标是寻找有效的方法来提高多播网络的健壮性，确保网络通信中数据的连续性或尽可能地减少中断，这就要求在网络中利用冗余的资源提高网络的生存性或在检测到网络故障后能够快速地确定新的路径，以绕过故障节点或链路保证网络的正常通信。

网络中通过多路径传输数据可以使网络健壮性提高、负载均衡、拥塞减少和吞吐量提高。通常从一个源节点到一个目的节点可以有多条路径，如果有足够的网络资源，这些路径可共享同一链路或节点，为了提高传输的可靠性和避免共享链路或节点的失败，这些路径则应是节点或链路不相交的。

对节点/链路不相交的多路径路由的研究已有很多[4,5]，这些研究关注于多路径路由对节点或链路失败的作用。其中一条路径作为主路径，其余作为备用路径，如果主路径中链路或节点发生故障，则数据将会通过备用路径传输。颜色树是一种使用最小的路由表项开销和查询时间实现节点/链路不相交的多路径路由的方法[6,7]，网络中每个节点到目的节点的多条路径中有两个最优的邻居：红色和蓝色，在源节点数据分组被标记为这两种颜色中的一种，中间节点通过识别数据分组的颜色标记，转发数据分组到相应的邻居节点。参考文献[8]中提出的SimCT算法通过组建和维护两棵节点/链路不相交的颜色树，同时在网络节点/链路失败情况下，通过本地信息有效地组建新的颜色树，提高了网络的健壮性。本文在SimCT算法的基础上，以多播源节点作为根节点组建两棵颜色树（Red和Blue），根据两棵颜色树有效地组建多播数据转发树；多播树节点/链路失效时，可通过颜色树快速地组建新的多播转发树，保证网络数据的传输。

2 SimCT算法

SimCT算法分为3个步骤：

（1）分发深度优先搜索（depth-first-search，DFS）序号和全局低点值计算；

（2）网络节点的逻辑分层；

（3）选择左（Blue）转发节点和右（Red）转发节点。

（2）中的逻辑分层与节点/链路不相交有关，本文只考虑节点不相交的多路径路由，此处节点不相交的限制如下。

如果从节点s到节点d的Red路径穿过节点i，那么从节点s到节点d的Blue路径则不会穿过节点i，如，坌s∈N{d}和坌i∈N{s,d}，则：

算法中所使用的符号如表1所示。

2.1 分发DFS序号

算法的第一阶段是为网络中各节点分发DFS索引序号和计算节点的全局低点值，具体算法如图1所示。

算法中，节点x的全局低点值是指节点x通过贯穿一系列节点所能达到的DFS索引最小的节点的索引值，即glpv（x）=min（DFS 索引），一系列节点中，除最后一跳外，其余DFS序号是递增的。

2.2 网络节点的逻辑分层

算法的第二个阶段是为网络节点进行逻辑分层，为了限制每一层节点的全局低点值glpv（x），此处定义一个势值（potential）术语——即同一层节点的glpv的边界值。节点x的势值表示为pot（x），根据glpv（x）和pot（x）的关系为节点分层（odd层和even层）。

表1 SimCT算法中所使用的符号

图1 分发DFS序号和计算glpv值的算法

势值计算规则如下：

p（x）为节点x的DFS搜索路径的父节点。分层规则如下：

～l（p（x））表示与p（x）不同的层，即如果l（p（x））=odd，则～l（p（x））=even。

2.3 选择转发节点

算法的第3个阶段是为每个节点选择到根节点的左转发节点（Blue）和右转发节点（Red）。

如果节点x在even层，则：

如果节点x在odd层，则：

通过SimCT算法组建两棵不同路径的颜色树，网络中各节点可以通过两棵不同颜色树到达根节点。

3 基于SimCT的多播树的组建

3.1 多播树的组建

SimCT算法要求网络拓扑必须为2连接网络，即点到点之间至少有两条通过不同节点的路径，如图2所示网络拓扑。如图3所示，以多播源节点S为根节点使用SimCT算法，组建Red和Blue两棵颜色树，节点上所标序号为算法中为各节点分发的DFS序号。

图2 网络拓扑示例

图3 用SimCT算法构造的以多播源节点S为根的颜色树

为了描述方便，本文把网络中的路由节点，按照在构建多播树过程中的不同职责分成3类：源节点、目的节点和中间节点。

源节点：一个源节点对应一棵多播树，负责发送多播数据，是多播树的根节点。

目的节点：用于接收从源节点发出的多播数据，多播树的组建将会连接源节点和所有目的节点，是多播树的叶子节点。

中间节点：在多播树中连接源节点和各个目的节点，只负责转发接收的数据报文，是多播树的非叶子节点。

网络中需要接收多播数据的节点，沿着到达多播源节点的颜色树路径，发送加入多播组报文。网络中节点加入多播树算法如图4所示。

多播树组建的具体报文交互过程如下。

（1）网络中目的节点需要接收多播数据，则沿Blue树向源节点方向发送join报文。

图4 节点加入多播树算法

（2）中间节点维护两个多播表项，即多播树的上游节点列表iif_list和多播树的下游节点列表oif_list。中间节点x接收join报文后，将join报文的发送节点添加到oif_list中；同时，检查iif_list是否为空，如为空，则将join报文沿Blue树转发到节点x的左转发节点，并添加节点x的左转发节点（Blue树路径）到iif_list中。如果iif_list不为空，则不再转发join报文，并向join报文接收的方向返回success报文。

（3）在join报文发送过程中，如果某中间节点检测到Blue树的上游节点或链路发生故障，则join报文沿Red树发送，即将join报文转发到中间节点的右转发节点；如果Red树的上游节点或链路也发生故障，则向join报文接收的方向返回failure报文。

（4）如果join报文沿Blue/Red树路径一路转发到达源节点S，源节点将join报文的发送节点加入到自己的oif_list中，并向join报文接收的方向返回success报文。

（5）中间节点收到success报文，转发报文至oif_list中各节点。

（6）中间节点接收到failure报文，则将其转发至oif_list中的各节点，并删除相应的iif_list和oif_list中的节点。

（7）目的节点接收到success报文，则成功加入多播树；如接收到failure报文，则加入多播树失败。

（8）已成为多播组成员的节点如不再需要接收多播数据，则沿多播树上游方向发送prune报文。

（9）中间节点接收到 prune报文，删除 oif_list中接收prune报文的发送节点，接着检查oif_list表项中是否还有节点项存在，如果有，则不再转发prune报文；如oif_list已经为空，则转发prune报文至iif_list中节点，之后删除iif_list中相应的节点项。

图5 成功组建的多播通信树

多播通信是一对多的通信方式，因此iif_list中表项只有一个，而oif_list中则可有多个。为了满足多播通信中组成员的动态变化，可以通过发送加入/剪枝报文动态地加入或退出多播组。

如网络中节点4、8、9、12想要接收多播数据，则通过本文所述多播的组建过程，在没有故障的情况下得到多播通信树如图5所示。多播通信中如多播成员不再需要接收多播数据，则可向多播树上游节点发送剪枝报文prune，如节点12可向上游节点发送prune报文，退出多播组。

3.2 单节点/链路故障恢复

对于多播通信而言，多播通信树中的任何节点或链路故障都可能影响它下游所有的多播成员的正常通信，因此多播的通信故障恢复方法复杂于单播的故障恢复方法。为了提高多播通信的健壮性，需要有相应的通信保护或故障恢复措施。

本文提出的多播路由的故障恢复方法是由检测到故障的节点本地执行，快速地将受影响的故障节点的下游子树通过颜色树重新连接到多播树。

图6 故障恢复过程中的新路径选择算法

基于颜色树成功组建的多播通信树，如多播树中单节点或单链路发生故障时，故障恢复过程中的新路径选择算法如图6所示。

多播保护树构造的具体报文交互过程如下。

（1）多播树中故障节点或链路的下游节点检测到故障发生时，如果该下游节点的iif_list中节点为它的左转发节点（Blue树路径），则向其右转发节点（Red树路径）发送change报文，并更新iif_list中节点项为右转发节点；如果iif_list中节点项为该节点的右转发节点 （Red树路径），则向左转发节点 （Blue树路径）发送change报文，并更新iif_list中节点项为左转发节点。

（2）中间节点接收到change报文，首先检查change报文的发送节点是否与iif_list中节点项相同，如相同则删除iif_list中对应的此节点项。同时将change报文的发送节点添加到oif_list中。

（3）检查iif_list是否为空，如不为空，则不再转发change报文，并向change报文发送节点返回done报文；如iif_list为空，则转发change报文。

图7 节点7出现故障后，执行本文恢复方案得到的多播树

（4）转发change报文的规则如下：如果中间节点接收的change报文的发送节点是该节点的左转发节点（Blue树路径），则change报文转发至该中间节点的右转发节点（Red树路径）；其他情况则将change报文转发至该中间节点的左转发节点（Blue树路径）。

（5）如果中间节点的Blue树和Red树路径对应的转发节点都不能成功发送change报文，则沿change报文接收的方向返回exit报文。

（6）中间节点接收到done报文后，沿着change报文接收的方向转发done报文，一直转发至初始change报文的发送节点，则保护树构造成功。

（7）中间节点接收到exit报文后，沿着change报文接收的方向转发exit报文，一直转发至初始change报文的发送节点，则保护树构造失败。

（8）故障节点或链路的上游节点检测到失败发生时，删除自身节点中对应的oif_list中的下游节点项，检查oif_list表项中是否还有其他下游节点，如还有下游节点项存在，则不再做其他动作；如oif_list变为空，则该节点发送prune报文至iif_list中节点，之后删除iif_list中的节点项。

图8 节点5出现故障后，执行本文恢复方案得到的多播树

（9）中间节点接收到prune报文，删除oif_list中对应的prune报文的发送节点，接着检查oif_list中是否还有节点表项存在，如果有，则不再转发prune报文；如oif_list已经为空，则向iif_list中节点转发prune报文，之后删除iif_list中的节点项。

对于图5中的多播通信树，假如节点7发生故障，多播成员8、9、12与多播源的通信将中断。根据本文所提出的故障恢复方法在故障节点的下游节点8、10、11检测到故障后，执行本文所述恢复方法，将多播成员绕过故障节点重新连接到多播树。同时根据本文所提出的方案中，为了避免无用的多播数据流的发送，节点5发送prune剪枝报文将自己从多播通信树中剔除。通过本文方案的执行，得到如图7所示的新的多播通信树。图8为节点5到节点7的单链路失败后，通过本文恢复方案得到的新的多播树，图中节点7检测到多播树上游链路发生故障，通过Red树绕过故障链路，同时节点5检测链路故障并检测到下游已无多播接收成员，则向上游节点发送prune报文，删除多播树中多余的分枝。

4 仿真与性能分析

本文的性能仿真均是在Matlab上实现，仿真中使用的网络拓扑借鉴Salama博士的随机网络拓扑算法[9,10]生成，网络节点随机分布的正方形区域大小设定为2 000 km×2 000 km,根据概率来确定和之间是否存在链路，其中d(u,v)是u和v之间的欧氏距离，L是任意两点间的最大距离。α和β是常数，较小的α将增大链路的密度，较大的β将导致较高的链路密度。通过调整α、β使产生的网络拓扑满足2连接的要求，即拓扑中顶点之间必须至少有两个经过不同节点的路径，本文仿真中取α=0.15，β=2.2。

本节对方法的性能进行两方面的仿真分析：首先是生成的多播树所经过的网络节点数，多播树中网络节点数较少表明多播通信所需成本相对较低；另外需要关注的是多播通信保护中，故障恢复后多播树的代价，代价的增加量反映了多播故障恢复的质量。仿真中，每条链路的代价被配置为1，这样多播树的代价就是树中链路的总个数。

仿真实验中，随机选择一个网络节点作为多播源节点，并随机选择多个节点作为多播组成员，通过运行本文所提出的算法生成一棵多播树，记录多播树所经过的节点数。除了对本文方法仿真外，对参考文献[11]中所提出的多播冗余树方法也进行了对比仿真。在故障恢复仿真中，随机选择多播树中一个单节点作为故障节点，记录多播故障前与故障恢复后多播树的代价。本文做了100次重复实验，取所记录的平均值作对比分析。

图9 随机网络节点数为100个时，不同多播规模下的多播树包含节点数

图10 随机网络节点数为200个时，不同多播规模下的多播树包含节点数

图9显示随机网络节点数为100时，本文方案和参考文献[11]所提出的多播冗余树方案在不同多播规模下，多播树中所包含的节点数；图10显示随机网络节点数为200时的仿真对比。从图9、图10中可以看出本文的多播树方案生成的多播树所包含的节点数明显少于参考文献[11]中的冗余树方案；另外从图中还可以看出，在多播规模较小时，冗余树方案所生成的多播树仍包含较多的节点数，原因在于参考文献 [11]中的冗余树方案采用路径扩大（path augmentation）方法，使得较多的冗余节点也被加入多播树，而本文的方法则通过SimCT算法得到的颜色树组建多播树，在多播规模较小时，生成的多播树中节点数也相对较少，减少了过多的资源浪费。

图11和图12显示随机网络节点数分别为100和200时，本文方案中多播单节点故障前与单节点故障恢复后多播树的代价。从图中可以看出，采用本文中单节点故障恢复方案，故障前与恢复后多播树的代价成本基本一致，即有效克服了在多数方案[1～3]中所产生的多播保护树相对通信多播树长度过长的问题。

图11 随机网络节点数为100个时，单节点故障前与故障恢复后的多播树代价

图12 随机网络节点数为200个时，单节点故障前与故障恢复后的多播树代价

5 结束语

本文在分析和研究SimCT算法的基础上，提出了一种基于颜色树的多播树生成方法，并提出了一种多播单节点故障时的多播通信的恢复方案。仿真实验表明，本文所提出的多播树生成方案相比现有方案可以减少网络资源的浪费，并且故障恢复后的代价与原多播通信树相当。本文方案中的故障恢复，主要对单节点/链路进行保护，下一步将继续研究和分析在多个节点/链路失败情况下的故障恢复方法。

1 Hiltunen M，Schlichting R,Ugarte C.Building survivable servicesusingredundancy and adaptation.IEEE Transon Cormputers,2003,52（2）:181～194

2 Wu Jian,Shin K G.SMRP:fast restoration of multicast sessions from persistent failures.In:Proc of the 2005 International Conference on Dependable Systems and Networks （DSN’05）,Yokohama,Japan,2005

3 Feather M S.A risk-centric decision process.In:Proc of Software Engineering for High Assurance Systems （SEHAS） ,Portland,Oregon,USA,2003

4 Ramesh B.Survivable Networks:Algorithms for Diverse Routing.Norwell:Kluwer Academic Publishers,1999

5 Wayne D G.Mesh-Based Survivable Networks:Options and Strategies for Optical,MPLS,SONET and ATM Networking.New Jersey:Prentice Hall Publishers,2003

6 RamasubramanianS,Krishnamoorthy H,KrunzM.Disjoint multipath routing using colored trees.Computer Networks:The InternationalJournalofComputer and Telecommunications Networking,2007,51（8）

7 Ramasubramanian S,Harkara M,KrunzM.Lineartime distributed construction of colored trees for disjoint multipath routing.Computer Networks:The International Journal of Computer and Telecommunications Networking,2007,51（10）

8 Jayavelu G,Ramasubramanian S,Younis O.Maintaining colored trees for disjoint multipath routing under node failures.IEEE/ACM Transactions on Networking,2009,17（1）:346～359

9 Salama H F.Multicast routing for real-time communication of high-speed networks.Raleigh:Department of Electricaland Computer Engineering North Carolina State University,1996

10 Junhai Luo,Danxia Ye,Xue Liu,et al.A survey of multicast routing protocols for mobile ad hoc networks. IEEE Communications Surveys and Tutorials,2009,11（1）

11 Shang Wang,Chun He,Yide Zhang,et al.Construction of multicast protection tree based on single node failure.In:2010 International Conference on Communications and Mobile Computing （cmc’10）,Shenzhen,China,2010