一種線性時間復雜度的高效路由保護方法

摘 要：如何高效快速地應對網絡中的故障是設計路由協議的基本要求和主要任務。由于動態路由協議在應對網絡中的故障時，在協議動態收斂的過程中將會有大量的報文被丟棄。因此，目前路由器廠商普遍采用路由保護方法來克服網絡故障，在眾多的路由保護方法中，DC（downstream criterion）規則是一種被普遍認可的方法。然而，已有的實現 DC規則算法的時間復雜度普遍較高，并且復雜度隨著網絡節點平均度的增加而迅速增加。為了應對上述問題，提出一種線性時間復雜度的高效路由保護方案ERPLR（efficient routing protection method with linear time complexity），該方法首先提出了備份下一跳計算規則，然后在已有最短路徑樹的基礎上，根據備份下一跳計算規則為所有的源目的節點對計算備份下一跳。在計算備份下一跳的過程中，每個節點和其鄰居最多被訪問一次，因此ERPLR的時間復雜度為O（V+E）。實驗結果表明，與已有的實現DC規則相比較，ERPLR在故障保護率和路徑拉伸度兩個度量指標結果相似的情況下，在真實網絡拓撲和模擬拓撲中，ERPLR分別降低了大約74.93%和78.91%的計算開銷，該方法可以極大地降低DC規則的計算開銷。

關鍵詞：網絡故障；路由保護算法；DC規則；路徑拉伸度；故障保護率

文章編號：1001-3695（2023）06-031-1794-07

doi：10.19734/j.issn.1001-3695.2022.11.0521

Efficient routing protection method with linear time complexity

Geng Haijun Zhang Qidong Yin Xia

（1.a.School of Computer amp; Information Technology，b.School of Automation amp; Software Engineering，c.Institute of Big Data Science amp; Industry，Shanxi University，Taiyuan 030006，China；2.Dept.of Computer Science amp; Technology，Tsinghua University，Beijing 100048，China）

Abstract：How to deal with network faults efficiently and quickly is the basic requirement and main task of designing routing protocol.When dynamic routing protocols deal with network faults，a large number of packets are discarded during dynamic convergence.Therefore，at present，router manufacturers generally use routing protection methods to overcome network failures.Among many route protection methods，the DC（downstream criterion） rules is a generally recognized method.However，the time complexity of the existing DC rules algorithms is generally high，and the complexity increases rapidly with the increase of the average degree of network nodes.In order to deal with the above problems，this paper proposed a linear time complexity university routing protection scheme ERPLR（efficient routing protection method with linear time complexity）.The method firstly proposed the backup next hop calculation rule，and then calculated the backup next hop for all source-destination node pairs based on the existing shortest path tree according to the backup next hop calculation rule.In the process of calculating the backup next hop，accessing each node and its neighbors at most once，so the time complexity of ERPLR is O（V+E）.The experimental results show that，compared with the existing rules for implementing DC rules，ERPLR has similar results in four metrics：failure protection ratio and path stretch.Compared with DC rules，ERPLR reduces the computational overhead by about 74.93% and 78.91% in real topology and generated topology，respectively，this method can greatly reduce the calculation cost of DC rules.

Key words：network failure；routing protection algorithm；downstream criterion；path stretch；failure protection ratio

0 引言

互聯網已經成為數字化社會的一個關鍵基礎設施，越來越多的企業選擇將應用程序部署在云服務器上［1］。企業部署的應用涵蓋了健康檢測、商業交易、科學計算、電網管理和社交網絡等人們生活的方方面面。這些應用得以正常運行的前提是互聯網提供的無間斷的服務［2］。針對路由的研究主要是路由能耗［3］和路由可用性兩方面，本文主要在路由可用性方面進行研究。2017年Akamai的一項研究顯示，如果電商平臺中的響應時間延遲超過100 ms將會導致交易量大幅下降［4］；如果語音通話的時間延遲超過150 ms將會嚴重影響通話質量；如果在線游戲的時間延遲超過80 ms將會影響玩家的體驗質量［5］。隨著互聯網規模的逐步擴大，網絡故障已經成為一件不可避免的事情［6］。互聯網在設計之初就考慮使用動態路由協議來應對網絡中頻繁出現的故障。但是研究已經表明動態路由協議在修復故障的過程中面臨以下兩個方面的問題，即網絡中可能會出現路由環路和路由黑洞等問題［7，8］；并且其對應的收斂時間通常在幾秒到幾十秒，甚至幾分鐘。因此，動態路由協議無法滿足上述應用對網絡時間延遲的要求［9，10］。因此，如何高效快速地應對網絡中頻繁發生的故障是設計路由協議的基本要求和根本任務。

本文的主要貢獻包括四個方面：a）為了降低實現DC的復雜度，提出了兩個備份下一跳計算規則；b）從理論上證明了兩個備份下一跳計算規則的正確性；c）基于提出的備份下一跳計算規則，實現一種線性時間復雜度的高效路由保護方法ERPLR；d）在大量的網絡拓撲中模擬了算法ERPLR的性能，實驗結果表明，ERPLR不僅具有較小的計算開銷，并且可以提供相當于DC規則的故障保護率。

1 相關工作

目前學術界和工業界主要利用路由保護方案來應對網絡中的故障［11］，從而減少由于網絡故障造成的網絡中斷和報文丟失。路由保護方案進一步細化為逐跳轉發方式和非逐跳轉發方式［12］，非逐跳轉發方式需要一些輔助方案的配合才能正常工作，引入了較大的開銷，所以部署較為困難，不適合在實際中使用。逐跳發方式比較簡單，并不需要額外方案的協助，因此該轉發方式得到了因特網服務提供商的大力支持，從而得到了廣泛部署［13］。在逐跳轉發方式中，等價多路徑路由（equal-cost multipath routing，ECMP）是業界最早采用的一種最簡單的路由保護方案［14］，但是研究證實該方案無法提供較高的路由可用性。針對ECMP存在的問題，國際互聯網工程任務組（Internet Engineering Task Force，IETF）發布了快速重路由的框架（IP fast re-route，IPFRR），在該框架的基礎上提出了無環備選項（loop free alternates，LFA）［15］、基于Not-Via的路由保護方案［16］和基于隧道的路由保護方案［17］等。LFA重點是簡單性和可部署性，而不是對所有故障的全面覆蓋［18］。靜態快速重路由（fast re-route，FRR）機制是在已知故障之前配置條件故障轉移行為，文獻［19］提出設計了一種基于IP的快速重路由（FRR）方案，擬解決任意單鏈路/節點故障后流量重路由收斂問題。文獻［20］提出一種基于網絡分解的后處理FRR機制的算法框架，以提高快速重路由的彈性、性能和靈活性。但是如何在不同路由器上以最佳方式配置故障轉移規則存在著挑戰性。文獻［21］提出利用路由偏轉算法（deflection routing）來提高路由可用性，即首先利用無環路規則計算源節點到目的節點的所有可選下一跳，再利用標簽技術實現報文的靈活轉發。雖然該算法可以提高路由可用性，但是其實現復雜，開銷較大，難以實際部署。多配置路由［22］（multiple routing on configurations，MRC）提出為每個路由器保存多個配置圖，每個配置包括所有的節點和鏈路，通過調整鏈路權值從而使得部分節點和鏈路在該配置中得到保護，最終構造出針對所有可能出現的單故障的配置圖。當報文在轉發過程中遇到故障時，可以利用事先配置好的路由轉發該報文。文獻［23］提出了一種新的基于MRC的軟件定義網絡（SDN）快速重路由技術，大大減少了從網絡故障中恢復的時間，然而在現實網絡中，該算法需要消耗大量的計算資源和存儲開銷。多協議標簽交換（multi-protocol label switching，MPLS） 路徑保護方案［24］的原理與Not-Via方案的原理類似，它是一種隧道技術。MPLS方案可以提供快速轉發分組，縮短數據流的切換時間，雖然此方案縮短了交換時間，但適用范圍有限，只適用于支持MPLS協議的網絡。文獻［25］提出使用虛擬路由和轉發（VRF）部署多協議標簽交換（MPLS）。分組攜帶故障信息（failure carrying packet，FCP）［26］提出將報文在轉發過程中遇到的故障信息存儲在該報文的頭部，當報文到達某個節點時，該節點首先檢測該報文頭部的故障信息字段，根據該字段構造新的拓撲結構，然后利用新的拓撲結構重新計算最短路徑，從而實現報文的無環路轉發。該算法最大的好處是消除了路由收斂過程，然而計算復雜度高，對路由協議的改動比較大，不容易實際部署。在所有的路由保護方案中，DC［27］以其簡單而受到業界的密切關注，并且得到了華為和華三等路由器廠商的部署和支持。但是，目前DC的實現復雜度隨著網絡節點的平均度的增加而增加，極大地增加了路由器的開銷。

本文提出的一種線性時間復雜度的高效路由保護方法，致力于解決如何在保證不降低DC的故障保護率前提下，降低實現DC的復雜度。

2 網絡模型和DC規則

2.1 網絡模型

2.2 DC規則

3 備份下一跳計算規則和正確性證明

由2.2節DC規則的基本原理可知，DC規則的計算開銷主要來自于每個節點需要構造以其所有鄰居節點為根的最短路徑樹，這樣隨著網絡節點的增加需要構造的最短路徑樹的棵數也在增加，這樣使得DC規則的計算開銷極大地增加，本文依據DC規則cost（x，d）lt;cost（s，d）成立的基礎上，提出在原有的最短路徑樹上為所有源目的節點對計算出備份下一跳，這樣便可大大地減小DC規則的計算開銷。對于源目的節點對s和d，為了計算節點s到d的所有符合DC規則的備份下一跳，節點s需要知道其所有鄰居節點x∈N（s）到目的節點d的最小代價。目前互聯網部署的DC規則通過構造以鄰居節點為根的最短路徑樹來獲取鄰居節點到目的節點的最小代價。當節點的度數較大時，需要構造的最短路徑樹越多，因此部署開銷越大。

為了降低DC規則實現的復雜度，本章首先提出兩個備份下一跳計算規則，然后從理論上證明這些規則的正確性，最后通過一個例子來解釋備份下一跳計算規則。

3.1 備份下一跳計算規則

3.2 備份下一跳計算規則的正確性證明

3.3 備份下一跳規則舉例

3.4 算法ERPLR

在備份下一跳計算規則的基礎上，本節提出了ERPLR路由保護方法。ERPLR對應的輸入為網絡拓撲結構的G∈（V，E），運行算法時的節點s和以s為根的最短路徑樹spt（s），輸出為節點s到網絡中其余所有節點的備份下一跳集合。

對于任意節點d∈V，d≠s，遍歷源節點s的鄰居節點x，x≠bestnh（s，d），如果該鄰居節點x已經在源節點s到目的節點d的備份下一跳集合中，則遍歷源節點s的下一個鄰居節點（算法1第1～5行）。反之，如果該鄰居節點x不在源節點s到目的節點d的備份下一跳集合中，如果d∈N（s），利用Rule1（s，d，x）判斷備份下一跳計算規則1是否成立（算法2第1～10行），如果Rule1（s，d，x）的返回值為1，則節點x可以作為節點s到d的可選備份下一跳，并且根據定理6更新節點d的所有子孫節點的備份下一跳（算法1第6～9行）。如果dN（s），利用Rule2（s，d，x）判斷備份下一跳計算規則2是否成立（算法3第1～28行），如果Rule2（s，d，x）的返回值為1，則節點x可以作為節點s到d的可選備份下一跳，并且根據定理6更新節點d的所有子孫節點的備份下一跳（算法1第11～15行）。

3.5 算法復雜度分析

定理7 算法ERPLR的平均時間復雜度為O（V+E）。

證明 算法ERPLR為源節點s計算其到所有其他節點的備份下一跳。在計算的過程中，當源節點s的鄰居節點都有備份下一跳時，根據定理6可知，鄰居節點的所有子孫節點都可以計算出自己的備份下一跳。在這種情況下，除去源節點s外，其余所有的節點最多被訪問一次，每條鏈路最多被訪問一次，因此計算復雜度為O（V+E）。當源節點s的部分鄰居節點沒有備份下一跳的時候，ERPLR僅僅需要為其孩子節點計算備份下一跳，最壞的情況下，該鄰居節點的所有子孫節點都沒有備份下一跳，在這種情況下，需要為lg V個節點計算備份下一跳，因此計算復雜度為 lg|V|O（|V|+|E|）。在實際網絡中，在大多數情況下，源節點僅僅需要為其鄰居節點計算備份下一跳，因此在實際網絡中，ERPLR的復雜度近似于O（V+E）。

4 實驗

本章通過模擬實驗來驗證算法DC和ERPLR的性能，評價的指標主要包括運行時間、故障保護率和路徑拉伸度。下面首先介紹實驗數據集，然后描述實驗結果并對結果進行分析。

4.1 數據集

為了充分驗證算法的性能，本文在真實拓撲和模擬拓撲中選擇了21個網絡拓撲，其中真實拓撲來自于由阿德萊德大學公布的The Internet Topology Zoo ，模擬拓撲來自于利用 Brite［28］軟件生成的拓撲結構，兩者的參數如表2和3所示。

4.2 仿真環境

本文基于Python語言實現了ERPLR算法以及DC算法，并在4.1節所述的拓撲網絡中運行算法進行對比，這些程序運行在處理器Intel CoreTM i7-6400 CPU@2.60 GHz，內存16 GB的Windows 10電腦上。

4.3 評價指標

4.3.1 運行時間

本文利用實際計算時間來衡量不同算法的計算開銷。算法的運行時間為算法開始運行到算法結束所需要的時間。實驗中最終的運行時間為10次運行時間的平均值。

4.3.2 故障保護率

4.3.3 路徑拉伸度

分子計算方法為，對于每個節點對，隨機指定除這兩者之外其他的節點作為故障節點，尋找故障節點的前一個節點備份節點，求其到目的節點的最短路徑，如仍包含故障節點，重復上述操作，直至到達目的節點為止。式中分母為OSPF算法下的代價，僅當分子的節點對存在備份路徑，到達目的節點，則計算方法為刪去故障節點，重新生成一棵以源節點為根的最短路徑樹，計算源節點到目的節點的最小代價。

4.4 實驗結果

如表4所示，列出了算法DC和ERPLR在運行時間、故障保護率和路徑拉伸度三個指標的性能。從表4可以看出DC的運行時間遠遠大于ERPLR的運行時間。與DC相比較，在真實拓撲中ERPLR的運行時間平均降低了74.93%，在真實拓撲VtLWavenet2008和TataNId中，分別降低了92.67%和96.17%；在模擬拓撲中平均降低了78.91%的計算時間開銷。當網絡平均度一定時，隨著節點數量的增加，兩者的運行時間均有一定的增加，但是ERPLR的運行時間增加得較為平穩。 從表4可以看出算法ERPLR和DC在故障保護率、路徑拉伸度等指標的性能基本接近。從實驗結果可以得到如下結論：ERPLR可以在不影響故障保護率和路徑拉伸度的前提下極大地降低部署路由保護算法的開銷。

5 結束語

針對目前互聯網部署DC開銷較大的問題，本文提出了一種線性時間復雜度的高效路由保護方法ERPLR。ERPLR利用備份下一跳計算規則來計算符合條件的備份下一跳，備份下一跳計算規則中所有參數的數值都是已知的，不需要額外的計算，因此大大降低了計算開銷。模擬實驗結果表明，與DC規則比較，ERPLR不僅極大地降低了DC規則的計算開銷，并且與DC規則在故障保護率和路徑拉伸度指標具有相似的性能。本文主要研究在傳統網絡中改進DC的方法，對于一些大型的網絡，由于節點以及節點的平均度比較大，該算法可大大地節省計算開銷，避免給路由器帶來較大的負擔，保證路由器的性能穩定性，從而使得路由器廠商以及互聯網服務提供商提供更優質的服務；對網絡及時性需求較高的應用來說，可減少因網絡中斷帶來的影響。目前來說路由可用性的研究已經得到很大的發展，下一步將在路由可用性的基礎上研究路由節能技術。隨著SDN技術的出現，互聯網必將長期處于SDN技術和傳統技術共存的狀態，因此下一步將研究如何在混合SDN中快速部署DC技術。

參考文獻：

［1］Gopalan A，Ramasubramanian S.IP fast rerouting and disjoint multipath routing with three edge-independent spanning trees［J］.IEEE/ACM Trans on Networking，2018，24（3）：1336-1349.

［2］Singh V，Bharti A K，Chandra N.Edge computing：a soul to Internet of Things（IoT） data［M］//Artificial Intelligence and Machine Learning for EDGE Computing.New York：Academic Press，2022：355-372.

［3］Wang Huadong，Chen Ying，Dong Shi.Research on efficient-efficient routing protocol for WSNs based on improved artificial bee colony algorithm［J］.IET Wireless Sensor Systems，2017，7（1）：15-20.

［4］Young J，Barth T.Web performance analytics show even 100-millise-cond delays can impact customer engagement and online revenue［R/OL］.（2017-04-18）［2022-06-12］.https：//www.akamai.com/newsroom/press-release/akamai-releases-spring-2017-state-of-online-retail-performance-report.

［5］Suznjevic M，Saldana J.Delay limits for real-time services［EB/OL］.（2016-06-13）［2022-06-12］.https：//datatracker.ietf.org/doc/html/draft-suznjevic-dispatch-delay-limits.

［6］Tapolcai J，Retvari G，Babarczi P，et al.Scalable and efficient multipath routing：complexity and algorithms［C］//Proc of the 23rd International Conference on Network Protocols.Piscataway，NJ：IEEE Press，2016：1092-1648.

［7］Yang Yuan，Xu Mingwei，Li Qi.Tunneling on demand：a lightweight approach for IP fast rerouting against multi-link failures［C］//Proc of International Symposium on Quality of Service.Piscataway，NJ：IEEE Press，2018：1-10.

［8］Mani S，Nene M J.Data loss prevention due to link-flapping using software defined networking［C］//Proc of the 6th International Confe-rence for Convergence in Technology.Piscataway，NJ：IEEE Press，2021：1-5.

［9］Bogle J，Bhatia N，Ghobadi M，et al.Teavar：striking the right utilization-availability balance in WAN traffic engineering［C］//Proc of ACM Special Interest Group on Data Communication.New York：ACM Press，2019：29-43.

［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］耿海軍，施新剛，王之梁，等.基于最小路徑交叉度的域內路由保護方案［J］.軟件學報，2020，31（5）：1536-1548.（Geng Haijun，Shi Xingang，Wang Zhiliang，et al.Intra domain routing protection scheme based on minimum path crossing degree［J］.Journal of Software，2020，31（5）：1536-1548.）

［12］Jiang Jinfang，Han Guangjie.Routing protocols for unmanned aerial vehicles［J］.IEEE Communications Magazine，2018，56（1）：58-63.

［13］Schneider K，Zhang Beichuan，Benmohamed L.Hop-by-hop multipath routing：choosing the right next hop set［C］//Proc of IEEE International Conference on Computer Communications.Piscataway，NJ：IEEE Press，2020：2273-2282.

［14］Moy J.IETF STD 54，RFC 2328，OSPF version 2［S/OL］.（1998-04）［2022-06-12］.https：//www.rfc-editor.org/rfc/rfc2178.html.

［15］Shand M，Bryant S.RFC 5714，IP fast reroute framework［R/OL］.（2010-01）［2022-06-12］.https：//tools.ietf.org/html/rfc5714.

［16］Enyedi G，Szilagyi P，Retvari G，et al.IP fast reroute：lightweight Not-Via［C］//Proc of IEEE International Conference on Computer Communications.Piscataway，NJ：IEEE Press，2009：2771-2775.

［17］Xu Mingwei，Yang Yuan，Li Qi.Selecting shorter alternate paths for tunnel based IP fast reroute in linear time［J］.Computer Networks，2012，56（2）：845-857.

［18］Filsfils C，Francois P，Shand M，et al.RFC 6571，Loop-free alternate（LFA） applicability in service provider（SP） networks［S/OL］.（2012-06）［2022-06-12］.https：//tools.ietf.org/html/rfc6571.

［19］Jia Xuya，Li Dan，Zhu Jing，et al.Metro：an efficient traffic fast rerouting scheme with low overhead［J］.IEEE/ACM Trans on Networking，2019，27（5）：2015-2027.

［20］Foerster K T，Kamisinski A，Pignolet Y A，et al.Improved fast rerouting using postprocessing［J］.IEEE Trans on Dependable and Secure Computing，2020，19（1）：537-550.

［21］Yang Xiaowei，Wetherall D.Source selectable path diversity via routing deflections［C］//Proc of ACM Special Interest Group on Data Communication.New York：ACM Press，2006：159-170.

［22］Kvalbein A，Hansen A F，Cicic T，et al.Fast IP network recovery using multiple routing configurations［C］//Proc of IEEE International Conference on Computer Communications.Piscataway，NJ：IEEE Press，2006：1-11.

［23］Cevher S，Ulutas M，Altun S，et al.Multiple routing configurations for fast re-route in software defined networks［C］//Proc of the 24th Signal Processing and Communication Application Conference.Piscataway，NJ：IEEE Press，2016：993-996.

［24］Zhang Mingui，Liu Bin，Zhang Beichuan.Multi-commodity flow traffic engineering with hybrid MPLS/OSPF routing［C］//Proc of GLOBECOM IEEE Global Telecommunications Conference.Piscataway，NJ：IEEE Press，2009：1-6.

［25］Mehraban S，Vora K B，Upadhyay D.Deploy multi-protocol label switching（MPLS） using virtual routing and forwarding（VRF）［C］//Proc of the 2nd International Conference on Trends in Electronics and Informatics.Piscataway，NJ：IEEE Press，2018：543-548.

［26］Lakshminarayanan K，Caesar M，Rangan M，et al.Achieving convergence-free routing using failure-carrying packets［C］//Proc of ACM Special Interest Group on Data Communication.New York：ACM Press，2007：241-252.

［27］Atlas A，Zinin A.RFC 5286，Basic specification for IP fast reroute：loop-free alternates［S/OL］.（2008-09-01）［2022-06-12］.https：//www.hjp.at/doc/rfc/rfc5286.html.

［28］Xu Anmin，Bi Jun，Zhang Baobao，et al.Failure inference for shorte-ning traffic detours［C］//Proc of IEEE/ACM International Sympo-sium on Quality of Service.Piscataway，NJ：IEEE Press，2017：1-10.