孫 強(qiáng)，李德莉，任 葉

(北京交通大學(xué)電子信息工程學(xué)院，北京 100044)

網(wǎng)絡(luò)生存性方案追求的目標(biāo)是快速的恢復(fù)速度和較高的資源利用率。從未來(lái)網(wǎng)絡(luò)結(jié)構(gòu)來(lái)講，高速鐵路光傳送網(wǎng)的網(wǎng)絡(luò)結(jié)構(gòu)會(huì)逐步復(fù)雜化；從網(wǎng)絡(luò)傳輸?shù)臉I(yè)務(wù)種類來(lái)講，其傳輸?shù)臉I(yè)務(wù)會(huì)逐步多樣化；從客戶需求來(lái)講，客戶的大帶寬、大顆粒業(yè)務(wù)需求也對(duì)網(wǎng)絡(luò)提出了更高的要求[1]。研究網(wǎng)絡(luò)生存性、可靠性的目的，是為了在發(fā)生網(wǎng)絡(luò)故障后，使故障業(yè)務(wù)能盡快倒換到提前為其設(shè)置的保護(hù)路徑傳輸，減少業(yè)務(wù)中斷時(shí)間及其給網(wǎng)絡(luò)運(yùn)營(yíng)帶來(lái)的影響，提高網(wǎng)絡(luò)質(zhì)量，避免因?yàn)椴荒芸焖倩謴?fù)業(yè)務(wù)傳輸而給鐵路運(yùn)行帶來(lái)巨大損失，保障乘客生命安全。

以犧牲帶寬來(lái)?yè)Q取保護(hù)是環(huán)恢復(fù)技術(shù)的較大特點(diǎn)，文獻(xiàn)[2]為了避免用200%～300%的冗余帶寬進(jìn)行保護(hù)，構(gòu)造一個(gè)Hamiltonian環(huán)來(lái)連接網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)，但可能會(huì)造成保護(hù)帶寬的利用率不高。文獻(xiàn)[3]針對(duì)上述缺點(diǎn)，提出建立多個(gè)小環(huán)來(lái)覆蓋網(wǎng)絡(luò)中所有節(jié)點(diǎn)，不同小環(huán)可通過同一個(gè)節(jié)點(diǎn)，因此有效提高了備份帶寬的利用率。文獻(xiàn)[4]為了降低節(jié)點(diǎn)保護(hù)環(huán)的ILP容量需求，提出ILP設(shè)計(jì)模型。文獻(xiàn)[5]針對(duì)全光網(wǎng)絡(luò)有望發(fā)展為網(wǎng)狀網(wǎng)結(jié)構(gòu)的趨勢(shì)，提出P-Cycle保護(hù)的概念，P-Cycle保護(hù)同時(shí)結(jié)合了環(huán)網(wǎng)保護(hù)倒換快與網(wǎng)狀網(wǎng)選路靈活的優(yōu)點(diǎn)，資源利用率較高。當(dāng)通過ILP算法來(lái)實(shí)現(xiàn)P-Cycle保護(hù)時(shí)會(huì)需要較長(zhǎng)的時(shí)間，文獻(xiàn)[6]提出提前選擇出可用的圈來(lái)降低運(yùn)行ILP算法所需時(shí)間，進(jìn)而壓縮保護(hù)過程所需時(shí)間，不過這需要在選擇前列舉網(wǎng)絡(luò)中所有的P-Cycle，工作量較大，不能保證準(zhǔn)確率，關(guān)鍵還會(huì)影響算法最終的結(jié)果。文獻(xiàn)[7]為避免列舉P-Cycle，提出跨接鏈路算法SLA(Straddling Link Algorithm)，但該算法的保護(hù)效率與資源利用率較低，因?yàn)樗鼧?gòu)造的圈只能包含一條跨接鏈路。

總之，P-cycle保護(hù)以環(huán)結(jié)構(gòu)為基礎(chǔ)，利用網(wǎng)絡(luò)中的空閑資源提前為網(wǎng)狀網(wǎng)中的業(yè)務(wù)設(shè)置保護(hù)通道[8]，其不同于傳統(tǒng)環(huán)保護(hù)方案最大的特點(diǎn)在于，不僅可以為環(huán)上鏈路的業(yè)務(wù)提供一倍的保護(hù)資源，還可以為跨接鏈路的業(yè)務(wù)提供兩倍保護(hù)資源，資源利用率高[9]。本文提出RVPA P-Cycle構(gòu)造算法，以冗余度、方差為圈擴(kuò)展標(biāo)準(zhǔn)，降低為保護(hù)網(wǎng)絡(luò)中所有業(yè)務(wù)請(qǐng)求所需的P-Cycle數(shù)量與資源占用率，使網(wǎng)絡(luò)資源得到均衡的同時(shí)減少了網(wǎng)絡(luò)保護(hù)倒換時(shí)間。

1 RVPA算法

之前提出的P-Cycle構(gòu)造算法只計(jì)算擴(kuò)展候選圈的冗余度，以致于在最初圈擴(kuò)展時(shí)，P-Cycle的圈上鏈路、跨接鏈路未得到保護(hù)的工作容量方差及大小差距較大，使進(jìn)一步圈擴(kuò)展覆蓋的鏈路中，有部分鏈路上的工作容量均已保護(hù)完，而其他鏈路上還有很多沒被保護(hù)的工作容量，為使這部分工作容量也得到保護(hù)，就需要設(shè)置更多的圈，占用更多的空閑容量，資源利用率不高。因此，本文提出RVPA圈構(gòu)造算法來(lái)改善POCA算法的P-Cycle保護(hù)效果，它在圈擴(kuò)展時(shí)以所有候選圈上未保護(hù)工作容量的方差、冗余度兩個(gè)指標(biāo)為比較標(biāo)準(zhǔn)，選擇兩者都滿足條件的圈作為本輪最終擴(kuò)展圈，有效限制網(wǎng)絡(luò)保護(hù)所需圈個(gè)數(shù)；同時(shí)通過網(wǎng)絡(luò)未保護(hù)鏈路比率UPL、冗余度、參數(shù)M來(lái)限制擴(kuò)展圈長(zhǎng)度，使圈個(gè)數(shù)與圈上節(jié)點(diǎn)數(shù)做到有效均衡，仿真對(duì)比分析在不同M取值下RVPA算法、已有POCA算法[10]的性能，并為RVPA算法選擇其性能最優(yōu)時(shí)對(duì)應(yīng)的M值。

1.1 RVPA算法應(yīng)用舉例

POCA算法單純以冗余度為標(biāo)準(zhǔn)進(jìn)行圈擴(kuò)展，為了改進(jìn)此不足，以及完善其只通過選取取值在某一范圍內(nèi)的參數(shù)K來(lái)限制圈長(zhǎng)度，而并未選擇、比較出算法在性能最優(yōu)時(shí)的K值的缺憾，本文提出RVPA算法，它同時(shí)以方差、冗余度為圈擴(kuò)展標(biāo)準(zhǔn)，并對(duì)比分析兩算法在不同M取值下的仿真結(jié)果，最終為RVPA算法選擇、設(shè)置最優(yōu)M值。

圖1中的網(wǎng)絡(luò)拓?fù)浒?個(gè)節(jié)點(diǎn)、11條鏈路，鏈路權(quán)重代表該鏈路承載的業(yè)務(wù)請(qǐng)求數(shù)量，以該網(wǎng)絡(luò)拓?fù)錇槔f明POCA、RVPA算法的保護(hù)過程。

圖1 RVPA算法與POCA算法

步驟1以3-6鏈路為基礎(chǔ)構(gòu)造最小圈，因?yàn)樵撴溌飞衔幢Ｗo(hù)工作容量最大，具體算法構(gòu)造過程見表1。

表1 最小圈構(gòu)造

步驟2設(shè)定參數(shù)M=0.5，得到此時(shí)全網(wǎng)UPL為0.85，不滿足UPL

步驟3以最小圈C3為基礎(chǔ)開始圈擴(kuò)展，具體過程見表2。

表2 最小圈C3擴(kuò)展表

POCA算法圈擴(kuò)展結(jié)果會(huì)三選一，而RVPA算法圈擴(kuò)展結(jié)果為5-3-1-4-6-5，但其未保護(hù)鏈路比率不滿足小于其冗余度的條件，所以需在第一次圈擴(kuò)展結(jié)果5-3-1-4-6-5的基礎(chǔ)上繼續(xù)進(jìn)行圈擴(kuò)展，當(dāng)達(dá)到擴(kuò)展圈的未保護(hù)鏈路比率同時(shí)小于參數(shù)M和冗余度時(shí)，則本次P-Cycle構(gòu)造完成。然后更新本輪構(gòu)造P-Cycle覆蓋鏈路的工作容量，即圈上鏈路減1、跨接鏈路減2，之后進(jìn)行新一輪的構(gòu)造最小圈、最小圈圈擴(kuò)展、擴(kuò)展圈配置。

1.2 RVPA算法參數(shù)

算法參數(shù)說明見表3。

表3 算法參數(shù)說明

1.3 RVPA算法性能指標(biāo)

算法性能評(píng)價(jià)指標(biāo)說明如下。

(1)算法計(jì)算時(shí)間：即算法運(yùn)算時(shí)間，該值越小越好，它是網(wǎng)絡(luò)故障后受損業(yè)務(wù)保護(hù)倒換時(shí)間的一部分。

(2)PC：該值越大越好，是被保護(hù)的工作容量除以為它配置保護(hù)消耗的空閑容量。

(3)P-Cycle個(gè)數(shù)：指為保護(hù)全網(wǎng)工作容量所需圈的總個(gè)數(shù)，它越小越能降低算法計(jì)算時(shí)間與圈配置錯(cuò)誤的風(fēng)險(xiǎn)。

(4)冗余度R(p)：PC值的倒數(shù)，越小越好，用于評(píng)價(jià)P-Cycle資源利用效率[10-11]，即配置P-Cycle使用波長(zhǎng)總數(shù)除以圈上、跨接鏈路上被保護(hù)波長(zhǎng)的和。

( 1 )

式中：XP,i為圈的各邊能保護(hù)的工作容量大小，其取值由鏈路i與圈的關(guān)系決定，i為圈上邊時(shí)其值取1，i為跨接邊時(shí)其值取2，當(dāng)兩者都不是時(shí)其值取0。

(5)總?cè)哂喽龋涸撝翟降捅硎揪W(wǎng)絡(luò)資源利用率越高，則可用較少空閑容量來(lái)保護(hù)全網(wǎng)工作容量。

(6)P-Cycle平均保護(hù)效能：?jiǎn)蝹€(gè)P-Cycle保護(hù)能力的象征，為整個(gè)網(wǎng)絡(luò)配置的所有P-Cycle可保護(hù)的工作容量與圈個(gè)數(shù)的比值，該值越高則網(wǎng)絡(luò)資源利用率越高[12]。

2 RVPA算法流程

算法輸入：G=(N，L)、Wi、ui、M。

算法輸出：各項(xiàng)性能指標(biāo)，如算法計(jì)算時(shí)間、PC值、P-Cycle個(gè)數(shù)、冗余度R(p)、總?cè)哂喽?、P-Cycle平均保護(hù)效能，以及算法P-Cycle構(gòu)造結(jié)果。

算法具體步驟如下：

步驟1為G配置業(yè)務(wù)請(qǐng)求，分配工作容量，初始化ui=Wi(i∈L)，m=1。

步驟2在G中尋找承載最大工作容量的鏈路L1，其兩個(gè)端點(diǎn)分別為l1、l2，刪除L1，分別以l1、l2為起始節(jié)點(diǎn)、目標(biāo)節(jié)點(diǎn)，運(yùn)行Dijkstra算法尋找最短路徑L2，將L1與L2首尾相連構(gòu)造最小候選圈C1；刪除L2，重復(fù)上述尋找最短路徑過程，若可再次找到最短路徑L3，則將L3與L1首尾相連構(gòu)造最小候選圈C2，且L3與L2首尾相連構(gòu)造最小候選圈C3，可得L1為C3跨接鏈路；若沒找到最短路徑L3，則設(shè)L3=L1；將3個(gè)候選最小圈中冗余度最小的圈記為Cmin，其最小冗余度值記為Rmin。

步驟3若此時(shí)網(wǎng)絡(luò)的未保護(hù)鏈路比率UPL滿足UPL

步驟4以所有圈上邊為基礎(chǔ)依次進(jìn)行圈擴(kuò)展，即刪除圈上邊i(i≥1)，運(yùn)行Dijkstra算法找到與該邊鏈路分離的最短路徑Di，此時(shí)Di作為圈上邊與原有圈構(gòu)成了以第i條鏈路為跨接邊的新候選圈，計(jì)算該新候選圈的未保護(hù)工作容量的方差并存為V(c+i)、冗余度存為R(c+i)，i=i+1進(jìn)行循環(huán)，直至i不能再增加，即所有圈上邊都擴(kuò)展后轉(zhuǎn)至步驟5。

步驟5依次分別比較步驟4中儲(chǔ)存的R(c+i)、V(c+i)與R1、V1的大小，若滿足V(c+i)≤V1且R(c+i)≤R1圈擴(kuò)展條件，則V1=V(c+i)、R1=R(c+i)，并找到滿足上述擴(kuò)展條件的最優(yōu)圈，然后儲(chǔ)存為Cnew并釋放其他擴(kuò)展候選圈；若此時(shí)網(wǎng)絡(luò)的UPL滿足UPL

步驟6更新G工作容量矩陣(工作容量為0的鏈路不更新)，即圈上鏈路工作容量減1、跨接鏈路工作容量減2，直到所有的工作容量都得到保護(hù)時(shí)算法停止運(yùn)行，否則轉(zhuǎn)至步驟2，進(jìn)行算法迭代，更新m=m+1。

算法流程如圖2所示。RVPA算法對(duì)于圈長(zhǎng)度的約束力度通過參數(shù)M(0.1

圖2 RVPA算法流程

3 RVPA算法仿真結(jié)果與分析

3.1 仿真環(huán)境配置

COST239含11個(gè)節(jié)點(diǎn)、26條邊，節(jié)點(diǎn)平均度為4.73，為網(wǎng)狀網(wǎng)絡(luò)拓?fù)淠Ｐ?，生存性技術(shù)P-Cycle適于保護(hù)網(wǎng)狀光網(wǎng)絡(luò)，如圖3所示，本文選用泛歐COST239[13]為仿真網(wǎng)絡(luò)拓?fù)洌瑘D3(a)節(jié)點(diǎn)名稱與具體地理位置相對(duì)應(yīng)[14]，圖3(b)鏈路權(quán)重表示該鏈路上的工作容量(單位為波長(zhǎng)的個(gè)數(shù))，假設(shè)在仿真過程中，已知COST239工作容量矩陣，且其節(jié)點(diǎn)可全波長(zhǎng)變換，業(yè)務(wù)流向雙向?qū)ΨQ。

圖3 仿真網(wǎng)絡(luò)拓?fù)?/p>

3.2 仿真結(jié)果

圖4～圖9顯示了M從0.1開始以步長(zhǎng)0.1為單位增長(zhǎng)到0.9時(shí)，兩算法各性能指標(biāo)的取值情況。

由圖 4可知，兩種算法所需P-Cycle個(gè)數(shù)在M取值依次增長(zhǎng)時(shí)，均整體呈上升趨勢(shì)，且POCA算法增長(zhǎng)率較大，由M=0.1時(shí)的取值6增長(zhǎng)到最大值20，而RVPA算法M取0.1～0.6時(shí)的恒定值7增長(zhǎng)到最大值15，所需P-Cycle個(gè)數(shù)降低33.33%。M=0.5時(shí)POCA、RVPA算法所需P-Cycle個(gè)數(shù)分別為9、7，PVPA算法比POCA算法所示P-Cycle個(gè)數(shù)低22.22%，由此可見，RVPA算法性能比POCA算法性能更加穩(wěn)定，性能更優(yōu)。

如圖5可知，當(dāng)M取值依次增長(zhǎng)時(shí)，保護(hù)全網(wǎng)相同業(yè)務(wù)請(qǐng)求需要的圈數(shù)量與圈平均長(zhǎng)度整體相反。當(dāng)M取0.5時(shí)，圈平均長(zhǎng)度取值適中，滿足要求。

圖5 不同M取值下P-Cycle平均長(zhǎng)度

由圖 6可知，兩種算法的PC值在M取值依次增長(zhǎng)時(shí)，RVPA算法要整體高于POCA算法取值；且在M=0.5時(shí)，POCA、RVPA算法的PC取值分別為1.69、2.10，RVPA算法取值大，比POCA算法提高24.26%。由此可見，RVPA算法性能更優(yōu)。

圖6 不同M取值下PC值

圖7 不同M取值下的總?cè)哂喽?/p>

由圖 7可知，兩種算法的總?cè)哂喽仍贛取值依次增長(zhǎng)時(shí)，RVPA要整體小于POCA算法取值，但兩者取值均呈整體上升趨勢(shì)，且M=0.5時(shí)，POCA算法取值為7.2，而RVPA算法取最小值5.6，PVPA算法比POCA算法降低22.22%。由此可見，RVPA算法性能更優(yōu)。

運(yùn)行環(huán)境不同則算法耗時(shí)也不同，算法運(yùn)行耗時(shí)呈隨機(jī)分布，如圖8所示。由圖8可知，RVPA算法耗時(shí)在M取0.2、0.5時(shí)少于POCA算法耗時(shí)；且當(dāng)M=0.5時(shí)，RVPA、POCA算法耗時(shí)分別為0.070 931、0.089 097 s，PVPA算法比POCA算法耗時(shí)降低20.39%。

圖8 不同M取值下的算法耗時(shí)

新增方差運(yùn)算會(huì)增加算法復(fù)雜度，延長(zhǎng)算法耗時(shí)，但在保護(hù)相同業(yè)務(wù)請(qǐng)求時(shí)，RVPA算法所需P-Cycle個(gè)數(shù)少于POCA算法，而且單個(gè)P-Cycle上節(jié)點(diǎn)數(shù)較少，降低了算法整體耗時(shí)。

圖9 不同M取值下的平均保護(hù)效能

由圖 9可知，兩算法的平均保護(hù)效能在M取值依次增長(zhǎng)時(shí)，均整體呈下降趨勢(shì)，且RVPA算法取值由M取0.1～0.6時(shí)的最大值35下降，但其整體取值與最小取值大于POCA算法的整體取值與最小值。M=0.5時(shí)，POCA、RVPA算法平均保護(hù)效能分別取值27、最大值35，RVPA算法比POCA算法提高29.63%，RVPA算法性能更優(yōu)。

3.3 仿真結(jié)果分析

表4中顯示了在M=0.5時(shí)RVPA算法的各指標(biāo)取值與不同M取值下各指標(biāo)的平均取值對(duì)比情況。除P-Cycle平均長(zhǎng)度外，其他性能指標(biāo)均是PVPA優(yōu)于POCA，這是因?yàn)镸取較小值時(shí)算法的約束力度較高，所以構(gòu)造出的圈上節(jié)點(diǎn)數(shù)量較少，拉低了平均值，但圈數(shù)量偏多。

表4 RVPA算法性能匯總

M=0.5對(duì)應(yīng)算法最優(yōu)性能，此時(shí)兩算法的圈構(gòu)造結(jié)果見表5。

表5 M=0.5時(shí)兩算法圈構(gòu)造結(jié)果

由表 5可知，當(dāng)M取0.5時(shí)，POCA、RVPA算法在保護(hù)相同的業(yè)務(wù)請(qǐng)求時(shí)，所需要P-Cycle個(gè)數(shù)分別為9、7，而且后者的P-Cycle構(gòu)造結(jié)果平均長(zhǎng)度較小，整體性能更優(yōu)。圖10是以表5中第7個(gè)圈為例在COST239網(wǎng)絡(luò)拓?fù)渲械臉?gòu)造結(jié)果。

圖10 P圈構(gòu)造結(jié)果說明示例

4 結(jié)論

本文提出RVPA算法，通過求取擴(kuò)展候選圈上未保護(hù)工作容量的方差，在圈擴(kuò)展時(shí)以所有候選圈上未保護(hù)工作容量的方差、冗余度兩個(gè)指標(biāo)為比較標(biāo)準(zhǔn)，當(dāng)兩者同時(shí)滿足圈擴(kuò)展條件時(shí)，選該候選圈為本次擴(kuò)展的最終圈，與POCA算法相比有效限制了保護(hù)全網(wǎng)工作容量所需圈個(gè)數(shù)。仿真結(jié)果表明，在COST239網(wǎng)絡(luò)拓?fù)渲?，?dāng)POCA、RVPA算法保護(hù)相同業(yè)務(wù)請(qǐng)求時(shí)，后者在有效降低保護(hù)全網(wǎng)所需圈個(gè)數(shù)的同時(shí)，通過參數(shù)M限制每個(gè)P-Cycle的節(jié)點(diǎn)個(gè)數(shù)，使圈個(gè)數(shù)與圈長(zhǎng)度得到有效均衡，降低全網(wǎng)總?cè)哂喽?，提高P-Cycle平均保護(hù)效能、PC，最終分析可得M=0.5時(shí)可達(dá)到最優(yōu)仿真效果。M取0.5時(shí)POCA、RVPA算法的各性能指標(biāo)取值見表6。由表6可知，RVPA算法各項(xiàng)性能指標(biāo)優(yōu)于POCA算法。

表6 M取0.5時(shí)兩種算法性能指標(biāo)取值

由表6可知，POCA、RVPA算法同一個(gè)網(wǎng)絡(luò)中保護(hù)相同的業(yè)務(wù)請(qǐng)求時(shí)，在M=0.5時(shí)，PVPA算法比POCA算法的總?cè)哂喽冉档?2.22%，平均保護(hù)效能提高29.63%，PC取值提高24.26%，算法耗時(shí)降低20.39%，P-Cycle個(gè)數(shù)降低22.22%。綜上可得，RVPA算法性能整體優(yōu)于POCA算法性能，且M=0.5時(shí)RVPA算法保護(hù)效果最優(yōu)。預(yù)計(jì)到2030年，鐵路光傳送網(wǎng)的網(wǎng)絡(luò)結(jié)構(gòu)將朝著網(wǎng)狀網(wǎng)格局發(fā)展，鐵路建設(shè)將會(huì)基本形成內(nèi)與外互聯(lián)互通、縣與域基本覆蓋、區(qū)際之間多路暢通、地市之間快速通達(dá)、省會(huì)之間高鐵連通的局面[15]，故本文提出的適用于網(wǎng)狀光傳送網(wǎng)的基于冗余度和方差的P-Cycle圈構(gòu)造算法RVPA，隨著P-Cycle保護(hù)技術(shù)在鐵路光傳送網(wǎng)中的大力推廣，將對(duì)鐵路光傳送網(wǎng)保護(hù)技術(shù)有一定的借鑒意義。