可變帶寬光網絡路由與資源分配研究.doc

可變帶寬光網絡路由與資源分配研究摘要：文章針對靈活速率光信道數據單元(ODUflex)以及帶寬可變光正交頻分復用(OFDM)兩種光網絡分別提出路由與速率 分配和路由與頻譜分配課題該課題將降低系統總能耗作為最優 化目標，采用最優化軟件ILOG CPLEX進行仿真，分別提出瞭相應的啟發式算法，並將最優化結果同啟發式算法的結果進行瞭 性能上的比較與討論關鍵詞：帶寬可變光正交頻分復用；路由與頻譜分配；路由 與波長分配當前，數據業務爆炸式增長，計算機互聯網流量迅猛增加， 人們對網絡帶寬和容量的需求持續快速增長通信網絡所承載的 業務逐漸從文件傳輸(FTP)、網頁瀏覽(WWW)等通信方式轉變成P2P下載、網絡視頻點播等傳輸容量大、帶寬需求高的通信方式為瞭滿足帶寬和容量指數增長的需求，各種光復用技術被廣泛應光復用技術主要有波分復用、光時分復用和光碼分復用技術本文主要研究靈活速率光信道數據單元(0DUflex)、波分復用(WDM)和帶寬可變光正交頻分復用(OFDM)3種光網絡，其中ODUflex采用光時分復用技術ODUflex可根據業務速率進行匹配，使得客戶信號正好映射進入載荷區，占用高階K級光信道數 據單元(ODUk)中最少數量的時隙，使剩下的時隙能夠承載其他 業務，有效提高網絡帶寬利用率。

混合速率WDM光網絡采用波 分復用技術，相比單速率WDM網絡，混合速率WDM網絡能提 供10G. 40G和100G 3種信道速率可供選擇，具有一定的靈活性帶寬可變光OFDM網絡采用類似於波分復用的多子載波調 制技術，將高速數據信號分成多路低速數據信號，並調制到正交 子載波上進行並行傳輸，能夠明顯提高系統頻譜利用率帶寬可 變光OFDM子載波數量根據業務請求大小動態調整，具有良好 的顆粒度和靈活性伴隨著傳輸流量爆炸式地增長，通信網絡系統能耗急劇增長在不久的將來，通信網絡的能耗問題將成為世界范圍內亟待解決 的問題巨大的能耗不僅會消耗地球上緊缺的資源，引起環境污 染和氣候變化，同時會對網絡運營商的成本支出產生很大影響如何更好地規劃網絡資源，在滿足業務需求的情況下降低能耗， 是重要的研究課題K ODUflex光網絡光信道數據單元(ODU)是光傳送網中裝載單元信號的容器在光傳送網中，客戶信號首先映射進入ODUk ,然後在插入傳輸 頭部後在合適的波長上進行傳輸傳統ODU根據速率不同分為3 種：2.5Gbit/s（k二I）、10Gbit/s（k=2）. 40Gbit/s（k二3）為瞭能夠更好地傳輸各種新老客戶信號，引入瞭ODUO、ODU4以及能夠 靈活調整帶寬的ODUflex ,使得復用層次由原先的兩層復用結構:ODU1 - ODU2・ODU3更新成為4層復用結構:ODUO -0DU1 - 0DU2 - ODU3 - ODU4隨著網絡的高速發展，出現瞭大量新的客戶信號，且其中的 大多數都不能直接映射進入現有ODUk ,不產生明顯的帶寬損失，而每次定義一個新的ODU是不實際的。

ODUflex能通過調 節自身容器的大小，與業務速率進行匹配，僅占用高階ODUk 最少數量的時隙，使剩下的時隙能夠承載其他業務，有效提高瞭 帶寬利用率1.1路由與速率分配問題當業務請求到達時，光傳送網需要首先為每條業務分配路由 和每條路由上的速率，然後由光傳送網的信令負責光通路的建 立，達到傳送業務的目的一般可將路由和速率分配問題分成兩 個階段：在源節點和目的節點之間分配路由，為每條路由分配速路由與速率分配問題線性規劃的最優化目標：假設系統總能 耗由調制能耗和傳輸能耗兩部分組成*息能耗二調制能耗+傳輸能 耗，並假設調制能耗和節點輸出速率成正比，傳輸能耗和節點輸 出速率和光路長度成正比1.2路由選擇策略路由選擇策略主要有3種:(1) 固定路由固定路由選路策略的思路是對任意節點對間確定一條固定的 可用路由，可通過線下計算確定，一般由最短路徑算法確定，如Floyd算法和Dijkstra算法當業務達到時，在固定路由上分配速率或頻譜，若無可用速 率或頻譜，則該業務請求被阻塞這種方案的優點是分配速度快, 缺點是阻塞率高，並且因為沒有可替代路由，不具備鏈路故障恢 復能力(2) 固定備用路由固定備用路由選路策略的思路是對任意節點對間確定多條可 用路由，其中一條為主路由，其他為備用路由，並按規則進行優 先級排序，一般為最短路優先當業務達到時，首先使用主路由，當其阻塞時，再依次使用 備用路由。

相對於固定路由選擇策略，這種方案分配速度同樣比 較快，相對不太容易阻塞因為具備可替代路由，具備鏈路故障 恢復能力(3) 自適應性路由自適應性路由選路策略的思路是根據當前網絡狀態動態的選 擇路由，有兩種實現方案:(a) 受限的自適應路由預先確定一組無序的備選路由，根據業務請求和當前的網絡狀態選擇其中一條最適合的路由(b) 非受限的自適應路由無備選路由，完全動態地選擇路由相對於前兩種路由選擇策略，這種方案的阻塞率最低，具有鏈路 故障恢復能力，但時間復雜度也大大提高1.3路由與速率分配問題啟發式算法在啟發式算法中首先對業務進行排序，然後按照排序為每條 業務請求分配路由和速率路由分配采用固定備用路由策略業 務排序策略有：按業務流量進行排序、按業務路經進行排序(1)按業務流量進行排序按業務流量進行排序通常按業務的流量從大到小進行排序首先滿足流量較大的業務，對其分配路由和網絡資源該策略優勢在於分配成功率高，開始階段網絡資源較多，適 合大流量業務分配；隨著業務的分配，網絡資源逐漸變少，適合 小流量業務分配，整體而言阻塞率較低(2)按業務路經進行排序按業務流量進行排序通常按業務最短路路由長度或跳數從大 到小進行排序。

首先滿足路由長度長或跳數多的業務，對其分配 路由和網絡資源該策略優勢在於路由長度較長或跳數較多的業務對網絡資源 的占用要求比較高，應當預先使其得到滿足，同樣，整體而言阻 塞率較低路由與速率分配問題的啟發式算法主要分為4步：步驟4--采用Dijkstra算法計算每對節點對間的主路由和備用路由步驟2--按照業務流量和業務路經對每對節點間的業務從大 到小進行排序步驟3--按照業務排序依次為每條業務先按照主路由分配路由和速率若阻塞，則使用 備用路由，如果全部備用路由使用失敗，則報錯並返回，否則執 行步驟4步驟4--計算系統總能耗啟發式策略包括3種：啟發式策略按業務流量對業務進行排序啟發式策略2—按業務主路由長度對業務進行排序啟發式策略3—按業務各路由鏈路的使用頻率對業務進行排1.4仿真結果(1) ODUflex4點網絡拓撲圖I所示為4點拓撲網絡圖2所示為路由與速率分配問題4點拓撲網絡仿真結果示意路由與速率分配問題4點拓撲網絡仿真結果分析:(a)當流量較小時，各種啟發式策略均能得到全局最優解這是因為各項業務均分配均能滿足最短路徑路由分配而不產生阻(b)當流量較大時，各種啟發式策略增幅較小(不超過20%)。

啟發式策略1和啟發式3相對較好(2) ODUflex 24點拓撲網絡仿真3所示為24點拓撲網絡4所示為路由與速率分配問題24點拓撲網絡仿真結果示意圖路由與速率分配問題24點拓撲網絡仿真結果分析(a) 當流量較小時，各種啟發式策略計算結果均相同，推測為全局最優解因為此時各項業務平均分配均能滿足最短路徑路由 分配而不產生阻塞(b) 當流量較大時，啟發式策略I計算能耗最小，策略2、策 略3均有較小增幅當流量增大時策略3相對於策略1和2不 容易阻塞，阻塞概率比較低(c) 啟發式算法平均運算時間為66ms ,運算效率高2、帶寬可變光OFDM網絡當前，互聯網IP爆炸式的增長趨勢對傳輸容量和帶寬需求提 出瞭更高要求為瞭滿足爆炸式增長的業務，波分復用(WDM) 技術被廣泛應用於提高光纖的傳輸容量常見的混合速率WDM 有10G、40G、100Go相比單速率WDM ,混合速率WDM網 絡能夠提供10G、40G、100G3種信道速率進行選擇，因此具 有一定的靈活性，但是帶寬粒度仍然較大網絡中每個波長提供 瞭極高容量，但沒有被利用的帶寬資源卻是一種極大的浪費帶 寬可變光OFDM網絡能夠很好地解決這個問題OFDM使用多 子載波調制。

在發送端首先把高速數據信號轉換成並行的低速子 數據流，然後調制到每個子信道上進行傳輸，並保證每個子信道 之間的正交性；在接收端通過相關技術實現子信道的分離其作 為一種數字調制格式，由於每個子信道帶寬僅為原信道帶寬的一 小部分，因此極大提高瞭網絡的頻譜利用率和系統的傳輸效率2.1路由與波長分配問題路由與波長分配問題主要包括兩個子問題：在源節點和目的 節點之間分配路由、為每條路由分配波長系統能耗的假設與前 文相同WDM光網絡需要考慮波長連續性，分配更加復雜波 長連續性是指因光交叉節點(OXC)通常沒有波長轉換能力，從而 要求一條光路在OXC的人鏈路和出鏈路上分配相同的波長問 題主要分為3步：首先對業務進行排序，然後依次為業務分配路 由，最後為分配的路由分配波長具體到實際的WDM網絡，假設使用偏振(Polarization)正交 移相鍵控(QPSK)調制方式，則10G. 40G和100G3種速率的 實際使用帶寬分別為2.5 GHz、10 GHz和25 GHz因為WDM的信道間隔頻率是50 GHz ,所以這3種速率的所需占用帶寬均為 50GHz2.2路由與頻譜分配問題與路由與波長分配問題類似，路由與頻譜分配問題主要包括 兩個子問題：在源節點和目的節點之間分配路由、為每條路由分 配頻譜。

問題主要可以分為3步解決：首先對業務進行排序，然 後依次為業務分配路由，最後為分配的路由分配頻譜頻譜分配 策略有：隨機適應法、首次適應算法和最佳適應法和WDM中的光交叉連接相同，帶寬可變的光交叉連接一般 沒有頻譜搬移能力，因此需要考慮頻譜連續性約束本文假設帶寬可變光交叉連接均不具備頻譜搬移能力如果分配不能滿足頻譜連續性限制，連接請求將被阻塞具體到實際的光OFDM網絡，本文采用文獻中提出的正交頻 段復用OFDM網絡文獻中將OFDM信號分成多個子頻段，同 時保證這些子頻段之間的正交性光OFDM網絡每個子頻段的 頻譜是6.4 GHz ,提供21.4 Gbit/s數據速率，可以通過調整子頻段的數目產生與業務流量匹配的信號速率根據ITU・TG.694.1中規定的WDM信道分配標準，信道的頻譜間隔為50GHz ,在C・Band中將有80個信道假設每條光纖鏈路上可供 分配的頻譜資源為4000GHz ,則每條光纖鏈路上子頻率段的數目為625個2.3路由與頻譜分配問題啟發式算法在啟發式算法中首先對業務進行排序，然後按照業務排序依 次為每條業務請求分配路由和頻譜業務排序策略與路由與速率 分配問題中的3種策略相同。

頻譜分配策略主要包括3種(1) 隨機適應法隨機適應法首先遍歷所有可用資源，確定在選定路由上的可 用資源的集合，再等概率地隨機選取一段算法的時間復雜度低, 但沒有考慮當前的網絡狀態(2) 首次適應算法首次適應算法將所有資源進行統一編號，再依次搜索，直到 選擇第一段能滿足業務需求的資源來分配該算法傾向於使用靠 前的一段資源，保留瞭靠後的大塊空閑區便於以後分配(3) 最佳適應算法最佳適應算法將所有資源進行統一編號，再選取其中一段能 滿足業務需求的且編號最小的資源來分配該算法傾向於使用最 小的一段資源，保留瞭完整的大塊空閑區便於以後分配路由與頻譜分配問題的啟發式算法包括6個步驟:步驟-采用Dijkstra算法計算每對節點對間的主路。