時延和可靠性感知的多控制器均衡部署策略

趙文文, 孟相如, 康巧燕, 蘇玉澤

(1.空軍工程大學(xué)信息與導(dǎo)航學(xué)院，西安，710038；2.94303部隊, 山東濰坊, 261000)

傳統(tǒng)網(wǎng)絡(luò)因其數(shù)據(jù)和控制平面高度耦合，使得網(wǎng)絡(luò)的實時動態(tài)調(diào)整與快速升級部署比較困難。軟件定義網(wǎng)(software-defined networks, SDN)通過對網(wǎng)絡(luò)數(shù)據(jù)平面和控制平面的功能解耦，讓網(wǎng)絡(luò)功能擴(kuò)展更加靈活高效，并通過北向接口向上層用戶提供程序接口，為網(wǎng)絡(luò)運行維護(hù)的程序化、自動化提供了可能。

多控制器SDN中如何多控制器SDN數(shù)量和部署位置，并合理劃分控制域等問題一直是當(dāng)今研究的熱點。Heller等人在2012年首次提出SDN中控制器部署是NP-Hard問題，并研究了不同部署位置對系統(tǒng)平均時延和最大時延帶來的影響[1]。文獻(xiàn)[3～5]分別從不同角度，考慮了時延和負(fù)載指標(biāo)下多控制器部署問題，而對可靠性問題涉及不足。文獻(xiàn)[6]在考慮控制器負(fù)載和響應(yīng)時間的基礎(chǔ)上，研究了在考慮可靠性情況下的控制器部署策略，然而其僅考慮了最差時延，未考慮全網(wǎng)平均控制時延和控制器之間負(fù)載均衡差異，且其使用的細(xì)菌覓食算法收斂性較差。文獻(xiàn)[7]通過綜合權(quán)衡節(jié)點效能和路徑質(zhì)量評估節(jié)點可靠性，并設(shè)定負(fù)載均衡因子以優(yōu)化控制器部署位置，而沒有考慮控制時延因素。文獻(xiàn)[8]建立了一種針對鏈路故障引起的控制時延變動的SDN控制網(wǎng)絡(luò)可靠性模型，提出了一種控制器部署算法，卻并未考慮負(fù)載均衡因素。文獻(xiàn)[9]以交換機(jī)節(jié)點的負(fù)載和拓?fù)渲行亩葹橐罁?jù)，建立網(wǎng)絡(luò)可靠度模型，通過該模型計算滿足可靠性要求的控制器部署方案，但其僅以節(jié)點拓?fù)渲行亩茸鳛榭煽啃砸罁?jù)，對網(wǎng)絡(luò)實際運行時的可靠性考慮較少。文獻(xiàn)[10]在已知交換節(jié)點和控制器節(jié)點故障率的條件下，建立了一種可容錯的控制器部署模型(fault tolerant controller placement，F(xiàn)TCP)，但其僅考慮了可靠性，對時延、負(fù)載等因素沒有考慮。

文獻(xiàn)[7]、文獻(xiàn)[11]均提出了隨機(jī)部署算法，在滿足控制器負(fù)載容量限制的前提下，采用一定隨機(jī)策略在交換節(jié)點中選取控制器部署位置，隨機(jī)部署策略在計算速度上有一定優(yōu)勢，但由于沒有考慮其他因素，導(dǎo)致所得解空間的整體性表現(xiàn)不佳。文獻(xiàn)[12]提出了用k-means聚類算法解決控制器部署問題，將控制器部署和控制域劃分轉(zhuǎn)換為類簇中心點的確定和類簇的劃分問題，然而其僅依據(jù)物理距離進(jìn)行控制域劃分，沒有考慮負(fù)載均衡等問題，且初始類簇數(shù)量和類簇中心點的選取對聚類效果的好壞有很大的影響。

綜上所述，針對控制器部署問題，當(dāng)前研究只考慮了網(wǎng)絡(luò)時延、負(fù)載均衡和可靠性中的部分因素，而對上述因素綜合考慮較少[13-15]，針對該問題，本文在綜合衡量時延、可靠性和負(fù)載均衡因素的基礎(chǔ)上，建立了控制器部署評價模型，提出了基于模擬退火-遺傳算法(simulated annealing genetic algorithm，SAGA)的時延和可靠性感知的多控制器均衡部署策略(delay and reliability awared balancing strategy based on SAGA，SAGA-DRABS)。

1 問題描述與模型構(gòu)建

SDN按照控制信息流經(jīng)的路徑不同，分為帶內(nèi)控制SDN和帶外控制SDN。本文討論采用帶內(nèi)控制方式時SDN的多控制器部署問題，即按照一定的評價策略和指標(biāo)，在底層交換網(wǎng)絡(luò)選取合適的交換機(jī)節(jié)點，部署SDN控制器，并對控制器所管理的交換節(jié)點合理劃分，使網(wǎng)絡(luò)性能達(dá)到最優(yōu)。

底層交換網(wǎng)絡(luò)用加權(quán)有向圖G(S,E)表示，其中S={s1,s2,…,sn}，Si為交換機(jī)節(jié)點，n為交換機(jī)的數(shù)量，E={eij|i,j≤n}為圖G中邊的集合，其中eij=為節(jié)點si與sj之間的邊，邊的權(quán)值wij為路徑的物理距離。將交換網(wǎng)絡(luò)劃分為k個控制域等價于將圖G劃分為k個子圖，可以表示為：

Gcut={G1,G2,…,Gk|k≤n},∩Gj=?(Gj∈Gcut)

(1)

控制器用集合C={c1,c2,…,ck|k≤n}表示，其中cj(j≤k)為控制域Gj的控制器?？刂朴騁j的大小為|Gj|，表示Gj中交換機(jī)的數(shù)量。如前所述，在對G進(jìn)行分割時，主要考慮以下因素：控制時延、負(fù)載均衡度、可靠性和DRB度量(MDRB)。

1.1 控制時延

SDN控制時延是SDN南向接口運行效率的重要表征，也是SDN控制網(wǎng)絡(luò)最重要性能指標(biāo)之一。SDN控制時延包括控制器與控制器之間的時延和控制器與交換機(jī)之間的時延，在實際應(yīng)用中，控制器東西向接口之間通常用高速度大容量高帶寬專線連接，與控制器與交換機(jī)之間的時延相比，控制器之間的時延幾乎可以忽略不計，因此本文主要考慮控制器與交換機(jī)之間的時延，用網(wǎng)絡(luò)平均時延進(jìn)行衡量，為此，先定義各節(jié)點時延如下：

(2)

α+β+γ=1

(3)

0≤α，β，γ≤1

(4)

式中：α、β、γ為比例參數(shù)，針對不同場景可以設(shè)置不同的比例參數(shù)，比如，在數(shù)據(jù)中心網(wǎng)絡(luò)中，由于各交換節(jié)點部署較為集中，傳播時延對控制器部署影響不大，可設(shè)置γ的值為0。

(5)

1.2 負(fù)載均衡度(BL)

本文用負(fù)載均衡度來衡量SDN控制網(wǎng)絡(luò)中各控制器的負(fù)載均衡情況，為此定義各控制器的負(fù)載和負(fù)載均衡度如下所示：

定義3控制器cj的負(fù)載(RNj)。控制器負(fù)載主要由四部分組成：①處理事件中packet_in請求數(shù)據(jù)包并將處理結(jié)果傳遞給應(yīng)用程序和交換機(jī)；②維護(hù)控制域內(nèi)網(wǎng)絡(luò)視圖；③與其他控制器交互后形成全局網(wǎng)絡(luò)視圖；④向南向接口安裝由北向接口產(chǎn)生的流量。網(wǎng)絡(luò)場景不同，各部分的權(quán)重也不同，然而處理事件中packet_in請求數(shù)據(jù)包通常被認(rèn)為是控制器負(fù)載的最重要部分[12]。因此，本文用控制器處理的packet_in請求數(shù)據(jù)包的數(shù)量作為控制器負(fù)載的度量。在控制域Gj中，設(shè)交換機(jī)si向控制器cj發(fā)送packet_in請求的數(shù)量為pi，控制器cj的負(fù)載RNj可定義為式(6)，其中Ωj為控制器cj的額定負(fù)載。

(6)

(7)

τ+ξ=1

(8)

式中：τ、ξ為權(quán)重參數(shù)；BL1表示各控制器之間的負(fù)載差額，BL1越小表示各控制器之間負(fù)載越趨于均衡；BL2表示各控制器負(fù)載方差。BL1和BL2定義見式(9)、(10)。

(9)

(10)

定義4控制器cj的負(fù)載率(ηj)。指控制器cj中，當(dāng)前負(fù)載占額定負(fù)載的比率，當(dāng)控制器達(dá)到額定負(fù)載時，控制器對未知數(shù)據(jù)包的請求開始排隊處理。

(11)

在對RN進(jìn)行控制域劃分時，為控制器cj的負(fù)載率ηj設(shè)定負(fù)載閾值ηthr，使ηj≤ηthr，當(dāng)ηj>ηthr時，重新調(diào)整控制域。

1.3 可靠性

SDN控制網(wǎng)絡(luò)中，控制器為每個交換節(jié)點分別維護(hù)一條控制路徑，控制路徑的可靠性表示控制信息和流表信息從控制器到交換節(jié)點的可達(dá)程度，流表和控制信息的延遲可能造成控制時延和網(wǎng)絡(luò)時延抖動。在帶內(nèi)控制的情形下，當(dāng)?shù)讓咏粨Q節(jié)點的可靠性不同時，控制器的部署位置會導(dǎo)致各控制路徑的可靠性也不盡相同[7-10]，圖1中，A、B、C表示交換機(jī)節(jié)點，D代表控制器，假設(shè)交換機(jī)的可靠性分別為0.9、0.6、0.3，橙色表示控制器部署位置，在忽略鏈路可靠性、僅考慮節(jié)點可靠性的前提下，3種部署方案所形成控制路徑的可靠性分別為：R(a)=0.9+0.9×0.6+0.9×0.6×0.3=1.602；R(b)=0.6+0.6×0.3+0.6×0.9=1.32；R(c)=0.3+0.3×0.6+0.3×0.6×0.9=0.642。

圖1 部署位置對可靠性的影響

可以看出，對同一交換網(wǎng)絡(luò)，不同的控制器部署位置會導(dǎo)致控制路徑的可靠性也不同。本文在假定各交換節(jié)點的可靠度已知的前提下，分別定義了控制路徑、控制域和網(wǎng)絡(luò)整體可靠性。進(jìn)行控制器部署就是選取合適的部署策略，使得網(wǎng)絡(luò)的整體可靠性達(dá)到最高。

定義5控制域可靠度(RGj)。SDN中，每個控制域由多條控制路徑組成，本文定義控制域的可靠性度量(RGj)為各控制路徑可靠性之和，如式(12)所示。

(12)

式中：Rk表示交換節(jié)點sk的可靠度，為0到1區(qū)間的正數(shù)；Rij指控制器cj到交換節(jié)點si的控制路徑Pij的可靠性，該可靠性度量了控制信息和流表信息到交換節(jié)點的可達(dá)程度。

定義6控制網(wǎng)絡(luò)可靠度(Rtotal)?？刂凭W(wǎng)絡(luò)可靠度是全網(wǎng)的可靠性度量，為SDN中所有控制域的可靠性之和，如式(13)所示：

(13)

式中：RGj為控制域Gj的可靠度。

1.4 DRB度量(MDRB)

基于上述定義，本文提出用DRB度量MDRB來衡量控制器部署策略的整體性能，其與時延和負(fù)載均衡度成反比，與可靠性成正比，見式(14)：

(14)

σ+υ+ω=1

(15)

0≤σ,υ,ω≤1

(16)

式中：QT、QB、QR為縮放系數(shù)，用于平衡量綱，σ、υ、ω分別為比例系數(shù)，總和為1。

根據(jù)以上指標(biāo)，基于時延和可靠性感知的多控制器均衡部署策略就是找到一個合適方案，使得目標(biāo)值達(dá)到最大，為此，建立帶約束的最優(yōu)化模型如下式所示：

max{MDRB}=

(17)

σ+υ+ω=1

(18)

s.t.0≤σ,υ,ω≤1

(19)

ηi≤ηthr

(20)

式中:QT、QB、QR為縮放系數(shù)，用于平衡量綱；σ、υ、ω分別為比例系數(shù)，總和為1，式(20)表示控制器的負(fù)載不超過其額定負(fù)載。

2 策略描述

2.1 模擬退火-遺傳算法(SAGA)

遺傳算法借鑒生物進(jìn)化相關(guān)理論，將生物種群染色體編碼、選擇、交叉等進(jìn)化機(jī)制引入復(fù)雜非線性問題解空間的尋優(yōu)過程，同時通過變異操作幫助算法跳出局部最優(yōu)陷阱，一定程度上保證了解空間的全局特性。然而遺傳算法由于其子代種群的個數(shù)與父代適應(yīng)度大小成正比，且在算法早期因個體適應(yīng)度差異較大，容易使少數(shù)優(yōu)秀個體的后代占滿種群造成“早熟”，而在后期又由于適應(yīng)度趨于一致，無法較好地發(fā)揮優(yōu)秀個體的遺傳作用，導(dǎo)致算法較早陷入局部最優(yōu)解。

模擬退火算法(SA)將待優(yōu)化問題求解過程模擬為統(tǒng)計熱力學(xué)中的物理降溫過程，在搜索到最優(yōu)解(達(dá)到熱平衡)之前，反復(fù)降溫，每次降溫采用Metropolis接受準(zhǔn)則，使算法跳離局部最優(yōu)的“陷阱”。

本文將模擬退火算法與遺傳算法相結(jié)合用于控制器部署位置選擇，由于模擬退火算法和遺傳算法可以互相取長補短，通過在遺傳算法后期適應(yīng)度趨于一致時，引入模擬退火的降溫過程，對種群采用Metropolis接受準(zhǔn)則進(jìn)行取舍，較好地克服了傳統(tǒng)遺傳算法的早熟現(xiàn)象，使該算法更有效、快速地搜尋到全局較優(yōu)解。

2.2 部署策略

針對上述模型，本文引入模擬退火遺傳算法提出了一種時延和可靠性感知的多控制器均衡部署策略SAGA-DRABS。圖2為策略的具體流程。

圖2 SAGA-DRABS策略流程示意圖

SAGA-DRABS首先采用隨機(jī)選取的辦法確定控制器部署位置，組成原始解空間并編碼后，形成初始種群，利用式(15)計算各部署位置的MDRB值，即該種群所有個體的目標(biāo)值，得出SAGA的適應(yīng)度值fitValue。而后進(jìn)入退火降溫過程，對由不同部署位置的解空間形成的初始種群利用迭代方法進(jìn)行交叉、選擇、變異等進(jìn)化操作形成子代個體，每一次進(jìn)化操作(交叉、選擇、變異)后，計算新個體的適應(yīng)度值Mnew。若Mnew>MDRB，說明進(jìn)化后的子代優(yōu)于父代個體，將該子代個體加入種群，否則，利用Metropolis接受準(zhǔn)則進(jìn)行取舍，形成本輪最優(yōu)種群。繼續(xù)進(jìn)入下一輪降溫過程，每一輪降溫過程都是在上一輪最優(yōu)種群的基礎(chǔ)上，進(jìn)行交叉、選擇、變異等進(jìn)化操作后，以概率p進(jìn)行取舍得出最優(yōu)種群，如此反復(fù)，直至達(dá)到最終溫度，此時從所得最優(yōu)種群中選取最優(yōu)個體即所求結(jié)果。

pchoose=exp ((Mnew-MDRB)Ti)

(21)

式中：Ti為每輪降溫過程的當(dāng)前溫度值；Mnew和MDRB分別表示每次進(jìn)化形成個體的適應(yīng)度值。算法偽代碼如表1所示。

表1 SAGA-DRABS策略偽代碼

3 實驗仿真

3.1 仿真設(shè)置

基于Matlab平臺進(jìn)行實驗仿真，仿真在隨機(jī)生成的包含80個交換節(jié)點、604條物理鏈路，分布在2 500 km范圍內(nèi)的模擬網(wǎng)絡(luò)(見圖3)上進(jìn)行。實驗中，假設(shè)到達(dá)交換機(jī)的未知流數(shù)量服從以λ=1/14、μ=1/20為參數(shù)的泊松分布。控制器額定負(fù)載服從以σload=1 000、μload為參數(shù)的高斯分布，見式(23)：

圖3 仿真網(wǎng)絡(luò)

(23)

式中：np為未知流數(shù)量；k為控制器數(shù)量；ηi為控制器額定負(fù)載率。設(shè)節(jié)點可靠度Ri服從μreliability=0.95、σreliability=0.1為參數(shù)的高斯分布。網(wǎng)絡(luò)傳輸帶寬為1 Gbits/s。

SAGA算法變量初始化方面，設(shè)定種群大小Npop=10，最大進(jìn)化次數(shù)Xmax=10，交叉概率Pinter=0.6，變異概率Phet=0.05，退火初始溫度Tint=100，變異概率Ccool=0.6，終止溫度Tend=0。

3.2 仿真結(jié)果與分析

為對比不同部署策略對SDN性能的影響，本文將SAGA-DRABS分別與采用k-means聚類策略、貪心策略(greedy deployment, GRE)和隨機(jī)部署(random deployment, RD)策略進(jìn)行控制器部署時的性能進(jìn)行了比較。對所有策略進(jìn)行50次計算后取各自結(jié)果的算數(shù)平均。

圖4顯示當(dāng)控制器數(shù)量為4時，通過SAGA-DRABS策略對圖3所示網(wǎng)絡(luò)進(jìn)行控制器部署和控制域劃分的結(jié)果，圖中不同顏色表示不同控制域，其中控制器部署位置用相應(yīng)顏色的“★”表示，編號用紅色標(biāo)出。

圖4 控制器部署結(jié)果

圖5顯示SAGA-DRABS的尋優(yōu)曲線，本次計算共經(jīng)過11次降溫，每次降溫過程中，分別進(jìn)行10輪遺傳算法迭代，每輪迭代求出當(dāng)前局部最優(yōu)解，后一次降溫均在前一次降溫取得最優(yōu)解的基礎(chǔ)上進(jìn)行新的遺傳算法迭代。SAGA-DRABS中每次降溫可以看作一個完整的傳統(tǒng)遺傳算法流程，可以看出，該策略在傳統(tǒng)遺傳算法的基礎(chǔ)上，又進(jìn)行了多次降溫過程，使當(dāng)前最優(yōu)解跳出局部陷阱，進(jìn)一步增強(qiáng)了解空間的全局特性。

圖5 SAGA-DRABS尋優(yōu)曲線

圖6顯示不同控制器數(shù)量情況下，各算法所得部署策略的MDRB值?？梢钥闯觯啾绕渌惴?，通過 SAGA-DRABS所得的MDRB值更高，主要原因是該策略在考慮網(wǎng)絡(luò)平均控制時延最小的同時，也將可靠性和負(fù)載均衡度納入評價指標(biāo)，同時通過SAGA算法使所求結(jié)果具有較好的全局特性。作為對比，k-means算法主要是基于距離影響的全網(wǎng)平均控制時延因素所得的部署策略，在整體目標(biāo)衡量上要劣于SAGA-DRABS，GRE算法主要基于當(dāng)前最優(yōu)解尋求控制器最佳部署策略，其MDRB值與SAGA-DRABS算法相比，明顯缺乏全局最優(yōu)特性。而RD算法主要采取在滿足負(fù)載率的情況下的隨機(jī)部署方法，其DRB值也相應(yīng)為最小。

圖6 各策略DRB度量指標(biāo)

圖7～圖9顯示在不同控制器數(shù)量情況下，各算法所得部署策略在全網(wǎng)平均控制時延、負(fù)載均衡和可靠性度量上的表現(xiàn)，可以看出，由于k-means算法主要基于距離因素進(jìn)行控制器部署，因此在時延表現(xiàn)上要略優(yōu)于SAGA-DRABS。而在負(fù)載均衡方面，由于貪心算法主要基于當(dāng)前局部的DRB值，既沒有考慮DRB值的全局性，也缺乏對負(fù)載均衡的單獨考量，導(dǎo)致該算法相較其他算法，所得策略在負(fù)載均衡方面表現(xiàn)較差，而隨機(jī)部署算法由于在部署時僅考慮控制器負(fù)載容量限制，導(dǎo)致該算法在負(fù)載均衡度量上表現(xiàn)較優(yōu)。在可靠性方面可以看出， SAGA-DRABS所求策略的可靠性較k-means算法有較為明顯的優(yōu)勢，分析原因，也是因為DRA-SAGA既在目標(biāo)函數(shù)中考慮了可靠性因素，也強(qiáng)化了全局最優(yōu)解的搜索能力，保證了部署策略的可靠性。

圖7 各策略時延指標(biāo)對比

圖8 各策略負(fù)載均衡指標(biāo)對比

圖9 各策略可靠性指標(biāo)對比

4 結(jié)語

本文研究了SDN中多控制器部署問題，通過建立相應(yīng)模型，研究了不同部署策略對網(wǎng)絡(luò)時延、負(fù)載均衡和可靠性方面的影響，提出了一種時延和可靠性感知的控制器均衡部署策略。仿真結(jié)果表明，提出的部署策略在保證負(fù)載均衡的前提下，提高了控制網(wǎng)絡(luò)的可靠性，降低了網(wǎng)絡(luò)時延，進(jìn)而提高了網(wǎng)絡(luò)的整體性能，從而為面向QoS的網(wǎng)絡(luò)應(yīng)用提供了可靠的保障。