基于粒子群優(yōu)化的SDN負(fù)載均衡研究

曹欲曉，徐金寶

（南京工程學(xué)院 計(jì)算機(jī)工程學(xué)院，南京　211167）

基于粒子群優(yōu)化的SDN負(fù)載均衡研究

曹欲曉，徐金寶

（南京工程學(xué)院 計(jì)算機(jī)工程學(xué)院，南京211167）

軟件定義網(wǎng)絡(luò)SDN的轉(zhuǎn)發(fā)平面和控制平面分離，當(dāng)有新的流進(jìn)入網(wǎng)絡(luò)時(shí)，交換機(jī)不能確定對(duì)該流的操作，需要封裝Packet_In消息發(fā)送給控制器，由控制器決定對(duì)該流所進(jìn)行的操作。基于SDN的這種特點(diǎn)，傳統(tǒng)網(wǎng)絡(luò)中的負(fù)載均衡算法已經(jīng)不再適用于SDN網(wǎng)絡(luò)。在分析SDN網(wǎng)絡(luò)流轉(zhuǎn)發(fā)機(jī)制的基礎(chǔ)上，建立SDN負(fù)載均衡的數(shù)學(xué)模型，應(yīng)用粒子群算法對(duì)負(fù)載均衡問題進(jìn)行優(yōu)化，并把優(yōu)化算法運(yùn)行于SDN的控制器中。在Mininet上的仿真實(shí)驗(yàn)表明，粒子群優(yōu)化的SDN負(fù)載均衡算法可以有效地均衡網(wǎng)絡(luò)負(fù)載，提高網(wǎng)絡(luò)性能。

軟件定義網(wǎng)絡(luò)；負(fù)載均衡；粒子群算法；流表

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

0　引言

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

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

1　軟件定義網(wǎng)絡(luò)

相較于目前以TCP/IP為基礎(chǔ)的Internet來說，SDN是一種全新的網(wǎng)絡(luò)架構(gòu)，而不是運(yùn)行于當(dāng)前網(wǎng)絡(luò)上的一種協(xié)議，也不是對(duì)當(dāng)前網(wǎng)絡(luò)的改良方案。SDN的核心思想是控制平面和轉(zhuǎn)發(fā)平面的分離［4］。SDN的架構(gòu)可以用圖1來說明。

圖1　SDN的架構(gòu)

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

SDN的控制層和數(shù)據(jù)層之間的接口稱為 “南向接口”，目前OpenFlow協(xié)議已經(jīng)成為事實(shí)上的南向接口標(biāo)準(zhǔn)。控制層通過OpenFlow協(xié)議向數(shù)據(jù)層下發(fā)轉(zhuǎn)發(fā)策略。應(yīng)用層和控制層之間的接口稱為“北向接口”，由于應(yīng)用層各種應(yīng)用變化較多，目前尚沒有形成統(tǒng)一且標(biāo)準(zhǔn)的北向接口，但主流的控制器都以REST API的方式對(duì)應(yīng)用層提供北向接口。

2　粒子群優(yōu)化的SDN負(fù)載均衡

2.1問題描述

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

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

2.2粒子群算法

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

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

式（1）中，w稱為慣性因子，用來平衡個(gè)體最優(yōu)和全局最優(yōu)，c1稱為個(gè)體學(xué)習(xí)因子，用來表示粒子對(duì)自身最優(yōu)位置的跟蹤，c2稱為全局學(xué)習(xí)因子，用來表示粒子對(duì)群體中最優(yōu)粒子的跟蹤，r1和r2是區(qū)間［0，1］上的隨機(jī)數(shù)，PB稱為粒子的個(gè)體最優(yōu)值，GB稱為粒子群的最優(yōu)值。

2.3粒子群優(yōu)化的SDN負(fù)載均衡

應(yīng)用粒子群算法求解優(yōu)化問題時(shí)，首先要確定粒子的編碼方案，其次要根據(jù)優(yōu)化目標(biāo)設(shè)計(jì)相應(yīng)的適應(yīng)值函數(shù)。本文以SDN網(wǎng)絡(luò)通信鏈路的數(shù)目作為粒子的維數(shù)，以鏈路的帶寬使用率作為粒子在每一維上的坐標(biāo)，帶寬使用率可以通過專用軟件監(jiān)控得到，帶寬使用率的數(shù)值范圍從0到100。假設(shè)SDN中共有K條鏈路，如果要使SDN網(wǎng)絡(luò)的負(fù)載達(dá)到最為均衡的狀態(tài)，則所有鏈路的帶寬使用率應(yīng)該最為接近，故可構(gòu)造適應(yīng)值函數(shù)如式（3）所示。

其中：

函數(shù)f1表示所有鏈路負(fù)載差值平方的和，f1的值越小則鏈路之間負(fù)載的差值越小，SDN網(wǎng)絡(luò)的負(fù)載均衡程度越好。f2表示所有鏈路的負(fù)載和整個(gè)網(wǎng)絡(luò)的平均負(fù)載差值平方的和，顯然f2的值越小，每條鏈路的負(fù)載越接近整個(gè)網(wǎng)絡(luò)的平均值，SDN的負(fù)載均衡程度越好。α和β分別是f1和f2的系數(shù)，表示f1或f2對(duì)適應(yīng)值的貢獻(xiàn)程度，α和β的值可調(diào)，但要滿足（α+β=1）的條件。

下面給出應(yīng)用粒子群算法優(yōu)化SDN負(fù)載均衡的步驟。

①設(shè)置算法初始參數(shù)：確定種群規(guī)模Q、慣性因子w、學(xué)習(xí)因子c1和c2值。

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

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

③利用式（3）-（5）計(jì)算每個(gè)粒子的適應(yīng)值，求出每個(gè)粒子的個(gè)體極值和整個(gè)種群的全局極值。

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

⑤求出最優(yōu)粒子的適應(yīng)值函數(shù)值和位置。

⑥重復(fù)步驟③-⑤，直至達(dá)到規(guī)定的迭代次數(shù)。

迭代結(jié)束后，處于最優(yōu)位置的粒子的位置矢量就是控制器對(duì)新流的均衡分配方案。

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

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

圖2　測(cè)試網(wǎng)絡(luò)拓?fù)?/p>

表1　三種負(fù)載均衡算法的性能比較

4　結(jié)語

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

［1］左青云，陳鳴，趙廣松，等.基于OpenFlow的SDN技術(shù)研究［J］.軟件學(xué)報(bào)，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-），男，碩士，講師，研究方向?yàn)橹悄芩惴ā④浖x網(wǎng)絡(luò)徐金寶（1970-），男，碩士，副教授，研究方向?yàn)閿?shù)據(jù)挖掘、智能算法

2016-07-21

2016-09-15