摘  要： 在光網絡通信中，計算路由常常會出現(xiàn)共享風險鏈路組(SRLG)分離和“陷阱”問題。針對這種現(xiàn)象，提出了一種基于SRLG不相關的陷阱避免算法，并采用阿爾卡特朗訊公司的光網絡規(guī)劃工具1356NT進行驗證。實驗結果表明，與傳統(tǒng)路由算法相比，該算法不但縮短了恢復時間，還有效提高了網絡連接的可靠性和網絡資源的利用率。
關鍵詞： 光網絡；共享風險鏈路組；陷阱避免

　計算機通信網絡的可靠性問題十分復雜，抗毀性[1]是其中尤為重要的一點。目前維護網絡生存性的方式有很多種，其中最切實可行的就是為每個請求建立兩條“物理分離”的路徑，分別為工作路由和保護路由，一旦工作路由出現(xiàn)故障，業(yè)務可以立刻轉換到保護路由上進行。IETF組織針對此提出了共享風險鏈路組SRLG(Shared Risk Link Group)的概念[2]，對“物理分離”的路徑進行進一步抽象和深化。SRLG被定義為共享同一個物理資源的一組鏈路，同時也是共同承擔失效風險的一組鏈路。
    目前國內外計算路由的算法很多，基于SRLG限制的路由問題已經被證明是NP-完全問題[3]?，F(xiàn)有文獻提出多種算法來解決該問題，但都有不同程度的缺陷。參考文獻[3]提出的整數線性算法，其時間復雜度較大；參考文獻[4]提出基于SRLG限制的動態(tài)共享通路保護算法，網絡資源利用率不高；參考文獻[5]提出工作路由優(yōu)先(APF)算法，雖然簡單可靠，但卻不能解決“陷阱”問題。本研究基于傳統(tǒng)的TA算法[5]，提出了一種新型基于SRLG不相關的陷阱避免算法，并在1356NT平臺上進行驗證。實驗結果標明，該算法成功避免了“陷阱”問題，從而提高了網絡連接的可靠性。對于中小型網絡，在鏈路故障發(fā)生后，可以使恢復時間控制在50 ms以內，資源利用率提高17.23%，具有較強的實用價值。
1 理論研究
1.1 SRLG限制條件
　每一個SRLG都對應著一個唯一的標識，即SRLG標識。SRLG分離的兩條路徑可以減少同時失效的可能性，從而提高光路的抗毀能力。傳統(tǒng)的多路由保護方式只考慮單一鏈路或雙鏈路故障，而不考慮SRLG故障。這樣一來，如果工作通道和保護通道經過同一SRLG，即沒有SRLG分離，就很容易因SRLG故障而同時失效。本研究提出的算法是基于SRLG不相關的情況，該算法需要考慮以下兩個SRLG限制條件：(1)在為同一個業(yè)務分配工作通道和保護通道時，必須使它們處在兩個不同的SRLG里；(2)如果不同的保護通道共享鏈路上的同一資源，那么，這些保護通道對應的工作路徑必須處在不同的SRLG里。這樣就可以避免SRLG故障，大幅降低工作路由和保護路由同時失效的可能性，從而提高網絡整體的生存能力。
1.2 “陷阱”問題
　基于SRLG分離的雙路由選擇策略最簡單的方法是：當選好工作路由后，將工作路由經過的鏈路以及這些鏈路所處的SRLG中的所有鏈路全部刪除，然后再進行備用路由的選擇。這種算法稱為工作路由優(yōu)先(APF)算法，它較為簡單，并且保證了工作路由和備份路由的SRLG分離，但存在一個明顯的缺點，即容易造成備用路由無法獲取的情況，如圖1所示。以節(jié)點D到節(jié)點C的連接請求為例來對這種情況進行描述。
　圖1中鏈路上的數字代表權重，工作路由為D-E-B-C，刪除工作路由經過的所有鏈路(即D-E，E-B，B-C)之后，節(jié)點D和節(jié)點C之間便不存在任何路由。但實際上，這兩個節(jié)點之間可以找到兩條SRLG分離的路由，即D-A-B-C和D-E-F-C。這就是由APF算法的缺陷所導致的“陷阱”問題。

2 算法設計
　結合以前很多研究學者對于光網絡中路由保護算法的研究，在傳統(tǒng)TA算法的基礎上，綜合APF算法，本文提出了一種新型的基于SRLG不相關的“陷阱”避免算法。該算法不考慮每條鏈路上SRLG的數量，同時令每條鏈路上都有唯一的SRLG標識，該算法適用于SRLG數目不多的中小型網絡，簡單靈活，并且避免了SRLG故障和“陷阱”問題，對傳統(tǒng)的TA算法進行了一定程度的改進。
2.1 網絡模型
　為了方便描述算法，光網絡圖例拓撲由一個四元函數來表示：G(L，N，C，S)，其中，L代表光網絡中所有鏈路的集合，并且全部為雙向通信；N代表光網絡中全部節(jié)點的集合；Cij代表在第i個節(jié)點和第j個節(jié)點之間鏈路的權重(代價)；S代表所有SRLG標識組成的集合。規(guī)定主路由集合用AP(Active Path)表示，備份路由集合用BP(Backup Path)表示，cost表示每條鏈路的權重，M為一個權重較大的值，并且規(guī)定每條鏈路都有不同的SRLG標識。
2.2 算法步驟
　基于SRLG不相關陷阱避免算法的具體步驟如下：
　(1)確定網絡拓撲G(L，N，C，S)，等待動態(tài)業(yè)務連接請求到達。如果有業(yè)務連接請求到達，轉至步驟(2)；否則，更新網絡狀態(tài)。
　(2)檢查圖G中源節(jié)點和目的節(jié)點的度是否小于2，如果是，則退出算法，因為不可能找到兩條SRLG不相關的路徑；否則，跳轉到步驟(3)。
　(3)根據APF算法，先計算出圖G中的最短路徑，放入AP中，并將AP中所有的邊從圖G中刪除，記為圖G，然后檢查圖G′中源節(jié)點和目的節(jié)點之間的連通性。如果是連通的，即還有路徑可達，則計算出一條最短路徑，放入BP中，此時AP和BP兩條SRLG不相關的路徑已經找到，退出算法；如果不是連通的，即沒有路徑可達，則可能出現(xiàn)“陷阱”問題，由步驟(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.3 算法實例
　以圖1所示的網絡為例，說明該陷阱避免算法如何工作。對于節(jié)點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(xiàn)，C)，BP為(D，A，B，C)，此時，AP和BP沒有交集，即找到兩條SRLG不相關的路徑，從而避免了“陷阱”問題。
3 算法驗證及分析
　為了驗證此算法的正確性和有效性，實驗采用阿爾卡特朗訊公司的1356NT作為測試平臺，1356NT是一種智能光網絡解決方案的分布式網絡分析和規(guī)劃工具。驗證算法的網絡拓撲結構如圖3所示。

　圖3中A、B、C、D、E代表網元(NE)，每條鏈路上的數字代表該鏈路的權重，并設置每條鏈路的SRLG不相同，保證了SRLG的不相關性。通過1356NT測試平臺，可以查看到相應的工作路由、備份路由以及恢復時間。對該算法的驗證主要從可靠性、恢復時間和資源利用率三個方面進行。
3.1 實驗步驟
　測試項目：兩條業(yè)務，多次故障。
　(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所示。

　PRC類型的業(yè)務始終有兩條路由，即一條主路由和一條備份路由，當其中一條發(fā)生故障時，網絡會重新為該業(yè)務尋找一條新的路由，當主路由和備份路由都發(fā)生故障時，網絡則會為該業(yè)務建立兩條路由。
從表1可以看出，當主路由或備份路由發(fā)生故障時，按照APF算法計算的備份路由均為C-A-B-D，當主路由和備份路由同時發(fā)生故障時，電路存在“陷阱”問題。如果按照APF算法計算出的路由只有一條，即C-A-B-D，不能滿足PRC業(yè)務的需求。而按照本研究中提出的算法，可以計算出兩條SRLG不相關的路由，即C-A-D和C-B-D，避免了“陷阱”問題，提高了整個網絡的可靠性。
　從恢復時間上分析，該算法應用到該網絡的恢復時間均小于50 ms，相對于其他算法而言，恢復時間快、效率高。
　從資源利用率上分析，用Load表示資源占用率，假設該PRC業(yè)務的速率為ODU1(2.5 G)，NE的Load=每個網元節(jié)點使用的帶寬/網元總的帶寬；鏈路的Load=每個鏈路使用的帶寬/鏈路總的帶寬，通過在該軟件中查看相應的表，計算出網元的Load=0.26%，鏈路的Load= 25%，相對于其他算法，資源利用率提高了17.23%。
隨著網絡信息量與日俱增，提高網絡抗毀能力的重要性日益凸顯?？紤]SRLG約束，建立兩條SRLG不相關的路徑可以降低工作路由和保護路由同時失效的可能性，從而提高網絡的生存能力。在傳統(tǒng)TA算法的基礎上，本研究提出了一種新型基于SRLG不相關的陷阱避免算法，并在阿爾卡特朗訊公司1356NT平臺上進行驗證。實驗結果表明，該算法成功避免了“陷阱”問題，提高了網絡連接的可靠性，在鏈路故障發(fā)生后，可以讓恢復時間控制在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 ， Yu Hongfang ， Li Lemin  ． Dynamic shared-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.