董宏成，鄭飛毅

（1.重慶郵電大學(xué)通信新技術(shù)應(yīng)用研究中心，重慶 400065；2.重慶信科設(shè)計(jì)有限公司，重慶400065)

基于OpenFlow的數(shù)據(jù)中心網(wǎng)絡(luò)負(fù)載均衡算法

董宏成1，2，鄭飛毅1

（1.重慶郵電大學(xué)通信新技術(shù)應(yīng)用研究中心，重慶 400065；2.重慶信科設(shè)計(jì)有限公司，重慶400065)

現(xiàn)代數(shù)據(jù)中心網(wǎng)絡(luò)（Date Center Network，DCN）經(jīng)常會(huì)使用多路徑（MultiPath，MP）拓?fù)浣Y(jié)構(gòu)，這樣可以避免兩節(jié)點(diǎn)間某條鏈路失效而導(dǎo)致的網(wǎng)絡(luò)擁塞問題，而且增加了網(wǎng)絡(luò)的帶寬和容錯(cuò)率。傳統(tǒng)的OSPF（Open Shortest Path First）路由算法會(huì)選擇單條最短路徑作為最終路徑，這樣可能會(huì)導(dǎo)致大部分?jǐn)?shù)據(jù)流集中在單一路徑上而出現(xiàn)網(wǎng)絡(luò)擁塞，而其他可用路徑處于閑置狀態(tài)，不能充分地利用DCN中的鏈路資源，基于 SDN（Software Defined Network）的集中化的調(diào)度方式能夠提高網(wǎng)絡(luò)利用效率。設(shè)計(jì)了一套基于OpenFlow協(xié)議的鏈路負(fù)載均衡模型，詳細(xì)闡述了它的總體框架和算法實(shí)現(xiàn)過程，并通過實(shí)驗(yàn)仿真驗(yàn)證了算法的可行性和有效性。

SDN；MP;數(shù)據(jù)中心；負(fù)載均衡

0　引言

近年來，數(shù)據(jù)中心呈現(xiàn)爆炸式的急速發(fā)展，大量公司開始建立自己的大型互聯(lián)網(wǎng)數(shù)據(jù)中心(Internet Data Center，IDC)。云計(jì)算技術(shù)的出現(xiàn)對數(shù)據(jù)中心網(wǎng)絡(luò)提出了新的挑戰(zhàn)，比如網(wǎng)絡(luò)安全、虛擬機(jī)遷移、多租戶管理、負(fù)載均衡等。傳統(tǒng)的數(shù)據(jù)中心采用專用的負(fù)載均衡設(shè)備實(shí)現(xiàn)網(wǎng)絡(luò)資源的有效利用，具有設(shè)備成本高昂和可擴(kuò)展性差等問題，而基于軟件定義網(wǎng)絡(luò)的集中化的調(diào)度方式能夠提高資源利用率，簡化網(wǎng)絡(luò)管理，降低運(yùn)維成本。

SDN[1]是一種將控制層和轉(zhuǎn)發(fā)層分離的新型網(wǎng)絡(luò)架構(gòu)，交換機(jī)只負(fù)責(zé)數(shù)據(jù)流的轉(zhuǎn)發(fā)，降低了網(wǎng)絡(luò)交換機(jī)的負(fù)載，控制層的功能全部由運(yùn)行于服務(wù)器上的控制器實(shí)現(xiàn)。控制器需要下發(fā)流表到交換機(jī)才能支持轉(zhuǎn)發(fā)層設(shè)備的有效運(yùn)行，而控制層與轉(zhuǎn)發(fā)層之間的通信需要遵守一定的規(guī)則，目前較普遍的是采用 OpenFlow[2]協(xié)議來實(shí)現(xiàn)信息交互。本文目的是在SDN網(wǎng)絡(luò)架構(gòu)下解決網(wǎng)絡(luò)流量高峰期鏈路的負(fù)載分布不均勻問題，設(shè)計(jì)了負(fù)載均衡機(jī)制的總體框架、實(shí)現(xiàn)流程圖以及具體實(shí)現(xiàn)。

1　數(shù)據(jù)中心網(wǎng)絡(luò)流量特征

國內(nèi)外學(xué)者對真實(shí)數(shù)據(jù)中心網(wǎng)絡(luò)流量特征進(jìn)行了深入的觀察研究。Mckeown研究表明數(shù)據(jù)中心網(wǎng)絡(luò)流量與傳統(tǒng)的局域網(wǎng)和廣域網(wǎng)流量有著極大的不同，內(nèi)部節(jié)點(diǎn)間的數(shù)據(jù)流量在數(shù)據(jù)中心網(wǎng)絡(luò)所有流量中占主導(dǎo)地位[3]。Greenberg指出數(shù)據(jù)中心80%的數(shù)據(jù)流量為數(shù)據(jù)中心內(nèi)部的流量，而且85%的數(shù)據(jù)流小于100 KB[4]。目前采用最多的是 Fattree[5]網(wǎng)絡(luò)拓?fù)洌梢詾閮蓛晒?jié)點(diǎn)之間的流量提供多條路徑，這樣從理論上能降低單一路徑的負(fù)載率過高的問題，而在實(shí)際應(yīng)用中還是會(huì)出現(xiàn)某條路徑上流量擁塞嚴(yán)重而其他可用路徑卻處于閑置狀態(tài)的問題。

數(shù)據(jù)中心網(wǎng)絡(luò)流量模型由大流和小流組成，每個(gè)數(shù)據(jù)流由許多數(shù)據(jù)包組成，這些數(shù)據(jù)包具有5個(gè)相同特征（源 IP地址、源端口號(hào)、目的 IP地址、目的端口號(hào)、協(xié)議類型）。而大流是造成部分鏈路擁塞的主要原因，所以負(fù)載均衡機(jī)制主要針對大流，在調(diào)度過程中盡量忽視小流來降低調(diào)度開銷。數(shù)據(jù)流的大小由其所含字節(jié)數(shù)決定，同時(shí)數(shù)據(jù)流越大，持續(xù)的時(shí)間越長，小流持續(xù)時(shí)間很短。本文將字節(jié)數(shù)大于100 KB的流界定為大流。

2　負(fù)載均衡實(shí)現(xiàn)的總體框架

控制器的負(fù)載均衡功能模塊如圖1所示，主要包括拓?fù)浒l(fā)現(xiàn)模塊、大流監(jiān)測模塊、流量收集模塊、路徑計(jì)算模塊、流表導(dǎo)入模塊。拓?fù)浒l(fā)現(xiàn)模塊幫助控制器掌握通過全局的拓?fù)湫畔?，包括主機(jī)的位置信息、交換機(jī)之間的連接等。大流監(jiān)測模塊在鏈路利用率最大路徑上找出并標(biāo)記大流。流量收集模塊周期性地收集OpenFlow交換機(jī)網(wǎng)絡(luò)的流量信息，為兩個(gè)節(jié)點(diǎn)之間的多條路徑選擇提供參考流量監(jiān)測模塊統(tǒng)計(jì)交換機(jī)接口的流量信息，用于分析計(jì)算各鏈路的鏈路利用率。路徑計(jì)算模塊為大流的重路由提供支持，是實(shí)現(xiàn)負(fù)載均衡功能的重要部件。流表導(dǎo)入模塊是通過控制器向 OpenFlow交換機(jī)發(fā)送Packet_out消息實(shí)現(xiàn)的，動(dòng)態(tài)地將大流的最終得出的重路由路徑添加到交換機(jī)流表，從而實(shí)現(xiàn) OpenFlow網(wǎng)絡(luò)的負(fù)載均衡功能。負(fù)載均衡算法的實(shí)現(xiàn)流程如圖2所示。

圖1　總體框架圖

3　各功能模塊的數(shù)學(xué)建模與實(shí)現(xiàn)

首先為負(fù)載均衡制定一個(gè)啟動(dòng)閾值，這里采用負(fù)載均衡參數(shù)：

其中l(wèi)oadi，j(t)代表在t時(shí)刻鏈路＜i，j＞上的已經(jīng)被占用的帶寬[6]，N是網(wǎng)絡(luò)中所有鏈路的數(shù)目。下面簡單描述各模塊的實(shí)現(xiàn)方式。

圖2　負(fù)載均衡算法流程圖

3.1拓?fù)浒l(fā)現(xiàn)模塊

拓?fù)浒l(fā)現(xiàn)模塊的功能是收集網(wǎng)絡(luò)的拓?fù)湫畔?，將其保存在拓?fù)鋱D表中，并對網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行管理?？刂破髋c交換機(jī)之間是在OpenFlow標(biāo)準(zhǔn)協(xié)議的基礎(chǔ)下進(jìn)行通信的，但是控制器并不能通過Open。Flow協(xié)議獲得網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，是通過 LLDP組件[7]發(fā)送 LLDP(Link Layer Discovery Protocol)數(shù)據(jù)包到 OpenFlow交換機(jī)，再收集并解析交換機(jī)反饋的LLDP數(shù)據(jù)包，從而實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)涓兄?/p>

3.2大流監(jiān)測模塊

由于本文所提出的負(fù)載均衡機(jī)制是針對大流的，所以必須有一種方法將大流和小流區(qū)分開來。文獻(xiàn)[8]對3種主流的大流監(jiān)測機(jī)制進(jìn)行了分析比較，包括采樣監(jiān)測、應(yīng)用監(jiān)測和統(tǒng)計(jì)監(jiān)測。文獻(xiàn)[9]中提出探測大流最有效的方式是在終端主機(jī)進(jìn)行，一方面占用的資源比例相對交換機(jī)要少，從而避免大流監(jiān)測占用過多的交換機(jī)端資源；另一方面流的狀態(tài)也取決于終端應(yīng)用程序生成數(shù)據(jù)包的快慢，而不是網(wǎng)絡(luò)的鏈路狀態(tài)，終端對應(yīng)用程序發(fā)包速率的可知性更強(qiáng)。監(jiān)測原理是通過觀測終端主機(jī)socket緩存區(qū)，當(dāng)緩存區(qū)內(nèi)具有相同特征的數(shù)據(jù)包大小超過 100 KB，它就會(huì)被標(biāo)記為大流，本文便采用對主機(jī)端的統(tǒng)計(jì)監(jiān)測方式來進(jìn)行大流監(jiān)測，主機(jī)端需要精確統(tǒng)計(jì)和維護(hù)數(shù)據(jù)流的速率和字節(jié)等信息，再將統(tǒng)計(jì)信息通過交換機(jī)發(fā)送到控制器，從而實(shí)現(xiàn)控制器的大流監(jiān)測功能。

3.3流量收集模塊

這個(gè)組件的目的是詢問每個(gè) OpenFlow交換機(jī)的流量信息，再將所有收到的反饋信息進(jìn)行聯(lián)合并最終存儲(chǔ)到控制器的存儲(chǔ)單元。這些收集到的數(shù)據(jù)被路徑計(jì)算模塊用來計(jì)算不同鏈路上的負(fù)載，因?yàn)榛跈?quán)重的多路徑路由的核心思想是將大流的數(shù)據(jù)包分配到負(fù)載較輕的鏈路上，因此需要確切知道路徑上所有可能的鏈路負(fù)載。這個(gè)單元模塊周期性地通過輪詢的方式收集每個(gè)OpenFlow交換機(jī)的流數(shù)量、流表以及端口數(shù)據(jù)，并作為一個(gè)快照對象進(jìn)行存儲(chǔ)。每個(gè)快照對象都會(huì)通過一串?dāng)?shù)字標(biāo)識(shí)，每個(gè)周期生成新的快照對象后數(shù)字標(biāo)識(shí)會(huì)自動(dòng)加1，存儲(chǔ)區(qū)只會(huì)保存最新的2個(gè)快照對象，其他的功能模塊都有獲得快照對象數(shù)據(jù)的權(quán)限。

3.4路徑計(jì)算模塊

初始狀態(tài)采用 Floyd[10]算法計(jì)算基于跳數(shù)的 Top-K最短路徑，然后需要對每條路徑的狀態(tài)進(jìn)行評估。本文主要對路徑的兩個(gè)方面指標(biāo)進(jìn)行評估，一個(gè)是路徑所包含鏈路的長度，這個(gè)體現(xiàn)在跳數(shù)（Hop Count）；另外一個(gè)指標(biāo)是路徑上的負(fù)載，這個(gè)體現(xiàn)在這條路徑所包含的交換機(jī)和鏈路上的流量。由于每條路徑上包含多個(gè)交換機(jī)以及多條鏈路，不能簡單地以總流量的平均數(shù)來表示這條路徑的負(fù)載，而應(yīng)該根據(jù)特定的交換機(jī)和鏈路來代表該路徑的負(fù)載情況。交換機(jī)的負(fù)載通過它所統(tǒng)計(jì)的PC (Packet Count)和 BC(Byte Count)來體現(xiàn)，鏈路的負(fù)載通過端口的轉(zhuǎn)發(fā)率（Forwarding Rate）來表示。這些數(shù)據(jù)可以通過控制器周期性地向OpenFlow交換機(jī)發(fā)送狀態(tài)請求消息得到。每條路徑的負(fù)載狀況可以表示為S=(H，P，B，F(xiàn))，其中 H表示跳數(shù)；P=Max(P1，P2，…，PH)，Pi表示該路徑的第i臺(tái)交換機(jī)所轉(zhuǎn)發(fā)的封包數(shù)量，共包含H臺(tái)交換機(jī)；B=Max(B1，B2，…，BH)，Bi表示該路徑的第 i臺(tái)交換機(jī)所轉(zhuǎn)發(fā)的字節(jié)數(shù)量。F=Max(F1，F(xiàn)2，…，F(xiàn)H)，F(xiàn)i表示該鏈路經(jīng)過的第i臺(tái)交換機(jī)出端口的轉(zhuǎn)發(fā)率。由于參數(shù)之間的差異比較大，需要先進(jìn)行如下變換[11]：

每一條路徑可以用矩陣 R=(rhrprbrf)表示,權(quán)重向量W=(0.35，0.20，0.20，0.25)，各個(gè)參數(shù)值根據(jù)經(jīng)驗(yàn)自己定義，這里路徑的長度取0.35顯示了其重要性。每個(gè)節(jié)點(diǎn)對之間的所有路徑可以通過一個(gè)矩陣表示為：

Qi表示路徑i最后的權(quán)值，根據(jù)權(quán)值可以確定數(shù)據(jù)流經(jīng)i節(jié)點(diǎn)傳輸?shù)絡(luò)節(jié)點(diǎn)的最佳路徑。路徑計(jì)算模塊偽代碼如下：

3.5流表導(dǎo)入模塊

中心控制器通過路徑計(jì)算模塊產(chǎn)生的結(jié)果生成轉(zhuǎn)發(fā)規(guī)則，然后封裝到 Packet_out消息中導(dǎo)入到支持OpenFlow的交換機(jī)，交換機(jī)流表添加該轉(zhuǎn)發(fā)規(guī)則并根據(jù)更新的流表項(xiàng)來指導(dǎo)流量轉(zhuǎn)發(fā)。由于網(wǎng)絡(luò)流量和拓?fù)浣Y(jié)構(gòu)都是不可預(yù)測的，交換機(jī)流表會(huì)伴隨負(fù)載均衡機(jī)制實(shí)時(shí)、動(dòng)態(tài)地更新，而且過期的流表項(xiàng)會(huì)根據(jù)交換機(jī)配置而刪除。

4　實(shí)驗(yàn)結(jié)果分析

本文采用 Mininet2.2.0[12]作為一個(gè)開發(fā)環(huán)境模擬數(shù)據(jù)中心網(wǎng)絡(luò)場景，搭建如圖3所示的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，在Ubuntu Kylin 14.04.3上運(yùn)行RYU控制器，結(jié)合 iperf工具來產(chǎn)生TCP(Transmission Control Protocol)數(shù)據(jù)流和UDP (User Datagram Protocol)數(shù)據(jù)流，并且能夠測量端到端的吞吐量，從而得出整個(gè)網(wǎng)絡(luò)的吞吐量。host1～4同時(shí)向host5～8發(fā)送數(shù)據(jù)流量，在 RYU[12]控制器中結(jié)合拓?fù)浒l(fā)現(xiàn)模塊、流量監(jiān)測模塊、路徑計(jì)算模塊和流表導(dǎo)入模塊來對負(fù)載均衡算法進(jìn)行驗(yàn)證。仿真實(shí)驗(yàn)通過h1～h16傳輸時(shí)延、總吞吐量和總體鏈路利用率這3個(gè)指標(biāo)來驗(yàn)證本文所提出的負(fù)載均衡算法的有效性。總體鏈路利用率通過下式得到：

其中，MAXLOAD代表每條物理鏈路最大帶寬，仿真實(shí)驗(yàn)的信息見表1。

圖3　網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

選擇h1和h16為網(wǎng)絡(luò)時(shí)延測量的觀測對象,實(shí)驗(yàn)結(jié)果如圖4所示，在實(shí)驗(yàn)進(jìn)行的前47 s數(shù)據(jù)包從 h1～h16延時(shí)很低，而且本文所提出的LB(Load balance)算法和基于最短路徑算法的時(shí)延曲線表現(xiàn)出了極高的相似度。這是因?yàn)閯傞_始時(shí)鏈路負(fù)載較輕，兩種算法都是采用h1-S1-S9-h16來傳輸流量，而LB算法由于需要監(jiān)測數(shù)據(jù)流量并且周期性地向控制器發(fā)送網(wǎng)絡(luò)狀態(tài)信息，這樣會(huì)產(chǎn)生部分開銷而導(dǎo)致延時(shí)略高于基于最短路徑算法；但是47 s之后LB算法下的時(shí)延明顯低于采用OSPF算法的時(shí)延，這是因?yàn)樘嗟牧髁考性谧疃搪窂?h1-S1-S9-h16，而其他可用路徑處于空閑狀態(tài)，負(fù)載不均衡度大于判決門限，就會(huì)觸發(fā)負(fù)載均衡機(jī)制，原路徑上的流量會(huì)轉(zhuǎn)移到其他可用路徑，鏈路利用率也得到了明顯提升，如圖5所示。網(wǎng)絡(luò)整體吞吐量的性能比較如圖6所示，當(dāng)負(fù)載低于550 Mb/s時(shí)，兩者的性能曲線非常相似，由于LB算法需要傳輸額外的鏈路狀態(tài)信息導(dǎo)致吞吐量會(huì)略高于 550 Mb/s；當(dāng)負(fù)載超過 550 Mb/s，基于最短路徑算法網(wǎng)絡(luò)出現(xiàn)擁塞，其他可用鏈路得不到有效利用，吞吐量的增長明顯放緩。而LB算法下的網(wǎng)絡(luò)吞吐量在550～700 Mb/s區(qū)間能一直保持快速增長。因此本文提出的LB算法相比傳統(tǒng)的OSPF算法能夠在負(fù)載不均衡情況下改善網(wǎng)絡(luò)性能。

表1　仿真結(jié)果

圖4　h1～h16延時(shí)對比圖

圖5　總體鏈路利用率對比圖

圖6　總吞吐量對比圖

5　結(jié)束語

本文設(shè)計(jì)了負(fù)載均衡功能實(shí)現(xiàn)的總體框架，主要包括拓?fù)浒l(fā)現(xiàn)模塊、流量監(jiān)測模塊、路徑計(jì)算模塊、流表導(dǎo)入模塊。設(shè)計(jì)了負(fù)載均衡功能的實(shí)現(xiàn)流程圖，對相關(guān)的數(shù)學(xué)模型進(jìn)行了詳細(xì)的分析設(shè)計(jì)，確定了以大流為目標(biāo)流的調(diào)度策略，并通過實(shí)驗(yàn)驗(yàn)證了該負(fù)載均衡算法相比傳統(tǒng)的OSPF算法能夠?qū)崿F(xiàn)更低的網(wǎng)絡(luò)延時(shí)和更高的總體鏈路利用率和吞吐量。

該算法的不足之處是沒有考慮到大流出現(xiàn)重復(fù)調(diào)度的情況，如果某個(gè)大流被多次選為目標(biāo)流調(diào)度，可能會(huì)使情況更糟糕，而且流的轉(zhuǎn)移開銷也會(huì)影響負(fù)載均衡的實(shí)現(xiàn)效率。降低大流在調(diào)度過程中的開銷具有重要的意義，上述兩點(diǎn)將是下一步需要重點(diǎn)關(guān)注的內(nèi)容。

[1]左青云，陳鳴，趙廣松.基于Open Flow的SDN技術(shù)研究[J].軟件學(xué)報(bào)，2013，24（5）：1078-1097.

[2]Open Networking Foundation.OpenFlow[EB/OL].(2016) [2016].https：//www.opennetworking.org/en/sdn-resources/ openflow.

[3]MCKEOWN N，ANDERSON T，BALAKRISHNAN H，et al. OpenFlow：Enabling innovation in campus networks[J]. SIGCOMM Computer Communication Review，2008，38(2)：69-74.

[4]GREENBERG A，HAMILTON J R，JAIN N，et al.VL2：A scalable and flexible data center network[C].Proceedings of the AC_MSIGCOMM 2009 Conference on Data Communication.Barcelona，Spain，2009：51-62.

[5]GREENBERG A，HAMILTON J，MALTZ D A，et al.The cost of a cloud：research problems in data center networks[C].In ACM SIGCOMM，2008：68-73.

[6]Long Hui.Research on the OpenFlow-based load-balancing routing in distributed networks[D].Shanghai：Shanghai Jiao Tong University，2013.

[7]張遠(yuǎn).基于OpenFlow的負(fù)載均衡研究[D].北京：北京工業(yè)大學(xué)，2014.

[8]李龍，付斌章.Nimble：一種適用于 OpenFlow網(wǎng)絡(luò)的快速流調(diào)度策略[J].計(jì)算機(jī)學(xué)報(bào)，2015，38（5）：1056-1068.

[9]CURTIS A R，KIM W.Mahout：low-overhead datacenter traffic management using end-host-based elephant detection[J]. IEEE INFOCOM，2011，2(3)：1629-1637.

[10]BACKHOUSE R C，EIJINDE J P H W，GASTEREN A.J. M.V.Calculating path algorithms[J].Science of Computer Programming，1994，22(1-2)：3-19.

[11]Li Jun，Chang Xiangqing，Ren Yongmao，et al.An effective path load balancing mechanism based on SDN[C].IEEE13th International Conference on Trust，Security and Privacy in Computing and Communications，2014.

[12]Mininet Team.Mininet：An instant virtual network on your laptop[EB/OL].(2016)[2016].http://www.mininet.org/.

A load balancing algorithm for date center network based on OpenFlow

Dong Hongcheng1，2，Zheng Feiyi1
(1.Research Center for Application of New Communication Technology，Chongqing University of Posts and Telecommunications，Chongqing 400065，China；2.Chongqing Information Technology Designing Co.，Ltd，Chongqing 400065，China)

Modern data center network(Date Center Network，DCN)often uses multiple paths(MultiPath，MP)topology to avoid a link failure between two nodes caused by network congestion,and increases bandwidth and fault tolerance rate of network.Traditional OSPF(Open Shortest Path First)routing algorithm selects the shortest path as the final single path,that may lead to most of the data stream centralized in a single path and course the congestion of network,but other available paths are idle and can not be fully utilized the DCN link resources.Centralized scheduling based on SDN can improve network efficiency.This paper designs the overall framework and the algorithm flowchart of load balancing mechanism based on OpenFlow protocol,and simulation experiments prove the feasibility and effectiveness of the algorithm.

SDN；MP；date center；load balance

TP393

A

10.16157/j.issn.0258-7998.2016.05.033

董宏成(1969-)，男，碩士生導(dǎo)師，高級工程師，主要研究方向：下一代網(wǎng)絡(luò)。

鄭飛毅(1990-)，男，碩士研究生，主要研究方向：軟件定義網(wǎng)絡(luò)。

中文引用格式：董宏成，鄭飛毅.基于OpenFlow的數(shù)據(jù)中心網(wǎng)絡(luò)負(fù)載均衡算法[J].電子技術(shù)應(yīng)用，2016，42(5)：120-123，127.

英文引用格式：Dong Hongcheng，Zheng Feiyi.A load balancing algorithm for date center network based on OpenFlow[J].Application of Electronic Technique，2016，42(5)：120-123，127.