基于SRLG不相關陷阱避免算法的研究

張 琦 ，徐 林 ，孫 杰 ，林鵬飛

(1.四川大學 計算機學院， 四川 成都 610065；2.四川大學 物理科學與技術學院，四川 成都 610065；3.阿爾卡特朗訊公司，四川 成都 610041)

計算機通信網絡的可靠性問題十分復雜，抗毀性[1]是其中尤為重要的一點。目前維護網絡生存性的方式有很多種，其中最切實可行的就是為每個請求建立兩條“物理分離”的路徑，分別為工作路由和保護路由，一旦工作路由出現故障，業務可以立刻轉換到保護路由上進行。IETF組織針對此提出了共享風險鏈路組SRLG(Shared Risk Link Group)的概念[2]，對“物理分離”的路徑進行進一步抽象和深化。SRLG被定義為共享同一個物理資源的一組鏈路，同時也是共同承擔失效風險的一組鏈路。

目前國內外計算路由的算法很多，基于SRLG限制的路由問題已經被證明是NP-完全問題[3]。現有文獻提出多種算法來解決該問題，但都有不同程度的缺陷。參考文獻[3]提出的整數線性算法，其時間復雜度較大；參考文獻[4]提出基于SRLG限制的動態共享通路保護算法，網絡資源利用率不高；參考文獻[5]提出工作路由優先(APF)算法，雖然簡單可靠，但卻不能解決“陷阱”問題。本研究基于傳統的TA算法[5]，提出了一種新型基于SRLG不相關的陷阱避免算法，并在1356NT平臺上進行驗證。實驗結果標明，該算法成功避免了“陷阱”問題，從而提高了網絡連接的可靠性。對于中小型網絡，在鏈路故障發生后，可以使恢復時間控制在50 ms以內，資源利用率提高17.23%，具有較強的實用價值。

1 理論研究

1.1 SRLG限制條件

每一個SRLG都對應著一個唯一的標識，即SRLG標識。SRLG分離的兩條路徑可以減少同時失效的可能性，從而提高光路的抗毀能力。傳統的多路由保護方式只考慮單一鏈路或雙鏈路故障，而不考慮SRLG故障。這樣一來，如果工作通道和保護通道經過同一SRLG，即沒有SRLG分離，就很容易因SRLG故障而同時失效。本研究提出的算法是基于SRLG不相關的情況，該算法需要考慮以下兩個SRLG限制條件：(1)在為同一個業務分配工作通道和保護通道時，必須使它們處在兩個不同的SRLG里；(2)如果不同的保護通道共享鏈路上的同一資源，那么，這些保護通道對應的工作路徑必須處在不同的SRLG里。這樣就可以避免SRLG故障，大幅降低工作路由和保護路由同時失效的可能性，從而提高網絡整體的生存能力。

1.2 “陷阱”問題

基于SRLG分離的雙路由選擇策略最簡單的方法是：當選好工作路由后，將工作路由經過的鏈路以及這些鏈路所處的SRLG中的所有鏈路全部刪除，然后再進行備用路由的選擇。這種算法稱為工作路由優先(APF)算法，它較為簡單，并且保證了工作路由和備份路由的SRLG分離，但存在一個明顯的缺點，即容易造成備用路由無法獲取的情況，如圖1所示。以節點D到節點C的連接請求為例來對這種情況進行描述。

圖1中鏈路上的數字代表權重，工作路由為D-EB-C，刪除工作路由經過的所有鏈路(即 D-E，E-B，BC)之后，節點D和節點C之間便不存在任何路由。但實際上，這兩個節點之間可以找到兩條SRLG分離的路由，即D-A-B-C和D-E-F-C。這就是由APF算法的缺陷所導致的“陷阱”問題。

圖1 “陷阱”問題圖示

2 算法設計

結合以前很多研究學者對于光網絡中路由保護算法的研究，在傳統TA算法的基礎上，綜合APF算法，本文提出了一種新型的基于SRLG不相關的“陷阱”避免算法。該算法不考慮每條鏈路上SRLG的數量，同時令每條鏈路上都有唯一的SRLG標識，該算法適用于SRLG數目不多的中小型網絡，簡單靈活，并且避免了SRLG故障和“陷阱”問題，對傳統的TA算法進行了一定程度的改進。

2.1 網絡模型

為了方便描述算法，光網絡圖例拓撲由一個四元函數來表示：G(L，N，C，S)，其中，L 代表光網絡中所有鏈路的集合，并且全部為雙向通信；N代表光網絡中全部節點的集合；Cij代表在第i個節點和第j個節點之間鏈路的權重(代價)；S代表所有SRLG標識組成的集合。規定主路由集合用AP(Active Path)表示，備份路由集合用BP(Backup Path)表示，cost表示每條鏈路的權重，M為一個權重較大的值，并且規定每條鏈路都有不同的SRLG標識。

2.2 算法步驟

基于SRLG不相關陷阱避免算法的具體步驟如下：

(1)確定網絡拓撲 G(L，N，C，S)，等待動態業務連接請求到達。如果有業務連接請求到達，轉至步驟(2)；否則，更新網絡狀態。

(2)檢查圖G中源節點和目的節點的度是否小于2，如果是，則退出算法，因為不可能找到兩條SRLG不相關的路徑；否則，跳轉到步驟(3)。

(3)根據APF算法，先計算出圖G中的最短路徑，放入AP中，并將AP中所有的邊從圖G中刪除，記為圖G，然后檢查圖G′中源節點和目的節點之間的連通性。如果是連通的，即還有路徑可達，則計算出一條最短路徑，放入 BP中，此時AP和BP兩條SRLG不相關的路徑已經找到，退出算法；如果不是連通的，即沒有路徑可達，則可能出現“陷阱”問題，由步驟(4)～(6)來解決此問題。首先將圖G中所有的信息放入圖GAP中，并跳轉到步驟(4)。

(4)將AP和BP設置為空，將GAP中所有邊的權重恢復至圖G中的原始數據，先計算出圖GAP中一條最短路徑，放入到AP中。如果AP為空，則不存在主路由。

(5)在圖G中將AP所有邊的權重改為M，并在圖G中再次計算出一條最短路徑，放入到BP中。如果BP為空，則不存在備份路由。

(6)計算AP和BP的邊交集T。如果交集為空，則AP和BP兩條SRLG不相關的路徑已經找到，退出算法；如果交集不為空，則從圖GAP中將邊交集T刪除，如果圖GAP中的邊不為空，則返回步驟(4)，否則退出算法。

該算法的流程圖如圖2所示。

圖2 算法流程圖

2.3 算法實例

以圖1所示的網絡為例，說明該陷阱避免算法如何工作。對于節點D和C之間的連接請求，由步驟(4)～(6)算得 AP 為(D，E，B，C)，BP 為(D，A，B，C)，AP 和 BP 的邊交集 T為(B，C)，從圖 GAP中刪除邊 T后，重復步驟(4)～(6)，算 得 AP 為 (D，E，F，C)，BP 為 (D，A，B，C)， 此時，AP和BP沒有交集，即找到兩條SRLG不相關的路徑，從而避免了“陷阱”問題。

3 算法驗證及分析

為了驗證此算法的正確性和有效性，實驗采用阿爾卡特朗訊公司的1356NT作為測試平臺，1356NT是一種智能光網絡解決方案的分布式網絡分析和規劃工具。驗證算法的網絡拓撲結構如圖3所示。

圖3 算法驗證網絡拓撲結構圖

圖3中 A、B、C、D、E 代表網元(NE)，每條鏈路上的數字代表該鏈路的權重，并設置每條鏈路的SRLG不相同，保證了SRLG的不相關性。通過1356NT測試平臺，可以查看到相應的工作路由、備份路由以及恢復時間。對該算法的驗證主要從可靠性、恢復時間和資源利用率三個方面進行。

3.1 實驗步驟

測試項目：兩條業務，多次故障。

(1)在圖3所示的網絡中，建立一條從C→D的標簽交換路徑(LSP)，設置保護類型為 PRC，主路由為 C-D，備份路由為C-E-D；

(2)在相應端口設置SDH分析儀；

(3)斷開主路由，即C和D之間連接的光纖，查詢并記錄恢復路由和恢復時間；

(4)斷開備份路由，即C和E之間連接的光纖，查詢并記錄恢復路由和恢復時間；

(5)斷開工作路由和保護路由，即 C、D之間和 C、E之間連接的光纖，查詢并記錄恢復路由和恢復時間。

3.2 實驗結果及分析

實驗結果如表1所示。

表1 實驗結果

PRC類型的業務始終有兩條路由，即一條主路由和一條備份路由，當其中一條發生故障時，網絡會重新為該業務尋找一條新的路由，當主路由和備份路由都發生故障時，網絡則會為該業務建立兩條路由。

從表1可以看出，當主路由或備份路由發生故障時，按照APF算法計算的備份路由均為C-A-B-D，當主路由和備份路由同時發生故障時，電路存在“陷阱”問題。如果按照APF算法計算出的路由只有一條，即C-A-B-D，不能滿足PRC業務的需求。而按照本研究中提出的算法，可以計算出兩條SRLG不相關的路由，即C-A-D和C-BD，避免了“陷阱”問題，提高了整個網絡的可靠性。

從恢復時間上分析，該算法應用到該網絡的恢復時間均小于50 ms，相對于其他算法而言，恢復時間快、效率高。

從資源利用率上分析，用Load表示資源占用率，假設該PRC業務的速率為ODU1(2.5 G)，NE的 Load=每個網元節點使用的帶寬/網元總的帶寬；鏈路的Load=每個鏈路使用的帶寬/鏈路總的帶寬，通過在該軟件中查看相應的表，計算出網元的Load=0.26%，鏈路的Load=25%，相對于其他算法，資源利用率提高了17.23%。

隨著網絡信息量與日俱增，提高網絡抗毀能力的重要性日益凸顯。考慮SRLG約束，建立兩條SRLG不相關的路徑可以降低工作路由和保護路由同時失效的可能性，從而提高網絡的生存能力。在傳統TA算法的基礎上，本研究提出了一種新型基于SRLG不相關的陷阱避免算法，并在阿爾卡特朗訊公司1356NT平臺上進行驗證。實驗結果表明，該算法成功避免了“陷阱”問題，提高了網絡連接的可靠性，在鏈路故障發生后，可以讓恢復時間控制在50 ms以內，資源利用率提高17.23%，具有較強的實用價值。本算法僅適用于中小型網絡，并未考慮SRLG復雜的網絡類型，這將是以后研究的方向。

[1]劉嘯林.網絡抗毀性研究介紹[J].計算機應用與軟件，2007，24(6)：135-137.

[2]PAPADIMITRIOU D， POPPE F， JONES J.Inference of shared risk link groups [EB/OL].http：//www.watersprings.org/pub/id/draft-many-inference-srlg-02.txt，2001-11-14

[3]HU J Q.Diverse routing in optical Mesh networks[J].IEEE Transactions on Communications，2003，51(3)：489-494.

[4]Guo Lei， YuHongfang， LiLemin.Dynamicshared-path protection based on SRLG constraints in WDM Mesh networks[A].ICCCAS 2004.Chengdu， China： IEEE PRESS，2004.

[5]Xu Dahai，Xiong Yizhi，Qiao Chunming.Failure protection in layered networks with shared risk link groups[J].IEEE Network， 2004，18(3)：36-41.