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

摘要：文章針對靈活速率光信道數據單元(ODUflex)以及帶寬可變光正交頻分復用(OFDM)兩種光網絡分別提出路由與速率分配和路由與頻譜分配課題。該課題將降低系統總能耗作為最優化目標，采用最優化軟件ILOG CPLEX進行仿真，分別提出了相應的啟發式算法，并將最優化結果同啟發式算法的結果進行了性能上的比較與討論。

關鍵詞：帶寬可變光正交頻分復用；路由與頻譜分配；路由與波長分配

當前，數據業務爆炸式增長，計算機互聯網流量迅猛增加，人們對網絡帶寬和容量的需求持續快速增長。通信網絡所承載的業務逐漸從文件傳輸(FTP)、網頁瀏覽(WWW)等通信方式轉變成P2P下載、網絡視頻點播等傳輸容量大、帶寬需求高的通信方式。為了滿足帶寬和容量指數增長的需求，各種光復用技術被廣泛應用。

光復用技術主要有波分復用、光時分復用和光碼分復用技術。本文主要研究靈活速率光信道數據單元(ODUflex)、波分復用(WDM)和帶寬可變光正交頻分復用(OFDM)3種光網絡，其中ODUflex采用光時分復用技術。ODUflex可根據業務速率進行匹配，使得客戶信號正好映射進入載荷區，占用高階K級光信道數據單元(ODUk)中最少數量的時隙，使剩下的時隙能夠承載其他業務，有效提高網絡帶寬利用率。混合速率WDM光網絡采用波分復用技術，相比單速率WDM網絡，混合速率WDM網絡能提供10G、40G和100G 3種信道速率可供選擇，具有一定的靈活性。帶寬可變光OFDM網絡采用類似于波分復用的多子載波調制技術，將高速數據信號分成多路低速數據信號，并調制到正交子載波上進行并行傳輸，能夠明顯提高系統頻譜利用率。帶寬可變光OFDM子載波數量根據業務請求大小動態調整，具有良好的顆粒度和靈活性。

伴隨著傳輸流量爆炸式地增長，通信網絡系統能耗急劇增長。在不久的將來，通信網絡的能耗問題將成為世界范圍內亟待解決的問題。巨大的能耗不僅會消耗地球上緊缺的資源，引起環境污染和氣候變化，同時會對網絡運營商的成本支出產生很大影響。如何更好地規劃網絡資源，在滿足業務需求的情況下降低能耗，是重要的研究課題。

1、ODUflex光網絡

光信道數據單元(ODU)是光傳送網中裝載單元信號的容器。在光傳送網中，客戶信號首先映射進入ODUk，然后在插入傳輸頭部后在合適的波長上進行傳輸。傳統ODU根據速率不同分為3種：2.5 Gbit/s(k=I)、10Gbit/s(k=2)、40Gbit/s(k=3)。為了能夠更好地傳輸各種新老客戶信號，引入了ODU₀、ODU₄以及能夠靈活調整帶寬的ODUflex，使得復用層次由原先的兩層復用結構：ODU₁－ODU₂－ODU₃更新成為4層復用結構：ODU₀－ODU₁－ODU₂－ODU₃－ODU₄。

隨著網絡的高速發展，出現了大量新的客戶信號，且其中的大多數都不能直接映射進入現有ODU_k，不產生明顯的帶寬損失，而每次定義一個新的ODU是不實際的。ODUflex能通過調節自身容器的大小，與業務速率進行匹配，僅占用高階ODUk最少數量的時隙，使剩下的時隙能夠承載其他業務，有效提高了帶寬利用率。

1.1 路由與速率分配問題

當業務請求到達時，光傳送網需要首先為每條業務分配路由和每條路由上的速率，然后由光傳送網的信令負責光通路的建立，達到傳送業務的目的。一般可將路由和速率分配問題分成兩個階段：在源節點和目的節點之間分配路由，為每條路由分配速率。

路由與速率分配問題線性規劃的最優化目標：假設系統總能耗由調制能耗和傳輸能耗兩部分組成，總能耗=調制能耗+傳輸能耗，并假設調制能耗和節點輸出速率成正比，傳輸能耗和節點輸出速率和光路長度成正比。

1.2 路由選擇策略

路由選擇策略主要有3種：

(1)固定路由

固定路由選路策略的思路是對任意節點對間確定一條固定的可用路由，可通過線下計算確定，一般由最短路徑算法確定，如Floyd算法和Dijkstra算法。

當業務達到時，在固定路由上分配速率或頻譜，若無可用速率或頻譜，則該業務請求被阻塞。這種方案的優點是分配速度快，缺點是阻塞率高，并且因為沒有可替代路由，不具備鏈路故障恢復能力。

(2)固定備用路由

固定備用路由選路策略的思路是對任意節點對間確定多條可用路由，其中一條為主路由，其他為備用路由，并按規則進行優先級排序，一般為最短路優先。

當業務達到時，首先使用主路由，當其阻塞時，再依次使用備用路由。相對于固定路由選擇策略，這種方案分配速度同樣比較快，相對不太容易阻塞。因為具備可替代路由，具備鏈路故障恢復能力。

(3)自適應性路由

自適應性路由選路策略的思路是根據當前網絡狀態動態的選擇路由，有兩種實現方案：

(a)受限的自適應路由。預先確定一組無序的備選路由，根據業務請求和當前的網絡狀態選擇其中一條最適合的路由。

(b)非受限的自適應路由。無備選路由，完全動態地選擇路由。相對于前兩種路由選擇策略，這種方案的阻塞率最低，具有鏈路故障恢復能力，但時間復雜度也大大提高。

1.3 路由與速率分配問題啟發式算法

在啟發式算法中首先對業務進行排序，然后按照排序為每條業務請求分配路由和速率。路由分配采用固定備用路由策略。業務排序策略有：按業務流量進行排序、按業務路經進行排序。

(1)按業務流量進行排序

按業務流量進行排序通常按業務的流量從大到小進行排序。首先滿足流量較大的業務，對其分配路由和網絡資源。

該策略優勢在于分配成功率高，開始階段網絡資源較多，適合大流量業務分配；隨著業務的分配，網絡資源逐漸變少，適合小流量業務分配，整體而言阻塞率較低。

(2)按業務路經進行排序

按業務流量進行排序通常按業務最短路路由長度或跳數從大到小進行排序。首先滿足路由長度長或跳數多的業務，對其分配路由和網絡資源。

該策略優勢在于路由長度較長或跳數較多的業務對網絡資源的占用要求比較高，應當預先使其得到滿足，同樣，整體而言阻塞率較低。

路由與速率分配問題的啟發式算法主要分為4步：

步驟1——采用Dijkstra算法計算每對節點對間的主路由和備用路由。

步驟2——按照業務流量和業務路經對每對節點間的業務從大到小進行排序。

步驟3——按照業務排序依次為每條業務先按照主路由分配路由和速率。若阻塞，則使用備用路由，如果全部備用路由使用失敗，則報錯并返回，否則執行步驟4。

步驟4——計算系統總能耗。

啟發式策略包括3種：

啟發式策略1——按業務流量對業務進行排序。

啟發式策略2——按業務主路由長度對業務進行排序。

啟發式策略3——按業務各路由鏈路的使用頻率對業務進行排序。

1.4 仿真結果

(1)ODUflex4點網絡拓撲

圖l所示為4點拓撲網絡。圖2所示為路由與速率分配問題4點拓撲網絡仿真結果示意圖。

路由與速率分配問題4點拓撲網絡仿真結果分析：

(a)當流量較小時，各種啟發式策略均能得到全局最優解。這是因為各項業務均分配均能滿足最短路徑路由分配而不產生阻塞。

(b)當流量較大時，各種啟發式策略增幅較小(不超過20％)。啟發式策略1和啟發式3相對較好。

(2)ODUflex 24點拓撲網絡仿真

圖3所示為24點拓撲網絡。圖4所示為路由與速率分配問題24點拓撲網絡仿真結果示意圖。

路由與速率分配問題24點拓撲網絡仿真結果分析：

(a)當流量較小時，各種啟發式策略計算結果均相同，推測為全局最優解。因為此時各項業務平均分配均能滿足最短路徑路由分配而不產生阻塞。

(b)當流量較大時，啟發式策略l計算能耗最小，策略2、策略3均有較小增幅。當流量增大時策略3相對于策略1和2不容易阻塞，阻塞概率比較低。

(c)啟發式算法平均運算時間為66ms，運算效率高。

2、帶寬可變光OFDM網絡

當前，互聯網IP爆炸式的增長趨勢對傳輸容量和帶寬需求提出了更高要求。為了滿足爆炸式增長的業務，波分復用(WDM)技術被廣泛應用于提高光纖的傳輸容量。常見的混合速率WDM有10G、40G、100G。相比單速率WDM，混合速率WDM網絡能夠提供10G、40G、100G 3種信道速率進行選擇，因此具有一定的靈活性，但是帶寬粒度仍然較大。網絡中每個波長提供了極高容量，但沒有被利用的帶寬資源卻是一種極大的浪費。帶寬可變光OFDM網絡能夠很好地解決這個問題。OFDM使用多子載波調制。在發送端首先把高速數據信號轉換成并行的低速子數據流，然后調制到每個子信道上進行傳輸，并保證每個子信道之間的正交性；在接收端通過相關技術實現子信道的分離。其作為一種數字調制格式，由于每個子信道帶寬僅為原信道帶寬的一小部分，因此極大提高了網絡的頻譜利用率和系統的傳輸效率。

2.1 路由與波長分配問題

路由與波長分配問題主要包括兩個子問題：在源節點和目的節點之間分配路由、為每條路由分配波長。系統能耗的假設與前文相同。WDM光網絡需要考慮波長連續性，分配更加復雜。波長連續性是指因光交叉節點(OXC)通常沒有波長轉換能力，從而要求一條光路在OXC的人鏈路和出鏈路上分配相同的波長。問題主要分為3步：首先對業務進行排序，然后依次為業務分配路由，最后為分配的路由分配波長。

具體到實際的WDM網絡，假設使用偏振(Polarization)正交移相鍵控(QPSK)調制方式，則10G、40G和100G 3種速率的實際使用帶寬分別為2.5 GHz、10 GHz和25 GHz。因為WDM的信道間隔頻率是50 GHz，所以這3種速率的所需占用帶寬均為50GHz。

2.2 路由與頻譜分配問題

與路由與波長分配問題類似，路由與頻譜分配問題主要包括兩個子問題：在源節點和目的節點之間分配路由、為每條路由分配頻譜。問題主要可以分為3步解決：首先對業務進行排序，然后依次為業務分配路由，最后為分配的路由分配頻譜。頻譜分配策略有：隨機適應法、首次適應算法和最佳適應法。

和WDM中的光交叉連接相同，帶寬可變的光交叉連接一般沒有頻譜搬移能力，因此需要考慮頻譜連續性約束。

本文假設帶寬可變光交叉連接均不具備頻譜搬移能力。如果分配不能滿足頻譜連續性限制，連接請求將被阻塞。

具體到實際的光OFDM網絡，本文采用文獻中提出的正交頻段復用OFDM網絡。文獻中將OFDM信號分成多個子頻段，同時保證這些子頻段之間的正交性。光OFDM網絡每個子頻段的頻譜是6.4 GHz，提供21.4 Gbit/s數據速率，可以通過調整子頻段的數目產生與業務流量匹配的信號速率。根據ITU－TG.694.1中規定的WDM信道分配標準，信道的頻譜間隔為50 GHz，在C－Band中將有80個信道。假設每條光纖鏈路上可供分配的頻譜資源為4000GHz，則每條光纖鏈路上子頻率段的數目為625個。

2.3 路由與頻譜分配問題啟發式算法

在啟發式算法中首先對業務進行排序，然后按照業務排序依次為每條業務請求分配路由和頻譜。業務排序策略與路由與速率分配問題中的3種策略相同。頻譜分配策略主要包括3種。

(1)隨機適應法

隨機適應法首先遍歷所有可用資源，確定在選定路由上的可用資源的集合，再等概率地隨機選取一段。算法的時間復雜度低，但沒有考慮當前的網絡狀態。

(2)首次適應算法

首次適應算法將所有資源進行統一編號，再依次搜索，直到選擇第一段能滿足業務需求的資源來分配。該算法傾向于使用靠前的一段資源，保留了靠后的大塊空閑區便于以后分配。

(3)最佳適應算法

最佳適應算法將所有資源進行統一編號，再選取其中一段能滿足業務需求的且編號最小的資源來分配。該算法傾向于使用最小的一段資源，保留了完整的大塊空閑區便于以后分配。

路由與頻譜分配問題的啟發式算法包括6個步驟：

步驟1——采用Dijkstra算法計算每對節點對間的主路由和備用路由。

步驟2——按照業務流量和業務路經對每對節點對間的業務從大到小進行排序。

步驟3——按照業務排序依次為每條業務按主路由分配路由，盡可能滿足業務所需帶寬，若分配失敗，記錄分配失敗的流量。

步驟4——判斷業務分配成功否，若存在分配失敗的流量，按照主路由集合分配路由；若分配失敗，記錄分配失敗的流量。

步驟5——判斷業務分配成功否，若存在分配失敗的流量，按照備用路由順序分配路由；若全部備用路由分配失敗，則報錯并返回，否則執行步驟6。

步驟6——計算系統總能耗。

啟發式策略包括6種：

策略1A——采用頻譜分配首次適應法，并且按業務流量對業務進行排序。

策略2A——采用頻譜分配首次適應法，并且按業務主路由長度對業務進行排序。

策略3A——采用頻譜分配首次適應法，并且按業務各路由鏈路的使用頻率對業務進行排序。

策略1B——采用頻譜分配最佳適應法，并且按業務流量對業務進行排序。

策略2B——采用頻譜分配最佳適應法，并且按業務主路由長度對業務進行排序。

策略3B——采用頻譜分配最佳適應法，并按業務各路由鏈路的使用頻率對業務進行排序。

2.4 仿真結果

(1)波分復用與帶寬可變光OFDM比較

圖5所示為WDM光網絡與帶寬可變光OFDM網絡帶寬利用率比較。圖6所示為WDM光網絡與帶寬可變光OFDM網絡能耗比較。

仿真結果分析：

(a)在頻譜利用率方面帶寬可變光OFDM網絡具有絕對優勢。

(b)在能耗方面WDM光網絡具有一定微弱優勢。

(c)因為在光傳輸網中頻譜是相對緊缺的資源，應首先考慮。OFDM比WDM更具優勢。

(2)帶寬可變光OFDM 4點拓撲網絡仿真

圖7所示為路由與頻譜分配問題各種算法4點拓撲網絡仿真結果。

路由與頻譜分配問題4點拓撲網絡仿真結果分析：

(a)當流量較小時，各種啟發式策略均能得到全局最優解，這是因為各項業務分配均能滿足最短路徑路由分配而不產生阻塞。

(b)當流量較大時，各種啟發式策略增幅較小(不超過15％)。綜合而言，采用按各路由鏈路的使用頻率對業務進行排序效果較好，各種頻譜分配方法對計算結果影響不大。

(c)最優化平均運算時間為117 s，啟發式算法平均運算時間為168 p，s，運算速度約為最優化的7×105倍，運算效率極高。

(3)帶寬可變光OFDM 24點拓撲網絡仿真

圖8所示為帶寬可變光OFDM 24點拓撲網絡仿真結果。

路由與頻譜分配問題24點拓撲網絡仿真結果分析：

(a)當流量較小時，各種啟發式策略計算結果均相同，推測為全局最優解，因為此時各項業務分配均能滿足最短路徑路由分配而不產生阻塞。

(b)當流量較大時，各種啟發式策略阻塞概率大致相同，同時使用按業務各路由鏈路的使用頻率對業務進行排序和首次適應算法相對較好。

(c)啟發式算法平均運算時間為89 ms，運算效率高。

3、結束語

當前，隨著數據業務爆炸式的增長和各種新業務的出現，計算機互聯網面臨兩大問題，即帶寬和容量的需求持續快速增長和各種業務的不同粒度和傳輸信道帶寬容量難以匹配。ODUflcx光網絡和帶寬可變光OFDM網絡能夠較好地解決這兩大問題，是本文研究的重點。伴隨著傳輸流量的急劇增長，網絡能耗增加迅猛，如何優化網絡資源分配，降低能耗是本文研究的核心。

本文針對ODUflex以及帶寬可變光OFDM兩種光網絡分別提出路由與速率分配問題和路由與頻譜分配問題，給出了最優化及啟發式算法的仿真比較。