一种基于转发图的域内路由保护算法

耿海军 孟 卓 姚姗姗 杨 静 池浩田 尹 霞

1 （山西大学计算机与信息技术学院 太原 030006）

2 （山西大学自动化与软件学院 太原 030006）

3 （山西大学大数据科学与产业研究院 太原 030006）

4 （清华大学计算机科学与技术系 北京 100084）

（genghaijun@sxu.edu.cn）

开放最短路径优先（open shortest path first, OSPF）[1]协议和中间系统到中间系统（intermediate system to intermediate system, IS-IS）协议是互联网目前使用的2 个典型的域内路由协议[2]，这2 个协议采用最短路径将报文从源地址转发到目的地址. 在OSPF 和ISIS 中，每个路由器通过交互链路状态通告获得整个网络的拓扑结构，然后该路由器通过迪杰斯特拉算法计算以自身为根的最短路径树，最后该路由器根据最短路径树构造出自己的路由表. 当网络出现故障时，OSPF 和IS-IS 采用重新收敛机制来应对网路中的故障. 但是研究表明[3-5]，它们的重新收敛时间大概在几秒甚至几十秒左右，在路由协议重新收敛的过程中受这些故障影响的报文将会被丢弃，严重影响了网络的性能，大大降低了用户的体验. 互联网部署的实时应用对网络的收敛时间提出了更高的要求[6-8]. 传统的路由协议无法满足实时应用对网络收敛时间的要求[9]. 为此，业界提出利用路由保护算法来解决此问题，研究表明路由保护算法[10]可以大大降低由于故障造成的网络中断时间，显著减少报文丢失.

在已有的路由保护算法中，最经典的方法是IP快速重路由（IP fast rerouting, IPFRR）[11]，该算法可以选择事先计算好的备份下一跳绕过故障，从而降低由于故障造成的报文丢失率. 与最短路径路由相比，IPFRR 有明显的优点：可以立即重新转发数据包，而不是等待路由重新收敛（通常为几秒甚至几十秒），从而避免在路由重新收敛阶段出现路由环路和数据包丢失问题[12].

路由保护算法最核心的技术是如何为每个结点计算到达目的结点的无环路备份下一跳. 下游规则（downstream criterion, DC）[13]是一种经典的无环路计算规则，该规则选择距目的地址更近的邻居结点作为备份下一跳. 以目的结点构造有向无环图（directed acyclic graph, DAG），也可以计算出无环路备份下一跳. 基于最大邻接顺序的最大可选择性路由算法（maximum alternative routing algorithm, MARA）[14]的核心思想就是将网络拓扑转换为DAG. 但是文献[13−14]算法和网络拓扑结构密切相关，在某些拓扑结构中故障保护率较低. 在DAG 图中，每条链路仅有1 个方向，这个要求大大降低了结点可以计算出无环路备份下一跳的可能性. JNHOR-SP（shortest path compatible Joker-capable next hop optimality routing）[15]利用路由结点排序和Joker 链路来提高DAG 图的故障保护率，网络中的Joker 链路具有2 个方向，但是由于计算Joker 链路算法的缺陷，JNHOR-SP 平均仅能提供95%左右的故障保护率. 基于报文入端口的无环路路由（loop free inport-dependent, LFID）[16]通过扩展DAG，将部分链路修改为双向链路，从而同时解决网络故障和网络拥塞问题，但是LFID 的故障保护率为88.9% ～ 98.2%. Not-Via[17]和段路由[18]（segment routing,SR）可以保护网络所有可能的单故障，但是二者需要借助辅助机制的协助，在实际中部署比较困难.

已有的路由保护算法存在4 个方面的问题：1）无法应对网络中所有可能的单故障情形；2）需要额外辅助机制的协助；3）不支持增量部署；4）需要存储多个备份下一跳. 我们拟设计一个路由算法，该算法满足4 个要求：1）每个路由器存储2 个下一跳，其中一个为最优下一跳，另外一个为备份下一跳；2）可以应对网络中所有可能出现的单故障情形；3）不需要额外辅助机制的协助；4）支持增量部署. 基于此本文提出了一个满足这4 个要求的基于转发图的域内路由保护算法（an intra-domain routing protection algorithm based on forwarding graph, RPBFG）. 受JNHOR-SP 和LFID 这2 个算法的启发，本文通过构造转发图来解决DAG 图故障保护率较低的问题. 在转发图中，每条链路可能存在2 个方向，这将明显提高故障保护率. 与JNHOR-SP 和LFID 不同的是，RPBFG 可以提供100%故障保护率. 我们将在后面的章节中详细介绍什么是转发图，如何构造转发图，如何利用转发图计算无环路备份下一跳.

本文的主要贡献包括4 个方面：

1） 提出了以最大化故障保护率为目标，转发图包含反向最短路径树为约束条件的路由保护算法模型RPBFG.

2） 针对提出的路由保护算法模型，首先提出了利用RPBFG 解决快速构造转发图的算法，然后利用转发图为每个结点计算唯一一个备份下一跳.

3） RPBFG 是对当前链路状态路由协议的扩展，不会改变路由协议报文的交互过程. RPBFG 需要的数据都可以从链路状态路由协议中获得，唯一的变化是路由计算部分，因此RPBFG 支持增量部署.

4） 在11 个真实网络拓扑中进行了实验，实验结果表明RPBFG 不仅可以支持100% 的单故障保护，而且具有较小的路径拉伸度.

根据这4 点贡献的描述可知RPBFG 可以应对网络中所有可能的单故障情形，不需要额外辅助机制的协助，支持增量部署，每个结点存储唯一一个到达目的地址的备份下一跳. 因此RPBFG 可以解决文中描述的已有路由保护算法存在的4 个问题.

1 相关工作

已有研究[19]证实，互联网中每天都会出现大量的网络故障. 为了应对互联网中频繁出现的故障，业界提出了路由保护算法[20]，从而尽量降低由于故障造成的损失. 根据报文在转发过程中是否需要辅助机制的协助，可以将路由保护算法分为2 类：第1 类不需要借助辅助转发机制；第2 类需要借助辅助转发机制.

第1 类路由保护算法主要包括等价多路径路由（equal cost multipath routing, ECMP）、 无环路备选条件（loop-free alternates, LFA）、U-turn、MARA-MA、基于扩展最短路径的最大可选择性路由算法（maximum alternative routing algorithm-shortest path extension,MARA-SPE）等；第2 类路由保护算法主要包括Not-Via、SR、多配置路由（multiple routing configuration,MRC）、报文携带故障（failure carrying packet, FCP）等.第1 类算法和目前使用的路由协议是兼容的，因此支持增量部署. 然而第2 类路由保护算法需要对目前使用的路由协议进行修改，实现难度较大. 本文重点研究第1 类路由保护算法，下面将分别介绍这类路由算法.

OSPF 协议增加了对ECMP 的支持，但是ECMP仅仅支持代价相同的最短路径，因此对提高路由可用性的贡献比较有限[21]. 为了应对ECMP 在解决路由可用性方面存在的问题，国际互联网工程任务组（Internet Engineering Task Force, IETF）提出了快速重路由的基本框架. LFA 就是基于此框架提出的无环路路由. LFA 包括3 种应对故障的保护条件：链路保护条件（link protection condition, LPC）、结点保护条件（node protection condition, NPC）和DC. 文献[22−23]分别介绍了如何通过调整链路权值和修改网络拓扑结构提高LFA 的故障保护率. U-turn[24]将选择备份下一跳扩展到计算结点邻居的邻居，即如果计算结点的邻居没有满足无环路规则的下一跳，但是计算结点的邻居的邻居有满足无环路规则的下一跳，则该邻居可以作为计算结点的备份下一跳，因此U-turn 可以进一步提高故障保护率. MARA-MA[14]以最大化最小连通性为目标构造DAG，MARA-SPE[14]和MARA-MA的目标是一致的，但是MARA-SPE 的约束条件为DAG必须包含最短路径树.

文献[25] 提出了基于Not-Via 地址的快速重路由机制. 在该算法中，网络中的每条链路都有2 个地址，一个是正常的IP 地址，另一个Not-Via 地址. 该机制使用Not-Via 地址显示的说明网络中出现故障的结点或者链路，从而使报文避开该故障. 基于隧道的路由保护算法[26]为所有源目的对计算中转隧道结点，然而并不是所有的结点对之间都存在中转结点. 基于SR[14]的路由保护算法将网络的路径分成一个个的小段，然后为这些段和网络结点分配Segment Routing 的ID，通过对这些 Segment Routing ID 进行有序的排列，就可以生成一条完整的转发路径.

MRC[27]通过改变网络中链路的代价计算出多个配置图，这些不同配置图可以应对网络中出现的不同故障，从而达到提高路由可用性的目的，但是MRC 部署开销较大. FCP[28]的核心思路为：首先将报文遇到的故障存放在其头部，然后根据该头部信息更新网络拓扑结构，最后利用新的网路拓扑结构计算新的最短路径. FCP 可以应对网络中的单故障问题，但是该方法需要改变路由协议，部署难度较大.

表1 列出了RPBFG 和已有路由保护算法的链路状态路由协议，在支持逐跳转发和支持100%的单故障保护等方面进行比较.

Table 1 Comparison of Routing Protection Algorithms表1 路由保护算法的比较

1） 链路状态路由协议. 每个路由器根据网络拓扑结构做出最终的路由决策.

2） 支持逐跳转发. 每个路由器基于目标地址查找数据报的下一跳，转发过程不需要借助额外机制的协助.

3） 支持100%的单故障保护. 当网络出现单故障时，只要网络依然保持链路，数据报就可以被正确转发到目的地址.

2 基于转发图的网络模型和问题描述

本节首先定义了反向最短路径树、转发图、故障保护率和路径拉伸度，然后对基于转发图的路由保护算法进行了形式化的描述. 为了便于读者阅读，将文中使用的部分符号总结在表2 中.

Table 2 Symbols Defined in Our paper表2 本文定义的符号

2.1 网络模型

本文使用无向图G=（V,E） 来表示一个网络，其中V是无向图中的结点集合，代表网络中的路由器，E是无向图中的边集合，代表网络中的链路. 对于网络中的任意一个结点v∈V，bestn（v,d）表示结点v到结点d的最优下一跳，backn（v,d）表示结点v到结点d的备份下一跳. 下面给出反向最短路径树、转发图、故障保护率和路径拉伸度的定义.

定义1.反向最短路径树. 对于目的结点d，其余结点到目的结点d都具有最短路径的树.r（d）表示目的地址为d的反向最短路径树.

定义2.转发图. 按照一定的规则遍历无环路的有向图.G（d）表示目的地址为d的转发图.

定义3.在转发图G（d）中，对于任意的结点v∈V,v≠d，如果v到d的最优下一跳出现故障，v依然可以到达目的地址d，我们称在G（d）中结点v可以被保护，否则结点v未被保护.

定义4.转发图G（d）的故障保护率可以表示为其中当结点v被保护时f（v,d）=1，否则f（v,d）=0.

定义5.路径拉伸度. 当网络出现故障时，利用路由保护算法计算出的所有源目的对之间的代价总和与利用最短路径计算出的所有源目的对之间的代价总和的比值.

我们通过一个简单的例子解释上面的定义1～5.图1 表示网络拓扑结构，链路上的数字表示该链路对应的代价. 图2 表示以结点d为根的反向最短路径树，实线表示在反向最短路径树中的边，从图2 中可以计算出每个结点到目的结点d的最优下一跳. 例如，f到d的最优下一跳可以表示为bestn（f,d）=c,k到d的最优下一跳是bestn（k,d）=j. 图3 是以d为目的地址的转发图，从图3 中可以计算出每个结点到目的结点d的备份下一跳. 在图3 中实线箭头表示结点的最优下一跳，空心箭头表示结点的备份下一跳. 例如，f到d的备份下一跳可以表示为backn（f,d）=e,k到d的备份下一跳可以表示为backn（k,d）=h. 转发图是如何构造出来的，为什么利用转发图可以计算出结点的备份下一跳将在后面的章节中详细介绍.

Fig. 1 Network topology structure图1 网络拓扑结构

Fig. 2 Reverse shortest path tree图2 反向最短路径树

Fig. 3 Forwarding graph图3 转发图

2.2 问题描述

为了解决已有路由保护算法存在的4 个问题，我们形式化地描述了本文需要解决的科学问题. 在已知网络拓扑结构G=（V,E） 的前提条件下，对于目的结点d∈V，如何构造一组转发图G（d）包含反向最短路径树r（d），从而使得故障保护率最高. 该问题可以形式化表示为

其中式（1）为目标函数，即最大化故障保护率；式（2）表示反向最短路径树属于转发图.

3 转发算法

在构造转发图的过程中，需要解决2 个关键问题：1）如何设计遍历算法，即转发算法；2）如何给转发图中链路设置方向，从而使得该转发图包含反向最短路径树.

3.1 转发算法规则

对于问题1 我们采用互联网部署的路由转发算法，这样设计的算法和互联网是兼容的，便于实际部署. 我们对转发算法进行简单地描述：在网络中，当路由器收到一个报文后，就会根据报文中目的地址的信息从路由表中查找对应的下一跳，然后将该报文直接发送给对应的下一跳. 具体的转发规则为：

1） 如果最优下一跳路由器发生了故障，就从备份路由表中查找备份下一跳，将报文发送给备份下一跳；

2） 如果收到的报文来自最优下一跳，也将报文发送给备份下一跳；

3） 其他情况均将报文发送给最优下一跳.

下面通过一个例子来解释转发算法. 在图3 中，假设报文的源地址是c，目的地址是d，当结点a出现故障时，结点c将报文转发给备份下一跳f，结点f发现该报文来自于自己的最优下一跳c，因此结点f将报文发送给其备份下一跳e，接着结点e将报文转发给最优下一跳b，最后b将报文转发给目的地址d.

3.2 基于遗传算法构造转发图的算法

下面重点描述如何解决问题2. 给定目的地址d，构造G（d）就是为网络拓扑中的链路设定特定的方向. 其中G（d）包含r（d）的条件比较容易实现，只需要在反向最短路径树r（d）的基础上构造转发图即可.如何保证构造的图是转发图成为本文研究的重点和难点. 构造转发图就是为网络中的链路指定方向，对于网络中的链路(u,v)∈E，每条链路有4 种状态：第1种状态是该链路不在转发图中；第2 种状态是该链路的方向为u→v；第3 种状态是该链路的方向为v→u；第4 种状态是u→v和v→u都在转发图中，用v−u来表示. 如果(u,v)∈r（d），假设链路的方向为u→v，则该链路的状态只有u→v和v−u这2 种可能性；反之假设链路的方向为v→u，则该链路的状态只有v→u和v−u这2 种可能性. 通过上述分析可知当链路(u,v)∈r（d）时，该链路的状态有2 种可能性；当(u,v)∉r（d），则该链路的状态有4 种可能性；对于一个包含|V|个结点、|E|条边的网络拓扑来讲，有|V|−1 条链路在反向最短路径树上，|E|+|V|+1 条链路不在反向最短路径树上，因此链路状态的数量为2|V|−1×4|E|−|V|+1=22×|E|−|V|+1，如果把所有的链路状态的组合都枚举出来，然后从中选择符合条件的转发图，在实际网络中部署是一种不现实的解决方案.

为了解决该问题，本文提出利用遗传算法来构造转发图，该算法包含2 个步骤：1）计算以结点d为根的反向最短路径树r（d）；2）在r（d）的基础上，利用遗传算法构造转发图.

算法1（RPBFG 算法）描述了利用遗传算法构造转发图的过程. 算法的输入为网络拓扑结构G=（V,E），输出为每个结点的备份路由表. 下面以目的地址d为例进行描述.RPBFG 主要通过3 个步骤实现：首先对网络中的链路进行编码，在链路编码的基础上生成初始转发图；然后利用选择、交叉和变异操作计算出最优个体，根据选择的最优个体构造出最优转发图；最后根据最优转发图计算出所有结点的备份下一跳.

算法1.RPBFG 算法.

在介绍RPBFG 之前，我们描述链路编码的算法和适应度函数. 首先描述链路编码的算法. 对于网络中的链路(u,v)∈E，用2 位二进制编码来表示链路的状态：因此每条链路有4 种状态：00 表示该链路不在转发图中，01 表示该链路的方向为u→v，10 表示该链路的方向为v→u,11 表示该链路的方向为v−u.例如网络中有5 条链路，分别是（a,b）,（b,c）,（c,d）,（a,d）,（b,d），如果对应的链路编码为（1001101101），则表示链路（a,b）的方向为a→b，链路（b,c）的方向为c→b，链路（c,d）的方向为c→d，链路（a,d）的方向为a→d，链路（b,d）的方向为d→b. 然后描述适应度函数. 为了保证RPBFG 在满足最大化故障保护率的同时，尽可能降低重路由路径的路径拉伸度，本文的适应度函数=故障保护率+0.001×路径拉伸度. 下面详细介绍算法RPBFG 的执行过程，如算法1 所示. 将备份下一跳集合初始化为空（行①～③）；对于网络中的结点d∈V，利用迪杰斯特拉算法计算反向最短路径树r（d）（行④）. 行⑤表示生成初始化种群，本文利用r（d）生成初始种群，所有种群的规模数为N，所有初始种群的编码相同. 遗传算法的迭代过程中迭代次数为m（行⑥），在每次迭代中，利用轮盘赌算法[29]进行选择操作，该算法根据个体的适应度和累计概率计算个体被选择的概率，轮盘赌选择中个体的适应度越好越有可能被保留，如果要保留n个个体，则在现有的2n个个体中进行n次有放回抽样，每次抽样中每个个体被抽中的概率为其中pi表示该个体被保留的概率，fi表示该个体的适应度，表示所有个体适应度之和（行⑦ ）. 行⑪和行⑫分别表示交叉和变异操作. 本文使用的交叉方法为多点交叉. 具体方法为：首先将要执行交叉的2 个个体分别表示为A和B，然后随机选择若干个位置（每个位置被选择的概率是提前设置好的），将这些位置记为{i1,i2,…,in}，而后将A和B中的{i1,i2,…,in}位置上的基因相互交换. 算法1 中使用2 个位置的基因表示1 条边的方向，所以在交叉互换的过程中将基因两两视为一个整体，以确保边的方向信息作为整体被交换.

本文采用的变异方法为：用变异率p表示基因变异的概率，当1 个染色体发生变异时，它的每个基因都按照概率p发生变异，当某个位置的基因发生变异时，如果基因未变异概率为1，则基因概率变异为0，反之，如果基因未变异概率为0，则基因概率变异为1. 为了保证变异后的染色体所表示的转发图不产生路由环路，在每次变异后都会检查其是否产生了环路，如果这次变异导致了环路，那就将该基因还原. 需要注意的是，染色体中表示最短路径树中有向边的基因不会发生变异，因为这些基因表示的是最优下一跳. 当迭代部分执行完毕以后，根据最优个体Best（population）中链路的方向利用ComputeFG（Best（population））计算出转发图（行⑰）；然后利用该转发图为网络中的其他结点计算到达目的地址d的备份下一跳，为结点v∈V,v≠d计算备份下一跳的算法如下：遍历结点v的不是最优下一跳的邻居结点v，如果该边的编码为10 或者11，则结点u可以将结点v作为备份下一跳（行⑱～⑳）. 当算法1 执行完毕以后，返回所有结点到达目的结点d的备份下一跳集合（行㉑）.

下面分析算法的时间复杂度. 算法1 的行①～③的时间复杂度为O(|V|)，行④的时间复杂度为O(|V|lg|V|+|E|)，行⑤的时间复杂度为O(N)，行⑥～⑯的时间复杂度为O(N×m)，行⑰的时间复杂度为O(|E|)，行⑱～⑳的时间复杂度为O(|V|)，RPBFG 的总时间复杂度为O(|V|)+O(|V|lg|V|+|E|)+O(N)+O(N×m)+O(|E|)+O(|V|)，即O(|V|lg|V|+2|E|+N×m).

4 实验及结果分析

本节将RPBFG与NPC，U-turn，MARA-MA，MARASPE 进行比较，采用Python 实现这5 种算法. 实验采用了11 种真实的网络拓扑结构[30]，如表3 所示，使用真实拓扑结构使得实验结果更加真实准确. 实验采用的度量指标包括故障保护率和路径拉伸度. 故障保护率反映了算法应对网络中发生故障的能力，该值越大说明算法应对故障的能力越强. 路径拉伸度表示当网络出现故障以后，重路由路径的代价和最短路径的代价的比值，该值越小说明利用路由保护算法计算出的路径代价和利用最短路径计算出的路径代价接近，给网络带来的额外开销越低.

Table 3 Real Network Topology表3 真实网络拓扑

4.1 故障保护率

本节比较算法RPBFG，NPC，U-turn，MARA-MA，MARA-SPE 的故障保护率. 图4 描述了5 种算法在11 个真实网络拓扑图中的故障保护率. 在所有实验的网络拓扑结构中RPBFG 的故障保护率均为1.0，NPC，U-turn，MARA-MA，MARA-SPE 的故障保护率均低于1.0. 例如，在Abilene 中，NPC，U-turn，MARAMA，MARA-SPE 对应的故障保护率分别是0.48 ，0.75，0.85 ，0.88，在Arpanet 19728 中， NPC，U-turn，MARAMA，MARA-SPE 对应的故障保护率分别是0.07，0.23 ，0.81 ，0.84. 这是因为NPC，U-turn，MARA-MA，MARASPE 使用一定的规则计算备份下一跳，因为这些规则和网络拓扑结构密切相关，在某些网络拓扑结构中无法为所有的源目的结点对计算符合这些规则的备份下一跳. 而RPBFG 与网络拓扑无关，只要网络中存在的路径可以到达目的地址，RPBFG 就可以计算出相应的重路由路径.

Fig. 4 Failure protection ratio of different algorithms in real topologies图4 不同算法在真实拓扑中的故障保护率

4.2 路径拉伸度

在计算路径拉伸度的过程中，为了体现公平性，只考虑2 个算法都能保护的路径. 具体计算算法为：算法A可以保护所有源目的结点对的集合 α，算法B可以保护所有源目的结点对集合 β，这2 个集合的交集C=α∩β就是需要计算的源目的结点对集合. 表4列出了RPBFG 和NPC 的路径拉伸度的平均值和方差. 表5 列出了RPBFG 和U-turn 的路径拉伸度的平均值和方差. 表6 列出了RPBFG 和MARA-MA 的路径拉伸度的平均值和方差. 表7 列出了RPBFG 和MARA-SPE 的路径拉伸度的平均值和方差. 从表4～7 可以看出，RPBFG 的路径拉伸度的平均值和方差几乎明显低于其余4 种算法. 在平均路径拉伸度方面，RPBFG比NPC，U-turn，MARA-MA，MARA-SPE 分别降低了0.11%，0.72%，37.79%，36.26%.

Table 4 Comparison Result of Path Stretch for NPC and RPBFG表4 NPC 和PBFG 路径拉伸度比较结果

Table 5 Comparison Result of Path Stretch for U-turn and RPBFG表5 U-turn 和RPBFG 路径拉伸度比较结果

Table 6 Comparison Result of Path Stretch for MARAMA and RPBFG表6 MARA-MA 和RPBFG 路径拉伸度比较结果

Table 7 Comparison Result of Path Stretch for MARASPE and RPBFG表7 MARA-SPE 和RPBFG 路径拉伸度比较结果

5 结 论

为了应对网络中频繁出现的故障，本文提出了一种基于转发图的域内路由保护算法（RPBFG），该算法通过构造最优转发图应对网络故障. 与已有路由保护算法不同，RPBFG 仅为每个结点存储1 个备份下一跳，这样可以大大降低存储开销. 我们首先描述了需要解决的关键科学问题；然后理论分析直接求解的复杂度；接着采用遗传算法来解决提出的问题，从而降低求解的复杂度；最后在11 个真实拓扑中对RPBFG 的性能进行了测试. 仿真测试表明该算法可以应对网络中所有可能的单故障情形，并且具有较小的路径拉伸度. RPBFG 是一种域内路由保护算法，在未来的工作中将研究如何将RPBFG 的核心思想应用到域间路由保护算法中，从而进一步提高网络的可用性.

作者贡献声明：耿海军提出了算法思路和实验方案，并撰写论文；孟卓负责执行实验方案；姚珊珊参与实验方案指导和对部分实验结果分析；杨静参与论文校对和实验方案指导；池浩田提出了指导意见并修改论文；尹霞提出方法的指导意见和审核论文.