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

2、備：S1S5； 6個將OXC相連的物理鏈路：l1l6。一般 一條物理鏈路包含一對光纖供雙向運用，有的OXC間沒有 物理鏈路相連。但更多的情況是一條物理鏈路包含多根光纖 供不同方向運用。一根光纖上可采用多個波長。一般情況下，OXC不直接和電設備相連，只起光交叉連 接作用。OXC可分為無波長變換和有波長變換(也可以是部分端 口有波長變換或波長變換的范圍有限)兩種：無波長變換的 OXC的作用是將一根輸入光纖上的某一波長信號連到另一 根輸出光纖的同一波長上，即波長是連續的；有波長變換則 是將一根輸入光纖上的某一波長信號連到另一根輸出光纖 的另一波長上。適當地安排路由和分配波長，可為電設備間 建立光路(

3、opticalpath)。在一根光纖上，不能為不同光路分配 相同波長。圖2(a)為圖1建立的光路例子。將圖2(a)的光路 連接用圖2(b)來表示，稱為邏輯結構，也稱邏輯拓撲或虛拓 撲。例如，圖2(a)中，節點B與E間的光路是經節點A中的 OXC轉接的，在圖2(b)中用04表示。圖2(b)中，06、04、 O1都是中間有OXC轉接的。O2、O3、O5是直接光路。這樣建立的光路對信號是透明的，即信號可以是任意方 式。實際設計中，一種需求情況是：提出所需建立的光路， 為這種光路選取物理路由并分配相應的波長1,2。例如，圖 2(b)中提出要建立6條光路，圖2(a)就是一種選路和波長分 配方案。網絡向分

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

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

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

7、有限情況下會造成波長不夠分配。改進的方法 是采用能使負載平衡的選路算法。可以采用整數線性規劃的 優化方法使網絡中一根光纖上的光路數盡量小，這為減小波 長數創造了條件，但這種方法在網絡規模較大時較復雜。為 此，可采用使網絡負載平衡的啟發式路由算法。啟發式算法 是根據概念推出的優化算法，能得到較優的結果，但不一定 最優。例如，可以按某種合適次序逐條地為光路選取路由， 每一條均采用某種優化的動態路由算法5。備用路由是為每條光路選取多條路由，最簡單的方法是 選取k條最短路徑。為多條光路的一組路由分配波長時，若 發生波長數不夠用，則通過置換備用路由構成另一組路由， 再分配波長，直到完成要求。如何從備用路

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

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

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

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

12、角度看，空域和頻域的作 用是一致的。分層圖將空域和頻域結合起來，繪出一張新的 通道圖，動態RWA問題成為在分層圖中選取一條通道的問 題。各種動態選路的算法都可考慮，目標是使阻塞率最小。 仿真表明，采用較好選路算法的分層圖法比將選路和波長分 配割裂的方法阻塞率小。3基于運送分組業務的RWA算法圖1所示是電設備（例如路由器或ATM交換機）通過光路 進行連接。可以將所有的光路部分稱為光層，其中有光交叉 連接。如果光路已經給定，則分組業務運行遇到的是一般的 選路問題，但是實用中會遇到給定各分組通信設備間的業務 量矩陣，要設計光路結構（稱為邏輯拓撲或虛拓撲）的問題2一4,7。對于電設備來說，最好是各自間

13、都建有一條光路， 但是，這樣設計不經濟。有的電設備間的連接可以經過其他 的電設備轉接，從而節省光路，圖2(b)中A與B間就沒有光 路。基于運送分組業務的選路和波長分配(RWA)算法是根據 運送分組業務的需求來設計網絡，也可分為靜態和動態兩 種。3.1基于運送分組業務的靜態 RWA算法基于運送分組業務的靜態選路和波長分配(RWA)算法是 在給定物理拓撲和各分組電設備間的業務量矩陣情況下設 計網絡，使網絡性能和經濟性盡量好。從理論上說，優先目 標一直要考慮所用的光纖數最小，使用的波長數最小等問 題，但是這樣經常很復雜。可將問題割裂分為幾步考慮，首 先進行虛拓撲設計3,4，再為虛拓撲中的光路進行選路

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

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

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

17、應的RWA算法11。5結束語本文綜述了 WDM光傳送網的RWA算法。可以看到， 光傳送網的RWA算法有多種應用情況，并要考慮多種問題， 是較復雜的。今后人們還可能提出一些新的算法。算法研究如何投入工程應用，也需要做進一步的工作。口參考文獻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光傳送網中選路和波長 分配.通信學報,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