文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.2016.05.033
中文引用格式: 董宏成,,鄭飛毅. 基于OpenFlow的數(shù)據(jù)中心網(wǎng)絡(luò)負載均衡算法[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.
0 引言
近年來,,數(shù)據(jù)中心呈現(xiàn)爆炸式的急速發(fā)展,,大量公司開始建立自己的大型互聯(lián)網(wǎng)數(shù)據(jù)中心(Internet Data Center,IDC),。云計算技術(shù)的出現(xiàn)對數(shù)據(jù)中心網(wǎng)絡(luò)提出了新的挑戰(zhàn),,比如網(wǎng)絡(luò)安全、虛擬機遷移,、多租戶管理,、負載均衡等。傳統(tǒng)的數(shù)據(jù)中心采用專用的負載均衡設(shè)備實現(xiàn)網(wǎng)絡(luò)資源的有效利用,,具有設(shè)備成本高昂和可擴展性差等問題,,而基于軟件定義網(wǎng)絡(luò)的集中化的調(diào)度方式能夠提高資源利用率,,簡化網(wǎng)絡(luò)管理,降低運維成本,。
SDN[1]是一種將控制層和轉(zhuǎn)發(fā)層分離的新型網(wǎng)絡(luò)架構(gòu),,交換機只負責(zé)數(shù)據(jù)流的轉(zhuǎn)發(fā),降低了網(wǎng)絡(luò)交換機的負載,,控制層的功能全部由運行于服務(wù)器上的控制器實現(xiàn),。控制器需要下發(fā)流表到交換機才能支持轉(zhuǎn)發(fā)層設(shè)備的有效運行,,而控制層與轉(zhuǎn)發(fā)層之間的通信需要遵守一定的規(guī)則,,目前較普遍的是采用OpenFlow[2]協(xié)議來實現(xiàn)信息交互。本文目的是在SDN網(wǎng)絡(luò)架構(gòu)下解決網(wǎng)絡(luò)流量高峰期鏈路的負載分布不均勻問題,,設(shè)計了負載均衡機制的總體框架,、實現(xiàn)流程圖以及具體實現(xiàn)。
1 數(shù)據(jù)中心網(wǎng)絡(luò)流量特征
國內(nèi)外學(xué)者對真實數(shù)據(jù)中心網(wǎng)絡(luò)流量特征進行了深入的觀察研究,。Mckeown研究表明數(shù)據(jù)中心網(wǎng)絡(luò)流量與傳統(tǒng)的局域網(wǎng)和廣域網(wǎng)流量有著極大的不同,,內(nèi)部節(jié)點間的數(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ò)拓撲,它可以為兩兩節(jié)點之間的流量提供多條路徑,,這樣從理論上能降低單一路徑的負載率過高的問題,,而在實際應(yīng)用中還是會出現(xiàn)某條路徑上流量擁塞嚴重而其他可用路徑卻處于閑置狀態(tài)的問題。
數(shù)據(jù)中心網(wǎng)絡(luò)流量模型由大流和小流組成,,每個數(shù)據(jù)流由許多數(shù)據(jù)包組成,,這些數(shù)據(jù)包具有5個相同特征(源IP地址、源端口號,、目的IP地址,、目的端口號、協(xié)議類型),。而大流是造成部分鏈路擁塞的主要原因,,所以負載均衡機制主要針對大流,在調(diào)度過程中盡量忽視小流來降低調(diào)度開銷,。數(shù)據(jù)流的大小由其所含字節(jié)數(shù)決定,,同時數(shù)據(jù)流越大,持續(xù)的時間越長,,小流持續(xù)時間很短,。本文將字節(jié)數(shù)大于100 KB的流界定為大流。
2 負載均衡實現(xiàn)的總體框架
控制器的負載均衡功能模塊如圖1所示,,主要包括拓撲發(fā)現(xiàn)模塊,、大流監(jiān)測模塊,、流量收集模塊、路徑計算模塊,、流表導(dǎo)入模塊,。拓撲發(fā)現(xiàn)模塊幫助控制器掌握通過全局的拓撲信息,包括主機的位置信息,、交換機之間的連接等,。大流監(jiān)測模塊在鏈路利用率最大路徑上找出并標記大流。流量收集模塊周期性地收集OpenFlow交換機網(wǎng)絡(luò)的流量信息,,為兩個節(jié)點之間的多條路徑選擇提供參考流量監(jiān)測模塊統(tǒng)計交換機接口的流量信息,,用于分析計算各鏈路的鏈路利用率。路徑計算模塊為大流的重路由提供支持,,是實現(xiàn)負載均衡功能的重要部件,。流表導(dǎo)入模塊是通過控制器向OpenFlow交換機發(fā)送Packet_out消息實現(xiàn)的,動態(tài)地將大流的最終得出的重路由路徑添加到交換機流表,,從而實現(xiàn)OpenFlow網(wǎng)絡(luò)的負載均衡功能,。負載均衡算法的實現(xiàn)流程如圖2所示。
3 各功能模塊的數(shù)學(xué)建模與實現(xiàn)
首先為負載均衡制定一個啟動閾值,,這里采用負載均衡參數(shù):
其中l(wèi)oadi,,j(t)代表在t時刻鏈路<i,j>上的已經(jīng)被占用的帶寬[6],,N是網(wǎng)絡(luò)中所有鏈路的數(shù)目,。下面簡單描述各模塊的實現(xiàn)方式。
3.1 拓撲發(fā)現(xiàn)模塊
拓撲發(fā)現(xiàn)模塊的功能是收集網(wǎng)絡(luò)的拓撲信息,,將其保存在拓撲圖表中,,并對網(wǎng)絡(luò)的拓撲結(jié)構(gòu)進行管理,??刂破髋c交換機之間是在OpenFlow標準協(xié)議的基礎(chǔ)下進行通信的,但是控制器并不能通過Open,。Flow協(xié)議獲得網(wǎng)絡(luò)的拓撲結(jié)構(gòu),,是通過LLDP組件[7]發(fā)送LLDP(Link Layer Discovery Protocol)數(shù)據(jù)包到OpenFlow交換機,再收集并解析交換機反饋的LLDP數(shù)據(jù)包,,從而實現(xiàn)網(wǎng)絡(luò)拓撲感知,。
3.2 大流監(jiān)測模塊
由于本文所提出的負載均衡機制是針對大流的,所以必須有一種方法將大流和小流區(qū)分開來,。文獻[8]對3種主流的大流監(jiān)測機制進行了分析比較,,包括采樣監(jiān)測、應(yīng)用監(jiān)測和統(tǒng)計監(jiān)測,。文獻[9]中提出探測大流最有效的方式是在終端主機進行,,一方面占用的資源比例相對交換機要少,,從而避免大流監(jiān)測占用過多的交換機端資源;另一方面流的狀態(tài)也取決于終端應(yīng)用程序生成數(shù)據(jù)包的快慢,,而不是網(wǎng)絡(luò)的鏈路狀態(tài),,終端對應(yīng)用程序發(fā)包速率的可知性更強。監(jiān)測原理是通過觀測終端主機socket緩存區(qū),,當緩存區(qū)內(nèi)具有相同特征的數(shù)據(jù)包大小超過100 KB,,它就會被標記為大流,本文便采用對主機端的統(tǒng)計監(jiān)測方式來進行大流監(jiān)測,,主機端需要精確統(tǒng)計和維護數(shù)據(jù)流的速率和字節(jié)等信息,,再將統(tǒng)計信息通過交換機發(fā)送到控制器,從而實現(xiàn)控制器的大流監(jiān)測功能,。
3.3 流量收集模塊
這個組件的目的是詢問每個OpenFlow交換機的流量信息,,再將所有收到的反饋信息進行聯(lián)合并最終存儲到控制器的存儲單元。這些收集到的數(shù)據(jù)被路徑計算模塊用來計算不同鏈路上的負載,,因為基于權(quán)重的多路徑路由的核心思想是將大流的數(shù)據(jù)包分配到負載較輕的鏈路上,,因此需要確切知道路徑上所有可能的鏈路負載。這個單元模塊周期性地通過輪詢的方式收集每個OpenFlow交換機的流數(shù)量,、流表以及端口數(shù)據(jù),,并作為一個快照對象進行存儲。每個快照對象都會通過一串數(shù)字標識,,每個周期生成新的快照對象后數(shù)字標識會自動加1,,存儲區(qū)只會保存最新的2個快照對象,其他的功能模塊都有獲得快照對象數(shù)據(jù)的權(quán)限,。
3.4 路徑計算模塊
初始狀態(tài)采用Floyd[10]算法計算基于跳數(shù)的Top-K最短路徑,,然后需要對每條路徑的狀態(tài)進行評估。本文主要對路徑的兩個方面指標進行評估,,一個是路徑所包含鏈路的長度,,這個體現(xiàn)在跳數(shù)(Hop Count);另外一個指標是路徑上的負載,,這個體現(xiàn)在這條路徑所包含的交換機和鏈路上的流量,。由于每條路徑上包含多個交換機以及多條鏈路,不能簡單地以總流量的平均數(shù)來表示這條路徑的負載,,而應(yīng)該根據(jù)特定的交換機和鏈路來代表該路徑的負載情況,。交換機的負載通過它所統(tǒng)計的PC(Packet Count)和BC(Byte Count)來體現(xiàn),鏈路的負載通過端口的轉(zhuǎn)發(fā)率(Forwarding Rate)來表示,。這些數(shù)據(jù)可以通過控制器周期性地向OpenFlow交換機發(fā)送狀態(tài)請求消息得到,。每條路徑的負載狀況可以表示為S=(H,P,B,,F(xiàn)),,其中H表示跳數(shù);P=Max(P1,,P2,,…,PH),,Pi表示該路徑的第i臺交換機所轉(zhuǎn)發(fā)的封包數(shù)量,,共包含H臺交換機;B=Max(B1,,B2,,…,BH),,Bi表示該路徑的第i臺交換機所轉(zhuǎn)發(fā)的字節(jié)數(shù)量,。F=Max(F1,F(xiàn)2,,…,,F(xiàn)H),F(xiàn)i表示該鏈路經(jīng)過的第i臺交換機出端口的轉(zhuǎn)發(fā)率,。由于參數(shù)之間的差異比較大,,需要先進行如下變換[11]:
每一條路徑可以用矩陣R=(rh rp rb rf)表示,權(quán)重向量W=(0.35,0.20,,0.20,,0.25),各個參數(shù)值根據(jù)經(jīng)驗自己定義,,這里路徑的長度取0.35顯示了其重要性,。每個節(jié)點對之間的所有路徑可以通過一個矩陣表示為:
Qi表示路徑i最后的權(quán)值,根據(jù)權(quán)值可以確定數(shù)據(jù)流經(jīng)i節(jié)點傳輸?shù)絡(luò)節(jié)點的最佳路徑,。路徑計算模塊偽代碼如下:
Algorithm : Route Construction
(1)Connect the topology with the RYU controller
(2)Detect the topology and do the following activities:
(3)Calculate top K shortest paths between each pair of nodes using Top-K Shortest Path algorithm(TKSP is the extension of Open Shortest Path First).
(4)Evaluate the Top-K path with the proposed method.
(5)Sort the paths between each pair of nodes according to the evaluation and store the results to the controller.
(6)Reconstruct the path using step1-5 in case of a node/link failure.
3.5 流表導(dǎo)入模塊
中心控制器通過路徑計算模塊產(chǎn)生的結(jié)果生成轉(zhuǎn)發(fā)規(guī)則,,然后封裝到Packet_out消息中導(dǎo)入到支持OpenFlow的交換機,交換機流表添加該轉(zhuǎn)發(fā)規(guī)則并根據(jù)更新的流表項來指導(dǎo)流量轉(zhuǎn)發(fā),。由于網(wǎng)絡(luò)流量和拓撲結(jié)構(gòu)都是不可預(yù)測的,,交換機流表會伴隨負載均衡機制實時,、動態(tài)地更新,,而且過期的流表項會根據(jù)交換機配置而刪除。
4 實驗結(jié)果分析
本文采用Mininet2.2.0[12]作為一個開發(fā)環(huán)境模擬數(shù)據(jù)中心網(wǎng)絡(luò)場景,,搭建如圖3所示的網(wǎng)絡(luò)拓撲結(jié)構(gòu),,在Ubuntu Kylin 14.04.3上運行RYU控制器,結(jié)合iperf工具來產(chǎn)生TCP(Transmission Control Protocol)數(shù)據(jù)流和UDP(User Datagram Protocol)數(shù)據(jù)流,并且能夠測量端到端的吞吐量,,從而得出整個網(wǎng)絡(luò)的吞吐量,。host1~4同時向host5~8發(fā)送數(shù)據(jù)流量,在RYU[12]控制器中結(jié)合拓撲發(fā)現(xiàn)模塊,、流量監(jiān)測模塊,、路徑計算模塊和流表導(dǎo)入模塊來對負載均衡算法進行驗證。仿真實驗通過h1~h16傳輸時延,、總吞吐量和總體鏈路利用率這3個指標來驗證本文所提出的負載均衡算法的有效性,。總體鏈路利用率通過下式得到:
其中,,MAXLOAD代表每條物理鏈路最大帶寬,,仿真實驗的信息見表1。
選擇h1和h16為網(wǎng)絡(luò)時延測量的觀測對象,實驗結(jié)果如圖4所示,,在實驗進行的前47 s數(shù)據(jù)包從h1~h16延時很低,,而且本文所提出的LB(Load balance)算法和基于最短路徑算法的時延曲線表現(xiàn)出了極高的相似度。這是因為剛開始時鏈路負載較輕,,兩種算法都是采用h1-S1-S9-h16來傳輸流量,,而LB算法由于需要監(jiān)測數(shù)據(jù)流量并且周期性地向控制器發(fā)送網(wǎng)絡(luò)狀態(tài)信息,這樣會產(chǎn)生部分開銷而導(dǎo)致延時略高于基于最短路徑算法,;但是47 s之后LB算法下的時延明顯低于采用OSPF算法的時延,,這是因為太多的流量集中在最短路徑h1-S1-S9-h16,而其他可用路徑處于空閑狀態(tài),,負載不均衡度大于判決門限,,就會觸發(fā)負載均衡機制,原路徑上的流量會轉(zhuǎn)移到其他可用路徑,,鏈路利用率也得到了明顯提升,,如圖5所示。網(wǎng)絡(luò)整體吞吐量的性能比較如圖6所示,,當負載低于550 Mb/s時,,兩者的性能曲線非常相似,由于LB算法需要傳輸額外的鏈路狀態(tài)信息導(dǎo)致吞吐量會略高于550 Mb/s,;當負載超過550 Mb/s,,基于最短路徑算法網(wǎng)絡(luò)出現(xiàn)擁塞,其他可用鏈路得不到有效利用,,吞吐量的增長明顯放緩,。而LB算法下的網(wǎng)絡(luò)吞吐量在550~700 Mb/s區(qū)間能一直保持快速增長。因此本文提出的LB算法相比傳統(tǒng)的OSPF算法能夠在負載不均衡情況下改善網(wǎng)絡(luò)性能,。
5 結(jié)束語
本文設(shè)計了負載均衡功能實現(xiàn)的總體框架,,主要包括拓撲發(fā)現(xiàn)模塊、流量監(jiān)測模塊、路徑計算模塊,、流表導(dǎo)入模塊,。設(shè)計了負載均衡功能的實現(xiàn)流程圖,對相關(guān)的數(shù)學(xué)模型進行了詳細的分析設(shè)計,,確定了以大流為目標流的調(diào)度策略,,并通過實驗驗證了該負載均衡算法相比傳統(tǒng)的OSPF算法能夠?qū)崿F(xiàn)更低的網(wǎng)絡(luò)延時和更高的總體鏈路利用率和吞吐量。
該算法的不足之處是沒有考慮到大流出現(xiàn)重復(fù)調(diào)度的情況,,如果某個大流被多次選為目標流調(diào)度,,可能會使情況更糟糕,而且流的轉(zhuǎn)移開銷也會影響負載均衡的實現(xiàn)效率,。降低大流在調(diào)度過程中的開銷具有重要的意義,,上述兩點將是下一步需要重點關(guān)注的內(nèi)容。
參考文獻
[1] 左青云,,陳鳴,,趙廣松.基于Open Flow的SDN技術(shù)研究[J].軟件學(xué)報,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] 張遠.基于OpenFlow的負載均衡研究[D].北京:北京工業(yè)大學(xué),,2014.
[8] 李龍,付斌章.Nimble:一種適用于OpenFlow網(wǎng)絡(luò)的快速流調(diào)度策略[J].計算機學(xué)報,,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].IEEE 13th 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/.