為了克服電處理的速率“瓶頸”，寬帶網(wǎng)絡(luò)向光網(wǎng)絡(luò)發(fā)展。目前，光突發(fā)交換、光分組(包)交換正在積極研究中，但是距商用還較遠(yuǎn)。已可商用的是具有光分插復(fù)用器(OADM,OpticalAdd－DropMultiplexer)和光交叉連接器(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è)備：S1～S5；6個(gè)將OXC相連的物理鏈路：l1～l6。一般一條物理鏈路包含一對(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è)備間建立光路(opticalpath)。在一根光纖上，不能為不同光路分配相同波長(zhǎng)。圖2(a)為圖1建立的光路例子。將圖2(a)的光路連接用圖2(b)來表示，稱為邏輯結(jié)構(gòu)，也稱邏輯拓?fù)浠蛱撏負(fù)洹＠?，圖2(a)中，節(jié)點(diǎn)B與E間的光路是經(jīng)節(jié)點(diǎn)A中的OXC轉(zhuǎn)接的，在圖2(b)中用O4表示。圖2(b)中，O6、O4、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ò)向分組化發(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)[2－4]。與根據(jù)光路需求情況進(jìn)行設(shè)計(jì)相比，增加了要考慮電的多跳。

下面分別敘述兩種需求情況下的選路和波長(zhǎng)分配(RWA)算法。

2基于光路的RWA算法

光路需求的提出有3類：靜態(tài)的、遞增的和動(dòng)態(tài)的。靜態(tài)RWA問題是預(yù)先給出多條光路連接需求，計(jì)算路由和分配波長(zhǎng)。這種計(jì)算可以是離線(off－line)的，即不需要實(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光路選取路由并分配波長(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ù)有限情況下會(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)，直到完成要求。如何從備用路由集選擇合適的路由也是需要考慮的[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)。

2.2基于光路的動(dòng)態(tài)RWA算法

對(duì)于上面講過的遞增情況，在給定的物理拓?fù)浜妥畲蟛ㄩL(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)路由也可納入前兩類中，即只分成兩類)。固定路由通常采用最短路徑。備用路由可采用多條最短路徑，在首條路由上波長(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算法只考慮一條路由上的局部情形，還有一種最大－總數(shù)算法(Max－Sum)[1,2]，其思路是按分配波長(zhǎng)后網(wǎng)絡(luò)中仍可容納的光路數(shù)最大為目標(biāo)來分配波長(zhǎng)。采用Max－Sum算法的阻塞率優(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)分配算法。

采用分層圖(layered－graph)的方法可以將選路和波長(zhǎng)分配一步完成[6]。OXC中的光開關(guān)是空間域的連接，波長(zhǎng)分配是頻率域的連接，從提供通道的角度看，空域和頻域的作用是一致的。分層圖將空域和頻域結(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è)備來說，最好是各自間都建有一條光路，但是，這樣設(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)行選路和分配波長(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ù)性限制。下面對(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)本身抗毀，可以分成保護(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í)存在，也需要有相應(yīng)的RWA算法[11]。

5結(jié)束語

本文綜述了WDM光傳送網(wǎng)的RWA算法?？梢钥吹?，光傳送網(wǎng)的RWA算法有多種應(yīng)用情況，并要考慮多種問題，是較復(fù)雜的。今后人們還可能提出一些新的算法。算法研究如何投入工程應(yīng)用，也需要做進(jìn)一步的工作。□

參考文獻(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－60

2 徐世中,王晟,李樂民. DWDM光傳送網(wǎng)中選路和波長(zhǎng)分配. 通信學(xué)報(bào), 2001, 22(4): 51－57

3 Leonardi E, Mellia M, Marsan M A. Algorithms for the logical topology design in WDM all optical networks. Optical Networks Magazine, 2000, 1(1): 35－46

4 Dutta R, Rouskas G N. A survey of virtual topology design algorithms for wavelength routed optical networks. Optical Networks Magazine, 2000, 1(1): 73－89

5 Kodialam M, Lakshman T V. Minimum interference routing with application to MPLS traffic engineering. IEEE INFOCOM, Tel－Aviv, Israel, 2000

6 Xu S, Li L, Wang S. Dynamic routing and assignment of wavelength algorithms in multifiber wavelength division multiplexing networks. IEEE J, Selected Areas in Commun, 2000, 18(10): 2130－2137

7 Harai H, Kubota F, Nakazato H. Design of reconfigurable lightpaths in IP over WDM networks. IEICE Trans Commun, 2000, E83－B(10): 2234－2244

8 Kodialam M, Lakshman T V. Integrated dynamic IP and wavelength routing in IP over WDM networks. IEEE INFOCOM, Anchorage, Alaska, 2001

9 王燁,李樂民,王晟. IP over WDM網(wǎng)絡(luò)結(jié)構(gòu)和生存性研究. 電信科學(xué), 2000, 16(11): 25－30

10 何榮希,李樂民,徐世中. WDM光傳送網(wǎng)中支持優(yōu)先級(jí)的波長(zhǎng)分配算法. 通信學(xué)報(bào), 2001, 22(3): 27－32

11 王燁,李樂民等. 抗毀WDM網(wǎng)絡(luò)中支持多優(yōu)先級(jí)的波長(zhǎng)分配算法. 電子學(xué)報(bào), 2001, 29(1): 27－31

(收稿日期：2001－09－05)

作者簡(jiǎn)介

李樂民，中國工程院院士，電子科技大學(xué)教授，博士生導(dǎo)師。研究方向?yàn)樾畔鬏斉c通信網(wǎng)，近年側(cè)重于寬帶通信。已發(fā)表論文200余篇。