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

唐鐵斌 劉 煒

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

0 引 言

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

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

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

1 樽海鞘群算法

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

(1)

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

(2)

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

(3)

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

2 控制器部署方案設計

2.1 SDN多控制器的數學模型

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

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

(4)

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

(5)

(6)

(7)

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

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

(8)

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

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

(9)

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

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

minf(N,C,D)

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

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

(10)

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

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

u:X→R

(11)

(12)

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

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

(13)

(14)

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

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

(15)

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

網絡中每個控制器的總效用UCi是兩個效用函數的加權求和：

(16)

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

(17)

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

(18)

(19)

2.2 改進的樽海鞘群算法

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

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

(20)

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

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

(21)

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

(22)

2.3 基于CSSA的最佳控制器數量和分配

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

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

算法1基于CSSA的控制器數量優化

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

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

While(t≤tmax)

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

F=最優位置；

利用式(2)更新C1值；

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

for(i=1:n)do

if(i==1)

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

else

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

endif

endfor

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

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

根據算法2的結果更新最佳組合；

t←t+1；

end

返回F

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

算法2基于CSSA的控制器分布優化

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

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

While (t≤tmax)

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

F=最優位置；

利用式(2)更新C1值；

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

for (i=1:n) do

if (i==1)

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

else

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

end if

end for

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

t←t+1；

end

返回F

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

3 實驗與結果分析

為了評估本文模型的性能，采用Internet Topology Zoo中的拓撲對本文算法進行測試，并將結果與其他基于元啟發式算法的SDN多控制器部署方法進行對比，如基于灰狼優化算法(Gray Wolf Optimization，GWO)[13]、基于粒子群和教學優化算法(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是因為它適用于不同的廣域網拓撲，網絡拓撲中的每個存在點(Point-of-Presence，PoP)被認為是網絡交換機(即轉發設備)。十種拓撲分為兩個組，第一組包含具有少量轉發設備的拓撲，第二組包含具有大量轉發設備的拓撲。假設流量是服從泊松分布的隨機變量，控制器的平均服務速率被設置為30 000。表2給出了評估過程中包含的仿真參數。

表1 拓撲類別

表2 模擬參數

3.2 實驗結果

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

表3 兩種考慮方案的參數變化

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

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

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

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

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

表4 密集網絡的參數變化

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

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

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

4 結 語

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