基于大流調度的軟件定義數據中心網絡負載均衡算法

朱素霞 龍翼飛 孫廣路

(哈爾濱理工大學計算機科學與技術學院 黑龍江 哈爾濱 150080)

0 引 言

隨著云計算和互聯網應用的飛速發展，數據中心網絡(Data Center Network，DCN)的規模逐步擴大，其內部的網絡流量也在以指數等級增長，對帶寬的需求不斷增加。現有的網絡拓撲無法滿足其對帶寬的需求[1]，為此，眾多研究人員提出了許多新型數據中心網絡拓撲結構，如DCell[2]、PortLand[3]、BCube[4]、Fat-Tree[5]等。目前，在數據中心使用最為廣泛的是Fat-Tree網絡拓撲。另外，傳統的網絡架構已經無法滿足現代數據中心網絡的發展需求。因此，軟件定義網絡(Software Defined Network，SDN)作為新興的網絡體系架構誕生了，其核心思想是將網絡數據的控制和轉發分離[6]。由于SDN集中式架構的特性，使其能夠掌握全局網絡視圖，從而為解決數據中心流量調度，實現全網負載均衡提供了很好的思路。

針對數據中心流量負載均衡問題，國內外科研人員對真實的數據中心網絡流量特征進行了大量的研究。其中，Benson等[7]發現在數據中心網絡中大流數量雖然少于網絡流數量的10%，但卻占了網絡流量帶寬的80%。同時，有研究表明小流經常在大流的后面，容易產生較長時間的隊列延遲[8]。為了提高數據中心的網絡性能，研究對大流的重路由算法，減少大流之間的沖突，從而保證網絡整體鏈路的負載均衡變得尤為重要。

鑒于目前的負載均衡算法在對大流進行調度的時候沒有考慮到大流在鏈路上的分布情況，可能將多條大流分配到同一鏈路，導致流傳輸時延過高。為此，本文針對大流在網絡鏈路中的分布，進一步提出了一種基于大流調度的軟件定義數據中心網絡負載均衡算法(Large-flows Routing Load Balancing，LRLB)。

本文的主要貢獻如下：

(1) 結合多商品流問題(Multi-commodity Flow，MCF)[9]，對負載均衡問題進行了建模，根據網絡流量的分布提出了基于鏈路負載離散度的目標函數。

(2) 針對網絡中的大流提出了基于大流分布度和可用負載度的大流重路由方法，并且與現有負載均衡方法進行了比較，綜合多種評價指標，在Fat-Tree拓撲結構下進行實驗研究，驗證了LRLB算法的性能。

1 相關工作

關于數據中心網絡中流量負載不均衡的問題，現有的解決方法主要有兩大類，分別是確定性方法和非確定性方法[10]。確定性方法是針對特定的輸入產生相同的輸出，這類方法普遍存在的問題是容易產生較長的時延和過大的丟包率；而非確定性方法則是針對相同的輸入，在不同的運行環境中可能會有不同的輸出，該類算法的總體缺點是由于計算量較大，容易導致過高的系統開銷和資源消耗。

在確定性算法中，傳統的等價多路徑算法(ECMP)[11]采用靜態散列的方式將數據流均勻地分配到多條等價路徑上，但該算法沒有考慮到網絡流量的特征以及鏈路狀態的實時變化，以至于該算法局限性很大。付應輝等[12]提出了一種基于帶寬需求的多路徑負載均衡算法(F-MPLB)，通過對鏈路的評估，在滿足帶寬需求的路徑中選擇瓶頸帶寬最大的路徑進行路由，考慮因素過于單一，可能錯過更好的路徑。彭大芹等[13]根據流量特征和鏈路狀態提出了一種多路徑路由算法(MLF)，針對小流僅依據剩余帶寬對其進行調度，調度路徑可能時延較大，容易導致小流的傳輸時延不理想。

另外，在非確定性算法中，Al-Fares等[14]針對數據中心網絡負載均衡問題提出了Hedera動態流量調度系統，其中包括全局最先匹配算法(GFF)，該算法是從所有候選路徑中貪婪地選擇第一條滿足流需求的路徑，其缺點是該路徑可能不是全局最優路徑；模擬退火算法(SA)使用概率性搜索的方式確定最優路徑，雖然執行的速度很快，但是收斂速度比較慢。林智華等[15]通過對粒子群算法的改進，進一步提出了離散粒子群算法(DPSOFS)，算法針對路徑隨機搜索的盲目性，限定了其搜索范圍，使其收斂速度加快，但是開銷相對較大。

2 算法設計

2.1 負載均衡問題建模

由于負載均衡問題和多商品流問題MCF的本質是一樣的，都是一種組合優化的NP(Non-deterministic Polynomial)完全問題。因此，本文把網絡中的負載均衡問題轉化為經典的多商品流問題，對其進行建模求解。其中模型的主要特征是在給定的網絡拓撲結構和鏈路容量約束的條件下，通過合理地調度網絡流量，控制其在網絡中的傳輸代價值，進而使其均勻地分布在網絡中的每條鏈路上。這里把多商品流問題中的商品映射為網絡負載均衡問題中的數據流。目標是將數據流中的大流盡量均勻地分配到其候選路徑上，從而均衡全網鏈路負載，實現數據中心網絡的負載均衡。模型本質是一種整數線性規劃數學模型，對于網絡中包含大流數目較多的情況效果明顯，具備一定優勢。問題的具體建模描述如下：

對于典型的Fat-Tree網絡拓撲結構，可以將其抽象為一個有向圖G=(H∪S,E)。其中：H與S分別代表主機節點集合和交換機節點集合；E則代表鏈路集合。網絡中共有m條鏈路，其中鏈路可表示為lij,i,j∈H∪S，另外，定義鏈路的最大負載為Cij。網絡中共有n條流，流的集合可以表示為F={f1,f2,…,fn}，定義其中一條流fk為一個四元組(sk,dk,rk,tk)，k∈{1,2,…,n}，其中：sk∈H表示源主機節點；dk∈H表示目的主機節點；rk表示流fk的帶寬需求；tk為流fk的大小標記，當其值為1時即為大流，值為0時則為小流。

由于本文的目標是實現全網鏈路的負載均衡，即將網絡流量均勻地分配到全網鏈路中。這里利用數學中的標準差概念，使用離散程度反映均勻程度，對目標函數的具體定義如下：

(1)

(2)

(3)

其約束條件如下：

(4)

(5)

(6)

(7)

(8)

其中：式(4)定義了流守恒約束；式(5)代表流fk從源主機流出的流量等于流入目的主機的流量；式(6)則表示除源主機和目的主機節點外，流fk在中間任意交換機節點流入和流出的流量相等;式(7)代表流容量約束，即任意一條鏈路上的總流量應小于等于鏈路容量；式(8)代表流請求帶寬約束，流fk的請求帶寬應大于等于0，不能為負值。

2.2 算法架構

本文提出的LRLB算法處理流程主要包括五大模塊，分別為信息收集模塊、拓撲發現模塊、大流檢測模塊、路徑計算模塊、流表安裝模塊。總體架構如圖1所示。具體的LRLB算法運行步驟如下：

(1) 拓撲發現模塊通過鏈路層發現協議(Link Layer Discovery Protocol，LLDP)獲取并更新全局網絡拓撲。

(2) 信息收集模塊通過周期性地調用端口狀態請求方法和流狀態請求方法向交換機發送相關狀態請求消息，進而獲取交換機端口狀態信息以及流的統計信息。

(3) 大流檢測模塊根據信息收集模塊所收集的信息對流經邊緣交換機的流大小進行判定，由于目前普遍將超過鏈路帶寬的1%～10%的流定義為大流[16]，所以，這里將超過鏈路帶寬5%的流標記為大流。路徑計算模塊則根據其判定結果對流進行路由，如果是小流則采用默認的ECMP路由方式對其進行路由，反之，若是大流則采用大流調度算法對其進行重路由。

(4) 流表安裝模塊根據路徑計算模塊的結果將流表下發到對應交換機。

圖1 總體架構

2.3 大流調度算法

大流調度的主要思想是結合網絡中大流分布度和可用負載度對大流進行調度。其中大流分布度分為鏈路和路徑兩種，這里將鏈路上的大流分布度定義為流經鏈路的大流數量與網絡中大流總量的比值，相應路徑上的大流分布度即為所有組成路徑的鏈路上大流分布度最大值。同樣，將鏈路可用負載度定義為鏈路上剩余可用帶寬和鏈路總帶寬的比值，對應路徑上其最大值即為路徑可用負載度。具體大流調度算法執行流程如下：

(1) 由于大流流經鏈路越多，大流之間發生碰撞的次數就越多。為此，本文根據獲取的網絡統計信息，通過KSP算法[17]計算得出大流源主機和目的主機之間基于跳數的x條最短候選路徑集合P={P1,P2,…,Px}。選擇跳數較少的路徑對大流進行調度可以有效降低大流之間產生沖突的概率和次數。同時，選擇多條相對較短的路徑作為備選，可以很好地避免遺漏較好的路徑。

(2) 計算候選路徑集合P中每個鏈路的大流分布度Ldegree，其具體計算方式如下：

(9)

式中：Lnum表示流經對應鏈路的大流數量。當網絡中越來越多的大流流經當前鏈路時，相應的鏈路上大流分布度就會越高，對應鏈路上大流之間碰撞次數就會越多。

(3) 求出每條候選路徑的大流分布度Pdegree，即當前路徑所包括的全部鏈路上大流分布度中的最大值，其值代表了該候選路徑大流分布度的瓶頸，具體求解方式如下：

(10)

(11)

(4) 在這y條路徑中找出可用負載度最高的路徑，即滿足式(12)，對大流進行重路由。

max(δ1,δ2,…,δy)

(12)

(13)

(14)

3 仿真與結果分析

為了展示所提出算法的優越性能，本文將對比在目前數據中心中應用廣泛的ECMP算法，還有基于GFF算法的Hedera動態流量調度系統。分別從平均對分帶寬、鏈路帶寬利用率、端到端的往返時延這三方面進行測試驗證。

3.1 仿真環境

本文采用兩臺安裝有Ubuntu 16.04 LTS系統的服務器作為實驗主機。其中：一臺實驗主機安裝Ryu 4.3.0[18]控制器，并在上面實現了LRLB算法原型；另一臺實驗主機則安裝Mininet 2.3.0[19]輕量級網絡仿真工具，用于模擬真實數據中心網絡環境。實驗采用經典的Fat-Tree網絡拓撲，Fat-Tree網絡拓撲中包含(k/2)2個核心交換機，k個Pod，每個Pod連接(k/2)2個主機，同時，其內部包含有k/2個聚合交換機和k/2個邊緣交換機，另外，每個交換機端口數量為k。這里取k=4，具體拓撲情況如圖2所示。虛擬交換機采用支持OpenFlow 1.3協議[6]的OpenvSwitch 2.5.5，同時，設置其內部最大緩沖隊列數為1 000。另外，設置鏈路帶寬為10 Mbit/s，并且為全雙工。每臺虛擬主機使用Iperf 2.0.5流量生成工具生成實驗所需網絡流量。

圖2 Fat-Tree網絡拓撲圖

虛擬主機之間采用隨機通信模式和交錯通信模式進行通信。其中，隨機通信模式Random表示網絡中虛擬主機之間以相等的概率進行隨機通信，交錯通信模式Staggered(pEdge,pPod)中pEdge表示同一Pod內相同子網的流量占比，而pPod則為不同子網之間的流量占比，另外，不同Pod間的流量占比為1-pEdge-pPod。

為了實驗測試的公平性，其中，針對交錯模式本文采用兩種具有不同特點的流量模型，分別為Staggered(0,0.5)、Staggered(0.3,0.5)。這里對每組流量模型重復測試20次，每次測試運行時間為60 s。其中控制器循環監控周期設置為5 s，設置基于跳數的候選路徑數x=8，具體如表1所示。測試期間使用bwm-ng 0.6.1工具對網絡帶寬進行監測，最后將每組流量模型測試結果取平均值作為實驗結果。

表1 實驗環境參數

3.2 性能分析

平均對分帶寬的實驗結果對比如圖3所示。從整體來看，當不同Pod間的流量占比較低時，網絡對分帶寬要高于其占比較高的時候。其原因是在Pod間流量占比較低的時候，即跨Pod間主機通信概率較低，相應地會導致網絡中大流之間的沖突概率降低，從而使其獲得相對更高的平均對分帶寬。在隨機的通信模式下，同一Pod內相同子網之間的通信量較低，與交錯通信模式Staggered(0,0.5)的流量模型所產生的結果較為接近。通過對比可以看出三種算法的差距較為明顯，其中，LRLB算法在平均對分帶寬上較ECMP提升了19.21%，較GFF提升了8.17%。而在流量模型Staggered(0.3,0.5)的實驗結果中，三種算法性能幾乎差不多，LRLB算法只是略高于其他兩種算法。這是由于此時Pod間通信量低，需要重調度的大流很少，以至于效果沒有那么明顯。由此可以看出Pod間流量占比越高，即需要重調度的大流越多，LRLB算法的優勢就越明顯。這是由于LRLB算法對大流進行了重調度，調度的同時綜合考慮了候選路徑的大流分布度和可用負載度，進而將多條大流從相對繁忙的路徑調度到相對空閑的路徑上，從而有效地減少了大流之間的沖突，最大限度提高了網絡的平均對分帶寬。

圖3 平均對分帶寬對比

圖4、圖5、圖6分別為三種流量模型下的鏈路帶寬利用率(CDF)對比實驗結果。總的來看，LRLB算法相對另外兩種算法，在低帶寬利用率的鏈路中占比明顯偏低。其中，在Random和Staggered(0,0.5)的流量模型內，LRLB算法中鏈路帶寬利用率低于10%的僅占比約20%，而在ECMP和GFF算法中占比則分別約40%和50%。LRLB算法不僅減少了帶寬利用率低的鏈路數量，同時也減少了帶寬利用率高的鏈路數量。這是因為LRLB算法在對大流重調度時，選擇將其調度到大流分布度相對較低的路徑上，從而使得大流被盡可能均勻地分配到網絡鏈路中，避免了部分鏈路上流經大流數目過多和過少的情況。同時，又由于大流所占帶寬相對較高，所以大多數鏈路的帶寬利用率相差不大，進而很好地降低了鏈路帶寬利用率的離散度，使得全網鏈路負載更加均勻。

圖4 Random下鏈路帶寬利用率對比

圖5 Staggered(0,0.5)下鏈路帶寬利用率對比

圖6 Staggered(0.3,0.5)下鏈路帶寬利用率對比

圖7為包平均往返時延實驗結果對比。通過三種流量模型的對比可以看出，LRLB算法通過將大流重路由到大流分布度相對較低的路徑上，使得小流不總是排在大流后面，從而相對另外兩種算法大幅降低了網絡中數據包的往返時延。其中，相對GFF算法分別降低了約44%、39%、29%，相對ECMP算法分別降低了約47%、46%、37%。雖然基于GFF算法的Hedera動態流量調度系統也對大流進行了重路由，但是由于其只是從單一的帶寬因素考慮進行的重調度，因此顯得較為片面。而LRLB算法同時又考慮了大流在鏈路中的分布情況，所以LRLB算法要更優于GFF算法。

圖7 包的平均往返時延對比

4 結 語

本文針對廣泛應用的Fat-Tree數據中心網絡，進行了相關負載均衡算法的研究。考慮到大流對網絡的影響較大，結合大流在網絡中的分布度和候選路徑的可用負載度，設計了一種基于大流調度的LRLB算法。該算法對大流和小流分別采用了不同的路由方式，以實現全網流量的負載均衡。通過與經典的ECMP和GFF負載均衡算法的仿真對比，進一步驗證了本文提出的LRLB算法通過合理地調度大流，不僅獲得了在對分帶寬上的提升，而且降低了網絡傳輸時延，實現了更好的負載均衡效果。