一种改进的IP网络快速恢复重路由算法

张莉敏 周锡玲 邓怡辰 陈晓纯

摘要： 针对IP网络发生单个网络组件（链路或节点）故障时，重路由花费（重路由数据包增加的跳数）增加的情况，提出了一种新的备份配置创建方法。主要思想是根据备份配置中节点的介数值（Betweenness）和亲密度（Closeness）来定义关键节点，然后最大化关键节点的可用链路，从而减少最短路径跳数。从仿真数据可得出，采用的改进算法对于较大型的网络，考虑关键节点的位置并且使用Closeness算法选取关键节点能最大的减少重路由跳数。

关键词： IP快速恢复；路由花费；重路由；备份配置；关键节点

中图分类号：TP393 文献标识码：A

文章编号：1009-3044（2019）08-0126-03

An Improved Reroute Method for Fast IP Network Recovery

ZHANG Li-min， ZHOU Xi-ling， DENG Yi -chen，CHEN Xiao-chun

（Information Engineering，Guang Dong Polytechnic College ，Zhao qing 526100， China）

Abstract： IP fast reroute is based on two principles： local rerouting and precomputed reroute paths， when single network component （link or node） fails， routers are able to switch to an alternate path instantly. So this paper proposes a new backup topology design method. The main idea is to define the Key nodes according to the value of Betweenness Centrality and Closeness of nodes in backup topology， and then maximizes available links of Key nodes to reduce the number of hops in the shortest path. Two methods are adopted to select the key nodes： the first is Top K method， it is select K nodes with higher value of Betweenness and Closeness； the second method is Non-adjacent K method， when selecting the key nodes， considering the location of the key nodes， the adjacent nodes cannot be the used as the key nodes. The experimental results show that the proposed algorithm can achieve better results in large networks. For larger networks， considering the location of the key nodes and using the Closeness algorithm selected the key nodes can maximum reduce the number of hops.

Key words： IP fast reroute； routing cost； reroute； backup topology； key node

IP快速重路由是一種新的提高网络可靠性和稳定性的方法[1-2]。在网络发生单个故障（链路或节点）后，它重路由数据流量到备份路由，而不必等待路由重收敛过程的完成。

为了能从单个组件（链路或节点）网络故障快速恢复，多路由备份配置（MRC）方法也已经被提出[3]。MRC的核心思想是为网络的物理拓扑（或称为原始拓扑）提前配置多个备份的拓扑，并计算相对应的备份路由。当数据包遇到故障时，故障ID标记到数据包头部，并且采用与故障ID相对应的转发表将数据包转发到备份的下一跳[4-5]。

IP快速恢复主要是通过使用提前计算的备份配置减少重收敛时间。针对MRC算法的改进，文献[6]提出IMRC算法，该算法增加了重路由时可使用的路径数，从而降低恢复路径的总跳数；文献[7]提出在备份配置中生成最小生成数，减少路由跳数；文献[8]给出了一种新的备份配置设计方案，将高负荷路径的流量分离到其他可用路径，同时兼顾网络状况，如流量矩阵或网络拓扑。因为备份配置的减少会成功的减少转发表的数量，但是备份配置数的减少也会造成网络中某些链路负载过重，备份配置中的可用于备份路由的可用链路数量也会减少，这将造成重路由跳数的增加，重路由跳数的增加也会造成数据包延迟的增加。

针对上述问题，提出在备份配置创建过程中定义关键节点（Key node）[9]的方法来减少重路由跳数。主要思想是根据备份配置中节点的介数值（Betweenness）和亲密度（Closeness）来定义关键节点，通过增加关键节点的可用链路，缩短最短路径的跳数。选择关键节点时考虑节点的位置，相邻的节点不能同为关键节点。

1 多路由备份配置

本小节描述了使用MRC算法创建备份配置的特征，说明了如何使用备份配置进行IP网络快速恢复，并且讨论了使用该算法所存在的问题。

1.1 备份配置的创建

如图1所示，表示的最初网络拓扑和由原始备份配置算法产生的三个备份配置。每一个备份配置包括两种节点（如图中的圆形所示）和两种链路（如图中的连接线所示）。其中孤立节点和受保护的链路不用来转发数据包。为保证所产生的备份配置能从单一网络组件故障中快速恢复，该配置应该符合以下条件：

（1）必须包含每一个节点，并且任意两个节点间需有一条可用链路。

（2）原始拓扑中的所有链路和节点至少在一个备份配置（backup configuration， BC）中孤立一次。

如果备份配置满足以上的特征，将会确保每一條链路至少在一个备份配置中受保护。

1.2 数据包重路由过程

在MRC算法中，通常存储两种路由表来传输数据：正常路由表和备份路由表。具体路由过程已在之前工作文献[7]中详细写出。此处，以图1为例说明。假如数据包从节点1发送到节点6，路径1-4不可用。正常情况下从节点1到节点6的最短路径是1→4→6，当节点1收到来自上层的数据包，它会在数据包的头部标记0，根据最短路径，将数据包发送给节点4。当数据包到达节点4，因为路径1-4不可用，并且节点6是目的节点，所以节点4将会选择节点6和链路4-6受保护的备份配置进行重路由，即BC3。然后，它会在数据包的头部标记3，数据包会转发到节点2，因为在BC3中，从节点4到节点6的最短路径为4→2→5→6。如此反复，数据包转发到节点6。因此新的转发路径为1→4→2→5→6。

1.3 MRC算法出现的问题

在MRC方法中，如前面所描述，在正常情况下如果数据包不经过故障链路，则在故障状态下这些数据包的重路由跳数保持不变。相反地，如果在正常情况下数据包经过故障链路，则在故障状态下这些数据包重路由跳数会增加。路由跳数的增加将导致数据流量增多和包传输延迟的增大。故而，研究的目标是要尽量缩短重路由增加的总跳数。

2新的备份配置创建算法

2.1 关键节点选取

文章所提算法的主要思想就是在备份配置创建的过程中使用关键节点，通过增加关键节点的可用链路来缩短最短路径的跳数。基于网络环境，我们有两种定义关键节点[10]的方法：介数中心性排序法和亲密度排序法。

（1）介数中心性排序法。在这个方法中，基于网络结构定义关键节点。节点v的介数中心性[Bv]表示所有通过节点v的最短传输跳数与总的最短传输跳数的比值。另外，[σst]定义为从s到t的最短传输跳数，[σst（v）] 定义为从源端s到目的端t并且经过节点v的最短传输跳数。[Bv]定义如公式1，其中n 代表拓拓扑中节点的数量。

[Bv=snt，t≠snσstvσst] （1）

（2）亲密度排序法。在此方法中，节点p的亲密度（[Cp]）代表的是从点p到拓扑中其他点的最短传输跳数总和的倒数。[Cp]定义如公式2，其中n 为拓扑中节点的数量。[dpi，pk]是从某一点[pi]到某点[pk]的最小路线跳数。亲密度表示了某点相比拓扑中剩余节点居于中心的水平。

[Cp=1/i=1，i≠kndpi，pk] （2）

2.2算法流程

算法输入变量是关键节点的数量K，输出变量是备份配置数量N。初始时，N定义为1，然后算法从步骤1到步骤5连续执行。

步骤1：根据2.1所提的两种方法来定义关键节点。

步骤2：选取K个关键节点， Non-adjacent K方法：使用此方法选取关键节点，既要具有较高的介数值（或亲密度值），同时还要兼顾到关键节点在拓扑中位置信息。如果当前选择的关键节点与之前选取的关键节点相邻，则跳过当前这个节点，顺序地选取下一个节点作为关键节点。

步骤3：与关键节点连接的路径的保护过程。与关键节点相连的受保护链路在每个备份配置中的数量定义为M，关键节点的最大出入度定义为D，则M的最大整数值小于等于ceil（D/N）+1（ceil表示向上取整）。

步骤4：执行其他普通节点的链路保护过程。按原始的MRC方法，执行链路保护过程。

步骤5：判断改进的备份配置是否满足2.1节所提出的备份配置创建规则。如果满足，则算法结束。否则，N的值加1，然后继续从步骤1执行。

3仿真分析

3.1 实验环境

为了测试所提方法在单链路故障后对重路由总跳数的影响，仿真是在网络拓扑结构COST 239和COST 266进行，拓扑图连接了欧洲主要的城市。实验评估的参数是在所有单链路故障情况下，数据包重路由跳数随K值变化的情况。通常情况下链路cost值设成1，除了备份配置中孤立的链路。

3.2 路由结果

图2和图3分别显示了在Non-adjacent K方法下，COST 239模型和COST 266模型中路由总跳数随K值变化的情况。其中，COST 239备份配置数N是3，COST 266备份配置数是4。

如图2所示，对于COST 239模型，在Non-adjacent K算法中，减少的最大总跳数是：Betweennes=20， Closeness=33。从结果可知，在备份配置中确定关键节点并且最大化关键节点的可用链路数是可行的。当使用Non- adjacent K方法时， Closeness 算法相比Betweenness算法能更高的减少重路由跳数。

图3 表示COST 266模型使用Non-adjacent K方法的结果。在Non-adjacent K算法下选取关键节点，使用Betweennes方法减少的最大总跳数是1198，使用Closeness方法减少的最大总跳数是6439。从结果可知，在COST 266模型中，使用改进后的备份配置，能更好地减少路径跳数。因为COST 266模型拥有较多的节点，选取相邻节点作为关键节点的可能性较高并且不能最大化可用链路。且Closeness算法比Betweennes算法有更好的效果。由此可以得出，对于较大的网络，考虑关键节点的位置，使用Closeness算法选取关键节点是较好的策略。

3.3 对比分析

基于以上的实验环境，将改进算法与文献[6]中所提IMRC算法进行对比。在单故障情况下，IMRC算法提出使用孤立的非故障链路，增加重路由过程中的可用链路数，从而减少替换路径的总跳数。实验评估是在单链路故障状态下，使用Non-adjacent K算法， IMRC算法后，COST 266模型中所有节点对之间的总跳数。

如图4 所示，在COST 266模型中，路由总跳数都有明显的降低，并且在Non-adjacent K算法中，链路9故障时，路由总跳数可以减少42%。由以上结果可以得知，所提算法在大型网络中有很好的应用，能减少单组件故障时所增加的路由跳数。并且，Non-adjacent K算法是较好的选择策略。

4 总结

文中提出了一种新的备份配置设计算法来减少IP快速重路由过程中增加的路由跳数，我们的算法可以在不增加备份配置的前提下减少总路由跳数。所提方法的主要思想是在备份配置创建的过程中引入关键节点的概念，比较在不同关键节点数量情况下，网络发生单故障后重路由路径总跳数。仿真实验可得出，改进的备份配置设计方法在大型网络中能取得较好的效果。对于较大的网络，考虑关键节点的位置并且使用Closeness算法选取关键节点能最大的减少重路由跳数。

未来的工作，我们希望使用新的备份配置创建算法进行多故障快速恢复并且实现最小的路由花费。

参考文献：

[1] Shand M，Bryant S. IP Fast Reroute Framework[J]. IETF RFC 5714，2010，4（4）：206-207.

[2] 余学杰.对TCP/IP计算机网络拥塞控制的研究[J].现代电子技术，2014，37（15）：38-40.

[3] Kvalbein A F. Hansen， T. Cicic， et al， Multiple routing configurations for fast IP network recovery[J]. IEEE/ACM Transactions on Networking （TON）， 2009，17（2）：473-486.

[4] 張莉敏，王辉，李沛谕， 等.基于多路由配置的数据中心网络故障恢复研究[J].计算机应用与软件， 2017，34（3）： 289-293，328.

[5] 郭帅，李沛谕，王辉， 等.基于LFA的IP网络快速恢复算法[J].计算机工程与设计，2017，38（4）：878-882.

[6] Daiki Imahama， Yukinobu Fukushima， Tokumi Yokohira. A Reroute Method Using Multiple Routing Configurations for Fast IP Network Recovery，APCC 2013：439-444.

[7] Kamamura S， Miyamura T， Pelsser C I. Inoue， and K.Shiomoto. Minimum Backup Configurations Creation Method for IP Fast Reroute[C]. Proceedings of GLOBE COM-2009 IEEE Global Telecommunications Conference. IEEE， Honolulu， 2009：1-6.

[8] 陈荣庆，黄艳红.一种改进的IP网络多故障快速恢复算法[J].微型机与应用，2013，32（14）：53-55.

[9] 荆云. 复杂网络重要节点识别方法研究[D].河南师范大学，2017.

[10] 南栋卿. 复杂网络中关键节点的识别研究[D].吉林大学，2016.

【通联编辑：唐一东】