基于SDN的數(shù)據(jù)傳輸路徑負(fù)載均衡策略研究*

蘇建姜 蘇 亮

(包頭職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)與信息工程系，內(nèi)蒙古 包頭 014030)

隨著大數(shù)據(jù)時(shí)代的到來(lái)，網(wǎng)絡(luò)建設(shè)規(guī)模變得更加復(fù)雜以及網(wǎng)絡(luò)用戶(hù)不斷增加，傳統(tǒng)網(wǎng)絡(luò)體系結(jié)構(gòu)是以IP為核心的分層體系結(jié)構(gòu)，其弊端逐漸明顯，網(wǎng)絡(luò)設(shè)備包含多種協(xié)議，相互通信處理數(shù)據(jù)的速率也不同，不利于網(wǎng)絡(luò)的管理，尤其在網(wǎng)絡(luò)中瀑布式流量，出現(xiàn)靈活度差，容易出現(xiàn)資源利用不均衡和網(wǎng)絡(luò)堵塞的問(wèn)題。

近年來(lái)SDN網(wǎng)絡(luò)負(fù)載均衡的研究也越來(lái)越多，劉?？偷忍岢龌谝环NOpenFlow網(wǎng)絡(luò)的動(dòng)態(tài)負(fù)載均衡方法[1]；羅晨提出一種基于面向負(fù)載均衡的軟件定義網(wǎng)絡(luò)最優(yōu)路徑算法研究[2]；許紅亮等提出一種基于自適應(yīng)多路徑負(fù)載均衡算法。[3]上述網(wǎng)絡(luò)負(fù)載研究主要面向服務(wù)器，在網(wǎng)絡(luò)拓?fù)滏溌分g負(fù)載均衡差別。本文重點(diǎn)研究SDN網(wǎng)絡(luò)數(shù)據(jù)傳輸是鏈路之間負(fù)載均衡問(wèn)題，提出一種基于SDN的數(shù)據(jù)傳輸路徑負(fù)載均衡策略研究，將每條鏈路帶寬空閑率作為蜂群進(jìn)化型遺傳算法(BEGA)的變異因子，利用SDN控制器可以獲得全網(wǎng)拓?fù)浣Y(jié)構(gòu)來(lái)實(shí)現(xiàn)基于鏈路的負(fù)載均衡，主要從鏈路利用率、網(wǎng)絡(luò)吞吐量和網(wǎng)絡(luò)時(shí)延等方面來(lái)改善網(wǎng)絡(luò)性能，并通過(guò)實(shí)驗(yàn)仿真驗(yàn)證本方法的有效性和可行性。

1 SDN網(wǎng)絡(luò)架構(gòu)

1.1 SDN架構(gòu)

SDN(Software Defined Network)是一種邏輯集中控制的新網(wǎng)絡(luò)架構(gòu)，其關(guān)鍵屬性包括：數(shù)據(jù)平面和控制平面分離；控制平面和數(shù)據(jù)平面之間有統(tǒng)一的開(kāi)放接口OpenFlow。一般稱(chēng)控制器開(kāi)放的API為北向接口，而控制器與底層網(wǎng)絡(luò)之間的接口為南向接口。SDN網(wǎng)絡(luò)體系結(jié)構(gòu)主要包括SDN網(wǎng)絡(luò)應(yīng)用、北向接口、SDN控制器、南向接口和SDN數(shù)據(jù)平面五部分[4],如圖1所示。

圖1 SDN體系架構(gòu)圖

1.2 負(fù)載均衡

服務(wù)器負(fù)載均衡是指直接在服務(wù)器和外部網(wǎng)絡(luò)之間安裝負(fù)載均衡設(shè)備，將處理后負(fù)載平均分配到多臺(tái)服務(wù)器上，最大程度增強(qiáng)服務(wù)器數(shù)據(jù)包的處理能力、提高數(shù)據(jù)傳輸效率、增強(qiáng)網(wǎng)絡(luò)穩(wěn)定性和利用率。[5]服務(wù)器端負(fù)載均衡框架如圖2所示。

圖2 服務(wù)器負(fù)載均衡架構(gòu)

鏈路層負(fù)載均衡策略是指通過(guò)合理調(diào)度網(wǎng)絡(luò)鏈路策略，如在鏈路層增加冗余鏈路來(lái)提高鏈路數(shù)據(jù)處理傳輸能力同時(shí)可應(yīng)對(duì)單點(diǎn)故障，進(jìn)而調(diào)節(jié)網(wǎng)絡(luò)拓?fù)渲腥哂噫溌穾捹Y源，達(dá)到負(fù)載均衡效果，如圖3所示。

圖3 數(shù)據(jù)鏈路負(fù)載均衡架構(gòu)

1.3 SDN與負(fù)載均衡技術(shù)

在傳統(tǒng)網(wǎng)絡(luò)中為實(shí)現(xiàn)負(fù)載均衡,需要使專(zhuān)門(mén)的軟件或硬件設(shè)備，存在擴(kuò)展性較差和費(fèi)用高等問(wèn)題。相比于傳統(tǒng)網(wǎng)絡(luò)，基于SDN的網(wǎng)絡(luò)體系結(jié)構(gòu)為解決網(wǎng)絡(luò)數(shù)據(jù)鏈路負(fù)載均衡提供新的解決方法且有三大優(yōu)勢(shì)：SDN架構(gòu)中的控制器通過(guò)OpenFlow協(xié)議收集全局資源信息；SDN架構(gòu)中所有OpenFlow轉(zhuǎn)發(fā)設(shè)備抽象為一個(gè)整體，由控制器統(tǒng)一下發(fā)至交換機(jī)等轉(zhuǎn)發(fā)設(shè)備中實(shí)現(xiàn)集中化的邏輯控制；SDN架構(gòu)中可用軟件方式制定負(fù)載均衡策略。

2 基于算法的負(fù)載均衡研究

2.1 改進(jìn)蜂群算法

2.1.1 蜂群算法實(shí)現(xiàn)

蜂群算法(Bee Colony Algorithm)是以仿生自然界中蜂群的自組織模型和群體智能行為的一種算法。Bitam等，Derelict和Marinali[6-8]根據(jù)蜂群的蜜蜂繁殖(reproductive)行為(或過(guò)程)與采蜜(foraging)行為啟發(fā)，蜂群算法主要分為蜂群進(jìn)化型算法(Bee evolutionary algorithm)與人工蜂群算法(Artificial Bee Colony Algorithm)。

2.1.2 蜜蜂進(jìn)化機(jī)制抽象模型

BCA影響蜂群進(jìn)化方向的重要因素是引入蜂群最優(yōu)個(gè)體和外來(lái)蜂群，基于此提出蜜蜂進(jìn)化型遺傳算法(BEGA)，以給定概率將算法中最優(yōu)個(gè)體(蜂王)與一般個(gè)體(雄蜂)進(jìn)行交叉操作，從而增強(qiáng)對(duì)蜂群最優(yōu)個(gè)體信息開(kāi)采能力，降低陷入局部最優(yōu)解概率[9]，BEGA實(shí)質(zhì)是對(duì)遺傳算法的一種改進(jìn)。

(1)蜜蜂繁殖進(jìn)化過(guò)程簡(jiǎn)介

蜜蜂的繁殖方式為孤雌生殖。蜜蜂蜂群中有三個(gè)階層：蜂王、工蜂、雄蜂。蜂王一個(gè)，為雌蜂，領(lǐng)導(dǎo)蜂群，負(fù)責(zé)繁衍，蜂王在小蜂房中產(chǎn)的卵將來(lái)發(fā)育為工蜂，產(chǎn)在大蜂房的受精卵發(fā)育成蜂王；雄蜂，由蜂王產(chǎn)在中蜂房中的未受精的卵發(fā)育而來(lái)，任務(wù)是負(fù)責(zé)與蜂王交配，任務(wù)完成后生命就結(jié)束了；蜂王具體交配過(guò)程為：蜂王雄蜂出巢飛舞，最強(qiáng)壯雄蜂與蜂王交配，雄蜂死去，蜂王回巢，蜂王產(chǎn)卵孵化有且僅有一個(gè)蜂王。

(2)蜜蜂進(jìn)化過(guò)程的抽象模型

在遺傳算法中引入蜜蜂繁殖進(jìn)化機(jī)制，包括最優(yōu)個(gè)體(蜂王)、一般個(gè)體(雄蜂)和隨機(jī)蜂群將提高遺傳算法性能，我們得到蜜蜂進(jìn)化機(jī)制在GA中的抽象模型，如圖4所示。

圖4 蜂群繁殖進(jìn)化抽象模型

2.1.3 BEGA算法

蜜蜂進(jìn)化型遺傳算法(BEGA)吸取蜜蜂進(jìn)化機(jī)制的優(yōu)點(diǎn)，同時(shí)優(yōu)化遺傳算法的進(jìn)化結(jié)構(gòu)，蜂王存在可提高遺傳算法全局收斂性能，隨機(jī)蜂群引入避免算法陷入最優(yōu)解。

(1)自適應(yīng)交叉率、變異率

基本遺傳算法SGA(Simple Genetic Algorithms)是基于自然選擇的生物進(jìn)化，模仿生物進(jìn)化過(guò)程的隨機(jī)方法，采納了自然進(jìn)化模型，其基本操作主要有選擇、交叉和變異。傳統(tǒng)的簡(jiǎn)單遺傳算法收斂速度慢很難得到全局最優(yōu)解，且在求解復(fù)雜多峰值優(yōu)化問(wèn)題容易陷入局部最優(yōu)解。GA算法中交叉率和變異率產(chǎn)生方法的選擇很大程度上會(huì)影響遺傳算法行為和性能[10]，若交叉率越大，產(chǎn)生新個(gè)體的速度就越快，且容易破壞高適應(yīng)值的個(gè)體結(jié)構(gòu)；但過(guò)小，搜索過(guò)程緩慢、收斂速度慢。若變異率過(guò)小，新個(gè)體不易產(chǎn)生；若越大，遺傳算法失去本來(lái)算法意義，淪為純粹的隨機(jī)搜索算法。

1994年，Srinivas等人提出了一種根據(jù)適應(yīng)度值動(dòng)態(tài)調(diào)整交叉概率和變異概率的自適應(yīng)遺傳算法AGA(Adaptive Genetic Algorithm)，和能隨個(gè)體適應(yīng)度自適應(yīng)調(diào)整。此Pc和Pm按如下在公式(1)和(2)基礎(chǔ)上自適應(yīng)調(diào)整。

(1)

(2)

式中：fmax為種群中最大適應(yīng)度；favg為每代種群中的平均適應(yīng)度；f′為將要交叉的兩個(gè)體的較大適應(yīng)度值；f為變異個(gè)體的適應(yīng)度值；Pc1=0.9，Pc2=0.6，Pm1=0.1，Pm2=0.01。

改進(jìn)后的基本遺傳算法除了具有基本遺傳算法的特點(diǎn)之外，還有以下新的特點(diǎn)：避免了算法早熟問(wèn)題，提升全局搜索能力；避免了鋸齒問(wèn)題，提升局部搜索能力；遺傳算子的進(jìn)化更具方向性，具有較強(qiáng)的收斂能力。

(2)適應(yīng)度尺度變換

在遺傳算法中用適應(yīng)度值來(lái)衡量個(gè)體優(yōu)劣的程度。本文用到的為適應(yīng)度線(xiàn)性變換法，假設(shè)原適應(yīng)度為函數(shù)f，變換后的適應(yīng)度函數(shù)為f′，則線(xiàn)性變換可用式(3)表示：

f′=α*f+β

(3)

其中α,β為變換系數(shù)。

(3)算子設(shè)定

① 選擇算子

由于BEGA算法中蜂王的存在，其實(shí)質(zhì)作用為“最優(yōu)個(gè)體保留”策略，而我們通常認(rèn)為為“最優(yōu)個(gè)體保留”策略是導(dǎo)致GA算法“早熟”的原因之一，但從算法全局收斂性角度考慮，“最優(yōu)個(gè)體保留”策略是必要的。在衛(wèi)星艙布局優(yōu)化實(shí)踐中發(fā)現(xiàn)，若GA群體規(guī)模越小，則“最優(yōu)個(gè)體保留”策略對(duì)GA的影響越大(收斂速度快)；反之越小。適當(dāng)控制GA種群的規(guī)模即可控制GA的早熟又保證算法具有全局收斂性。結(jié)合上述，選擇策略為錦標(biāo)賽選擇算子，因?yàn)殡S機(jī)錦標(biāo)賽操作簡(jiǎn)單，具有很強(qiáng)的通用性和魯棒性。

② 交叉算子

GA算法中常用到的交叉算子有單點(diǎn)交叉、兩點(diǎn)交叉、均勻交叉、多點(diǎn)交叉等，針對(duì)本文布局設(shè)計(jì)問(wèn)題而言?xún)牲c(diǎn)交叉操作是比較合適的。兩點(diǎn)交叉的操作與單點(diǎn)交叉類(lèi)似，只是隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)。

考慮如下兩個(gè)11位變量的個(gè)體：

父?jìng)€(gè)體1 01110011001 父?jìng)€(gè)體2 10101100101

交叉點(diǎn)位置為2、6，則產(chǎn)生的個(gè)體為：

子個(gè)體1 01101111001 子個(gè)體2 10110000101

③ 變異算子

在進(jìn)化過(guò)程中，變異算子作用大于選擇和交叉算子。進(jìn)化前期，種群中個(gè)體之間差異較大，進(jìn)化速度較快，此階段選擇和交叉操作的作用明顯；進(jìn)化后期，種群中個(gè)體差異越來(lái)越小，選擇和交叉操作的作用不明顯，變異操作的作用明顯，提高變異率可以增加種群的多樣性，降低算法陷入局部最優(yōu)解。本文采用高斯變異，高斯分布在原數(shù)值附近隨機(jī)產(chǎn)生數(shù)值，有利于提高布局優(yōu)化局部尋優(yōu)和全局搜索能力。具體變異方式如下：設(shè)個(gè)體的每個(gè)基因有均等的變異機(jī)會(huì)，若某位基因的變異幾率小于設(shè)定的變異概率，則按式(4)對(duì)該基因位進(jìn)行變異：

(4)

2.1.4 BEGA算法描述

基于BEGA算法SDN網(wǎng)絡(luò)負(fù)載均衡策略的步驟如下：

Step 1 隨機(jī)生成初始種群A(0)，t=0，分別對(duì)參數(shù)r、交叉概率和變異概率及最大進(jìn)化代數(shù)、種群規(guī)模進(jìn)行賦值。

Step 2 計(jì)算種群A(0)中個(gè)體適應(yīng)度，將最優(yōu)個(gè)體(第0代蜂王)保存到Queen中。

Step 3 如果滿(mǎn)足停止準(zhǔn)則，算法輸出結(jié)果并停止運(yùn)行；否則，繼續(xù)。

Step 4 利用選擇方式，A(t-1)中自適應(yīng)選出N*r/2個(gè)。隨機(jī)生成N(1-r)/2個(gè)。

Step 5 計(jì)算此代交叉概率，Queen分別與Step 4得到的N*r/2個(gè)個(gè)體進(jìn)行兩點(diǎn)交叉運(yùn)算，得到子代種群，記為B (t)。

Step 6 計(jì)算此代自適應(yīng)變異概率，對(duì)B(t)執(zhí)行變異操作，得到種群C(t)。

Step 7 計(jì)算種群C (t)中個(gè)體的適應(yīng)度，從父代中選出的Nr?0/2個(gè)個(gè)體執(zhí)行免疫檢測(cè)操作，將適應(yīng)度最大的個(gè)體記為Queen_New。

Step 8 如果f(Queen_New) >f(Queen)，Queen = Queen_New，C(t)即為第t代種群A(t)；否則，用Queen中的個(gè)體替代C(t)中的最差個(gè)體，得到種群A(t)。轉(zhuǎn)到Step3。

算法的代進(jìn)化過(guò)程如圖5所示，蜜蜂進(jìn)化型遺傳算法流程圖6。

圖5 蜜蜂進(jìn)化型遺傳算法代進(jìn)化圖

圖6 蜜蜂進(jìn)化型遺傳算法流程圖

3 實(shí)驗(yàn)證明

3.1 負(fù)載均衡仿真環(huán)境與方案

本文采用Mininet網(wǎng)絡(luò)仿真工具和Ryu控制器，在Linux操作系統(tǒng)搭建仿真平臺(tái)。Mininet仿真器用于模擬網(wǎng)絡(luò)拓?fù)?，Ryu控制器實(shí)現(xiàn)負(fù)載均衡算法。

本文采用仿真測(cè)試網(wǎng)絡(luò)拓?fù)?，K=4的Fat-tree拓?fù)渥鳛閿?shù)據(jù)中心網(wǎng)絡(luò)結(jié)構(gòu)，包含20臺(tái)OpenFlow交換機(jī)，其中8個(gè)邊緣層交換機(jī)、8個(gè)匯聚層交換機(jī)和4個(gè)核心層交換機(jī)，16臺(tái)主機(jī)。該網(wǎng)絡(luò)中所有鏈路均為全雙工鏈路，鏈路帶寬設(shè)置為1Gbps，流量統(tǒng)計(jì)時(shí)間間隔為1秒，監(jiān)控負(fù)載時(shí)間為5秒，參數(shù)r=0.6，兩點(diǎn)交叉、自適應(yīng)交叉概率，高斯變異均值為0、標(biāo)準(zhǔn)差為5，自適應(yīng)變異概率最大值0.1、最小值0.01，錦標(biāo)賽選擇、聯(lián)賽規(guī)模為2，最大進(jìn)化代數(shù)100、種群規(guī)模30進(jìn)行賦值。網(wǎng)絡(luò)數(shù)據(jù)鏈路流量由iperf工具模擬產(chǎn)生，主機(jī)h1-h8向主機(jī)h9-h16發(fā)送數(shù)據(jù)流，拓?fù)淙鐖D7所示。

圖7 網(wǎng)路拓?fù)鋱D

根據(jù)蜜蜂進(jìn)化型遺傳算法計(jì)算出最優(yōu)負(fù)載鏈路，在SDN中通過(guò)Ryu控制器把該鏈路的動(dòng)作指令補(bǔ)充到鏈路相應(yīng)Openflow流表項(xiàng)中，然后把流表項(xiàng)下發(fā)給對(duì)應(yīng)SDN交換機(jī)。SDN交換機(jī)根據(jù)流表項(xiàng)指定動(dòng)作選擇數(shù)據(jù)路徑完成報(bào)文數(shù)據(jù)的轉(zhuǎn)發(fā)。基于蜜蜂進(jìn)化型遺傳算法SDN負(fù)載均衡的方案如圖8所示。

圖8 BEGA的SDN負(fù)載均衡方案

3.2 仿真結(jié)果

本文的目標(biāo)是數(shù)據(jù)在網(wǎng)絡(luò)設(shè)備鏈路間傳輸時(shí)，可根據(jù)控制器指令選擇鏈路實(shí)現(xiàn)負(fù)載均衡，選取評(píng)價(jià)指標(biāo)是網(wǎng)路的鏈路平均利用率和網(wǎng)絡(luò)吞吐量。

如圖9所示，BEGA算法和ECMP算法的網(wǎng)絡(luò)鏈路平均利用率在仿真開(kāi)始階段0～10s差別較小。但隨著時(shí)間推移，本文算法依據(jù)鏈路實(shí)時(shí)信息進(jìn)行選路，而ECMP算法是隨機(jī)選路，二者在網(wǎng)絡(luò)中的各條鏈路的狀態(tài)不再一樣，因此在利用多路徑的鏈路資源方面，BEGA算法比ECMP算法更加有效，鏈路的平均利用率也高于ECMP算法。

圖9 鏈路平均利用率對(duì)比圖

如圖10所示，BEGA算法和ECMP算法在0～500Mb/s發(fā)包速率之間，網(wǎng)絡(luò)吞吐量差距不大。隨著時(shí)間推移，當(dāng)發(fā)包速率大于530Mb/s時(shí)，BEGA算法的網(wǎng)絡(luò)吞吐量逐漸增加到680Mb/s左右，而ECMP算法吞吐量無(wú)明顯變化，因此，根據(jù)鏈路的實(shí)時(shí)狀態(tài)進(jìn)行選路的新算法能有效提高網(wǎng)絡(luò)性能。

圖10 網(wǎng)絡(luò)吞吐量對(duì)比圖

4 結(jié)語(yǔ)

為提高多路徑網(wǎng)絡(luò)拓?fù)湄?fù)載均衡分配能力，本文提出一種基于SDN體系結(jié)構(gòu)的蜜蜂進(jìn)化型遺傳算法，Ryu控制器獲取網(wǎng)絡(luò)鏈路數(shù)據(jù)實(shí)時(shí)狀態(tài)和數(shù)據(jù)傳輸信息，針對(duì)負(fù)載均衡較高的路徑，重新選定數(shù)據(jù)傳輸路徑。本文選用胖樹(shù)網(wǎng)絡(luò)拓?fù)溥M(jìn)行實(shí)驗(yàn)結(jié)果表明，BEGA算法在鏈路平均利用率和網(wǎng)絡(luò)吞吐量等方面有一定提高。