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

屈 曉,劉 海

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

1 引言

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

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

2 分簇聚類算法設計

2.1 數(shù)據(jù)中心拓撲結(jié)構(gòu)

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

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

(1)

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

(2)

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

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

2.2 流量信息檢測

(3)

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

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

(4)

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

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

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

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

c=u+b

(5)

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

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

u=J(c,?)

(6)

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

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

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

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

(7)

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

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

1)前向傳播階段

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

(8)

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

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

(9)

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

2)反向傳播階段

可用誤差更新輸出層在多層感知機中的權(quán)重,隱層在多層感知機中不存在誤差,因此無法直接將梯度下降法應用在隱層中,通過反向傳播在鏈式法則的基礎上將誤差傳播到隱層,再采用上述方法展開處理。

設R代表的是多層感知機的均方誤差,可通過下式計算得到

(10)

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

(11)

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

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

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

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

(12)

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

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

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

(13)

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

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

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

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

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

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

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

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

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

(14)

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

2)調(diào)度約束

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

(15)

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

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

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

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

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

3 實驗與分析

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

表1 實驗參數(shù)

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

圖2 流量分布情況

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

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

由圖3可知,所提方法可將數(shù)據(jù)中心中存在大象流和老鼠流分為兩個簇,而文獻[3]算法和文獻[4]方法無法精準地將大象流和老鼠流分簇,驗證了所提算法具有較高的分簇精度,因為所提算法對數(shù)據(jù)中心流量分簇處理之前,采用多層感知機對流量數(shù)據(jù)展開了去噪處理,在此基礎上,分簇聚類流量數(shù)據(jù),提高了流量數(shù)據(jù)的分簇精度。

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

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

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

4 結(jié)束語

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