基于改進樽海鞘群算法的SDN控制器部署算法

唐鐵斌 劉 煒

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

0 引 言

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

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

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

1 樽海鞘群算法

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

(1)

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

(2)

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

(3)

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

2 控制器部署方案設計

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

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

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

(4)

檢查控制器性能的方法是評估受排隊延遲影響的控制器的時間響應。使用M/M/s多服務器排隊模型對控制器進行建模。控制器Ci的平均響應時間Ti是排隊時間和處理時間的總和，可以由式(5)計算。

(5)

(6)

(7)

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

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

(8)

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

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

(9)

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

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

minf(N,C,D)

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

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

(10)

式中：N表示部署控制器的數(shù)量；D是控制器與連接的交換機之間的平均延遲；C是部署控制器的成本；f()表示N、D和C的非線性函數(shù)。上述問題表示一個多目標、多約束的優(yōu)化問題。第一個約束條件表示控制器Ci的平均響應時間Ti應該小于預先定義的閾值τ；第二個約束條件與每個控制器的利用率指標有關，控制器的利用率指數(shù)用于映射到電源，存儲和處理效用，該指標應該位于控制器利用率指標的下限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表示當響應時間等于閾值時所使用的時間效用最小的非零值，一般取0.7。

成本效用函數(shù)是映射到所用控制器的成本。控制器Ci的成本效用可以定義如下：

(15)

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

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

(16)

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

(17)

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

(18)

(19)

2.2 改進的樽海鞘群算法

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

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

(20)

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

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

(21)

式中：ε=4，混沌映射的初始條件假定為0.7。可以使用新的C2值來重寫式(1)，結果如下：

(22)

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

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

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

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

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

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

While(t≤tmax)

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

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

利用式(2)更新C1值；

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

for(i=1:n)do

if(i==1)

使用式(22)來更新領導者個體的位置；

else

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

endif

endfor

基于上下邊界調整樽海鞘個體；

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

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

t←t+1；

end

返回F

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

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

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

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

While (t≤tmax)

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

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

利用式(2)更新C1值；

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

for (i=1:n) do

if (i==1)

使用式(22)來更新領導者個體的位置；

else

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

end if

end for

基于上下邊界調整樽海鞘個體；

t←t+1；

end

返回F

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

3 實驗與結果分析

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

3.1 實驗設置

本文算法是在裝有Intel Core i5處理器和8 GB RAM的計算機上使用MATLAB 2018a實施和測試的。表1給出了Internet Topology Zoo中10種近似拓撲。考慮Internet Topology Zoo是因為它適用于不同的廣域網(wǎng)拓撲，網(wǎng)絡拓撲中的每個存在點(Point-of-Presence，PoP)被認為是網(wǎng)絡交換機(即轉發(fā)設備)。十種拓撲分為兩個組，第一組包含具有少量轉發(fā)設備的拓撲，第二組包含具有大量轉發(fā)設備的拓撲。假設流量是服從泊松分布的隨機變量，控制器的平均服務速率被設置為30 000。表2給出了評估過程中包含的仿真參數(shù)。

表1 拓撲類別

表2 模擬參數(shù)

3.2 實驗結果

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

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

圖1展示了第一個方案不同情況的結果。圖1(a)和(b)分別顯示了在方案1的每種情況下，第一組拓撲和第二組拓撲的最佳控制器數(shù)量。對于每種情況，隨著約束閾值時間τ的增加，SDN網(wǎng)絡部署的控制器最佳數(shù)量減少了。對于相同數(shù)量的網(wǎng)絡交換機(即相同的拓撲)，所需控制器的最佳數(shù)量得以維持或減少。這可以解釋為閾值時間τ的增加允許每個部署控制器的響應時間增加，因此，控制器可以處理更多數(shù)量的轉發(fā)設備。

(a) 第一組拓撲 (b) 第二組拓撲圖1 第一個方案不同情況的結果

圖2顯示了第二個方案的不同情況的結果。圖2(a)和(b)分別顯示了第一組拓撲和第二組拓撲在每種情況的最佳控制器數(shù)量。結果表明，隨著控制器利用率指標上限的提高，支持網(wǎng)絡所需的最優(yōu)控制器數(shù)量減少。

(a) 第一組拓撲 (b) 第二組拓撲圖2 第二個方案不同情況的結果

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

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

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

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

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

4 結 語

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