基于改進的粒子群優化算法的SDN負載均衡研究

李瑞玲，易向陽

（廣西大學計算機與電子信息學院，南寧 530004）

0 引言

在面對復雜網絡流量和新興的網絡業務時，以TCP/IP為核心的傳統網絡框架表現得越來越難以維護和擴展，并且傳統的網絡框架無法為研究者提供特定環境下各種技術和新功能的相關支持，這些相關問題嚴重限制了互聯網的行業發展前景，也促使人們對新的網絡架構進行研究。因此，數據中心網絡應運而生，數據中心網絡是一個連接數十萬乃至百萬級的大規模服務器群，作為連接分布式存儲和計算的橋梁，數據中心的性能將直接影響云計算、大數據等業務的發展。因此，如何對流量進行有效的控制，保證網絡的利用率，實現有效的負載均衡，節約網絡的資源，成為數據中心網絡研究中需要解決的核心問題之一。

為了更好的解決數據網絡中負載均衡問題，同時也為了靈活方便的對其進行規劃以及對設備進行有效的管理，研究者提出了軟件定義網絡（Software Defined Network，SDN）這一概念[1]。SDN相較于傳統網絡的不同之處在于其運用了分層的思想，將數據層與控制層分隔開，從而實現了對網絡流量的靈活有效控制。在控制層面，涵蓋了有邏輯的中心化與可編程特點的控制器，通過控制器可控制了解全局網絡的信息，也方便了運營商和研究者對網絡的配置以及新協議的部署等；而在數據層面的交換機僅僅提供一些簡易的數據轉發功能，這樣就大大提升了對網絡匹配的數據包的處理速度，同時也解決了對龐大流量的需求問題。

針對傳統網絡存在的眾多弊端，SDN的出現為解決這些弊端提供了新的思路。例如，基于SDN技術的數據中心有很多優點[2]。首先，基于SDN網絡管理與控制相分隔的特點，運營商和研究者可以通過控制器掌握全局的網絡信息，隨時查看網絡的負載情況。其次，通過負載均衡算法優化網絡的鏈路負載情況，不僅提升了SDN網絡的性能，也極大地降低了運營的成本。最后，對于引進的新的網絡及應用，SDN只需在控制層面加入相應的策略算法，無需再對底層的硬件進行更換，不但節約設備成本，也解決了傳統網絡難維護和擴展差的問題。

另一方面，在數據中心需要處理龐大的網絡數據流量時，對鏈路的負載均衡提出了更為嚴格的要求，而基于SDN的負載均衡的相關技術在一定程度上為該問題提供解決思路。本文設計并改進了一種多商品流的粒子群優化（Particle Swarm Optimization,PSO）算法并用于求解負載均衡問題。針對求解過程中PSO算法在搜索后期易陷入局部最優的困境，本文在構建了基于路徑長度與鏈路利用率的大象流分布的算法目標函數的基礎上，提出了改進的粒子群優化（Improved Particle Swarm Optimization,IPSO）算法，該算法結合分治算法的思想，將整個粒子群體劃分成多個子群體，然后對這些子群體分別求得各自的全局最優解，最后再對所有的子群體的全局最優解進行加權平均，最終求得整個粒子群體全局的最優解。

本文首先介紹當前數據中心的廣泛使用，接著引出SDN環境下實現數據中心的負載均衡的研究情況；然后根據眾學者對負載均衡以及PSO算法不斷的研究改進和完善的基礎上，給出負載均衡優化的模型，并提出一種改進后的IPSO優化算法，基于該算法給出一種SDN負載均衡方案；最后對算法進行控制仿真驗證，并對全文作出總結。

1 相關研究工作

近年來，隨著對SDN技術不斷的研究，眾多學者嘗試著將SDN應用到數據中心中，利用SDN集中控制的這一優點來改善現有的流量管理方式，對鏈路產生的流量選用負載均衡算法來進行相關調度。目前，常見的流量調度負載均衡算法包括等價多路徑（Equal-Cost Multi-path Routing，ECMP）算法、Floodlight自帶的單路徑最優路徑算法、包輪詢算法以及粒子群優化負載均衡算法等。Gao等作者在文獻[3]中詳述了ECMP算法，該算法適合處理鏈路中的老鼠流問題，在處理大象流問題時，鏈路的流量容易分配不均從而會導致網絡的傳輸的性能下降。文獻[4]中針對大象流使用EC?MP算法進行測試，結果證明傳輸性能下降達50%；文獻[5]中提到了包輪詢算法，該算法可以確保每條路徑上的轉發包數基本相同，但是即使是文獻[6]中改進后的差額輪詢算法也無法避免數據包亂序到達從而產生的鏈路擁塞問題。

PSO算法[9]是受到鳥群覓食的行為啟發而發現的一種群體的智能優化的算法，是由James Kennedy和Russell Eberhart博士在1995年提出的。該算法從隨機解開始，多次迭代去找尋滿足條件的最優的解，再根據適應值來判斷找到的解的優劣。文獻[9]中給出了一種基于多商品流的PSO負載均衡算法，這種算法以其實現容易、精度高、收斂快等優點，很好地契合了求解多商品流的問題，從而能高效快速的找到符合鏈路的最優路徑，使得鏈路的負載趨于平衡。但是PSO算法也存在著一些問題，比如算法搜索后期的收斂性變差、尋優的精度變低以及容易陷入局部最優解等。為了改進算法，文獻[11]中提到了自適應的調整慣性因子的策略，這樣算法不但在前期就有較大的搜索能力，而且在搜索后期也能較為精確；文獻[12]中給出了一種帶收斂因子的PSO算法，與PSO算法相比較，經實驗測試表明，改進后的算法的收斂性更好；文獻[13]中提出了通過選用不同鄰域的拓撲來確保收斂PSO算法的性能，結果表明，改進后的算法較PSO算法的全局拓撲性能更好；文獻[14]中提到了一種動態鄰域的PSO優化算法，并且將這種優化算法運用到了求解多個目標優化的問題當中；文獻[15]將人工蜂群算法和PSO算法相結合，再通過基準函數的仿真，實驗證明了改進后的算法性能更佳。

基于上述分析，以及眾學者對PSO算法不斷的改進與完善的基礎上，針對PSO算法搜索后期易于陷入局部的最優的這一缺點，本文在文獻[9]的基礎上改進了PSO算法，并結合分治算法的思想，對粒子群體進行全局的最優處理，以便得到全局的最優解，最終解決鏈路的負載均衡問題。

2 改進的IPSO算法及負載均衡求解

2.1 多商品流及PSO算法描述

在SDN網絡當中，我們把流量分為兩種[7]，一種是長時間的穩定的流，稱之為大象流，另一種是短時間的不穩定的流，稱之為老鼠流。針對這兩種不同的流采用不同的負載均衡方案，由于老鼠流持續時間很短，對鏈路影響不是很大，因此針對這種流可以采用ECMP算法進行轉發，而本文的負載均衡方案主要是針對穩定的大象流。

多商品流問題是指在同一時間內通過尋找不同的路徑，將種類不同的商品從各源點分送到相應的目的節點，在符合相應約束性條件的前提下，使得產生的花費最少[8]。在文獻[8]中，Ghamisi等作者詳細介紹了多商品流問題，闡述了將多商品流方法應用到網絡流量調度問題上的可行性和優勢。根據描述，可以把商品流中的商品文本看成是穩定流中的帶寬請求，同時設定一些相應的約束條件，如設定網絡中可以傳輸的流的最大數量為K，轉換成商品流問題后，目標就成了在相應約束條件下，從整個網絡中尋找不同的滿足要求的路徑，將流量發送到相應的目的節點，同時確保網絡產生的開銷最小，提高網絡的鏈路利用率。本文中，結合商品流問題可以將數據中心的流量調度問題做如下的描述：

將網絡 G 描述為（V,E）的集合（即 G=（V,E）），其中V表示所有節點的集合，E表示所有邊的集合，設定e（i,j）為起點 i到終點 j的邊，用 bi,j表示邊 e（i,j）鏈路的帶寬。設定有K條流在G中傳輸，設定流k（1≤i≤K）需求的帶寬為dk，xijk表示 k個流在邊 e（i,j）上的流量，xk表示為流量的矢量，ck表示流k的單位流量中的傳送代價的矢量，這樣就可以將目標函數表示為：

即在符合（2）式鏈路的帶寬以及（3）式流量的請求的帶寬約束的條件下，讓整個網絡的傳送代價達到最少。

定義P為所有的路徑的集合，則pi表示為從源節點到目的節點的可行性的路徑上的第i條路徑，其中，每一條路徑都是有許多條鏈路e（i,j）構成的，采用線性函數可以將權值作如下定義：

其中a，b為常量，phl為 pi的長度，pul為 pi的利用率。

在將網絡中的大象流調度問題轉化為求解多商品流的問題時，要讓大象流盡可能地先選擇網絡帶寬剩余比較多的路徑，也要盡可能的去躲避開鏈路中利用率比較高的路徑，同時盡可能的躲避開與鏈路中其它的大象流發生碰撞。為滿足上述各條件，通過改變權值ck可以控制網絡的整個流量的分布情況。綜上所述，在給定的網絡G=（V,E）中，基于路徑的長度與鏈路的利用率的大象流分布的算法的目標函數可表示為:

這樣，（1）式中目標函數求解鏈路最小代價的問題就轉化為（5）式中目標函數求解網絡最低傳輸代價的問題了，即本文中所要解決的網絡負載均衡問題。在將網絡中大象流的調度問題轉化成多商品流的問題后，先求解多商品流的問題，再根據求解結果確定轉發的路徑，這樣不僅可以做到避免鏈路的擁塞，同時也提升了整個網絡的利用率。由（2）式（3）式可知，在求解的過程中需要滿足鏈路的帶寬以及流量請求的帶寬等約束條件，而PSO算法能夠很好地解決約束優化問題，該算法易于實現，并且具有高精度、快速收斂等優點，很好地契合了求解多商品流的問題，基于此，本文采用了PSO算法來求解多商品流的問題。

PSO算法中，所有的粒子都會有一個被目標函數所確定的適應值（Fitness Value），通過這個適應值來評價粒子的“好”與“壞”。應用PSO算法來解決約束性的優化問題時有兩個步驟較為重要，一個是對問題的解進行編碼，另一個就是要確定好適應值的函數。例如給定一個問題f（x）=x12+x22+x32，要對其進行求解，則在用PSO算法求解時可將粒子編碼為（x1，x2，x3），則f（x）就可表示為適應值的函數。基于此，可構造數據中心的大象流的調度問題的適應值函數如下所示。

每個粒子的相對位置對應了問題的一個解，并且每個粒子在不斷尋找自身的最優位置的同時也在尋找整個群體中最優粒子的一個位置。在整個的迭代過程中，為了改變自身的位置，使得自身離最優粒子的位置更近，粒子通過比較自身的兩個“極值”[9]的適應值的優劣來更新自身位置。一個是本身粒子所找到的最優的解，這個解稱之為個體極值，用pBest來表示；另一個極值是整個的群體目前能找到的最優的解，這個解稱之為全局極值，用gBest來表示。粒子的速度和位置具體的更新方式如下：

其中 t為迭代次數，v（t）表示粒子當前的速度，x（t）表示粒子當前的位置，c1、c2是學習因子，取值[0-2]的常數，w 是慣性加權因子，取值[0.1-0.9]的常數，rand（）是[0,1]隨機數。

2.2 改進的IPSO算法及應用

文獻[9]的基于多商品流的PSO優化算法能夠很好的求得問題最優解，然而這些解存在著易于陷入局部最優的問題。PSO算法在查找的過程當中，群體中的所有粒子通過比較pBest和gBest的適應值來更新當前的位置，而粒子總是會往適應值好的粒子位置區域聚攏，這樣就會出現粒子群體中的所有粒子都會往一個地方靠近，出現一種“聚攏”現象。隨著聚攏現象的出現，算法就難以保證所求的解是滿足條件的全局最優解。基于此，在PSO算法的基礎上，本文提出了一種改進的粒子群優化算法。該算法結合分治算法的基本思想，將粒子群劃分為m個子粒子群，并通過多次迭代的方式求得每個子粒子群的全局最優解，然后對這m個子粒子群的全局最優解進行均值求解，最后得到整個粒子群體的全局最優解。具體實現過程如下。

首先，將整個粒子群體劃分為m個子群體，為達到子群體的最優效果，先選取其中一個子群體j，再對這個子群體的個體極值pBestj作如下的改進：在子群體j中取個體i（該個體極值為pBestji）的前后選取兩個個體極值，分別記作 pBestji-1和pBestji+1

，根據下面的公式計算出i的個體極值，記作 pBest′ji。

其中t為迭代次數，i表示第i個粒子，j表示第j個子群體,且 j∈（1,m），α、β、χ是[0,1]的隨機數，滿足α+β+χ=1。

對 pBestj的改進如下：將上面所有得到的子群體個體極值進行統計 pBest′j1、pBest′j2、...、pBest′jn，用這n個子個體的加權平均值表示pBest′j。

其中t為迭代次數，i表示第i個粒子，αi是[0,1]的隨機的數，并且滿足條件

選用上述方法，得到m個子群體的全局最優解后，再對這m個解進行加權平均值，得到最后的全局最優解 pBest′。

IPSO算法的流程圖如圖1所示。

圖1 改進的IPSO算法流程圖

算法IPSO While t＜=100 //滿足迭代條件

2.3 算法性能分析

本文中改進后的IPSO算法，結合分治算法的思想，將粒子群體劃分為m個子粒子群體，通過多次迭代的方式求得每個子粒子群體的的全局的最優的解，再對這m個子粒子群體的全局最優解進行均值求解得到整個粒子群全局最優解。這一方法很好的解決了PSO算法搜索后期易于求得局部的最優的解的問題。PSO算法的時間復雜度和迭代次數t以及維度n存在著線性的關系，時間復雜度為O（t*n），而IPSO算法是在PSO算法的基礎上對整個群體進行劃分的，因此，它的時間復雜度為O（mlogn）。同時在后續的仿真的實驗中表明，該算法較PSO算法有更好的收斂效果，避免了PSO算法后期易于陷入局部的最優解的問題。

2.4 基于IPSO算法的SDN負載均衡方案

在SDN網絡中，數據流進到網絡中時，OpenFlow交換機開始解析該數據流，并與交換機中的流表開始進行匹配，匹配如果成功，開始執行流表里的相應操作（轉發或丟棄）；如果不成功，交換機先將該數據流封裝成消息，然后再傳給集成了改進的IPSO算法的控制器中，通過IPSO算法來計算得出從源節點到目的節點之間的最優的路徑，再通過流表下發的方式，告知交換機的數據流的轉發方式，最后交換機根據流表的表項中的動作來對這些數據流進行轉發，具體的實現過程方案如圖2所示。

3 仿真結果與分析

為了對IPSO算法進行有效性驗證，本文在Flood?light和Mininet的控制仿真環境下進行了實驗[10]，整個實驗是在Ubuntu14.04系統下進行的。在使用Mininet構建的拓撲網絡中，選用iPerf軟件來模擬了端到端的流量，iPerf軟件是一個網絡性能測試工具，能夠創建指定帶寬的數據流量，因此選用該軟件對網絡進行流量的灌輸，并設定鏈路的帶寬10Mb/s。算法中相關參數的描述和取值如表1所示。

表1 仿真實驗參數值

為了避免實驗過程中出現的偶然情況，我們對自定義的網絡針對不同的算法各做了六組實驗，同時選取不同的鏈路來查看它們鏈路負載情況，本文主要是根據鏈路的延時以及鏈路的丟包率兩方面來反應鏈路的情況，根據實驗數據結果，繪制了圖3和圖4所示的曲線圖。

圖3 三種算法的各鏈路延時

圖4 三種算法的各鏈路丟包率

從上圖3和圖4中，我們能夠很清楚地看出，無論是在鏈路延時還是鏈路丟包率的問題上，IPSO負載均衡算法相較于PSO算法和單路徑算法在性能上都有著明顯的提升，該算法較另外兩種算法能夠很好的保證網絡鏈路的利用率，從而達到鏈路負載的均衡效果。而且在圖中，我們能夠看出IPSO負載均衡算法的曲線圖走向相較于另外兩種算法更趨于平穩，曲線波動范圍較小，這說明IPSO算法在各組實驗中都趨于平衡，穩定性較好，即改進后算法的可靠性更好。

隨后，在基于Floodlight控制器的Dashboard網頁界面上查看整體的網絡的負載情況，圖5、圖6和圖7是根據查看到的網絡負載情況結果分別繪制出來的單路徑、PSO和IPSO算法的效果圖。

圖中包含了交換機、主機以及它們之間的鏈路連線，其中不同的鏈路連線表示不同的鏈路利用率，細實線表示鏈路的利用率為0-0.3，虛線表示鏈路的利用率為0.3-0.5，點線表示鏈路的利用率為0.5-0.7，點虛線表示鏈路的利用率為0.7-1。

從上圖中能夠很清晰的看到，單路徑最優選路算法出現了點虛線和點線的鏈路情況，說明這個時候鏈路利用率過高，出現了鏈路擁塞的情況；PSO算法雖然沒有出現點虛線的鏈路，但也存在虛線和點線的鏈路情況，說明這個時候鏈路還是會有一些擁塞的情況出現，但不是很嚴重；而IPSO算法基本上都是細實線的鏈路，說明在采用IPSO算法后，鏈路都趨于平衡，沒有出現鏈路擁塞的情況，同時也驗證了該算法能夠均衡網絡中的流量，很好保證了鏈路的利用率。

4 結語

SDN具有集中管控、便于性能優化等優點，很好的解決了數據中心的負載均衡問題，而PSO算法能夠很好的契合了多商品流問題，本文在眾多學者研究的基礎上，為更好的解決數據中心大象流負載均衡的問題，設計改進了一種基于多商品流的IPSO算法并用于求解負載均衡問題。該算法結合分治算法的思想，將粒子群體劃分成多個子群體，并通過多次迭代的方式求得每個子群體的全局最優解，然后對這些子群體的全局最優解進行加權平均，從而求得整個粒子群體全局的最優解。最后，本文構建了基于Floodlight和Mini?net環境下的SDN數據中心實驗平臺，對單路徑算法、PSO算法以及IPSO鏈算法的負載鏈路的均衡的策略進行了仿真實驗比較，實驗數據表明改進后的IPSO算法能夠很好地對大象流進行可靠的傳輸，整個鏈路基本上趨于平衡且沒有出現鏈路擁塞的狀態，極大地確保了鏈路的利用率。

圖5 單路徑鏈路負載展示圖

圖6 PSO鏈路負載展示圖

圖7 IPSO鏈路負載展示圖

[1]Wang Wen-Dong,Hu Yan-Nan.SDN:the ongoing Network Change[J].Journal of the technology,2013,19(1):39-43.

[2]Zhang Yuan.Based on OpenFlow Load Balancing Research[D].Beijing:Beijing University of Technology,2014.

[3]Gao Yan-Qing,Wang Hua.Research the Network Energy Model and Intelligent Algorithm Based on Multi-Commodity Flows[D].Shandong:Shandong University,2016.

[4]Al-Fares M,Radhakrishnan S,Raghavan B,et al.Hedera:Dynamic Flow Scheduling for Data Center Networks[C].Usenix Symposium on Networked Systems Design and Implementation,NSDI 2010,April 28-30,2010,San Jose,Ca,USA.DBLP,2010:281-296.

[5]M.Shreedhar,G.Varghese.Efficient Fair Queuing Using Deficit Round[C].SIGCOMM,1995:375-385.

[6]Liao Y.Adaptive Scheme on IEEE 802.11 PCF[J].Computer Science,2007,64(1):58-65.

[7]Mckeown N,Anderson T,Balakrishnan H,et al.OpenFlow:Enabling Innovation in Campus Networks[J].ACM Sigcomm Computer Communication Review,2008,38(2):69-74.

[8]Ghamisi P,Benediktsson J A.Feature Selection Based on Hybridization of Genetic Algorithm and Particle Swarm Optimization[J].IEEE Geoscience&Remote Sensing Letters,2014,12(2):309-313.

[9]Yu M,Rexford J,Freedman M J,et al.Scalable Flow-Based Networking with DIFANE[C].ACM SIGCOMM 2010 Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications,New Delhi,India,August 30-September.DBLP,2010:351-362.

[10]Kreutz D,Ramos F M V,Esteves Verissimo P,et al.Software-Defined Networking:A Comprehensive Survey[J].Proceedings of the IEEE,2014,103(1):10-13.

[11]Shi Y,Eberhart R C.Parameter Selection in Particle Swarm Optimization[M].Evolutionary Programming VII.Springer Berlin Heidelberg,1998:591-600.

[12]Premalatha K,Natarajan A M.Hybrid PSO and GA for Global Maximization[J].Icsrs Int.j.open Problems Compt.math,2009,2(4):597-608.

[13]Specification,OpenFlow Switch.Version 1.0.0(Wire Protocol 0x01)[S].2009.

[14]Kreutz D,Ramos F M V,Esteves Verissimo P,et al.Software-Defined Networking:A Comprehensive Survey[J].Proceedings of the IEEE,2014,103(1):10-13.

[15]Jo E,Pan D,Liu J,et al.A Simulation and Emulation Study of SDN-Based Multipath Routing for Fat-Tree Data Center Networks[C].Simulation Conference.IEEE,2015:3072-3083.

[16]Kirkpatrick K.Software-Defined Networking[J].Communications of the Acm,2013,56(9):16-19.

[17]Wang Wen-Dong,Hu Yan-Nan.SDN:the ongoing Network Change[J].Journal of the Technology,2013,19(1):39-43.