朱素霞 龍翼飛 孫廣路

(哈爾濱理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 黑龍江 哈爾濱 150080)

0 引 言

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

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

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

本文的主要貢獻(xiàn)如下：

(1) 結(jié)合多商品流問題(Multi-commodity Flow，MCF)[9]，對負(fù)載均衡問題進(jìn)行了建模，根據(jù)網(wǎng)絡(luò)流量的分布提出了基于鏈路負(fù)載離散度的目標(biāo)函數(shù)。

(2) 針對網(wǎng)絡(luò)中的大流提出了基于大流分布度和可用負(fù)載度的大流重路由方法，并且與現(xiàn)有負(fù)載均衡方法進(jìn)行了比較，綜合多種評價指標(biāo)，在Fat-Tree拓?fù)浣Y(jié)構(gòu)下進(jìn)行實驗研究，驗證了LRLB算法的性能。

1 相關(guān)工作

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

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

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

2 算法設(shè)計

2.1 負(fù)載均衡問題建模

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

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

由于本文的目標(biāo)是實現(xiàn)全網(wǎng)鏈路的負(fù)載均衡，即將網(wǎng)絡(luò)流量均勻地分配到全網(wǎng)鏈路中。這里利用數(shù)學(xué)中的標(biāo)準(zhǔn)差概念，使用離散程度反映均勻程度，對目標(biāo)函數(shù)的具體定義如下：

(1)

(2)

(3)

其約束條件如下：

(4)

(5)

(6)

(7)

(8)

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

2.2 算法架構(gòu)

本文提出的LRLB算法處理流程主要包括五大模塊，分別為信息收集模塊、拓?fù)浒l(fā)現(xiàn)模塊、大流檢測模塊、路徑計算模塊、流表安裝模塊。總體架構(gòu)如圖1所示。具體的LRLB算法運行步驟如下：

(1) 拓?fù)浒l(fā)現(xiàn)模塊通過鏈路層發(fā)現(xiàn)協(xié)議(Link Layer Discovery Protocol，LLDP)獲取并更新全局網(wǎng)絡(luò)拓?fù)洹?/p>

(2) 信息收集模塊通過周期性地調(diào)用端口狀態(tài)請求方法和流狀態(tài)請求方法向交換機(jī)發(fā)送相關(guān)狀態(tài)請求消息，進(jìn)而獲取交換機(jī)端口狀態(tài)信息以及流的統(tǒng)計信息。

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

(4) 流表安裝模塊根據(jù)路徑計算模塊的結(jié)果將流表下發(fā)到對應(yīng)交換機(jī)。

圖1 總體架構(gòu)

2.3 大流調(diào)度算法

大流調(diào)度的主要思想是結(jié)合網(wǎng)絡(luò)中大流分布度和可用負(fù)載度對大流進(jìn)行調(diào)度。其中大流分布度分為鏈路和路徑兩種，這里將鏈路上的大流分布度定義為流經(jīng)鏈路的大流數(shù)量與網(wǎng)絡(luò)中大流總量的比值，相應(yīng)路徑上的大流分布度即為所有組成路徑的鏈路上大流分布度最大值。同樣，將鏈路可用負(fù)載度定義為鏈路上剩余可用帶寬和鏈路總帶寬的比值，對應(yīng)路徑上其最大值即為路徑可用負(fù)載度。具體大流調(diào)度算法執(zhí)行流程如下：

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

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

(9)

式中：Lnum表示流經(jīng)對應(yīng)鏈路的大流數(shù)量。當(dāng)網(wǎng)絡(luò)中越來越多的大流流經(jīng)當(dāng)前鏈路時，相應(yīng)的鏈路上大流分布度就會越高，對應(yīng)鏈路上大流之間碰撞次數(shù)就會越多。

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

(10)

(11)

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

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

(12)

(13)

(14)

3 仿真與結(jié)果分析

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

3.1 仿真環(huán)境

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

圖2 Fat-Tree網(wǎng)絡(luò)拓?fù)鋱D

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

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

表1 實驗環(huán)境參數(shù)

3.2 性能分析

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

圖3 平均對分帶寬對比

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

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

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

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

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

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

4 結(jié) 語

本文針對廣泛應(yīng)用的Fat-Tree數(shù)據(jù)中心網(wǎng)絡(luò)，進(jìn)行了相關(guān)負(fù)載均衡算法的研究?？紤]到大流對網(wǎng)絡(luò)的影響較大，結(jié)合大流在網(wǎng)絡(luò)中的分布度和候選路徑的可用負(fù)載度，設(shè)計了一種基于大流調(diào)度的LRLB算法。該算法對大流和小流分別采用了不同的路由方式，以實現(xiàn)全網(wǎng)流量的負(fù)載均衡。通過與經(jīng)典的ECMP和GFF負(fù)載均衡算法的仿真對比，進(jìn)一步驗證了本文提出的LRLB算法通過合理地調(diào)度大流，不僅獲得了在對分帶寬上的提升，而且降低了網(wǎng)絡(luò)傳輸時延，實現(xiàn)了更好的負(fù)載均衡效果。