薛文革,陳莉
(上海電信技術(shù)研究院,上海200122)
摘要:生存性是光傳送網(wǎng)絡(luò)中亟待解決的問題.文章基于環(huán)網(wǎng)的優(yōu)良保護倒換能力提出了環(huán)覆蓋保護策略,給出了選擇環(huán)覆蓋的控制流程,建立了以保護容量需求作為優(yōu)化目標的環(huán)覆蓋優(yōu)化設(shè)計模型.
關(guān)鍵詞:生存性;環(huán)覆蓋;整型線性規(guī)劃;網(wǎng)狀網(wǎng)
光傳送網(wǎng)絡(luò)的拓撲結(jié)構(gòu)一直是網(wǎng)絡(luò)設(shè)計人員所關(guān)注的問題[1].盡管當前可用的拓撲種類較多,但人們往往比較喜歡網(wǎng)狀結(jié)構(gòu),這是因為網(wǎng)狀光傳送網(wǎng)絡(luò)具有高度連通性,所以無論是在正常狀態(tài)還是故障狀態(tài)下它都能有效地使用網(wǎng)絡(luò)資源,從而使得網(wǎng)絡(luò)容量需求達到最小,但其結(jié)構(gòu)復(fù)雜,使得網(wǎng)絡(luò)資源的控制和管理變得復(fù)雜.當發(fā)生故障時除了需要硬件交換器以外,還必須使用大量的軟件處理(恢復(fù)消息的交換和處理、網(wǎng)絡(luò)配置數(shù)據(jù)庫的一致性維護以及波長信道分配策略等)才能夠?qū)崿F(xiàn)受損業(yè)務(wù)的恢復(fù),導(dǎo)致故障恢復(fù)時間較長,可靠性差。
環(huán)形拓撲是所有通信網(wǎng)絡(luò)都支持的一種結(jié)構(gòu),在目前的計算機網(wǎng)絡(luò)和電信網(wǎng)絡(luò)等領(lǐng)域中正運行著大量的環(huán)形網(wǎng)絡(luò);它也是光傳送網(wǎng)絡(luò)的一種主要拓撲結(jié)構(gòu),盡管在容量效率方面比不上網(wǎng)狀結(jié)構(gòu),但它具有一些網(wǎng)狀結(jié)構(gòu)無法達到的優(yōu)良特征,尤其當發(fā)生網(wǎng)絡(luò)故障時,環(huán)形網(wǎng)絡(luò)通過硬件交換器可以輕松地實現(xiàn)網(wǎng)絡(luò)保護,倒換速度快,可靠性高.正是基于這一優(yōu)良特性,我們提出了環(huán)覆蓋保護方法.
1 分層互連環(huán)
網(wǎng)絡(luò)規(guī)模是影響環(huán)形網(wǎng)絡(luò)性能的一個關(guān)鍵因素,在環(huán)形網(wǎng)絡(luò)中,隨著節(jié)點數(shù)的增加,網(wǎng)絡(luò)容量需求以及業(yè)務(wù)節(jié)點間的路徑長度將明顯增加,這限制了單個環(huán)形網(wǎng)絡(luò)能夠容納的節(jié)點數(shù)目.為了在大規(guī)模網(wǎng)絡(luò)中利用環(huán)形網(wǎng)絡(luò)的優(yōu)點,比較實際的做法就是對網(wǎng)絡(luò)節(jié)點分組,然后為每個分組建立一個環(huán)形網(wǎng)絡(luò),且這些環(huán)形網(wǎng)絡(luò)之間通過公共節(jié)點相互連接,從而形成具有層次結(jié)構(gòu)的互連環(huán)網(wǎng)(Interconnected Ring);如果每個環(huán)都具有生存能力(即屬于自愈環(huán)類型),則稱該互連環(huán)是為自愈互連環(huán)[2~3].
分層互連環(huán)根據(jù)網(wǎng)絡(luò)規(guī)模可以劃分成不同等級,除了最頂層僅包含一個環(huán)形網(wǎng)絡(luò)之外,其它各層都包括一定數(shù)量的環(huán)網(wǎng)絡(luò).較高層次的環(huán)可以互連多個較低層次的環(huán),它們的連通性是通過層間公共節(jié)點(Common Node),也被稱作互連節(jié)點(Interconnecting Node)的橋接作用來保證的,各個環(huán)在正常狀態(tài)下的操作以及故障狀態(tài)下的自動保護交換都是相互獨立的.圖1給出了兩層互連環(huán)的典型拓撲結(jié)構(gòu),其中,(a)為單歸宿(Single homing)型網(wǎng)絡(luò),它包括4個初級環(huán)和一個2級環(huán),它能夠處理任何單個鏈路故障.但由于環(huán)之間僅通過一個公共節(jié)點進行連接,所以它無法處理發(fā)生在這些公共節(jié)點上的故障,此時的互連環(huán)被分割成兩個“孤島”,失去了物理連通性的網(wǎng)絡(luò)顯然是不可恢復(fù)的.為了解決這個問題,單歸宿型互連環(huán)網(wǎng)絡(luò)必須在環(huán)之間增加一個冗余公共節(jié)點,即必須構(gòu)建雙歸宿(Dualhoming)型互連網(wǎng)才能保證網(wǎng)絡(luò)在公共節(jié)點有故障時也是可生存的.圖1(b)描述了它的基本結(jié)構(gòu),圖中的所有初級環(huán)都是通過兩個公共節(jié)點與2級環(huán)進行互連的.
由于分層互連環(huán)的各組成環(huán)相互獨立,這為網(wǎng)絡(luò)消除多個故障的影響提供了可能.只要這些故障分布在不同的環(huán)網(wǎng)上,它們總能夠得到妥善的處理;而且在時間上可以重疊,即具有并發(fā)處理特征,這將極大地減少網(wǎng)絡(luò)保護倒換時間;尤其是在理想情況下,多個故障的處理時間能夠做到與單個故障的處理時間幾乎相等.
2 環(huán)覆蓋保護原理
分層互連環(huán)是一個比較理想化的解決方案,實際的網(wǎng)絡(luò)結(jié)構(gòu)存在很大的任意性,它們難以構(gòu)建出具有嚴格上、下層次關(guān)系的互連環(huán)網(wǎng).為了既適應(yīng)網(wǎng)絡(luò)結(jié)構(gòu)的隨意性,又能夠發(fā)揮出環(huán)形網(wǎng)絡(luò)的優(yōu)勢,我們在分層互連環(huán)的基礎(chǔ)上提出了環(huán)覆蓋技術(shù),它能夠有效地滿足上述兩項要求.所謂環(huán)覆蓋(Ring Cover)就是一個必須覆蓋網(wǎng)絡(luò)所有鏈路的環(huán)形網(wǎng)絡(luò)集合,它實際上是一種混合(Hybrid)互連環(huán)結(jié)構(gòu),與分層互連環(huán)不同的是環(huán)覆蓋中的各組成成員(即環(huán)形網(wǎng)絡(luò))之間不存在任何關(guān)聯(lián).環(huán)覆蓋保護就是通過互連的環(huán)形網(wǎng)絡(luò)來實現(xiàn)對受損業(yè)務(wù)的保護倒換,它可以將網(wǎng)狀網(wǎng)絡(luò)的業(yè)務(wù)保護時間縮短到與自愈環(huán)大體相當?shù)某潭?
根據(jù)圖論的連通性理論我們可以從網(wǎng)狀光傳送網(wǎng)絡(luò)得出如下推論:
推論1:一個給定的網(wǎng)狀結(jié)構(gòu)網(wǎng)絡(luò)可以存在多個環(huán)覆蓋;
推論2:環(huán)覆蓋中的環(huán)網(wǎng)絡(luò)尺寸大小可以不一樣;
推論3:環(huán)覆蓋為了覆蓋所有的網(wǎng)絡(luò)鏈路和節(jié)點,必定有使用相同網(wǎng)絡(luò)鏈路(節(jié)點)的環(huán)存在;
推論4:網(wǎng)絡(luò)路徑總是被環(huán)覆蓋中的一個或多個環(huán)所容納,它不可能超越環(huán)覆蓋的作用范圍;
推論5:單個網(wǎng)絡(luò)故障影響的工作業(yè)務(wù)需要環(huán)覆蓋中提供保護的環(huán)個數(shù)不得超過覆蓋該故障的環(huán)個數(shù);
推論6:特定路由上的業(yè)務(wù)只能由環(huán)覆蓋中的單個環(huán)提供保護;
根據(jù)上面分析可以看出:環(huán)覆蓋技術(shù)特別適合于縮短網(wǎng)狀光傳送網(wǎng)絡(luò)保護倒換時間,這對于大容量的波長傳輸信道尤其重要.因為在相同的倒換時間內(nèi),它中斷的業(yè)務(wù)數(shù)據(jù)流量要遠遠高于任何傳統(tǒng)傳輸網(wǎng)絡(luò).
3 環(huán)形網(wǎng)絡(luò)的構(gòu)建
由于網(wǎng)狀拓撲的網(wǎng)絡(luò)結(jié)構(gòu)可以對應(yīng)多個環(huán)形網(wǎng)絡(luò),如何構(gòu)建并確定合適的環(huán)形網(wǎng)絡(luò)是實施環(huán)覆蓋保護的先決條件.根據(jù)業(yè)務(wù)負載傳輸要求,可以將環(huán)形網(wǎng)絡(luò)的構(gòu)建策略分成兩種類型,一種是環(huán)內(nèi)(IntraRing)傳輸策略;另一種就是環(huán)間(InterRing)傳輸策略.前者是指網(wǎng)絡(luò)上的所有業(yè)務(wù)傳輸只能局限在某一特定的環(huán)形網(wǎng)絡(luò)內(nèi)部,而不能傳輸?shù)狡渌h(huán)形網(wǎng)絡(luò)當中;后者則沒有這個限制,它允許業(yè)務(wù)傳輸路由跨越單個或者多個環(huán)形網(wǎng)絡(luò).從理論上講,我們希望在傳輸時業(yè)務(wù)盡可能跨越數(shù)量較少的環(huán)形網(wǎng)絡(luò)[5].
圖2給出了一個環(huán)內(nèi)傳輸策略范例,它通過R1=1,2,3,4,5,6}、R2={4,5,6,7,8,9}和R3={1,2,3,4,6,7,8,9}這3個環(huán)形網(wǎng)絡(luò)來保證網(wǎng)絡(luò)的任何業(yè)務(wù)傳輸都圖2環(huán)內(nèi)傳輸策略可以僅使用一個環(huán)即可.例如節(jié)點對(1,5)、(4,8)和(1,9)的通信分別使用環(huán)形網(wǎng)絡(luò)R1、R2和R3,沒有其它選擇;而節(jié)點對(1,2)的通信既可以使用R1,也可以使用R3,但最終還是只能確定其中一個.較簡單的處理方法就是選擇較小的環(huán)形網(wǎng)絡(luò),但也可以根據(jù)網(wǎng)絡(luò)的業(yè)務(wù)分布以及鏈路容量進行選擇,這樣能夠充分利用網(wǎng)絡(luò)的信道資源,但控制復(fù)雜度較高.
圖3給出了一個環(huán)間傳輸策略范例,盡管這種情況下的環(huán)形網(wǎng)絡(luò)構(gòu)建沒有限制,但最后的結(jié)果必須能夠滿足網(wǎng)絡(luò)業(yè)務(wù)的傳輸要求.例如環(huán)形網(wǎng)絡(luò)R1={1,2,4,5}、R2={2,3,5,6}、R3={4,5,7,8}和R4={5,6,8,9}就是一個符合需求的結(jié)果,所有的網(wǎng)絡(luò)業(yè)務(wù)總是能夠通過它們的組合得到傳輸.例如節(jié)點對(1,2)和(5,9)的通信僅需要分別使用單個環(huán)形網(wǎng)絡(luò)R1和R4即可,而節(jié)點對(1,8)間的通信必須使用環(huán)形網(wǎng)絡(luò)R1和R3的組合才能完成.
環(huán)內(nèi)傳輸策略與環(huán)間傳輸策略的根本差異在于最終環(huán)形網(wǎng)絡(luò)的大小問題.前者可以避免網(wǎng)絡(luò)業(yè)務(wù)跨越多個網(wǎng)絡(luò)而帶來的控制復(fù)雜性,但它使得某些環(huán)形網(wǎng)絡(luò)變得非常龐大,甚至?xí)`背環(huán)覆蓋的初衷,因為互連環(huán)本身就是為了克服較大規(guī)模的網(wǎng)絡(luò)結(jié)構(gòu)而提出的;盡管第2種策略的復(fù)雜度較高,但它的“區(qū)域分割”機制能夠真正使用環(huán)形網(wǎng)絡(luò)的固有優(yōu)勢,因此,本文僅針對環(huán)間傳輸策略進行進一步的分析和研究.
4 環(huán)形網(wǎng)絡(luò)選擇策略
如果將網(wǎng)狀結(jié)構(gòu)的網(wǎng)絡(luò)看作是一個連通性無向圖,那么環(huán)形網(wǎng)絡(luò)的構(gòu)建問題可以轉(zhuǎn)化成無向圖的圈(Cycle)搜索問題[4~6].對于一個強連通圖而言,它往往可以搜索出多個不同的圈,這些圈的大小(可容納在圈上的節(jié)點數(shù)目)可以相同,也可以不同.基于圖論的圈搜索算法盡管很多,但它的實現(xiàn)一般比較復(fù)雜,文獻[6]提出了一種簡單的啟發(fā)式圈搜索算法,它可以同時適用于無向圖和有向圖.
從上面分析我們可以得知:一個網(wǎng)狀網(wǎng)絡(luò)可能同時包含多個環(huán)形網(wǎng)絡(luò),且其數(shù)量隨著網(wǎng)絡(luò)規(guī)模的擴大成比例增長,它們的可能組合將非常龐大.例如在18節(jié)點的歐洲RACE2028計劃網(wǎng)絡(luò)中,它可以生成1 228個大小不同的環(huán)形網(wǎng)絡(luò).如果僅使用其中的12個環(huán)形網(wǎng)絡(luò)來試構(gòu)建可行的環(huán)覆蓋,將會出現(xiàn)2.8×1031種可能組合.因此,計算并比較所有可能的環(huán)覆蓋以便確定其中的最優(yōu)者將極為復(fù)雜,這使它在實際應(yīng)用中難以實現(xiàn).
不過,我們可以充分利用已有的環(huán)形網(wǎng)絡(luò)知識壓縮不必要的環(huán)覆蓋,從而降低計算復(fù)雜度.影響環(huán)形網(wǎng)絡(luò)性能特征的核心因素在于它的大小,即較小者在容量使用效率和保護倒換時間等性能優(yōu)勢方面要明顯超過較大者.理論上已經(jīng)證明: 在大小為N且業(yè)務(wù)需求均勻分布的環(huán)形網(wǎng)絡(luò)中,平均每個業(yè)務(wù)連接需要經(jīng)過N2/4(N-1)條鏈路(N為偶數(shù))或者(N+1)/4條鏈路(N為奇數(shù)),這表明對于同等級別的業(yè)務(wù)而言,大環(huán)總是比小環(huán)需要更多的容量;同時小環(huán)在保護倒換時間上具有一定的優(yōu)勢.因此,構(gòu)建環(huán)覆蓋的候選環(huán)形網(wǎng)絡(luò)必須限制在一定的規(guī)模范圍以內(nèi);這不僅可以發(fā)揮小環(huán)的性能優(yōu)勢,而且能有效地解決計算復(fù)雜度問題.
經(jīng)過上述分析可以發(fā)現(xiàn)環(huán)覆蓋設(shè)計問題必須包括業(yè)務(wù)分布、環(huán)形網(wǎng)絡(luò)搜索、構(gòu)建環(huán)覆蓋需要的候選環(huán)以及環(huán)覆蓋優(yōu)化5個基本功能模塊,圖4給出了環(huán)覆蓋設(shè)計問題的功能模塊控制流程.
5 環(huán)覆蓋保護優(yōu)化模型
由于環(huán)覆蓋保護本身能夠保證最小網(wǎng)絡(luò)保護倒換時間需求,因此,它的優(yōu)化設(shè)計主要集中在容量需求領(lǐng)域.在提出環(huán)覆蓋保護優(yōu)化設(shè)計模型之前,我們先給出它的適用環(huán)境,即必須滿足下列假設(shè)條件:
· 只能在單個網(wǎng)絡(luò)故障狀態(tài)下對業(yè)務(wù)保證完全恢復(fù),而對于多故障必須要求它們分布在不同的環(huán)形網(wǎng)絡(luò)當中;
· 網(wǎng)絡(luò)鏈路上的波長保護信道只能在環(huán)形網(wǎng)絡(luò)內(nèi)部共享,而各環(huán)形網(wǎng)絡(luò)之間不能共享任何保護波長信道;
· 為了減輕網(wǎng)絡(luò)控制管理復(fù)雜度,要求經(jīng)過同一網(wǎng)絡(luò)鏈路的環(huán)形網(wǎng)絡(luò)數(shù)量不得超過某一預(yù)置的門限值;
· 為了降低網(wǎng)絡(luò)節(jié)點復(fù)雜度,要求方位同一節(jié)點的環(huán)形網(wǎng)絡(luò)數(shù)量不得超過某一預(yù)置的門限值;
· 為了簡化環(huán)覆蓋設(shè)計問題,假定網(wǎng)絡(luò)節(jié)點具有完全波長轉(zhuǎn)換能力.
符號定義:
· N:網(wǎng)絡(luò)節(jié)點集合;
· L:網(wǎng)絡(luò)光纖鏈路集合;
· D:業(yè)務(wù)連接集合,即可能的源、宿(s-d)節(jié)點對集合 ,如果網(wǎng)絡(luò)滿足全連通關(guān)系,則|D|=|N|·(|N|-1)/2,它表明任意兩個節(jié)點之間都存在業(yè)務(wù)連接;
· dm:網(wǎng)絡(luò)業(yè)務(wù)連接m的光路徑需求;
· lj:鏈路j的物理距離;
· Nl:允許經(jīng)過同一網(wǎng)絡(luò)鏈路的最大環(huán)形網(wǎng)絡(luò)數(shù)量;
· TMax:常量參數(shù),表明網(wǎng)絡(luò)鏈路提供工作波長信道的上門限值;
· CMax:常量參數(shù),表明網(wǎng)絡(luò)鏈路提供保護波長信道的上門限值;
· R:用于構(gòu)建環(huán)覆蓋的候選環(huán)形網(wǎng)絡(luò)集合;
· Pm:網(wǎng)絡(luò)業(yè)務(wù)連接m的工作路由集合;
· :表明網(wǎng)絡(luò)業(yè)務(wù)連接m的第p條工作路由是否經(jīng)過鏈路j,如果是則 =1,否則 =0;
:表明環(huán)形網(wǎng)絡(luò)r是否包含鏈路j,如果是則=1,否則=0;
· :表明鏈路j上的負載流量是否需要環(huán)形網(wǎng)絡(luò)r的保護,如果是則=1,否則=0;
· :網(wǎng)絡(luò)業(yè)務(wù)連接m的第p條工作路由的物理長度,它的數(shù)值等于沿途經(jīng)過鏈路的長度總和;
· :環(huán)形網(wǎng)絡(luò)r的物理長度,它的數(shù)值等于包含在該環(huán)形網(wǎng)絡(luò)中的所有鏈路長度的總和;
· :業(yè)務(wù)連接m要求工作路由p提供的光路徑需求;
· δr:表明環(huán)形網(wǎng)絡(luò)r是否被確定為環(huán)覆蓋的組成部分,如果是則δr=1,否則δr=0;
· cr:環(huán)形網(wǎng)絡(luò)r為提供保護而必需的保護波長信道需求.
上述符號中,、δr和cr是隨后環(huán)覆蓋優(yōu)化設(shè)計問題需要求解的變量,其它各符號可以從現(xiàn)有網(wǎng)絡(luò)拓撲以及業(yè)務(wù)規(guī)劃中得到具體數(shù)值.下面以網(wǎng)絡(luò)容量總需求(同時包括工作容量和保護容量)為優(yōu)化目標建立數(shù)學(xué)模型.
優(yōu)化目標函數(shù):
約束條件:
(1) 任何網(wǎng)絡(luò)業(yè)務(wù)在它的工作路由上所建立的光路徑總和必須滿足負載流量需求,即:
(2) 對于任何承載工作光路徑的網(wǎng)絡(luò)鏈路,至少需要一個覆蓋該鏈路的環(huán)形網(wǎng)絡(luò)對它提供保護,即:
(3) 波長保護信道只能分配給構(gòu)成環(huán)覆蓋的那些環(huán)形網(wǎng)絡(luò),且其容量不得超過預(yù)定的門限數(shù)值,即:
(4) 對于任何網(wǎng)絡(luò)鏈路,包含它的環(huán)形網(wǎng)絡(luò)必須得到足夠的保護波長信道容量以保護那些正在使用該網(wǎng)絡(luò)鏈路的工作光路徑,即:
(5) 環(huán)覆蓋中利用同一網(wǎng)絡(luò)鏈路構(gòu)建的環(huán)網(wǎng)網(wǎng)絡(luò)數(shù)量不能超過預(yù)置的上限(該約束條件在一定程度上也可以限制訪問同一節(jié)點的環(huán)形網(wǎng)絡(luò)數(shù)目),即:
(6) 環(huán)形網(wǎng)絡(luò)保護波長信道容量需求以及業(yè)務(wù)連接保護路由分擔(dān)的恢復(fù)流量必須滿足非負整數(shù)要求,即:
環(huán)覆蓋保護設(shè)計問題就是求解以上描述的整型線性規(guī)劃問題,至于它的求解存在許多方法,我們可以采用一些啟發(fā)式算法來解決此類組合優(yōu)化問題.
6 結(jié)論
我們可以看到環(huán)覆蓋保護方法不但可以使網(wǎng)狀結(jié)構(gòu)的光傳送網(wǎng)絡(luò)能夠利用環(huán)形網(wǎng)絡(luò)的優(yōu)點,而且提高了網(wǎng)絡(luò)在多故障場合下的生存能力.但由于強連通網(wǎng)絡(luò)可能構(gòu)造出多個不同的環(huán)覆蓋,它們將直接影響網(wǎng)絡(luò)的保護容量需求、光節(jié)點硬件結(jié)構(gòu)以及網(wǎng)絡(luò)控制和管理,因此,如何選擇一個合理的環(huán)覆蓋就成為實施環(huán)覆蓋保護技術(shù)的關(guān)鍵.
參考文獻
[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