基於多面體結構的光網絡多故障保護方法
2023-09-21 05:29:20
基於多面體結構的光網絡多故障保護方法
【專利摘要】本發明公開了一種基於多面體結構的光網絡多故障保護方法，該方法包括：根據所述光網絡的物理拓撲和預計將出現並發故障的鏈路的數目，構建所述多面體保護結構；以及在所構建的多面體保護結構的每一條鏈路上分配保護資源。通過上述技術方案，根據光網絡的物理拓撲和預計將出現並發故障的鏈路的數目，構建所述多面體保護結構並利用所構建的多面體保護結構來對光網絡進行保護，能夠實現對多故障光網絡進行有效地保護。
【專利說明】基於多面體結構的光網絡多故障保護方法
【技術領域】
[0001]本發明涉及通信領域，具體地，涉及一種基於多面體結構的光網絡多故障保護方法。
【背景技術】
[0002]在光通信網絡中，為了保證光信號遠距離、低損耗的傳輸，整條光纖鏈路必須滿足非常苛刻且敏感的物理條件，任何細微的幾何形變或者輕微汙染都會造成信號的巨大衰減，甚至中斷通信。隨著超大容量光網絡規模的擴大和傳輸速率的提高，使得網絡遭受自然災害破壞、人工操作失誤和軟體配置錯誤等多重故障的概率增加，這些將降低光網絡帶寬提供的可靠性，增加保護恢復資源配置冗餘和調度的複雜性。
[0003]預置圈(P圈或P-cycle)是I D.Grover教授在1998年提出的概念，是一種基於環結構的網絡保護方案。P-cycle是利用空閒資源預先設置的環形通道來實現網狀網絡中的快速保護。它區別於其他如增強環法、單向環雙重覆蓋法等基於環的保護方案的最大特點就是在允許工作通道任意選擇路由的條件下，同時可對圈上和跨接區段上的鏈路故障提供保護。在單故障的情況下，P-cycle中的哈密爾頓圈達到最優的資源利用率。
[0004]為了實現多條並發鏈路故障的保護，已有文獻提出了以p-cycle為基礎的保護方案。這樣的保護方案中，對於物理拓撲中每條鏈路，必須使得其處在多條物理路徑不相交的圈(cycle)中，以使在多故障的情況下至少有一個cycle是沒有受到故障的影響。但是根據理論證明和實際應用，對於多條鏈路並發故障情況下，p-cycle組合併不能達到最優的保護資源利用。
[0005]針對多條並發鏈路故障的光網絡保護問題，現有技術中尚無良好的解決方案。
【發明內容】
[0006]本發明的目的是提供一種光通信網絡中使用的保護方法以至少解決現有技術中存在的上述問題。
[0007]為了實現上述目的，本發明提供一種基於多面體結構的光網絡多故障保護方法，該方法包括:根據所述光網絡的物理拓撲和預計將出現並發故障的鏈路的數目，構建所述多面體保護結構；以及在所構建的多面體保護結構的每一條鏈路上分配保護資源。
[0008]進一步地，所述構建所述多面體保護結構的步驟包括:確定所述光網絡的物理拓撲中的跨接鏈路；以及從所述光網絡的物理拓撲中去除所確定的跨接鏈路，由剩餘的鏈路和節點組成所構建的多面體保護結構。
[0009]進一步地，所述確定所述光網絡的物理拓撲中的跨接鏈路包括:對於所述光網絡的物理拓撲的每一條鏈路，判斷鏈路兩端的節點是否都滿足條件:度大於m+1，其中m為所述預計將出現並發故障的鏈路的數目；以及將滿足所述條件的鏈路確定為所述跨接鏈路。
[0010]進一步地，所述在所構建的多面體保護結構的每一條鏈路上分配保護資源的步驟包括:根據所構建的多面體保護結構中具有最大工作資源的鏈路的工作資源數量以及具有最大工作資源的跨接鏈路的工作資源數量來分配所述保護資源。
[0011]進一步地，所述在所構建的多面體保護結構的每一條鏈路上分配保護資源的步驟包括:確定第一資源值，其中該第一資源值為所述具有最大工作資源的鏈路的工作資源數量乘以m;確定第二資源值，其中該第二資源值為所述具有最大工作資源的跨接鏈路的工作資源數量乘以m除以(m+1);比較所述第一資源值和所述第二資源值；以及根據比較結果，以所述第一資源值和所述第二資源值中的較大者來分配所述保護資源到所構建的多面體保護結構的每一條鏈路。
[0012]進一步地，在確定所述光網絡的物理拓撲中的跨接鏈路之前，該方法還包括:確定所述光網絡的物理拓撲中存在哈密爾頓圈，在不存在所述哈密爾頓圈的情況下，確定所述光網絡的物理拓撲中的跨接鏈路。
[0013]通過上述技術方案，根據光網絡的物理拓撲和預計將出現並發故障的鏈路的數目，構建所述多面體保護結構並利用所構建的多面體保護結構來對光網絡進行保護，能夠實現對多故障光網絡進行有效地保護；在所構建的多面體保護結構上分配保護資源，能夠使網絡具有較低的冗餘度，提高了資源的利用率，並且能夠使光網絡在50ms以內進行保護倒換。
[0014]本發明的其他特徵和優點將在隨後的【具體實施方式】部分予以詳細說明。
【專利附圖】
【附圖說明】
[0015]附圖是用來提供對本發明的進一步理解，並且構成說明書的一部分，與下面的【具體實施方式】一起用於解釋本發明，但並不構成對本發明的限制。在附圖中:
[0016]圖1是根據本發明實施方式的一種基於多面體結構的光網絡多故障保護方法的流程圖；
[0017]圖2是根據本發明優選實施方式的一種基於多面體結構的光網絡多故障保護方法的流程圖；
[0018]圖3是根據本發明優選實施方式的一種基於多面體結構的光網絡多故障保護方法的流程圖；
[0019]圖4是示例的光網絡拓撲示意圖；
[0020]圖5是本發明的方法可以實施的示例的C0ST239光網絡拓撲示意圖；
[0021]圖6是示例的網絡拓撲結構示意圖；以及
[0022]圖7是在預計出現並發故障的數目為2的情況下的保護倒換示意圖。
【具體實施方式】
[0023]以下結合附圖對本發明的【具體實施方式】進行詳細說明。應當理解的是，此處所描述的【具體實施方式】僅用於說明和解釋本發明，並不用於限制本發明。
[0024]圖1是根據本發明實施方式的一種基於多面體結構的光網絡多故障保護方法的流程圖。如圖1所示，本發明提供的一種基於多面體結構的光網絡多故障保護方法，包括:根據光網絡的物理拓撲和預計將出現並發故障的鏈路的數目，構建多面體保護結構(SlO);以及在所構建的多面體保護結構的每一條鏈路上分配保護資源(S15)。其中，光網絡的物理拓撲可以表示光網絡中的所有鏈路和節點；預計將出現並發故障的鏈路數目可以根據需要例如網絡規劃要求進行設置。需要說明的是，這裡的多面體保護結構可以包括完整的多面體保護結構(例如，超立方保護結構)，還可以包括次或次優的多面體保護結構(例如，不規則的保護結構)。
[0025]通過上述技術方案，根據光網絡的物理拓撲和預計將出現並發故障的鏈路的數目，構建多面體保護結構並利用所構建的多面體保護結構來對光網絡進行保護，能夠實現對多故障光網絡進行有效地保護；在所構建的多面體保護結構上分配保護資源，能夠使網絡具有較低的冗餘度，提高了資源的利用率，並且能夠使光網絡在50ms以內進行保護倒換，滿足光網絡的使用要求。
[0026]圖2是根據本發明優選實施方式的一種基於多面體結構的光網絡多故障保護方法的流程圖。如圖2所示，優選地，構建多面體保護結構的步驟(SlO)可以包括:確定光網絡的物理拓撲中的跨接鏈路(SI I);以及從光網絡的物理拓撲中去除所確定的跨接鏈路，由剩餘的鏈路和節點組成所構建的多面體保護結構(S12)。下面結合圖4對跨接鏈路進行說明。圖4是示例的光網絡拓撲示意圖。如圖4所示網路拓撲，在雙故障情況下，其中鏈路(a，b)和(c)都可以為跨接鏈路，但是只能有鏈路(a，b)或(c)中的一者為跨接鏈路，不能同時為跨接鏈路。當跨接鏈路(鏈路(a，b)或(c))確定以後，該光網絡拓撲中剩餘的鏈路就是多面體保護結構上的鏈路，這些鏈路和每條鏈路兩端的節點一起組成所構建的多面體保護結構。現有技術中有多種確定跨接鏈路的方法，以下結合圖3對本發明的一個優選的實施方式進行說明。
[0027]圖3是根據本發明優選實施方式的一種基於多面體結構的光網絡多故障保護方法的流程圖。如圖3所示，優選地，確定光網絡的物理拓撲中的跨接鏈路(Sll)包括:對於光網絡的物理拓撲的每一條鏈路，判斷鏈路兩端的節點是否都滿足條件:度大於m+1，其中m為預計將出現並發故障的鏈路的數目(S13);以及將滿足條件的鏈路確定為跨接鏈路(S14)。
[0028]圖5是本發明的方法可以實施的示例的C0ST239光網絡拓撲示意圖。結合圖5對圖3所示的方法做進一步舉例說明，這裡假設:m=3，即網絡中並發出現的鏈路故障數目為3，並且在當前光網絡的物理鏈路中隨機地出現；光網絡中每條鏈路的資源以波長為單位，並且不需要考慮波長連續性限制。如圖5中(a)所示，C0ST239光網絡物理拓撲中，包括11個物理鏈路節點和25條物理鏈路。從圖5中可以看出，節點的度(或自由度)大於4的節點為:節點2，3，4，6，9，10。因此，可以確定鏈路2-10，3-4和6_9為跨接鏈路，從而所構建的多面體保護結構如圖5中(b)所示。
[0029]在一種優選的實施方式中，構建多面體保護結構的步驟還可以包括:確定光網絡的物理拓撲中存在哈密爾頓圈(Hamilton-Cycle);以及在不存在哈密爾頓圈的情況下，確定光網絡的物理拓撲中的跨接鏈路。判斷在光網絡物理拓撲圖中存在哈密爾頓圈，即在給定的光網絡物理拓撲中，能不能找到這樣的路徑:從某一節點出發不重複地經過所有的節點(不必通過物理拓撲中每一條邊(或鏈路))，最後又回到初始節點。對於在光網絡物理拓撲存在哈密爾頓圈的情況下，多面體保護結構的構建方法已記載在 申請人:2011年11月2日提交的中國專利申請(申請號:201110341566.7)中，這裡將其引用作為參考。對於光網絡物理拓撲不存在哈密爾頓圈的情況，可以根據光網絡的物理拓撲和預計將出現並發故障的鏈路的數目，構建多面體保護結構。需要說明的是，首先判斷或確定光網絡拓撲中是否存在哈密爾頓圈，目的是對網絡拓撲的屬性進行判斷，從而可以判斷網絡可以構建的保護結構的類型(例如，超立方保護結構或不規則的保護結構)，進而根據判斷出的類型來構建保護結構。但是，是否事先知道網絡可以構建的保護結構的類型並不會影響根據本發明的方法來構建多面體保護結構。作為舉例，可以採用如下的貪婪算法來構建多面體保護結構而不需要考慮光網絡的物理拓撲中是否存在哈密爾頓圈。作為舉例的貪婪算法如下:
[0030]( I) / "/ _Pc= (j{V, /:)
[0031](2) for e±j ^ E (i ^ Vj j ^ Vj i ^ j) each do
[0032](3) if (Degree (i) > m+l&& Degree (j) > m+1) do
[0033](4) Poly—P = Poly—P/e。.[0034](5) end if
[0035](6) end for
[0036](7) return Poly—P
[0037]其中G(V，E)為所述光網絡的物理拓撲，V為所述光網絡的物理拓撲中節點的集合，E為所述光網絡的物理拓撲中鏈路的集合，Poly_P為所述貪婪算法構建的所述多面體保護結構，Degree(i)為節點i的度，m為所述預計將出現並發故障的鏈路的數目。
[0038]在一種實施方式中，在所構建的多面體保護結構的每一條鏈路上分配保護資源的步驟(S15)可以包括:根據所構建的多面體保護結構中具有最大工作資源的鏈路的工作資源數量以及具有最大工作資源的跨接鏈路的工作資源數量來分配保護資源。在一種實施方式中，在所構建的多面體保護結構的每一條鏈路上分配保護資源的步驟可以包括:確定第一資源值，其中該第一資源值 為具有最大工作資源的鏈路的工作資源數量乘以m;確定第二資源值，其中該第二資源值為具有最大工作資源的跨接鏈路的工作資源數量乘以m除以(m+1);比較第一資源值和第二資源值；以及根據比較結果，以第一資源值和第二資源值中的較大者來分配保護資源到所構建的多面體保護結構的每一條鏈路。
[0039]以下結合附圖對發明提供的基於多面體結構的光網絡多故障保護方法的優勢和特點進一步說明。其中，進行保護資源的分配時，以保護結構上工作容量最大的鏈路為基準，對於保護結構上的工作鏈路分配保護資源，鏈路資源以波長為最小的粒度；對於保護結構上的跨接鏈路，共享保護結構上的保護資源。圖6是示例的網絡拓撲結構示意圖。其中，圖6中(a)所示的光網絡物理拓撲主體為正六面體。根據前述的內容，可以得到，在雙故障情況下，根據現有技術的預製圈方法構建的六個P-cycle的保護結構如圖6中(b)所示，其中，每個P-cycle的每一條鏈路上分配一個波長的保護波長。而根據本發明基於多面體結構的光網絡多故障保護方法構建的正六面體如圖6中(c)所示。其中，假設正六面體上每條鏈路的工作波長數目為I個波長，在雙並發故障的情況下，作為舉例，在保護結構上分配資源算法如下:
[0040](l)Poly_P = G(Vp, Ep)
[0041](2) fOreij e Ep(i e Vp, j e Vp, i ^ j) each do
[0042](3) find the maximum working wavelengths number MAX_P
[0043](4) end for
[0044](5 ) for 在 A & &ey e 即 G vp, J € Vp, i 本 j) each do
[0045](6) find the maximum working wavelengths number MAX_ff[0046](7) end for
[0047](8) MAX=max(m*MAX_P，m*MAX_W/(m+1))
[0048](9) Assign MAX wavelengths in the Poly_P
[0049]其中保護結構為G (Vp, Ep)，Vp為保護結構節點集合，Ep為保護結構鏈路集合，MAX為對保護結構上的每一條鏈路需要分配的波長數目(本例中，得到MAX=2)。
[0050]根據網絡冗餘度的計算公式:冗餘度=(網絡保護資源的總量)/ (網絡工作資源的總量)，可以得到在使用圖6中(b)所示的六個p-cycle保護結構的情況下網絡冗餘度為:(4*6)/(12+0) =2 ;而在使用圖6中(c)所示的正六面體保護結構的情況下網絡冗餘度為:(12*2)/(12+2*3) =4/3。根據最優的冗餘度公式:m/ (d_m)，其中，m為故障鏈路數目(本例中，m=2)，d為網絡節點的平均度數(本例中，d=7/2)，可以得到圖6中(a)示出的網路的最優的冗餘度為4/3。因此，使用根據本發明的基於多面體結構的光網絡多故障保護方法構建的多面體保護結構實現了最優的網絡冗餘度和最好的保護資源利用效率。
[0051]圖7是在預計出現並發故障的數目為2的情況下的保護倒換示意圖。如圖7所示，假設對於任意一個正六面體保護結構，一條鏈路上的業務可以組播到正六面體保護結構任意一條鏈路中去。根據以上得到的保護結構和分配的保護資源，可以構成兩個正六面體的保護結構，其中，每個結構上的每一條鏈路都有一個保護波長。對於網絡中隨機出現的雙鏈路故障，可以如圖7中(b)所示，其中一個故障鏈路倒換到一個正六面體保護結構；如圖7(c)所示，另外一個故障鏈路倒換到另一個正六面體保護結構。從而實現對光網絡中並發多故障的保護。
[0052]本發明實施例所述的基於多面體結構的光網絡多故障保護方法，將多面體結構和光網絡多故障保護方法相結合，通過尋找最優的保護結構，實現保護資源的冗餘度最低，最優的利用了光網絡中空閒帶寬資源並能夠達到50ms的光網絡恢復速度。
[0053]以上結合附圖詳細描述了本發明的優選實施方式，但是，本發明並不限於上述實施方式中的具體細節，在本發明的技術構思範圍內，可以對本發明的技術方案進行多種簡單變型，這些簡單變型均屬於本發明的保護範圍。
[0054]另外需要說明的是，在上述【具體實施方式】中所描述的各個具體技術特徵，在不矛盾的情況下，可以通過任何合適的方式進行組合。為了避免不必要的重複，本發明對各種可能的組合方式不再另行說明。
[0055]此外，本發明的各種不同的實施方式之間也可以進行任意組合，只要其不違背本發明的思想，其同樣應當視為本發明所公開的內容。
【權利要求】
1.一種基於多面體結構的光網絡多故障保護方法，該方法包括: 根據所述光網絡的物理拓撲和預計將出現並發故障的鏈路的數目，構建所述多面體保護結構；以及 在所構建的多面體保護結構的每一條鏈路上分配保護資源。
2.根據權利要求1所述的光網絡多故障保護方法，其特徵在於，所述構建所述多面體保護結構的步驟包括: 確定所述光網絡的物理拓撲中的跨接鏈路；以及 從所述光網絡的物理拓撲中去除所確定的跨接鏈路，由剩餘的鏈路和節點組成所構建的多面體保護結構。
3.根據權利要求2所述的光網絡多故障保護方法，其特徵在於，所述確定所述光網絡的物理拓撲中的跨接鏈路包括: 對於所述光網絡的物理拓撲的每一條鏈路，判斷鏈路兩端的節點是否都滿足條件:度大於m+1，其中m為所述預計將出現並發故障的鏈路的數目；以及 將滿足所述條件的鏈路確定為所述跨接鏈路。
4.根據權利要求2或3所述的光網絡多故障保護方法，其特徵在於，所述在所構建的多面體保護結構的每一條鏈路上分配保護資源的步驟包括: 根據所構建的多面體保護結構中具有最大工作資源的鏈路的工作資源數量以及具有最大工作資源的跨接鏈路的工作資源數量來分配所述保護資源。
5.根據權利要求4所述的光網絡多故障保護方法，其特徵在於，所述在所構建的多面體保護結構的每一條鏈路上分配保護資源的步驟包括: 確定第一資源值，其中該第一資源值為所述具有最大工作資源的鏈路的工作資源數量乘以m ； 確定第二資源值，其中該第二資源值為所述具有最大工作資源的跨接鏈路的工作資源數量乘以m除以(m+1)； 比較所述第一資源值和所述第二資源值；以及 根據比較結果，以所述第一資源值和所述第二資源值中的較大者來分配所述保護資源到所構建的多面體保護結構的每一條鏈路。
6.根據權利要求2所述的光網絡多故障保護方法，其特徵在於，在確定所述光網絡的物理拓撲中的跨接鏈路之前，該方法還包括:確定所述光網絡的物理拓撲中存在哈密爾頓圈， 在不存在所述哈密爾頓圈的情況下，確定所述光網絡的物理拓撲中的跨接鏈路。
【文檔編號】H04L12/24GK103580746SQ201210283059
【公開日】2014年2月12日 申請日期:2012年8月9日 優先權日:2012年8月9日
【發明者】李新, 黃善國, 趙永利, 胡楠, 張 傑, 顧畹儀 申請人:北京郵電大學