基于冗余度和方差的P-Cycle圈構造算法的研究

孫 強，李德莉，任 葉

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

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

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

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

1 RVPA算法

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

1.1 RVPA算法應用舉例

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

圖1中的網絡拓撲包含7個節點、11條鏈路，鏈路權重代表該鏈路承載的業務請求數量，以該網絡拓撲為例說明POCA、RVPA算法的保護過程。

圖1 RVPA算法與POCA算法

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

表1 最小圈構造

步驟2設定參數M=0.5，得到此時全網UPL為0.85，不滿足UPL

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

表2 最小圈C3擴展表

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

1.2 RVPA算法參數

算法參數說明見表3。

表3 算法參數說明

1.3 RVPA算法性能指標

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

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

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

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

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

( 1 )

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

(5)總冗余度：該值越低表示網絡資源利用率越高，則可用較少空閑容量來保護全網工作容量。

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

2 RVPA算法流程

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

算法輸出：各項性能指標，如算法計算時間、PC值、P-Cycle個數、冗余度R(p)、總冗余度、P-Cycle平均保護效能，以及算法P-Cycle構造結果。

算法具體步驟如下：

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

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

步驟3若此時網絡的未保護鏈路比率UPL滿足UPL

步驟4以所有圈上邊為基礎依次進行圈擴展，即刪除圈上邊i(i≥1)，運行Dijkstra算法找到與該邊鏈路分離的最短路徑Di，此時Di作為圈上邊與原有圈構成了以第i條鏈路為跨接邊的新候選圈，計算該新候選圈的未保護工作容量的方差并存為V(c+i)、冗余度存為R(c+i)，i=i+1進行循環，直至i不能再增加，即所有圈上邊都擴展后轉至步驟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)，并找到滿足上述擴展條件的最優圈，然后儲存為Cnew并釋放其他擴展候選圈；若此時網絡的UPL滿足UPL

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

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

圖2 RVPA算法流程

3 RVPA算法仿真結果與分析

3.1 仿真環境配置

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

圖3 仿真網絡拓撲

3.2 仿真結果

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

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

如圖5可知，當M取值依次增長時，保護全網相同業務請求需要的圈數量與圈平均長度整體相反。當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算法性能更優。

圖6 不同M取值下PC值

圖7 不同M取值下的總冗余度

由圖 7可知，兩種算法的總冗余度在M取值依次增長時，RVPA要整體小于POCA算法取值，但兩者取值均呈整體上升趨勢，且M=0.5時，POCA算法取值為7.2，而RVPA算法取最小值5.6，PVPA算法比POCA算法降低22.22%。由此可見，RVPA算法性能更優。

運行環境不同則算法耗時也不同，算法運行耗時呈隨機分布，如圖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取值下的算法耗時

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

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

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

3.3 仿真結果分析

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

表4 RVPA算法性能匯總

M=0.5對應算法最優性能，此時兩算法的圈構造結果見表5。

表5 M=0.5時兩算法圈構造結果

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

圖10 P圈構造結果說明示例

4 結論

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

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

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