基于粒子群優化的SDN負載均衡研究

曹欲曉，徐金寶

（南京工程學院 計算機工程學院，南京　211167）

基于粒子群優化的SDN負載均衡研究

曹欲曉，徐金寶

（南京工程學院 計算機工程學院，南京211167）

軟件定義網絡SDN的轉發平面和控制平面分離，當有新的流進入網絡時，交換機不能確定對該流的操作，需要封裝Packet_In消息發送給控制器，由控制器決定對該流所進行的操作。基于SDN的這種特點，傳統網絡中的負載均衡算法已經不再適用于SDN網絡。在分析SDN網絡流轉發機制的基礎上，建立SDN負載均衡的數學模型，應用粒子群算法對負載均衡問題進行優化，并把優化算法運行于SDN的控制器中。在Mininet上的仿真實驗表明，粒子群優化的SDN負載均衡算法可以有效地均衡網絡負載，提高網絡性能。

軟件定義網絡；負載均衡；粒子群算法；流表

江蘇省自然科學基金青年基金（No.BK20150730）、南京工程學院校級科研基金（No.CKJC201506）

0　引言

自上世紀90年代開始，隨著技術的發展和應用的促進，因特網已經逐漸成為當今社會的基礎設施之一，在人類的生產生活中發揮著愈加重要的作用。特別是最近幾年，由于云計算、物聯網、大數據的逐步實用化，智能手機在全球的迅速普及，網絡的規模和網絡中的數據流量呈現爆炸式的增長［1］。傳統的基于TCP/IP的因特網架構，控制平面和轉發平面緊密耦合在一起，共存于網絡設備中，這種模式已經難以適應未來網絡的發展需求。具體原因體現在以下幾個方面：首先管理人員難以應用一種統一的自動的模式對網絡設備進行管理、配置和升級，只能對設備逐一進行手工管理，效率低且容易出錯，如果核心網絡中的設備配置出錯，將會造成大面積的網絡故障。其次網絡中存在多家廠商的設備，這些廠商為了維護自身的利益，盡可能把設備做地封閉化，用戶無法自行在設備中增加新協議，無法對設備的功能進行修改，因此也無法對網絡進行新的部署和升級。為了解決上述問題，便于對網絡進行靈活的規劃和對設備進行方便的管理，軟件定義網絡（Software Defined Network，SDN）［2］的概念最近幾年被提出來并且逐漸得到學術界和工業界的普遍重視。SDN的核心思想是控制平面和轉發平面分離，控制平面的決策功能集中于邏輯上集中的控制器中，數據平面的轉發功能則由交換機實現，交換機按照控制器下發的流表對流進行轉發，控制器和交換機通過一個標準的接口進行通信。

SDN的概念提出以后，已經在真實網絡中獲得了越來越多的應用。2012年4月，Google在其數據中心的骨干網絡中已經全面應用了OpenFlow［3］協議，建立了SDN領域著名的B4網絡。隨后，Facebook也在其數據中心應用了SDN的OpenFlow技術。隨著SDN的大量應用，許多新的問題也隨之出現，比如多租戶管理、交換機遷移、網絡安全、負載均衡等。傳統的基于IP的網絡負載均衡是通過負載均衡器實現的，負載均衡器可以專用硬件或軟件的形式出現，技術已經比較成熟。傳統網絡中的負載均衡算法主要有隨機算法、輪詢算法、加權輪詢算法、最少連接算法、最快響應時間算法等。但是在SDN網絡中，數據中心面對來自整個Internet的大量用戶訪問請求，由于交換機和控制器分離，因此交換機如何把服務請求均勻的分配到各個服務器上是一個全新的問題。本文在分析SDN網絡架構的基礎上，針對SDN負載均衡的特點，建立SDN負載均衡的數學模型，確定負載均衡的優化目標，最后在控制器中應用粒子群算法對SDN的負載分配進行了優化。最后在Mininet仿真環境下，應用Ryu控制器對算法進行了仿真模擬，結果表明本文提出的方法較傳統負載均衡算法的性能提高1倍以上，本文的方法是行之有效的。

1　軟件定義網絡

相較于目前以TCP/IP為基礎的Internet來說，SDN是一種全新的網絡架構，而不是運行于當前網絡上的一種協議，也不是對當前網絡的改良方案。SDN的核心思想是控制平面和轉發平面的分離［4］。SDN的架構可以用圖1來說明。

圖1　SDN的架構

由圖1可知，從上到下，SDN一共由三層組成：應用層、控制層和數據層。應用層是用戶編寫的應用軟件，可以通過開放的API和控制層進行信令的交互，從而實現對網絡的管理和研究。控制層是把原來的路由器、交換機、防火墻等傳統網絡設備中的網絡管理、路由規劃等管理功能抽取出來集中在一起而形成的一個控制軟件。控制層的核心是控制器。數據層由大量稱為交換機的網絡設備組成，SDN中的交換機不同于傳統網絡中的交換機，其不但具有第二層的交換功能，還具有第三層的路由等其它功能，能完成第2-4層的數據轉發任務，再者SDN交換機本身不具備數據轉發決策功能，只能根據控制器下發的流表工作。

SDN的控制層和數據層之間的接口稱為 “南向接口”，目前OpenFlow協議已經成為事實上的南向接口標準。控制層通過OpenFlow協議向數據層下發轉發策略。應用層和控制層之間的接口稱為“北向接口”，由于應用層各種應用變化較多，目前尚沒有形成統一且標準的北向接口，但主流的控制器都以REST API的方式對應用層提供北向接口。

2　粒子群優化的SDN負載均衡

2.1問題描述

相對于網絡技術的發展，服務器CPU的處理速度和內存訪問速度的增長要落后于網絡帶寬和網絡訪問量的增長，這就使得服務器的負載能力成為了網絡的瓶頸。另外關鍵的網絡應用也要求服務器必須隨時能提供可靠的服務，因此對于SDN來說，負載均衡是一個必須面對和解決的問題。所謂負載均衡就是按照某種策略盡可能地把來自外部的訪問平均分配到服務器集群中的每臺服務器上，使每臺服務器的負載均勻穩定且網絡中沒有擁塞。

在SDN網絡中，當有流進入網絡后，交換機對流進行解析并和流表進行匹配，如果匹配成功，則按照流表中的操作項對流執行相應的操作 （轉發或丟棄）；如果匹配失敗，交換機把流封裝成Packet-In消息送給控制器，由控制器決定流的去向并生成新的流表下發給交換機，交換機根據新的流表對流進行處理［5-6］。可見當有新流進入SDN網絡時，控制器需要根據服務器的負載情況、鏈路的占用率等多種因素決定流的轉發路徑，并在交換機沒有發送Packet-In消息期間，定時檢查整個網絡的運行狀況，并對轉發策略做出實時調整。

2.2粒子群算法

粒子群優化 （Particle Swarm Optimization，PSO）算法［7］由Eberhart和Kennedy提出，是一種受鳥群覓食行為啟發而發現的群體智能算法。粒子群算法中，每個粒子的位置對應問題的一個解，每個粒子既不斷飛向自身的最優位置又追尋整個群體中最優粒子的位置，在解空間中不斷飛行，通過多次迭代求得問題的最優解。

設群體規模為Q，粒子在D維空間中飛行，則每個粒子的速度和位置更新可用式（1）和式（2）表示：

式（1）中，w稱為慣性因子，用來平衡個體最優和全局最優，c1稱為個體學習因子，用來表示粒子對自身最優位置的跟蹤，c2稱為全局學習因子，用來表示粒子對群體中最優粒子的跟蹤，r1和r2是區間［0，1］上的隨機數，PB稱為粒子的個體最優值，GB稱為粒子群的最優值。

2.3粒子群優化的SDN負載均衡

應用粒子群算法求解優化問題時，首先要確定粒子的編碼方案，其次要根據優化目標設計相應的適應值函數。本文以SDN網絡通信鏈路的數目作為粒子的維數，以鏈路的帶寬使用率作為粒子在每一維上的坐標，帶寬使用率可以通過專用軟件監控得到，帶寬使用率的數值范圍從0到100。假設SDN中共有K條鏈路，如果要使SDN網絡的負載達到最為均衡的狀態，則所有鏈路的帶寬使用率應該最為接近，故可構造適應值函數如式（3）所示。

其中：

函數f1表示所有鏈路負載差值平方的和，f1的值越小則鏈路之間負載的差值越小，SDN網絡的負載均衡程度越好。f2表示所有鏈路的負載和整個網絡的平均負載差值平方的和，顯然f2的值越小，每條鏈路的負載越接近整個網絡的平均值，SDN的負載均衡程度越好。α和β分別是f1和f2的系數，表示f1或f2對適應值的貢獻程度，α和β的值可調，但要滿足（α+β=1）的條件。

下面給出應用粒子群算法優化SDN負載均衡的步驟。

①設置算法初始參數：確定種群規模Q、慣性因子w、學習因子c1和c2值。

②初始化每個粒子的位置和速度。位置矢量由式（6）給出，速度矢量由式（7）給出。

Loadj是第j條鏈路的帶寬使用率，rand（）是隨機函數，VMin是速度的最小值，VMax是速度的最大值。

③利用式（3）-（5）計算每個粒子的適應值，求出每個粒子的個體極值和整個種群的全局極值。

④由式（1）計算粒子的速度，由式（2）更新粒子的位置。

⑤求出最優粒子的適應值函數值和位置。

⑥重復步驟③-⑤，直至達到規定的迭代次數。

迭代結束后，處于最優位置的粒子的位置矢量就是控制器對新流的均衡分配方案。

3　仿真結果及分析

為了驗證本文提出的基于粒子群的SDN負載均衡算法的性能，利用Mininet［8］軟件進行了仿真測試。仿真環境為Ubuntu12.04操作系統，仿真軟件Mininet2.2.0，控制器是Ryu。首先應用Mininet生成圖2所示SDN網絡，再使用iperf軟件生成TCP流和UDP流模擬對網絡的訪問。在相同的網絡環境下，分別運行負載均衡的隨機算法、輪詢算法、本文提出的粒子群優化算法各100次，取其平均值作為測試的結果列于表1中。由表1可見，粒子群優化的SDN負載均衡算法無論在延時還是在丟包率上，性能都較隨機算法和輪詢算法有明顯提高。

圖2　測試網絡拓撲

表1　三種負載均衡算法的性能比較

4　結語

SDN網絡是一種全新的網絡架構，設計思想是把數據流的轉發動作和做出這種動作的邏輯決策分離，這樣人們就可以在控制器上進行新協議的部署以及網絡功能的優化，極大地增強了網絡的靈活性，是未來網絡發展的方向。由于SDN網絡和傳統網絡的運行機制不同，這就導致了SDN網絡的負載均衡也不同于傳統網絡。在SDN網絡中，當有新流進入網絡時，交換機的流表中尚沒有針對該流的流表項，因此需要控制器做出對該流的轉發決策，這時控制器根據實時反饋的鏈路負載情況，應用粒子群算法計算出負載均衡最佳的一條鏈路分配給新進入網絡的流。通過用Mininet軟件仿真證明，本文提出的粒子群優化的SDN負載均衡算法較傳統算法有著更好的表現，在真實網絡中是完全可行的。

［1］左青云，陳鳴，趙廣松，等.基于OpenFlow的SDN技術研究［J］.軟件學報，2013，24（5）：1078-1097.

［2］McKeown N.Software-Defined Networking.In：Proc.of the INFOCOM Key Note.2009.http：//infocom2009.ieee-infocom.org/technical-Program.htm

［3］Mckeown N，Anderson T，Balakrishnan H，Parulkar G，Peterson L，Rexford J，Shenker S，Turner J.OpenFlow：Enabling Innovation in Campus networks.ACM SIGCOMM Computer Communication Review，2008，38（2）：69？74.［doi：10.1145/1355734.1355746］

［4］Open Networking Foundation.SDN Architecture Overview，Version 1.0.2013.

［5］Software-Defined Networking Research Group（SDNRG）.2013.http：//irtf.org/sdnrg

［6］Tootoonchian A，Ganjali Y.HyperFlow：A Distributed Control Plane for OpenFlow.In：Proc.of the 2010 Internet Network Management Workshop/Workshop on Research on Enterprise Networking（INM/WREN）.San Jose：USENIX Association，2010.http：//dl.acm.org/citation.cfm？id=1863136

［7］Kennedy，J，Eberhart R C.A Discrete Binary Version of the Particle Swarm Slgorithm［C］.The 1997 Conference on System，Cybernetics and Informatics.Piscataway，NJ USA：IEEE Press，1997：4104-4109.

［8］Mininet Team.Mininet：An Instant Virtual Network on Your Laptop［EB/OL］.（2016）［2016］.http：//www.mininet.org/.

Software Defined Network；Load Balance；Particle Swarm Optimization Algorithm；Flow Table

Research on SDN Load Balance Based on Particle Swarm Optimization

CAO Yu-xiao，，XU Jin-bao
（School of Computer Engineering，Nanjing Institute of Technology，Nanjing 211167）

Software Defined Network’s（SDN）controller platform and data platform are separated，when new data flow comes to SDN，switch can't decide to how to deal with the flow，then Packet_In message is sent to controller and controller decides which action can be added to the new coming flow.Based on the feature of SDN，traditional load balance algorithm is not suitable to SDN.After the mechanism of flow transmutation of SDN is analyzed，the mathematic model of SDN load balance is built.Then particle swarm optimization algorithm is used to solve SDN load balance problem and the algorithm is built in SDN controller.The emulation on Mininet platform proves that PSO load balance algorithm can equal load of SDN and increase performance of network effectively.

1007-1423（2016）29-0018-04

10.3969/j.issn.1007-1423.2016.29.004

曹欲曉（1971-），男，碩士，講師，研究方向為智能算法、軟件定義網絡徐金寶（1970-），男，碩士，副教授，研究方向為數據挖掘、智能算法

2016-07-21

2016-09-15