軟件定義光網絡中的高效路由機制研究

俞慧慧

(安徽電子信息職業技術學院 信息與智能工程系，蚌埠 233000)

光纖的超大容量的特性使得光網絡在網絡數據傳輸和轉移方面一直以來扮演著重要的角色。然而，由于缺乏靈活的管理和合理的調度分配機制，大部分的光波長資源都處于被浪費的狀態[1]。此外，傳統的光傳輸網絡極度依賴人工的干預和管理。軟件定義網絡(Software-Defined Networking, SDN)提出為公共基礎設施的管理建立一個抽象且靈活的控制平面，用于對底層設備進行統一管理和配置[2-3]。盡管SDN已經被廣泛研究并且已有成果應用于傳統IP網絡中，對于軟件定義光網絡(Software-Defined Optical Networking, SDON)的研究目前還比較少。SDON將光網絡的快速傳輸能力與SDN的靈活控制能力相結合，既提高了光傳輸網絡的能力、降低了能耗，也為底層設備的管理提供了靈活且集中的控制機制。這種結合所獲得的優勢能夠在一定程度上打破當前光網絡的研究瓶頸，進一步推動對光網絡的研究[4]。

在傳統的波分復用(Wavelength Division Multiplexed, WDM)網絡中, 光纖中的所謂帶寬資源通常被分為不同的頻率段，它們被稱為波長(Wavelength)。通過在網絡中重新配置光交換機，我們能夠在不同節點終端上選擇特定的波長作為光電交換或者光波長路由的媒介。對于一個具有多個節點的網絡，理想情況是建立多條光路徑。這樣可以保證任意一對節點之間的突發流量請求都能得到滿足。然而實際的情況并沒有那么多的波長資源供我們去使用，這就限制了我們能夠建立的光路徑數量。傳統AON中的波長路由問題已經得到了較好地解決，對此類問題進行了優化，同時提出一系列的啟發式算法來求解多路徑路由波長選擇問題。然而，針對SDON背景下的多徑長路由的路由波長選擇問題研究較少，因此有必要對其進行深入研究。

將SDN的思想引入到AON中，基于SDN的全局資源視圖和控制機制，能夠對底層的光設備進行統一的配置和管理，使其具有高度的協同工作能力。同時，數據鏈路的增加引起端到端的路徑延遲，也稱為差分時延(Differential Delay, DD)。針對這些問題，在SDON中提出一種差分時延約束多路徑路由波長選擇算法。該方法不僅可以避免單路徑路由限制和可能的路徑障礙，同時還可以提高網絡吞吐量和利用率。該方法將多路徑優化問題，轉變為解決非相交路徑基數M最大化問題和平均端到端傳輸延遲最小化問題。采用迭代方法和整數規劃，求解M最小值，并根據M值確定最優路由波長。

1 軟件定義光網絡(SPON)架構

(SDON)尋求利用靈活的SDN控制為底層光網絡基礎設施提供網絡應用能力。圖1為SDON架構。這個架構的控制核心是一個抽象概念，通過擴展OpenFlow (OF) 控制器和協議實現。這個機制支持底層異構光傳輸和數據包集成。這個架構包括3個組件，分別為硬件抽象層，OF擴展層和SDN應用層。硬件抽象層的作用在于隱藏底層異構傳輸網絡資源的細節，同時為硬件狀態配置提供編程接口；在OF擴展中，SDON采用多維流表來表示OF使能交換。每個表中包括詳細的匹配域、計數器和一系列附屬動作。

圖1 軟件定義光網絡架構

2 問題描述及模型引入

SDON中路由波長的選擇是指光信號經過網絡節點通過一定的波長進行傳播。多路徑路由是一種網絡功能，它控制數據流在多個物理路徑之間從源到目的地的分裂。在多路徑路由規劃算法中，主要的研究重點在于從給定的源節點到目標節點間的路由路徑的確定，路由路徑集的完備性直接影響請求路由的波長選擇。在相同的差分時延束下，找到M個鏈路不相交的S-T路徑集，最小化平均端到端延遲L，我們稱之為復合模型。為了簡化對復合模型的求解過程，我們將復合模型公式轉換成一個由混合整數規劃公式(Mixed-Integer Linear Programming， MILP)的子問題進行迭代求解，在復合模型中的單路徑路由中強制添加差分時延約束會使得與路由路徑相關的路由循環出現，這種循環出現問題會導致路徑判斷誤差。因此，對復合模型進行如下定量描述。

使用無向圖G(v,ε)表示的由各節點經過一定的連接方式組成的網絡，其中，v和ε分別表示的是各個節點組成的節點集合以及節點之間的無向連接。每個連接鏈路e∈ε與連接其節點的兩個相對定向弧e′和e″相關聯。所有這類弧的集合由η表示(注意，由此產生的有向圖G(v,Ν)是有向且是雙向的)。弧η的源節點和目標節點分別用A(η)和B(η)表示。加權值ωη表示弧η∈Ν的延遲程度參數。弧σ+(v)和σ-(v)集合分別表示從節點v∈V發出的弧的傳出方向和指向v的弧的傳入方向。對復合模型的求解的關鍵點是在給定的差分時延以及端到端的平均延遲上界α的條件下，求給定源節點A以及目標節點B之間的多路徑路由連接的最優解，并且能夠最大化不相交路徑M，之后根據確定的最多的不相交路徑使得端到端的平均延遲L最小化。

3 基于SDON的差分時延約束多路徑路由波長優化

多徑路由連接問題實際是有向圖G(v,N)從節點A到節點B的M個不相交路徑W的一個集合。我們采用4個參數來表達多徑路由連接請求，這4個參數分別為A，B，和Δ，M。其中，A和B分別為源節點和目的點，Δ是微分延遲上界，M是假定的不相交路徑數。提出的差分時延約束多路徑路由波長優化算法共包括3個部分：M值最大化、差分時延約束和路由波長選擇。

3.1 M值最大化

M值的最大化，可以充分提高算法解決網絡擁塞能力。不相交路徑的最大化可以為DD求解提供更大的解析空間，并一定程度提高網絡分發速度。我們將多徑路由連接累積延遲作為目標函數。在公式(1)中，φη為M中的傳輸延遲，xηm為流變量，m為路由跳數。φη和xηm的乘積表示累積延遲。在公式(1)的基礎上，我們提出6條約束條件，通過約束條件限定目標函數，從而獲得M最大值。用xηm的差值表示源節點A到目標節點B的M條路徑，如公式(2)所示。通過公式(3)，我們限定了路由路徑的不連接屬性。引入微分延遲上限，作為M條路徑的延遲上限，用公式(4)和公式(5)表示。為了獲得最優解，采用非負變量作為最優解下線，如公式(6)所示。其中，hvm表示從源節點A到v的每條路徑。公式(7)為hvm的約束條件。綜上，我們可以獲得M的最大優化值。

minimize∑η∈Ν∑m∈Mωηxηm，

(1)

(2)

∑m∈Mxe'm+xe''m≤1,e∈ε，

(3)

∑η∈Νωηxηm-∑η∈Νωηxμn≤Δ,m,n∈M,m

(4)

∑η∈Νωηxηn-∑η∈Νωηxμm≤Δ,m,n∈M,m

(5)

hb(η)k-ha(η)k≥1-M(1-xηm),η∈Ν,m∈M，

(6)

xηmbinary,hvm≥0.

(7)

3.2 差分延遲約束

差分延遲補償可以有效緩解和解決SDON中的環路和隔離環問題。為了實現差分延遲補償，我們假設網絡內部允許路由循環的存在。在3.1節的基礎上，我們增加2個限制變量和一個約束條件。通過新增加的變量和約束條件，解決路徑內循環問題，并實現差分延遲約束功能，從而最小化DD。

設集合Rηvm和rηm分別為人工流約束條件，用來對流變量進行約束。其中，Rηvm表示路徑W上的節點v到節點B的人工流值，rηm表示屬于路徑W的人流值。我們通過加強對xηm約束，去除網絡內路由循環問題，這種方式也可以避免孤立循環。流量變量的差分延遲限制公式為：

Rηvm≤xηm≤rvm,η∈Ν,v∈V{A,B},m∈M，

(8)

同時，路徑W上的流量守恒公式為：

(9)

通過約束條件，將xηm取值范圍限定在正整數范圍內，即xηm∈N+。由于引入了新的限制變量，我們需要將3.1節中公式(7)更新為：

xηmbinary,Rηvm·rvm≥0

，

(10)

至此，我們可以通過公式(8)～(10)，并結合3.1節公式(1)～(6)得到最小化的DD。

3.3 多路徑路由波長選擇

在完成3.1節和3.2節內容之后，我們可以得到差分約束條件下的基數M和最優的DD，根據網絡請求優先級排序，進行最優化路由和波長分配。這種分配方式可以對更高延遲請求實現波長配置的優先分配。盡可能滿足建立光路的高層次要求，提高光網絡資源的利用率，降低高等級請求的拒絕率。影響域內路由選路的主要因素有：(1)下一跳節點的程度；(2)距目標節點的距離；(3)在鏈路中占用波長的情況下，下一跳鏈路優先選擇波長更大且無波長轉換的鏈路；(4)請求級別越高，路由優先級越高。

4 實驗結果與數據分析

4.1 實驗條件設置和對比方法

假設SDON中沒有使用波長轉換器，并且每對鄰接節點之間都由兩條光纖所連接以構成雙向鏈路。另外，所有的光纖都包含相同的波長數目。采用14個節點的NSFNET拓撲作為仿真對象。并且基于該拓撲，對兩種情況進行仿真，分別為每條光纖中波長數為8，如圖2(a)所示；和波長數為16，如圖2(b)所示。

為了驗證文中算法的適應性以及合理性，選取了另外三種算法作為比較的對象，分別為固定路由(Fixed Routing, FR)、固定可選路由(Fixed Alternate Routing, FAR)和自適應路由(Adaptive Routing, AR)。其中，FR是一種比較直接的光網絡路由算法，它提前規劃好任意源目的節點對之間的路徑，一旦有流量請求到達，就會按照預先定義好的路徑進行轉發。該方法簡單，但是缺乏靈活性。FAR以FR為基礎，區別在于FR僅僅只為任意的源目的節點對規劃一條可用路徑，而FAR則會規劃多條，一旦發生阻塞或者斷路，FAR就會迅速切換到另外一條光通路上以減少損失。AR相對文中的靜態LPR而言，其本質屬于動態路由。任意的源目的節點對之間的路由都根據網絡當前狀態而制定。即對于同樣的源目的節點對，不同時刻它們之間的路由可能是不一樣的。

4.2 對比實驗結果及分析

分別使用這4種算法測試了在SDON環境下，隨著時間變化網絡的阻塞率(Blocking Probability, BP)，BP描述的是網絡整體的阻塞率。通常，我們會為每條光鏈路定一個閾值，超過這個閾值則可以判斷其處于擁塞的狀態。通過判斷整個網絡中的所有鏈路的狀態變能夠得到全局的網絡阻塞率。另外，使用Matlab工具來求解上述定義的LPR問題。

圖2對比了文中算法和另外幾種算法在解決光網絡中的路由問題時所產生的網絡擁塞隨時間變化的情況。通過觀察整體的結果形式可以發現，圖2(b)中的結果要明顯優于圖2(a)，原因很簡單，因為圖2(b)中的結果是通過仿真每條光纖中具有16條波長所得到的。相反，圖2(a)中的結果是基于每條光纖只含有8條波長。圖2(b)仿真使用的資源數量是圖2(a)的兩倍，因此更加利于網絡流量的傳播，降低阻塞率。此外，我們分別觀察圖2(a)和圖2(b)中的結果，會發現LPR都能夠取得很好的效果。這是因為LPR相對來說是一種靜態的策略，需要提前知曉流量的情況，并且基于線性規劃來進行集中式求解，這個過程相對耗時較長，這是LPR所需要克服的問題。

(a)波長數=8

(b)波長數=16

另外，還對比了各種算法對于波長利用的均衡性分析。也就是在建立光路徑的過程中，波長資源的使用是否平衡。這個指標從一定程度上也能夠反映出網絡中的擁塞情況。比如，一條波長如果使用次數過多，必然會造成其他波長使用率可能不高或者被閑置。在這種情況下，波長的使用不均衡勢必在某些特定情況下造成網絡中某些部分擁塞。同樣還是針對波長數分別為8和16的情況，假設任意的節點對之間都存在著流量，且每條流量對波長資源數量的需求都小于1。在此情況下進行仿真并記錄仿真過程中各條波長的使用次數，結果如表1所示。通過觀察表1中的數據，我們能夠發現：(1)LPR的波長總的使用次數相對要高一些，這說明LPR具有較好的波長利用率；(2)從波長使用次數的分布情況來看，基于LPR的波長負載相對要更均勻，這種優勢在波長數較多時表現得尤為明顯，如W=16時，各算法得到的波長負載情況就比W=8情況下要明顯。(3)波長數越多，其平均使用次數越少。另外，還需要注意的一點是，在W=16時，LPR實際上只使用了其中的14條，這一點也說明了LPR具有較高的波長利用率。

表1 各波長使用次數分析

5 結語

SDON是一種將軟件定義技術融入到光通信網絡的新型網絡，代表了未來光網絡的發展方向。擬從SDON中的路由問題出發，研究了SDN架構對于突破傳統光網絡中的瓶頸問題的價值所在，提出了一種基于SDON的差分時延約束多路徑路由波長優化算法。結果表明，在傳統光網絡中引入SDN機制能夠減小網絡的阻塞情況，提高網絡的整體性能，對于促進SDON的發展有重大意義。