基于節點偏序關系的路由可用性框架研究

作者簡介：胡睿乾（1999－），男，山西臨汾人，碩士研究生，主要研究方向為路由算法；耿海軍（1983－），男（通信作者），山西晉中人，副教授，碩導，博士，主要研究方向為軟件定義網絡、路由算法和網絡體系結構（ghj123025449@163.com）；宋艷濤（1989－），女，山西臨汾人，副教授，碩導，博士，主要研究方向為圖像處理、醫學影像分析．

摘 要：為了維護路由可用性，需要采取一定的路由保護策略來防止網絡故障可能對網絡造成的影響。因此，提出了一種基于節點偏序關系的路由可用性框架，該框架首先利用節點之間的偏序關系構造有向無環圖，然后根據構造的有向無環圖為每個節點計算備份下一跳節點。在此框架基礎上，根據節點之間的偏序關系提出了四種路由保護方法。實驗結果表明，四種路由保護算法都擁有較高的故障保護率，能有效降低故障造成的網絡中斷，在真實拓撲中故障保護率可以到達89.76%，在模擬拓撲中故障保護率達到98.995%，幾乎接近100%。

關鍵詞：路由可用性；網絡延遲；故障保護率；備份節點；路由保護

中圖分類號：TP309.7 文獻標志碼：A

文章編號：1001－3695（2023）04－032－1160－05

doi：10.19734/j.issn.1001-3695.2022.08.0431

Abstract：In order to maintain routing availability，it need to adopt certain routing protection strategies to prevent the possible impact of network failures on the network.Therefore，this paper proposed a routing availability framework based on node bias order relationship，which first constructed a directed acyclic graph using the bias order relationship between nodes，and then calculated the backup next-hop node for each node based on the constructed directed acyclic graph.Based on this framework，this paper proposed four routing protection methods based on the biased order relationship between nodes.The experimental results show that all four routing protection algorithms have high fault protection rate and effectively reduce the network disruption caused by faults，which can reach 89.76% in the real topology and 98.995% in the simulated topology，almost close to 100%.

Key words：routing availability；network latency；fail-safe rate；backup node；route protection

0 引言

隨著互聯網的蓬勃發展，人們將關注點從使用的手機逐步轉變到追求上網的體驗。傳統的網絡應用大部分是非實時應用，它們對網絡的要求并不高，而現在的網絡應用大部分是實時應用，例如在線游戲、在線視頻、網絡直播等。如果網絡中出現了故障，則會導致網絡暫時性的中斷，影響用戶的上網體驗，因此，實時性應用對網絡的要求很高，需要網絡提供高可靠性的保證。路由保護是指保護網絡中的路由，讓它們盡量避免受到故障的影響。為了保護路由，網絡中存在各種各樣的路由協議，主要分為兩大類：a）內部網關協議（IGP），如RIP—路由信息協議，屬于早期的動態路由協議，它的優點是成本低、配置簡單，缺點是可能會導致路由環路等；b）外部網關協議（BGP），運行在不同自治系統之間，優點是可以實現不同自治系統之間的通信，缺點是成本高、配置復雜等。盡管網絡中存在這些路由協議，但也不可避免地會發生一些嚴重的網絡事故，影響人們的上網體驗，干擾社會的正常生活秩序，甚至造成嚴重的經濟損失。另外，網絡層的故障恢復能力包括在控制平面上和在數據平面上，然而這些路由協議大部分工作在網絡中的控制平面上，控制平面機制在應對故障時反應緩慢[1]，故將研究重點放到了數據平面的恢復上。路由協議在發生故障時的收斂時間較長，一般在幾秒到幾十秒，而這樣的時間對現實的網絡需求而言往往是漫長的，面對實時應用的迅速發展，網絡中可以容忍的時間在毫秒級甚至是微秒級乃至更短，收斂時間長可能會導致互聯網中數據包的交付延遲，路由協議不能及時作出反應，會導致傳輸的數據包丟失[2]，故障修復后又可能造成網絡擁塞，對網絡的正常運行產生較大影響。

國內外的研究人員提出利用路由保護策略解決路由故障的問題，主要包括基于逐條轉發和基于非逐條轉發[3]。無環備選項（loop free alternates，LFA）是廣受歡迎的逐條轉發路由保護策略，其是用一定的策略讓流量通過備份路徑轉發到目的地，無須改變現有的路由協議[4]，但有兩個缺點：a）一些流量無法在節點或鏈路中得到保護；b）在節點故障或多故障發生時可能會導致循環，且計算開銷比較大[5，6]。Not-Via是經典的基于非逐條轉發策略[7]，但其計算復雜度較高，難以實際部署。多協議標簽交換方案MPLS [8]可以優化網絡資源，但缺乏安全性和靈活性。國內外學者還對軟件定義網絡（software-defined network，SDN）中可能發生的故障設計了一些解決方案，例如通過將中斷的流量從故障鏈路重新路由到備用路徑上，從而減輕鏈路故障帶來的影響，但缺點是恢復時間尚不確定，且網絡資源利用率不高[9]。

另外，快速重路由（fast reroute，FRR）機制在IP和MPLS網絡中被廣泛使用，在故障發生前提前計算恢復路徑，相比傳統方法更容易部署和擴展，也有著更高的效率和性能[10～12]。從這個角度出發，解決路由可用性的思路放在了如何提前為網絡中的節點計算大于等于兩個備份節點的上面。

現有的路由保護方案雖然可以在一定程度上避免路由故障帶來的網絡中斷，但在數據恢復過程中，數據包的轉發往往可能會產生環路，這就大大降低了路由的可用性，況且其實現煩瑣、效率低下且成本高昂。為了解決這些問題，需要設計一種方案來避免數據包的轉發循環且便于部署，而基于節點偏序關系的保護方案可以完美實現以上目的，通過定義節點之間的偏序關系，優化數據包的轉發策略，不僅可以規避網絡中可能出現的路由環路，而且其實現簡單，具有良好的應用前景。

針對以上分析和研究，本文提出基于節點偏序關系的路由可用性框架，重點放在如何提高路由的可用性，進而減少網絡故障所帶來的影響。本文算法側重于提前為網絡拓撲中的每個節點計算盡可能多的備份下一跳節點，通過設計不同的方案來尋求最佳的算法性能，與傳統方法相比，路由收斂時間短，故障保護率較高，進而優化網絡資源，促進網絡中的負載均衡[13]，減少故障發生時的保護切換時間，實現業務的快速恢復[14]。

Ohara等人[15]提出了最大可替代路由算法，受此啟發，本文提出了基于節點偏序關系的路由可用性框架，在路由保護方面作出的創新點和貢獻如下：

a）與其他路由保護方案相比，本文的創新點在于提出了基于節點偏序的路由保護框架，利用偏序關系可以更好地處理排序問題這一思想，可以有效避免數據包在轉發過程中可能出現的路由環路，通過設計不同的節點選擇規則來實現節點偏序關系，更有利于在實際中的部署和實施。

b）將路由保護方案與求最短路徑的Dijkstra算法相結合，使得本文算法在選擇加入的節點時必須在之前通過Dijkstra算法計算出來的最短路徑集合的節點中進行選擇，這樣保證了選擇節點的高效，節約運行成本。

c）在真實拓撲和模擬拓撲上進行了實驗，驗證該路由保護框架具有較高的故障保護率和平均備份節點數，且該算法較靈活，擴展性強。

DC算法[4]是目前比較受歡迎的一種路由保護規則，它的核心是滿足cost（x，d）lt;cost（s，d）的節點x將作為節點s的備份下一跳節點，其中cost（s，d）是指從起始節點s到目的節點d的最短路徑上的權重和，核心式子中的x是起始節點s的鄰居節點。為了進一步說明本文提出的基于節點偏序關系的路由可用性保護方案取得的良好效果，實驗部分將本文算法與DC算法進行比較，通過兩個重要的評價指標來說明本文算法的優勢。

1 網絡模型和問題描述

表1是本文用到的一些符號描述。

在該LP模型中，式（6）是要解決的目標函數，式（7）～（12）是約束條件。其中，式（7）說明本文方案針對的是有向無環圖；式（8）對應上述條件式（1），（）是截取方法，里面參數是以v節點為目的節點構造的最短路徑樹，里層的∑是對單個節點到目的節點的最短路徑樹進行截取，外層∑是累加所有節點到目的節點的最短路徑樹線段；式（9）和（10）是約束節點偏序關系，式（9）說明集合S非空并且里面的節點都滿足小于的偏序關系，式（10）是對節點偏序關系做進一步的解釋；式（11）和（12）是在約束只有滿足條件式（1）（2）的節點才可以加入到最后的輸出序列中。

2 基于節點偏序關系的路由可用性框架

本文框架的大致思路是：首先計算拓撲中以某一點為根的最短路徑樹；然后通過循環遍歷與輸出集合相連的且在其最短路徑樹上的節點，選擇滿足算法篩查規則的節點；最后將其加入到輸出集合中，并按節點加入集合的順序進行編號。

2.1 算法思想

為了達到路由保護的目的，一個直觀的想法是提前給每個節點計算它到目的節點的最短路徑，然后給每個節點以它的最短路徑樹為基礎再尋找其他的下一跳節點，但這會帶來很多問題：a）計算策略需要重新規劃，而且不能保證路徑可以達到目的節點；b）可能產生路由環路，造成網絡擁塞和資源的浪費；c）計算開銷大，算法具有很大的不確定性。

因此實現上章LP模型的關鍵在于要滿足給定的約束條件，它們貫穿在本文算法中，算法的總體思想包括以下幾個步驟：

a）確定初始節點v0并對后續可能用到的集合做初始化工作，根據最短路徑樹截取成最短路徑線段的集合。

b）開始時S={v0}≠，判斷其余節點與v0節點構成的線段是否在步驟a）計算出來的最短路徑線段集合中，將其加入到備選節點集合中。

c）在備選節點集合中選擇滿足算法篩查規則的節點，將最優的節點加入到輸出序列S中，同時用另一個集合記錄節點的下一跳節點。

d）在輸出節點中確定節點的偏序關系并編號，同時判斷節點的下一跳節點是否滿足節點偏序關系，最后輸出算法結果。

通過上述四個步驟可以大致知道算法的運行流程，輸出數據包的轉發序列，下面詳細說明步驟中的兩個重要問題。

問題1 如何確定算法篩查規則。算法篩查規則是選擇輸出節點的關鍵，由篩查規則選出滿足算法要求的最優節點。本文首先設計了一個算法框架，并由此擴展了四種方法用來比較哪個能得到最優的篩查結果。以第一種方案為例，如圖2所示的拓撲圖，創建空列表S，d為目的節點，將d加入S集合中。在選擇之后加入的節點時，要保證：a）是集合S的鄰接節點；b）滿足最短路徑線段的節點；c）與S集合相連邊數最多的節點。

下面分別在真實拓撲和模擬拓撲中比較每個算法在每個拓撲中的平均備份節點數的情況，圖3是在真實拓撲下的比較情況。

通過上述五個算法在真實拓撲中的實驗結果可以看出，前四種算法的實驗結果都要比DC算法性能要好，且它們主要分為以下五類：

a）前四種算法的平均備份節點數一樣。圖3（a）中的Atmnet、Belnet2004，圖3（b）中的NJLATA這三個拓撲中，這四個算法的平均備份節點數是一樣的。

b）在Sunet拓撲中，RPP-MTMIN和RPP-MTHMAX算法略微比RPP-MAX和RPP-MTMAX的6.791 67好，為6.875，而DC算法的結果只有5.458。

c）算法比較結果為RPP-MTMAX=RPP-MAXgt;RPP-MTMINgt;RPP-MTHMAXgt;DC。在AttMpls和TataNld拓撲中，RPP-MTMAX和RPP-MAX算法是一樣的，分別是21.8和41.727 94，RPP-MTMIN次之，然后是RPP-MTHMAX，最后是DC算法。

d）算法比較結果為RPP-MTMAX=RPP-MAXgt;RPP-MTHMAXgt;RPP-MTMINgt;DC。這種情況全部在圖3（b）中的SwitchL3、USLD和TORONTO拓撲。

e）除了上述四種情況外，剩下的拓撲均為RPP-MTMAX和RPP-MAX算法性能一樣，都優于RPP-MTHMAX和RPP-MTMIN的性能，且后兩者性能也一樣，它們四種算法同樣都優于第五種DC算法，即RPP-MTMAX=RPP-MAXgt;RPP-MTHMAX=RPP-MTMINgt;DC。圖4是度為4的模擬拓撲中的比較結果，橫坐標代表拓撲中的節點數量，總共有五個拓撲，節點數量分別為20、40、60、80和100。由實驗結果可以看出，隨著節點數量的增加，五種算法的平均備份節點數都呈現線性增加。實驗結果表明，節點為20時，前四種算法求得的平均備份節點數一致，都為18，而DC算法的平均備份節點數只有16.85。在拓撲節點數分別為40、60、80時，五種算法性能為RPP-MTMAX=RPP-MAXgt;RPP-MTHMAX=RPP-MTMINgt;DC，當拓撲節點為100時，RPP-MTHMAX算出的平均備份節點數為94.24，略好于RPP-MTMIN的94.2，RPP-MTMAX和RPP-MAX是最優的，為96.87，而DC算法的結果只有83.31。

隨著拓撲節點的逐漸遞增，RPP-MTMAX和RPP-MAX與RPP-MTHMAX和RPP-MTMIN的差距逐漸拉開（圖4），因此考慮拓撲更大的情況（圖5）。

圖5結果表明，在節點數量為200，度為2的拓撲中，這兩類算法的差距是最大的，其中RPP-MTHMAX計算出來的平均備份節點數為128.3，略強于RPP-MTMIN的127.815。度為2和4的拓撲在RPP-MAX和RPP-MTMAX中的比較結果均是RPP-MTMAXgt;RPP-MAX。由圖5還可以看出，當拓撲大小不變時，隨著度數的增加，RPP-MTMAX和RPP-MAX與RPP-MTHMAX和RPP-MTMIN的差距在很快減小，當拓撲度為12時，它們之間的差距只有0.17，DC算法結果最低，為194.075。由圖4、5還可看出，雖然隨著拓撲節點數量和節點度的增加，DC算法所得到的平均備份節點數也在不斷增加，但上述四種算法均優于DC算法。

3.2.2 故障保護率

當故障發生時，如果路由器擁有大于或等于兩個下一跳路由器，這樣就稱這個路由器是被保護的。故障保護率指的是在一個拓撲中，被保護的節點數量與總節點數量之比。利用之前的真實拓撲與模擬拓撲繼續做實驗，比較每個算法的實驗結果如圖6所示。

圖6（a）（b）是在真實拓撲下的實驗結果，圖6（c）（d）是在模擬拓撲實驗下的結果。兩者結果都表明，這五個算法中，前四者的運行結果均優于DC算法，且前四個算法大致可以分為兩類，其中RPP-MTMAX和RPP-MAX性能接近，均優于第二類算法。第二類算法為RPP-MTHMAX和RPP-MTMIN，它們的性能不如第一類算法，且它們的性能表現在某些拓撲上會略微有所不同。在圖6（c）中，兩類算法隨著拓撲節點數量的增多，計算出來的故障保護率差異也越來越大，而DC算法的結果都不如這兩類算法，且性能沒有本文算法穩定可靠。

4 結束語

本文提出了基于節點偏序關系的路由可用性框架，通過與DC算法的對比可以看出，該框架可以有效保護網絡中的節點免受故障影響，從而提高路由可用性。實驗部分比較了平均備份節點數和故障保護率兩個指標，四種算法均優于DC算法，且它們大致可以分為兩類，第一類是RPP-MTMAX和RPP-MAX算法，它們的性能都強于第二類的RPP-MTHMAX和RPP-MTMIN算法。對于模擬拓撲在度為4時，隨著拓撲節點增加到100，這兩類算法差距越來越大。本文RPP-MTMAX和RPP-MAX算法對于中小型企業網絡而言是比較適合的，對于大型網絡而言四種算法都具有不錯的性能。綜合來看，本文算法通過給節點編號，避免了網絡中數據包轉發可能出現環路的情況，通過算法策略，在盡可能節約網絡開銷的情況下，提高節點應對故障的能力。下一步研究的重點將放在本文算法時間復雜度的優化上，另外，如何提高節點在發生故障時的應變能力，這對于本文算法的改進將產生重要影響。

參考文獻：

［1］Chiesa M，Kamisiński A，Rak J，et al.A survey of fast-recovery mechanisms in packet-switched networks[J].IEEE Communications Surveys amp; Tutorials，2021，23（2）：1253-1301.

[2]Li Qi，Xu Mingwei，Wu Jianping，et al.A unified approach to routing protection in IP networks[J].IEEE Trans on Network and Service Management，2012，9（3）：306-319.

[3]耿海軍，張爽，尹霞.互聯網域內路由可用性綜述[J].計算機科學，2019，46（7）：1-6.（Geng Haijun，Zhang Shuang，Yin Xia.An overview of routing availability in the Internet domain[J].Computer Science，2019，46（7）：1-6.）

[4]Hartmann M，Hock D，Menth M.Routing optimization for IP networks with loop-free alternates[J].Computer Networks，2016，95：35-50.

[5]Braun W，Menth M.Loop-free alternates with loop detection for fast reroute in software-defined carrier and data center networks[J].Journal of Network and Systems Management，2016，24（3）：470-490.

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

[7]Papán J，Segecˇ 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.

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

[9]Wang Shishuang，Xu Hongli，Huang Liusheng，et al.Fast recovery for single link failure with segment routing in SDNs[C]//Proc of the 21st International Conference on High Performance Computing and Communications；the 17th International Conference on Smart City；the 5th International Conference on Data Science and Systems.Piscataway，NJ：IEEE Press，2019：2013－2018.

[10]Qiu Kun，Zhao Jin，Wang Xin，et al.Efficient recovery path computation for fast reroute in large-scale software-defined networks[J].IEEE Journal on Selected Areas in Communications，2019，37（8）：1755-1768.

[11]Lemeshko O，Yeremenko O，Sleiman B，et al.Fast reroute model with realization of path and bandwidth protection scheme in SDN[J].Advances in Electrical and Electronic Engineering，2020，18（1）：23-30.

[12]Papan J，Segec P，Paluch P，et al.The new multicast repair（M-REP） IP fast reroute mechanism[J].Concurrency and Computation：Practice and Experience，2020，32（13）：e5105.

[13]Shvedov A V，Gadasin D V，Alyoshintsev A V.Segment routing in data transmission networks[J].T-Comm，2022，16（5）：56－62.

[14]Sun Qiang，Xiong Zhuangzhuang，Zhou Yang.Routing algorithm based on fast service recovery[C]//Proc of Asia Communications and Photonics Conference.Piscataway，NJ：IEEE Press，2019：1－3.

[15]Ohara Y，Imahori S，Van Meter R.MARA：maximum alternative routing algorithm[C]//Proc of IEEE INFOCOM.Piscataway，NJ：IEEE Press，2009：298－306.

[16]Wang Xiaozhu.The comparison of three algorithms in shortest path issue[J].Journal of Physics Conference Series，2018，1087（2）：022011.

[17]Al-Qudah Z，Jomhawy I，Alsarayreh M，et al.On the stability and diversity of Internet routes in the MPLS era[J].Performance Evaluation，2020，138：102084.

[18]Bento L M S，Boccardo D R，Machado R C S，et al.Dijkstra graphs[J].Discrete Applied Mathematics，2019，261：52－62.