薛文革，陳莉
(上海電信技術研究院，上海200122)
摘要：生存性是光傳送網絡中亟待解決的問題.文章基于環網的優良保護倒換能力提出了環覆蓋保護策略，給出了選擇環覆蓋的控制流程，建立了以保護容量需求作為優化目標的環覆蓋優化設計模型.
關鍵詞：生存性；環覆蓋；整型線性規劃；網狀網
光傳送網絡的拓撲結構一直是網絡設計人員所關注的問題[1].盡管當前可用的拓撲種類較多，但人們往往比較喜歡網狀結構，這是因為網狀光傳送網絡具有高度連通性，所以無論是在正常狀態還是故障狀態下它都能有效地使用網絡資源，從而使得網絡容量需求達到最小，但其結構復雜,使得網絡資源的控制和管理變得復雜.當發生故障時除了需要硬件交換器以外，還必須使用大量的軟件處理(恢復消息的交換和處理、網絡配置數據庫的一致性維護以及波長信道分配策略等)才能夠實現受損業務的恢復，導致故障恢復時間較長，可靠性差。
環形拓撲是所有通信網絡都支持的一種結構，在目前的計算機網絡和電信網絡等領域中正運行著大量的環形網絡；它也是光傳送網絡的一種主要拓撲結構，盡管在容量效率方面比不上網狀結構，但它具有一些網狀結構無法達到的優良特征，尤其當發生網絡故障時，環形網絡通過硬件交換器可以輕松地實現網絡保護，倒換速度快，可靠性高.正是基于這一優良特性,我們提出了環覆蓋保護方法.
1 分層互連環
網絡規模是影響環形網絡性能的一個關鍵因素，在環形網絡中，隨著節點數的增加，網絡容量需求以及業務節點間的路徑長度將明顯增加，這限制了單個環形網絡能夠容納的節點數目.為了在大規模網絡中利用環形網絡的優點，比較實際的做法就是對網絡節點分組，然后為每個分組建立一個環形網絡，且這些環形網絡之間通過公共節點相互連接，從而形成具有層次結構的互連環網(Interconnected Ring)；如果每個環都具有生存能力(即屬于自愈環類型)，則稱該互連環是為自愈互連環[2～3].
分層互連環根據網絡規�？梢詣澐殖刹煌燃�，除了最頂層僅包含一個環形網絡之外，其它各層都包括一定數量的環網絡.較高層次的環可以互連多個較低層次的環，它們的連通性是通過層間公共節點(Common Node)，也被稱作互連節點(Interconnecting Node)的橋接作用來保證的，各個環在正常狀態下的操作以及故障狀態下的自動保護交換都是相互獨立的.圖1給出了兩層互連環的典型拓撲結構，其中，(a)為單歸宿(Single homing)型網絡，它包括4個初級環和一個2級環，它能夠處理任何單個鏈路故障.但由于環之間僅通過一個公共節點進行連接，所以它無法處理發生在這些公共節點上的故障，此時的互連環被分割成兩個“孤島”，失去了物理連通性的網絡顯然是不可恢復的.為了解決這個問題，單歸宿型互連環網絡必須在環之間增加一個冗余公共節點，即必須構建雙歸宿(Dualhoming)型互連網才能保證網絡在公共節點有故障時也是可生存的.圖1(b)描述了它的基本結構，圖中的所有初級環都是通過兩個公共節點與2級環進行互連的.
由于分層互連環的各組成環相互獨立，這為網絡消除多個故障的影響提供了可能.只要這些故障分布在不同的環網上，它們總能夠得到妥善的處理；而且在時間上可以重疊，即具有并發處理特征，這將極大地減少網絡保護倒換時間；尤其是在理想情況下，多個故障的處理時間能夠做到與單個故障的處理時間幾乎相等.
2 環覆蓋保護原理
分層互連環是一個比較理想化的解決方案，實際的網絡結構存在很大的任意性，它們難以構建出具有嚴格上、下層次關系的互連環網.為了既適應網絡結構的隨意性，又能夠發揮出環形網絡的優勢，我們在分層互連環的基礎上提出了環覆蓋技術，它能夠有效地滿足上述兩項要求.所謂環覆蓋(Ring Cover)就是一個必須覆蓋網絡所有鏈路的環形網絡集合，它實際上是一種混合(Hybrid)互連環結構，與分層互連環不同的是環覆蓋中的各組成成員(即環形網絡)之間不存在任何關聯.環覆蓋保護就是通過互連的環形網絡來實現對受損業務的保護倒換，它可以將網狀網絡的業務保護時間縮短到與自愈環大體相當的程度.
根據圖論的連通性理論我們可以從網狀光傳送網絡得出如下推論：
推論1：一個給定的網狀結構網絡可以存在多個環覆蓋；
推論2：環覆蓋中的環網絡尺寸大小可以不一樣；
推論3：環覆蓋為了覆蓋所有的網絡鏈路和節點，必定有使用相同網絡鏈路(節點)的環存在；
推論4：網絡路徑總是被環覆蓋中的一個或多個環所容納，它不可能超越環覆蓋的作用范圍；
推論5：單個網絡故障影響的工作業務需要環覆蓋中提供保護的環個數不得超過覆蓋該故障的環個數；
推論6：特定路由上的業務只能由環覆蓋中的單個環提供保護；
根據上面分析可以看出：環覆蓋技術特別適合于縮短網狀光傳送網絡保護倒換時間，這對于大容量的波長傳輸信道尤其重要.因為在相同的倒換時間內，它中斷的業務數據流量要遠遠高于任何傳統傳輸網絡.
3 環形網絡的構建
由于網狀拓撲的網絡結構可以對應多個環形網絡，如何構建并確定合適的環形網絡是實施環覆蓋保護的先決條件.根據業務負載傳輸要求，可以將環形網絡的構建策略分成兩種類型，一種是環內(IntraRing)傳輸策略；另一種就是環間(InterRing)傳輸策略.前者是指網絡上的所有業務傳輸只能局限在某一特定的環形網絡內部，而不能傳輸到其它環形網絡當中；后者則沒有這個限制，它允許業務傳輸路由跨越單個或者多個環形網絡.從理論上講，我們希望在傳輸時業務盡可能跨越數量較少的環形網絡[5].
圖2給出了一個環內傳輸策略范例，它通過R1=1，2，3，4，5，6｝、R2=｛4，5，6，7，8，9｝和R3=｛1，2，3，4，6，7，8，9｝這3個環形網絡來保證網絡的任何業務傳輸都圖2環內傳輸策略可以僅使用一個環即可.例如節點對(1,5)、(4,8)和(1,9)的通信分別使用環形網絡R1、R2和R3，沒有其它選擇；而節點對(1,2)的通信既可以使用R1，也可以使用R3，但最終還是只能確定其中一個.較簡單的處理方法就是選擇較小的環形網絡，但也可以根據網絡的業務分布以及鏈路容量進行選擇，這樣能夠充分利用網絡的信道資源，但控制復雜度較高.
圖3給出了一個環間傳輸策略范例，盡管這種情況下的環形網絡構建沒有限制，但最后的結果必須能夠滿足網絡業務的傳輸要求.例如環形網絡R1=｛1，2，4，5｝、R2=｛2，3，5，6｝、R3=｛4，5，7，8｝和R4=｛5，6，8，9｝就是一個符合需求的結果，所有的網絡業務總是能夠通過它們的組合得到傳輸.例如節點對(1,2)和(5,9)的通信僅需要分別使用單個環形網絡R1和R4即可，而節點對(1,8)間的通信必須使用環形網絡R1和R3的組合才能完成.
環內傳輸策略與環間傳輸策略的根本差異在于最終環形網絡的大小問題.前者可以避免網絡業務跨越多個網絡而帶來的控制復雜性，但它使得某些環形網絡變得非常龐大，甚至會違背環覆蓋的初衷，因為互連環本身就是為了克服較大規模的網絡結構而提出的；盡管第2種策略的復雜度較高，但它的“區域分割”機制能夠真正使用環形網絡的固有優勢，因此，本文僅針對環間傳輸策略進行進一步的分析和研究.
4 環形網絡選擇策略
如果將網狀結構的網絡看作是一個連通性無向圖，那么環形網絡的構建問題可以轉化成無向圖的圈(Cycle)搜索問題[4～6].對于一個強連通圖而言，它往往可以搜索出多個不同的圈，這些圈的大小(可容納在圈上的節點數目)可以相同，也可以不同.基于圖論的圈搜索算法盡管很多，但它的實現一般比較復雜，文獻[6]提出了一種簡單的啟發式圈搜索算法，它可以同時適用于無向圖和有向圖.
從上面分析我們可以得知：一個網狀網絡可能同時包含多個環形網絡，且其數量隨著網絡規模的擴大成比例增長，它們的可能組合將非常龐大.例如在18節點的歐洲RACE2028計劃網絡中，它可以生成1 228個大小不同的環形網絡.如果僅使用其中的12個環形網絡來試構建可行的環覆蓋，將會出現2.8×1031種可能組合.因此，計算并比較所有可能的環覆蓋以便確定其中的最優者將極為復雜，這使它在實際應用中難以實現.
不過，我們可以充分利用已有的環形網絡知識壓縮不必要的環覆蓋，從而降低計算復雜度.影響環形網絡性能特征的核心因素在于它的大小，即較小者在容量使用效率和保護倒換時間等性能優勢方面要明顯超過較大者.理論上已經證明： 在大小為N且業務需求均勻分布的環形網絡中，平均每個業務連接需要經過N2/4(N-1)條鏈路(N為偶數)或者(N+1)/4條鏈路(N為奇數)，這表明對于同等級別的業務而言，大環總是比小環需要更多的容量；同時小環在保護倒換時間上具有一定的優勢.因此，構建環覆蓋的候選環形網絡必須限制在一定的規模范圍以內；這不僅可以發揮小環的性能優勢，而且能有效地解決計算復雜度問題.
經過上述分析可以發現環覆蓋設計問題必須包括業務分布、環形網絡搜索、構建環覆蓋需要的候選環以及環覆蓋優化5個基本功能模塊，圖4給出了環覆蓋設計問題的功能模塊控制流程.
5 環覆蓋保護優化模型
由于環覆蓋保護本身能夠保證最小網絡保護倒換時間需求，因此，它的優化設計主要集中在容量需求領域.在提出環覆蓋保護優化設計模型之前，我們先給出它的適用環境，即必須滿足下列假設條件：
· 只能在單個網絡故障狀態下對業務保證完全恢復，而對于多故障必須要求它們分布在不同的環形網絡當中；
· 網絡鏈路上的波長保護信道只能在環形網絡內部共享，而各環形網絡之間不能共享任何保護波長信道；
· 為了減輕網絡控制管理復雜度，要求經過同一網絡鏈路的環形網絡數量不得超過某一預置的門限值；
· 為了降低網絡節點復雜度，要求方位同一節點的環形網絡數量不得超過某一預置的門限值；
· 為了簡化環覆蓋設計問題，假定網絡節點具有完全波長轉換能力.
符號定義：
· N：網絡節點集合；
· L：網絡光纖鏈路集合；
· D：業務連接集合，即可能的源、宿(s-d)節點對集合 ，如果網絡滿足全連通關系，則｜D｜=｜N｜·(｜N｜-1)/2，它表明任意兩個節點之間都存在業務連接；
· dm：網絡業務連接m的光路徑需求；
· lj：鏈路j的物理距離；
· Nl：允許經過同一網絡鏈路的最大環形網絡數量；
· TMax：常量參數，表明網絡鏈路提供工作波長信道的上門限值；
· CMax：常量參數，表明網絡鏈路提供保護波長信道的上門限值；
· R：用于構建環覆蓋的候選環形網絡集合；
· Pm：網絡業務連接m的工作路由集合；
· ：表明網絡業務連接m的第p條工作路由是否經過鏈路j，如果是則 =1，否則 =0；
：表明環形網絡r是否包含鏈路j，如果是則=1，否則=0；
· ：表明鏈路j上的負載流量是否需要環形網絡r的保護，如果是則=1，否則=0；
· ：網絡業務連接m的第p條工作路由的物理長度，它的數值等于沿途經過鏈路的長度總和；
· ：環形網絡r的物理長度，它的數值等于包含在該環形網絡中的所有鏈路長度的總和；
· ：業務連接m要求工作路由p提供的光路徑需求；
· δr：表明環形網絡r是否被確定為環覆蓋的組成部分，如果是則δr=1，否則δr=0；
· cr：環形網絡r為提供保護而必需的保護波長信道需求.
上述符號中，、δr和cr是隨后環覆蓋優化設計問題需要求解的變量，其它各符號可以從現有網絡拓撲以及業務規劃中得到具體數值.下面以網絡容量總需求(同時包括工作容量和保護容量)為優化目標建立數學模型.
優化目標函數：
約束條件：
(1) 任何網絡業務在它的工作路由上所建立的光路徑總和必須滿足負載流量需求，即：
(2) 對于任何承載工作光路徑的網絡鏈路，至少需要一個覆蓋該鏈路的環形網絡對它提供保護，即：
(3) 波長保護信道只能分配給構成環覆蓋的那些環形網絡，且其容量不得超過預定的門限數值，即：
(4) 對于任何網絡鏈路，包含它的環形網絡必須得到足夠的保護波長信道容量以保護那些正在使用該網絡鏈路的工作光路徑，即：
(5) 環覆蓋中利用同一網絡鏈路構建的環網網絡數量不能超過預置的上限(該約束條件在一定程度上也可以限制訪問同一節點的環形網絡數目)，即：
(6) 環形網絡保護波長信道容量需求以及業務連接保護路由分擔的恢復流量必須滿足非負整數要求，即：
環覆蓋保護設計問題就是求解以上描述的整型線性規劃問題，至于它的求解存在許多方法，我們可以采用一些啟發式算法來解決此類組合優化問題.
6 結論
我們可以看到環覆蓋保護方法不但可以使網狀結構的光傳送網絡能夠利用環形網絡的優點，而且提高了網絡在多故障場合下的生存能力.但由于強連通網絡可能構造出多個不同的環覆蓋，它們將直接影響網絡的保護容量需求、光節點硬件結構以及網絡控制和管理，因此，如何選擇一個合理的環覆蓋就成為實施環覆蓋保護技術的關鍵.
參考文獻
�。�1］Wayne D, Grover. Case studies of survivable ring, mesh and mesharc hybrid networks [J]. Proc. GLOBECOM, 1992,1:633 638.
�。�2］Proestaki A, Sinclair M C. Design and dimensioning of dualhoming hierarchical multiring networks [J]. IEE ProcCommun, 2000, 147(2):96104.
［3］Jianxu Shi, John P, Fonseka. Hierarchial selfhealing rings [J]. IEEE/ACM Trans. Networking, 1995, 3(6):690697.
�。�4］Andrea Fumagalli, Isabella Cerutti, Marco Tacca, et al. Survivable networks based on optimal routing and WDM selfhealing rings [J]. ICC 1999(8):726733.
�。�5］Wuttisittikulkij L, O'Mahony M J. Design of a WDM network using a multiple ring approach [J]. GLOBECOM, 1997(11):551555.
［6］Gardner L M, Heydari M, Shah J, et al. Techniques for finding ring covers in survivable networks [J]. GLOBECOM, 1994(3):18621866
