唐鐵斌 劉 煒

1(長沙民政職業(yè)技術(shù)學(xué)院軟件學(xué)院 湖南 長沙 410004)2(湘潭大學(xué)信息工程學(xué)院 湖南 湘潭 411105)

0 引 言

隨著計算機(jī)網(wǎng)絡(luò)的不斷發(fā)展，軟件定義網(wǎng)絡(luò)(SDN)[1]在現(xiàn)代網(wǎng)絡(luò)設(shè)計中發(fā)揮了重要作用，越來越多地應(yīng)用于校園網(wǎng)絡(luò)、企業(yè)網(wǎng)絡(luò)、光網(wǎng)絡(luò)等場景。SDN背后的主要思想是通過可編程軟件控制器將控制平面和轉(zhuǎn)發(fā)平面進(jìn)行物理隔離，從而實現(xiàn)整個網(wǎng)絡(luò)的動態(tài)配置和控制[2]。SDN方法涵蓋了控制平面和數(shù)據(jù)平面之間的交互和協(xié)作，控制平面和數(shù)據(jù)平面之間的命令信號可以通過適當(dāng)?shù)臉?biāo)準(zhǔn)接口協(xié)議(如ForCES和OpenFlow)[3-4]完成。

在SDN網(wǎng)絡(luò)中，控制平面負(fù)責(zé)設(shè)置配置參數(shù)，并根據(jù)收到的指令確定執(zhí)行流量轉(zhuǎn)發(fā)的所有轉(zhuǎn)發(fā)設(shè)備的轉(zhuǎn)發(fā)角色，因此需要在控制平面內(nèi)部署一組智能控制器作為SDN網(wǎng)絡(luò)的控制中心。控制器放置和分配問題對啟用SDN的網(wǎng)絡(luò)的性能有很大影響，也引起了許多研究人員對該領(lǐng)域的關(guān)注[5]。目前，針對控制器分配問題和控制器最佳數(shù)量問題，已存在許多解決方案。Wang等[6]提出了一種基于聚類的網(wǎng)絡(luò)劃分算法，該方法以最小的部署成本研究了控制器的最佳數(shù)量、控制器的最佳類型、交換機(jī)和控制器的最佳連接。Farshin等[7]提出了一種基于混沌的灰狼優(yōu)化算法來解決等待時間感知的控制器放置問題，該算法通過獲得最佳數(shù)量的已部署控制器以及交換機(jī)和控制器的最佳連接，以最大程度地減少網(wǎng)絡(luò)延遲。但是該算法是針對小型網(wǎng)絡(luò)實現(xiàn)的，并未針對大型網(wǎng)絡(luò)和實際拓?fù)溥M(jìn)行過測試。Chen等[8]提出了一種社區(qū)檢測的控制器部署方法，利用復(fù)雜網(wǎng)絡(luò)分析理論，將待部署控制器的網(wǎng)絡(luò)拓?fù)湟暈橛啥鄠€社區(qū)組成的網(wǎng)絡(luò)，然后在每個社區(qū)中選擇合適的位置來放置控制器，從而能夠避免全局部署的復(fù)雜性。該方法可以有效地平衡控制器的負(fù)載，降低延遲，但是未考慮社區(qū)內(nèi)的部署成本和網(wǎng)絡(luò)間的彈性問題。Lu等[9]為了提高多控制器部署方案的可靠性并減少延遲，提出了一種基于可靠性和延遲的多控制器彈性布局算法，該算法將多控制器部署問題轉(zhuǎn)化為基于譜聚類的網(wǎng)絡(luò)拓?fù)渚仃嚨男邢蛄糠诸悊栴}，然后基于模擬退火的k-medoids算法用于對行向量進(jìn)行分類，實現(xiàn)了多個控制器的靈活部署。Qi等[10]提出了一種基于改進(jìn)的密度峰聚類算法解決控制器放置問題的方法，通過將控制器放在子網(wǎng)中最小化交換機(jī)和控制器之間的平均傳播延遲，但是未考慮部署成本。

現(xiàn)有文獻(xiàn)中大多數(shù)從最小化部署成本或者最小化網(wǎng)絡(luò)延遲單方向考慮控制器的放置問題，未能從兩個方向均衡考慮。針對該問題，提出一種基于改進(jìn)樽海鞘群算法的SDN控制器部署算法，該算法以網(wǎng)絡(luò)延遲和部署成本最小化為目標(biāo)，實現(xiàn)了控制器的最佳數(shù)量以及控制器與交換機(jī)的最佳分配問題。

1 樽海鞘群算法

樽海鞘群算法[11](Salp Swarm Algorithm，SSA)是Mirjalili等在2017年提出的一種群智能優(yōu)化算法。樽海鞘是一種生活在深海中的海洋生物，該生物不以群的方式分布，通常采取鏈聚集即樽海鞘鏈。樽海鞘鏈中，存在領(lǐng)導(dǎo)者和跟隨者兩種類型。領(lǐng)導(dǎo)者位于鏈的首端，其余為跟隨者。領(lǐng)導(dǎo)者對環(huán)境有著最優(yōu)的判斷，能夠影響到第二個樽海鞘個體的位置更新，對其余樽海鞘位置影響程度會依次減弱，因此不會直接影響種群的移動方向。排在后面的個體會受到前一個個體的直接影響，同時比前一個個體擁有更好的多樣性。

(1)

C1=2e-(4t/Tmax)2

(2)

式中：t為當(dāng)前迭代次數(shù)；Tmax為最大迭代次數(shù)。C2是在[0,1]之間均勻分布的隨機(jī)數(shù)，C3是在[-1,1]之間均勻分布的隨機(jī)數(shù)。樽海鞘鏈中跟隨者的位置更新為：

(3)

SSA通過多次搜索進(jìn)化,群體不斷地移動、更新位置。由于在每次迭代中有效地權(quán)衡了探索和開發(fā)，從而有效避免了局部最優(yōu)，取得了全局最優(yōu)解。該算法的優(yōu)點是結(jié)構(gòu)簡單、控制參數(shù)少、搜索能力強、容易實現(xiàn)，可用于處理多模態(tài)優(yōu)化問題。

2 控制器部署方案設(shè)計

2.1 SDN多控制器的數(shù)學(xué)模型

為了制定問題并確定優(yōu)化問題的適合度函數(shù)，首先對系統(tǒng)進(jìn)行建模。SDN多控制器網(wǎng)絡(luò)使用支持適當(dāng)SDN接口(如OpenFlow)的M個交換機(jī)Sj(j=1,2,…,M)。OpenFlow交換機(jī)連接到通過網(wǎng)絡(luò)分布的N個控制器Ci(i=1,2,…,N)。

為了執(zhí)行網(wǎng)絡(luò)操作，每個OpenFlow交換機(jī)都從相應(yīng)的控制器請求服務(wù)。控制器以切換規(guī)則和轉(zhuǎn)發(fā)表作為響應(yīng)。由于控制器的資源(包括存儲、帶寬和處理速率)受到限制，因此，單個控制器Ci只能夠處理和管理有限數(shù)量的OpenFlow交換機(jī)。Ki表示一次與某個控制器Ci關(guān)聯(lián)的交換機(jī)數(shù)量，可以通過控制器-交換機(jī)矩陣計算獲得。當(dāng)N=5和M=6時，控制器-交換機(jī)矩陣可以由式(4)表示，矩陣的行表示不同的控制器，列表示交換機(jī)，K矩陣包括每個控制器連接的交換機(jī)數(shù)量。

(4)

檢查控制器性能的方法是評估受排隊延遲影響的控制器的時間響應(yīng)。使用M/M/s多服務(wù)器排隊模型對控制器進(jìn)行建模?？刂破鰿i的平均響應(yīng)時間Ti是排隊時間和處理時間的總和，可以由式(5)計算。

(5)

(6)

(7)

式中：ρ是服務(wù)器利用率，表示系統(tǒng)穩(wěn)定性。僅當(dāng)服務(wù)器利用率ρ小于1時，系統(tǒng)才具有穩(wěn)定的分布?？梢允褂肕/M/s模型的狀態(tài)轉(zhuǎn)換圖來解釋。當(dāng)隊列中接收到的請求大于控制器的服務(wù)器時，傳輸為sμ，并且控制器處于最大容量。

控制器Ci的到達(dá)率λi可以表示為連接到控制器的所有交換機(jī)的平均到達(dá)率之和：

(8)

式中：s表示服務(wù)器個數(shù)；λs表示交換機(jī)平均請求率。

使用Erlang C公式，控制器Ci上的平均負(fù)載Li可以由排隊和處理的平均請求計算獲得：

(9)

網(wǎng)絡(luò)負(fù)載的動態(tài)變化使最優(yōu)數(shù)量和不同控制器的最優(yōu)位置隨之動態(tài)變化。因此，控制器的最佳數(shù)量的動態(tài)值和網(wǎng)絡(luò)中部署的不同控制器的動態(tài)最佳位置成為一個優(yōu)化問題。網(wǎng)絡(luò)負(fù)載與控制器的部署數(shù)量及其位置有關(guān)。一旦網(wǎng)絡(luò)負(fù)載增加，應(yīng)部署更多控制器來處理增加的負(fù)載并補償控制器過載問題。另一方面，如果減少網(wǎng)絡(luò)負(fù)載，則根據(jù)減少的負(fù)載量，一些已部署的控制器應(yīng)進(jìn)入睡眠模式或者分離。

本文框架的主要目標(biāo)是找到數(shù)量最少的SDN控制器及其最佳位置，以及將控制器分配給分布式交換機(jī)的最佳方式。這些最佳解決方案應(yīng)滿足與每個控制器的時間響應(yīng)和利用率相關(guān)的主要限制。可以將問題建模如下：

minf(N,C,D)

s.t.Ti≤τ,i=1,2,…,N

Ulb≤Ui≤Uub,i=1,2,…,N

(10)

式中：N表示部署控制器的數(shù)量；D是控制器與連接的交換機(jī)之間的平均延遲；C是部署控制器的成本；f()表示N、D和C的非線性函數(shù)。上述問題表示一個多目標(biāo)、多約束的優(yōu)化問題。第一個約束條件表示控制器Ci的平均響應(yīng)時間Ti應(yīng)該小于預(yù)先定義的閾值τ；第二個約束條件與每個控制器的利用率指標(biāo)有關(guān)，控制器的利用率指數(shù)用于映射到電源，存儲和處理效用，該指標(biāo)應(yīng)該位于控制器利用率指標(biāo)的下限Ulb與上限Uub之間。

首先，定義系統(tǒng)效用函數(shù)，該函數(shù)用于比較不同解決方案并指出最佳解決方案的適用性。系統(tǒng)效用函數(shù)由時間效用和成本效用兩部分組成。系統(tǒng)效用函數(shù)通常用于將變量的值映射為實數(shù)。一般可以定義為：

u:X→R

(11)

(12)

式中：α和β是常量。α和β的計算如式(13)和式(14)所示。

α=UT-thr?UT-thr∈[0,1]

(13)

(14)

式中：UT-thr表示當(dāng)響應(yīng)時間等于閾值時所使用的時間效用最小的非零值，一般取0.7。

成本效用函數(shù)是映射到所用控制器的成本?？刂破鰿i的成本效用可以定義如下：

(15)

式中：φ=1/(Uub-Ulb)2。

網(wǎng)絡(luò)中每個控制器的總效用UCi是兩個效用函數(shù)的加權(quán)求和：

(16)

式中：δC表示成本加權(quán)因子；δT表示時間加權(quán)因子。系統(tǒng)總效用函數(shù)表示每個控制器效用的平均值。因此，效用函數(shù)U可以計算如下：

(17)

同樣，所有可用控制器的總成本效用UCT和總時間效用UTT可以計算為：

(18)

(19)

2.2 改進(jìn)的樽海鞘群算法

樽海鞘群體的初始位置是隨機(jī)生成的，因此該算法存在收斂速度慢和尋優(yōu)精度低等問題。為了克服這一問題，將混沌映射引入樽海鞘群優(yōu)化算法中，即混沌樽海鞘群算法(Chaotic Salp Swarm Algorithm，CSSA)?；煦缋碚撌且环N常見的數(shù)學(xué)方法，用于分析具有關(guān)鍵初始條件的動態(tài)系統(tǒng)的行為。通過增強隨機(jī)映射參數(shù)，混沌映射成為增強元啟發(fā)式算法性能的解決方案。這些隨機(jī)參數(shù)是根據(jù)均勻或高斯分布提取的，因此可以通過具有相同特征且性能更好的混沌映射控制它們。使用混沌映射控制這些參數(shù)會降低局部最優(yōu)值并會增加收斂性。

對于樽海鞘群體的初始位置，使用混沌變量代替了隨機(jī)變量，即使用混沌映射來調(diào)整式(1)中第二個系數(shù)C2的值：

(20)

式中：ω(t)是在t次迭代時的混沌映射的值。最佳混沌映射是Robert于1976年提出的邏輯映射[12]，邏輯混沌映射的一般方程為：

ω(t+1)=εω(t)[1-ω(t)]

(21)

式中：ε=4，混沌映射的初始條件假定為0.7?？梢允褂眯碌腃2值來重寫式(1)，結(jié)果如下：

(22)

2.3 基于CSSA的最佳控制器數(shù)量和分配

對于建模的問題，目標(biāo)是為S中的每個交換機(jī)優(yōu)化控制器的最佳數(shù)量和最佳連接。此問題是一個NP難題，解決該問題的方法是使用CSSA元啟發(fā)式算法。CSSA的主要思想是：通過迭代，多個樽海鞘個體并行搜索得到最優(yōu)解，即控制器的最優(yōu)數(shù)目和控制器在交換機(jī)之間的最優(yōu)分布。因此，在嵌套循環(huán)中部署兩個基于CSSA的算法以獲得最優(yōu)解。

算法1表示為定義問題引入CSSA的偽代碼，其中每個樽海鞘個體表示網(wǎng)絡(luò)中控制器的數(shù)量，算法的輸出F表示控制器的最佳數(shù)目。

算法1基于CSSA的控制器數(shù)量優(yōu)化

參數(shù)初始化：對ub、lb、tmax、d、n進(jìn)行初始化。

種群初始化：對樽海鞘個體xi(i=1,2,…,n)的位置進(jìn)行初始化。

While(t≤tmax)

利用式(17)計算每個個體位置的適合度函數(shù)；

F=最優(yōu)位置；

利用式(2)更新C1值；

獲取邏輯混沌映射ω(t)值；

for(i=1:n)do

if(i==1)

使用式(22)來更新領(lǐng)導(dǎo)者個體的位置；

else

使用式(3)來更新跟隨者個體的位置；

endif

endfor

基于上下邊界調(diào)整樽海鞘個體；

計算交換機(jī)的最佳連接以獲得最佳個體(調(diào)用算法2)；

根據(jù)算法2的結(jié)果更新最佳組合；

t←t+1；

end

返回F

算法2表示部署控制器的偽代碼，根據(jù)算法1計算的控制器最佳數(shù)目來查找所有交換機(jī)的最佳連接。算法2中的每個樽海鞘表示所有交換機(jī)及其專用控制器的所有可用連接，它是一個M維向量，每個維表示一個交換機(jī)，輸出F是控制器在交換機(jī)之間的最佳分布。

算法2基于CSSA的控制器分布優(yōu)化

參數(shù)初始化：對ub、lb、tmax、d、n進(jìn)行初始化。

種群初始化：樽海鞘個體xi(i=1,2,…,n)的位置進(jìn)行初始化；

While (t≤tmax)

利用式(17)計算每個個體位置的適合度函數(shù)；

F=最優(yōu)位置；

利用式(2)更新C1值；

獲取邏輯混沌映射ω(t)值；

for (i=1:n) do

if (i==1)

使用式(22)來更新領(lǐng)導(dǎo)者個體的位置；

else

使用式(3)來更新跟隨者個體的位置；

end if

end for

基于上下邊界調(diào)整樽海鞘個體；

t←t+1；

end

返回F

系統(tǒng)通過設(shè)置CSSA的初始參數(shù)(包括上下邊界和最大迭代次數(shù))開始工作，然后隨機(jī)初始化n個樽海鞘個體，每個個體代表網(wǎng)絡(luò)中可用控制器的數(shù)量。使用式(17)計算每個個體的適合度，并且認(rèn)為適合度最高的個體是當(dāng)前的最優(yōu)解。最適宜的樽海鞘個體位置認(rèn)為是食物位置。根據(jù)樽海鞘個體的位置對CSSA的參數(shù)進(jìn)行更新。重復(fù)更新樽海鞘個體位置并評估每個樽海鞘個體的適合度，直到找到最優(yōu)解或達(dá)到最大迭代次數(shù)為止。

3 實驗與結(jié)果分析

為了評估本文模型的性能，采用Internet Topology Zoo中的拓?fù)鋵Ρ疚乃惴ㄟM(jìn)行測試，并將結(jié)果與其他基于元啟發(fā)式算法的SDN多控制器部署方法進(jìn)行對比，如基于灰狼優(yōu)化算法(Gray Wolf Optimization，GWO)[13]、基于粒子群和教學(xué)優(yōu)化算法(Particle Swarm Optimization and Teaching Learning Based Optimization，PSO-TLBO)[14]和基于遺傳算法(Genetic Algorithm，GA)[15]。

3.1 實驗設(shè)置

本文算法是在裝有Intel Core i5處理器和8 GB RAM的計算機(jī)上使用MATLAB 2018a實施和測試的。表1給出了Internet Topology Zoo中10種近似拓?fù)洹？紤]Internet Topology Zoo是因為它適用于不同的廣域網(wǎng)拓?fù)?，網(wǎng)絡(luò)拓?fù)渲械拿總€存在點(Point-of-Presence，PoP)被認(rèn)為是網(wǎng)絡(luò)交換機(jī)(即轉(zhuǎn)發(fā)設(shè)備)。十種拓?fù)浞譃閮蓚€組，第一組包含具有少量轉(zhuǎn)發(fā)設(shè)備的拓?fù)?，第二組包含具有大量轉(zhuǎn)發(fā)設(shè)備的拓?fù)洹＜僭O(shè)流量是服從泊松分布的隨機(jī)變量，控制器的平均服務(wù)速率被設(shè)置為30 000。表2給出了評估過程中包含的仿真參數(shù)。

表1 拓?fù)漕悇e

表2 模擬參數(shù)

3.2 實驗結(jié)果

對于考慮的十種拓?fù)?，每種拓?fù)淇紤]兩個主要方案。在第一種方案下，旨在分析更改閾值時間τ對最佳控制器數(shù)量的影響。在這種情況下，每個控制器的上限利用率指標(biāo)Uub假定為恒定，即Uub=0.9。在第二種方案下，以閾值延遲τ的恒定值檢查每個控制器的上利用率指標(biāo)變化的影響。對于每個可用的控制器，主要考慮較高的利用率指數(shù)，以補償網(wǎng)絡(luò)流量的突然增加并避免控制器以最大容量工作。表3給出了兩種情況下的組合參數(shù)。該算法對每一個網(wǎng)絡(luò)拓?fù)溥M(jìn)行了多次測試，實驗結(jié)果是多次測試的平均值。

表3 兩種考慮方案的參數(shù)變化

圖1展示了第一個方案不同情況的結(jié)果。圖1(a)和(b)分別顯示了在方案1的每種情況下，第一組拓?fù)浜偷诙M拓?fù)涞淖罴芽刂破鲾?shù)量。對于每種情況，隨著約束閾值時間τ的增加，SDN網(wǎng)絡(luò)部署的控制器最佳數(shù)量減少了。對于相同數(shù)量的網(wǎng)絡(luò)交換機(jī)(即相同的拓?fù)?，所需控制器的最佳數(shù)量得以維持或減少。這可以解釋為閾值時間τ的增加允許每個部署控制器的響應(yīng)時間增加，因此，控制器可以處理更多數(shù)量的轉(zhuǎn)發(fā)設(shè)備。

(a) 第一組拓?fù)?(b) 第二組拓?fù)鋱D1 第一個方案不同情況的結(jié)果

圖2顯示了第二個方案的不同情況的結(jié)果。圖2(a)和(b)分別顯示了第一組拓?fù)浜偷诙M拓?fù)湓诿糠N情況的最佳控制器數(shù)量。結(jié)果表明，隨著控制器利用率指標(biāo)上限的提高，支持網(wǎng)絡(luò)所需的最優(yōu)控制器數(shù)量減少。

(a) 第一組拓?fù)?(b) 第二組拓?fù)鋱D2 第二個方案不同情況的結(jié)果

為了更好地評估本文算法并檢查參數(shù)變化的影響，將本文算法應(yīng)用于由30個交換機(jī)組成的隨機(jī)網(wǎng)絡(luò)。通過系統(tǒng)的閾值時間τ和上限利用率指標(biāo)Uub的變化，對密集網(wǎng)絡(luò)進(jìn)行算法驗證。考慮兩種主要情況；在第一種情況下，算法是針對閾值時間τ的不同值和上限利用率指標(biāo)Uub的四個不同值測試的；第二種情況是使用四個不同的閾值時間值測試系統(tǒng)的Uub值范圍。表4列出了τ和Uub的兩種情況。

表4 密集網(wǎng)絡(luò)的參數(shù)變化

圖3(a)給出了四種情況下，控制器的閾值響應(yīng)變化對網(wǎng)絡(luò)最佳控制器數(shù)量的影響。每種情況都代表控制器的上限利用率指標(biāo)Uub的某個值。選擇這四個值，使其覆蓋Uub的可能范圍，從而提供可靠的狀態(tài)。對于四條曲線，隨著閾值時間的增加，所需的控制器數(shù)量減少。控制器個數(shù)的最佳值位于所有曲線的最后部分，此時τ的值足夠高，可以處理許多任務(wù)并為許多交換機(jī)服務(wù)。圖3(b)給出了對于閾值時間τ的四個不同值，最優(yōu)控制器數(shù)量隨每個控制器的上限利用率指標(biāo)的變化而變化。第一條曲線表示最差的一條曲線，因為它表示所需控制器數(shù)量的最大值。這是因為閾值時間的較小值會阻止控制器處理大量任務(wù)，因此，該控制器只能用于最少數(shù)量的轉(zhuǎn)發(fā)設(shè)備。第四條曲線表示所需控制器數(shù)量方面的最佳結(jié)果。這是因為閾值時間τ的高值允許控制器支持更多交換機(jī)。

(a) 時間閾值 (b) 上限利用率圖3 閾值時間和上限利用率的變化對控制器配置的影響

圖4給出了不同SDN控制器放置優(yōu)化算法的測試對比結(jié)果，用于評估所引入算法的性能和優(yōu)點。本文算法與其他三種算法之間的對比所考慮的性能指標(biāo)是算法的執(zhí)行時間，該時間代表算法獲得最優(yōu)解所需的延遲。執(zhí)行時間對于SDN網(wǎng)絡(luò)至關(guān)重要，因為在網(wǎng)絡(luò)負(fù)載變化的情況下激活控制器需要花費很長時間，當(dāng)前部署的控制器可能會過載，并且會發(fā)生故障?？梢钥闯?，每個算法的執(zhí)行時間隨著閾值時間和上限利用率的增加而減少。相對于其他算法，本文算法具有更好的性能。

4 結(jié) 語

本文以網(wǎng)絡(luò)延遲和部署成本最小化為目標(biāo)，提出一種基于改進(jìn)樽海鞘群算法的SDN控制器部署算法。該算法考慮樽海鞘群算法存在收斂速度慢和尋優(yōu)精度低等問題，通過引入混沌映射來提高優(yōu)化器性能，防止出現(xiàn)局部最優(yōu)。實驗結(jié)果表明，與其他SDN控制器部署算法相比，本文算法的測試結(jié)果更具優(yōu)勢，實現(xiàn)了最佳數(shù)量的控制器以及控制器與交換機(jī)的最佳分配，從而最大程度地減少了時間延遲和部署成本。