劉必果，束永安，付應(yīng)輝

(安徽大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,安徽 合肥 230601)

基于多目標(biāo)優(yōu)化的軟件定義網(wǎng)絡(luò)負(fù)載均衡方案

劉必果*，束永安，付應(yīng)輝

(安徽大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,安徽 合肥 230601)

(*通信作者電子郵箱15556983773@163.com)

針對軟件定義網(wǎng)絡(luò)(SDN)中控制平面的負(fù)載均衡問題，提出了一種基于多目標(biāo)優(yōu)化的動態(tài)交換機遷移算法(M-DSMA)。該算法首先將交換機與控制器之間的映射關(guān)系轉(zhuǎn)變?yōu)?- 1矩陣優(yōu)化問題；其次，通過基于NSGA-II的多目標(biāo)遺傳算法同時優(yōu)化控制平面負(fù)載均衡度和交換機遷移所產(chǎn)生的通信開銷這兩個相互沖突的目標(biāo)。在多目標(biāo)優(yōu)化過程中，利用適應(yīng)度函數(shù)選擇個體進(jìn)行交叉變異，隨后采用快速非支配排序?qū)ΨN群進(jìn)行精英策略，產(chǎn)生下一代種群，使得整個種群不斷進(jìn)化，搜索較優(yōu)的解。仿真實驗結(jié)果表示，相比于動態(tài)交換機遷移算法(DSMA)，M-DSMA在有效均衡控制平面負(fù)載的同時，降低了30%～50%的通信開銷，且在提高控制平面可擴展性方面具有明顯優(yōu)勢。

軟件定義網(wǎng)絡(luò)；負(fù)載均衡；多目標(biāo)優(yōu)化；遺傳算法；交換機遷移

0 引言

軟件定義網(wǎng)絡(luò)(Software Defined Network, SDN)[1]采用與傳統(tǒng)互聯(lián)網(wǎng)截然不同的控制架構(gòu)，將控制平面與數(shù)據(jù)平面分離，通過開放和可編程接口實現(xiàn)軟件定義[2]。隨著網(wǎng)絡(luò)規(guī)模的擴大，典型的單控制器結(jié)構(gòu)已經(jīng)不能滿足用戶的需求，單控制器節(jié)點的服務(wù)能力極有可能成為網(wǎng)絡(luò)性能的瓶頸，并且?guī)砜刂萍軜?gòu)難以拓展和單點攻擊等一系列問題[3]。因此實現(xiàn)一個邏輯上集中、物理上分布的控制器集群成為解決SDN控制架構(gòu)可拓展性的良好解決方案。

為了解決單控制器帶來的問題，業(yè)界提出了多控制器架構(gòu)，如HyperFlow[4]、 Onix[5]、 Ethane[6]、 Kandoo[7]等。多控制器架構(gòu)能夠有效提高SDN可擴展性，但同時也帶來了一系列問題，例如控制平面負(fù)載均衡問題?？刂破矫尕?fù)載均衡問題是SDN目前面臨的主要問題。近年來，研究發(fā)現(xiàn)交換機與控制器之間的映射關(guān)系是靜態(tài)的，不能動態(tài)適應(yīng)流量的變化，這一靜態(tài)關(guān)系會造成控制平面負(fù)載不均衡[8]。目前為解決交換機與控制器之間的靜態(tài)映射問題，學(xué)術(shù)界提出了動態(tài)多控制器架構(gòu)的概念。動態(tài)多控制器架構(gòu)通過實時監(jiān)控控制平面流量情況，調(diào)節(jié)控制平面負(fù)載，能夠有效解決控制平面負(fù)載不均衡問題。動態(tài)多控制器架構(gòu)主要從兩個方面均衡控制平面負(fù)載：1)遷移過載控制器下交換機至空閑控制器；2)增減控制器數(shù)量。

針對上述控制平面負(fù)載不均衡問題，Hock 等[9]提出了一種 Pareto 最優(yōu)的控制器布局方式(Pareto-based Optimal COntroller placement, POCO)。POCO 針對某個控制器失效時如何對多控制器重新布局這個問題，綜合考慮控制器性能、容錯能力和負(fù)載均衡并提出了當(dāng)控制器失效時對其管理的交換機進(jìn)行遷移的策略。ElastiCon[10]采用基于窗口的雙門限方法動態(tài)地遷移交換機實現(xiàn)控制器和交換機之間的動態(tài)配置,以達(dá)到均衡控制平面負(fù)載的目的，這種策略提高了控制器資源利用率。ElastiCon在負(fù)載決策窗口內(nèi)設(shè)置負(fù)載閾值，當(dāng)控制器負(fù)載超過上、下門限時，采取增加新控制器、刪除已有控制器或遷移交換機等動作。然而上述兩種方案都主張將交換機遷移至鄰近控制器，雖然減小了網(wǎng)絡(luò)時延，但是會造成控制器鄰近區(qū)域負(fù)載過大，不能有效均衡控制平面負(fù)載。Yao等[11]針對控制器放置問題提出CCPP(Capacitated Controller Placement Problem)算法，CCPP中提及當(dāng)某個控制器過載時，可以將交換機遷移至控制器容量使用率最低的控制器，這種策略稱作利用率最低遷移策略(Lowest Utilization Migration Algorithm，LUMA)。但是LUMA沒有考慮控制器和交換機之間的通信時延，導(dǎo)致網(wǎng)絡(luò)時延較大。陳飛宇等[12]提出的動態(tài)交換機遷移算法 (Dynamic Switch Migration Algorithm, DSMA)方案把交換機與控制器之間的映射關(guān)系建模成0- 1規(guī)劃問題，利用單目標(biāo)優(yōu)化免疫粒子群算法首先得到滿足控制平面負(fù)載均衡要求的一組解，然后考慮控制器與交換機之間的通信開銷，在這一組解中選出最合適的交換機控制器部署方案。DSMA能夠有效均衡控制平面負(fù)載，然而DSMA中單目標(biāo)優(yōu)化算法尋優(yōu)過程只考慮到負(fù)載均衡度，沒有考慮交換機遷移產(chǎn)生的通信開銷，尋優(yōu)方向過于單一。

基于上述控制平面負(fù)載均衡方案的不足，本文提出一種于多目標(biāo)優(yōu)化的動態(tài)交換機遷移算法(Dynamic Switch Migration Algorithm based on Multi-objective optimization, M-DSMA)。首先,通過問題建模在理論上對SDN控制平面負(fù)載均衡問題進(jìn)行分析，設(shè)計了滿足負(fù)載均衡度和交換機遷移所產(chǎn)生的通信開銷多重約束的目標(biāo)函數(shù)；其次,設(shè)計了一種多目標(biāo)遺傳算法對問題進(jìn)行處理。M-DSMA可以從負(fù)載均衡度和通信開銷兩個方向?qū)?yōu)，從而權(quán)衡負(fù)載均衡度和通信開銷。

1 問題建模

OpenFlow[13]中定義了交換機與多控制器相連的概念，多連接可以有效地避免控制器單點故障問題。OpenFlow將控制器分為三種:Equal控制器、Slave控制器和Master控制器。Equal控制器對交換機具有所有權(quán)限，不僅能夠接收交換機發(fā)來的異步消息(例如PACKET_IN、FLOW-REMOVED消息等)，還可以發(fā)送控制器-交換機消息以修改交換機的狀態(tài)。Slave控制器不接收任何交換機異步消息，但可以處理Slave控制器的角色請求消息。Master控制器與Equal控制器對交換機所具有的權(quán)限類似，但每個交換機只能有一個Master控制器，可以擁有多個Equal控制器或Slave控制器。由于Equal控制器、Slave控制器和Master控制器的不同特性，各交換機可以在不同的控制器間平滑無縫遷移。

本文討論的控制平面負(fù)載均衡問題通過優(yōu)化交換機與控制器映射關(guān)系并據(jù)此遷移交換機實現(xiàn)。控制平面負(fù)載均衡的理想狀態(tài)是所有的控制器節(jié)點都處于較低負(fù)載狀態(tài)，并且交換機遷移所產(chǎn)生的通信開銷較小。為了闡述優(yōu)化交換機與控制器映射關(guān)系的過程，引入以下幾個概念。

定義1 交換機與控制器之間的映射關(guān)系建模成0- 1矩陣F=(fij)M×N用于描述交換機與控制器之間的映射關(guān)系。

(1)

其中：M表示交換機個數(shù);N表示控制器個數(shù)；fij的值為1表示控制器Cj是交換機Si的Master控制器；fij的值為0表示控制器Cj是交換機Si的Equal控制器或Salve控制器。

定義2 負(fù)載均衡度。SDN控制器的負(fù)載主要由以下四個因素決定[14]：1)處理PACKET_IN事件；2)維護(hù)本控制器管理域的網(wǎng)絡(luò)視圖；3)與其他控制器的通信；4)安裝流表項。在不同的網(wǎng)絡(luò)環(huán)境中，處理PACKET_IN事件對負(fù)載影響最大，因此把到達(dá)控制器的PACKET_IN事件數(shù)目作為該控制器的負(fù)載值?？刂破髫?fù)載值的計算式如下：

(2)

其中：LCj表示控制器Cj的當(dāng)前負(fù)載；xi表示交換機Si發(fā)送到控制器Cj的PACKET_IN事件數(shù)目。

負(fù)載均衡度是為了衡量所有控制器的負(fù)載差異情況，因此本文利用標(biāo)準(zhǔn)差表示負(fù)載均衡度，如式(3)所示：

(3)

定義3 負(fù)載均衡代價的主要組成部分為交換機遷移產(chǎn)生的通信開銷，定義通信開銷為cost，即交換機與控制器的映射狀態(tài)從當(dāng)前映射狀態(tài)(用F=(fij)M×N表示)到新的狀態(tài)(用F1=(fij1)M×N表示)所產(chǎn)生的通信開銷。本文用控制器與交換機之間的最小距離表示通信開銷cost，如式(4)所示計算通信開銷:

(4)

其中：Hij表示待遷移交換機Si與過載控制器Cj的最短距離；Hij1表示待遷移交換機Si與目標(biāo)控制器Cj1的最短距離。交換機與控制器映射狀態(tài)從F=(fij)M×N到F1=(fij1)M×N，根據(jù)式(5)計算mi值，mi值為0表示交換機Si的狀態(tài)未發(fā)生改變；mi值為1表示交換機Si的狀態(tài)發(fā)生改變。

(5)

控制平面負(fù)載均衡問題有兩個目標(biāo)：第一個目標(biāo)是均衡控制平面負(fù)載；另一個目標(biāo)是從當(dāng)前映射狀態(tài)轉(zhuǎn)換到新的映射狀態(tài)只需要最小的通信開銷。理論上，控制平面負(fù)載均衡度和交換機遷移所產(chǎn)生的通信開銷是相互矛盾的兩個指標(biāo)，無法使這兩個衡量指標(biāo)同時達(dá)到最優(yōu)。然而，基于單目標(biāo)優(yōu)化的遷移算法尋優(yōu)方向單一，搜索空間較小，這就造成了優(yōu)化結(jié)果不理想。針對這個問題，本文設(shè)計了負(fù)載均衡度和交換機遷移所產(chǎn)生的通信開銷這兩個相互矛盾的目標(biāo)，使得搜索最優(yōu)解能力加強，可以取得較好的優(yōu)化結(jié)果。因此可以得出本文交換機部署的多目標(biāo)優(yōu)化模型如下：

(6)

s.t.LTj>LCj,?j

(7)

(8)

式(6)是模型的兩個目標(biāo)函數(shù)，即在交換機的動態(tài)遷移過程中兼顧控制平面負(fù)載均衡度和交換機遷移產(chǎn)生的通信開銷。約束條件(7)表示映射狀態(tài)轉(zhuǎn)換后控制器的負(fù)載不能超過其閾值LTj，即要保證遷移交換機之后不會造成其他控制器過載。約束條件(8)表示每個交換機只能有一個Master控制器。

2 算法M-DSMA描述

SDN控制平面的負(fù)載均衡問題是非確定多項式完全(Non-deterministicPolynomialComplete,NPC)問題，很難在多項式時間內(nèi)找到其最優(yōu)解[15]。遺傳算法通過模擬生物進(jìn)化機制在全局范圍內(nèi)搜索最優(yōu)解，是解決NP問題的常用技術(shù)之一。遺傳算法在不需要了解問題域的先驗知識的前提下，采用交叉、變異策略使得種群不斷靠近最優(yōu)解區(qū)域[15]。本文基于遺傳算法的這些優(yōu)點，提出了一種利用遺傳算法進(jìn)行多目標(biāo)優(yōu)化的SDN負(fù)載均衡算法。

針對交換機遷移過程中沒有考慮通信開銷的問題，設(shè)計了基于多目標(biāo)優(yōu)化的負(fù)載均衡算法M-DSMA。M-DSMA的設(shè)計主要由以下幾個方面構(gòu)成：對種群進(jìn)行編碼設(shè)計、初始化種群、個體評價以及基本的遺傳算子。本文提出的M-DSMA算法中多目標(biāo)進(jìn)化框架是基于多目標(biāo)遺傳算法NSGA-II(Non-dominatedSortingGeneticAlgorithm-II)[16]實現(xiàn)的，具體算法流程如圖1所示。

圖1 M-DSMA流程

2.1 編碼與初始化種群

在遺傳算法中首先要解決的是問題域的編碼問題，只有先將問題進(jìn)行抽象、編碼成為遺傳學(xué)中的個體，才能形成種群進(jìn)行選擇、交叉和變異等操作。由于本文要優(yōu)化的目標(biāo)是控制器與交換機之間的0- 1映射關(guān)系，所以將問題域中的0- 1矩陣轉(zhuǎn)化為遺傳學(xué)中的個體基因。為了準(zhǔn)確描述0- 1矩陣中表達(dá)的交換機與控制器之間的映射關(guān)系，本文利用組編碼方式將交換機和交換機的Master控制器結(jié)合在一起，即將0- 1矩陣F中每行的0和1共同組成一個基因。隨后將所有行組成的基因序列串在一起形成一個基因序列組，這個基因序列組構(gòu)成了遺傳個體，多個個體則組成了一個種群。遺傳算法基于這個群體迭代生成若干子代，在子代中尋找近似最優(yōu)解。本文中的初始化種群規(guī)模為n=100。

圖2給出了交換機與控制器之間映射關(guān)系編碼示例。在圖2中，OpenFlow網(wǎng)絡(luò)中有3個控制器和6個交換機，如圖所示交換機S1、S2、S3的Master控制器為C1，S4、S5的Master控制器為C2，S6的Master控制器為C3。用編碼100表示某個交換機的Master控制器為C1，同理用編碼010表示某個交換機的Master控制器為C2，從而可以得出如圖2所示的交換機與控制器映射關(guān)系可表示成長度為3*6位的0- 1序列。這個序列的第一個三位子序列表示交換機S1與控制器的映射關(guān)系，第二個三位子序列表示交換機S2與控制器的映射關(guān)系，所以圖2中個體可編碼為100100100010010001。這種編碼方式確保了每個交換機只能有一個Master控制器。

遺傳算法是對群體進(jìn)行的進(jìn)化操作，需要生成初始種群，初始種群的生成是隨機的。本文中設(shè)置初始種群規(guī)模n=100。

圖2 交換機與控制器之間映射關(guān)系編碼示例

Fig. 2Exampleofmappingrelationshipbetweenswitchandcontroller

2.2 操作算子

編碼完成之后，遺傳算法需要對初始種群迭代生成若干子代，在子代中尋找近似最優(yōu)解，達(dá)到進(jìn)化的目的。種群的進(jìn)化離不開個體的評價和基本的遺傳算法操作算子，遺傳算子主要包括選擇算子、交叉算子和變異算子[15]。

2.2.1 選擇運算

選擇運算是從子代中選擇較優(yōu)的個體作為新一代父體，繼續(xù)重復(fù)迭代過程。個體的優(yōu)勢是通過定義適應(yīng)度函數(shù)來衡量的，而適應(yīng)度函數(shù)是以個體的屬性(如：個體的負(fù)載均衡度和遷移交換機產(chǎn)生的通信開銷)為基礎(chǔ)的。

2.2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)的目的是衡量個體優(yōu)劣性，從而選擇較優(yōu)的個體作為遺傳的父代個體。本文借助NSGA-II算法定義適應(yīng)度函數(shù)，NSGA-II算法中對個體的評價主要有以下三個步驟：

1)快速非支配排序算子設(shè)計，多目標(biāo)優(yōu)化問題的設(shè)計關(guān)鍵在于求取Pareto最優(yōu)解集，NSGA-II算法中的快速非支配排序依據(jù)目標(biāo)函數(shù)對種群進(jìn)行分層。本文中根據(jù)每個個體(即一種交換機與控制器映射關(guān)系)的負(fù)載均衡度、通信開銷計算個體的等級，同一等級可能包含多個個體。

2)個體擁擠距離算子設(shè)計，為了在同一等級的個體中進(jìn)行選擇性排序，NSGA-II算法提出個體擁擠距離的概念。為了避免陷入局部搜索，個體擁擠距離的計算基于個體屬性的分布，個體屬性值分布密集則個體擁擠距離越?。环粗?，個體擁擠距離越大。個體之間擁擠距離越大，該個體越優(yōu)。

3)精英策略選擇算子設(shè)計，精英策略是指保留父代個體中的優(yōu)秀個體作為子代，防止獲得的Pareto最優(yōu)解丟失。

2.2.3 交叉運算

交叉算子是指在父本個體和母本個體的基因序列上隨機地選擇一個或者多個基因位點作為交叉點，然后交換這兩個個體上對應(yīng)的部分基因序列。交叉的發(fā)生具有一定的概率性，如果交叉發(fā)生的概率過大，那么遺傳算法能夠搜索到更多的解空間，但是搜索能力增強的同時帶來了更多性能上的不穩(wěn)定。相反，如果交叉發(fā)生的概率太小，遺傳算法搜索問題最優(yōu)解的速度將會放緩，甚至出現(xiàn)種群停滯不前無法進(jìn)化的情況[15]。一般的交叉概率設(shè)置在0.25到1.00之間[15]，本文設(shè)置交叉概率為0.8。本文采用單點交叉，交換個體A和個體B交叉點及其之后全部的基因序列，如圖3所示，交叉運算主要由以下2個步驟組成：

1)在父代個體上隨機選擇一個基因作為交叉點，個體A和個體B的交叉點位置相同，如圖3(a)中所示，個體A的基因為100001100010010001，交叉點基因為100；個體B的基因為100010010010001001，交叉點基因為010。

2)個體A、B上的交叉點基因分別為100和010，如圖3(b)所示，交換這兩個基因及其之后的所有基因。交叉運算之后得到個體A、B的基因分別為100001010010001001、100010100010010001。交叉結(jié)果表示個體A中交換機S3的Master控制器由C1變?yōu)镃2，交換機S5的Master控制器由C2變?yōu)镃3；個體B中交換機S3的Master控制器由C2變?yōu)镃1，交換機S5的Master控制器由C3變?yōu)镃2。

圖3 交叉實例示意圖

2.2.4 變異運算

在繁殖過程中，新產(chǎn)生的個體的基因會以一定的概率出錯，這一行為稱為變異，變異能夠增加新的信息以擴大搜索空間。變異操作也是按一定概率進(jìn)行的，較低的概率可防止群體中重要而單一的基因的丟失，而較高的概率會使得遺傳算法趨于純粹的隨機搜索[15]，本文根據(jù)經(jīng)驗值設(shè)定變異概率值為0.2。如圖4中所示，變異有以下2個步驟：

1)在個體上隨機選擇變異點。如圖4(a)所示，個體基因為100100010010100001，隨機選擇變異點，變異點基因為100，表示交換機S5的Master控制器為C1。

2)改變變異點基因。遵循一個交換機只能有一個Master的原則，變異點基因序列中必須僅有一個基因位為1。如圖4(b)所示，更改變異點基因為001，表示交換機S5的Master控制器為從C1變?yōu)镃3。變異運算之后得到個體基因為100100010010001001。

圖4 變異實例示意圖

3 仿真實驗及結(jié)果分析

在Mininet[17]上建立多控制器拓?fù)?，本文模擬了5個控制器與20個交換機的網(wǎng)絡(luò)。通過增加某些交換機發(fā)送PACKET_IN包的速率使得某些控制器過載，引起控制平面負(fù)載不均衡觸發(fā)M-DSMA算法。為了說明基于多目標(biāo)遺傳的M-DSMA算法能夠有效地權(quán)衡負(fù)載均衡度和遷移交換機產(chǎn)生的通信開銷，與基于單目標(biāo)優(yōu)化的負(fù)載均衡算法DSMA作對比實驗。圖5表示分別運行M-DSMA算法和DSMA算法、交換機遷移前后控制器負(fù)載值的變化情況。

圖5中虛線表示控制器負(fù)載閾值，可以看出遷移前有兩個控制器發(fā)生過載，分別使用DSMA和M-DSMA這兩種負(fù)載均衡方案后，控制平面負(fù)載都得到了有效均衡，所有控制器負(fù)載均低于控制器負(fù)載閾值。通過實驗數(shù)據(jù)可以計算得出遷移前后控制平面負(fù)載均衡度分別為：σ遷移前=1 692 packet/s，σDSMA=211.485 6 packet/s，σM-DSMA=57.693 7 packet/s。從計算結(jié)果中可知，多目標(biāo)優(yōu)化算法效果比單目標(biāo)優(yōu)化算法負(fù)載均衡效果好。

圖5 控制器負(fù)載分布

圖6～7分別表示單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化搜索最優(yōu)解的過程。單目標(biāo)優(yōu)化算法依據(jù)負(fù)載均衡度這個目標(biāo)搜索一組最優(yōu)解。

圖6 單目標(biāo)求解過程

圖7 多目標(biāo)求解過程

從圖6可以看出，隨著迭代次數(shù)的增加，種群中最優(yōu)的負(fù)載均衡度逐漸減小，說明單目標(biāo)優(yōu)化算法能夠?qū)崿F(xiàn)控制平面負(fù)載均衡。多目標(biāo)優(yōu)化算法依據(jù)負(fù)載均衡度和通信開銷這兩個相互矛盾的目標(biāo)搜索最優(yōu)解，可以找到較好的交換機控制器部署關(guān)系。從圖7可以看出，第1代種群、第50代種群、第100代種群的分布情況，隨著迭代次數(shù)的增加，Pareto前沿面趨向于原點，說明多目標(biāo)優(yōu)化算法能夠有效權(quán)衡負(fù)載均衡度和通信開銷，負(fù)載均衡度和通信開銷均可以取得較優(yōu)解。

M-DSMA兼顧負(fù)載均衡度和通信開銷，且這兩個指標(biāo)均優(yōu)于DSMA。如圖8～9所示，實驗中通過提高部分交換機發(fā)包速率來逐次提高負(fù)載均衡度，模擬多次不同的交換機與控制器重新布局，從而得出負(fù)載均衡度和通信開銷對比圖。圖8為負(fù)載均衡度對比，從圖8可以看出，M-DSMA能夠大幅度降低負(fù)載均衡度，更有效地均衡控制平面負(fù)載。圖9為通信開銷對比，從圖9可以看出，多次實驗中M-DSMA的通信開銷始終小于DSMA通信開銷，說明M-DSMA能夠在均衡控制平面負(fù)載的同時更加有效地兼顧通信開銷。根據(jù)每次實驗結(jié)果取平均值，計算得出：相比于算法DSMA，算法M-DSMA降低了30%～50%的通信開銷

圖8 負(fù)載均衡度對比

圖9 通信開銷對比

4 結(jié)語

本文針對交換機與控制器之間靜態(tài)映射關(guān)系導(dǎo)致的負(fù)載均衡問題，提出了基于多目標(biāo)優(yōu)化的負(fù)載均衡方案M-DSMA。M-DSMA以負(fù)載均衡度和遷移交換機產(chǎn)生的通信開銷為優(yōu)化目標(biāo)，采用遺傳算法找到交換機分布的近似最優(yōu)解。仿真實驗結(jié)果表明，與基于單目標(biāo)優(yōu)化的均衡算法DSMA相比，M-DSMA能夠有效均衡控制平面負(fù)載，同時降低遷移交換機產(chǎn)生的通信開銷。然而，本文只關(guān)注了在控制器資源能滿足交換機流請求下交換機如何遷移的情況，對于需要添加新控制器的情況，將在下一步的工作中繼續(xù)研究。

)

[1]MCKEOWNN,ANDERSONT,BALAKRISHNANH,etal.OpenFlow:enablinginnovationincampusnetworks[J].ACMSIGCOMMComputerCommunicationReview, 2008, 38(2): 69-74.

[2] 黃韜,劉江,魏亮,等.軟件定義網(wǎng)絡(luò)核心原理與應(yīng)用實踐[M].北京:人民郵電出版社,2014:4-5,9.(HUANGT,LIUJ,WEIL,etal.SoftwareDefineNetworkCorePrincipleandApplicationPractice[M].Beijing:Posts&TelecomPress, 2014: 4-5, 9.)

[3]TOOTOONCHIANA,GORBUNOVS,GANJALIY,etal.Oncontrollerperformanceinsoftware-definednetworks[C]//Hot-ICE’12:Proceedingsofthe2012 2ndUSENIXConferenceonHotTopicsinManagementofInternet,Cloud,andEnterpriseNetworksandServices.Berkeley,CA:USENIXAssociation, 2012: 10-10.

[4]TOOTOONCHIANA,GANJALIY.HyperFlow:adistributedcontrolplaneforOpenFlow[C]//INM/WREN’10:Proceedingsofthe2010InternetNetworkManagementConferenceonResearchonEnterpriseNetworking.Berkeley,CA:USENIXAssociation, 2010: 3-3.

[5]KOPONENT,CASADOM,GUDEN,etal.Onix:adistributedcontrolplatformforlarge-scaleproductionnetworks[C]//OSDI’10:Proceedingsofthe2010 9thUSENIXConferenceonOperatingSystemsDesignandImplementation.Berkeley,CA:USENIXAssociation, 2010: 351-364.

[6]CASADOM,FREEDMANMJ,PETTITJ,etal.Ethane:takingcontroloftheenterprise[J].ACMSIGCOMMComputerCommunicationReview, 2007, 37(4): 1-12.

[7]YEGANEHSH,GANJALIY.Kandoo:aframeworkforefficientandscalableoffloadingofcontrolapplications[C]//HotSDN’12:ProceedingsoftheFirstWorkshopOnHotTopicsInSoftwareDefinedNetworks.NewYork:ACM, 2012: 19-24.

[8]YAOG,BIJ,GUOLY,etal.Onthecascadingfailuresofmulti-controllersinsoftwaredefinednetworks[C]//Proceedingsofthe2013 21stIEEEInternationalConferenceonNetworkProtocols.Piscataway,NJ:IEEE, 2013: 1-2.

[9]HOCKD,GEBERTS,HARTMANNM,etal.POCO-frameworkforPareto-optimalresilientcontrollerplacementinSDN-basedcorenetworks[C]//Proceedingsofthe2014IEEENetworkOperationsandManagementSymposium.Piscataway,NJ:IEEE, 2014: 1-2.

[10]DIXITA,HAOF,MUKHERJEES,etal.TowardsanelasticdistributedSDNcontroller[C]//HotSDN’13:Proceedingsofthe2ndACMSIGCOMMWorkshoponHotTopicsinSoftwareDefinedNetworking.NewYork:ACM, 2013: 7-12.

[11]YAOG,BIJ,LIYL,etal.Onthecapacitatedcontrollerplacementprobleminsoftwaredefinednetworks[J].IEEECommunicationLetters, 2014, 18( 8): 1339-1342.

[12] 陳飛宇,汪斌強,孟飛,等.一種軟件定義網(wǎng)絡(luò)中交換機動態(tài)遷移算法[J].計算機應(yīng)用研究,2016,33(5):1446-1449.(CHENFY,WANGBQ,MENGF,etal.Dynamicswitchesmigrationalgorithminsoftwaredefinednetworks[J].ApplicationResearchofComputers, 2016, 33(5): 1446-1449.)

[13]RENTT,XUYW.AnalysisofthenewfeaturesofOpenFlow1.4 [C]//Proceedingsofthe2ndInternationalConferenceonInformation,ElectronicsandComputer.Amsterdam:AtlantisPress, 2014: 73-77.

[14] CHENG G, CHEN H, HU H, et al. Dynamic switch migration towards a scalable SDN control plane [J]. International Journal of Communication Systems, 2016, 29(9): 1482-1499.

[15] 鄧?yán)?，姚力，金?云計算中基于多目標(biāo)優(yōu)化的動態(tài)資源配置方法[J].計算機應(yīng)用,2016,36(9):2396-2401.(DENG L, YAO L, JIN Y. Dynamic resource allocation method based on multi-objective optimization in cloud computing [J]. Journal of Computer Applications, 2016, 36(9): 2396-2401.)

[16] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

[17] DE OLIVEIRA R L S, SHINODA A, SCHWEITZER C M, et al. Using Mininet for emulation and prototyping software defined networks [C]// Proceedings of the 2014 IEEE Colombian Conference on Communications and Computing. Piscataway, NJ: IEEE, 2014: 1-6.

This work is partially supported by the Natural Science Foundation of Anhui Province (1408085MF125).

LIU Biguo, born in 1992, M. S. candidate. Her research interests include software-defined network, load balancing.

SHU Yong’an, born in 1966, Ph. D., professor. His research interests include wireless network, next-generation network architecture.

FU Yinghui, born in 1991, M. S. candidate. His research interests include software-defined network, load balancing.

Load balancing scheme based on multi-objective optimization for software defined network

LIU Biguo*, SHU Yong’an, FU Yinghui

(SchoolofComputerScienceandTechnology,AnhuiUniversity,HefeiAnhui230601,China)

In order to solve the problem of load balancing in Software Defined Network (SDN) control plane, a Dynamic Switch Migration Algorithm based on Multi-objective optimization (M-DSMA) was proposed. Firstly, the mapping relationship between the switch and the controller was transformed into 0- 1 matrix optimization problem. Then, the two conflicting objective functions were simultaneously optimized and controlled by the multi-objective genetic algorithm based on Non-dominated Sorting Genetic Algorithm-II (NSGA-II), one was the plane load balancing degree and another one was the communication overhead generated by switch migration. In the process of multi-objective optimization, the individuals were selected by using the fitness function for crossover and mutation, and then a rapid non-dominated sorting method was used to elite strategy in population. The next generation population was generated and the whole population was continually evolved, thus the global optimal solution was searched. The simulation results show that, the proposed M-DSMA can effectively balance the control plane load, and reduce the communication overhead by 30% to 50% compared with Dynamic Switch Migration Algorithm (DSMA). The proposed algorithm has the significant advantages in improving the control plane scalability.

Software Defined Network (SDN); load balancing; multi-objective optimization; Genetic Algorithm (GA); switch migration

2016- 11- 09;

2016- 12- 22。 基金項目:安徽省自然科學(xué)基金資助項目(1408085MF125)。

劉必果(1992—)，女，安徽池州人，碩士研究生，主要研究方向：軟件定義網(wǎng)絡(luò)、負(fù)載均衡； 束永安(1966—)，男，安徽六安人，教授，博士，主要研究方向：無線網(wǎng)絡(luò)、下一代網(wǎng)絡(luò)體系結(jié)構(gòu)； 付應(yīng)輝(1991—)，男，安徽六安人，碩士研究生，主要研究方向：軟件定義網(wǎng)絡(luò)、負(fù)載均衡。

1001- 9081(2017)06- 1555- 05

10.11772/j.issn.1001- 9081.2017.06.1555

TP393;TP18

A