蔣雯麗 梁思遠(yuǎn) 趙芳利 趙 峰 王聰一

(西安郵電大學(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ò)可靠性和可擴展性，但其使得負(fù)載均衡性能又面臨挑戰(zhàn)。負(fù)載均衡技術(shù)提高了網(wǎng)絡(luò)設(shè)備和服務(wù)器等資源利用率，其可拓展現(xiàn)有的網(wǎng)絡(luò)設(shè)備，增加網(wǎng)絡(luò)吞吐量，提高網(wǎng)絡(luò)速率和增強網(wǎng)絡(luò)整體運用能力。劉必果[2]針對單一的負(fù)載均衡架構(gòu)，提出基于層結(jié)構(gòu)模型的控制平面負(fù)載均衡算法，但該算法無法動態(tài)地改變控制器數(shù)目。趙季紅等[3]提出基于Q-learning算法的動態(tài)交換機遷移算法，該算法將所有交換機都看作是普通的交換機，對交換機的重要程度沒有做出劃分。Min等[4]提出基于Q-learning算法的動態(tài)控制器負(fù)載均衡算法，該算法對SDN交換機遷移模型進(jìn)行了優(yōu)化，但沒有考慮交換機的重要性程度。Chen等[5]提出彈性分布式控制器能夠根據(jù)網(wǎng)絡(luò)中的負(fù)載程度，動態(tài)地改變控制器數(shù)目。但該方案只考慮了單個控制器在負(fù)載過載時的情況，其采用就近遷移的策略，雖能減少交換機和控制器之間的延遲，但若鄰近控制器的負(fù)載程度過大，將會增加交換機遷移次數(shù)，甚至需添加新的控制器，效率并不高。針對上述提到的問題，以SDN控制器負(fù)載均衡度最小化作為優(yōu)化目標(biāo)，提出一種基于Q-learning算法區(qū)分交換機等級的SDN控制器負(fù)載均衡算法。算法面向交換機等級進(jìn)行遷移設(shè)計，不同重要等級的交換機采取不同的遷移方式，為保證交換機的安全性，選取獲得Q值最大的動作中連接關(guān)鍵交換機數(shù)目最少的動作作為最優(yōu)策略。算法在實現(xiàn)SDN控制器負(fù)載均衡的同時，避免高等交換機遷移至同一控制器，提升了全網(wǎng)絡(luò)生存性。

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

(1)

(2)

(3)

(4)

(5)

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

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

(6)

e

(7)

(8)

(9)

(10)

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

圖1 交換機的遷移過程

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

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

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

(11)

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

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

3 算法設(shè)計

3.1 算法介紹

運用Q-learning算法的自學(xué)習(xí)特性[10]，需確定一些算法相關(guān)的要素，并動態(tài)選擇系統(tǒng)性能指標(biāo)最優(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)空間?；赒-learning算法的SDN區(qū)分交換機等級的控制器負(fù)載均衡算法，其將所有控制器構(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值最大的控制器作為遷移目標(biāo)，進(jìn)行交換機的遷移。若交換機為關(guān)鍵交換機，根據(jù)交換機的附加回報函數(shù)RK結(jié)合Q-learning算法求出最大Q值。若最大Q值的遷移目標(biāo)只有一個，則該目標(biāo)控制器作為遷移目標(biāo)，進(jìn)行交換機的遷移；若最大Q值的遷移目標(biāo)有多個，則將連接關(guān)鍵交換機數(shù)目最少的目標(biāo)控制器作為遷移目標(biāo)，進(jìn)行交換機的遷移。

3.4 回報函數(shù)

回報函數(shù)r(s,a)是指智能體在與環(huán)境的不斷交互中，環(huán)境對智能體動作好壞產(chǎn)生的一種評價?？刂破鲝膭幼骷现羞x擇某一動作后，網(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)獲得的未來獎勵值。其次，進(jìn)行迭代運算繼續(xù)優(yōu)化Q函數(shù)，根據(jù)Q函數(shù)進(jìn)行決策，如下式所示：

(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ò)拓?fù)鋱D中交換機的節(jié)點個數(shù)，得到衡量交換機重要程度的附加回報函數(shù)RK。最后計算出回報函數(shù)r(s,a)，根據(jù)回報函數(shù)進(jìn)行值函數(shù)的更新，即Q(s,a)，其表示最大折扣未來獎勵函數(shù)為：

(14)

(15)

3.7 偽代碼

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

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

1： 策略初始化：

2：fors∈S，a∈Ado

3： 初始化Q(s，a)

4：endfor

5： 確定當(dāng)前狀態(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： 迭代計算進(jìn)行Q表更新

13： 動作選擇：

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

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

圖3 NSFMET網(wǎng)絡(luò)拓?fù)鋱D

4.2 Q-learning算法對控制器負(fù)載的影響

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

圖4 控制器負(fù)載均衡過程中負(fù)載變化圖

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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