摘要：文章綜述了波分復(fù)用(WDM)光傳送網(wǎng)的選路和波長分配(RWA)算法；考慮了兩種需求情況：一種是從建立光路的需求出發(fā)，另一種是從運(yùn)送分組業(yè)務(wù)的需求出發(fā)；還概述了RWA設(shè)計(jì)中要考慮的附加問題，包括波長變換、抗毀和服務(wù)策略。
關(guān)鍵詞：波分復(fù)用 光傳送網(wǎng) 選路和波長分配
Abstract:A review of routing and wavelength assignment (RWA) algorithms for WDM optical transport networks is presented. Two cases of requirements are considered: One is the requirement of establishing optical paths and the other is the requirement of transporting packet services. Related problems including wavelength converting, survivability and policy of services in RWA design are also briefly discussed.
Key words:Wavelength division multiplex Optical transport network Routing and wavelength assignment
　　為了克服電處理的速率“瓶頸”，寬帶網(wǎng)絡(luò)向光網(wǎng)絡(luò)發(fā)展。目前，光突發(fā)交換、光分組(包)交換正在積極研究中，但是距商用還較遠(yuǎn)。已可商用的是具有光分插復(fù)用器(OADM,Optical Add－Drop Multiplexer)和光交叉連接器(OXC,Optical Cross－Connect)的波分復(fù)用(WDM)網(wǎng)絡(luò)。由于是提供可調(diào)度的傳送用光路，稱這種網(wǎng)絡(luò)為WDM光傳送網(wǎng)(OTN,Optical Transport Network)。
　　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è)波長。

圖1　網(wǎng)絡(luò)物理結(jié)構(gòu)舉例
　　一般情況下，OXC不直接和電設(shè)備相連，只起光交叉連接作用。
　　OXC可分為無波長變換和有波長變換(也可以是部分端口有波長變換或波長變換的范圍有限)兩種：無波長變換的OXC的作用是將一根輸入光纖上的某一波長信號(hào)連到另一根輸出光纖的同一波長上，即波長是連續(xù)的；有波長變換則是將一根輸入光纖上的某一波長信號(hào)連到另一根輸出光纖的另一波長上。適當(dāng)?shù)匕才怕酚珊头峙洳ㄩL，可為電設(shè)備間建立光路(optical path)。在一根光纖上，不能為不同光路分配相同波長。圖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是直接光路。

圖2　光路舉例
　　這樣建立的光路對(duì)信號(hào)是透明的，即信號(hào)可以是任意方式。
　　實(shí)際設(shè)計(jì)中，一種需求情況是：提出所需建立的光路，為這種光路選取物理路由并分配相應(yīng)的波長[1,2]。例如，圖2(b)中提出要建立6條光路，圖2(a)就是一種選路和波長分配方案。
　　網(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ù)洳�為其光路選取物理路由和分配波長[2－4]。與根據(jù)光路需求情況進(jìn)行設(shè)計(jì)相比，增加了要考慮電的多跳。
　　下面分別敘述兩種需求情況下的選路和波長分配(RWA)算法。
　　2 基于光路的RWA算法
　　光路需求的提出有3類：靜態(tài)的、遞增的和動(dòng)態(tài)的。靜態(tài)RWA問題是預(yù)先給出多條光路連接需求，計(jì)算路由和分配波長。這種計(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光路選取路由并分配波長。設(shè)計(jì)時(shí)的優(yōu)化目標(biāo)可以是使所用的資源如波長數(shù)最小。這個(gè)優(yōu)化問題可用整數(shù)線性規(guī)劃法求解[1]。若OXC無波長變換，則將波長連續(xù)作為約束條件。這個(gè)問題的反過來是在一定的波長數(shù)下使連接的光路數(shù)最大。這種優(yōu)化方法的復(fù)雜性隨網(wǎng)絡(luò)規(guī)模的增大而急劇增加，因此，工程上常將RWA問題拆成選路子問題和波長分配子問題，分兩步求解。
　　(1)為每條光路選取路由
　　選路方案有兩類：固定路由和備用路由(alternate routing)。
　　固定路由是為每條光路選取一條固定的路由。通�？捎檬熘�的最短路徑算法。但是，最短路徑算法的缺點(diǎn)是有時(shí)會(huì)使網(wǎng)絡(luò)中某些部分過于擁擠，即某些光纖上經(jīng)過的光路數(shù)過多，在波長數(shù)有限情況下會(huì)造成波長不夠分配。改進(jìn)的方法是采用能使負(fù)載平衡的選路算法�？梢圆捎谜麛�(shù)線性規(guī)劃的優(yōu)化方法使網(wǎng)絡(luò)中一根光纖上的光路數(shù)盡量小，這為減小波長數(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條最短路徑。為多條光路的一組路由分配波長時(shí)，若發(fā)生波長數(shù)不夠用，則通過置換備用路由構(gòu)成另一組路由，再分配波長，直到完成要求。如何從備用路由集選擇合適的路由也是需要考慮的[2]。
　　(2)分配波長
　　若OXC沒有波長變換，則波長分配的約束條件是每條經(jīng)OXC連接的光路應(yīng)是波長連續(xù)的，并且在一根光纖上不同光路需分配不同波長，優(yōu)化目標(biāo)是使采用的波長數(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)間就有邊相連。波長分配相當(dāng)于為G的節(jié)點(diǎn)著色，約束條件是相連的節(jié)點(diǎn)不能采用同一顏色，優(yōu)化目標(biāo)是使采用的顏色數(shù)最小。這個(gè)著色問題已有有效的算法[1]，但較復(fù)雜。為了簡(jiǎn)化，可以采用一些啟發(fā)式算法，對(duì)多條路由逐條分配波長。
　　2.2 基于光路的動(dòng)態(tài)RWA算法
　　對(duì)于上面講過的遞增情況，在給定的物理拓?fù)浜妥畲蟛ㄩL數(shù)條件下，要為每一條新增光路選取路由并分配波長，優(yōu)化目標(biāo)為被拒絕(由于波長數(shù)不夠)的百分比(相對(duì)于總增加數(shù))盡量�。粚�(duì)于動(dòng)態(tài)的連接請(qǐng)求和拆除情況，優(yōu)化目標(biāo)為被拒絕(或稱阻塞)的概率盡量小。這兩類情況的RWA算法是在線的，當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)，為了減小復(fù)雜性，常將選路和波長分配分兩步進(jìn)行；當(dāng)網(wǎng)絡(luò)規(guī)模不太大時(shí)，可以采用分層圖的方法將選路和波長分配合在一起考慮[6]。
　　若首先進(jìn)行選路，可分為3類：固定路由、備用路由和自適應(yīng)路由(自適應(yīng)路由也可納入前兩類中，即只分成兩類)。固定路由通常采用最短路徑。備用路由可采用多條最短路徑，在首條路由上波長資源不夠時(shí)，換一條再試，與固定路由相比減小了阻塞率。采用最短路徑的缺點(diǎn)是有時(shí)會(huì)使網(wǎng)絡(luò)中某些部分過于擁擠，阻塞率加大。改進(jìn)的方法是采用自適應(yīng)路由[1]，在每次選路時(shí)，根據(jù)網(wǎng)絡(luò)的狀態(tài)，使各條光纖上的光路數(shù)盡量平衡。
　　選定一條路由后，要為它分配波長，有多種方法[1,2]。第一種方法是從該路由上已建光路所使用的波長之外，隨機(jī)地另選一個(gè)波長，稱為隨機(jī)波長分配算法(R算法)；第二種是將波長編號(hào)，從低到高依次觀察是否已在該路由上建光路使用，首先找到的波長就被使用，稱為首先適合算法(FF)。仿真表明，采用FF算法的阻塞率比采用R算法時(shí)小。R和FF算法只考慮一條路由上的局部情形，還有一種最大－總數(shù)算法(Max－Sum)[1,2]，其思路是按分配波長后網(wǎng)絡(luò)中仍可容納的光路數(shù)最大為目標(biāo)來分配波長。采用Max－Sum算法的阻塞率優(yōu)于FF算法(但有時(shí)差別不大)，代價(jià)是增加復(fù)雜性。文獻(xiàn)1還敘述了其他8種波長分配算法。
　　對(duì)于將選路和波長分配分兩步進(jìn)行的算法，仿真表明，影響阻塞率的主要是選路算法。好的選路算法會(huì)顯著地減小阻塞率，而各種波長分配算法的性能差別不大。因此，在工程上可采用一種自適應(yīng)路由算法加簡(jiǎn)易的FF波長分配算法。
　　采用分層圖(layered－graph)的方法可以將選路和波長分配一步完成[6]。OXC中的光開關(guān)是空間域的連接，波長分配是頻率域的連接，從提供通道的角度看，空域和頻域的作用是一致的。分層圖將空域和頻域結(jié)合起來，繪出一張新的通道圖，動(dòng)態(tài)RWA問題成為在分層圖中選取一條通道的問題。各種動(dòng)態(tài)選路的算法都可考慮，目標(biāo)是使阻塞率最小。仿真表明，采用較好選路算法的分層圖法比將選路和波長分配割裂的方法阻塞率小。
　　3 基于運(yùn)送分組業(yè)務(wù)的RWA算法
　　圖1所示是電設(shè)備(例如路由器或ATM交換機(jī))通過光路進(jìn)行連接。可以將所有的光路部分稱為光層，其中有光交叉連接。如果光路已經(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ù)的選路和波長分配(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)選路和波長分配(RWA)算法是在給定物理拓?fù)浜透鞣纸M電設(shè)備間的業(yè)務(wù)量矩陣情況下設(shè)計(jì)網(wǎng)絡(luò)，使網(wǎng)絡(luò)性能和經(jīng)濟(jì)性盡量好。從理論上說，優(yōu)先目標(biāo)一直要考慮所用的光纖數(shù)最小，使用的波長數(shù)最小等問題，但是這樣經(jīng)常很復(fù)雜�？蓪�問題割裂分為幾步考慮，首先進(jìn)行虛拓?fù)湓O(shè)計(jì)[3,4]，再為虛拓?fù)渲械墓饴愤M(jìn)行選路和分配波長，最后可能反過來對(duì)第一步設(shè)計(jì)進(jìn)行調(diào)整。在設(shè)計(jì)中，也可以將光路的選路放在第一步中。
　　
　　3.2 基于運(yùn)送分組業(yè)務(wù)的動(dòng)態(tài)RWA算法
　　在IP over WDM網(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與波長選路算法[8]。這種算法是將IP網(wǎng)絡(luò)的QoS路由技術(shù)進(jìn)一步推廣到IP over WDM網(wǎng)絡(luò)。
　　4 RWA設(shè)計(jì)中要考慮的附加問題
　　上面從概念上說明了有關(guān)RWA算法。最基本的情況是采用無波長變換的OXC，即對(duì)一條經(jīng)OXC構(gòu)成的光路有波長連續(xù)性限制。下面對(duì)引入波長變換、抗毀、服務(wù)策略等問題作概要敘述。
　　4.1 波長變換問題
　　引入波長變換可使在一條光路上分配波長時(shí)更靈活，動(dòng)態(tài)建立光路時(shí)阻塞率減小。引入波長變換與無波長變換相比的得益程度與具體情況有關(guān)，有時(shí)明顯，有時(shí)并不明顯。波長變換器價(jià)格較貴，而且技術(shù)上有限制。文獻(xiàn)2中研究了各種不同的配置情況：網(wǎng)絡(luò)中只有少數(shù)節(jié)點(diǎn)配置有完全波長變換的OXC，稱為稀疏波長變換；OXC只有部分端口具有波長變換；波長變換范圍有限，如只能在幾個(gè)波長間變換。上述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ò)有一定的冗余容量。
　　另一種情況是考慮IP over WDM網(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)中選路和波長分配. 通信學(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í)的波長分配算法. 通信學(xué)報(bào), 2001, 22(3): 27－32
11 王燁,李樂民等. 抗毀WDM網(wǎng)絡(luò)中支持多優(yōu)先級(jí)的波長分配算法. 電子學(xué)報(bào), 2001, 29(1): 27－31