基于重構(gòu)SPT的單鏈路故障路由保護(hù)方法

侯巍 耿海軍 暢江

摘 要：為了減少故障對網(wǎng)絡(luò)運(yùn)行帶來的影響，提出了一種基于重構(gòu)SPT的單鏈路故障路由保護(hù)算法SLFRPRSPT。該算法在最短路徑樹SPT的基礎(chǔ)上實(shí)現(xiàn)，通過制定一系列定義和規(guī)則，對SPT進(jìn)行重構(gòu)，搜索節(jié)點(diǎn)關(guān)系發(fā)生改變的節(jié)點(diǎn)，為每個(gè)節(jié)點(diǎn)計(jì)算最佳備份下一跳節(jié)點(diǎn)，從而達(dá)到提高路由可用性的目的。經(jīng)過實(shí)驗(yàn)驗(yàn)證，其在網(wǎng)絡(luò)拓?fù)渲泄收媳Ｗo(hù)率可以達(dá)到1，并且具有較低的路徑拉伸度，可以有效避免單鏈路故障帶來的影響。該方案支持增量部署和逐跳轉(zhuǎn)發(fā)，便于實(shí)現(xiàn)。

關(guān)鍵詞：單鏈路故障；節(jié)點(diǎn)關(guān)系；重構(gòu)SPT；增量部署

中圖分類號：TP309.7?? 文獻(xiàn)標(biāo)志碼：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 引言

互聯(lián)網(wǎng)的起源最早可追溯至上個(gè)世紀(jì)60年代。當(dāng)時(shí)，美國國防部為在軍方內(nèi)不同部門和機(jī)構(gòu)之間實(shí)現(xiàn)數(shù)據(jù)共享與交流，設(shè)計(jì)出來阿帕網(wǎng)（ARPANET）［1］，并在七十年代開始向其他國家和地區(qū)推廣運(yùn)用。起初的互聯(lián)網(wǎng)結(jié)構(gòu)單一，節(jié)點(diǎn)較少，管理便捷。然而，進(jìn)入高度信息化社會的今天，隨著計(jì)算機(jī)技術(shù)的快速普及和運(yùn)用，人們對信息的需求也越來越大［2，3］?；ヂ?lián)網(wǎng)規(guī)模和結(jié)構(gòu)變得越來越復(fù)雜。但與此同時(shí)，網(wǎng)絡(luò)中可能會遇到各種各樣的故障問題，例如因?yàn)楣饫w切斷和端口損壞導(dǎo)致的物理原因，還有因?yàn)镸AC地址沖突導(dǎo)致的鏈路層原因以及因?yàn)镮P地址錯(cuò)誤導(dǎo)致的網(wǎng)絡(luò)層原因等，這些給互聯(lián)網(wǎng)的運(yùn)行帶來了巨大挑戰(zhàn)［4，5］。

單鏈路故障路由是指在互聯(lián)網(wǎng)中，由于物理和邏輯等因素導(dǎo)致某條鏈路發(fā)生中斷或者異常，從而導(dǎo)致數(shù)據(jù)包無法正常在該鏈路上進(jìn)行傳輸。單鏈路故障會造成路由節(jié)點(diǎn)之間無法正常通信，可能會形成數(shù)據(jù)孤島［6］，還可能會造成數(shù)據(jù)包丟失，這嚴(yán)重影響了網(wǎng)絡(luò)的運(yùn)行效率和穩(wěn)定性，使得網(wǎng)絡(luò)收斂時(shí)間增加，大大降低了域內(nèi)路由的可用性。這引起學(xué)術(shù)界和工業(yè)界的重視，對此，國內(nèi)外研究者已經(jīng)做了大量研究，并提出了不同的保護(hù)方案，這些保護(hù)方案可以分為基于逐跳和基于非逐跳兩大類。無環(huán)路備選項(xiàng)（loop free alternates，LFA）［7，8］是基于逐跳保護(hù)方案的代表，它又可以分為LFC、NPC、DC三類規(guī)則，這些規(guī)則的核心思想是通過不同的計(jì)算方法，選擇滿足條件的鄰居節(jié)點(diǎn)作為節(jié)點(diǎn)的備份下一跳。以DC規(guī)則為例，假設(shè)計(jì)算節(jié)點(diǎn)為a，目的節(jié)點(diǎn)為d，b是計(jì)算節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，c是計(jì)算節(jié)點(diǎn)的最優(yōu)下一跳節(jié)點(diǎn)，它們之間應(yīng)滿足dist（b，d）

研究表明，在互聯(lián)網(wǎng)發(fā)生的故障中單鏈路故障占到了約70％［12］，因此本文主要關(guān)注如何設(shè)計(jì)保護(hù)方案來減少單鏈路故障對路由帶來的影響。最短路徑樹（shortest path tree，SPT）被廣泛應(yīng)用在路由保護(hù)方案中［13，14］，它容易實(shí)現(xiàn)，且復(fù)雜度較低，可以顯著降低算法開銷。但存在以下兩個(gè)方面的不足：a）基于最短路徑樹的保護(hù)方案效果不穩(wěn)定，有些保護(hù)方案的故障保護(hù)率很低，無法保證網(wǎng)絡(luò)的可靠性；b）有些保護(hù)方案沒有充分利用最短路徑樹，可能會導(dǎo)致流量在某條鏈路上大量聚集，從而造成路由堵塞的發(fā)生。因此根據(jù)上述分析，為了減少單鏈路故障對路由的影響，本文提出了一種基于重構(gòu)SPT的單鏈路故障路由保護(hù)方法，通過重構(gòu)最短路徑樹，改進(jìn)在利用最短路徑樹過程中的不足，進(jìn)而提升路由的可靠性。本文的貢獻(xiàn)總結(jié)如下：a）提出三條備份下一跳選取規(guī)則；b）對于不滿足三條規(guī)則的節(jié)點(diǎn)，對其相連鏈路進(jìn)行基于重構(gòu)SPT計(jì)算，保證節(jié)點(diǎn)在遇到故障時(shí)的可用性；c）通過路徑拉伸度等指標(biāo)進(jìn)行實(shí)驗(yàn)對比，確保在不增加網(wǎng)絡(luò)開銷的前提下進(jìn)行故障規(guī)避，大大提高了網(wǎng)絡(luò)運(yùn)行效率與路由可用性。

1 網(wǎng)絡(luò)模型和問題描述

為方便各位讀者理解，本章將對網(wǎng)絡(luò)模型和相關(guān)定義進(jìn)行介紹，并以此為基礎(chǔ)描述本文需要解決的科學(xué)問題，表1對本文中的符號作出解釋。

1.1 網(wǎng)絡(luò)模型和基本理論

現(xiàn)實(shí)世界中的網(wǎng)絡(luò)是由許多龐大而復(fù)雜的網(wǎng)絡(luò)拓?fù)錁?gòu)成，而網(wǎng)絡(luò)拓?fù)淇梢猿橄蟊硎緸橐粋€(gè)無向連通圖G=（V，E，weight），其中V是指包含該圖中所有節(jié)點(diǎn)（路由器）的集合，weight（u，v）是指包含該圖中所有邊（鏈路）的集合。weight是指該圖中所有邊上的權(quán)重和，權(quán)重又可以稱為“代價(jià)”，“代價(jià)”可以是丟包率、帶寬等屬性。其中，weight（u，v）是指節(jié)點(diǎn)u和v連邊上的權(quán)值（“代價(jià)”）。sp（s，d）是指從源節(jié)點(diǎn)s到目的節(jié)點(diǎn)d的最短路徑樹上的鏈路集合。為了便于描述本文模型和問題，本文中存在如下定義。

定義1 最短路徑集合。給定一個(gè)拓?fù)鋱DG=（V，E），對于任意節(jié)點(diǎn)d∈V，將其作為目的節(jié)點(diǎn)，通過Dijkstra算法［15］計(jì)算出所有節(jié)點(diǎn)到目的節(jié)點(diǎn)d的最短路徑集合，記為Td={P1，P2，…，P|V|-1}。其中：P1代表在圖G中從第一個(gè)節(jié)點(diǎn)到目的節(jié)點(diǎn)d的最短路徑；P2 代表在圖G中從第二個(gè)節(jié)點(diǎn)到目的節(jié)點(diǎn)d的最短路徑；P|V|-1代表在圖G中從最后一個(gè)未被訪問的節(jié)點(diǎn)到目的節(jié)點(diǎn)d的最短路徑（P1≠P2≠……≠P|V|-1）。

定義3 孩子節(jié)點(diǎn)、子樹。由拓?fù)鋱DG=（V，E）生成的最短路徑樹為TEd（V，Ed），對于任意節(jié)點(diǎn)v∈V，child（v）表示節(jié)點(diǎn)v的孩子節(jié)點(diǎn)，parent（v）表示節(jié)點(diǎn)v的父親節(jié)點(diǎn)，subtree（v，TEd）表示在最短路樹TEd中，以節(jié)點(diǎn)v為根節(jié)點(diǎn)（包含v節(jié)點(diǎn)在內(nèi)）生成的子樹，它是最短路徑樹的一部分。

定義4 健壯網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。給定一個(gè)拓?fù)鋱DG=（V，E），任意單條鏈路e∈E發(fā)生故障時(shí)，拓?fù)渲械娜抗?jié)點(diǎn)仍然保持連通，數(shù)據(jù)包仍然可以正常轉(zhuǎn)發(fā)和接收，則稱這個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是健壯網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

上述定義是本文的一些基本概念，它們構(gòu)成了網(wǎng)絡(luò)模型的雛形，其中，核心是圍繞G=（V，E）最短路徑樹為中心展開研究。在拓?fù)鋱DG=（V，E）中，根據(jù)最短路徑樹TEd尋找節(jié)點(diǎn)n的父親節(jié)點(diǎn)pn，這樣的父親節(jié)點(diǎn)稱為節(jié)點(diǎn)n的最佳下一跳節(jié)點(diǎn)，即bestn（n，d）=pn，下面用一個(gè)例子來說明上述定義。

在給定拓?fù)銰=（V，E，weight）中，由G生成的以節(jié)點(diǎn)10為根的最短路徑樹TE10，如圖1所示。在圖1中包含的節(jié)點(diǎn)集合為V={0，1，2，3，4，5，6，7，8，9，10}，包含的邊集合為E={（0，1），（1，2），（1，3），…}實(shí)線代表最短路徑樹中的邊，虛線則代表在拓?fù)銰中但不在最短路徑樹中的邊。其中，（10，9）表示從節(jié)點(diǎn)10到9的邊，邊上的數(shù)字233表示邊的權(quán)重為233，即weight（10，9）=233。由圖1可知，從節(jié)點(diǎn)2到目的節(jié)點(diǎn)10的最短路徑鏈路集合sp（2，10）={（2，5），（5，8），（8，10）}。節(jié)點(diǎn)7的父親節(jié)點(diǎn)為節(jié)點(diǎn)6，節(jié)點(diǎn)6也是最佳下一跳節(jié)點(diǎn)，即parent（7）=6，child（6）=7，bestn（7，10）=6。

下面是網(wǎng)絡(luò)模型的幾個(gè)關(guān)鍵定義。

定義5 依附關(guān)系。假設(shè)某一網(wǎng)絡(luò)拓?fù)涞淖疃搪窂綐錇門Ed（V，Ed），對于節(jié)點(diǎn)n∈TEd，其被分為兩個(gè)分支subtree（d，TEd）和subtree（v，TEd），其中，第一個(gè)分支仍然是以目的節(jié)點(diǎn)d為根的最短路徑樹，那么滿足以下兩個(gè)條件的關(guān)系稱為節(jié)點(diǎn)的依附關(guān)系。

a）原先的最短路徑樹中包含節(jié)點(diǎn)n 和其父親節(jié)點(diǎn)，即{n & parent（n，TEd）}∈TEd。

b）拓?fù)渲邪l(fā)生鏈路故障之后，節(jié)點(diǎn)n在以節(jié)點(diǎn)v為根的子樹subtree（v，TEd）中，但節(jié)點(diǎn)n的父親節(jié)點(diǎn)不屬于subtree（v，TEd）分支，而是屬于另一個(gè)分支subtree（d，TEd），這樣的關(guān)系可以用符號表示為parent（n）subtree（v，TEd） & parent（n）∈subtree（d，TEd）。

定理1 當(dāng)f（u，best（u，d））發(fā)生時(shí)，v∈subtree（u，TEd）且在新的最短路由樹上parent（v）subtree（u，TEd），即當(dāng)有鏈路發(fā)生故障時(shí)，在以u為根節(jié)點(diǎn)的子樹中，一定存在節(jié)點(diǎn)依附于別的分支。

證明 使用反證法，若f（u，best（u，d））發(fā)生，假設(shè)不存在一對具有父子關(guān)系的節(jié)點(diǎn)x和y，使得x∈subtree（u，TEd）且ysubtree（u，TEd），即以節(jié)點(diǎn)u為根的子樹中不存在某一節(jié)點(diǎn)依附于別的分支，則拓?fù)鋱D不再連通。這與本文的健壯網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)定義相矛盾。即原假設(shè)不成立，定理得證。

定義6 重構(gòu)SPT。假設(shè)某一網(wǎng)絡(luò)拓?fù)涞淖疃搪窂綐錇門Ed（V，Ed），斷開某一與根節(jié)點(diǎn)d相連的鏈路e∈Ed，此時(shí)最短路徑樹分為兩個(gè)分支，其中一個(gè)是以節(jié)點(diǎn)d為根的子樹subtree（d，TEd），另外一個(gè)是以節(jié)點(diǎn)v為根的子樹subtree（v，TEd），且節(jié)點(diǎn)v存在節(jié)點(diǎn)依附關(guān)系，存在節(jié)點(diǎn)v的父親節(jié)點(diǎn)依附于subtree（d，TEd）分支上，則稱這個(gè)過程叫做重構(gòu)SPT。

在發(fā)生重構(gòu)SPT之后，有如下關(guān)系：n∈subtree（v，TEd），parent（n）subtree（v，TEd），parent（n）∈subtree（d，TEd），則節(jié)點(diǎn)n在重構(gòu)后新的最短路徑樹中其父親節(jié)點(diǎn)依附于別的分支，則稱這類節(jié)點(diǎn)為優(yōu)先節(jié)點(diǎn)（priority node），優(yōu)先節(jié)點(diǎn)的父親節(jié)點(diǎn)是節(jié)點(diǎn)的最佳備份下一跳節(jié)點(diǎn)，即backn（n，d）=parent（n）。

定義7 父子節(jié)點(diǎn)關(guān)系互換。節(jié)點(diǎn)m和其父親節(jié)點(diǎn)n原先同屬于一棵最短路徑樹，在發(fā)生某種變化之后，它們之間的關(guān)系改變，即節(jié)點(diǎn)n的父親節(jié)點(diǎn)為節(jié)點(diǎn)m，這樣的關(guān)系改變稱為父子節(jié)點(diǎn)關(guān)系互換，用式（1）來表示。

1.2 問題描述

本文要解決的問題可以描述為：在雙連通圖中，當(dāng)單鏈路故障路由發(fā)生之后，如何設(shè)計(jì)保護(hù)方案，可以最大限度減少對網(wǎng)絡(luò)運(yùn)行的影響。用符號hop（v，G）表示在拓?fù)鋱DG中節(jié)點(diǎn)v的下一跳節(jié)點(diǎn)數(shù)量，目標(biāo)是要使得拓?fù)渲械墓?jié)點(diǎn)擁有盡可能多的下一跳節(jié)點(diǎn)，在雙連通圖中，就是要使得除了目的節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)都擁有兩個(gè)下一跳，分別是最佳下一跳和最佳備份下一跳。本文問題可以描述成為一個(gè)整數(shù)線性規(guī)劃（integer linear programming，ILP）問題［16］，即

式（2）是ILP問題的目標(biāo)函數(shù)，在上述約束條件中，式（3）說明本文是在雙連通圖（biconnected components of graph，BCG）上進(jìn)行的研究，式（4）提到本文的最短路徑樹是由圖中的每個(gè)節(jié)點(diǎn)到目的節(jié)點(diǎn)的最短路徑上的鏈路集合所構(gòu)成。節(jié)點(diǎn)之間的依附關(guān)系用式（5）進(jìn)行表示。有了節(jié)點(diǎn)的依附關(guān)系之后，式（6）則表示重構(gòu)SPT，最短路徑樹被劃分為兩個(gè)子樹，式（7）說明父子節(jié)點(diǎn)關(guān)系互換，這是尋找節(jié)點(diǎn)最佳備份下一跳的關(guān)鍵。

2 轉(zhuǎn)發(fā)機(jī)制和選取最佳備份下一跳的步驟

本文主要解決的問題是設(shè)計(jì)一種路由保護(hù)算法，該算法可以為每一個(gè)源-目的節(jié)點(diǎn)對計(jì)算一個(gè)最佳下一跳節(jié)點(diǎn)和一個(gè)最佳備份下一跳節(jié)點(diǎn)。為了完成該目標(biāo)，本文首先設(shè)計(jì)了報(bào)文的轉(zhuǎn)發(fā)規(guī)則，然后提出了選取最佳備份下一跳的步驟。

2.1 轉(zhuǎn)發(fā)機(jī)制

在拓?fù)銰=（V，E）中，當(dāng)數(shù)據(jù)報(bào)文開始在網(wǎng)絡(luò)拓?fù)渲羞M(jìn)行傳輸時(shí)，它有以下兩條轉(zhuǎn)發(fā)機(jī)制，決定報(bào)文應(yīng)該往拓?fù)渲心膫€(gè)節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)。假設(shè)節(jié)點(diǎn)v收到報(bào)文時(shí)，節(jié)點(diǎn)應(yīng)該將報(bào)文轉(zhuǎn)發(fā)至：

a）最佳下一跳節(jié)點(diǎn)。如果在拓?fù)渲?，?jié)點(diǎn)v到目的節(jié)點(diǎn)的最佳下一跳沒有發(fā)生故障，則報(bào)文被轉(zhuǎn)發(fā)至最佳下一跳節(jié)點(diǎn)。

b）最佳備份下一跳節(jié)點(diǎn)。此時(shí)分兩種情況。（a）節(jié)點(diǎn)v無法將數(shù)據(jù)報(bào)文發(fā)送到最佳下一跳節(jié)點(diǎn)，即發(fā)生了單鏈路故障f（v，d），則節(jié)點(diǎn)v將報(bào)文轉(zhuǎn)發(fā)至最佳備份下一跳節(jié)點(diǎn)。（b）節(jié)點(diǎn)v收到來自其最佳下一跳節(jié)點(diǎn)發(fā)送過來的報(bào)文，這說明路徑上必定發(fā)生了故障，這個(gè)可以表示為f（bestn（v，d），d），即節(jié)點(diǎn)的最佳下一跳節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑發(fā)送了故障，則節(jié)點(diǎn)v將報(bào)文轉(zhuǎn)發(fā)至最佳備份下一跳節(jié)點(diǎn)。

2.2 選取最佳備份下一跳的步驟

根據(jù)上面所說的轉(zhuǎn)發(fā)機(jī)制，本文將以此為基礎(chǔ)，介紹選取最佳備份下一跳的步驟，其大致思路為：逐一分支處理，為本分支的所有節(jié)點(diǎn)尋找最佳備份下一跳，當(dāng)本分支所有節(jié)點(diǎn)尋找到最佳備份下一跳之后，開始處理下一分支。需要注意的是，在發(fā)生重構(gòu)SPT之后，TEd（V，Ed）被分成subtree（d，TEd）和subtree（v，TEd）兩個(gè)分支。其中，在存在優(yōu)先節(jié)點(diǎn)的subtree（v，TEd）分支上，如果有父子節(jié)點(diǎn)關(guān)系互換的節(jié)點(diǎn)，則它們存在最佳備份下一跳，即節(jié)點(diǎn)的父親節(jié)點(diǎn)，否則，繼續(xù)斷開鏈路，重構(gòu)SPT。

假設(shè)bestn（u，d）是節(jié)點(diǎn)u到目的節(jié)點(diǎn)d在最短路徑上的最佳下一跳，backn（u，d）是節(jié)點(diǎn)u的最佳備份下一跳，最佳備份下一跳需要滿足以下三個(gè)條件：a）bestn（u，d）sp（backn（u，d），d）；b）backn（u，d）是節(jié)點(diǎn)u在重構(gòu)SPT之后的父親節(jié)點(diǎn)；c）需要滿足cost（u，（backn（u，d）））+cost（（backn（u，d）），d）為最小代價(jià)路徑。下面用一個(gè)例子來說明選取最佳備份下一跳的步驟。

假設(shè)將節(jié)點(diǎn)10與9之間的鏈路斷開，根據(jù)上述定義重構(gòu)SPT，節(jié)點(diǎn)7存在父親節(jié)點(diǎn)8依附于不同分支，得到如圖2所示結(jié)構(gòu)，圖中可以看做將圖3劃分為subtree（10，TE10）和subtree（7，TE10）兩個(gè)子樹。其中邊的代價(jià)與圖1相同，不再圖中標(biāo)出。在圖3中，節(jié)點(diǎn)7的父親節(jié)點(diǎn)是節(jié)點(diǎn)6，即節(jié)點(diǎn)7的最佳下一跳節(jié)點(diǎn)是節(jié)點(diǎn)6，用符號表示為bestn（7，10）=6。而在圖2中，節(jié)點(diǎn)7的父親節(jié)點(diǎn)是節(jié)點(diǎn)8，從圖中可以看出，節(jié)點(diǎn)8與7不屬于同一子樹，7∈subtree（7，TE10） & 8subtree（7，TE10），節(jié)點(diǎn)7就是定義6中定義的優(yōu)先節(jié)點(diǎn)，其最佳備份下一跳節(jié)點(diǎn)為節(jié)點(diǎn)7中依附于其他分支的父親節(jié)點(diǎn)8，即backn（7，10）=parent（7）=8。下面為處理某一分支的詳細(xì)步驟。

a）從原始拓?fù)渲袠?gòu)造以節(jié)點(diǎn)10為目的節(jié)點(diǎn)的最短路徑樹TE10（V，E10），如圖3所示。

b）假設(shè)此分支中節(jié)點(diǎn)9與根節(jié)點(diǎn)10相連的鏈路發(fā)生故障，即f（9，10）。重構(gòu)最短路徑樹TE10（V，E10），由于重構(gòu)后，最短路徑樹中節(jié)點(diǎn)7存在依附關(guān)系，所以節(jié)點(diǎn)7是優(yōu)先節(jié)點(diǎn)（prioritynode），故可以將最短路徑樹劃分為subtree（10，TE10）和subtree（7，TE10），如圖2所示。

c）遍歷subtree（7，TE10）分支，并將優(yōu)先節(jié)點(diǎn)在重構(gòu)后的父親節(jié)點(diǎn)8，作為優(yōu)先節(jié)點(diǎn)的最佳備份下一跳?？梢员硎緸?/p>

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

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

d）深度遍歷優(yōu)先節(jié)點(diǎn)7的孩子節(jié)點(diǎn)child（7）={6，4}，如果該孩子節(jié)點(diǎn)發(fā)生了父子節(jié)點(diǎn)關(guān)系互換，則重構(gòu)后的父親節(jié)點(diǎn)作為該節(jié)點(diǎn)的最佳備份下一跳，例如節(jié)點(diǎn)6在分支中的父親節(jié)點(diǎn)是節(jié)點(diǎn)7，但在原最短路徑樹中，節(jié)點(diǎn)7是節(jié)點(diǎn)6的孩子節(jié)點(diǎn)，則將節(jié)點(diǎn)7作為節(jié)點(diǎn)6的最佳備份下一跳節(jié)點(diǎn)。然后繼續(xù)深度遍歷，出現(xiàn)以下兩種情況后停止遍歷。

（a）遍歷到空節(jié)點(diǎn)，即child（9，subtree（7，TE10））=。

（b）遍歷到的節(jié)點(diǎn)不符合父子節(jié)點(diǎn)關(guān)系互換條件，即表示為

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

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

例如在圖2中，節(jié)點(diǎn)7的孩子節(jié)點(diǎn)4，節(jié)點(diǎn)4的父親節(jié)點(diǎn)在subtree（7，TE10）分支中是節(jié)點(diǎn)7，同時(shí)在重構(gòu)SPT之前，節(jié)點(diǎn)4的父親節(jié)點(diǎn)在TE10（V，E10）中仍然是節(jié)點(diǎn)7，沒有發(fā)生父子節(jié)點(diǎn)關(guān)系互換，故停止遍歷。

e）在深度遍歷過程中，若出現(xiàn)節(jié)點(diǎn)v∈subtree（7，TE10）符合步驟d）中的停止遍歷條件（b），則刪除鏈路（v，parent（v，subtree（7，TE10））），繼續(xù)執(zhí)行步驟b）～d）。

3 SLFRPRSPT算法

SLFRPRSPT算法主要分為以下兩個(gè)算法，其中算法1描述了逐個(gè)處理原最短路徑樹中各個(gè)分支的節(jié)點(diǎn){d1，d2，d3，…}∈child（d，TEd），每個(gè)分支生成的子樹為subtree（b1，TEd），subtree（b2，TEd），…。假設(shè)發(fā)生f（d1，d），對于處理節(jié)點(diǎn)d1分支的主要思想是，重構(gòu)最短路徑樹TEd，得到其生成子樹subtree（b1，TEd），然后比對新舊最短路由樹。算法2具體描述了刪除某條鏈路之后，如何通過比對新舊最短路由樹，來為該分支上的節(jié)點(diǎn)找到最佳備份下一跳。其主要思想為，通過比對新舊最短路由樹，找出依附在別的分支上的節(jié)點(diǎn)，并存儲其最佳備份下一跳。

算法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è)有向帶權(quán)圖G（V，E，weight），一個(gè)目的節(jié)點(diǎn)d，一個(gè)最短路徑樹TEd，算法的輸出是節(jié)點(diǎn)集合V中每個(gè)節(jié)點(diǎn)v到目的節(jié)點(diǎn)d的最佳備份下一跳節(jié)點(diǎn)。偽代碼中的第1行表示對圖中的每個(gè)節(jié)點(diǎn)v，執(zhí)行以下操作。第2行是將backn（v，d）賦值為空集合，表示節(jié)點(diǎn)v到d的最佳備份下一跳集合為空。第4行表示在最短路徑樹TEd中，遍歷重構(gòu)SPT中的每個(gè)分支子樹的根節(jié)點(diǎn)di，并執(zhí)行以下操作。算法第5行調(diào)用sptcompare（G，d，di）函數(shù)，該函數(shù)會刪除邊（d，di），并重新計(jì)算最短路徑樹，然后比對新舊最短路徑樹，為節(jié)點(diǎn)找到其最佳備份下一跳。

算法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的主要目的是刪除鏈路，為圖中的節(jié)點(diǎn)找到最佳備份下一跳，以保證在發(fā)生故障時(shí)仍然能夠到達(dá)目的節(jié)點(diǎn)。之后重構(gòu)最短路徑樹，并對新舊最短路徑樹進(jìn)行比對，找出哪些節(jié)點(diǎn)的父子節(jié)點(diǎn)關(guān)系發(fā)生了變化，為它們找到最佳備份下一跳節(jié)點(diǎn)。

算法中的第1行在最短路徑子樹subtree（u，TEd）中對每個(gè)節(jié)點(diǎn)n執(zhí)行以下操作。第2行，如果在最短路徑子樹subtree（u，TEd）中，節(jié)點(diǎn)n的父親節(jié)點(diǎn)不屬于以節(jié)點(diǎn)u為根節(jié)點(diǎn)的子樹subtree（u，TEd）中，則執(zhí)行以下操作。第3行將節(jié)點(diǎn)n在TEd中的父親節(jié)點(diǎn)添加到backn（u，d）中，表示它是節(jié)點(diǎn)u到d的最佳備份下一跳節(jié)點(diǎn)。第4行將子樹subtree（u，TEd）中節(jié)點(diǎn)u的孩子節(jié)點(diǎn)賦值給節(jié)點(diǎn)x。第5行表示如果節(jié)點(diǎn)x的父親節(jié)點(diǎn)u不屬于子樹subtree（u，TEd），則在第6行中，將節(jié)點(diǎn)x的父親節(jié)點(diǎn)parent（x）加入到節(jié)點(diǎn)x到d的最佳備份下一跳集合backn（x，d）中。否則，第7行中將節(jié)點(diǎn)x傳入sptcompare（G，d，x）函數(shù)進(jìn)行遞歸遍歷，遞歸查找節(jié)點(diǎn)x的最佳備份下一跳。這個(gè)算法是遞歸的，也就是說，它會不斷地刪除邊，重新計(jì)算最短路徑樹SPT，比對新舊最短路徑樹，直到找到所有節(jié)點(diǎn)的最佳備份下一跳為止。以下是算法的時(shí)間復(fù)雜度分析。

定理2 SLFRPRSPT算法的時(shí)間復(fù)雜度為

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

證明 SLFRPRSPT算法分為handlebranch（G，d）算法和sptcompare（G，d，u）算法兩部分。在式（11）中，O（|V|）表示循環(huán)遍歷節(jié)點(diǎn)集合V的時(shí)間復(fù)雜度。加號后面第一項(xiàng)（|V|-1）表示在handlebranch（G，d）算法中遍歷除目的節(jié)點(diǎn)以外的節(jié)點(diǎn)所需要的時(shí)間復(fù)雜度，同時(shí)調(diào)用sptcompare（G，d，u）算法，其時(shí)間復(fù)雜度為log |E|。在sptcompare（G，d，u）算法中，首先會對子樹中的節(jié)點(diǎn)進(jìn)行循環(huán)，所以其時(shí)間復(fù)雜度為log |V|。在算法中，會進(jìn)行遞歸條件判斷，若滿足遞歸條件，則繼續(xù)進(jìn)行遞歸，所以需要log |E|的時(shí)間復(fù)雜度。因此，算法的時(shí)間復(fù)雜度可以表示為O（|V|）+O（（|V|-1）（log |V|×log |E|））。

4 實(shí)驗(yàn)結(jié)果及分析

本章將在真實(shí)拓?fù)渖线M(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)環(huán)境采用酷睿i7系列處理器，16 GB內(nèi)存，為了能更好說明算法的保護(hù)效果，本文利用故障保護(hù)率和路徑拉伸度這兩個(gè)指標(biāo)對實(shí)驗(yàn)結(jié)果進(jìn)行分析。

LFC和DC算法是目前比較受歡迎的路由保護(hù)方案［17，18］，下面對它們進(jìn)行詳細(xì)介紹。DC（downstream condition）算法主要對節(jié)點(diǎn)的鄰居節(jié)點(diǎn)進(jìn)行遍歷，從而尋找其下一跳節(jié)點(diǎn)。假設(shè)計(jì)算節(jié)點(diǎn)為a，目的節(jié)點(diǎn)為d，b是節(jié)點(diǎn)a的鄰居節(jié)點(diǎn)，則它們之間應(yīng)滿足規(guī)則dist（b，d）

通過對比SLFRPRSPT、DC和LFC算法在不同拓?fù)湎鹿收媳Ｗo(hù)率和路徑拉伸度的表現(xiàn)情況，分析得到可以獲得最佳路由保護(hù)效果的算法。下面將從實(shí)驗(yàn)拓?fù)洹⒐收媳Ｗo(hù)率、路徑拉伸度三個(gè)方面來介紹本次實(shí)驗(yàn)。

4.1 實(shí)驗(yàn)拓?fù)?/p>

選取合適的實(shí)驗(yàn)拓?fù)涫潜疚膶?shí)驗(yàn)的關(guān)鍵。為了使實(shí)驗(yàn)可以更加全面、客觀地評價(jià)不同算法的表現(xiàn)結(jié)果，本文采用真實(shí)環(huán)境下的網(wǎng)絡(luò)拓?fù)溥M(jìn)行實(shí)驗(yàn)。其中，真實(shí)拓?fù)涫侵笇?shí)際存在的網(wǎng)絡(luò)拓?fù)?，用于?yàn)證和評估路由保護(hù)方案的適用性和實(shí)際效果，如表2所示，例如從互聯(lián)網(wǎng)中得到的Abilene拓?fù)洌?9］，它是美國某教育網(wǎng)的拓?fù)浣Y(jié)構(gòu)。真實(shí)拓?fù)淇梢苑从吵稣鎸?shí)網(wǎng)絡(luò)世界中的各種特性和問題，比如節(jié)點(diǎn)分布、拓?fù)浣Y(jié)構(gòu)等，從而更加真實(shí)地評估路由保護(hù)方案的可用性和實(shí)用性。實(shí)驗(yàn)拓?fù)渲械穆酚善鲾?shù)量在11～88，鏈路數(shù)量在14～92，本次實(shí)驗(yàn)的拓?fù)浣Y(jié)構(gòu)如表2所示。

4.2 故障保護(hù)率

在本文實(shí)驗(yàn)的不同算法中，它們都為每個(gè)節(jié)點(diǎn)計(jì)算盡可能多地最佳備份下一跳節(jié)點(diǎn)。在拓?fù)鋱DG=（V，E）中，對于v∈V，如果節(jié)點(diǎn)v存在最佳備份下一跳節(jié)點(diǎn)，即backn（v，d）≠，那么就稱這個(gè)節(jié)點(diǎn)v是被保護(hù)的節(jié)點(diǎn)，假設(shè)節(jié)點(diǎn)v為源節(jié)點(diǎn)，目的節(jié)點(diǎn)為d，則v-d稱為被保護(hù)的源-目的節(jié)點(diǎn)對。

故障保護(hù)率是用來衡量一個(gè)算法保護(hù)效果的重要指標(biāo)，它有如下定義：在拓?fù)鋱D中，故障保護(hù)率是指拓?fù)鋱D中被保護(hù)的源-目的節(jié)點(diǎn)對與拓?fù)鋱D中所有源-目的節(jié)點(diǎn)對的比值。本小節(jié)利用故障保護(hù)率這一指標(biāo)對比不同算法在不同拓?fù)湎碌膶?shí)驗(yàn)結(jié)果，結(jié)果如圖4所示。

圖4（a）（b）展示了三種算法對不同拓?fù)溥M(jìn)行故障保護(hù)率的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)結(jié)果表明，本文基于重構(gòu)SPT的單鏈路故障路由保護(hù)算法SLFRPRSPT在所有拓?fù)渲械墓收媳Ｗo(hù)率均為1，明顯優(yōu)于另外兩種算法的實(shí)驗(yàn)結(jié)果，SLFRPRSPT算法具有最佳保護(hù)效果，可以有效保護(hù)單鏈路故障路由，避免網(wǎng)絡(luò)受到故障的影響。在V2008實(shí)驗(yàn)拓?fù)渲?，三種算法的故障保護(hù)率差距最為明顯，最優(yōu)的是SLFRPRSPT算法，故障保護(hù)率結(jié)果為1，其次是LFC算法，實(shí)驗(yàn)結(jié)果為0.068 97，效果最差的是DC算法，結(jié)果為0.045 45。另外，在NJLATA拓?fù)渲?，SLFRPRSPT和LFC算法的故障保護(hù)率都達(dá)到了1，但DC算法的故障保護(hù)率只有0.809 09，保護(hù)效果最低。實(shí)驗(yàn)結(jié)果的原因有：

a）SLFRPRSPT算法的設(shè)計(jì)目的在于為拓?fù)渲械乃泄?jié)點(diǎn)計(jì)算最佳備份下一跳，因此其可以百分之百保護(hù)拓?fù)渲械墓?jié)點(diǎn)。

b）SLFRPRSPT算法采取遞歸遍歷的思想，如果有節(jié)點(diǎn)無法計(jì)算出最佳備份下一跳，則斷開與節(jié)點(diǎn)相連鏈路，進(jìn)行重構(gòu)SPT計(jì)算，因此其故障保護(hù)率高。

c）LFC和DC算法僅通過考慮鏈路權(quán)重大小進(jìn)行計(jì)算，沒有充分考慮節(jié)點(diǎn)與節(jié)點(diǎn)之間的聯(lián)系，而SLFRPRSPT算法通過尋找存在依附關(guān)系的節(jié)點(diǎn)，進(jìn)行重構(gòu)SPT，可以有效利用節(jié)點(diǎn)，尋找節(jié)點(diǎn)的最佳備份下一跳節(jié)點(diǎn)。

4.3 路徑拉伸度

本小節(jié)用路徑拉伸度來衡量算法計(jì)算出來的重路由路徑的優(yōu)劣。當(dāng)鏈路發(fā)生故障時(shí)，路徑拉伸度表示為算法計(jì)算出來的新重路由路徑與用最短路徑算法計(jì)算出來的原路由路徑的比值。通過定義可知，路徑拉伸度越小，算法計(jì)算出來的重路由路徑與原路由路徑越相近，不會給網(wǎng)絡(luò)帶來較多的額外開銷和延遲，說明算法的效果越好。相反，如果路徑拉伸度越大，說明算法計(jì)算出來的重路由路徑與原路由路徑差距越大，從而給網(wǎng)絡(luò)帶來額外的開銷，算法的效果也越差。圖5是不同算法在路徑拉伸度指標(biāo)下的實(shí)驗(yàn)結(jié)果。

如圖5（a）（b）所示，通過對三種算法在路徑拉伸度指標(biāo)下的實(shí)驗(yàn)結(jié)果可知，本文SLFRPRSPT算法在三種算法的比較中，其路徑拉伸度最高，其次是LFC算法，路徑拉伸度最低的是DC算法，這是因?yàn)镈C算法的故障保護(hù)率最低，被保護(hù)的節(jié)點(diǎn)較少，因此，其計(jì)算出來的重路由路徑簡單，路徑拉伸度最低。而本文SLFRPRSPT算法保護(hù)拓?fù)渲械乃泄?jié)點(diǎn)，計(jì)算路徑多于其他兩種算法，因此其路徑拉伸度稍高。對比算法性能時(shí)，首先比較故障保護(hù)率，故障保護(hù)率高的算法性能最優(yōu)。但在故障保護(hù)率相同的情況下，對比其路徑拉伸度，比如在NJLATA拓?fù)渲?，SLFRPRSPT和LFC算法的故障保護(hù)率均是1，但SLFRPRSPT算法的路徑拉伸度為1.007 69，LFC算法的路徑拉伸度為1.034 82，SLFRPRSPT算法具有較小的路徑拉伸度，其性能最佳，可以有效節(jié)約網(wǎng)絡(luò)資源，減少網(wǎng)絡(luò)開銷。

5 結(jié)束語

由于網(wǎng)絡(luò)中單鏈路故障的頻繁發(fā)生，本文在此背景下研究了一種基于重構(gòu)SPT的單鏈路故障路由保護(hù)方法，針對單鏈路故障路由保護(hù)問題，該方法能夠快速檢測鏈路故障并進(jìn)行故障切換，從而保障計(jì)算機(jī)網(wǎng)絡(luò)的高可用性和穩(wěn)定性。實(shí)驗(yàn)結(jié)果表明，本文SLFRPRSPT算法比其他方法具有更高的故障保護(hù)率，在故障保護(hù)率相同的前提下，具有更低的路徑拉伸度，同時(shí)還能夠保證數(shù)據(jù)的傳輸質(zhì)量，加快路由收斂速度。該方法具有廣泛的應(yīng)用前景，例如在某公司的數(shù)據(jù)中心內(nèi)部有多個(gè)服務(wù)器和交換機(jī)，服務(wù)器之間通過交換機(jī)連接，它們共同組成了一個(gè)類似于有向圖的拓?fù)浣Y(jié)構(gòu)。若采用基于重構(gòu)SPT的單鏈路故障路由保護(hù)方法，當(dāng)發(fā)生網(wǎng)絡(luò)故障時(shí)，網(wǎng)絡(luò)中的節(jié)點(diǎn)可以選擇最佳備份下一跳作為主選項(xiàng)，繞開故障鏈路，以此來進(jìn)行數(shù)據(jù)的正常傳輸，從而確保網(wǎng)絡(luò)的正常運(yùn)行。

未來的研究可以從以下兩個(gè)方面進(jìn)行展開：a）結(jié)合多鏈路保護(hù)技術(shù)，進(jìn)一步提高網(wǎng)絡(luò)的可靠性和容錯(cuò)能力；b）通過優(yōu)化路由保護(hù)方案，進(jìn)一步降低算法的路徑拉伸度。

參考文獻(xiàn)：

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

［2］葉朝陽，沈辰，黃明慶，等.互聯(lián)網(wǎng) BGP 路由可視及安全檢測技術(shù)架構(gòu)與實(shí)踐［J］.電信科學(xué)，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，F(xiàn)raire 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］耿海軍，施新剛，王之梁，等.基于最小路徑交叉度的域內(nèi)路由保護(hù)方案［J］.軟件學(xué)報(bào)，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.