數(shù)據(jù)中心流量調(diào)度的分簇聚類算法仿真

屈 曉,劉 海

(1. 華南農(nóng)業(yè)大學(xué)珠江學(xué)院,廣東 廣州 510900;2. 華南師范大學(xué)計(jì)算機(jī)學(xué)院,廣東 廣州 510631)

1 引言

數(shù)據(jù)中心網(wǎng)絡(luò)中的流量傳輸與普通應(yīng)用中數(shù)據(jù)流傳輸?shù)男枨蟛煌?主要體現(xiàn)在截止時(shí)間、傳輸速率和響應(yīng)速度等方面[1-2]。傳輸故障和網(wǎng)絡(luò)擁塞是數(shù)據(jù)中心面臨的主要問(wèn)題,當(dāng)數(shù)據(jù)中心出現(xiàn)上述問(wèn)題時(shí)數(shù)據(jù)流的傳輸無(wú)法得到保障。因此,需要對(duì)數(shù)據(jù)中心流量調(diào)度算法展開分析和研究。

尹長(zhǎng)川[3]等人首先計(jì)算數(shù)據(jù)中心的最小時(shí)隙,根據(jù)計(jì)算結(jié)果對(duì)數(shù)據(jù)中心的采樣周期展開調(diào)整,將流偏移規(guī)劃算法應(yīng)用在奇偶映射方案中完成流量調(diào)度。該方法無(wú)法有效分類數(shù)據(jù)中心中存在的流量的類型,存在分簇精度低的問(wèn)題。馬樞清[4]等人首先分析了數(shù)據(jù)中心的拓?fù)浣Y(jié)構(gòu),根據(jù)數(shù)據(jù)中心網(wǎng)絡(luò)流量帶寬和鏈路帶寬資源建立流量調(diào)度目標(biāo)函數(shù),采用粒子群算法對(duì)函數(shù)求解,獲得數(shù)據(jù)中心流量的最佳調(diào)度路徑。該方法無(wú)法在規(guī)定時(shí)間內(nèi)完成流量的調(diào)度,且調(diào)度速率無(wú)法得到保障。為了解決上述方法中存在的問(wèn)題,提出面向數(shù)據(jù)中心流量調(diào)度的分簇聚類算法。

2 分簇聚類算法設(shè)計(jì)

2.1 數(shù)據(jù)中心拓?fù)浣Y(jié)構(gòu)

用十元組描述數(shù)據(jù)中心U

U=(F,V,C,Q,B,A1,A2,A,I,N)

(1)

式中,N表示網(wǎng)絡(luò)帶寬;F表示數(shù)據(jù)集合,由f個(gè)設(shè)備中的數(shù)據(jù)構(gòu)成;I表示任務(wù)類型矩陣;V表示物理云節(jié)點(diǎn);A表示節(jié)點(diǎn)執(zhí)行任務(wù)時(shí)的功率集合;C表示虛擬機(jī)設(shè)備;A1表示節(jié)點(diǎn)峰值狀態(tài)下的功率集合;A2表示節(jié)點(diǎn)空閑狀態(tài)下的功率集合;集合Q由用戶命令構(gòu)成;B表示節(jié)點(diǎn)與任務(wù)塊之間對(duì)應(yīng)的矩陣,其表達(dá)式如下

(2)

式中,bmn表示虛擬機(jī)中任務(wù)塊ti產(chǎn)生的執(zhí)行結(jié)果。

在云計(jì)算服務(wù)和網(wǎng)絡(luò)架構(gòu)的基礎(chǔ)上調(diào)整數(shù)據(jù)中心的拓?fù)浣Y(jié)構(gòu),調(diào)整云節(jié)點(diǎn)中存在的流量,避免數(shù)據(jù)中心出現(xiàn)流量擁塞問(wèn)題。

2.2 流量信息檢測(cè)

(3)

當(dāng)鏈路帶寬小于鏈路負(fù)載時(shí),流量在數(shù)據(jù)中心會(huì)發(fā)生擁塞現(xiàn)象,降低鏈路在數(shù)據(jù)中心中的利用率[5-6]。

設(shè)Nw(rxy)代表鏈路負(fù)載,Nu(rxy)代表鏈路利用率,其計(jì)算公式分別如下

(4)

式中,Dx表示鏈路端口在數(shù)據(jù)中心中發(fā)送的字節(jié)數(shù);Nc(rxy)表示鏈路傳輸帶寬,即容量;Tx表示鏈路端口在數(shù)據(jù)中心中接收的字節(jié)數(shù)。

鏈路在其利用率Nu(rxy)高于0.9或負(fù)載Nw(rxy)高于門限值時(shí)會(huì)出現(xiàn)擁塞現(xiàn)象,需要對(duì)流量展開調(diào)度。

2.3 數(shù)據(jù)中心流量去噪

用c表示數(shù)據(jù)中心內(nèi)的流量數(shù)據(jù),其表達(dá)式如下

c=u+b

(5)

式中,b表示噪聲;u表示不存在噪聲的流量數(shù)據(jù)。

在多層感知機(jī)中,輸入含噪的流量數(shù)據(jù)c,輸出不存在噪聲的流量數(shù)據(jù)u,兩者之間的關(guān)系可通過(guò)下式描述

u=J(c,?)

(6)

式中,?表示由多層感知機(jī)參數(shù)構(gòu)成的集合;J表示多層感知機(jī)的網(wǎng)絡(luò)結(jié)構(gòu)。數(shù)據(jù)中心流量的去噪過(guò)程可以描述為在較少噪聲的流量中映射存在噪聲的流量,因此,需要建立多層感知機(jī)模型用于表示上述映射關(guān)系。

多層感知機(jī)由隱層、輸出層和輸入層構(gòu)成,其中輸入層不存在計(jì)算內(nèi)容,只負(fù)責(zé)接收流量數(shù)據(jù)[7-8],按照權(quán)重大小將流量數(shù)據(jù)傳輸?shù)诫[層中,隱層建立了非線性激活函數(shù),主要用于處理流量數(shù)據(jù),并將處理結(jié)果傳輸?shù)蕉鄬痈兄獧C(jī)的輸出層中,獲得數(shù)據(jù)中心流量的去噪結(jié)果。

設(shè)置激活函數(shù)s,用g(x)表示多層感知機(jī),其表達(dá)式如下

g(x)=n2+E2s(n1+E1c)

(7)

式中,n1、n2表示偏置矩陣;E1、E2表示權(quán)重矩陣。

通過(guò)網(wǎng)絡(luò)流量對(duì)多層感知機(jī)的參數(shù)展開調(diào)節(jié),當(dāng)多層感知機(jī)的輸出接近不存在噪聲的網(wǎng)絡(luò)流量時(shí),完成多層感知機(jī)的訓(xùn)練。多層感知機(jī)的訓(xùn)練需要多次循環(huán),每次訓(xùn)練都存在兩個(gè)階段,分別是前向傳播階段和反向傳播階段,通過(guò)梯度下降方法[9-10]對(duì)多層感知機(jī)的參數(shù)展開調(diào)節(jié)。

1)前向傳播階段

用βj表示第j個(gè)神經(jīng)元在多層感知機(jī)隱層中收到的輸入,其表達(dá)式如下

(8)

式中,ck表示神經(jīng)元的數(shù)據(jù)分量;ekj表示不同神經(jīng)元在不同層次中的連接權(quán)重。

在隱層中采用Sigmoid激活函數(shù)處理數(shù)據(jù)βj,并向輸出層傳送處理結(jié)果,用χi表示第i個(gè)神經(jīng)元在多層感知機(jī)輸出層中收到的輸入,其表達(dá)式如下

(9)

式中,bji表示輸出層第i個(gè)神經(jīng)元與隱層神經(jīng)元之間的權(quán)重。通過(guò)上述過(guò)程,獲得多層感知機(jī)的輸出u′=[χ1,χ2,…,χm]T。

2)反向傳播階段

可用誤差更新輸出層在多層感知機(jī)中的權(quán)重,隱層在多層感知機(jī)中不存在誤差,因此無(wú)法直接將梯度下降法應(yīng)用在隱層中,通過(guò)反向傳播在鏈?zhǔn)椒▌t的基礎(chǔ)上將誤差傳播到隱層,再采用上述方法展開處理。

設(shè)R代表的是多層感知機(jī)的均方誤差,可通過(guò)下式計(jì)算得到

(10)

式中,ui表示第i個(gè)神經(jīng)元在輸出層的數(shù)據(jù)分量。在梯度下降策略的基礎(chǔ)上誤差逆?zhèn)鞑ニ惴ㄍㄟ^(guò)下式調(diào)整權(quán)重

(11)

式中,ι存在于區(qū)間(0,1)內(nèi),表示學(xué)習(xí)率。

2.4 基于K-means的流量分簇聚類

面向數(shù)據(jù)中心流量調(diào)度的分簇聚類算法采用K-means算法[11-12]對(duì)數(shù)據(jù)中心的流量展開聚類優(yōu)化處理,具體過(guò)程如下:

1)設(shè)置數(shù)據(jù)集F,由網(wǎng)絡(luò)流量構(gòu)成,通過(guò)下述公式獲得流量包在F中對(duì)應(yīng)的樣本點(diǎn)分布密度g(i)以及距離因子均值Fis：

(12)

式中,n表示流量包的數(shù)量;h(xi,xj)表示度量因子。

2)設(shè)置數(shù)據(jù)集S,初始聚類中心選取g(i)值最大的流量包s1,將其存儲(chǔ)到S中,當(dāng)流量包與s1之間的距離因子小于距離因子均值Fis時(shí),在集合F中剔除該流量包;

3)針對(duì)集合F中剩余的流量包,用λ表示其最大分布密度乘積,可通過(guò)下式計(jì)算得到

(13)

式中,?(i)表示距離因子均值;f(xi,xj)表示距離度量因子。根據(jù)上式計(jì)算結(jié)果,第二個(gè)流量聚類中心s2選取最大λ對(duì)應(yīng)的點(diǎn)i,并在數(shù)據(jù)集S中記錄聚類中心s2,按照相同的方式剔除數(shù)據(jù)集F中的一部分流量包樣本點(diǎn)。

4)計(jì)算流量包樣本點(diǎn)s1、s2在數(shù)據(jù)集F中的最大分布密度乘積λ,選擇最大λ對(duì)應(yīng)的樣本點(diǎn)i作為第三個(gè)流量數(shù)據(jù)的聚類中心s3,將其存儲(chǔ)在數(shù)據(jù)集F中,同理,刪除部分流量包樣本點(diǎn)。

5)按照相同的方式選取聚類中心,在數(shù)據(jù)中心中獲得流量數(shù)據(jù)的K個(gè)聚類中心。

6)通過(guò)上述過(guò)程確定聚類中心和初始聚類中心,完成數(shù)據(jù)中心流量的分簇聚類。

2.5 調(diào)度路徑確定

根據(jù)網(wǎng)絡(luò)流量的聚類結(jié)果,在調(diào)度過(guò)程中選取互相覆蓋的多條大象流作為目標(biāo),分析數(shù)據(jù)中心的結(jié)構(gòu)特點(diǎn),當(dāng)目的主機(jī)與源主機(jī)不在相同區(qū)域內(nèi)時(shí),兩者之間存在K2/4條流量調(diào)度路徑,在上述路徑中選取流量數(shù)據(jù)傳輸調(diào)度的最優(yōu)路徑。在相同區(qū)域內(nèi),面向數(shù)據(jù)中心流量調(diào)度的分簇聚類算法采用分簇聚合交換機(jī)調(diào)度目的主機(jī)與源主機(jī)中存在的流量數(shù)據(jù),獲得K/2條流量數(shù)據(jù)的調(diào)度路徑。

2.6 數(shù)據(jù)中心流量調(diào)度

1)網(wǎng)絡(luò)帶寬分配

數(shù)據(jù)中心網(wǎng)絡(luò)帶寬的分配結(jié)果體現(xiàn)在鏈路在數(shù)據(jù)中心中的擁塞程度,通過(guò)下式描述數(shù)據(jù)中心分配網(wǎng)絡(luò)帶寬的過(guò)程[13-14]

(14)

式中,γk表示數(shù)據(jù)中心預(yù)設(shè)的優(yōu)先級(jí);X表示物理鏈路在數(shù)據(jù)中心中的最大帶寬。

2)調(diào)度約束

用戶的網(wǎng)絡(luò)接口速度在數(shù)據(jù)中心流量調(diào)度過(guò)程中是存在一定限制的,約束條件如下

(15)

式中,Bi表示數(shù)據(jù)中心需要傳輸?shù)牧髁繑?shù)據(jù)量;Li表示判斷系數(shù),其主要目的是判斷虛擬機(jī)中節(jié)點(diǎn)是否存在任務(wù)傳輸請(qǐng)求。

3)流量分類調(diào)度

按照流量數(shù)據(jù)聚類結(jié)果,以及流量傳輸對(duì)數(shù)據(jù)中心鏈路的質(zhì)量要求,確定不同流量簇集在數(shù)據(jù)中心中的優(yōu)先等級(jí)[15],對(duì)其展開調(diào)度處理,如圖1所示。

圖1 數(shù)據(jù)中心流量調(diào)度

圖1中ni表示網(wǎng)絡(luò)流量聚類后的簇集,在數(shù)據(jù)中心中劃分網(wǎng)絡(luò)流量,獲得G1、G2、G3三條流量。當(dāng)流量在路徑中出現(xiàn)負(fù)載現(xiàn)象時(shí),可利用數(shù)據(jù)中心中存在的其它路徑調(diào)度該條路徑中存在的流量數(shù)據(jù),實(shí)現(xiàn)數(shù)據(jù)中心的流量調(diào)度。

3 實(shí)驗(yàn)與分析

為了驗(yàn)證面向數(shù)據(jù)中心流量調(diào)度的分簇聚類算法的整體有效性,需要對(duì)其展開測(cè)試。本次測(cè)試的數(shù)據(jù)中心相關(guān)參數(shù)如表1所示。

表1 實(shí)驗(yàn)參數(shù)

流量在數(shù)據(jù)中心中的分布情況如圖2所示。

圖2 流量分布情況

圖2中的方框?qū)儆诶鲜罅?淺色圓球?qū)儆诖笙罅鳌８鶕?jù)圖2可知,大象流和老鼠流混合分布在數(shù)據(jù)中心中,現(xiàn)采用面向數(shù)據(jù)中心流量調(diào)度的分簇聚類算法、文獻(xiàn)[3]算法、文獻(xiàn)[4]算法對(duì)數(shù)據(jù)中心展開流量分簇處理,分簇結(jié)果如圖3所示。

圖3 不同方法的流量分簇結(jié)果

由圖3可知,所提方法可將數(shù)據(jù)中心中存在大象流和老鼠流分為兩個(gè)簇,而文獻(xiàn)[3]算法和文獻(xiàn)[4]方法無(wú)法精準(zhǔn)地將大象流和老鼠流分簇,驗(yàn)證了所提算法具有較高的分簇精度,因?yàn)樗崴惴▽?duì)數(shù)據(jù)中心流量分簇處理之前,采用多層感知機(jī)對(duì)流量數(shù)據(jù)展開了去噪處理,在此基礎(chǔ)上,分簇聚類流量數(shù)據(jù),提高了流量數(shù)據(jù)的分簇精度。

在數(shù)據(jù)中心中存在不同優(yōu)先級(jí)的流量包,需要優(yōu)先調(diào)度優(yōu)先級(jí)高的流量包,在本次測(cè)試過(guò)程中設(shè)置三個(gè)等級(jí)的流量包,優(yōu)先級(jí)按照從大到小的排序?yàn)榱髁堪?、流量包2、流量包3。將流量包1的傳輸時(shí)間設(shè)置為10s,流量包2的傳輸時(shí)間設(shè)置為20s,流量包3的傳輸時(shí)間設(shè)置為15s,現(xiàn)采用所提算法、文獻(xiàn)[3]算法和文獻(xiàn)[4]算法對(duì)三種流量包展開調(diào)度,調(diào)度結(jié)果如圖4所示。

圖4 不同算法的流量調(diào)度結(jié)果

分析圖4可知,采用所提算法展開調(diào)度時(shí),該算法根據(jù)流量包的優(yōu)先級(jí)對(duì)流量包展開調(diào)度,并且調(diào)度三個(gè)流量包的速率相同,表明所提方法具有較高的穩(wěn)定性,采用文獻(xiàn)[3]算法和文獻(xiàn)[4]算法調(diào)度流量包1花費(fèi)了20s,表明這兩種算法無(wú)法在規(guī)定時(shí)間內(nèi)完成流量包的調(diào)度,且調(diào)度流量包的速率存在差異,表明以上兩種算法的調(diào)度效果較差。

4 結(jié)束語(yǔ)

在網(wǎng)絡(luò)流量不斷增加的背景下,人們對(duì)數(shù)據(jù)中心的流量調(diào)度提出了更高的要求。目前流量調(diào)度方法存在分簇精度低和調(diào)度效果差的問(wèn)題,提出面向數(shù)據(jù)中心流量調(diào)度的分簇聚類算法,該算法在流量調(diào)度過(guò)程中消除了流量數(shù)據(jù)中存在的噪聲,并對(duì)流量展開了分簇處理,在此基礎(chǔ)上,完成數(shù)據(jù)中心的流量調(diào)度,經(jīng)實(shí)驗(yàn)驗(yàn)證可知,所提算法可有效避免數(shù)據(jù)中心出現(xiàn)擁塞現(xiàn)象。