路由波長分配（RWA）算法的研究現(xiàn)狀班級：2010211117學號：10210518姓名：劉芷若1.前言波分復用（Wavelength

Division

Multiplexing—WDM）網絡利用了光纖傳輸鏈路的巨大帶寬，隨著WDM技術日趨成熟，WDM傳輸技術已經進入實用化和商用化階段。WDM全光通信網是光纖通信未來發(fā)展的主要方向之一。由于光網絡對傳輸信號的速率和格式透明，具有靈活的波長選路和動態(tài)資源配置能力，可以實現(xiàn)網絡的動態(tài)重構，被認為是通信網絡升級的首選方案。如何利用現(xiàn)有的和即將敷設的光纖連網，構成未來高速、大容量、多業(yè)務的WDM網絡已經成為光通信領域中的一個重大問題。WDM網絡節(jié)點處采用光分插復用器（OADM）或光交叉連接設備（OXC）在光層建立光連接，即光通道（optical

path），為高層的多個邏輯電網絡提供了高速、大容量的信息傳送平臺。光通道的建立，要求在傳送網的物理結構中選擇一條由業(yè)務源點到宿點的路由，并為其分配一定的波長信道（參見圖1.1）。考慮到波長資源的重利用以及提高網絡的阻塞性能，優(yōu)化光通道的選路和波長分配（Routing

and

Wavelength

Assignment

—RWA）方案成為光通道層設計的核心問題。RWA解決如何尋找一條合適的光通道并合理地分配通道所使用的波長，使有限的資源充分發(fā)揮作用，以提供盡可能大的通信容量。2.RWA算法的分類WRON被認為是構建下一代光網絡的候選方案之一。但是由于網絡資源有限(如波長數(shù)、收發(fā)器數(shù)目等)，不可能在網絡中為每一節(jié)點對都建立一條直接相連的光路，因此針對不同的網絡需求，需要考慮對現(xiàn)有可用資源進行高效利用和優(yōu)化設計。WRON的核心問題是優(yōu)化設計光路的選路和波長分配，尋找一條合適的光路并為之合理地分配波長，使有限的資源充分發(fā)揮作用，以提供盡可能大的通信容量。根據光通道連接請求的特點，可以把RWA問題分成靜態(tài)和動態(tài)兩類。(1)靜態(tài)RWA(SRWA)問題：網絡的業(yè)務類型是靜態(tài)的，而且當所有連接建立好之后，連接將保持不變。光通道連接請求是預先給出的，因此要求離線計算路由和分配波長，而不需要實時計算。SR—WA問題的研究適合廣域網(或骨干網)，因為對于廣域網來說，其業(yè)務流量基本是確定的。SRWA的輸出結果是所有的源一目的節(jié)點對之間的光通道的路由以及給這些光通道分配的波長。(2)動態(tài)RWA(DRWA)問題：光通道連接請求是逐條提出的，而且一條光通道持續(xù)一段時間后又被拆除，因此需要為每一條光通道做實時RWA計算。對于DRWA問題，對光通道建立請求的處理通常有兩種策略：可重構型策略和不可重構型策略。所謂可重構型策略，就是當網絡擁塞發(fā)生的時候，光網絡的邏輯拓撲可以進行重構，以消除擁塞情況。但是這樣的操作可能會中斷很多現(xiàn)有的連接，而且需要對網絡節(jié)點之間的光通道進行大量的調整(拆除或者重新建立)，因此不適合大規(guī)模的網絡。而不可重構型策略，則在擁塞發(fā)生的時候不能重構光通道，只能拒絕該請求。圖圖SEQ圖\*ARABIC1RWA算法的分類

表1典型RWA算法序號算法名稱時間研究機構說明1固定路由選路(FR)法2008北京交通大學光波技術研究所解決路由選擇子問題2固定備用路由選路(FAR)法2008北京交通大學光波技術研究所解決路由選擇子問題3自適應選路(AR)法2008北京交通大學光波技術研究所解決路由選擇子問題4整數(shù)線性規(guī)劃(ILP)法2008北京交通大學光波技術研究所解決路由選擇子問題5路由擴展方法2008北京交通大學光波技術研究所解決路由選擇子問題6隨機分配(R)算法2009河北工程大學基于局部信息的波長分配算法7首次命中(FF)算法2009河北工程大學基于局部信息的波長分配算法8最大使用(MU)算法：2009河北工程大學基于全局資源信息的波長分配算法9最小使用(LU)算法2009河北工程大學基于全局資源信息的波長分配算法10最小乘積(MP)算法2009河北工程大學基于全局光通道信息的波長分配算法11最輕承載(LL)算法2009河北工程大學基于全局光通道信息的波長分配算法12最大總和(MS)算法2009河北工程大學基于全局光通道信息的波長分配算法13最小影響(LI)算法2009河北工程大學基于全局光通道信息的波長分配算法14相對容量損失(RCL)算法2009河北工程大學基于全局光通道信息的波長分配算法15頂點著色算法、啟發(fā)式算法16遺傳算法和緊急搜啟發(fā)式算法17索算法等啟發(fā)式算法2.1固定路由選路(FR)法：選路是事先進行的，網絡拓撲結構已知后，按照標準最短路徑算法(如Dijkstra算法和Bellman-Ford算法)為每個節(jié)點對分配固定的光路。當光路請求到達時，源、目的節(jié)點對之間的通信連接總是建立在預定好的路由上。這種方法的優(yōu)點是可以把RwA問題簡化為波長分配問題，從而大大簡化網絡的控制和管理。缺點是網絡性能較差、阻塞率較高。另外，該算法中網絡不具備鏈路故障恢復能力。2.2固定備用路由選路(FAR)法：FAR的核心思想是為每個節(jié)點對預先確定多條備用路由，并按一定的優(yōu)先級順序排列。排在最前面的稱為主路由，其他的視為備用路由。當業(yè)務到達時，按照工作路由建立光通路，當工作路由己被占用或失效時，選擇次優(yōu)路由。與固定路由方案相比，網絡的阻塞率大大降低，網絡具有故障恢復能力，但時間復雜度相對較高。2.3自適應選路(AR)法：AR算法中路由根據網絡的狀態(tài)動態(tài)地確定。它的實現(xiàn)可采用以下兩類方法，第～類是預先為節(jié)點對之間確定多條備用路由，與固定、備用路由方案類似。第二類方法是不預先為節(jié)點對確定備選路由，當連接請求到達時根據網絡狀態(tài)為其確定路由。AR業(yè)務請求的阻塞率同F(xiàn)R和FAR相比最低，但網絡的控制和管理比較復雜，時間復雜度也大大提高。2.4整數(shù)線性規(guī)劃(ILP)法：通常分為基于流的II。P和基于通道的ILP?；舅悸肥牵毫袑憙?yōu)化目標方程一列寫約束條件方程一求解線性規(guī)劃。這里可以利用現(xiàn)有的線性規(guī)劃軟件工具(Lingo)對光網絡拓撲設計的ILP方程進行求解，最終求得優(yōu)化路由的方法。利用ILP選路靈活，網絡可以具有或不具有故障恢復機制，但是這種方法只適用于規(guī)模較小的網絡。2.5路由擴展方法： 該方法是在一段鏈路中插入一個節(jié)點，用新節(jié)點與原鏈路兩端節(jié)點構成的兩段鏈路來替換原來的一段鏈路，這樣就構成了一個新路由，利用逐步擴展思想來構造節(jié)點之間所有的可能連接方式。此方法既可以用于網絡的實際拓撲，也可以用于網絡的虛拓撲。這種方法對于業(yè)務的恢復路由計算速度比較快，但路由擴展方法只是一種局部的方法，不具有全局性。2.6基于局部信息的波長分配算法2.6.1隨機分配(R)算法： 首先搜索所有波長的集合，找出可用波長集，再從中隨機選擇波長分配給光通道。2.6.2首次命中(FF)算法： 將波長在可用波長集中按固定順序排列，對新到達的連接請求要建立的光通路，每次選擇波長時均按固定順序選擇可用波長，并將選到的可用波長分配給路由。2．7基于全局資源信息的波長分配算法2.7.1最大使用(MU)算法： 首先統(tǒng)計全網中所有波長的使用率，然后優(yōu)先選擇使用率最高的可用波長。這種算法有利于將流量集中在少數(shù)波長上，這樣可以減少網絡的波長需求。2.7.2最小使用(LU)算法： 首先統(tǒng)計全網中的所有波長的使用率，然后選擇使用率最低的可用波長。這種算法的出發(fā)點是使網絡流量均勻分攤到各個波長上。2.8基于全局光通道信息的波長分配算法2.8.1最小乘積(MP)算法： 優(yōu)先選擇能使光通道的所有鏈路占用某波長的光纖總數(shù)乘積項最小的且編號較低的波長。當每條鏈路的光纖數(shù)目為1時，MP算法就蛻化為FF算法。2.8.2最輕承載(LL)算法： 將最空閑的波長分配給最繁忙的鏈路段。2.8.3最大總和(MS)算法： 該方法使得選擇該波長后，全網的其他通道的剩余可用通道數(shù)目總和最大。2.8.4最小影響(LI)算法： 選擇該波長后，對全網其他通道的影響(相關通道造成的瓶頸總和)最小。2.8.5相對容量損失(RCL)算法： 該方法類似于MS算法，也是針對提升網絡其他鏈路的空閑容量。MS算法只是致力于將網絡其他鏈路的絕對空閑容量最大化，而RCL算法則致力于將相對空閑容量最大化。2.7啟發(fā)式算法3.結論 WRON被認為是實現(xiàn)未來高速率、大容量全光網絡的有效的解決方案。它以一個波長為交換粒度，采用WDM技術和波長路由技術，通過波長進行端到端之間的路由。但由于在WRON中，網絡單元的功能、物理傳輸性能以及實際可使用的網絡資源受到限制，在網絡的所有接人節(jié)點之間都建立直接的光通道連接是非常困難的。所以，為了合理進行網絡優(yōu)化設計，有效