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

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

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

0 引 言

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

1 SDN中交換機動態遷移問題建模

(1)

(2)

(3)

(4)

(5)

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

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

(6)

e

(7)

(8)

(9)

(10)

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

圖1 交換機的遷移過程

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

實際情況下，整個網絡中每臺交換機的重要程度并不相同，不同重要程度的交換機遷移優先性會存在差異。本文根據網絡中每臺交換機的節點度數進行交換機重要性等級的劃分，每個交換機作為節點，每個節點與網絡中其他節點之間的關聯邊總數定義為該交換機的節點度數。每臺交換機節點度數的不同，導致交換機重要程度存在差異，設網絡拓撲結構中某交換機的節點度數為p，則該交換機的附加回報函數為：

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

(11)

式中：RK表示交換機的重要程度，RK值越大，交換機的重要性程度越強。λ是一個參數，依實際情況來定，無實際意義。根據特定的網絡拓撲結構圖，本文定義關鍵交換機的重要程度門限值為Th，其具體值由實際情況而定。

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

3 算法設計

3.1 算法介紹

運用Q-learning算法的自學習特性[10]，需確定一些算法相關的要素，并動態選擇系統性能指標最優的動作。算法模型加入了特征模塊，原理是通過區分交換機等級，得到附加回報函數，對外界環境反饋一個調和函數，調和函數結合環境中的回報函數，形成一種新的回報函數。SDN系統模塊與環境的交互示意圖如圖2所示。

圖2 基于Q-learning的SDN控制器系統模塊與環境的交互示意圖

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

3.2 狀態空間

智能體合理選擇動作的基礎是劃分狀態空間?；赒-learning算法的SDN區分交換機等級的控制器負載均衡算法，其將所有控制器構成的集合定義為狀態空間，即{State}={C1,C2,…，Cj,…,CNC}。

3.3 動作空間

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

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

3.4 回報函數

回報函數r(s,a)是指智能體在與環境的不斷交互中，環境對智能體動作好壞產生的一種評價。控制器從動作集合中選擇某一動作后，網絡環境會對這個動作作出評價，給予一個獎勵值，并發生狀態轉移[12]?？刂破鲝哪硞€動作得到的回報函數值越大，此后控制器再次選擇該動作的概率就越大。控制器從某個動作得到的回報函數值越小，此后控制器再次選擇該動作的概率就越小?；诨貓蠛瘮祌(s,a)的設計，期望分配給每個控制器的關鍵交換機的數目最小化，回報函數如下式所示：

(12)

3.5 搜索策略

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

(13)

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

3.6 Q值更新

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

(14)

(15)

3.7 偽代碼

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

算法1智能學習算法

1： 策略初始化：

2：fors∈S，a∈Ado

3： 初始化Q(s，a)

4：endfor

5： 確定當前狀態sc，前一狀態，s=sc，前一動作a=A0，下一狀態sn

6：repeat

7： 等待(學習間隔)

8： 策略更新：

9： 讀s，a，sn

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

11： 觀察虛擬網絡性能并確定前動作的獎勵函數r

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

13： 動作選擇：

14： 確定當前狀態sc

15： 選擇一個動作，ac∈A，使用給定的動作選擇準則的相應狀態

16： 采取行動ac，決定下一個狀態s′

17： 設置s=sc，a=ac，sn=s′

18：until學習停止

4 仿真分析及結果

4.1 算法仿真環境

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

圖3 NSFMET網絡拓撲圖

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

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

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

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

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

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

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

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

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

4.5 控制器負載均衡性與網絡生存性

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

表1 相關算法的對比

5 結 語

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