基于覆蓋網絡的災后恢復策略研究綜述

吳之沫，馬琳茹

（中國人民解放軍軍事科學院 系統工程研究院，北京 100039）

0 引言

人們的日常生活離不開網絡提供的各種服務，各行各業對網絡性能的要求越來越嚴格，網絡規模和復雜度呈爆炸性增長趨勢。然而，當前的網絡基礎設施面臨著各種各樣的潛在威脅，除了網絡部件自然老化而導致的失效問題，還隨時可能遭遇地震、洪水、颶風等自然災害，以及恐怖襲擊、軍事戰爭等人為災難性事件。即使發生故障的是一個或幾個網絡部件，其周圍區域也會由于受到網絡信息流量過載的影響而發生擁塞，引發連鎖效應，最終導致相當一部分節點甚至整個網絡崩潰。因此，及時對網絡故障進行修復至關重要。

為解決現有TCP/IP 體系架構服務質量提升緩慢、路由故障恢復效率低下以及可擴展性差等問題，科學家們提出使用覆蓋網絡對現有網絡進行系統性、廣泛性、整體性改造。覆蓋網絡是一種整合式互聯網改進方案，相較于打補丁式的改良式方案與從零開始的革命式方案，其是一種介于二者之間的折中方案［1］，既不會明顯增加網絡復雜性，也無需拋棄現有網絡體系，只需在現有網絡結構的IP 層之上、應用層之下增加一個中間層，采用覆蓋網絡改善當前互聯網即可。這種對互聯網體系架構的系統性修補可以在保留現有互聯網架構的前提下提供更可靠的服務，為下一代互聯網設計提供了一種可行性方案。

基于虛擬化傳輸的特性，覆蓋網絡部署時間短、可拓展性強，在災后恢復方面的應用研究呈上升趨勢，目前已被廣泛應用于公路交通網絡［2］、光網絡［3］、相互依存網絡［4］、水下無線傳感器網絡［5］等各個領域。然而，覆蓋網絡在災后恢復中的應用研究尚不成體系，或僅聚焦于單純的故障定位［6］、故障檢測［7］，或側重于相互依存網絡［4］的災后響應。為此，本文對覆蓋網絡應用于信息網絡災后恢復方面的相關文獻進行整理與總結，從故障建模和受損網絡連接恢復兩個方面入手，綜述覆蓋網絡災后恢復方法，為相關研究者提供參考。

1 覆蓋網絡容災性研究基礎

1.1 覆蓋網絡發展歷程

覆蓋網絡本質上是一種面向服務的邏輯網絡［8］，其節點由連接在互聯網上的部分終端節點或應用類服務器組成，每條網絡鏈路對應一條或多條物理鏈路。如圖1 所示，覆蓋網絡將二層報文封裝在IP 報文之上，利用成熟的IP 路由協議進行數據分發，構建了一層邏輯拓撲。其網絡拓撲由服務提供商們根據用戶需求定義，可以在不改變互聯網基礎設施的前提下提供更可靠、容錯性更好的服務，彌補了傳統網絡路由的缺陷，提高了互聯網的可擴展性和魯棒性。

Fig.1 Impact of overlay network technology on the Internet hierarchy architecture圖1 覆蓋網絡技術對互聯網層次架構的影響

早在1974 年，英國學者Duerdoth［9］就提出了覆蓋網絡的概念，不過這個概念最初是應用于電信技術上。在那個模擬技術與數字技術并存的時期，使用覆蓋網絡作為主干網絡可以在保留原有電話服務的基礎上引入數字技術，同時避免高昂的經濟成本。隨著信息技術的發展，光纖技術開始走進大眾視野。1986 年，德國學者提出寬帶通信服務覆蓋網絡［10］，德國郵政公司將覆蓋網絡技術視為發展高效集成通用網絡的戰略［11］。自此，覆蓋網絡正式被視為承舊啟新的框架技術，繼電報網、電話網、綜合業務數字網之后走進了人們的視線。21 世紀初，覆蓋網絡被應用于可靠多播技術［12］，充分利用底層網絡拓撲，通過覆蓋樹協議構造了可靠分發樹，為用戶提供故障容忍的密集帶寬。此后，覆蓋網絡普遍應用于網絡組播技術。

近年來，覆蓋網絡技術得到了深入研究和廣泛應用，如以去中心化為特點的對等網絡（Peer to Peer，P2P）常用于文件共享［13-14］、即時通信［15］、協同處理［16］和流媒體通信［17］領域；內容分發網（Content Delivery Network，CDN）用于視頻分發，采用重定向機制縮短了分發服務器與用戶的距離［18］，不僅可以提高訪問速度，還能緩解網絡擁塞；應用層多播機制通過建立路由器間的多播分發樹管理成員和分發數據［19］。此外，覆蓋網絡還常用于增強服務質量（Quality of Service，QoS）［20］、云計算數據中心網［21］、軟件定義網絡（Software Defined Network，SDN）［22］等技術領域。

覆蓋網絡受到大眾青睞的主要原因是其可以在不改變底層網絡的前提下提供組播、QoS 增強等服務，對下層網絡故障透明，結構多樣化且具有較低的部署成本和部署難度。這些優點有效緩解了傳統IP 網絡的僵化問題，精簡和優化了網絡整體結構。同時，超節點的存在使復雜的網絡鏈路變得簡單靈活，具有很好的魯棒性［23］。

1.2 網絡容災性的含義

伴隨科學技術日新月異的發展，通信網絡面臨的潛在威脅也越來越極端，一個完備的通信網絡體系必須具備一定的容災能力。從數學層面來說，網絡容災性可被描述為一個網絡被徹底破壞所需要除掉的節點數占總節點數的比例，在現實世界中則表現為當局部網絡遭到破壞或網絡服務大規模損毀時，網絡仍然可以保持關鍵服務正常運行的能力。具有較高容災性的網絡能夠更好地預防和抵御攻擊，并在受到攻擊后快速恢復。

如圖2 所示，圍繞提高容災性這一目標，覆蓋網絡研究工作可以分為兩個方面：一是災難損毀模型建立。合適的損毀模型可以精確描述網絡受損情況，分為確定性損毀模型和概率故障模型兩種；二是受損網絡的連接恢復。可采用主動式保護、被動式恢復以及主被動結合恢復3 種策略，其中主動式保護策略通過提供備份節點或鏈路，使覆蓋網絡可以迅速切換受損節點或鏈路，防止由于部分節點或鏈路失效而造成的大面積癱瘓；被動式恢復策略是指在災難發生后，即使網絡遭受到外力破壞導致拓撲結構發生變化或重組，仍然可以通過重路由等方式使系統恢復正常運作，完成預期主要目標，強調的是網絡的恢復能力。

Fig.2 Classification of overlay network research work圖2 覆蓋網絡研究工作分類

2 災難損毀故障建模

網絡災后恢復的前提是定位網絡發生損毀的位置，及時精確地監控網絡故障，這就需要對災難損毀故障進行建模。災難損毀模型可以直觀展示災害對網絡的影響，包括受損位置、損毀范圍、癱瘓程度等。然而，由于災難類型多樣，研究人員很難為每一種自然災害和人為損壞建立合適的模型，現有研究多為利用幾何知識建立理論模型，主要分為確定性損毀模型和概率故障模型兩種。

2.1 確定性損毀模型

確定性損毀模型的關鍵在于找到受災區域，關注的是故障的地理位置，一旦計算出受災區域，便假設這個區域中所有的網絡設備全部被損毀，即故障概率為1。2010年，Neumayer 等［24］首次將計算幾何的理論工具應用于網絡容災性研究中，提出一個簡化的二部圖模型。該模型使用線段表示颶風等造成的線性災害，圓形表示地震等造成的區域性災害，利用多項式時間算法在平面圖模型中識別最壞線切割和最壞圓切割，這是網絡最脆弱的部分，任何在地理位置上與該災害區域相交的網絡組件均無法正常工作；Stojan 等［25］降低了Neumayer 等研究的復雜性，在其基礎上開發了一種多項式時間算法，采用橢圓形和多邊形表示網絡失效的脆弱區域；Tapolcai 等［26］受到二部圖模型的啟發，提出固定半徑的圓盤破壞模型，以故障點為圓心，認為一定半徑內的所有網絡部件均受到了災難影響。考慮到大多數災難可能并不是均勻分布的，Gour 等［27］在固定半徑的圓盤失效模型中引入邊和路徑脆弱區的概念，使其適用于失效事件非均勻分布的災難區域。該模型使用圓盤表示災難損毀區域，簡單直觀，極大降低了處理區域性損毀的復雜度，在災后恢復工作中得到廣泛使用。然而，圓盤形災難模型僅適用于區域性災害，如地震、大規模殺傷性武器導致的災難，而對于颶風、海嘯、山體滑坡、自然火災等，圓盤模型并不能精確描述。

在實際場景中，受災區域往往不是呈現出圓盤形、四邊形、線形等規則形狀。為精確描述災難造成的不規則傷害，Agrawal 等［28］針對地震造成的損毀，結合震中位置、震中密度、地震震級和網絡拓撲等要素提出地震風險骨干網絡模型，將地理區域細分為多個任意形狀的地震帶，表示不同級別的地震風險；同時還提出地震風險最小化節點遷移方案，使得模型在網絡動態變化時也能準確描述受損區域與受損程度。然而，這些關于災難建模的研究均默認網絡在一個平面上，而地球是類球形的，這種計算方式難免有些失真。對于一些小規模的損毀，這種失真是微不足道的，而對于一個幅員遼闊的國家、大陸甚至大洲，這種映射的誤差將會超過5%。為此，Vass 等［29］通過改進多項式共享風險鏈路組（Shared Risk Link Groups，SRLG）生成技術，使模型適應球面幾何，生成更精確的SRLG 列表，同時還引入圖密度參數，使模型同樣適用于不規則受災區域。

2.2 概率故障模型

確定性損毀模型雖然直觀，但過于簡化，難以表達真實損毀場景的一些重要特征。事實上，某區域即使發生了災害，其網絡組件也未必全部損毀，只是大大增加了發生故障的概率。網絡損毀的概率與鏈路長度、節點密度、災害強弱和災害區域大小均有關系，可采用概率損毀模型進行預測。例如，Vass等［30］假設在災害發生后區域網絡平面中會產生一個明顯的故障概率分布，并依據該假設構造了鏈路失效的聯合概率分布，提出通用概率區域損毀模型，其中鏈路的累積失效概率取決于鏈路長度以及鏈路與災害的地理鄰近性。針對虛擬網絡的生存性，Oliveira 等［31］提出高度時空相關的多鏈路故障災難模型。由于網絡功能虛擬化（Virtual Network Feature，VNF）基礎設施具有極高的復用度，VNF 網絡中的節點和鏈路故障具有高度相關性，如果在前一組故障修復前發生了更多災害，可能會導致多組相關鏈路發生故障。該文獻還創造性地采用基于網格分區的方案估計隨機區域故障下的各種網絡統計指標，網格劃分不僅有助于識別網絡的脆弱區域，還可以依據網格對故障發起適當保護。

表1 對以上災難損毀故障建模方案的基本信息進行了總結，其中適用網絡為靜態網絡的方案只能在災難發生后進行一次建模，而動態網絡則可以根據受災區域的變化進行適應性建模。

Table 1 Disaster damage modeling schemes表1 災難損毀建模方案

3 受損網絡連接恢復

3.1 主動式連接保護策略

建立災難損毀故障模型的目的是為了更加及時有效地恢復受損鏈接。當前應用最為廣泛的網絡連接恢復策略為主動式連接保護策略，主要應用于發生單鏈路故障或多條獨立鏈路故障的場景，即當網絡遭受不嚴重的破壞，只有個別節點或鏈路發生故障之時。研究指出，網絡中70%的故障都是單鏈路故障［32］。在大多數情況下，任意網絡節點對之間傳輸數據都只選擇路徑最優的那一條，如果這條最優路徑上的任何一條鏈路發生了故障，那么該節點對之間的通信便會中斷。主動式連接保護策略即在災難發生前為這對節點設置一條或多條備用路徑，當使用最優路徑無法進行通信時，源節點快速將流量轉入次優路徑，使得通信業務得到恢復并實現正常傳輸。

根據備份原理，主動式連接保護策略又可分為節點備份方案和鏈路備份方案。在節點備份方案方面，Zhi 等［33］以節點度作為評價指標，采用對等覆蓋網絡拓撲自動恢復算法為關鍵節點的每一條邊選取一個度較小的點作為備用節點，同時在節點接收數據包時執行路徑壓縮算法，以確保網絡拓撲的正確性和連通性，提高網絡傳輸效率；朱國暉等［34］將建立覆蓋網絡的成本與收益納入考量，綜合考慮節點資源度、接受中心度、網絡收益開銷比、鏈路重要程度等因素建立覆蓋網絡，只有新生成的鏈路所需資源之和小于物理網絡剩余資源時才將鏈路端點納入備用節點候選集；郝黨科等［35］將大數據技術引入節點篩選算法，將研究場景設定在高速公路網絡上，利用工程參數表和大數據用戶識別技術篩選出核心節點，并由此建立關系庫；然后應用黃金分割搜索算法得出最優備份節點，最終實現了站點故障后網絡的自修復，確保了故障區域的網絡覆蓋與業務質量。

在面向業務的覆蓋網絡中可優先選擇最佳鏈路恢復故障。例如，Li等［36］將保護能力感知技術與面向故障避免技術相結合以提高虛擬網絡的可靠性。其假設每條鏈路都對應一個失效概率，由此選出需要重點保護的主鏈路，并使用基于馬爾可夫的線性規劃為每條主鏈路計算備份路徑。為減少預備份所需資源，耿海軍等［37］提出可在每個路由節點轉發表中保存和維護最優下一跳和次優下一跳，當目標節點的最優路徑發生故障時便自動切換至次優下一跳，如此以來大大減小了算法的存儲空間；Hirano 等［38］和Khouangvichit 等［39］認為傳統穩健優化方案高估了備份鏈路的容量，分別將備份鏈路設計問題描述為具有魯棒優化和穩健優化的混合整數線性規劃（Mixed Integer Linear Programming，MILP）問題，以最小化備份資源為目標尋找最優備份鏈路；Wang 等［40］以提高備份資源利用率為思路，提出一種基于環的單鏈路故障恢復方法，根據節點重要性與鏈路性能選擇核心節點并將其連接成共享環，使所有備份路徑共享該路徑，即每個備份路徑都包含共享環的一部分。共享環生成后，根據故障鏈路的位置處理故障，若故障鏈路不屬于共享環，就先將受故障影響的數據包重定向至環節點，然后沿環傳輸；若故障鏈路屬于共享環，受故障影響的數據包將沿環以相反方向傳輸。該方法提高了備份的可重用性，降低了備份路由數；同時為了保證備份路由性能，該方法還會根據預測負載定期更新環路。

主動式連接保護策略可以非常高效地恢復網絡連接，這是由于所有路徑的計算工作是預先完成的，故障發生后只需要進行簡單的路徑切換。然而，為不同故障場景建立不同備份路徑需要較高的部署成本，而且當發生地震、洪水等大規模區域損毀時，主動式連接保護策略提供的多條備份路徑極有可能同時失效。表2 列出了上述主動連接保護策略的優點、局限性等基本信息。

3.2 被動式重新尋路策略

被動式重新尋路策略無需提前預留資源，只需要在故障發生后根據當前網絡的實時路由狀態及資源剩余情況計算重路由方案，基于設定的反應機制應對災難損毀。目前關于該策略的研究主要集中在最短路徑計算、故障信息傳播等方面，且多數研究是依靠覆蓋網絡的虛擬性靈活繞開發生故障的網絡部件，以保持信息的正常傳輸。例如，張艷梅［41］通過限制網絡拓撲單位時間內需要維護的消息數量，在給定維護代價的基礎上使用自適應搜索的免疫克隆算法求解路由性能最好、物理鏈路重用度最小的備選鏈路，將網絡災后恢復工作轉化為多目標約束優化問題。從單個角度來看，該方法找到的備選鏈路可能并不是最優的，但當同時考慮維護代價、路由性能和物理鏈路負載等多個子目標時，其是最優方案。然而與大多數主動式連接保護策略相同，這種選擇節點或鏈路的方法難以應對大規模災難損毀。Zad 等［42］提出一種針對大規模區域損毀場景的網絡恢復方法，稱為迭代隨機恢復算法（Iterative Stochastic Recovery，ISR）。該算法將修復成本建模為網絡中每個要素的失效概率函數，該成本與節點所在位置有關，旨在恢復連接的同時最小化期望恢復成本。該算法無需使用故障概率先驗知識，解決了在不了解受損節點確切位置時的網絡恢復問題，但沒有考慮到災難損毀后恢復資源受限的情況。

考慮到發生故障時覆蓋網絡路由與底層網絡均會發出報警信號，且會采取各自獨立的重路由機制恢復故障，如果不對二者路由策略的沖突問題加以協調控制，將會產生恢復沖突和網絡資源浪費現象。為此，Srinivasan 等［43］提出3 種雙重路由協調恢復機制：①為覆蓋網絡的故障恢復設置概率門限；②為網絡故障恢復設置計時器，等待IP層先進行重路由；③為覆蓋網絡與IP 層檢測到的故障時間間隔設置門限。然而以上3 種方式均會增加故障恢復時間，且需要確定是哪一層發生了故障。為降低選路代價，武照東［44］提出基于不同自治域的雙重路由協調機制，按照自治域對故障進行分類，自治域之內的覆蓋網絡節點可以采用內部網關協議（如OSPF 路由協議、RIP 協議）選擇路由，而自治域之間需要采用外部網關協議（如BGP 協議）使得自治域互聯。在OSPF 協議中的Hello 包中加入自治系統（Autonomous System，AS）號，若接收節點的AS 號與源節點相同，則為自治域內故障，可使用IP 網絡的重路由機制恢復；若AS 號不同，則采用覆蓋網絡的重路由機制恢復，如此以來可以降低網絡抖動次數，減少恢復時的競爭沖突，實現路由的最優恢復。

3.3 主被動結合的災后恢復策略

主動式保護策略降低了受損網絡恢復時間，但需要大量備份資源；被動式恢復策略更加靈活，但所需恢復時間較長。從網絡全生命周期的視角考慮，將主動式連接保護策略與被動式重新尋路策略緊密結合起來可對網絡拓撲進行更全面的保護，極大提高其對災難的抵御能力。

覆蓋網絡中最常見的主被動結合災后恢復策略均在彈性覆蓋網絡（Resilience Overlay Network，RON）的基礎上進行［45］。作為一種應用層路由技術，RON 節點采用主動與被動相結合的方式監測內部路由的服務質量，并依據這些信息選擇下一跳覆蓋節點。在生成彈性路由層時需要首先隔離部分鏈路，然后檢查鏈路的連通性并由此生成路由層。理論上來說，當生成的彈性層足夠多、隔離的鏈路組合足夠豐富時便可以恢復所有類型的多鏈路故障。例如，Andersen 等［46］證實了RON 的故障診斷和恢復能力明顯優于普通路由，能有效降低數據傳輸丟失率和延遲；Iloglu 等［47］對受損后的道路基礎設施網絡進行數學建模，分別使用基于拉格朗日的求解過程和基于線性松弛的整數規劃過程兩種啟發式算法證明了多重覆蓋的可行性。然而，由于要想獲得好的恢復效果就必須生成足夠多的路由層，導致開銷巨大，傳統的RON 網絡難以大規模部署，可拓展性較差。此外，RON 的路由表只能覆蓋RON 節點，對于RON 以外的目的地則無能為力。為此，趙珩等［48］提出基于網絡分塊的主被動相結合的網絡恢復策略，利用Kmeans 算法將網絡分塊，選取集合中心的節點作為集合中間節點，度最大的節點作為系統覆蓋節點，如此以來網絡流量在傳輸中便可以借助源路由及時跳過故障區域，通信網絡的可靠性明顯提升。此外，考慮到災后故障區域極容易發生網絡信息擁堵現象，該策略還加入擁塞感知恢復系統，以便實現跳級處理，同時客戶端模塊與覆蓋節點模塊可保障系統中節點不會發生環路傳輸情況；Zhang 等［49］提出一種用較少備份資源實現故障恢復的方法，根據鏈路復用度和帶寬利用率兩個指標確定鏈路對故障的影響程度，將其分為3 個具有不同優先級的集合，對于具有更低延遲和更高傳輸質量要求的鏈路，使用雙路徑恢復策略進行恢復，即為其記錄兩條備份路徑；對于復用度低或對延遲與數據包丟失沒有較高需求的鏈路采用反應式恢復策略，該策略的備份路徑是動態分配的，但不會在故障發生之前分配恢復路徑所需資源，故障發生后需要額外的信令建立備份路徑；對于優先級居中的鏈路采用單路徑恢復策略，只需預先配置一條備份路徑用于恢復鏈路故障，從而滿足故障切換所需延遲，如果該策略失敗再觸發反應式恢復策略。以上方法可以在滿足鏈路故障所需恢復延遲的同時降低對預備份資源的需求。

3.4 小結

主動式連接保護策略通過預先規劃為重要鏈路預留出冗余資源，在遭遇故障時及時建立保護連接，保證網絡的正常運行。這種方法可以在較短時間內恢復故障，預留資源不能被其他業務共享，會造成網絡資源利用率降低，且靈活性相對較差，若發生大規模災害導致冗余鏈路同時損毀，該策略便會失效。被動式重新尋路策略可在故障場景中動態地為業務計算路由分配資源，從而恢復通信并提高網絡的生存性。這種方法的關鍵在于根據故障發生時刻的網絡現狀以及閑置資源重新規劃路由，從而實現對故障路由的替代，無需預留冗余資源，大大提高了資源利用率。然而，重新進行路由規劃需要花費較多時間，因此對故障的恢復速度不及主動式連接保護策略。為提高網絡生存性，目前常在使用主動式連接保護策略的同時通過被動式重新尋路策略對網絡業務進行保護。

4 結語

與通用的故障處理思路相同，覆蓋網絡的災后恢復策略同樣是先定位、再恢復，相關研究主要聚焦于災難損毀模型建立和受損網絡連接恢復兩方面。當前對于覆蓋網絡在災后恢復方面的應用研究仍處于探索階段，雖然恢復個別節點或鏈路故障的方案較為成熟，但面對地震、颶風等自然災害導致的大規模網絡癱瘓，恢復方案仍存在局限性。在未來研究中應充分考慮災難發生的隨機性和不確定性，以降低冗余資源需求、縮短故障恢復時間和提高恢復率為目標進一步優化覆蓋網絡的災后恢復策略。