董宏成1，2，鄭飛毅1
（1.重慶郵電大學通信新技術應用研究中心，重慶400065；2.重慶信科設計有限公司，重慶400065)
摘 要：現代數據中心網絡（Date Center Network，DCN）經常會使用多路徑（MultiPath，MP）拓撲結構，這樣可以避免兩節點間某條鏈路失效而導致的網絡擁塞問題，而且增加了網絡的帶寬和容錯率。傳統的OSPF（Open Shortest Path First）路由算法會選擇單條最短路徑作為最終路徑，這樣可能會導致大部分數據流集中在單一路徑上而出現網絡擁塞，而其他可用路徑處於閒置狀態，不能充分地利用DCN中的鏈路資源，基於SDN（Software Defined Network）的集中化的調度方式能夠提高網絡利用效率。設計了一套基於OpenFlow協議的鏈路負載均衡模型，詳細闡述了它的總體框架和算法實現過程，並通過實驗仿真驗證了算法的可行性和有效性。
中圖分類號：TP393
文獻標識碼：A
DOI：10.16157/j.issn.0258-7998.2016.05.033
中文引用格式：董宏成，鄭飛毅. 基於OpenFlow的數據中心網絡負載均衡算法[J].電子技術應用，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 引言
近年來，數據中心呈現爆炸式的急速發展，大量公司開始建立自己的大型網際網路數據中心(Internet Data Center，IDC)。雲計算技術的出現對數據中心網絡提出了新的挑戰，比如網絡安全、虛擬機遷移、多租戶管理、負載均衡等。傳統的數據中心採用專用的負載均衡設備實現網絡資源的有效利用，具有設備成本高昂和可擴展性差等問題，而基於軟體定義網絡的集中化的調度方式能夠提高資源利用率，簡化網絡管理，降低運維成本。
ADVERTISEMENT
SDN[1]是一種將控制層和轉發層分離的新型網絡架構，交換機只負責數據流的轉發，降低了網絡交換機的負載，控制層的功能全部由運行於伺服器上的控制器實現。控制器需要下發流表到交換機才能支持轉發層設備的有效運行，而控制層與轉發層之間的通信需要遵守一定的規則，目前較普遍的是採用OpenFlow[2]協議來實現信息交互。本文目的是在SDN網絡架構下解決網絡流量高峰期鏈路的負載分布不均勻問題，設計了負載均衡機制的總體框架、實現流程圖以及具體實現。
1 數據中心網絡流量特徵
國內外學者對真實數據中心網絡流量特徵進行了深入的觀察研究。Mckeown研究表明數據中心網絡流量與傳統的區域網和廣域網流量有著極大的不同，內部節點間的數據流量在數據中心網絡所有流量中占主導地位[3]。Greenberg指出數據中心80%的數據流量為數據中心內部的流量，而且85%的數據流小於100 KB[4]。目前採用最多的是Fattree[5]網絡拓撲，它可以為兩兩節點之間的流量提供多條路徑，這樣從理論上能降低單一路徑的負載率過高的問題，而在實際應用中還是會出現某條路徑上流量擁塞嚴重而其他可用路徑卻處於閒置狀態的問題。
ADVERTISEMENT
數據中心網絡流量模型由大流和小流組成，每個數據流由許多數據包組成，這些數據包具有5個相同特徵（源IP位址、源埠號、目的IP位址、目的埠號、協議類型）。而大流是造成部分鏈路擁塞的主要原因，所以負載均衡機制主要針對大流，在調度過程中儘量忽視小流來降低調度開銷。數據流的大小由其所含字節數決定，同時數據流越大，持續的時間越長，小流持續時間很短。本文將字節數大於100 KB的流界定為大流。
2 負載均衡實現的總體框架
控制器的負載均衡功能模塊如圖1所示，主要包括拓撲發現模塊、大流監測模塊、流量收集模塊、路徑計算模塊、流表導入模塊。拓撲發現模塊幫助控制器掌握通過全局的拓撲信息，包括主機的位置信息、交換機之間的連接等。大流監測模塊在鏈路利用率最大路徑上找出並標記大流。流量收集模塊周期性地收集OpenFlow交換機網絡的流量信息，為兩個節點之間的多條路徑選擇提供參考流量監測模塊統計交換機接口的流量信息，用於分析計算各鏈路的鏈路利用率。路徑計算模塊為大流的重路由提供支持，是實現負載均衡功能的重要部件。流表導入模塊是通過控制器向OpenFlow交換機發送Packet_out消息實現的，動態地將大流的最終得出的重路由路徑添加到交換機流表，從而實現OpenFlow網絡的負載均衡功能。負載均衡算法的實現流程如圖2所示。
ADVERTISEMENT
3 各功能模塊的數學建模與實現
首先為負載均衡制定一個啟動閾值，這裡採用負載均衡參數：
其中loadi，j(t)代表在t時刻鏈路<i，j>上的已經被占用的帶寬[6]，N是網絡中所有鏈路的數目。下面簡單描述各模塊的實現方式。
3.1 拓撲發現模塊
拓撲發現模塊的功能是收集網絡的拓撲信息，將其保存在拓撲圖表中，並對網絡的拓撲結構進行管理。控制器與交換機之間是在OpenFlow標準協議的基礎下進行通信的，但是控制器並不能通過Open。Flow協議獲得網絡的拓撲結構，是通過LLDP組件[7]發送LLDP(Link Layer Discovery Protocol)數據包到OpenFlow交換機，再收集並解析交換機反饋的LLDP數據包，從而實現網絡拓撲感知。
3.2 大流監測模塊
由於本文所提出的負載均衡機制是針對大流的，所以必須有一種方法將大流和小流區分開來。文獻[8]對3種主流的大流監測機制進行了分析比較，包括採樣監測、應用監測和統計監測。文獻[9]中提出探測大流最有效的方式是在終端主機進行，一方面占用的資源比例相對交換機要少，從而避免大流監測占用過多的交換機端資源；另一方面流的狀態也取決於終端應用程式生成數據包的快慢，而不是網絡的鏈路狀態，終端對應用程式發包速率的可知性更強。監測原理是通過觀測終端主機socket緩存區，當緩存區內具有相同特徵的數據包大小超過100 KB，它就會被標記為大流，本文便採用對主機端的統計監測方式來進行大流監測，主機端需要精確統計和維護數據流的速率和字節等信息，再將統計信息通過交換機發送到控制器，從而實現控制器的大流監測功能。
3.3 流量收集模塊
這個組件的目的是詢問每個OpenFlow交換機的流量信息，再將所有收到的反饋信息進行聯合併最終存儲到控制器的存儲單元。這些收集到的數據被路徑計算模塊用來計算不同鏈路上的負載，因為基於權重的多路徑路由的核心思想是將大流的數據包分配到負載較輕的鏈路上，因此需要確切知道路徑上所有可能的鏈路負載。這個單元模塊周期性地通過輪詢的方式收集每個OpenFlow交換機的流數量、流表以及埠數據，並作為一個快照對象進行存儲。每個快照對象都會通過一串數字標識，每個周期生成新的快照對象後數字標識會自動加1，存儲區只會保存最新的2個快照對象，其他的功能模塊都有獲得快照對象數據的權限。
3.4 路徑計算模塊
初始狀態採用Floyd[10]算法計算基於跳數的Top-K最短路徑，然後需要對每條路徑的狀態進行評估。本文主要對路徑的兩個方面指標進行評估，一個是路徑所包含鏈路的長度，這個體現在跳數（Hop Count）；另外一個指標是路徑上的負載，這個體現在這條路徑所包含的交換機和鏈路上的流量。由於每條路徑上包含多個交換機以及多條鏈路，不能簡單地以總流量的平均數來表示這條路徑的負載，而應該根據特定的交換機和鏈路來代表該路徑的負載情況。交換機的負載通過它所統計的PC(Packet Count)和BC(Byte Count)來體現，鏈路的負載通過埠的轉發率（Forwarding Rate）來表示。這些數據可以通過控制器周期性地向OpenFlow交換機發送狀態請求消息得到。每條路徑的負載狀況可以表示為S=(H，P，B，F)，其中H表示跳數；P=Max(P1，P2，…，PH)，Pi表示該路徑的第i台交換機所轉發的封包數量，共包含H台交換機；B=Max(B1，B2，…，BH)，Bi表示該路徑的第i台交換機所轉發的字節數量。F=Max(F1，F2，…，FH)，Fi表示該鏈路經過的第i台交換機出埠的轉發率。由於參數之間的差異比較大，需要先進行如下變換[11]：
每一條路徑可以用矩陣R=(rhrprbrf)表示,權重向量W=(0.35，0.20，0.20，0.25)，各個參數值根據經驗自己定義，這裡路徑的長度取0.35顯示了其重要性。每個節點對之間的所有路徑可以通過一個矩陣表示為：
Qi表示路徑i最後的權值，根據權值可以確定數據流經i節點傳輸到j節點的最佳路徑。路徑計算模塊偽代碼如下：
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 流表導入模塊
中心控制器通過路徑計算模塊產生的結果生成轉發規則，然後封裝到Packet_out消息中導入到支持OpenFlow的交換機，交換機流表添加該轉發規則並根據更新的流表項來指導流量轉發。由於網絡流量和拓撲結構都是不可預測的，交換機流表會伴隨負載均衡機制實時、動態地更新，而且過期的流表項會根據交換機配置而刪除。
4 實驗結果分析
本文採用Mininet2.2.0[12]作為一個開發環境模擬數據中心網絡場景，搭建如圖3所示的網絡拓撲結構，在Ubuntu Kylin 14.04.3上運行RYU控制器，結合iperf工具來產生TCP(Transmission Control Protocol)數據流和UDP(User Datagram Protocol)數據流，並且能夠測量端到端的吞吐量，從而得出整個網絡的吞吐量。host1～4同時向host5～8發送數據流量，在RYU[12]控制器中結合拓撲發現模塊、流量監測模塊、路徑計算模塊和流表導入模塊來對負載均衡算法進行驗證。仿真實驗通過h1～h16傳輸時延、總吞吐量和總體鏈路利用率這3個指標來驗證本文所提出的負載均衡算法的有效性。總體鏈路利用率通過下式得到：
其中，MAXLOAD代表每條物理鏈路最大帶寬，仿真實驗的信息見表1。
選擇h1和h16為網絡時延測量的觀測對象,實驗結果如圖4所示，在實驗進行的前47 s數據包從h1～h16延時很低，而且本文所提出的LB(Load balance)算法和基於最短路徑算法的時延曲線表現出了極高的相似度。這是因為剛開始時鏈路負載較輕，兩種算法都是採用h1-S1-S9-h16來傳輸流量，而LB算法由於需要監測數據流量並且周期性地向控制器發送網絡狀態信息，這樣會產生部分開銷而導致延時略高於基於最短路徑算法；但是47 s之後LB算法下的時延明顯低於採用OSPF算法的時延，這是因為太多的流量集中在最短路徑h1-S1-S9-h16，而其他可用路徑處於空閒狀態，負載不均衡度大於判決門限，就會觸發負載均衡機制，原路徑上的流量會轉移到其他可用路徑，鏈路利用率也得到了明顯提升，如圖5所示。網絡整體吞吐量的性能比較如圖6所示，當負載低於550 Mb/s時，兩者的性能曲線非常相似，由於LB算法需要傳輸額外的鏈路狀態信息導致吞吐量會略高於550 Mb/s；當負載超過550 Mb/s，基於最短路徑算法網絡出現擁塞，其他可用鏈路得不到有效利用，吞吐量的增長明顯放緩。而LB算法下的網絡吞吐量在550～700 Mb/s區間能一直保持快速增長。因此本文提出的LB算法相比傳統的OSPF算法能夠在負載不均衡情況下改善網絡性能。
5 結束語
本文設計了負載均衡功能實現的總體框架，主要包括拓撲發現模塊、流量監測模塊、路徑計算模塊、流表導入模塊。設計了負載均衡功能的實現流程圖，對相關的數學模型進行了詳細的分析設計，確定了以大流為目標流的調度策略，並通過實驗驗證了該負載均衡算法相比傳統的OSPF算法能夠實現更低的網絡延時和更高的總體鏈路利用率和吞吐量。
該算法的不足之處是沒有考慮到大流出現重複調度的情況，如果某個大流被多次選為目標流調度，可能會使情況更糟糕，而且流的轉移開銷也會影響負載均衡的實現效率。降低大流在調度過程中的開銷具有重要的意義，上述兩點將是下一步需要重點關注的內容。
參考文獻
[1] 左青雲，陳鳴，趙廣松.基於Open Flow的SDN技術研究[J].軟體學報，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].北京：北京工業大學，2014.
[8] 李龍，付斌章.Nimble：一種適用於OpenFlow網絡的快速流調度策略[J].計算機學報，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/.
沒有留言:
張貼留言