WDM光傳送網(wǎng)的選路和波長(zhǎng)分配算法

1、WDM光傳送網(wǎng)的選路和波長(zhǎng)分配算法為了克服電處理的速率“瓶頸”，寬帶網(wǎng)絡(luò)向光網(wǎng)絡(luò) 發(fā)展。目前，光突發(fā)交換、光分組(包)交換正在積極研究中， 但是距商用還較遠(yuǎn)。已可商用的是具有光分插復(fù)用器 (OADM,OpticalAddDropMultiplexer )和光交叉連接器 (OXC,OpticalCross Connect)的波分復(fù)用(WDM)網(wǎng)絡(luò)。由于 是提供可調(diào)度的傳送用光路，稱這種網(wǎng)絡(luò)為WDM光傳送網(wǎng) (OTN,OpticalTransportNetwork)。1網(wǎng)絡(luò)結(jié)構(gòu)圖1是網(wǎng)絡(luò)物理結(jié)構(gòu)的一個(gè)例子，虛線內(nèi)為光傳送網(wǎng)。 圖中有5個(gè)OXC： A, B, C, D, E； 5個(gè)具有光接口的電 設(shè)

2、備：S1S5； 6個(gè)將OXC相連的物理鏈路：l1l6。一般 一條物理鏈路包含一對(duì)光纖供雙向運(yùn)用，有的OXC間沒有 物理鏈路相連。但更多的情況是一條物理鏈路包含多根光纖 供不同方向運(yùn)用。一根光纖上可采用多個(gè)波長(zhǎng)。一般情況下，OXC不直接和電設(shè)備相連，只起光交叉連 接作用。OXC可分為無波長(zhǎng)變換和有波長(zhǎng)變換(也可以是部分端 口有波長(zhǎng)變換或波長(zhǎng)變換的范圍有限)兩種：無波長(zhǎng)變換的 OXC的作用是將一根輸入光纖上的某一波長(zhǎng)信號(hào)連到另一 根輸出光纖的同一波長(zhǎng)上，即波長(zhǎng)是連續(xù)的；有波長(zhǎng)變換則 是將一根輸入光纖上的某一波長(zhǎng)信號(hào)連到另一根輸出光纖 的另一波長(zhǎng)上。適當(dāng)?shù)匕才怕酚珊头峙洳ㄩL(zhǎng)，可為電設(shè)備間 建立光路(

3、opticalpath)。在一根光纖上，不能為不同光路分配 相同波長(zhǎng)。圖2(a)為圖1建立的光路例子。將圖2(a)的光路 連接用圖2(b)來表示，稱為邏輯結(jié)構(gòu)，也稱邏輯拓?fù)浠蛱撏?撲。例如，圖2(a)中，節(jié)點(diǎn)B與E間的光路是經(jīng)節(jié)點(diǎn)A中的 OXC轉(zhuǎn)接的，在圖2(b)中用04表示。圖2(b)中，06、04、 O1都是中間有OXC轉(zhuǎn)接的。O2、O3、O5是直接光路。這樣建立的光路對(duì)信號(hào)是透明的，即信號(hào)可以是任意方 式。實(shí)際設(shè)計(jì)中，一種需求情況是：提出所需建立的光路， 為這種光路選取物理路由并分配相應(yīng)的波長(zhǎng)1,2。例如，圖 2(b)中提出要建立6條光路，圖2(a)就是一種選路和波長(zhǎng)分 配方案。網(wǎng)絡(luò)向分

4、組化發(fā)展，圖1中的電設(shè)備可以是ATM交換 機(jī)或IP路由器。例如，連在端口 B2的路由器可以通過光路 O6和連在端口 C3的路由器相連。B2到C3可有多條路徑， O6是最近的，也可以經(jīng)過O4-O5-O3或O4-O5-O1- O2連接，但需要路由器轉(zhuǎn)接，即電的多跳連接。A與B間 沒有光路，至少需經(jīng)C電跳連接一次。實(shí)際設(shè)計(jì)中另一種需求情況是：提出各路由器間的所需 業(yè)務(wù)量強(qiáng)度；設(shè)計(jì)出邏輯拓?fù)洳槠涔饴愤x取物理路由和分 配波長(zhǎng)24。與根據(jù)光路需求情況進(jìn)行設(shè)計(jì)相比，增加了 要考慮電的多跳。下面分別敘述兩種需求情況下的選路和波長(zhǎng)分配(RWA) 算法。2基于光路的RWA算法光路需求的提出有3類：靜態(tài)的、遞增的

5、和動(dòng)態(tài)的。靜 態(tài)RWA問題是預(yù)先給出多條光路連接需求，計(jì)算路由和分 配波長(zhǎng)。這種計(jì)算可以是離線(offline)的，即不需要實(shí)時(shí)計(jì) 算。在遞增情況，光路需求逐條地提出，需要為每一條作實(shí) 時(shí)在線RWA計(jì)算。光路數(shù)增加到一定值后，就不再增加。 對(duì)于動(dòng)態(tài)情況，光路需求逐條地提出，但一條光路持續(xù)一段 時(shí)間后又被拆除，要為每一條作實(shí)時(shí)RWA計(jì)算。這里所謂 的動(dòng)態(tài)，實(shí)用中常是緩慢變化的，例如幾小時(shí)甚至幾天才有 一次新的需求。后兩類情況的RWA算法常相同，只是性能 評(píng)價(jià)指標(biāo)不同，將在2.2節(jié)合在一起敘述。2.1基于光路的靜態(tài)RWA算法基于光路的靜態(tài)RWA算法是給定多條光路的連接需求 和物理拓?fù)浜鬄槊織l光路選

6、取路由并分配波長(zhǎng)。設(shè)計(jì)時(shí)的優(yōu) 化目標(biāo)可以是使所用的資源如波長(zhǎng)數(shù)最小。這個(gè)優(yōu)化問題可 用整數(shù)線性規(guī)劃法求解1。若OXC無波長(zhǎng)變換，則將波長(zhǎng) 連續(xù)作為約束條件。這個(gè)問題的反過來是在一定的波長(zhǎng)數(shù)下 使連接的光路數(shù)最大。這種優(yōu)化方法的復(fù)雜性隨網(wǎng)絡(luò)規(guī)模的 增大而急劇增加，因此，工程上常將RWA問題拆成選路子 問題和波長(zhǎng)分配子問題，分兩步求解。(1)為每條光路選取路由選路方案有兩類：固定路由和備用路由(alternaterouting)。固定路由是為每條光路選取一條固定的路由。通?？捎?熟知的最短路徑算法。但是，最短路徑算法的缺點(diǎn)是有時(shí)會(huì) 使網(wǎng)絡(luò)中某些部分過于擁擠，即某些光纖上經(jīng)過的光路數(shù)過 多，在波長(zhǎng)數(shù)

7、有限情況下會(huì)造成波長(zhǎng)不夠分配。改進(jìn)的方法 是采用能使負(fù)載平衡的選路算法?？梢圆捎谜麛?shù)線性規(guī)劃的 優(yōu)化方法使網(wǎng)絡(luò)中一根光纖上的光路數(shù)盡量小，這為減小波 長(zhǎng)數(shù)創(chuàng)造了條件，但這種方法在網(wǎng)絡(luò)規(guī)模較大時(shí)較復(fù)雜。為 此，可采用使網(wǎng)絡(luò)負(fù)載平衡的啟發(fā)式路由算法。啟發(fā)式算法 是根據(jù)概念推出的優(yōu)化算法，能得到較優(yōu)的結(jié)果，但不一定 最優(yōu)。例如，可以按某種合適次序逐條地為光路選取路由， 每一條均采用某種優(yōu)化的動(dòng)態(tài)路由算法5。備用路由是為每條光路選取多條路由，最簡(jiǎn)單的方法是 選取k條最短路徑。為多條光路的一組路由分配波長(zhǎng)時(shí)，若 發(fā)生波長(zhǎng)數(shù)不夠用，則通過置換備用路由構(gòu)成另一組路由， 再分配波長(zhǎng)，直到完成要求。如何從備用路

8、由集選擇合適的 路由也是需要考慮的2。(2 )分配波長(zhǎng)若OXC沒有波長(zhǎng)變換，則波長(zhǎng)分配的約束條件是每條 經(jīng)OXC連接的光路應(yīng)是波長(zhǎng)連續(xù)的，并且在一根光纖上不 同光路需分配不同波長(zhǎng)，優(yōu)化目標(biāo)是使采用的波長(zhǎng)數(shù)量最 小。這個(gè)問題可以轉(zhuǎn)化為一個(gè)輔助圖G(V,E)的著色問題1， V為節(jié)點(diǎn)集，E為邊集。V中的每個(gè)節(jié)點(diǎn)相應(yīng)于一條光路， 這條光路如果和某些其他的光路處于同一根光纖內(nèi)，則相應(yīng) 的節(jié)點(diǎn)間就有邊相連。波長(zhǎng)分配相當(dāng)于為G的節(jié)點(diǎn)著色，約 束條件是相連的節(jié)點(diǎn)不能采用同一顏色，優(yōu)化目標(biāo)是使采用 的顏色數(shù)最小。這個(gè)著色問題已有有效的算法1，但較復(fù)雜。 為了簡(jiǎn)化，可以采用一些啟發(fā)式算法，對(duì)多條路由逐條分配 波長(zhǎng)

9、。2.2基于光路的動(dòng)態(tài)RWA算法對(duì)于上面講過的遞增情況，在給定的物理拓?fù)浜妥畲蟛?長(zhǎng)數(shù)條件下，要為每一條新增光路選取路由并分配波長(zhǎng)，優(yōu) 化目標(biāo)為被拒絕(由于波長(zhǎng)數(shù)不夠)的百分比(相對(duì)于總增加 數(shù)）盡量??；對(duì)于動(dòng)態(tài)的連接請(qǐng)求和拆除情況，優(yōu)化目標(biāo)為被 拒絕（或稱阻塞）的概率盡量小。這兩類情況的RWA算法是在 線的，當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)，為了減小復(fù)雜性，常將選路和波 長(zhǎng)分配分兩步進(jìn)行；當(dāng)網(wǎng)絡(luò)規(guī)模不太大時(shí)，可以采用分層圖 的方法將選路和波長(zhǎng)分配合在一起考慮6。若首先進(jìn)行選路，可分為3類：固定路由、備用路由和 自適應(yīng)路由（自適應(yīng)路由也可納入前兩類中，即只分成兩類）。 固定路由通常采用最短路徑。備用路由可采用

10、多條最短路 徑，在首條路由上波長(zhǎng)資源不夠時(shí)，換一條再試，與固定路 由相比減小了阻塞率。采用最短路徑的缺點(diǎn)是有時(shí)會(huì)使網(wǎng)絡(luò) 中某些部分過于擁擠，阻塞率加大。改進(jìn)的方法是采用自適 應(yīng)路由1，在每次選路時(shí)，根據(jù)網(wǎng)絡(luò)的狀態(tài)，使各條光纖上 的光路數(shù)盡量平衡。選定一條路由后，要為它分配波長(zhǎng)，有多種方法1,2。 第一種方法是從該路由上已建光路所使用的波長(zhǎng)之外，隨機(jī) 地另選一個(gè)波長(zhǎng)，稱為隨機(jī)波長(zhǎng)分配算法（R算法）；第二種 是將波長(zhǎng)編號(hào)，從低到高依次觀察是否已在該路由上建光路 使用，首先找到的波長(zhǎng)就被使用，稱為首先適合算法（FF）。 仿真表明，采用FF算法的阻塞率比采用R算法時(shí)小。R和 FF算法只考慮一條路由上的

11、局部情形，還有一種最大一總數(shù) 算法（Max Sum）1,2，其思路是按分配波長(zhǎng)后網(wǎng)絡(luò)中仍可容 納的光路數(shù)最大為目標(biāo)來分配波長(zhǎng)。采用MaxSum算法的阻塞率優(yōu)于FF算法（但有時(shí)差別不大）,代價(jià)是增加復(fù)雜性。文獻(xiàn)1還敘述了其他8種波長(zhǎng)分配算法。對(duì)于將選路和波長(zhǎng)分配分兩步進(jìn)行的算法，仿真表明， 影響阻塞率的主要是選路算法。好的選路算法會(huì)顯著地減小 阻塞率，而各種波長(zhǎng)分配算法的性能差別不大。因此，在工 程上可采用一種自適應(yīng)路由算法加簡(jiǎn)易的FF波長(zhǎng)分配算法。采用分層圖（layeredgraph）的方法可以將選路和波長(zhǎng)分 配一步完成6。OXC中的光開關(guān)是空間域的連接，波長(zhǎng)分 配是頻率域的連接，從提供通道的

12、角度看，空域和頻域的作 用是一致的。分層圖將空域和頻域結(jié)合起來，繪出一張新的 通道圖，動(dòng)態(tài)RWA問題成為在分層圖中選取一條通道的問 題。各種動(dòng)態(tài)選路的算法都可考慮，目標(biāo)是使阻塞率最小。 仿真表明，采用較好選路算法的分層圖法比將選路和波長(zhǎng)分 配割裂的方法阻塞率小。3基于運(yùn)送分組業(yè)務(wù)的RWA算法圖1所示是電設(shè)備（例如路由器或ATM交換機(jī)）通過光路 進(jìn)行連接?？梢詫⑺械墓饴凡糠址Q為光層，其中有光交叉 連接。如果光路已經(jīng)給定，則分組業(yè)務(wù)運(yùn)行遇到的是一般的 選路問題，但是實(shí)用中會(huì)遇到給定各分組通信設(shè)備間的業(yè)務(wù) 量矩陣，要設(shè)計(jì)光路結(jié)構(gòu)（稱為邏輯拓?fù)浠蛱撏負(fù)洌┑膯栴}2一4,7。對(duì)于電設(shè)備來說，最好是各自間

13、都建有一條光路， 但是，這樣設(shè)計(jì)不經(jīng)濟(jì)。有的電設(shè)備間的連接可以經(jīng)過其他 的電設(shè)備轉(zhuǎn)接，從而節(jié)省光路，圖2(b)中A與B間就沒有光 路?；谶\(yùn)送分組業(yè)務(wù)的選路和波長(zhǎng)分配(RWA)算法是根據(jù) 運(yùn)送分組業(yè)務(wù)的需求來設(shè)計(jì)網(wǎng)絡(luò)，也可分為靜態(tài)和動(dòng)態(tài)兩 種。3.1基于運(yùn)送分組業(yè)務(wù)的靜態(tài) RWA算法基于運(yùn)送分組業(yè)務(wù)的靜態(tài)選路和波長(zhǎng)分配(RWA)算法是 在給定物理拓?fù)浜透鞣纸M電設(shè)備間的業(yè)務(wù)量矩陣情況下設(shè) 計(jì)網(wǎng)絡(luò)，使網(wǎng)絡(luò)性能和經(jīng)濟(jì)性盡量好。從理論上說，優(yōu)先目 標(biāo)一直要考慮所用的光纖數(shù)最小，使用的波長(zhǎng)數(shù)最小等問 題，但是這樣經(jīng)常很復(fù)雜?？蓪栴}割裂分為幾步考慮，首 先進(jìn)行虛拓?fù)湓O(shè)計(jì)3,4，再為虛拓?fù)渲械墓饴愤M(jìn)行選路

14、和分 配波長(zhǎng)，最后可能反過來對(duì)第一步設(shè)計(jì)進(jìn)行調(diào)整。在設(shè)計(jì)中， 也可以將光路的選路放在第一步中。3.2基于運(yùn)送分組業(yè)務(wù)的動(dòng)態(tài)RWA算法在IPoverWDM網(wǎng)絡(luò)中，可以采用MPLS(多協(xié)議標(biāo)記交 換)技術(shù)來實(shí)現(xiàn)業(yè)務(wù)量工程，解決有效利用網(wǎng)絡(luò)資源和保證 QoS(服務(wù)質(zhì)量)的問題。在MPLS網(wǎng)絡(luò)中，需在線建立保證帶寬的路徑，最好的解決方法是采用綜合的動(dòng)態(tài)IP與波長(zhǎng)選 路算法8。這種算法是將IP網(wǎng)絡(luò)的QoS路由技術(shù)進(jìn)一步推 廣到IPoverWDM 網(wǎng)絡(luò)。4RWA設(shè)計(jì)中要考慮的附加問題上面從概念上說明了有關(guān)RWA算法。最基本的情況是 采用無波長(zhǎng)變換的OXC，即對(duì)一條經(jīng)OXC構(gòu)成的光路有波 長(zhǎng)連續(xù)性限制。下面

15、對(duì)引入波長(zhǎng)變換、抗毀、服務(wù)策略等問 題作概要敘述。4.1波長(zhǎng)變換問題引入波長(zhǎng)變換可使在一條光路上分配波長(zhǎng)時(shí)更靈活，動(dòng) 態(tài)建立光路時(shí)阻塞率減小。引入波長(zhǎng)變換與無波長(zhǎng)變換相比 的得益程度與具體情況有關(guān)，有時(shí)明顯，有時(shí)并不明顯。波 長(zhǎng)變換器價(jià)格較貴，而且技術(shù)上有限制。文獻(xiàn)2中研究了各 種不同的配置情況：網(wǎng)絡(luò)中只有少數(shù)節(jié)點(diǎn)配置有完全波長(zhǎng)變 換的OXC，稱為稀疏波長(zhǎng)變換；OXC只有部分端口具有波 長(zhǎng)變換；波長(zhǎng)變換范圍有限，如只能在幾個(gè)波長(zhǎng)間變換。上 述3種情況可相互組合。對(duì)于不同的配置，除了要解決RWA 問題外，還要解決如何最佳配置問題。4.2抗毀問題光網(wǎng)絡(luò)的抗毀十分重要。一種情況是只考慮光傳送網(wǎng)本 身

16、抗毀，可以分成保護(hù)和恢復(fù)兩種機(jī)制9:保護(hù)機(jī)制是為每 一條工作光路準(zhǔn)備一條備用光路，要求這兩條光路不會(huì)在一 根光纖斷裂時(shí)同時(shí)失效，解決的算法類似于第2節(jié)中的備用 路由算法；恢復(fù)機(jī)制是在網(wǎng)絡(luò)有故障造成某一條光路失效 時(shí)，根據(jù)網(wǎng)絡(luò)狀態(tài)實(shí)時(shí)地重新構(gòu)造一條光路，這種方法實(shí)現(xiàn) 較復(fù)雜，同時(shí)也需要網(wǎng)絡(luò)有一定的冗余容量。另一種情況是考慮IPoverWDM網(wǎng)絡(luò)的抗毀，涉及光層 和IP層，可參考文獻(xiàn)9。4.3服務(wù)策略問題網(wǎng)絡(luò)運(yùn)行時(shí)可以引入各種策略，例如引入優(yōu)先級(jí)，某些 光路必須經(jīng)過某節(jié)點(diǎn)，某些光路不能經(jīng)過某節(jié)點(diǎn)等。要解決 這些額外要求情況下的RWA算法10。上面4.1至4.3節(jié)敘 述的問題可能同時(shí)存在，也需要有相

17、應(yīng)的RWA算法11。5結(jié)束語本文綜述了 WDM光傳送網(wǎng)的RWA算法?？梢钥吹?， 光傳送網(wǎng)的RWA算法有多種應(yīng)用情況，并要考慮多種問題， 是較復(fù)雜的。今后人們還可能提出一些新的算法。算法研究如何投入工程應(yīng)用，也需要做進(jìn)一步的工作?？趨⒖嘉墨I(xiàn)1 Zang H, Jue J P, Mukherjee B. A review of routing and wavelength assignment approaches for wavelength routed optical WDM networks. Optical Networks Magazine, 2000, 1(1): 47-602徐世中

18、，王晟，李樂民.DWDM光傳送網(wǎng)中選路和波長(zhǎng) 分配.通信學(xué)報(bào),2001, 22(4): 51 -57Leonardi E, Mellia M, Marsan M A. Algorithms for the logical topology design in WDM all optical networks. Optical Networks Magazine, 2000, 1(1): 35 -46Dutta R, Rouskas G N. A survey of virtual topology design algorithms for wavelength routed optical networks. Optical Networks Magazine, 2000, 1(1): 73 -89Kodialam M, Lakshman T V. Minimum interference routing with application to MPLS traffic engineering. IEEE INFOCOM, Tel-Aviv, Israel, 2000Xu S, Li L, Wang S. Dynamic routing and assignment of wavelength algorithms in multifi