俞慧慧

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

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

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

將SDN的思想引入到AON中，基于SDN的全局資源視圖和控制機(jī)制，能夠?qū)Φ讓拥墓庠O(shè)備進(jìn)行統(tǒng)一的配置和管理，使其具有高度的協(xié)同工作能力。同時(shí)，數(shù)據(jù)鏈路的增加引起端到端的路徑延遲，也稱為差分時(shí)延(Differential Delay, DD)。針對(duì)這些問(wèn)題，在SDON中提出一種差分時(shí)延約束多路徑路由波長(zhǎng)選擇算法。該方法不僅可以避免單路徑路由限制和可能的路徑障礙，同時(shí)還可以提高網(wǎng)絡(luò)吞吐量和利用率。該方法將多路徑優(yōu)化問(wèn)題，轉(zhuǎn)變?yōu)榻鉀Q非相交路徑基數(shù)M最大化問(wèn)題和平均端到端傳輸延遲最小化問(wèn)題。采用迭代方法和整數(shù)規(guī)劃，求解M最小值，并根據(jù)M值確定最優(yōu)路由波長(zhǎng)。

1 軟件定義光網(wǎng)絡(luò)(SPON)架構(gòu)

(SDON)尋求利用靈活的SDN控制為底層光網(wǎng)絡(luò)基礎(chǔ)設(shè)施提供網(wǎng)絡(luò)應(yīng)用能力。圖1為SDON架構(gòu)。這個(gè)架構(gòu)的控制核心是一個(gè)抽象概念，通過(guò)擴(kuò)展OpenFlow (OF) 控制器和協(xié)議實(shí)現(xiàn)。這個(gè)機(jī)制支持底層異構(gòu)光傳輸和數(shù)據(jù)包集成。這個(gè)架構(gòu)包括3個(gè)組件，分別為硬件抽象層，OF擴(kuò)展層和SDN應(yīng)用層。硬件抽象層的作用在于隱藏底層異構(gòu)傳輸網(wǎng)絡(luò)資源的細(xì)節(jié)，同時(shí)為硬件狀態(tài)配置提供編程接口；在OF擴(kuò)展中，SDON采用多維流表來(lái)表示OF使能交換。每個(gè)表中包括詳細(xì)的匹配域、計(jì)數(shù)器和一系列附屬動(dòng)作。

圖1 軟件定義光網(wǎng)絡(luò)架構(gòu)

2 問(wèn)題描述及模型引入

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

使用無(wú)向圖G(v,ε)表示的由各節(jié)點(diǎn)經(jīng)過(guò)一定的連接方式組成的網(wǎng)絡(luò)，其中，v和ε分別表示的是各個(gè)節(jié)點(diǎn)組成的節(jié)點(diǎn)集合以及節(jié)點(diǎn)之間的無(wú)向連接。每個(gè)連接鏈路e∈ε與連接其節(jié)點(diǎn)的兩個(gè)相對(duì)定向弧e′和e″相關(guān)聯(lián)。所有這類弧的集合由η表示(注意，由此產(chǎn)生的有向圖G(v,Ν)是有向且是雙向的)?；ˇ堑脑垂?jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分別用A(η)和B(η)表示。加權(quán)值ωη表示弧η∈Ν的延遲程度參數(shù)。弧σ+(v)和σ-(v)集合分別表示從節(jié)點(diǎn)v∈V發(fā)出的弧的傳出方向和指向v的弧的傳入方向。對(duì)復(fù)合模型的求解的關(guān)鍵點(diǎn)是在給定的差分時(shí)延以及端到端的平均延遲上界α的條件下，求給定源節(jié)點(diǎn)A以及目標(biāo)節(jié)點(diǎn)B之間的多路徑路由連接的最優(yōu)解，并且能夠最大化不相交路徑M，之后根據(jù)確定的最多的不相交路徑使得端到端的平均延遲L最小化。

3 基于SDON的差分時(shí)延約束多路徑路由波長(zhǎng)優(yōu)化

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

3.1 M值最大化

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

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 差分延遲約束

差分延遲補(bǔ)償可以有效緩解和解決SDON中的環(huán)路和隔離環(huán)問(wèn)題。為了實(shí)現(xiàn)差分延遲補(bǔ)償，我們假設(shè)網(wǎng)絡(luò)內(nèi)部允許路由循環(huán)的存在。在3.1節(jié)的基礎(chǔ)上，我們?cè)黾?個(gè)限制變量和一個(gè)約束條件。通過(guò)新增加的變量和約束條件，解決路徑內(nèi)循環(huán)問(wèn)題，并實(shí)現(xiàn)差分延遲約束功能，從而最小化DD。

設(shè)集合Rηvm和rηm分別為人工流約束條件，用來(lái)對(duì)流變量進(jìn)行約束。其中，Rηvm表示路徑W上的節(jié)點(diǎn)v到節(jié)點(diǎn)B的人工流值，rηm表示屬于路徑W的人流值。我們通過(guò)加強(qiáng)對(duì)xηm約束，去除網(wǎng)絡(luò)內(nèi)路由循環(huán)問(wèn)題，這種方式也可以避免孤立循環(huán)。流量變量的差分延遲限制公式為：

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

(8)

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

(9)

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

xηmbinary,Rηvm·rvm≥0

，

(10)

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

3.3 多路徑路由波長(zhǎng)選擇

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

4 實(shí)驗(yàn)結(jié)果與數(shù)據(jù)分析

4.1 實(shí)驗(yàn)條件設(shè)置和對(duì)比方法

假設(shè)SDON中沒(méi)有使用波長(zhǎng)轉(zhuǎn)換器，并且每對(duì)鄰接節(jié)點(diǎn)之間都由兩條光纖所連接以構(gòu)成雙向鏈路。另外，所有的光纖都包含相同的波長(zhǎng)數(shù)目。采用14個(gè)節(jié)點(diǎn)的NSFNET拓?fù)渥鳛榉抡鎸?duì)象。并且基于該拓?fù)?，?duì)兩種情況進(jìn)行仿真，分別為每條光纖中波長(zhǎng)數(shù)為8，如圖2(a)所示；和波長(zhǎng)數(shù)為16，如圖2(b)所示。

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

4.2 對(duì)比實(shí)驗(yàn)結(jié)果及分析

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

圖2對(duì)比了文中算法和另外幾種算法在解決光網(wǎng)絡(luò)中的路由問(wèn)題時(shí)所產(chǎn)生的網(wǎng)絡(luò)擁塞隨時(shí)間變化的情況。通過(guò)觀察整體的結(jié)果形式可以發(fā)現(xiàn)，圖2(b)中的結(jié)果要明顯優(yōu)于圖2(a)，原因很簡(jiǎn)單，因?yàn)閳D2(b)中的結(jié)果是通過(guò)仿真每條光纖中具有16條波長(zhǎng)所得到的。相反，圖2(a)中的結(jié)果是基于每條光纖只含有8條波長(zhǎng)。圖2(b)仿真使用的資源數(shù)量是圖2(a)的兩倍，因此更加利于網(wǎng)絡(luò)流量的傳播，降低阻塞率。此外，我們分別觀察圖2(a)和圖2(b)中的結(jié)果，會(huì)發(fā)現(xiàn)LPR都能夠取得很好的效果。這是因?yàn)長(zhǎng)PR相對(duì)來(lái)說(shuō)是一種靜態(tài)的策略，需要提前知曉流量的情況，并且基于線性規(guī)劃來(lái)進(jìn)行集中式求解，這個(gè)過(guò)程相對(duì)耗時(shí)較長(zhǎng)，這是LPR所需要克服的問(wèn)題。

(a)波長(zhǎng)數(shù)=8

(b)波長(zhǎng)數(shù)=16

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

表1 各波長(zhǎng)使用次數(shù)分析

5 結(jié)語(yǔ)

SDON是一種將軟件定義技術(shù)融入到光通信網(wǎng)絡(luò)的新型網(wǎng)絡(luò)，代表了未來(lái)光網(wǎng)絡(luò)的發(fā)展方向。擬從SDON中的路由問(wèn)題出發(fā)，研究了SDN架構(gòu)對(duì)于突破傳統(tǒng)光網(wǎng)絡(luò)中的瓶頸問(wèn)題的價(jià)值所在，提出了一種基于SDON的差分時(shí)延約束多路徑路由波長(zhǎng)優(yōu)化算法。結(jié)果表明，在傳統(tǒng)光網(wǎng)絡(luò)中引入SDN機(jī)制能夠減小網(wǎng)絡(luò)的阻塞情況，提高網(wǎng)絡(luò)的整體性能，對(duì)于促進(jìn)SDON的發(fā)展有重大意義。