林智華,高 文,吳春明,李勇燕

(1.福建江夏學(xué)院電子信息科學(xué)學(xué)院,福建福州350108；2.浙江大學(xué)計算機(jī)學(xué)院,浙江杭州310027；

?

基于離散粒子群算法的數(shù)據(jù)中心網(wǎng)絡(luò)流量調(diào)度研究

林智華1,2,高 文2,吳春明2,李勇燕3

(1.福建江夏學(xué)院電子信息科學(xué)學(xué)院,福建福州350108；2.浙江大學(xué)計算機(jī)學(xué)院,浙江杭州310027；

3.紹興文理學(xué)院上虞分院,浙江上虞312300)

數(shù)據(jù)中心網(wǎng)絡(luò)利用多個并行路徑為集群計算等網(wǎng)絡(luò)服務(wù)提供高對分帶寬.然而,現(xiàn)有的流量調(diào)度算法可能會引起鏈路負(fù)載不均衡,核心交換機(jī)沖突加劇,造成網(wǎng)絡(luò)總體性能降低.本文將流調(diào)度問題轉(zhuǎn)化成0-K背包問題求解,提出基于離散粒子群的流調(diào)度算法DPSOFS(Discrete Particle Swarm Optimization Flow Scheduling).該算法根據(jù)Fat-Tree結(jié)構(gòu)特點定義了粒子速度、位置和運算規(guī)則,以兩次迭代沖突流個數(shù)差值作為目標(biāo)函數(shù),并限定路徑搜索范圍,減少隨機(jī)搜索的盲目性.仿真實驗驗證了該算法對減少流沖突快速有效,能提高網(wǎng)絡(luò)對分帶寬.

Fat-Tree；數(shù)據(jù)中心網(wǎng)絡(luò)；離散粒子群；流調(diào)度

1 引言

隨著數(shù)據(jù)量指數(shù)級的增長和各種網(wǎng)絡(luò)服務(wù)不斷涌現(xiàn),網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對現(xiàn)代云計算數(shù)據(jù)中心的擴(kuò)展性、成本、容錯、整體性能等方面產(chǎn)生重大影響[1].目前新型的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)主要有兩類[2],一類是以交換機(jī)為中心的結(jié)構(gòu),如Fat-Tree[3],PortLand[4],SPAIN[5]等；另一類是以服務(wù)器為中心的結(jié)構(gòu),如DCell[6],BCube[7],Hyper-BCube[8],等.其中,Fat-Tree拓?fù)浣Y(jié)構(gòu)相對簡單,容易部署,同時支持多條等價路徑和完全的對分帶寬[9],是新型的數(shù)據(jù)中心網(wǎng)絡(luò)中最受重視的體系結(jié)構(gòu)之一.

研究表明,網(wǎng)絡(luò)流量由大部分短暫流和小部分長命流組成,長命流占據(jù)了大部分帶寬.數(shù)據(jù)中心網(wǎng)絡(luò)中流量也是由很多小型的、事務(wù)方式的RPC(Remote Procedure Call)流和小部分大流組成.這些大流在網(wǎng)絡(luò)中存在的時間較長,對應(yīng)的數(shù)據(jù)包數(shù)或字節(jié)數(shù)相對較多[10],占據(jù)大量的鏈路帶寬.在Fat-Tree等樹型拓?fù)浣Y(jié)構(gòu)中(圖1),主機(jī)之間存在多條等價的路徑.因此,針對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特點研究并設(shè)計大流調(diào)度算法,減少大流碰撞,保證鏈路負(fù)載均衡,對于提高網(wǎng)絡(luò)傳輸性能至關(guān)重要.

數(shù)據(jù)中心網(wǎng)絡(luò)流調(diào)度算法主要分成靜態(tài)和動態(tài)兩類,ECMP(Equal-CostMultipathRouting)[11],VLB(Valiant Load-Balancing)[12]等靜態(tài)調(diào)度法會造成某條鏈路過載.動態(tài)調(diào)度算法中,GFF[11]對邊界交換機(jī)收到的流在全網(wǎng)線性查找無沖突路徑,實現(xiàn)局部優(yōu)化.Hedera[11]采用集中控制調(diào)度策略,在全網(wǎng)視圖下通過模擬退火算法得到流優(yōu)化路徑.DDFS[13]和Flowlet[14]通過分布式方式控制匯聚層交換機(jī)鏈路負(fù)載率來實現(xiàn)網(wǎng)絡(luò)負(fù)載均衡,DiFS[15]通過交換機(jī)間控制命令來減少流量沖突,從而增加網(wǎng)絡(luò)帶寬利用率.

未來數(shù)據(jù)中心的網(wǎng)絡(luò)設(shè)備將實現(xiàn)數(shù)據(jù)面和控制面的分離,在控制面上可以進(jìn)行全局流量集中管控.本文針對Fat-Tree數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特點,借鑒離散粒子群DPSO思想,提出流調(diào)度算法DPSOFS,將流調(diào)度問題轉(zhuǎn)化成0-K背包問題求解,在數(shù)據(jù)中心網(wǎng)絡(luò)全局高度上進(jìn)行流路由安排,得到最優(yōu)網(wǎng)絡(luò)對分帶寬.實驗結(jié)果表明,該算法使網(wǎng)絡(luò)對分帶寬較GFF和Hedera算法提高了20%以上,沖突流數(shù)量減少40%左右,網(wǎng)絡(luò)性能得到明顯改善.

2 相關(guān)工作

總體來講,當(dāng)前數(shù)據(jù)中心網(wǎng)絡(luò)的流調(diào)度算法分成靜態(tài)和動態(tài)兩種,動態(tài)算法中又劃分成集中式調(diào)度和分布式調(diào)度兩種方式.

ECMP通過計算收到的數(shù)據(jù)包頭的散列值所對應(yīng)的等價路徑的端口地址來轉(zhuǎn)發(fā)數(shù)據(jù)流.但由于靜態(tài)調(diào)度的特性,該算法在轉(zhuǎn)發(fā)過程不考慮數(shù)據(jù)包或數(shù)據(jù)流大小,當(dāng)某一主機(jī)流量較大時,依然會映射到同一轉(zhuǎn)發(fā)端口,造成該端口負(fù)載增加,使得多條等價鏈路并不平衡.

VLB隨機(jī)選擇可用的轉(zhuǎn)發(fā)端口實現(xiàn)負(fù)載均衡,但是依然存在多條數(shù)據(jù)流選擇同一端口,導(dǎo)致流沖突和鏈路過載.

GFF流調(diào)度算法構(gòu)建了中心調(diào)度器,對邊界交換機(jī)收到的流線性查找一條無沖突路徑.但是由于該算法在流分配上的先后次序不同,不能保證整個網(wǎng)絡(luò)獲得較優(yōu)的對分帶寬.

Hedera在全局網(wǎng)絡(luò)視圖下通過模擬退火算法得到流優(yōu)化路徑,使網(wǎng)絡(luò)對分帶寬有了一定的提高.但是它在路徑選擇上完全隨機(jī),在主機(jī)數(shù)量較大的情況下,核心交換機(jī)上可能產(chǎn)生流量擁塞,優(yōu)化效果不明顯.

DDFS分布式調(diào)度定義了鏈路負(fù)載率,通過控制聚合層交換機(jī)鏈路負(fù)載率來防止核心層交換機(jī)過載,實現(xiàn)負(fù)載均衡.Flowlet在DDFS的基礎(chǔ)上利用Flow splitting技術(shù),按不同鏈路負(fù)載率之間的比例關(guān)系,動態(tài)分割數(shù)據(jù)流到這些鏈路上,達(dá)到充分利用空閑鏈路帶寬的目的.但這兩種算法沒有驗證數(shù)據(jù)中心總體網(wǎng)絡(luò)性能和吞吐量的改進(jìn).

DiFS算法在交換機(jī)上增加Explicit Adaption Request控制命令,通過該命令通告發(fā)送端遠(yuǎn)程流沖突,從而使發(fā)送端調(diào)整數(shù)據(jù)傳輸路徑來避免沖突發(fā)生.但在數(shù)據(jù)中心網(wǎng)絡(luò)較大的情況下,每臺交換機(jī)分布式獨立處理EAR控制命令,可能會增加通信開銷,降低整體網(wǎng)絡(luò)性能.

3 DPSOFS流調(diào)度算法

3.1 流調(diào)度問題數(shù)學(xué)模型

背包問題(Knapsack problem)是一種組合優(yōu)化的NP完全問題,其相似問題經(jīng)常出現(xiàn)在商業(yè)、組合數(shù)學(xué),密碼學(xué)和應(yīng)用數(shù)學(xué)等領(lǐng)域中.由于背包問題與流調(diào)度問題本質(zhì)是一致的,因此本文把該問題轉(zhuǎn)換成0-K背包這種經(jīng)典的問題進(jìn)行求解.

在Fat-Tree拓?fù)浣Y(jié)構(gòu)中,主機(jī)之間有條路徑.為某條流指定核心交換機(jī)的編號值,則唯一確定了主機(jī)間的通信路徑.因此,流調(diào)度問題可以描述成一個n維背包問題:已知n條流f1,f2,…,fn,以及對應(yīng)的流帶寬屬性值bi,(i=1,2,…,n),bi∈(0,1],m條鏈路l1,l2,…,lm,每條鏈路帶寬上限值為1.用一個向量ci(i=1,2,…,n)表示n條流對應(yīng)的核心交換機(jī)的編號,ci=(0,1,…,(K/2)2).當(dāng)ci取值為0表示選擇任何核心交換機(jī)都會造成流沖突,而非0值表示選擇某一臺核心交換機(jī)可行.另外,我們定義map(fi,bi,ci)為映射函數(shù),表示把流通過ci選擇的路徑映射到對應(yīng)的若干條鏈路上,用i×j的矩陣a表示映射結(jié)果,對應(yīng)的值是流fi占用鏈路lj的帶寬bi.該問題求解的目的是如何為所有的流fi選擇合適的ci,在保證所有鏈路l1,l2,…,lm,的帶寬上限值的前提下,使ci取值為0的個數(shù)最少.

嚴(yán)格的數(shù)學(xué)描述為:

(1)

式(1)中Minf(c1,c2,…,cn)為目標(biāo)函數(shù),求所有ci=0的個數(shù)總和最小值.約束條件為占用任意lj的流的帶寬之和aij應(yīng)限制在1以內(nèi).

3.2 流量帶寬需求預(yù)測算法

對數(shù)據(jù)中心網(wǎng)絡(luò)流量調(diào)度之前,必須先對每條大流的帶寬需求bi進(jìn)行預(yù)測.但流實際占用的帶寬值無法反映其真實帶寬需求.另外,流的大小、長度以及字節(jié)數(shù)都是未知變量,即使事先已知其流量大小,對其進(jìn)行帶寬需求的預(yù)測也是NP難的優(yōu)化問題.考慮到任何流的傳輸帶寬受限于發(fā)送端和接收端主機(jī)網(wǎng)卡的帶寬,利用主機(jī)網(wǎng)卡帶寬的限制來預(yù)測流的最大實際可用帶寬是可行的.流量帶寬預(yù)測算法描述如下:

輸入:n×n矩陣I(元素值Iij表示主機(jī)i向主機(jī)j發(fā)出大流數(shù)量),Si表示發(fā)送端主機(jī)i帶寬限值,Rj表示接收端主機(jī)j帶寬限值,帶寬初始限值為1.

輸出:n×n矩陣O(元素值Oij表示主機(jī)i向主機(jī)j發(fā)出流帶寬需求預(yù)測值).

矩陣變量T,其元素值Tij是由于受限于發(fā)送端的帶寬,計算得到發(fā)送端i向接收端j發(fā)送流的預(yù)測帶寬值.

矩陣變量A,其元素值A(chǔ)ij是由于受限于接收端的帶寬,計算得到發(fā)送端i向接收端j發(fā)送流的預(yù)測帶寬值.

步驟3:若存在任一元素Tij≠Aij則Oij=Min(Tij,Aij)；根據(jù)已確定的Oij,更新矩陣I和剩余Si值和Rj值；返回步驟1；

步驟4:若所有Tij=Aij則Oij=Tij；

步驟5:返回矩陣O；

3.3 DPSOFS算法設(shè)計

3.3.1 DPSOFS算法模型

粒子群算法PSO是一種受到鳥群飛行集群活動的規(guī)律啟發(fā)的群智能算法.在PSO算法中,每一個粒子被認(rèn)為問題的一個可行解,粒子以一定的速度在解空間運動,并向自身的歷史最佳位置和全局最佳位置聚集,實現(xiàn)對候選解的進(jìn)化[16],最終找到最優(yōu)解.與其他進(jìn)化算法相比,該算法收斂速度更快,更加簡單,易于實現(xiàn)并具有更強的全局優(yōu)化能力.近年來為了應(yīng)對實際工程應(yīng)用中的離散問題,研究者在原有算法基礎(chǔ)上進(jìn)行二進(jìn)制空間的擴(kuò)展,形成了離散粒子群算法DPSO.

(2)

整個群體得到的全局最優(yōu)值記為Gbk,則

(3)

每個粒子的速度更新公式為:

(4)

位置更新公式為:

(5)

輸入:由GFF流調(diào)度算法得到的ci(i=1,2,…,n)；

輸出:算法運算后的ci(i=1,2,…,n)結(jié)果以及ci=0的個數(shù)值；

步驟1:當(dāng)ci=0且i

步驟2:對每一條沖突的流隨機(jī)分配一臺核心交換機(jī),即ci=Rand(1,…,(k/2)2)；

步驟3:將步驟2中的流對應(yīng)的鏈路寫入矩陣a中,即map(fi,bi,ci);

步驟4:替換出原先已安排好的流,保證步驟2中的沖突流符合帶寬要求,R=replace(bi,ci)；

步驟5:對R集合中的流f執(zhí)行GFF(f)；

步驟6:計算ci=0的個數(shù)值并返回結(jié)果.

3.3.4 DPSOFS算法流程

DPSOFS流調(diào)度算法步驟如下:

輸入:n條流(f1,f2,…,fn)；

輸出:Gbk;

步驟1:設(shè)定最大迭代次數(shù),粒子個數(shù),獲得流量帶寬預(yù)測bi值,GFF算法ci值；

步驟3:令k=1；

步驟8:k=k+1；

步驟9:若k達(dá)到最大迭代次數(shù),則輸出Gbk,算法結(jié)束,否則返回步驟4.

4 實驗仿真平臺與結(jié)果

為了驗證DPSOFS算法的效果,我們通過Mininet[17]實驗平臺來搭建Fat-Tree網(wǎng)絡(luò).另外,為了驗證該算法收斂性能以及在大型數(shù)據(jù)中心網(wǎng)絡(luò)的擴(kuò)展性能,我們也模擬了算法在k值較大情況下的運行結(jié)果.

4.1 Mininet仿真平臺

在Mininet平臺上,我們配置了k=8-ary的Fat-Tree數(shù)據(jù)中心結(jié)構(gòu),每臺主機(jī)產(chǎn)生不同長度的流,長度服從指數(shù)分布,流產(chǎn)生的時間服從泊松分布.

每臺主機(jī)根據(jù)某種通信模式來選取目的主機(jī),并且每臺主機(jī)只接收網(wǎng)絡(luò)中某一臺主機(jī)的流量數(shù)據(jù).通信模式[3]有以下三種:間隔方式Stride(x)、交錯方式Staggered(pEdge,pPod)和隨機(jī)方式Random.

調(diào)度算法每隔5秒查詢所有邊界交換機(jī)大流(流傳輸數(shù)據(jù)超過100KB)的統(tǒng)計值,并計算最優(yōu)路徑.在流調(diào)度算法中,我們設(shè)定DPSOFS迭代次數(shù)為10,粒子數(shù)為3.在與Hedera算法對比時,由于Hedera循環(huán)不考慮流數(shù)量,因此我們把Hedera循環(huán)次數(shù)設(shè)為10×3×需調(diào)度的流數(shù)量.

在實驗中,我們使用對分帶寬作為測試的性能指標(biāo).對分帶寬越大,說明網(wǎng)絡(luò)的傳輸性能越強.

4.2 實驗結(jié)果

圖2是GFF、Hedera和DPSOFS三種算法在k=8的Fat-Tree拓?fù)湎戮W(wǎng)絡(luò)對分帶寬測試的結(jié)果.我們對三種通信模式分別進(jìn)行了多次測試,每次測試運行60秒,在第10秒到50秒這段時間內(nèi)測量對分帶寬.

在間隔模式下(一臺主機(jī)與距離其位置x的其它主機(jī)通信),GFF總能找到一條無沖突的路徑,得到最優(yōu)的對分帶寬值.這是由于Fat-Tree拓?fù)浣Y(jié)構(gòu)的特點,每臺交換機(jī)上聯(lián)和下聯(lián)的帶寬相同,即網(wǎng)絡(luò)過載率為1:1.按該模式通信的主機(jī)可以并行無沖突地傳輸.

在stag(0.5,0.3)交錯模式下,大多數(shù)流來自同一子網(wǎng),這些流通過邊界交換機(jī)直接進(jìn)行全雙工通信.由于不同Pod間通信的流數(shù)量較少,造成沖突的流也較少.三種算法得到的對分帶寬相差不大.在stag(0.2,0.3)交錯模式下,隨著Pod間通信流數(shù)量增加,沖突流也增多,因此,GFF得到的對分帶寬值有所降低.Hedera和DPSOFS在流數(shù)量較少的情況下都采用隨機(jī)調(diào)度的方式,但是DPSOFS利用多粒子并行搜索,并且粒子間共享全局最優(yōu)解,得到的結(jié)果好于Hedera,網(wǎng)絡(luò)對分帶寬亦高于Hedera.

在隨機(jī)模式下,同一個子網(wǎng)以及同一個pod之間的通信流減少,大多數(shù)為不同Pod之間的數(shù)據(jù)流.由于GFF調(diào)度先后次序造成較多的流無法找到無沖突路徑.因此其對分帶寬較低.Hedera對流的調(diào)度優(yōu)化不太明顯.但是從圖2(c)中可以看出,沖突流越多,DPSOFS多粒子并行運算獲得的網(wǎng)絡(luò)對分帶寬就越優(yōu),全局調(diào)度效果就越好.

4.3 大型數(shù)據(jù)中心網(wǎng)絡(luò)實驗仿真結(jié)果

由于大型數(shù)據(jù)中心網(wǎng)絡(luò)中的主機(jī)數(shù)量龐大,用Mininet無法實現(xiàn)仿真.為了驗證DPSOFS算法在收斂速度上的優(yōu)勢以及在大型數(shù)據(jù)中心網(wǎng)絡(luò)流調(diào)度性能,我們模擬了調(diào)度過程,得到了調(diào)度后三種算法產(chǎn)生的沖突流個數(shù),并進(jìn)行了比較.

(1)三種算法的收斂效果

在k=16的Fat-Tree拓?fù)浣Y(jié)構(gòu)下,我們測試了GFF、Hedera和DPSOFS在隨機(jī)通信模式下迭代20次后獲得的沖突流的個數(shù).

從圖3可以看出,經(jīng)過GFF調(diào)度后有124條流產(chǎn)生沖突.而DPSOFS在第三次迭代后時就獲得Hedera第五次迭代得到的較優(yōu)結(jié)果(優(yōu)化結(jié)果為108).DPSOFS在第七次迭代時就獲得超出Hedera最終的優(yōu)化結(jié)果(Hedera優(yōu)化結(jié)果為92).在迭代11次左右,DPSOFS算法基本完成了收斂,獲得全局較優(yōu)的結(jié)果,體現(xiàn)了該算法較強的收斂特性和全局優(yōu)化能力.

(2)三種算法在k值較大情況下的流調(diào)度效果

在算法測試過程中,我們選擇k=16、24和32的Fat-Tree拓?fù)浣Y(jié)構(gòu).測試結(jié)果為在隨機(jī)模式下,三種算法得到的沖突流個數(shù)值和對應(yīng)的占比關(guān)系,見表1,表2和表3.

表1 三種算法在隨機(jī)通信模式下的流沖突比較(k=16)

表2 三種算法在隨機(jī)通信模式下的流沖突比較(k=24)

表3 三種算法在隨機(jī)通信模式下的流沖突比較(k=32)

從表1,2,3中可以看到,DPSOFS在k值較大的情況下比Hedera表現(xiàn)出更優(yōu)的運算結(jié)果.隨著主機(jī)數(shù)的增加,Hedera優(yōu)化效果不明顯,在k=32時,多次測試Hedera/GFF比值保持在95%左右,而DPSOFS/GFF比值基本都在65%左右,體現(xiàn)了DPSOFS較好的流調(diào)度效果.這主要源于DPSOFS對隨機(jī)選擇核心交換機(jī)的改進(jìn)上.Hedera只是通過隨機(jī)選擇兩條流并交換各自的核心交換機(jī)位置來判斷兩次結(jié)果的優(yōu)劣；DPSOFS一方面通過多粒子并行計算并共享全局最優(yōu)解,另一方面充分利用空閑鏈路,避免選擇與其他流出現(xiàn)鏈路沖突的路徑,使得算法迭代次數(shù)減少,加快收斂,獲得更優(yōu)的調(diào)度結(jié)果.

5 結(jié)論

本文對當(dāng)前常用的Fat-Tree數(shù)據(jù)中心網(wǎng)絡(luò)流調(diào)度算法進(jìn)行了分析,針對集中控制的兩種動態(tài)調(diào)度算法GFF和Hedera進(jìn)行研究和改進(jìn),提出DPSOFS算法,將流調(diào)度問題轉(zhuǎn)化成0-K背包問題,以兩次迭代沖突流個數(shù)差值作為目標(biāo)調(diào)節(jié)函數(shù),并限定路徑搜索范圍.在仿真和驗證過程中,該算法體現(xiàn)出更快的收斂速度和更優(yōu)的調(diào)度結(jié)果.

[1]Hammadi A,Mhamdi L.A survey on architectures and energy efficiency in data center networks[J].Computer Communications,2014,40(1):1-21.

[2]Zhang Y,Ansari N.On architecture design,congestion notification,TCP incast and power consumption in data centers[J].Communications Surveys & Tutorials,IEEE,2013,15(1):39-64.

[3]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.

[4]Mysore R N,Pamboris A,Farrington N,et al.PortLand:a scalable fault-tolerant layer 2 data center network fabric[J].ACM SIGCOMM Computer Communication Review,2009,39(4):39-50.

[5]Mudigonda J,Yalagandula P,Al-Fares M,et al.SPAIN:COTS data-center ethernet for multipathing over arbitrary topologies[A].Proceedings of Networked System Design and Implementation[C].San Jose:NSDI,2010.265-280.

[6]Guo C,Wu H,Tan K,et al.DCell:a scalable and fault-tolerant network structure for data centers[J].ACM SIGCOMM Computer Communication Review,2008,38(4):75-86.

[7]Guo C,Lu G,Li D,et al.BCube:a high performance,server-centric network architecture for modular data centers[J].ACM SIGCOMM Computer Communication Review,2009,39(4):63-74.

[8]Lin D,Liu Y,Hamdi M,et al.Hyper-bcube:A scalable data center network[A].Proceedings of International Conferenceon Communications (ICC)[C].Ottawa:IEEE,2012.2918-2923.

[9]Escudero-Sahuquillo J,Garcia P J,Quiles F J,et al.A new proposal to deal with congestion in InfiniBand-based fat-trees[J].Journal of Parallel and Distributed Computing,2014,74(1):1802-1819.

[10]Tso F P,Hamilton G,Weber R,et al.Longer is better:exploiting path diversity in data center networks[A].Proceedings of Distributed Computing Systems[C].Philadelphia:IEEE,2013.430-439.

[11]Al-Fares M,Radhakrishnan S,Raghavan B,et al.Hedera:dynamic flow scheduling for data center networks[A].Proceedings of Networked System Design and Implementation[C].San Jose:NSDI,2010.19-19.

[12]Zhang-Shen R,McKeown N.Designing a predictable internet backbone with valiant load-balancing[A].Proceedings of Quality of Service-IWQoS [C].Passau:Springer,2005.178-192.

[13]Bharti S,Pattanaik K K.Dynamic distributed flow scheduling with load balancing for data center networks[J].Procedia Computer Science,2013,19(1):124-130.

[14]Bharti S,Pattanaik K K.Dynamic distributed flow scheduling for effective link utilization in data center networks[J].Journal of High Speed Networks,2014,20(1):1-10.

[15]Cui W,Qian C.Difs:Distributed flow scheduling for adaptive routing in hierarchical data center networks[J].Measurement,2014,5(1):17.

[16]程祥,張忠寶.基于粒子群優(yōu)化的虛擬網(wǎng)絡(luò)映射算法[J].電子學(xué)報,2011,39(10):2240-2244.

Cheng Xiang,Zhang Zhong-bao.Virutal network embedding based on particle swarm optimization[J].Acta Electronica Sinica,2011,39(10):240-2244.(in Chinese)

[17]Lantz B,Heller B,McKeown N.A network in a laptop:rapid prototyping for software-defined networks[A].Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks[C].New Delhi:ACM,2010.

林智華 男,1972年12月生于福建福州,現(xiàn)為福建江夏學(xué)院電子信息科學(xué)學(xué)院副教授,主要研究方向為新一代網(wǎng)絡(luò)技術(shù).

E-mail:lindiva@126.com

Data Center Network Flow Scheduling Based on DPSO Algorithm

LIN Zhi-hua1,2,GAO Wen2,WU Chun-ming2,LI Yong-yan3

(1.CollegeofElectronicsInformationEngineering,FujianJiangxiaUniversity,Fuzhou,Fujian350108,China;2.CollegeofComputerScience,ZhejiangUniversity,Hangzhou,Zhejiang310027,China；3.UniversityofShaoxingatShangyu,Shangyu,Zhejiang312300,China)

Data center networks leverage multiple parallel paths connecting end host pairs to offer high bisection bandwidth forcluster computing applications.However,state of the art flow scheduling algorithms may cause unfair link utilization and saturation of core switches,resulting in overall bandwidth loss.In the paper,we regard the flow scheduling problem as a 0-Kknapsack problem and propose a new flow scheduling algorithm named DPSOFS based on DPSO.DPSOFS formulates the position,velocity and their operation rules of particles according to Fat-Tree topology structure,and defines objective function as the difference of the number of conflict flows between two iterations.Moreover,our proposed mechanism reduces random search blindness by limiting the range of the path search.The simulation suggests that it can improve overall network bisection efficiently.

Fat-Tree；data center network；DPSO；flow scheduling

2014-11-10；

2015-03-06；責(zé)任編輯：梅志強

973計劃(No.2012CB315903)；浙江省重點科技創(chuàng)新團(tuán)隊(No.2011R50010-21)；國家科技支撐計劃(No.2014BAH24F01)；國家自然科學(xué)基金(No.61379118)

TP393

A

0372-2112 (2016)09-2197-06

??學(xué)報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.09.026