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

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

2 算法設(shè)計
　結(jié)合以前很多研究學(xué)者對于光網(wǎng)絡(luò)中路由保護算法的研究，在傳統(tǒng)TA算法的基礎(chǔ)上，綜合APF算法，本文提出了一種新型的基于SRLG不相關(guān)的“陷阱”避免算法。該算法不考慮每條鏈路上SRLG的數(shù)量，同時令每條鏈路上都有唯一的SRLG標(biāo)識，該算法適用于SRLG數(shù)目不多的中小型網(wǎng)絡(luò)，簡單靈活，并且避免了SRLG故障和“陷阱”問題，對傳統(tǒng)的TA算法進行了一定程度的改進。
2.1 網(wǎng)絡(luò)模型
　為了方便描述算法，光網(wǎng)絡(luò)圖例拓撲由一個四元函數(shù)來表示：G(L，N，C，S)，其中，L代表光網(wǎng)絡(luò)中所有鏈路的集合，并且全部為雙向通信；N代表光網(wǎng)絡(luò)中全部節(jié)點的集合；Cij代表在第i個節(jié)點和第j個節(jié)點之間鏈路的權(quán)重(代價)；S代表所有SRLG標(biāo)識組成的集合。規(guī)定主路由集合用AP(Active Path)表示，備份路由集合用BP(Backup Path)表示，cost表示每條鏈路的權(quán)重，M為一個權(quán)重較大的值，并且規(guī)定每條鏈路都有不同的SRLG標(biāo)識。
2.2 算法步驟
　基于SRLG不相關(guān)陷阱避免算法的具體步驟如下：
　(1)確定網(wǎng)絡(luò)拓撲G(L，N，C，S)，等待動態(tài)業(yè)務(wù)連接請求到達。如果有業(yè)務(wù)連接請求到達，轉(zhuǎn)至步驟(2)；否則，更新網(wǎng)絡(luò)狀態(tài)。
　(2)檢查圖G中源節(jié)點和目的節(jié)點的度是否小于2，如果是，則退出算法，因為不可能找到兩條SRLG不相關(guān)的路徑；否則，跳轉(zhuǎn)到步驟(3)。
　(3)根據(jù)APF算法，先計算出圖G中的最短路徑，放入AP中，并將AP中所有的邊從圖G中刪除，記為圖G，然后檢查圖G′中源節(jié)點和目的節(jié)點之間的連通性。如果是連通的，即還有路徑可達，則計算出一條最短路徑，放入BP中，此時AP和BP兩條SRLG不相關(guān)的路徑已經(jīng)找到，退出算法；如果不是連通的，即沒有路徑可達，則可能出現(xiàn)“陷阱”問題，由步驟(4)~(6)來解決此問題。首先將圖G中所有的信息放入圖GAP中，并跳轉(zhuǎn)到步驟(4)。
　(4)將AP和BP設(shè)置為空，將GAP中所有邊的權(quán)重恢復(fù)至圖G中的原始數(shù)據(jù)，先計算出圖GAP中一條最短路徑，放入到AP中。如果AP為空，則不存在主路由。
　(5)在圖G中將AP所有邊的權(quán)重改為M，并在圖G中再次計算出一條最短路徑，放入到BP中。如果BP為空，則不存在備份路由。
　(6)計算AP和BP的邊交集T。如果交集為空，則AP和BP兩條SRLG不相關(guān)的路徑已經(jīng)找到，退出算法；如果交集不為空，則從圖GAP中將邊交集T刪除，如果圖GAP中的邊不為空，則返回步驟(4)，否則退出算法。
該算法的流程圖如圖2所示。

2.3 算法實例
　以圖1所示的網(wǎng)絡(luò)為例，說明該陷阱避免算法如何工作。對于節(jié)點D和C之間的連接請求，由步驟(4)~(6)算得AP為(D，E，B，C)，BP為(D，A，B，C)，AP和BP的邊交集T為(B，C)，從圖GAP中刪除邊T后，重復(fù)步驟(4)~(6)，算得AP為(D，E，F(xiàn)，C)，BP為(D，A，B，C)，此時，AP和BP沒有交集，即找到兩條SRLG不相關(guān)的路徑，從而避免了“陷阱”問題。
3 算法驗證及分析
　為了驗證此算法的正確性和有效性，實驗采用阿爾卡特朗訊公司的1356NT作為測試平臺，1356NT是一種智能光網(wǎng)絡(luò)解決方案的分布式網(wǎng)絡(luò)分析和規(guī)劃工具。驗證算法的網(wǎng)絡(luò)拓撲結(jié)構(gòu)如圖3所示。

　圖3中A、B、C、D、E代表網(wǎng)元(NE)，每條鏈路上的數(shù)字代表該鏈路的權(quán)重，并設(shè)置每條鏈路的SRLG不相同，保證了SRLG的不相關(guān)性。通過1356NT測試平臺，可以查看到相應(yīng)的工作路由、備份路由以及恢復(fù)時間。對該算法的驗證主要從可靠性、恢復(fù)時間和資源利用率三個方面進行。
3.1 實驗步驟
　測試項目：兩條業(yè)務(wù)，多次故障。
　(1)在圖3所示的網(wǎng)絡(luò)中，建立一條從C→D的標(biāo)簽交換路徑(LSP)，設(shè)置保護類型為PRC，主路由為C-D，備份路由為C-E-D；
　(2)在相應(yīng)端口設(shè)置SDH分析儀；
　(3)斷開主路由，即C和D之間連接的光纖，查詢并記錄恢復(fù)路由和恢復(fù)時間；
　(4)斷開備份路由，即C和E之間連接的光纖，查詢并記錄恢復(fù)路由和恢復(fù)時間；
　(5)斷開工作路由和保護路由，即C、D之間和C、E之間連接的光纖，查詢并記錄恢復(fù)路由和恢復(fù)時間。
3.2 實驗結(jié)果及分析
　實驗結(jié)果如表1所示。

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