SDN中區(qū)分交換機等級的控制器負載均衡算法

蔣雯麗 梁思遠 趙芳利 趙 峰 王聰一

(西安郵電大學(xué)通信與信息工程學(xué)院 陜西 西安 710121)

0 引 言

SDN是一種新型的網(wǎng)絡(luò)架構(gòu)[1]，實現(xiàn)控制平面與數(shù)據(jù)轉(zhuǎn)發(fā)平面的完全解耦，為網(wǎng)絡(luò)虛擬化提供有效支撐，其特征是控制與傳輸分離、集中式控制以及軟件可編程。軟件定義網(wǎng)絡(luò)可以降低網(wǎng)絡(luò)控制和管理成本，使網(wǎng)絡(luò)控制與網(wǎng)絡(luò)管理在網(wǎng)絡(luò)運用方面具有很大靈活性，對改善網(wǎng)絡(luò)結(jié)構(gòu)的僵化問題非常有效。SDN易于解決小規(guī)模網(wǎng)絡(luò)中的問題，若將SDN部署在較大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)中，其集中式控制平面的可擴展性和性能等都將會面臨挑戰(zhàn)。隨著網(wǎng)絡(luò)規(guī)模的日益擴增，以及流量需求的迅速增加，單個控制器已無法滿足現(xiàn)有的網(wǎng)絡(luò)需求。為解決該問題，眾多研究者相繼提出具有多控制器的分布式SDN架構(gòu)，雖然分布式控制器的部署方案能夠有效地改善網(wǎng)絡(luò)可靠性和可擴展性，但其使得負載均衡性能又面臨挑戰(zhàn)。負載均衡技術(shù)提高了網(wǎng)絡(luò)設(shè)備和服務(wù)器等資源利用率，其可拓展現(xiàn)有的網(wǎng)絡(luò)設(shè)備，增加網(wǎng)絡(luò)吞吐量，提高網(wǎng)絡(luò)速率和增強網(wǎng)絡(luò)整體運用能力。劉必果[2]針對單一的負載均衡架構(gòu)，提出基于層結(jié)構(gòu)模型的控制平面負載均衡算法，但該算法無法動態(tài)地改變控制器數(shù)目。趙季紅等[3]提出基于Q-learning算法的動態(tài)交換機遷移算法，該算法將所有交換機都看作是普通的交換機，對交換機的重要程度沒有做出劃分。Min等[4]提出基于Q-learning算法的動態(tài)控制器負載均衡算法，該算法對SDN交換機遷移模型進行了優(yōu)化，但沒有考慮交換機的重要性程度。Chen等[5]提出彈性分布式控制器能夠根據(jù)網(wǎng)絡(luò)中的負載程度，動態(tài)地改變控制器數(shù)目。但該方案只考慮了單個控制器在負載過載時的情況，其采用就近遷移的策略，雖能減少交換機和控制器之間的延遲，但若鄰近控制器的負載程度過大，將會增加交換機遷移次數(shù)，甚至需添加新的控制器，效率并不高。針對上述提到的問題，以SDN控制器負載均衡度最小化作為優(yōu)化目標，提出一種基于Q-learning算法區(qū)分交換機等級的SDN控制器負載均衡算法。算法面向交換機等級進行遷移設(shè)計，不同重要等級的交換機采取不同的遷移方式，為保證交換機的安全性，選取獲得Q值最大的動作中連接關(guān)鍵交換機數(shù)目最少的動作作為最優(yōu)策略。算法在實現(xiàn)SDN控制器負載均衡的同時，避免高等交換機遷移至同一控制器，提升了全網(wǎng)絡(luò)生存性。

1 SDN中交換機動態(tài)遷移問題建模

(1)

(2)

(3)

(4)

(5)

式(1)定義為連接到控制器的交換機數(shù)目。式(2)定義為連接到控制器的關(guān)鍵交換機數(shù)目。式(3)定義為控制器負載，表示其連接的所有交換機的流請求總和。式(4)定義為所有控制器所連接交換機的平均負載值。如式(5)所示，SDN中區(qū)分交換機等級的控制器負載均衡算法的優(yōu)化目標是使控制器的負載均衡度最小。為了得到優(yōu)化解，一些約束是交換機遷移問題所固有的，即延遲約束、二元約束和代數(shù)約束[8-9]。

s.t.： min(max(dij))≤TD

(6)

e

(7)

(8)

(9)

(10)

式(6)表示延遲約束，指控制器到交換機的最大延遲的最小值必須小于閾值TD，控制器j到交換機i的延遲定義為dij。式(7)表示成本限制，遷移交換機的數(shù)目被定義為遷移成本，標記為e，遷移成本的最大值必須小于閾值TE。式(8)表示二進制約束，表示一個交換機只能連接一個專用控制器。式(9)表示代數(shù)約束，SDN中連接到控制器的交換機總數(shù)等于NS。式(10)表示SDN中連接到控制器的關(guān)鍵交換機的總數(shù)等于NZS。交換機的遷移過程如圖1所示，關(guān)鍵交換機S2與普通交換機S3從控制域C分別劃分至控制域A和B，控制器C1與控制器C2負載相差不大，但控制器C2連接了關(guān)鍵交換機S1，所以遷移交換機時將關(guān)鍵交換機S2從控制器C3遷移至控制器C1，將普通交換機S3從控制器C3遷移至控制器C2。此遷移方案在實現(xiàn)控制器負載均衡的基礎(chǔ)上，有效地提升了關(guān)鍵交換機的安全性，提高了網(wǎng)絡(luò)生存性。

圖1 交換機的遷移過程

2 SDN中交換機重要性等級的劃分

實際情況下，整個網(wǎng)絡(luò)中每臺交換機的重要程度并不相同，不同重要程度的交換機遷移優(yōu)先性會存在差異。本文根據(jù)網(wǎng)絡(luò)中每臺交換機的節(jié)點度數(shù)進行交換機重要性等級的劃分，每個交換機作為節(jié)點，每個節(jié)點與網(wǎng)絡(luò)中其他節(jié)點之間的關(guān)聯(lián)邊總數(shù)定義為該交換機的節(jié)點度數(shù)。每臺交換機節(jié)點度數(shù)的不同，導(dǎo)致交換機重要程度存在差異，設(shè)網(wǎng)絡(luò)拓撲結(jié)構(gòu)中某交換機的節(jié)點度數(shù)為p，則該交換機的附加回報函數(shù)為：

RK=λpK=1,2,…,n

(11)

式中：RK表示交換機的重要程度，RK值越大，交換機的重要性程度越強。λ是一個參數(shù)，依實際情況來定，無實際意義。根據(jù)特定的網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖，本文定義關(guān)鍵交換機的重要程度門限值為Th，其具體值由實際情況而定。

當RK≤Th時，該交換機劃分為普通交換機。對于普通交換機，其遷移方案主要考慮Q-learning算法，實現(xiàn)負載均衡。當RK>Th時，該交換機劃分為關(guān)鍵交換機。RK值越大，說明交換機重要程度越高。遷移關(guān)鍵交換機時，結(jié)合RK和Q-learning算法，實現(xiàn)負載均衡。本文基于保證交換機的安全性與提升網(wǎng)絡(luò)生存性，遷移交換機時，控制器作為遷移目標，應(yīng)避免將關(guān)鍵交換機遷移至同一控制器，保證同一控制器連接的關(guān)鍵交換機的數(shù)量最小化。

3 算法設(shè)計

3.1 算法介紹

運用Q-learning算法的自學(xué)習(xí)特性[10]，需確定一些算法相關(guān)的要素，并動態(tài)選擇系統(tǒng)性能指標最優(yōu)的動作。算法模型加入了特征模塊，原理是通過區(qū)分交換機等級，得到附加回報函數(shù)，對外界環(huán)境反饋一個調(diào)和函數(shù)，調(diào)和函數(shù)結(jié)合環(huán)境中的回報函數(shù)，形成一種新的回報函數(shù)。SDN系統(tǒng)模塊與環(huán)境的交互示意圖如圖2所示。

圖2 基于Q-learning的SDN控制器系統(tǒng)模塊與環(huán)境的交互示意圖

一個強化學(xué)習(xí)系統(tǒng)不僅有智能體和環(huán)境，還有四個基本元素：回報函數(shù)，值函數(shù)，選擇策略和環(huán)境模型(非必需)[11]。以下是Q-learning算法的幾個重要因素。

3.2 狀態(tài)空間

智能體合理選擇動作的基礎(chǔ)是劃分狀態(tài)空間。基于Q-learning算法的SDN區(qū)分交換機等級的控制器負載均衡算法，其將所有控制器構(gòu)成的集合定義為狀態(tài)空間，即{State}={C1,C2,…，Cj,…,CNC}。

3.3 動作空間

對Q-learning算法，單個狀態(tài)只能選擇單個動作，在SDN中，根據(jù)就近原則，設(shè)置結(jié)構(gòu)中有n個交換機和m個控制器，預(yù)先將n個交換機隨機分配給m個核心控制器管理，所有交換機到核心控制器的連接作為動作空間，即A={(C1,S1),(C2,S2)，…,(Cj,Sj),…,(CNC,SNS)}。

若交換機為普通交換機，依據(jù)Q-learning算法求出Q值最大的控制器作為遷移目標，進行交換機的遷移。若交換機為關(guān)鍵交換機，根據(jù)交換機的附加回報函數(shù)RK結(jié)合Q-learning算法求出最大Q值。若最大Q值的遷移目標只有一個，則該目標控制器作為遷移目標，進行交換機的遷移；若最大Q值的遷移目標有多個，則將連接關(guān)鍵交換機數(shù)目最少的目標控制器作為遷移目標，進行交換機的遷移。

3.4 回報函數(shù)

回報函數(shù)r(s,a)是指智能體在與環(huán)境的不斷交互中，環(huán)境對智能體動作好壞產(chǎn)生的一種評價。控制器從動作集合中選擇某一動作后，網(wǎng)絡(luò)環(huán)境會對這個動作作出評價，給予一個獎勵值，并發(fā)生狀態(tài)轉(zhuǎn)移[12]。控制器從某個動作得到的回報函數(shù)值越大，此后控制器再次選擇該動作的概率就越大。控制器從某個動作得到的回報函數(shù)值越小，此后控制器再次選擇該動作的概率就越小。基于回報函數(shù)r(s,a)的設(shè)計，期望分配給每個控制器的關(guān)鍵交換機的數(shù)目最小化，回報函數(shù)如下式所示：

(12)

3.5 搜索策略

Q-learning算法中，首先定義一個值函數(shù)Q(s,a)，表示在狀態(tài)s下執(zhí)行動作a(i,j)獲得的未來獎勵值。其次，進行迭代運算繼續(xù)優(yōu)化Q函數(shù)，根據(jù)Q函數(shù)進行決策，如下式所示：

(13)

式(13)表示一種動作選擇策略，即在狀態(tài)s下選擇動作a(i,j)的規(guī)則。若獲得最大Q值的動作只有一個，則采取獲得最大Q值的動作a(i,j)作為最優(yōu)策略；若獲得最大Q值的動作有多個，則采取獲得最大Q值動作中連接關(guān)鍵交換機數(shù)目最少的動作a(i,j)作為最優(yōu)策略。

3.6 Q值更新

Q-learning算法的核心思想是采用數(shù)值迭代求解方法逼近最優(yōu)Q值。在Q-learning算法學(xué)習(xí)過程中，通過迭代計算Q(s,a)逼近最優(yōu)值函數(shù)。首先預(yù)設(shè)一個m×n階的Q矩陣，初始化Q矩陣并設(shè)初始值為0。其次根據(jù)網(wǎng)絡(luò)拓撲圖中交換機的節(jié)點個數(shù)，得到衡量交換機重要程度的附加回報函數(shù)RK。最后計算出回報函數(shù)r(s,a)，根據(jù)回報函數(shù)進行值函數(shù)的更新，即Q(s,a)，其表示最大折扣未來獎勵函數(shù)為：

(14)

(15)

3.7 偽代碼

將Q-learning算法思想體現(xiàn)在區(qū)分交換機等級的SDN控制器負載均衡問題中，根據(jù)Q-learning算法思想定義區(qū)分交換機等級的SDN控制器系統(tǒng)的狀態(tài)空間、動作空間、策略函數(shù)、回報函數(shù)以及值函數(shù)，確定遷移方案以實現(xiàn)SDN控制器負載均衡。基于Q-learning算法的區(qū)分交換機等級的SDN控制器負載均衡算法偽代碼如算法1所示。

算法1智能學(xué)習(xí)算法

1： 策略初始化：

2：fors∈S，a∈Ado

3： 初始化Q(s，a)

4：endfor

5： 確定當前狀態(tài)sc，前一狀態(tài)，s=sc，前一動作a=A0，下一狀態(tài)sn

6：repeat

7： 等待(學(xué)習(xí)間隔)

8： 策略更新：

9： 讀s，a，sn

10： 確定基于特征模塊的附加返回函數(shù)RK

11： 觀察虛擬網(wǎng)絡(luò)性能并確定前動作的獎勵函數(shù)r

12： 迭代計算進行Q表更新

13： 動作選擇：

14： 確定當前狀態(tài)sc

15： 選擇一個動作，ac∈A，使用給定的動作選擇準則的相應(yīng)狀態(tài)

16： 采取行動ac，決定下一個狀態(tài)s′

17： 設(shè)置s=sc，a=ac，sn=s′

18：until學(xué)習(xí)停止

4 仿真分析及結(jié)果

4.1 算法仿真環(huán)境

現(xiàn)有的通過Q-learning算法模擬SDN控制器負載均衡的問題中，沒有考慮到交換機的重要性，本文著重分析劃分交換機重要性等級對基于Q-learning算法的SDN控制器的負載均衡度的影響，不同學(xué)習(xí)速率α、學(xué)習(xí)參數(shù)γ與關(guān)鍵交換機參數(shù)kS三者共同作用下SDN控制器負載均衡度的變化，為保護交換機的安全，保證在核心控制器下連接的關(guān)鍵交換機數(shù)目最小化。本文用于網(wǎng)絡(luò)仿真的拓撲圖為NSFMET[13]網(wǎng)絡(luò)拓撲圖，如圖3所示。設(shè)置該網(wǎng)絡(luò)拓撲中包含3個控制器，10個交換機。10個交換機按就近原則分別劃分到3個核心控制器控制范圍內(nèi)，即m=3，n=10。交換機等級的區(qū)分根據(jù)實際情況來定，根據(jù)每個交換機的節(jié)點個數(shù)，將p大于3的所有交換機設(shè)為關(guān)鍵交換機。將網(wǎng)絡(luò)拓撲中10個交換機等級劃分為3個關(guān)鍵交換機和7個普通交換機，則交換機5、8、13將作為關(guān)鍵交換機，剩下的交換機都作為普通交換機。kS是關(guān)鍵交換機的參數(shù)，依實際情況來設(shè)定大小，以確保SDN控制器系統(tǒng)達到最穩(wěn)定的狀態(tài)。學(xué)習(xí)參數(shù)γ為折扣系數(shù)，取值[0,1]。系數(shù)α是Q-learning算法中的動作遷移的學(xué)習(xí)效率，依實際情況取值，與交換機關(guān)鍵參數(shù)kS相結(jié)合，使SDN控制器系統(tǒng)達到最理想最穩(wěn)定的狀態(tài)。每個控制器所承受的負載有限，當其負載變化超過自身所承受范圍時，選擇最優(yōu)策略，將周圍其他核心控制器下的交換機遷移到該核心控制器下，從而實現(xiàn)SDN控制器負載均衡。同理，其他核心控制器發(fā)生超負載情況時，該核心控制器下的交換機也可以遷移到其他核心控制器下，進行負載均衡。

圖3 NSFMET網(wǎng)絡(luò)拓撲圖

4.2 Q-learning算法對控制器負載的影響

運行算法前，控制器之間負載值相差大會導(dǎo)致控制器出現(xiàn)過載、空閑或低負載的狀態(tài)，需解決資源使用不充分或者控制器資源浪費的問題。運行Q-learning算法后，控制器之間負載越來越接近，更好地達到負載均衡的效果。如圖4所示，運行Q-learning算法之前，控制器負載嚴重失衡，負載差值大，控制器負載值曲線波動大。而隨著Q-learning算法迭代次數(shù)的增多，每個控制器的負載值變化曲線越居平穩(wěn)，曲線波動越來越小，最后SDN控制器之間達到一種最平衡最理想的狀態(tài)，充分地利用每個控制器的資源，提高整體網(wǎng)絡(luò)資源利用率。仿真結(jié)果顯示，剛開始三個控制器負載分別為0.532、1.273、5.16，負載差值過大，控制器1與控制器11負載相差4.5，控制器1處于低負載狀態(tài)，而控制器11處于過載狀態(tài)，負載嚴重失衡。實現(xiàn)負載均衡之后，三個控制器的負載分別為1.972、2.825、1.078，負載差值明顯變小，控制器1與控制器11負載差值從4.5減少到0.894，很好地解決了控制器1低負載而控制器11負載過載的狀態(tài)。本文算法很好地解決了控制器之間的負載不均衡問題，使控制器達到一種最理想的狀態(tài)。

圖4 控制器負載均衡過程中負載變化圖

4.3 劃分交換機等級對控制器負載均衡度的影響

在文獻[4]中，采用Q-learning算法對SDN控制器交換機遷移模型進行了優(yōu)化，優(yōu)化過程中沒有考慮交換機的重要程度，本文區(qū)分了交換機等級，并引入了關(guān)鍵交換機的重要性參數(shù)kS。圖5所示為不考慮學(xué)習(xí)參數(shù)γ與學(xué)習(xí)速率α的變化，在學(xué)習(xí)參數(shù)γ與學(xué)習(xí)速率α取一定值時，仿真交換機重要參數(shù)kS對控制器負載均衡度的影響。隨著kS的變化，曲線波動與收斂性也發(fā)生變化，收斂速度也發(fā)生變化，學(xué)習(xí)速率α與學(xué)習(xí)參數(shù)γ分別為定值0.5與0.9。當kS=0時，不考慮交換機重要性，負載均衡度低，但是曲線的波動較大，曲線收斂速度較慢，不能很好地體現(xiàn)出關(guān)鍵交換機的重要性。當kS=0.1時，曲線收斂速度快，控制器負載均衡度曲線走勢也相對穩(wěn)定。在kS=0.2與kS=0.25時，曲線收斂速度較快，其曲線波動較小，負載均衡度各自收斂在0.664與0.752處，收斂效果較好。kS=0.3時，收斂速度與其他相差不大，曲線波動比較大，負載均衡度收斂在0.842處，不是最理想狀態(tài)。可以看出kS=0.2時收斂效果最好，曲線波動較小，在保護交換機的前提下可以達到最理想的狀態(tài)，最后負載均衡度收斂為0.664。因此，基于Q-learning區(qū)分交換機等級的SDN控制器負載均衡算法，不僅可以實現(xiàn)SDN控制器的負載均衡，又可以確保關(guān)鍵交換機的安全性與系統(tǒng)的穩(wěn)定性。

圖5 重要交換機參數(shù)kS對控制器負載均衡度的影響圖

4.4 不同參數(shù)共同作用下的SDN控制器負載均衡度

Q-learning算法中學(xué)習(xí)參數(shù)γ對控制器負載均衡有很大的影響，在一定的范圍內(nèi)，可促進控制器負載均衡度的收斂速度，但超過最優(yōu)值時，會使負載均衡度數(shù)值收斂速度變慢，曲線波動變大。考慮交換機重要參數(shù)kS、學(xué)習(xí)速率α與學(xué)習(xí)參數(shù)γ三者共同作用下對SDN控制器負載均衡度的影響。給出不同的學(xué)習(xí)參數(shù)γ，不同的學(xué)習(xí)速率α與不同的重要交換機參數(shù)kS，三種參數(shù)共同影響下SDN控制器負載均衡度的曲線走勢如圖6所示。由于數(shù)據(jù)量與篇幅等的原因，只給出了具有代表意義的四組數(shù)據(jù)進行比較。當kS=0.2，γ=0.9，α=0.2時，負載均衡度收斂在0.664處，收斂速度較快，該曲線相對其他曲線處于很平穩(wěn)的狀態(tài)，收斂效果很好。當kS=0.4，γ=0.9，α=0.3時，負載均衡度收斂值為1.019，收斂速度最快，曲線波動較大。當kS=0.3，α=0.5，γ=0.5時，負載均衡度收斂值為0.841 5，收斂速度適中，曲線波動較大，負載均衡效果不是最佳，非最理想的狀態(tài)。當kS=0.25，α=0.8，γ=0.6時，負載均衡度最后收斂在0.669處，曲線波動最大，收斂速度最慢。當kS=0.2，α=0.7，γ=0.9時，收斂值為0.663 7，其曲線波動最小，收斂效果最好，收斂值更小，說明在一定程度上學(xué)習(xí)速率越大，收斂值越小，負載均衡度數(shù)值為最優(yōu)解，系統(tǒng)達到最理想最穩(wěn)定的狀態(tài)。

圖6 學(xué)習(xí)速率α，學(xué)習(xí)參數(shù)γ與重要交換機參數(shù)kS三者對SDN控制器負載均衡度的影響圖

4.5 控制器負載均衡性與網(wǎng)絡(luò)生存性

基于SDN控制器負載均衡的相關(guān)算法對比仿真結(jié)果如表1所示。本文算法實現(xiàn)了較好的負載均衡功能，并且考慮了交換機的安全性。運行結(jié)束后，關(guān)鍵交換機8從控制器11遷移至控制器4，關(guān)鍵交換機5從控制器4遷移至控制器1。仿真結(jié)果表明，本文算法可以有效地完成控制器負載均衡功能，同時可以有效根據(jù)控制器等級進行遷移分配，在單個控制器故障時避免多個高等級關(guān)鍵交換機癱瘓，提升了網(wǎng)絡(luò)生存性。

表1 相關(guān)算法的對比

5 結(jié) 語

本文將Q-learning算法的自學(xué)習(xí)特性與區(qū)分交換機等級的SDN控制器負載均衡問題相結(jié)合，提出基于Q-learning算法區(qū)分交換機等級的SDN控制器負載均衡算法，劃分交換機的重要性等級，提出衡量交換機的重要性參數(shù)kS，面向交換機等級進行遷移設(shè)計。首先對SDN中控制器部署問題建模為以最小化控制器負載均衡度為目標的線性規(guī)劃問題。其次根據(jù)交換機的節(jié)點度數(shù)劃分交換機等級。最后基于Q-learning反饋機制設(shè)計SDN區(qū)分交換機等級的控制器負載均衡算法，重新定義狀態(tài)空間、動作空間、選擇策略、回報函數(shù)以及值函數(shù)，確定遷移方案以保證控制器負載均衡。仿真結(jié)果表明，與現(xiàn)有的控制器負載均衡算法相比，區(qū)分交換機等級的SDN控制器負載均衡算法能夠在完成負載均衡的同時，根據(jù)交換機等級實現(xiàn)遷移，保證多個高等級關(guān)鍵交換機不會遷移至同一個控制器，有效地降低了控制器故障帶來的網(wǎng)絡(luò)風(fēng)險，提升了網(wǎng)絡(luò)生存性。