基于重构SPT的单链路故障路由保护方法

侯巍 耿海军 畅江

摘 要：为了减少故障对网络运行带来的影响，提出了一种基于重构SPT的单链路故障路由保护算法SLFRPRSPT。该算法在最短路径树SPT的基础上实现，通过制定一系列定义和规则，对SPT进行重构，搜索节点关系发生改变的节点，为每个节点计算最佳备份下一跳节点，从而达到提高路由可用性的目的。经过实验验证，其在网络拓扑中故障保护率可以达到1，并且具有较低的路径拉伸度，可以有效避免单链路故障带来的影响。该方案支持增量部署和逐跳转发，便于实现。

关键词：单链路故障；节点关系；重构SPT；增量部署

中图分类号：TP309.7   文献标志码：A   文章编号：1001-3695（2024）01-037-0237-05

doi：10.19734/j.issn.1001-3695.2023.06.0203

Single-link fault routing protection method based on reconfigured SPT

Abstract：To reduce the impact of failures on the network operation，this paper proposed a single link failure routing protection algorithm SLFRPRSPT（single link failure routing protection algorithm based on reconstructed SPT） when facing frequent single-link failures in the network.The algorithm implemented the reconstruction of the shortest path tree （SPT） by formulating a series of definitions and rules，searching for nodes with changed node relationships，and calculating the best backup next-hop node for each node.This approach aimed to improve routing availability.After conducting experimental verification，the algorithm achieves a fault protection rate of 1 in the network topology and exhibits a low path stretch.It effectively avoids the impact of single link failure.Additionally，the scheme supports incremental deployment and hop-by-hop forwarding，making implementation easier.

Key words：single-link failure；node relationship；reconfigured SPT；incremental deployment

0 引言

互聯网的起源最早可追溯至上个世纪60年代。当时，美国国防部为在军方内不同部门和机构之间实现数据共享与交流，设计出来阿帕网（ARPANET）［1］，并在七十年代开始向其他国家和地区推广运用。起初的互联网结构单一，节点较少，管理便捷。然而，进入高度信息化社会的今天，随着计算机技术的快速普及和运用，人们对信息的需求也越来越大［2，3］。互联网规模和结构变得越来越复杂。但与此同时，网络中可能会遇到各种各样的故障问题，例如因为光纤切断和端口损坏导致的物理原因，还有因为MAC地址冲突导致的链路层原因以及因为IP地址错误导致的网络层原因等，这些给互联网的运行带来了巨大挑战［4，5］。

单链路故障路由是指在互联网中，由于物理和逻辑等因素导致某条链路发生中断或者异常，从而导致数据包无法正常在该链路上进行传输。单链路故障会造成路由节点之间无法正常通信，可能会形成数据孤岛［6］，还可能会造成数据包丢失，这严重影响了网络的运行效率和稳定性，使得网络收敛时间增加，大大降低了域内路由的可用性。这引起学术界和工业界的重视，对此，国内外研究者已经做了大量研究，并提出了不同的保护方案，这些保护方案可以分为基于逐跳和基于非逐跳两大类。无环路备选项（loop free alternates，LFA）［7，8］是基于逐跳保护方案的代表，它又可以分为LFC、NPC、DC三类规则，这些规则的核心思想是通过不同的计算方法，选择满足条件的邻居节点作为节点的备份下一跳。以DC规则为例，假设计算节点为a，目的节点为d，b是计算节点的邻居节点，c是计算节点的最优下一跳节点，它们之间应满足dist（b，d）

研究表明，在互联网发生的故障中单链路故障占到了约70％［12］，因此本文主要关注如何设计保护方案来减少单链路故障对路由带来的影响。最短路径树（shortest path tree，SPT）被广泛应用在路由保护方案中［13，14］，它容易实现，且复杂度较低，可以显著降低算法开销。但存在以下两个方面的不足：a）基于最短路径树的保护方案效果不稳定，有些保护方案的故障保护率很低，无法保证网络的可靠性；b）有些保护方案没有充分利用最短路径树，可能会导致流量在某条链路上大量聚集，从而造成路由堵塞的发生。因此根据上述分析，为了减少单链路故障对路由的影响，本文提出了一种基于重构SPT的单链路故障路由保护方法，通过重构最短路径树，改进在利用最短路径树过程中的不足，进而提升路由的可靠性。本文的贡献总结如下：a）提出三条备份下一跳选取规则；b）对于不满足三条规则的节点，对其相连链路进行基于重构SPT计算，保证节点在遇到故障时的可用性；c）通过路径拉伸度等指标进行实验对比，确保在不增加网络开销的前提下进行故障规避，大大提高了网络运行效率与路由可用性。

1 网络模型和问题描述

为方便各位读者理解，本章将对网络模型和相关定义进行介绍，并以此为基础描述本文需要解决的科学问题，表1对本文中的符号作出解释。

1.1 网络模型和基本理论

现实世界中的网络是由许多庞大而复杂的网络拓扑构成，而网络拓扑可以抽象表示为一个无向连通图G=（V，E，weight），其中V是指包含该图中所有节点（路由器）的集合，weight（u，v）是指包含该图中所有边（链路）的集合。weight是指该图中所有边上的权重和，权重又可以称为“代价”，“代价”可以是丢包率、带宽等属性。其中，weight（u，v）是指节点u和v连边上的权值（“代价”）。sp（s，d）是指从源节点s到目的节点d的最短路径树上的链路集合。为了便于描述本文模型和问题，本文中存在如下定义。

定义1 最短路径集合。给定一个拓扑图G=（V，E），对于任意节点d∈V，将其作为目的节点，通过Dijkstra算法［15］计算出所有节点到目的节点d的最短路径集合，记为Td={P1，P2，…，P|V|-1}。其中：P1代表在图G中从第一个节点到目的节点d的最短路径；P2 代表在图G中从第二个节点到目的节点d的最短路径；P|V|-1代表在图G中从最后一个未被访问的节点到目的节点d的最短路径（P1≠P2≠……≠P|V|-1）。

定义3 孩子节点、子树。由拓扑图G=（V，E）生成的最短路径树为TEd（V，Ed），对于任意节点v∈V，child（v）表示节点v的孩子节点，parent（v）表示节点v的父亲节点，subtree（v，TEd）表示在最短路树TEd中，以节点v为根节点（包含v节点在内）生成的子树，它是最短路径树的一部分。

定义4 健壮网络拓扑结构。给定一个拓扑图G=（V，E），任意单条链路e∈E发生故障时，拓扑中的全部节点仍然保持连通，数据包仍然可以正常转发和接收，则称这个网络拓扑结构是健壮网络拓扑结构。

上述定义是本文的一些基本概念，它们构成了网络模型的雏形，其中，核心是围绕G=（V，E）最短路径树为中心展开研究。在拓扑图G=（V，E）中，根据最短路径树TEd寻找节点n的父亲节点pn，这样的父亲节点称为节点n的最佳下一跳节点，即bestn（n，d）=pn，下面用一个例子来说明上述定义。

在给定拓扑G=（V，E，weight）中，由G生成的以节点10为根的最短路径树TE10，如图1所示。在图1中包含的节点集合为V={0，1，2，3，4，5，6，7，8，9，10}，包含的边集合为E={（0，1），（1，2），（1，3），…}实线代表最短路径树中的边，虚线则代表在拓扑G中但不在最短路径树中的边。其中，（10，9）表示从节点10到9的边，边上的数字233表示边的权重为233，即weight（10，9）=233。由图1可知，从节点2到目的节点10的最短路径链路集合sp（2，10）={（2，5），（5，8），（8，10）}。节点7的父亲节点为节点6，节点6也是最佳下一跳节点，即parent（7）=6，child（6）=7，bestn（7，10）=6。

下面是网络模型的几个关键定义。

定义5 依附关系。假设某一网络拓扑的最短路径树为TEd（V，Ed），对于节点n∈TEd，其被分为两个分支subtree（d，TEd）和subtree（v，TEd），其中，第一个分支仍然是以目的节点d为根的最短路径树，那么满足以下两个条件的关系称为节点的依附关系。

a）原先的最短路径树中包含节点n 和其父亲节点，即{n & parent（n，TEd）}∈TEd。

b）拓扑中发生链路故障之后，节点n在以节点v为根的子树subtree（v，TEd）中，但节点n的父亲节点不属于subtree（v，TEd）分支，而是属于另一个分支subtree（d，TEd），这样的关系可以用符号表示为parent（n）subtree（v，TEd） & parent（n）∈subtree（d，TEd）。

定理1 当f（u，best（u，d））发生时，v∈subtree（u，TEd）且在新的最短路由树上parent（v）subtree（u，TEd），即当有链路发生故障时，在以u为根节点的子树中，一定存在节点依附于别的分支。

证明 使用反证法，若f（u，best（u，d））发生，假设不存在一对具有父子关系的节点x和y，使得x∈subtree（u，TEd）且ysubtree（u，TEd），即以节点u为根的子树中不存在某一节点依附于别的分支，则拓扑图不再连通。這与本文的健壮网络拓扑结构定义相矛盾。即原假设不成立，定理得证。

定义6 重构SPT。假设某一网络拓扑的最短路径树为TEd（V，Ed），断开某一与根节点d相连的链路e∈Ed，此时最短路径树分为两个分支，其中一个是以节点d为根的子树subtree（d，TEd），另外一个是以节点v为根的子树subtree（v，TEd），且节点v存在节点依附关系，存在节点v的父亲节点依附于subtree（d，TEd）分支上，则称这个过程叫做重构SPT。

在发生重构SPT之后，有如下关系：n∈subtree（v，TEd），parent（n）subtree（v，TEd），parent（n）∈subtree（d，TEd），则节点n在重构后新的最短路径树中其父亲节点依附于别的分支，则称这类节点为优先节点（priority node），优先节点的父亲节点是节点的最佳备份下一跳节点，即backn（n，d）=parent（n）。

定义7 父子节点关系互换。节点m和其父亲节点n原先同属于一棵最短路径树，在发生某种变化之后，它们之间的关系改变，即节点n的父亲节点为节点m，这样的关系改变称为父子节点关系互换，用式（1）来表示。

1.2 问题描述

本文要解决的问题可以描述为：在双连通图中，当单链路故障路由发生之后，如何设计保护方案，可以最大限度减少对网络运行的影响。用符号hop（v，G）表示在拓扑图G中节点v的下一跳节点数量，目标是要使得拓扑中的节点拥有尽可能多的下一跳节点，在双连通图中，就是要使得除了目的节点外，每个节点都拥有两个下一跳，分别是最佳下一跳和最佳备份下一跳。本文问题可以描述成为一个整数线性规划（integer linear programming，ILP）问题［16］，即

式（2）是ILP问题的目标函数，在上述约束条件中，式（3）说明本文是在双连通图（biconnected components of graph，BCG）上进行的研究，式（4）提到本文的最短路径树是由图中的每个节点到目的节点的最短路径上的链路集合所构成。节点之间的依附关系用式（5）进行表示。有了节点的依附关系之后，式（6）则表示重构SPT，最短路径树被划分为两个子树，式（7）说明父子节点关系互换，这是寻找节点最佳备份下一跳的关键。

2 转发机制和选取最佳备份下一跳的步骤

本文主要解决的问题是设计一种路由保护算法，该算法可以为每一个源-目的节点对计算一个最佳下一跳节点和一个最佳备份下一跳节点。为了完成该目标，本文首先设计了报文的转发规则，然后提出了选取最佳备份下一跳的步骤。

2.1 转发机制

在拓扑G=（V，E）中，当数据报文开始在网络拓扑中进行传输时，它有以下两条转发机制，决定报文应该往拓扑中哪个节点进行转发。假设节点v收到报文时，节点应该将报文转发至：

a）最佳下一跳节点。如果在拓扑中，节点v到目的节点的最佳下一跳没有发生故障，则报文被转发至最佳下一跳节点。

b）最佳备份下一跳节点。此时分两种情况。（a）节点v无法将数据报文发送到最佳下一跳节点，即发生了单链路故障f（v，d），则节点v将报文转发至最佳备份下一跳节点。（b）节点v收到来自其最佳下一跳节点发送过来的报文，这说明路径上必定发生了故障，这个可以表示为f（bestn（v，d），d），即节点的最佳下一跳节点到目的节点的路径发送了故障，则节点v将报文转发至最佳备份下一跳节点。

2.2 选取最佳备份下一跳的步骤

根据上面所说的转发机制，本文将以此为基础，介绍选取最佳备份下一跳的步骤，其大致思路为：逐一分支处理，为本分支的所有节点寻找最佳备份下一跳，当本分支所有节点寻找到最佳备份下一跳之后，开始处理下一分支。需要注意的是，在发生重构SPT之后，TEd（V，Ed）被分成subtree（d，TEd）和subtree（v，TEd）两个分支。其中，在存在优先节点的subtree（v，TEd）分支上，如果有父子节点关系互换的节点，则它们存在最佳备份下一跳，即节点的父亲节点，否则，继续断开链路，重构SPT。

假设bestn（u，d）是节点u到目的节点d在最短路径上的最佳下一跳，backn（u，d）是节点u的最佳备份下一跳，最佳备份下一跳需要满足以下三个条件：a）bestn（u，d）sp（backn（u，d），d）；b）backn（u，d）是节点u在重构SPT之后的父亲节点；c）需要满足cost（u，（backn（u，d）））+cost（（backn（u，d）），d）为最小代价路径。下面用一个例子来说明选取最佳备份下一跳的步骤。

假设将节点10与9之间的链路断开，根据上述定义重构SPT，节点7存在父亲节点8依附于不同分支，得到如图2所示结构，图中可以看做将图3划分为subtree（10，TE10）和subtree（7，TE10）两个子树。其中边的代价与图1相同，不再图中标出。在图3中，节点7的父亲节点是节点6，即节点7的最佳下一跳节点是节点6，用符号表示为bestn（7，10）=6。而在图2中，节点7的父亲节点是节点8，从图中可以看出，节点8与7不属于同一子树，7∈subtree（7，TE10） & 8subtree（7，TE10），节点7就是定义6中定义的优先节点，其最佳备份下一跳节点为节点7中依附于其他分支的父亲节点8，即backn（7，10）=parent（7）=8。下面为处理某一分支的详细步骤。

a）从原始拓扑中构造以节点10为目的节点的最短路径树TE10（V，E10），如图3所示。

b）假设此分支中节点9与根节点10相连的链路发生故障，即f（9，10）。重构最短路径树TE10（V，E10），由于重构后，最短路径树中节点7存在依附关系，所以节点7是優先节点（prioritynode），故可以将最短路径树划分为subtree（10，TE10）和subtree（7，TE10），如图2所示。

c）遍历subtree（7，TE10）分支，并将优先节点在重构后的父亲节点8，作为优先节点的最佳备份下一跳。可以表示为

7∈subtree（7，TE10），parent（7）subtree（7，TE10）（8）

backn（7，10）=parent（7）=8（9）

d）深度遍历优先节点7的孩子节点child（7）={6，4}，如果该孩子节点发生了父子节点关系互换，则重构后的父亲节点作为该节点的最佳备份下一跳，例如节点6在分支中的父亲节点是节点7，但在原最短路径树中，节点7是节点6的孩子节点，则将节点7作为节点6的最佳备份下一跳节点。然后继续深度遍历，出现以下两种情况后停止遍历。

（a）遍历到空节点，即child（9，subtree（7，TE10））=。

（b）遍历到的节点不符合父子节点关系互换条件，即表示为

parent（child（7，subtree（7，TE10）））=

parent（child（7，subtree（7，TE10）），TE10（V，E10））（10）

例如在图2中，节点7的孩子节点4，节点4的父亲节点在subtree（7，TE10）分支中是节点7，同时在重构SPT之前，节点4的父亲节点在TE10（V，E10）中仍然是节点7，没有发生父子节点关系互换，故停止遍历。

e）在深度遍历过程中，若出现节点v∈subtree（7，TE10）符合步骤d）中的停止遍历条件（b），则删除链路（v，parent（v，subtree（7，TE10））），继续执行步骤b）～d）。

3 SLFRPRSPT算法

SLFRPRSPT算法主要分为以下两个算法，其中算法1描述了逐个处理原最短路径树中各个分支的节点{d1，d2，d3，…}∈child（d，TEd），每个分支生成的子樹为subtree（b1，TEd），subtree（b2，TEd），…。假设发生f（d1，d），对于处理节点d1分支的主要思想是，重构最短路径树TEd，得到其生成子树subtree（b1，TEd），然后比对新旧最短路由树。算法2具体描述了删除某条链路之后，如何通过比对新旧最短路由树，来为该分支上的节点找到最佳备份下一跳。其主要思想为，通过比对新旧最短路由树，找出依附在别的分支上的节点，并存储其最佳备份下一跳。

算法1 handlebranch（G，d）算法

输入：G（V，E，weight），TEd。

输出：backn（V，d）。

1 for v∈V do

2   backn（v，d）←

3 end for

4 for di∈TEd do

5   sptcompare（G，d，di）

6 end for

算法1中的输入为一个有向带权图G（V，E，weight），一个目的节点d，一个最短路径树TEd，算法的输出是节点集合V中每个节点v到目的节点d的最佳备份下一跳节点。伪代码中的第1行表示对图中的每个节点v，执行以下操作。第2行是将backn（v，d）赋值为空集合，表示节点v到d的最佳备份下一跳集合为空。第4行表示在最短路径树TEd中，遍历重构SPT中的每个分支子树的根节点di，并执行以下操作。算法第5行调用sptcompare（G，d，di）函数，该函数会删除边（d，di），并重新计算最短路径树，然后比对新旧最短路径树，为节点找到其最佳备份下一跳。

算法2 sptcompare（G，d，u）算法

输入：G（V，E，weight），TEd。

输出：backn（V，d）。

1 for n∈subtree（u，TEd） do

2  if parent（n，subtree（u，TEd））subtree（u，TEd） do

3   backn（u，d）←parent（n，TEd）

4   x←child（u，subtree（u，TEd））

5   if parent（x）subtree（u，TEd） do

6    backn（x，d）←parent（x）

7   else sptcompare（G，d，x）

8   end if

9  end if

10 end for

算法2的主要目的是删除链路，为图中的节点找到最佳备份下一跳，以保证在发生故障时仍然能够到达目的节点。之后重构最短路径树，并对新旧最短路径树进行比对，找出哪些节点的父子节点关系发生了变化，为它们找到最佳备份下一跳节点。

算法中的第1行在最短路径子树subtree（u，TEd）中对每个节点n执行以下操作。第2行，如果在最短路径子树subtree（u，TEd）中，节点n的父亲节点不属于以节点u为根节点的子树subtree（u，TEd）中，则执行以下操作。第3行将节点n在TEd中的父亲节点添加到backn（u，d）中，表示它是节点u到d的最佳备份下一跳节点。第4行将子树subtree（u，TEd）中节点u的孩子节点赋值给节点x。第5行表示如果节点x的父亲节点u不属于子树subtree（u，TEd），则在第6行中，将节点x的父亲节点parent（x）加入到节点x到d的最佳备份下一跳集合backn（x，d）中。否则，第7行中将节点x传入sptcompare（G，d，x）函数进行递归遍历，递归查找节点x的最佳备份下一跳。这个算法是递归的，也就是说，它会不断地删除边，重新计算最短路径树SPT，比对新旧最短路径树，直到找到所有节点的最佳备份下一跳为止。以下是算法的时间复杂度分析。

定理2 SLFRPRSPT算法的时间复杂度为

O（|V|）+O（（|V|-1）（log |V|×log |E|））（11）

证明 SLFRPRSPT算法分为handlebranch（G，d）算法和sptcompare（G，d，u）算法两部分。在式（11）中，O（|V|）表示循环遍历节点集合V的时间复杂度。加号后面第一项（|V|-1）表示在handlebranch（G，d）算法中遍历除目的节点以外的节点所需要的时间复杂度，同时调用sptcompare（G，d，u）算法，其时间复杂度为log |E|。在sptcompare（G，d，u）算法中，首先会对子树中的节点进行循环，所以其时间复杂度为log |V|。在算法中，会进行递归条件判断，若满足递归条件，则继续进行递归，所以需要log |E|的时间复杂度。因此，算法的时间复杂度可以表示为O（|V|）+O（（|V|-1）（log |V|×log |E|））。

4 实验结果及分析

本章将在真实拓扑上进行实验，实验环境采用酷睿i7系列处理器，16 GB内存，为了能更好说明算法的保护效果，本文利用故障保护率和路径拉伸度这两个指标对实验结果进行分析。

LFC和DC算法是目前比较受欢迎的路由保护方案［17，18］，下面对它们进行详细介绍。DC（downstream condition）算法主要对节点的邻居节点进行遍历，从而寻找其下一跳节点。假设计算节点为a，目的节点为d，b是节点a的邻居节点，则它们之间应满足规则dist（b，d）

通过对比SLFRPRSPT、DC和LFC算法在不同拓扑下故障保护率和路径拉伸度的表现情况，分析得到可以获得最佳路由保护效果的算法。下面将从实验拓扑、故障保护率、路径拉伸度三个方面来介绍本次实验。

4.1 实验拓扑

选取合适的实验拓扑是本文实验的关键。为了使实验可以更加全面、客观地评价不同算法的表现结果，本文采用真实环境下的网络拓扑进行实验。其中，真实拓扑是指实际存在的网络拓扑，用于验证和评估路由保护方案的适用性和实际效果，如表2所示，例如从互联网中得到的Abilene拓扑［19］，它是美国某教育网的拓扑结构。真实拓扑可以反映出真实网络世界中的各种特性和问题，比如节点分布、拓扑结构等，从而更加真实地评估路由保护方案的可用性和实用性。实验拓扑中的路由器数量在11～88，链路数量在14～92，本次实验的拓扑结构如表2所示。

4.2 故障保护率

在本文实验的不同算法中，它们都为每个节点计算尽可能多地最佳备份下一跳节点。在拓扑图G=（V，E）中，对于v∈V，如果节点v存在最佳备份下一跳节点，即backn（v，d）≠，那么就称这个节点v是被保护的节点，假设节点v为源节点，目的节点为d，则v-d称为被保护的源-目的节点对。

故障保护率是用来衡量一个算法保护效果的重要指标，它有如下定义：在拓扑图中，故障保护率是指拓扑图中被保护的源-目的节点对与拓扑图中所有源-目的节点对的比值。本小节利用故障保护率这一指标对比不同算法在不同拓扑下的实验结果，结果如图4所示。

图4（a）（b）展示了三种算法对不同拓扑进行故障保护率的实验结果。实验结果表明，本文基于重构SPT的单链路故障路由保护算法SLFRPRSPT在所有拓扑中的故障保护率均为1，明显优于另外两种算法的实验结果，SLFRPRSPT算法具有最佳保护效果，可以有效保护单链路故障路由，避免网络受到故障的影响。在V2008实验拓扑中，三种算法的故障保护率差距最为明显，最优的是SLFRPRSPT算法，故障保护率结果为1，其次是LFC算法，实验结果为0.068 97，效果最差的是DC算法，结果为0.045 45。另外，在NJLATA拓扑中，SLFRPRSPT和LFC算法的故障保护率都达到了1，但DC算法的故障保护率只有0.809 09，保护效果最低。实验结果的原因有：

a）SLFRPRSPT算法的设计目的在于为拓扑中的所有节点计算最佳备份下一跳，因此其可以百分之百保护拓扑中的节点。

b）SLFRPRSPT算法采取递归遍历的思想，如果有节点无法计算出最佳备份下一跳，则断开与节点相连链路，进行重构SPT计算，因此其故障保护率高。

c）LFC和DC算法仅通过考虑链路权重大小进行计算，没有充分考虑节点与节点之间的联系，而SLFRPRSPT算法通过寻找存在依附关系的节点，进行重构SPT，可以有效利用节点，寻找节点的最佳备份下一跳节点。

4.3 路径拉伸度

本小节用路径拉伸度来衡量算法计算出来的重路由路径的优劣。当链路发生故障时，路径拉伸度表示为算法计算出来的新重路由路径与用最短路径算法计算出来的原路由路径的比值。通过定义可知，路径拉伸度越小，算法计算出来的重路由路径与原路由路径越相近，不会给网络带来较多的额外开销和延迟，说明算法的效果越好。相反，如果路径拉伸度越大，说明算法计算出来的重路由路径与原路由路径差距越大，从而给网络带来额外的开销，算法的效果也越差。图5是不同算法在路径拉伸度指标下的实验结果。

如图5（a）（b）所示，通过对三种算法在路径拉伸度指标下的实验结果可知，本文SLFRPRSPT算法在三种算法的比较中，其路径拉伸度最高，其次是LFC算法，路径拉伸度最低的是DC算法，这是因为DC算法的故障保护率最低，被保护的节点较少，因此，其计算出来的重路由路径简单，路径拉伸度最低。而本文SLFRPRSPT算法保护拓扑中的所有节点，计算路径多于其他两种算法，因此其路径拉伸度稍高。对比算法性能时，首先比较故障保护率，故障保护率高的算法性能最优。但在故障保护率相同的情况下，对比其路径拉伸度，比如在NJLATA拓扑中，SLFRPRSPT和LFC算法的故障保护率均是1，但SLFRPRSPT算法的路径拉伸度为1.007 69，LFC算法的路径拉伸度为1.034 82，SLFRPRSPT算法具有较小的路径拉伸度，其性能最佳，可以有效节约网络资源，减少网络开销。

5 结束语

由于网络中单链路故障的频繁发生，本文在此背景下研究了一种基于重构SPT的单链路故障路由保护方法，针对单链路故障路由保护问题，该方法能够快速检测链路故障并进行故障切换，从而保障计算机网络的高可用性和稳定性。实验结果表明，本文SLFRPRSPT算法比其他方法具有更高的故障保护率，在故障保护率相同的前提下，具有更低的路径拉伸度，同时还能够保证数据的传输质量，加快路由收敛速度。该方法具有广泛的应用前景，例如在某公司的数据中心内部有多个服务器和交换机，服务器之间通过交换机连接，它们共同组成了一个类似于有向图的拓扑结构。若采用基于重构SPT的单链路故障路由保护方法，当发生网络故障时，网络中的节点可以选择最佳备份下一跳作为主選项，绕开故障链路，以此来进行数据的正常传输，从而确保网络的正常运行。

未來的研究可以从以下两个方面进行展开：a）结合多链路保护技术，进一步提高网络的可靠性和容错能力；b）通过优化路由保护方案，进一步降低算法的路径拉伸度。

参考文献：

［1］Crocker S D.The ARPANET and its impact on the state of networking［J］.Computer，2019，52（10）：14-23.

［2］叶朝阳，沈辰，黄明庆，等.互联网 BGP 路由可视及安全检测技术架构与实践［J］.电信科学，2021，37（12）：110-120.（Ye Chao-yang，Shen Chen，Huang Mingqing，et al.Internet BGP routing visibility and security detection technology architecture and practice［J］.Telecommunications Science，2021，37（12）：110-120.）

［3］Shen Fei.Internet use，freedom supply，and demand for internet freedom：a cross-national study of 20 countries［J］.International Journal of Communication，2017，11：2093-2114.

［4］Xing Liudong.Cascading failures in Internet of Things：review and perspectives on reliability and resilience［J］.IEEE Internet of Things Journal，2020，8（1）：44-64.

［5］Li Yuhong，Chen Kedong，Collignon S，et al.Ripple effect in the supply chain network：forward and backward disruption propagation，network health and firm vulnerability［J］.European Journal of Operational Research，2021，291（3）：1117-1131.

［6］Patel J.Bridging data silos using big data integration［J］.International Journal of Database Management Systems，2019，11（3）：1-6.

［7］Csikor L，Rétvári G.On providing fast protection with remote loop-free alternates：analyzing and optimizing unit cost networks［J］.Telecommunication Systems，2015，60（4）：485-502.

［8］Geng Haijun，Zhang Han，Shi Xingang，et al.Efficient computation of loop-free alternates［J］.Journal of Network and Computer Applications，2020，151：102501.

［9］Karthik K，Gunasekhar T，Meenu D，et al.A study on IP network recovery through routing protocols［J］.Indonesian Journal of Electrical Engineering and Informatics，2016，4（3）：176-180.

［10］Ridwan M A，Radzi N A M，Ahmad W S H M W，et al.Recent trends in MPLS networks：technologies，applications and challenges［J］.IET Communications，2020，14（2）：177-185.

［11］Papán J，Segeccˇ P，Moravcˇík M，et al.Overview of IP fast reroute solutions［C］//Proc of the 16th International Conference on Emerging eLearning Technologies and Applications.Piscataway，NJ：IEEE Press，2018：417-424.

［12］Shen Gangxiang，Wei Yue，Bose S K.Optimal design for shared backup path protected elastic optical networks under single-link failure［J］.Journal of Optical Communications and Networking，2014，6（7）：649-659.

［13］De Jonckère O，Fraire J A.A shortest-path tree approach for routing in space networks［J］.China Communications，2020，17（7）：52-66.

［14］Kravets O J，Atlasov I V，Aksenov I A，et al.Increasing efficiency of routing in transient modes of computer network operation［J］.International Journal on Information Technologies & Security，2021，13（2）：3-14.

［15］Luo Min，Hou Xiaorong，Yang Jing.Surface optimal path planning using an extended Dijkstra algorithm［J］.IEEE Access，2020，8：147827-147838.

［16］Bartlett M，Cussens J.Integer linear programming for the Bayesian network structure learning problem［J］.Artificial Intelligence，2017，244：258-271.

［17］Geng Haijun，Yao Jiangyuan，Zhang Yangyang.Single failure routing protection algorithm in the hybrid SDN network［J］.Computers，Materials & Continua，2020，64（1）：665-679.

［18］耿海军，施新刚，王之梁，等.基于最小路径交叉度的域内路由保护方案［J］.软件学报，2020，31（5）：1536-1548.（Geng Haijun，Shi Xingang，Wang Zhiliang，et al.Intradomain routing protection scheme based on minimum path crossing degree［J］.Journal of Software，2020，31（5）：1536-1548.）

［19］Tanha M，Sajjadi D，Ruby R，et al.Traffic engineering enhancement by progressive migration to SDN［J］.IEEE Communications Letters，2018，22（3）：438-441.