基于冗余度和方差的P-Cycle圈構(gòu)造算法的研究

孫 強，李德莉，任 葉

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

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

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

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

1 RVPA算法

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

1.1 RVPA算法應用舉例

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

圖1中的網(wǎng)絡拓撲包含7個節(jié)點、11條鏈路，鏈路權(quán)重代表該鏈路承載的業(yè)務請求數(shù)量，以該網(wǎng)絡拓撲為例說明POCA、RVPA算法的保護過程。

圖1 RVPA算法與POCA算法

步驟1以3-6鏈路為基礎構(gòu)造最小圈，因為該鏈路上未保護工作容量最大，具體算法構(gòu)造過程見表1。

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

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

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

表2 最小圈C3擴展表

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

1.2 RVPA算法參數(shù)

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

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

1.3 RVPA算法性能指標

算法性能評價指標說明如下。

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

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

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

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

( 1 )

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

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

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

2 RVPA算法流程

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

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

算法具體步驟如下：

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

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

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

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

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

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

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

圖2 RVPA算法流程

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

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

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

圖3 仿真網(wǎng)絡拓撲

3.2 仿真結(jié)果

圖4～圖9顯示了M從0.1開始以步長0.1為單位增長到0.9時，兩算法各性能指標的取值情況。

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

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

圖5 不同M取值下P-Cycle平均長度

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

圖6 不同M取值下PC值

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

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

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

圖8 不同M取值下的算法耗時

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

圖9 不同M取值下的平均保護效能

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

3.3 仿真結(jié)果分析

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

表4 RVPA算法性能匯總

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

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

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

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

4 結(jié)論

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

表6 M取0.5時兩種算法性能指標取值

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