一種多指標綜合評價負載均衡路由策略研究

倪曉軍，段元新，章 韻，張敏敏

(南京郵電大學 計算機學院·軟件學院，江蘇 南京 210003)

一種多指標綜合評價負載均衡路由策略研究

倪曉軍，段元新，章 韻，張敏敏

(南京郵電大學 計算機學院·軟件學院，江蘇 南京 210003)

目前，OpenFlow網絡還沒有一套完整的負載均衡解決方案，使得整體網絡資源利用率不高。文中利用OpenFlow網絡控制器集中控制的優勢，在控制器上設計并實現了一種動態負載均衡路由策略。該策略能夠根據網絡狀態信息動態制定數據流轉發策略：以鏈路多指標綜合評價值作為鏈路新的權重，并以此新權重計算源節點與目的節點間的最優路徑，從而引導數據流時刻處于最優轉發路徑上。最后利用Mininet仿真技術，對文中提出的負載均衡路由策略進行性能驗證仿真實驗。結果表明，文中提出的負載均衡路由策略有效緩解了網絡擁塞，提高了鏈路利用率。

OpenFlow；負載均衡；多指標；路由算法

1 概 述

從20世紀70年代互聯網開始到現在，隨著業務和應用的不斷豐富與發展，網絡規模及應用需求的大幅增長，與現有的網絡服務能力的矛盾越來越明顯。當前網絡以IP核心為網絡體系架構逐漸暴露出了各式各樣的問題，網絡承載功能已從數據處理、報文傳輸等基本需求擴展到從安全性、穩定性等多方面對服務質量做出承諾。隨著近年來數據中心的快速發展，作為網絡領域的一個經典問題，網絡鏈路的負載均衡開始得到大量關注。尤其是龐大而復雜的網絡拓撲數據中心網絡，如何對其進行管理和充分利用鏈路資源，正面臨來自流量工程、路徑優化、負載均衡等多個方面的挑戰。如果不能合理分配網絡負載，就很容易造成網絡擁塞，影響網絡服務的有效交付。鏈路負載均衡可以實現節點負載的均衡化，避免出現某些鏈路負載過重而其他鏈路閑置的情況。數據流均衡算法可以根據獲取的網絡鏈路狀態信息，動態選擇最優路徑，具有自適應能力，優化網絡資源分配，從而提高整體系統的吞吐量和資源的優化。傳統網絡采用的負載均衡路由算法大都基于跳數或時延參數，通過最短路徑優先算法實現。這些路由策略為相同源地址、目的地址的數據建立唯一傳輸路徑，而且在建立路徑時，未考慮網絡的傳輸狀態。這樣的路由策略由于其參數過于固定，路徑選擇結果相對單一，可能造成網絡局部鏈路擁塞，導致整體網絡資源利用率低下；同時，與最短路徑相比，次最短路徑或者花費稍長的路徑卻處于空閑狀態。

面對這些問題，研究者不得不借助硬件和相關協議進行網絡功能擴展，這種功能擴展和固化的硬件高度耦合的形式，將會導致新的想法和協議無法通過規模化部署得到驗證。網絡協議從最初的TCP/IP發展到現在的TCP/IP協議簇和上千種補丁協議。整個網絡越來越復雜，架構還是一如既往的封閉，缺少靈活性，難以跟上日益變化的網絡需求。

在這樣的背景下，亟需加快網絡技術創新的步伐，開發一種新型網絡技術架構來改善這種局面。其中軟件定義網絡[1-2](Software Defined Networking，SDN)則是近年來未來網絡領域諸多方向中堅實且明確的一個研究方向。它提出了一種更加靈活高效的部署模式，以適應企業級網絡越來越靈活多變的需求。在SDN技術中尤以OpenFlow[3]技術發展最快。OpenFlow網絡采用集中式的控制平面和分布式的轉發平面，控制平面利用OpenFlow相關協議對轉發平面進行集中控制，以此來完成數據的轉發。控制器集中控制能夠實現對全網絡中每一條鏈路的信息進行跟蹤檢測，保證制定數據流在網絡中的轉發策略時，充分考慮網絡的動態性能特征，從而改善網絡的負載均衡，提高其傳輸效率。

2 國內外研究現狀

2008年，Nick McKeown教授提出OpenFlow的概念，并詳細介紹了OpenFlow協議。OpenFlow憑借集中控制的優勢能夠有效處理復雜的流量模型，并基于負載狀況進行動態的、精細的調整。就負載均衡技術而言，傳統網絡的負載均衡通常是由負載均衡器完成。與傳統網絡不同，OpenFlow交換機本身只負責對數據包的轉發，負載均衡則由控制器來實現。對于網絡負載均衡而言，雖然傳統網絡中已有很多相關研究和解決方案，但在全新架構的SDN網絡中，如何利用OpenFlow協議原理去實現鏈路負載均衡策略的相關研究并不多，仍然有待開發與完善。目前基于OpenFlow的負載均衡研究主要集中在控制器上，利用控制器集中管理優勢，定時對交換機的流量狀態進行統計，根據網絡鏈路負載情況動態調整網絡中的數據流。

但OpenFlow技術目前還處于發展初期，在協議和處理機制上還存在諸多需要改進和完善的地方[4]。現有的OpenFlow控制器系統，如NOX[5]、FloodLight[6]等，均提供了用于完成數據幀轉發的模塊，其采用Dijkstra最短路由算法，為OpenFlow交換機網絡提供一種簡單策略，實現基本的數據轉發功能。然而，這種轉發方式很容易造成鏈路阻塞。

針對控制器在負載均衡方面存在的不足，國內外許多學者都在進行這方面的研究。文獻[7]中提出的名為Hedera的數據中心網絡動態流調度系統，具有可擴展、自適應調度的特點，但其使用的ECMP和VLB等路由策略未考慮路徑的帶寬剩余容量，很可能會導致多條帶寬需求較大數據流的傳輸路徑存在部分公共鏈路，易導致網絡的擁塞。文獻[8]中提出的基于OpenFlow的可適應QoS視頻流優化框架，采用帶時延約束的拉格朗日松弛路由算法計算視頻流轉發路徑。但該論文只單獨研究了視頻流的轉發策略，并未考慮鏈路傳輸過程中數據流業務的多樣性和復雜性。文獻[9]提出了一種在胖樹型網絡拓撲結構中，基于OpenFlow的動態負載均衡路由算法DLB。雖然DLB這種針對單跳使用貪婪算法的選路策略簡單有效，但它沒有考慮網絡負載的分布情況。該方法選出的源節點到目的節點的整條路徑，可能并不是當前最優路徑，在這種情況下，甚至會加劇網絡的擁塞。文獻[10]中的GLB負載均衡算法改進了文獻[9]中的DLB算法，使用當前路徑最大剩余帶寬容量作為選路依據。在進行路徑決策時，計算出源節點到目的節點的所有路徑，以當前路徑最大剩余帶寬容量為依據選出最優傳輸路徑。然而，GLB負載均衡算法在選擇路徑時，只考慮了剩余帶寬容量的影響，并未考慮網絡中其他鏈路指標，如：時延、丟包率、鏈路花費等。

OpenFlow網絡目前尚未形成一個完整、可信服的負載均衡路由策略，并且各個學者的研究方案采用的控制器、路由策略、網絡拓撲、仿真環境也各不相同，還無法對其性能優劣進行對比。這些路由策略都是在OpenFlow網絡中的一些有益嘗試，為后續流量工程解決方案的研究提供了新的思路。

綜合上述研究成果，文中就數據流在OpenFlow網絡中的路徑選擇問題，利用OpenFlow網絡中控制器集中控制的優勢，在控制器上設計并實現了一種新的負載均衡路由策略—多指標評價的鏈路負載均衡路由策略。文中使用多指標評價體系對每條鏈路進行綜合評價，充分考慮鏈路傳輸數據流業務的多樣性和復雜性，并采用基于主觀判斷的方法改變鏈路各指標的權重，引導數據流轉發到最適宜的路徑上。

3 多指標全局負載均衡路由算法設計

3.1 多指標綜合評價模型

目前，網絡性能的分析和評價主要側重于對網絡協議或算法的性能進行分析，所涉及到的往往只是某個具體性能指標。然而，對實際或設計的網絡本身進行性能評價時，單個性能指標有時并不能反映網絡的整體性能。例如，在比較A、B兩個網絡的性能優劣時，A網絡有些性能指標優于B網絡，而B網絡亦有些性能指標優于A網絡，在這種情況下，就很難根據其中某一個性能指標來比較A、B兩個網絡整體性能的優劣。所以，必須采用多指標評價體系對網絡進行綜合評價，即將多個指標轉換為一個能夠反映網絡綜合性能的指標，來對網絡進行評價。為此，文中設計并實現了一種基于多指標綜合評價體系的鏈路負載均衡路由策略。

全球互聯網技術權威核心組織IETF的IPPM(IP Performance Metrics)[11]工作組提出了一系列網絡性能指標：時延、時延抖動、丟包率、路徑利用率、網絡吞吐量、網絡帶寬等，用于評價網絡的服務質量[12]。在日常網絡使用過程中，可用帶寬剩余容量、時延、丟包率三個網絡性能指標對網絡服務質量影響最大。因此，文中選取可用帶寬剩余容量、時延、丟包率三個網絡性能指標，以OpenFlow交換機的網絡接口作為測量對象，建立網絡性能的綜合評價模型，如圖1所示。該模型以網絡接口的流量信息為數據源，對經過接口的流量進行分析，得出該鏈路的性能指標信息。

圖1 鏈路性能綜合評價模型

文中根據網絡測量獲得的各性能指標數據，建立一套行之有效的評價模型，對網絡運行狀態進行評價，從而更直觀地反映網絡的綜合性能情況。因各個指標之間的大小評價程度和影響力不同，無法進行統一比較，需要通過數學變換的方式，消除各測量指標數值之間的影響。模糊評估方法廣泛應用于各個領域，特別是評價參數較多、評估結論比較模糊的場合，效果更加明顯，如大小、高低、好壞的評估。模糊評估方法主要有模糊矩陣法[13-14]、Delphi法[15]、神經網絡法[16]等。文中運用模糊集之父—美國學者L.A.Zadeh提出的模糊隸屬度函數的方法，結合文獻[13-14,17]等提出的模糊評價模型，采用直線型模糊無量綱化方法評價網絡性能。此方法的操作步驟是：

(1)正指標，指標測量值越大，網絡性能越好，如帶寬等。

(2)負指標，指標測量值越大，網絡性能越差，如時延等。

最后，采用加權平均評價模型計算路徑的綜合性能評價值，計算方法如下：

wk的取值可以根據不同的網絡服務類型做相應調整。例如，對于網絡帶寬需求較大的文件傳輸，可通過相應提高鏈路可用帶寬剩余容量的權重系數來滿足其需求。通過調整鏈路各評價指標的權重，就可以適應各種類型的網絡服務。

3.2 鏈路選擇

在得到每一條鏈路的綜合性能評價值后，下一步就是根據該綜合評價值選出一條最優轉發路徑。由于需要動態制定轉發策略，每當有新數據流到達OpenFlow網絡交換機時，Floodlight控制器都會綜合全網絡中各鏈路的負載情況，為新數據流選擇適宜的轉發路徑，實現全網絡鏈路的負載均衡。同時，由于流表中沒有與到達交換機的新數據流相匹配的流表項，OpenFlow網絡交換機會將數據流的分組封裝Packet-in消息發送到控制器，控制器經過以下步驟完成對該數據流的處理：

Step1：解析數據包的源地址、目的地址；

Step2：根據源地址與目的地址，分別查找與其直連的OpenFlow網絡交換機；

Step3：根據鏈路狀態計算鏈路的綜合評價值；

Step4：根據網絡拓撲結構、鏈路綜合評價值，為該數據流選取最優轉發路徑；

Step5：創建流規則，并將該數據流的處理規則告知轉發路徑上的所有交換機。

4 仿真實驗與結果分析

為了實現上述實驗方案，文中設計并實現了一套基于OpenFlow網絡的仿真實驗系統。系統架構如圖2所示。

圖2 仿真實驗系統架構圖

該實驗系統是在一臺Windows 8系統主機上運行兩臺Ubuntu系統虛擬主機。一臺虛擬主機運行Mininet[18]仿真軟件并部署sFlow[19]代理采集器，另一臺虛擬主機運行Floodlight控制器軟件和sFlow收集器，sFlow收集器用于收集接口信息并反饋給控制器。sFlow是由InMon、HP和Foundy Networks于2001年聯合開發的一種網絡監測技術，并已形成RFC3176標準，是一種以設備端口為基本單位的數據流隨機采樣流量監控技術，不僅可以提供網絡的第2～4層實時流量信息，而且可以適應超大網絡流量(如大于10 Gbit/s)環境下的流量分析，讓用戶詳細、實時地分析網絡傳輸流的性能、趨勢以及存在的問題。sFlow作為一種標準協議，可以提供周期性的網絡接口統計采樣和數據包采樣，也能夠提供各接口的流量信息，而且幾乎不會對被統計設備造成任何負擔，管理成本極低(sFlow的原理和部署過程不再贅述)。兩臺虛擬主機使用Bridged Adapter模式進行通信。sFlow代理采集器會將采集到的各鏈路實時性能信息發送至sFlow收集器，sFlow收集器將接收到的鏈路信息存儲到本地數據庫中，并每隔一定周期更新一次數據庫中的鏈路信息。當控制器需要為新數據流分配轉發路徑時，控制器讀取本地數據庫中的鏈路信息，相應制定數據流轉發策略，從而實現動態調整網絡負載。采取傳統網絡中比較成熟的網絡信息采集軟件sFlow，可以避免出現因采集鏈路信息引發Floodlight控制器負荷過大的問題，使控制器在幾乎零負荷的情況下就能采集得到網絡中的鏈路信息。

仿真實驗采用的網絡拓撲結構如圖3所示。所有鏈路帶寬限定為5 Mbps，每條鏈路上的傳輸時延設定為10～20 ms間的一個隨機整數，sFlow收集器收集每個鏈路上的有效信息并傳至Floodlight控制器，設置sFlow統計數據的刷新時間為2 s，三個性能指標所占權重都設為1/3。

圖3 模擬實驗所用的網絡拓撲結構圖

為了測試鏈路評價值的靈敏度，將鏈路(s2,s1)作為觀測主體，向其注入流量，實時觀測各鏈路的綜合評價值。實驗步驟如下：

Step1：初始狀態時，沒有其他流量干擾，網絡狀態趨于穩定，得到的鏈路綜合評價值相對穩定。

Step2：h2以3Mbps的速率向h1發送udp數據包，為鏈路(s2,s1)注入流量，幾秒后以5Mbps的速率向h1發送udp數據包。

實驗結果如圖4所示。

從圖中可以看出，當鏈路(s2,s1)注入流量后，鏈路(s2,s1)的綜合評價值下降幅度很大，說明模擬實驗系統具有對鏈路信息實時監測計算的能力。

下面采用搭建的仿真實驗系統，在轉發路徑能夠正常分配的前提下，分別對文中提出的路由策略與Floodlight控制器的最短路由轉發策略進行仿真實驗。為保證實驗數據具有較高的可靠性，使用以上兩種路由策略各進行三次實驗，分別記錄路徑選擇結果。實驗條件如下：

圖4 鏈路性能評價曲線圖

設定主機h1每隔2s啟動一次，輪流與h6、h7進行通信，兩條數據流均為3Mbps的udp數據流，每條數據流持續時間為60s。

實驗結果如表1、表2所示。

表1 Floodlight最短路由轉發策略路徑分配表

表2 多指標綜合評價路由策略路徑分配表

從表1可以看出，三次模擬實驗Floodlight最短路由策略路徑選擇結果相同。當兩條數據流都在路徑s1-s2-s3-s6中傳輸時，勢必會出現鏈路擁塞問題。而從表2可以看出，多指標綜合評價路由策略在進行路徑分配時，能夠根據網絡鏈路的狀態信息，合理分配轉發路徑，避免了最短路由策略中部分鏈路過載、部分鏈路空閑的問題，提高了網絡資源的有效利用率。

采用文獻[20]中的隨機流量模式，分別使用文中提出的路由策略與Floodlight控制器的最短路由轉發策略進行仿真實驗，對比兩種路由策略對網絡帶寬利用率的影響。實驗過程中，每一臺主機等概率選擇另一臺主機進行通信，流量發送速率從0.5Mbps至5Mbps依次增大，每條數據流持續時間為60s。實驗結果如圖5所示。

從圖中可以看出，使用文中提出的基于鏈路綜合評價的數據流負載均衡路由策略，帶寬利用率明顯高于Floodlight的最短路由策略，且隨著數據流發送速率的增大，兩者之間的差距越來越明顯。因此，基于鏈路綜合評價的負載均衡路由策略可以有效提高網絡的利用率。

5 結束語

文中針對OpenFlow網絡發展初期負載均衡不完善的問題，分析了現有基于OpenFlow技術負載均衡的研究成果，提出了基于鏈路多指標評價體系的負載均衡路由策略。該策略采用多個鏈路指標，對鏈路的性能進行綜合評價，并據此制定數據流轉發策略，選取最有利于當前網絡負載均衡的傳輸路徑，避免出現局部鏈路阻塞的問題。最后在Mininet實驗平臺上搭建性能驗證仿真實驗系統，驗證了文中方案的可行性和有效性。

實驗結果表明，文中設計的負載均衡路由策略有效緩解了網絡擁塞，提高了網絡資源的整體利用效率。但文中也有很多不足之處。例如，由于該路由策略需要計算每條鏈路的綜合評價值，計算量較大，這在一定程度上限制了文中提出的路由策略的應用。針對不足之處，后續還將繼續修訂完善。

[1] 萬 昕.關于SDN如何解決傳統網絡問題的探究[J].江西通信科技,2013(2):11-13.

[2] 左青云,陳 鳴,趙廣松,等.基于OpenFlow的SDN技術研究[J].軟件學報,2013,24(5):1078-1097.

[3]FeamsterN,RexfordJ,ZeguraE.TheroadtoSDN:anintellectualhistoryofprogrammablenetworks[J].ACMSIGCOMMComputerCommunicationReview,2014,44(2):87-98.

[4] 張朝昆,崔 勇,唐翯祎,等.軟件定義網絡(SDN)研究進展[J].軟件學報,2015,26(1):62-81.

[5]GudeN,KoponenT,PettitJ,etal.NOX:towardsanoperatingsystemfornetworks[J].ACMSIGCOMMComputerCommunicationReview,2008,38(3):105-110.

[6] Floodlight[EB/OL].[2005-09-06].http://www.projectFloodlight.org/Floodlight/.

[7] Al-Fares M,Radhakrishnan S,Raghavan B,et al.Hedera:dynamic flow scheduling for data center networks[C]//Proc of networked system design and implementation.Berkeley:[s.n.],2010:19-33.

[8] Egilmez H E,Civanlar S,Tekalp A M.An optimization framework for QoS-enabled adaptive video streaming over OpenFlow networks[J].IEEE Transactions on Multimedia,2013,15(3):710-715.

[9] Li Y,Pan D.OpenFlow based load balancing for fat-tree networks with multi-path support[C]//Proc of IEEE international conference on communications.[s.l.]:IEEE,2013.

[10] 吳宇文.基于OpenFlow的網絡負載均衡算法的研究與設計[D].上海:華東師范大學,2014.

[11] Network Working Group.RFC 2678,IPPM metrics measuring connectivity[S].Pittsburgh:Network Working Group,1999.

[12] Garzon M,Rose J,Gao Y.DNA implementation of finite-state machines[C]//Proceedings of genetic programming 1997.[s.l.]:[s.n.],1997:479-490.

[13] 趙華瓊,唐學文.基于模糊層次分析法的網絡業務性能評估模型[J].計算機應用,2013,33(11):3035-3038.

[14] Yang Yunfei,Shi Jihong.Research on business performance evaluation model of power distribution network based on PTN[C]//Proc of international conference on computer science and network technology.[s.l.]:[s.n.],2011:902-905.

[15] Papamichael M K,Cakir C,Chia-Hsin C S,et al.DELPHI:a framework for RTL-based architecture design evaluation using DSENT models:performance analysis of systems and software[C]//Proc of ISPASS.[s.l.]:IEEE,2015:11-20.

[16] Payal A,Rai C S,Reddy B V R.Artificial neural networks for developing localization framework in wireless sensor networks:data mining and intelligent computing[C]//Proc of ICDMIC.[s.l.]:IEEE,2014:1-6.

[17] 袁凌云,王興超.基于路徑和多指標向量的WSN性能評價方法研究[C]//Proceedings of 2009 conference on communication faculty.出版地不詳：出版者不詳，2009:588-594.

[18] Mininet[EB/OL].[2015-09-06].http://mininet.org/.

[19] 董 青.sFlow統計數據在FloodLight控制器中的使用[EB/OL].[2013-01-17].http://blog.sina.com.cn/s/blog_3f2db1dc01015ah9.html.

[20] Al-Fares M,Loukissas A,Vahdat A.A scalable,commodity data center network architecture[J].ACM SIGCOMM Computer Communication Review,2008,38(4):63-74.

Research on Load Balancing Routing Strategy Based on Link Multi-index Evaluation System

NI Xiao-jun,DUAN Yuan-xin,ZHANG Yun,ZHANG Min-min

(College of Computer,College of Software,Nanjing University of Posts and Telecommunications, Nanjing 210003,China)

The underutilization of network resources is low,which resulted from the absence of a complete load-balancing solution in OpenFlow network.In this paper,a dynamic load balancing routing strategy for data flows is proposed and implemented on the controller of OpenFlow network,utilizing the centralized controlling advantages of controllers in OpenFlow network.The strategy could develop a dynamic data flows forwarding policy based on network condition information:the multi-index comprehensive evaluations of links served as the new weights which are applied in calculations of the best path between the source node and the destination node;sequentially the data flows would be forwarded on the best path at all times.At last,the Mininet simulation technology is used in verifying the performance of the proposed load-balancing routing strategy in this paper.The results show that the proposed load-balancing routing strategy can effectively alleviate the congestion of networks and improve the utilization of links.

OpenFlow;load balancing;multi-index;routing algorithm

2015-09-18

2015-12-22

時間：2016-05-25

國家自然科學基金資助項目(61472192)

倪曉軍(1969-)，男，碩士，副教授，研究方向為嵌入式系統的設計、實現及其在通信領域中的應用，嵌入式系統在無線傳感器網絡領域的技術及應用等；段元新(1989-)，女，碩士生，研究方向為軟件定義網絡、網絡性能分析等。

http://www.cnki.net/kcms/detail/61.1450.TP.20160525.1711.062.html

TP393

A

1673-629X(2016)06-0046-05

10.3969/j.issn.1673-629X.2016.06.010