基于博弈論的SDN多控制器負(fù)載均衡機制研究

劉曉鳳，王靈矯**，郭 華

(1. 湘潭大學(xué) 信息工程學(xué)院，湖南 湘潭 411105；2. 湘潭大學(xué) 智能計算與信息處理教育部重點實驗室，湖南 湘潭 411105)

軟件定義網(wǎng)絡(luò)（Software Defined Network，SDN）體系結(jié)構(gòu)的主要特點在于控制平面與數(shù)據(jù)平面的解耦，具有可編程、自動化和網(wǎng)絡(luò)控制等特性，操作者可靈活構(gòu)建可編程網(wǎng)絡(luò)以適應(yīng)不斷變化的網(wǎng)絡(luò)環(huán)境. 網(wǎng)絡(luò)規(guī)模的擴展使得單控制器的部署已不能滿足現(xiàn)有網(wǎng)絡(luò)需求. 因此，一些研究人員相繼提出了一系列邏輯上集中，物理上分布的多控制器體系結(jié)構(gòu)（HyperFlow、Onix、Kandoo）[1-3]. 在物理上集中的控制平面由整個網(wǎng)絡(luò)的單個控制器組成，這是理論上理想的設(shè)計選擇. 但是，隨著SDN中交換機數(shù)量的增加，集中控制器在處理越來越多的請求并同時努力實現(xiàn)相同的性能保證時，它可能變得不堪重負(fù). 而且，由于單點故障，SDN控制器的故障會導(dǎo)致整個網(wǎng)絡(luò)癱瘓. 因此，有人提出使用多個物理分布式SDN多控制器以提高系統(tǒng)的可擴展性和可靠性.

現(xiàn)有的分布式SDN多控制器體系結(jié)構(gòu)存在的問題之一是SDN交換機與控制器之間的靜態(tài)映射，使得控制平面無法適應(yīng)流量變化. 當(dāng)網(wǎng)絡(luò)中的流量發(fā)生巨大的變化時，如果SDN轉(zhuǎn)換控制器映射是靜態(tài)的，那么巨大的變化可能會導(dǎo)致控制器之間負(fù)載的不均衡，即有些超負(fù)荷，有些未充分利用. 過載的控制器將以增加的延遲響應(yīng)切換請求，從而惡化用戶的體驗.

目前現(xiàn)有的通過交換機確保負(fù)載均衡的方案，大多雖然能夠動態(tài)地調(diào)整網(wǎng)絡(luò)的負(fù)載，但是在交換機遷移過程中，對目標(biāo)控制器進行選取時，僅考慮時延或控制器容量，易導(dǎo)致目標(biāo)控制器選取僵化.簡單的主從控制器按距離分配進行交換機遷移時，當(dāng)最近鄰控制器負(fù)載較重時，易導(dǎo)致遷移震蕩問題.

針對多控制器負(fù)載不均衡問題，本文給出了一種基于博弈論的負(fù)載均衡機制（Game Theory Load Balancing，GTLB）. 其主要創(chuàng)新工作如下：

（1）結(jié)合交換機遷移思想，利用交換機遷移概率、交換機與控制器的傳輸時延和換機遷移成本實現(xiàn)GTLB機制的建模.

（2）構(gòu)建博弈域模型，實現(xiàn)了以遷移概率確定遷移交換機、粒子群算法選擇目標(biāo)控制器和遷移計時模型，提高交換機遷移效率.

（3）進行仿真實驗，驗證GTLB機制性能.

1 相關(guān)工作

傳統(tǒng)的SDN實現(xiàn)依賴于一個集中式控制器，在性能和可伸縮性方面有一些限制. 一些研究工作表明，分布式控制器的部署是解決問題的一種有效的方法[4-6]. 為了在分布式網(wǎng)絡(luò)中獲得更好的性能和可伸縮性，Bari等[7]提出一個框架，該框架可以調(diào)整控制器的數(shù)量并委托每個控制器，可以最低限度降低通信開銷的同時最大程度減少流建立時間. 但是，這很容易導(dǎo)致網(wǎng)絡(luò)不穩(wěn)定. 為了實現(xiàn)一個可擴展的SDN控制平面，Cheng等[8]提供了一個博弈決策機制，將交換機遷移問題表示為一個具有多個資源維度約束的集中式可用資源最大化問題. 對多控制器負(fù)載均衡的研究過程中，Heller等[9]以交換機和控制器之間的時延為遷移度量，研究了控制器不同部署位置對交換機遷移的影響，取得了一定的理論成果. Dixit等[10]提出彈性分布式控制器體系結(jié)構(gòu)“ElastiCon”，以網(wǎng)絡(luò)狀態(tài)為據(jù)增加或減少控制器池的剩余控制器，遷移控制器之間的負(fù)載. 史久根等[11]提出了多控制器優(yōu)化方案，重點關(guān)注控制器負(fù)載均衡和控制器之間的時延，權(quán)衡多個相互矛盾實現(xiàn)優(yōu)化目標(biāo). Adlen等[12]提出使用博弈論優(yōu)化部署SDN控制器，以時延、通信開銷、控制器負(fù)載均衡獲取均衡度量，實現(xiàn)控制器部署數(shù)量和位置的優(yōu)化. Fan等[13]提出基于博弈論的單一控制器主控制器重選機制.

2 分析與建模

2.1 問題描述多域SDN網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示，4個控制器分別與交換機連接構(gòu)成子域. 每個交換機可以配備3種控制器：主控制器、從控制器、等價控制器[14]. 若子域2聚集了大量的流請求，c2就會過載，它所控制的交換機通過選擇從控制器作為交換機新的主控制器來實現(xiàn)交換機遷移. 多域SDN網(wǎng)絡(luò)的交換機遷移需要完成兩項工作：①確定遷移交換機和目標(biāo)控制器；②設(shè)計有效的交換機遷移模式，提高負(fù)載均衡效率.

2.2 SDN博弈模型組成

2.2.1 SDN博弈域 博弈域（Game Domain，GD）是一個臨時的、松散的且具有特定目標(biāo)的聯(lián)盟，SDN中的GD是為交換機遷移選定的區(qū)域且僅與過載控制器和相關(guān)相鄰控制器有關(guān)[15]. 在圖1所示的4個子域中，c2是過載控制器，G4負(fù)載較高，則G2的GD可為F2={G1,G2,G3}.

圖1 分布式多控制器部署的體系架構(gòu)Fig. 1 An architecture for distributed multi-controller deployment

GTLB機制的基本思想是構(gòu)建博弈域和實現(xiàn)交換機無縫遷移. 過載控制器cr（r∈（1,M））和相鄰的子域構(gòu)建GD，并將過載控制器控制子域下的交換機si（i∈（1,N））遷移至目標(biāo)控制器ck(k∈（1,M））.

2.2.2 SDN博弈模型 根據(jù)圖論相關(guān)知識，整個網(wǎng)絡(luò)可用無向圖G=(V,E) 表示，其中V是網(wǎng)絡(luò)的所有節(jié)點集合，E是所有鏈路的集合. 假設(shè)一個網(wǎng)絡(luò)由M個控制器和N個交換機組成，控制器集合C={c1,c2,···,cM}，交換機集合S={s1,s2,···,sN}，所以節(jié)點總數(shù)|V|=M+N. 假設(shè)所有控制器的位置都已優(yōu)化好[16]. 設(shè)備i和j之間的跳轉(zhuǎn)定義為dij，xij表示交換機si和控制器cj的連接關(guān)系為

圖1中，GTLB博弈模型定義為 θGTLB={C,L,U}，其中C是博弈的參與者集合，過載控制器c2作為博弈者向鄰近控制器發(fā)送構(gòu)建博弈域請求，博弈的參與者集合為C={c1,c2,c3}；L是每個參與者可選擇的行動方案集合，若控制器c2選擇交換機si為遷移對象，每個參與者cr具有兩種策略，即Lr={cr接受交換機si,cr拒絕交換機si}；U是所有參與者在某一組特定策略組合下的效用，其效用函數(shù)包含傳輸時延和遷移成本兩部分[17-18].

定義1交換機si與控制器cj之間的傳輸時延為二者之間的最小距離，則所有交換機與控制器之間的傳輸時延Vij如式（2）所示：

定義2交換機遷移成本Pm包括遷移規(guī)則安裝成本Pru、通信成本Pc和遷移請求成本Pre.

確定需要遷移的交換機si后，控制器cr必須在域內(nèi)將flow_mod規(guī)則安裝到遷移交換機. 則Pru如下：

其中，δ表示flow_mod包的平均大小.

遷移交換機si和目標(biāo)控制器ck進行正常的信息傳遞時產(chǎn)生交換機通信成本為

其中，ε表示交換機的平均通信速度，xir和xlk分別表示cr和ck域內(nèi)交換機與控制器的連接關(guān)系.

當(dāng)遷移交換機向目標(biāo)控制器發(fā)送流請求時，生成Pre，表示為

其中，mindik表示遷移交換機到目標(biāo)控制器的最小跳數(shù).

因此，交換機遷移成本Pm是上述3種成本的總和，表示為

綜合考慮控制器與交換機之間的傳輸時延和交換機遷移成本，將博弈域中的目標(biāo)控制器的選擇問題轉(zhuǎn)化為多代價線性規(guī)劃問題進行求解，因此，效用函數(shù)

其中，α、β表示權(quán)值，F(xiàn)r和Fk表示任意兩個不同的博弈域，R表示Fr內(nèi)的控制器數(shù)量. 約束條件分別表示子域中每一個交換機只有一個主控制器. GD中的控制器數(shù)量少于網(wǎng)絡(luò)控制器的總數(shù). 任意兩個GD之間沒有交集，并且控制器只屬于一個GD.

3 GTLB的設(shè)計與實現(xiàn)

基于GTLB的基本原理及建模思想，GTLB的流程圖如圖2所示，主要分為3個階段：①分析網(wǎng)絡(luò)負(fù)載信息，判定控制器的負(fù)載情況；②利用博弈論和粒子群算法選擇遷移交換機和目標(biāo)控制器[19]；③設(shè)置倒計時實現(xiàn)交換機無縫遷移和控制器角色轉(zhuǎn)換[20]；最后判斷控制器負(fù)載均衡狀況. 如果判定結(jié)果符合控制器資源利用率的約束條件，跳出GTLB，否則返回第一階段繼續(xù).

圖2 基于博弈論的負(fù)載均衡機制的流程圖Fig. 2 Flow chart of load balancing mechanism based on Game Theory

3.1 收集網(wǎng)絡(luò)負(fù)載信息，構(gòu)建博弈域網(wǎng)絡(luò)負(fù)載信息包括鏈路信息，跳轉(zhuǎn)信息和控制器資源利用率γr，控制器資源利用率如式（8）所示，表示控制器的處理容量被其管理下的交換機占用的程度. 并根據(jù)所有控制器的資源利用率求得這些控制器平均資源利用率.

其中，λi表示交換機si的流量請求速率（主要包括Packet-in消息），Ψr表示cr控制的交換機數(shù)目，ωr表示控制器的處理容量.

博弈域的構(gòu)造采用遍歷搜索方法，流程如下：收集網(wǎng)絡(luò)中的各類信息，設(shè)定控制器的過載條件，如式（10）所示，控制器的過載情況由控制器狀態(tài)γr決定. 如果 0.9≤γr≤1，那么控制器cr是過載的，cr將向相鄰的控制器cn發(fā)送請求，cn有兩種選擇意向，根據(jù)式（11）的相應(yīng)條件選擇適當(dāng)?shù)牟呗訮，聯(lián)合所有同意的鄰居控制器構(gòu)建博弈域.

3.2 遷移目標(biāo)選擇

3.2.1 遷移交換機si的選擇 為了盡可能快地降低過載控制器的負(fù)載，優(yōu)先選擇遷移流請求率較高且距離過載控制器較遠的交換機. 交換機的遷移概率定義為ρir，如式（12）所示：

其中，ηir表示交換機si在控制器cr上所占用的控制資源，dir表示交換機與控制器之間的跳轉(zhuǎn). 遷移ρir值最大的交換機被遷移.

3.2.2 目標(biāo)控制器ck的選擇 利用粒子群算法在博弈域中選擇最優(yōu)目標(biāo)控制器，算法步驟如下：

步驟 1初始化粒子的位置x0和速度v0;

步驟 2根據(jù)式（13）計算每個粒子的適應(yīng)值，找出每個粒子的個體極值p、全局極值g，

步驟 3根據(jù)公式（14）和（15）更新粒子的速度與位置

步驟 4計算更新位置粒子的適應(yīng)度；

步驟 5更新個體極值、全局極值；

步驟 6重復(fù)步驟2～5，直至達到規(guī)定迭代次數(shù).

3.3 目標(biāo)遷移實現(xiàn)GTLB的遷移過程如圖3所示. 過載控制器cr選擇遷移交換機si并向目標(biāo)控制器ck發(fā)送遷移信號Move.ck接受到遷移信號后回復(fù)Move-start消息，選擇一個隨機數(shù)n開始倒計時(遷移交換機和相鄰控制器數(shù)量越多，以及控制器資源利用率越高，倒計時設(shè)置越短)，其中n由式（19）生成，其中l(wèi)是與控制器cr相連的交換機集合，Nr是相鄰控制器cn的集合. 在n下降到0之前，如果交換機si遷移完成，si的主控制器轉(zhuǎn)移到ck，cr成為的si從控制器，GPF自動解散，廣播更新消息到整個網(wǎng)絡(luò). 倒計時超時或cr仍處于超載狀態(tài)，重置倒計時和GTLB回到重建博弈域.

圖3 交換機無縫遷移具體過程Fig. 3 Switch seamless migration process

4 仿真實驗

4.1 仿真環(huán)境設(shè)置根據(jù)文獻[21]建立仿真實驗環(huán)境. 采用Ubuntu 16.04操作系統(tǒng)，F(xiàn)loodlight為實驗控制器，Mininet部署網(wǎng)絡(luò)拓?fù)? 實驗拓?fù)淙∽設(shè)S3E，通過Iperf軟件模擬交換機發(fā)包分組測試算法.

以文獻[22]描述的流量特征配置實驗參數(shù)，流的大小呈現(xiàn)分布式和具有不同的到達速率，流平均速率為500 K/s. 假設(shè)所有控制器具有相同性能，處理容量的上限為ωr=10 MB，資源利用率γr是在0和1之間，F(xiàn)low_mod數(shù)據(jù)包δ=30 Byte，交換機間的通信速率ε=15 kb/s，α∶β=1∶1，學(xué)習(xí)因子c1=c2=2.

4.2 仿真分析實驗比較GTLB與文獻[4]中多控制器備份機制（Multi Controller Backup，MCB）、文獻[18]中分布式?jīng)Q策機制（Distributed Policy based Controller Load Balancing，DPCLB）、文獻[21]中非合作博弈遷移機制（Non-cooperative game migration mechanism，GAME-SM）等機制的性能. MCB通過控制器備份池應(yīng)對流量的激增. DPCLB考慮多個負(fù)載代價，通過貪婪算法進行優(yōu)化求解；GAMESM基于非合作博弈的交換機遷移算法以動態(tài)平衡控制平面負(fù)載. 實驗分別驗證了網(wǎng)絡(luò)通信開銷、流表建立時間、流表平均建立時間和控制器資源利用率等性能.

網(wǎng)絡(luò)通信開銷情況如圖4所示，通信總開銷為控制器與控制器之間的通信開銷和控制器與交換機之間的通信開銷總和. 從控制器的通信開銷方面看，GAME-SM是最高的，MCB位居第二，DPCLB和GTLB相差不大；從控制器與交換機自己的通信開銷來看，MCB是最大的，GAME-SM開銷較高，DPCLB和GTLB差別不大. 因此，在實現(xiàn)負(fù)載均衡的基礎(chǔ)上，GTLB機制的總通信開銷最少，它相較于MCB、DPSLB、GAME-SM分別減少39.2%、5%、20.8%.

圖4 控制器與交換機及控制器之間的通信開銷Fig. 4 Communication overhead between controller and switch and controller

流表建立時間動態(tài)反映控制器負(fù)載的情況，它的情況如圖5所示. MCB和GAME-SM波動明顯.DPCLB和GTLB波動較小，GTLB劃分不干擾GPF，設(shè)置了控制器的倒計時數(shù)，避免了遷移沖突，GTLB的流表建立時間低于其它3種機制.

圖5 交換機流表建立時間Fig. 5 The setup time of switch flow table

流表平均建立時間通過對圖5中的實驗結(jié)果進行量化統(tǒng)計得到，如圖6所示. GTLB機制的流表平均建立時間相較于MCB、DPCLB、GAME-SM分別下降57.1%、14.3%、33.3%，平均縮短了0.12 s.

圖6 交換機流表平均建立時間Fig. 6 The setup time of average switch flow table

控制器資源利用率反映控制器負(fù)載的利用情況，利用率越高，控制器負(fù)載均衡性能越好. 如圖7所示. GAME-SM最低，MCB較低，DPCLB和GTLB相差不大，都能較好地實現(xiàn)控制器負(fù)載均衡和高效地資源利用，但GTLB部署了更少的控制器，控制器資源利用率提高了20.4%. 因此，GTLB控制器負(fù)載均衡性能最佳.

圖7 控制器資源利用率Fig. 7 The utilization of controller resource

5 結(jié)論

針對SDN 的控制器負(fù)載均衡問題，本文提出了基于博弈論的SDN多控制器負(fù)載均衡機制，優(yōu)化了控制器負(fù)載的動態(tài)均衡. GTLB機制結(jié)合交換機遷移，構(gòu)建博弈域模型，通過3個階段實現(xiàn)了交換機的協(xié)調(diào)遷移和控制器的角色轉(zhuǎn)換. 與其他機制相比，GTLB降低了網(wǎng)絡(luò)的總通信開銷，流建立時間平均縮短了0.12 s，控制器資源利用率提高了20.4%，控制器負(fù)載更為均衡. 今后的工作將集中在研究控制器博弈的最佳門限和解決粒子群算法后期收斂性差、易陷入局部最優(yōu)解的問題.