基于SDN的數據傳輸路徑負載均衡策略研究*

蘇建姜 蘇 亮

(包頭職業技術學院 計算機與信息工程系，內蒙古 包頭 014030)

隨著大數據時代的到來，網絡建設規模變得更加復雜以及網絡用戶不斷增加，傳統網絡體系結構是以IP為核心的分層體系結構，其弊端逐漸明顯，網絡設備包含多種協議，相互通信處理數據的速率也不同，不利于網絡的管理，尤其在網絡中瀑布式流量，出現靈活度差，容易出現資源利用不均衡和網絡堵塞的問題。

近年來SDN網絡負載均衡的研究也越來越多，劉海客等提出基于一種OpenFlow網絡的動態負載均衡方法[1]；羅晨提出一種基于面向負載均衡的軟件定義網絡最優路徑算法研究[2]；許紅亮等提出一種基于自適應多路徑負載均衡算法。[3]上述網絡負載研究主要面向服務器，在網絡拓撲鏈路之間負載均衡差別。本文重點研究SDN網絡數據傳輸是鏈路之間負載均衡問題，提出一種基于SDN的數據傳輸路徑負載均衡策略研究，將每條鏈路帶寬空閑率作為蜂群進化型遺傳算法(BEGA)的變異因子，利用SDN控制器可以獲得全網拓撲結構來實現基于鏈路的負載均衡，主要從鏈路利用率、網絡吞吐量和網絡時延等方面來改善網絡性能，并通過實驗仿真驗證本方法的有效性和可行性。

1 SDN網絡架構

1.1 SDN架構

SDN(Software Defined Network)是一種邏輯集中控制的新網絡架構，其關鍵屬性包括：數據平面和控制平面分離；控制平面和數據平面之間有統一的開放接口OpenFlow。一般稱控制器開放的API為北向接口，而控制器與底層網絡之間的接口為南向接口。SDN網絡體系結構主要包括SDN網絡應用、北向接口、SDN控制器、南向接口和SDN數據平面五部分[4],如圖1所示。

圖1 SDN體系架構圖

1.2 負載均衡

服務器負載均衡是指直接在服務器和外部網絡之間安裝負載均衡設備，將處理后負載平均分配到多臺服務器上，最大程度增強服務器數據包的處理能力、提高數據傳輸效率、增強網絡穩定性和利用率。[5]服務器端負載均衡框架如圖2所示。

圖2 服務器負載均衡架構

鏈路層負載均衡策略是指通過合理調度網絡鏈路策略，如在鏈路層增加冗余鏈路來提高鏈路數據處理傳輸能力同時可應對單點故障，進而調節網絡拓撲中冗余鏈路帶寬資源，達到負載均衡效果，如圖3所示。

圖3 數據鏈路負載均衡架構

1.3 SDN與負載均衡技術

在傳統網絡中為實現負載均衡,需要使專門的軟件或硬件設備，存在擴展性較差和費用高等問題。相比于傳統網絡，基于SDN的網絡體系結構為解決網絡數據鏈路負載均衡提供新的解決方法且有三大優勢：SDN架構中的控制器通過OpenFlow協議收集全局資源信息；SDN架構中所有OpenFlow轉發設備抽象為一個整體，由控制器統一下發至交換機等轉發設備中實現集中化的邏輯控制；SDN架構中可用軟件方式制定負載均衡策略。

2 基于算法的負載均衡研究

2.1 改進蜂群算法

2.1.1 蜂群算法實現

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

2.1.2 蜜蜂進化機制抽象模型

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

(1)蜜蜂繁殖進化過程簡介

蜜蜂的繁殖方式為孤雌生殖。蜜蜂蜂群中有三個階層：蜂王、工蜂、雄蜂。蜂王一個，為雌蜂，領導蜂群，負責繁衍，蜂王在小蜂房中產的卵將來發育為工蜂，產在大蜂房的受精卵發育成蜂王；雄蜂，由蜂王產在中蜂房中的未受精的卵發育而來，任務是負責與蜂王交配，任務完成后生命就結束了；蜂王具體交配過程為：蜂王雄蜂出巢飛舞，最強壯雄蜂與蜂王交配，雄蜂死去，蜂王回巢，蜂王產卵孵化有且僅有一個蜂王。

(2)蜜蜂進化過程的抽象模型

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

圖4 蜂群繁殖進化抽象模型

2.1.3 BEGA算法

蜜蜂進化型遺傳算法(BEGA)吸取蜜蜂進化機制的優點，同時優化遺傳算法的進化結構，蜂王存在可提高遺傳算法全局收斂性能，隨機蜂群引入避免算法陷入最優解。

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

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

1994年，Srinivas等人提出了一種根據適應度值動態調整交叉概率和變異概率的自適應遺傳算法AGA(Adaptive Genetic Algorithm)，和能隨個體適應度自適應調整。此Pc和Pm按如下在公式(1)和(2)基礎上自適應調整。

(1)

(2)

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

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

(2)適應度尺度變換

在遺傳算法中用適應度值來衡量個體優劣的程度。本文用到的為適應度線性變換法，假設原適應度為函數f，變換后的適應度函數為f′，則線性變換可用式(3)表示：

f′=α*f+β

(3)

其中α,β為變換系數。

(3)算子設定

① 選擇算子

由于BEGA算法中蜂王的存在，其實質作用為“最優個體保留”策略，而我們通常認為為“最優個體保留”策略是導致GA算法“早熟”的原因之一，但從算法全局收斂性角度考慮，“最優個體保留”策略是必要的。在衛星艙布局優化實踐中發現，若GA群體規模越小，則“最優個體保留”策略對GA的影響越大(收斂速度快)；反之越小。適當控制GA種群的規模即可控制GA的早熟又保證算法具有全局收斂性。結合上述，選擇策略為錦標賽選擇算子，因為隨機錦標賽操作簡單，具有很強的通用性和魯棒性。

② 交叉算子

GA算法中常用到的交叉算子有單點交叉、兩點交叉、均勻交叉、多點交叉等，針對本文布局設計問題而言兩點交叉操作是比較合適的。兩點交叉的操作與單點交叉類似，只是隨機設置兩個交叉點。

考慮如下兩個11位變量的個體：

父個體1 01110011001 父個體2 10101100101

交叉點位置為2、6，則產生的個體為：

子個體1 01101111001 子個體2 10110000101

③ 變異算子

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

(4)

2.1.4 BEGA算法描述

基于BEGA算法SDN網絡負載均衡策略的步驟如下：

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

Step 2 計算種群A(0)中個體適應度，將最優個體(第0代蜂王)保存到Queen中。

Step 3 如果滿足停止準則，算法輸出結果并停止運行；否則，繼續。

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

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

Step 6 計算此代自適應變異概率，對B(t)執行變異操作，得到種群C(t)。

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

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

算法的代進化過程如圖5所示，蜜蜂進化型遺傳算法流程圖6。

圖5 蜜蜂進化型遺傳算法代進化圖

圖6 蜜蜂進化型遺傳算法流程圖

3 實驗證明

3.1 負載均衡仿真環境與方案

本文采用Mininet網絡仿真工具和Ryu控制器，在Linux操作系統搭建仿真平臺。Mininet仿真器用于模擬網絡拓撲，Ryu控制器實現負載均衡算法。

本文采用仿真測試網絡拓撲，K=4的Fat-tree拓撲作為數據中心網絡結構，包含20臺OpenFlow交換機，其中8個邊緣層交換機、8個匯聚層交換機和4個核心層交換機，16臺主機。該網絡中所有鏈路均為全雙工鏈路，鏈路帶寬設置為1Gbps，流量統計時間間隔為1秒，監控負載時間為5秒，參數r=0.6，兩點交叉、自適應交叉概率，高斯變異均值為0、標準差為5，自適應變異概率最大值0.1、最小值0.01，錦標賽選擇、聯賽規模為2，最大進化代數100、種群規模30進行賦值。網絡數據鏈路流量由iperf工具模擬產生，主機h1-h8向主機h9-h16發送數據流，拓撲如圖7所示。

圖7 網路拓撲圖

根據蜜蜂進化型遺傳算法計算出最優負載鏈路，在SDN中通過Ryu控制器把該鏈路的動作指令補充到鏈路相應Openflow流表項中，然后把流表項下發給對應SDN交換機。SDN交換機根據流表項指定動作選擇數據路徑完成報文數據的轉發。基于蜜蜂進化型遺傳算法SDN負載均衡的方案如圖8所示。

圖8 BEGA的SDN負載均衡方案

3.2 仿真結果

本文的目標是數據在網絡設備鏈路間傳輸時，可根據控制器指令選擇鏈路實現負載均衡，選取評價指標是網路的鏈路平均利用率和網絡吞吐量。

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

圖9 鏈路平均利用率對比圖

如圖10所示，BEGA算法和ECMP算法在0～500Mb/s發包速率之間，網絡吞吐量差距不大。隨著時間推移，當發包速率大于530Mb/s時，BEGA算法的網絡吞吐量逐漸增加到680Mb/s左右，而ECMP算法吞吐量無明顯變化，因此，根據鏈路的實時狀態進行選路的新算法能有效提高網絡性能。

圖10 網絡吞吐量對比圖

4 結語

為提高多路徑網絡拓撲負載均衡分配能力，本文提出一種基于SDN體系結構的蜜蜂進化型遺傳算法，Ryu控制器獲取網絡鏈路數據實時狀態和數據傳輸信息，針對負載均衡較高的路徑，重新選定數據傳輸路徑。本文選用胖樹網絡拓撲進行實驗結果表明，BEGA算法在鏈路平均利用率和網絡吞吐量等方面有一定提高。