基于重構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.