一種基于轉發圖的域內路由保護算法

耿海軍 孟 卓 姚姍姍 楊 靜 池浩田 尹 霞

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 的核心思想應用到域間路由保護算法中，從而進一步提高網絡的可用性.

作者貢獻聲明：耿海軍提出了算法思路和實驗方案，并撰寫論文；孟卓負責執行實驗方案；姚珊珊參與實驗方案指導和對部分實驗結果分析；楊靜參與論文校對和實驗方案指導；池浩田提出了指導意見并修改論文；尹霞提出方法的指導意見和審核論文.