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

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

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

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

1 理論研究

1.1 SRLG限制條件

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

1.2 “陷阱”問題

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

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

圖1 “陷阱”問題圖示

2 算法設(shè)計(jì)

結(jié)合以前很多研究學(xué)者對(duì)于光網(wǎng)絡(luò)中路由保護(hù)算法的研究，在傳統(tǒng)TA算法的基礎(chǔ)上，綜合APF算法，本文提出了一種新型的基于SRLG不相關(guān)的“陷阱”避免算法。該算法不考慮每條鏈路上SRLG的數(shù)量，同時(shí)令每條鏈路上都有唯一的SRLG標(biāo)識(shí)，該算法適用于SRLG數(shù)目不多的中小型網(wǎng)絡(luò)，簡單靈活，并且避免了SRLG故障和“陷阱”問題，對(duì)傳統(tǒng)的TA算法進(jìn)行了一定程度的改進(jìn)。

2.1 網(wǎng)絡(luò)模型

為了方便描述算法，光網(wǎng)絡(luò)圖例拓?fù)溆梢粋€(gè)四元函數(shù)來表示：G(L，N，C，S)，其中，L 代表光網(wǎng)絡(luò)中所有鏈路的集合，并且全部為雙向通信；N代表光網(wǎng)絡(luò)中全部節(jié)點(diǎn)的集合；Cij代表在第i個(gè)節(jié)點(diǎn)和第j個(gè)節(jié)點(diǎn)之間鏈路的權(quán)重(代價(jià))；S代表所有SRLG標(biāo)識(shí)組成的集合。規(guī)定主路由集合用AP(Active Path)表示，備份路由集合用BP(Backup Path)表示，cost表示每條鏈路的權(quán)重，M為一個(gè)權(quán)重較大的值，并且規(guī)定每條鏈路都有不同的SRLG標(biāo)識(shí)。

2.2 算法步驟

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

(1)確定網(wǎng)絡(luò)拓?fù)?G(L，N，C，S)，等待動(dòng)態(tài)業(yè)務(wù)連接請(qǐng)求到達(dá)。如果有業(yè)務(wù)連接請(qǐng)求到達(dá)，轉(zhuǎn)至步驟(2)；否則，更新網(wǎng)絡(luò)狀態(tài)。

(2)檢查圖G中源節(jié)點(diǎn)和目的節(jié)點(diǎn)的度是否小于2，如果是，則退出算法，因?yàn)椴豢赡苷业絻蓷lSRLG不相關(guān)的路徑；否則，跳轉(zhuǎn)到步驟(3)。

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

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

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

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

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

圖2 算法流程圖

2.3 算法實(shí)例

以圖1所示的網(wǎng)絡(luò)為例，說明該陷阱避免算法如何工作。對(duì)于節(jié)點(diǎn)D和C之間的連接請(qǐng)求，由步驟(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)， 此時(shí)，AP和BP沒有交集，即找到兩條SRLG不相關(guān)的路徑，從而避免了“陷阱”問題。

3 算法驗(yàn)證及分析

為了驗(yàn)證此算法的正確性和有效性，實(shí)驗(yàn)采用阿爾卡特朗訊公司的1356NT作為測試平臺(tái)，1356NT是一種智能光網(wǎng)絡(luò)解決方案的分布式網(wǎng)絡(luò)分析和規(guī)劃工具。驗(yàn)證算法的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖3所示。

圖3 算法驗(yàn)證網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

圖3中 A、B、C、D、E 代表網(wǎng)元(NE)，每條鏈路上的數(shù)字代表該鏈路的權(quán)重，并設(shè)置每條鏈路的SRLG不相同，保證了SRLG的不相關(guān)性。通過1356NT測試平臺(tái)，可以查看到相應(yīng)的工作路由、備份路由以及恢復(fù)時(shí)間。對(duì)該算法的驗(yàn)證主要從可靠性、恢復(fù)時(shí)間和資源利用率三個(gè)方面進(jìn)行。

3.1 實(shí)驗(yàn)步驟

測試項(xiàng)目：兩條業(yè)務(wù)，多次故障。

(1)在圖3所示的網(wǎng)絡(luò)中，建立一條從C→D的標(biāo)簽交換路徑(LSP)，設(shè)置保護(hù)類型為 PRC，主路由為 C-D，備份路由為C-E-D；

(2)在相應(yīng)端口設(shè)置SDH分析儀；

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

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

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

3.2 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)結(jié)果如表1所示。

表1 實(shí)驗(yàn)結(jié)果

PRC類型的業(yè)務(wù)始終有兩條路由，即一條主路由和一條備份路由，當(dāng)其中一條發(fā)生故障時(shí)，網(wǎng)絡(luò)會(huì)重新為該業(yè)務(wù)尋找一條新的路由，當(dāng)主路由和備份路由都發(fā)生故障時(shí)，網(wǎng)絡(luò)則會(huì)為該業(yè)務(wù)建立兩條路由。

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

從恢復(fù)時(shí)間上分析，該算法應(yīng)用到該網(wǎng)絡(luò)的恢復(fù)時(shí)間均小于50 ms，相對(duì)于其他算法而言，恢復(fù)時(shí)間快、效率高。

從資源利用率上分析，用Load表示資源占用率，假設(shè)該P(yáng)RC業(yè)務(wù)的速率為ODU1(2.5 G)，NE的 Load=每個(gè)網(wǎng)元節(jié)點(diǎn)使用的帶寬/網(wǎng)元總的帶寬；鏈路的Load=每個(gè)鏈路使用的帶寬/鏈路總的帶寬，通過在該軟件中查看相應(yīng)的表，計(jì)算出網(wǎng)元的Load=0.26%，鏈路的Load=25%，相對(duì)于其他算法，資源利用率提高了17.23%。

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

[1]劉嘯林.網(wǎng)絡(luò)抗毀性研究介紹[J].計(jì)算機(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， 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.