喬　焰,焦　俊,饒　元

(安徽農(nóng)業(yè)大學(xué)　信息與計(jì)算機(jī)學(xué)院，合肥　230061)

?

重力模型的數(shù)據(jù)中心網(wǎng)絡(luò)流量推理算法

喬焰,焦俊,饒?jiān)?/p>

(安徽農(nóng)業(yè)大學(xué)信息與計(jì)算機(jī)學(xué)院，合肥230061)

摘要：數(shù)據(jù)中心網(wǎng)絡(luò)是云計(jì)算等大型分布式計(jì)算服務(wù)的基礎(chǔ)，有效地設(shè)計(jì)與管理數(shù)據(jù)中心網(wǎng)絡(luò)需要遵循該網(wǎng)絡(luò)的流量特征。而目前直接對數(shù)據(jù)中心網(wǎng)絡(luò)進(jìn)行端到端地流量測量是非常困難的，間接地通過SNMP數(shù)據(jù)推理得到端到端流量的方法已在傳統(tǒng)計(jì)算機(jī)網(wǎng)絡(luò)中得到認(rèn)可，但無法直接應(yīng)用于現(xiàn)有的數(shù)據(jù)中心網(wǎng)絡(luò)。為了解決以上問題，提出一種基于重力模型的數(shù)據(jù)中心網(wǎng)絡(luò)流量推理算法，首先根據(jù)數(shù)據(jù)中心網(wǎng)絡(luò)流量的條件獨(dú)立性將網(wǎng)絡(luò)拓?fù)浞纸鉃槿舾勺蛹?，在此基礎(chǔ)上提出相關(guān)定理可準(zhǔn)確地計(jì)算出網(wǎng)絡(luò)中的粗粒度流量，最后利用重力模型和網(wǎng)絡(luò)層析技術(shù)得到細(xì)粒度端到端流量。通過與現(xiàn)有的流量推理算法SRMF和ELIA在NS3搭建的不同規(guī)模的數(shù)據(jù)中心網(wǎng)絡(luò)中做性能對比，實(shí)驗(yàn)結(jié)果表明新算法能有效地利用數(shù)據(jù)中心拓?fù)浣Y(jié)構(gòu)特點(diǎn)，在保證計(jì)算效率的前提下，將計(jì)算準(zhǔn)確度大幅提升，可滿足當(dāng)前數(shù)據(jù)中心網(wǎng)絡(luò)實(shí)時(shí)獲取端到端流量數(shù)據(jù)的需求，為今后數(shù)據(jù)中心網(wǎng)絡(luò)的設(shè)計(jì)和研究提供了重要參考依據(jù)。

關(guān)鍵詞：數(shù)據(jù)中心網(wǎng)絡(luò)；網(wǎng)絡(luò)測量；流量推理；重力模型；網(wǎng)絡(luò)層析

數(shù)據(jù)中心是云計(jì)算的核心基礎(chǔ)設(shè)施，而數(shù)據(jù)中心網(wǎng)絡(luò)是連接用于云計(jì)算的大規(guī)模服務(wù)器進(jìn)行大型分布式計(jì)算的橋梁。隨著云計(jì)算和大數(shù)據(jù)應(yīng)用的飛速發(fā)展，數(shù)據(jù)中心網(wǎng)絡(luò)已成為學(xué)術(shù)界的研究熱點(diǎn)。近幾年，眾多研究者紛紛將研究重心轉(zhuǎn)向?qū)?shù)據(jù)中心網(wǎng)絡(luò)的設(shè)計(jì)與管理，其中包括網(wǎng)絡(luò)結(jié)構(gòu)的設(shè)計(jì)[1-3]，網(wǎng)絡(luò)傳輸協(xié)議及路由策略的研究[4-5]，資源分配與負(fù)載均衡[6]，自定義網(wǎng)絡(luò)[7]，以及網(wǎng)絡(luò)能耗[8]等方面。然而，截止到目前，學(xué)者對數(shù)據(jù)中心網(wǎng)絡(luò)流量特征(包括網(wǎng)絡(luò)中端到端流量的源與宿，流量的大小等)的研究卻非常匱乏，這主要是因?yàn)椋?1)測量困難，目前在交換機(jī)上廣泛應(yīng)用的SNMP模塊僅能夠統(tǒng)計(jì)交換機(jī)轉(zhuǎn)發(fā)的總流量，無法得到流量具體的源端和目的端；(2)現(xiàn)有的流量推理方法無法直接應(yīng)用，由于數(shù)據(jù)中心網(wǎng)絡(luò)結(jié)構(gòu)的特殊性，傳統(tǒng)計(jì)算機(jī)網(wǎng)絡(luò)中的流量推理方法無法應(yīng)用于現(xiàn)有的數(shù)據(jù)中心網(wǎng)絡(luò)。

眾所周知，了解一個(gè)網(wǎng)絡(luò)的流量特征能夠?yàn)楦行У卦O(shè)計(jì)網(wǎng)絡(luò)結(jié)構(gòu)，研究傳輸策略和檢測網(wǎng)絡(luò)異常提供重要的參考條件。因此，眾多學(xué)者在致力于研究數(shù)據(jù)中心網(wǎng)絡(luò)的同時(shí)，也漸漸意識到測量數(shù)據(jù)中心網(wǎng)絡(luò)流量特征的重要性。近年來，國外一部分學(xué)者率先總結(jié)了對自己所管理數(shù)據(jù)中心網(wǎng)絡(luò)流量的典型特征[9-12]，從而為其他研究者的研究工作提供了參考。在這些文獻(xiàn)中，端到端流量的獲取是通過在交換機(jī)上部署額外的測量模塊，或者部署具有可編程能力的交換機(jī)(例如Openflow[13]) 來實(shí)現(xiàn)的，因此并不能作為一種通用的流量測量方法。然而不同數(shù)據(jù)中心網(wǎng)絡(luò)所承載的應(yīng)用各有不同，其流量特征也千差萬別，如何為眾多現(xiàn)有的數(shù)據(jù)中心網(wǎng)絡(luò)提供一種通用的流量測量方法是目前數(shù)據(jù)中心網(wǎng)絡(luò)研究領(lǐng)域亟待解決的問題。

近些年來，已有眾多研究者提出了傳統(tǒng)計(jì)算機(jī)網(wǎng)絡(luò)中的端到端流量推理技術(shù)，僅利用普通交換機(jī)上的SNMP數(shù)據(jù)即可推理得到所有的端到端流量的大小，這些方法主要分為兩大類：基于流量重力模型的流量推理技術(shù)[14-15]，以及基于網(wǎng)絡(luò)層析的流量推理技術(shù)[16-17]。S.Kandula等人在文獻(xiàn)[11]中嘗試將這兩類方法應(yīng)用在一般的數(shù)據(jù)中心網(wǎng)絡(luò)中，卻并沒有得到理想的推理結(jié)果。這是由于數(shù)據(jù)中心網(wǎng)絡(luò)中的終端是進(jìn)行海量計(jì)算的服務(wù)器，并不等同于傳統(tǒng)計(jì)算機(jī)網(wǎng)絡(luò)中的終端，因此并不能直接應(yīng)用流量重力模型；網(wǎng)絡(luò)層析技術(shù)要求網(wǎng)絡(luò)的端到端路徑盡可能少，而為了保證可靠性，數(shù)據(jù)中心網(wǎng)絡(luò)卻存在大量的冗余路徑，因此無法通過網(wǎng)絡(luò)層析的方法得到較準(zhǔn)確的計(jì)算結(jié)果。

在以上背景下，該文利用數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)渲辛髁康臈l件獨(dú)立性將網(wǎng)絡(luò)拓?fù)溥M(jìn)行了分解，并通過改進(jìn)的流量重力模型和網(wǎng)絡(luò)層析技術(shù)推理得到較準(zhǔn)確的端到端流量?？偨Y(jié)來說，本文為數(shù)據(jù)中心網(wǎng)絡(luò)的研究領(lǐng)域做了以下三點(diǎn)貢獻(xiàn)。

(1)根據(jù)數(shù)據(jù)中心網(wǎng)絡(luò)端到端流量的條件獨(dú)立性，把網(wǎng)絡(luò)拓?fù)浞纸鉃槿舾勺蛹?，并提出相關(guān)定理。通過相關(guān)定理可準(zhǔn)確計(jì)算得到網(wǎng)絡(luò)的粗粒度端到端流量。實(shí)驗(yàn)表明，數(shù)據(jù)中心網(wǎng)絡(luò)的粗粒度流量相對細(xì)粒度流量更符合流量重力模型。

(2)在相關(guān)定理的基礎(chǔ)上提出高效的端到端流量推理算法，利用粗粒度的流量重力模型將粗粒度流量特征逐步細(xì)化到所有端到端流量特征上，并通過改進(jìn)的網(wǎng)絡(luò)層析算法優(yōu)化計(jì)算結(jié)果，最終得到最近接真實(shí)情況的細(xì)粒度流量特征。

(3)用NS3搭建了較大規(guī)模和較小規(guī)模的數(shù)據(jù)中心網(wǎng)絡(luò)，并用Matlab實(shí)現(xiàn)了新算法以及基于重力模型的經(jīng)典流量推理算法Tomogravity[15]和本文作者提出的基于網(wǎng)絡(luò)層析的流量推理算法ELIA[16]，將三個(gè)算法計(jì)算得到的數(shù)據(jù)中心網(wǎng)絡(luò)端到端流量與實(shí)際產(chǎn)生的端到端流量做對比，結(jié)果表明新算法相比Tomogravity以及ELIA具有更高的計(jì)算準(zhǔn)確度和更短的計(jì)算時(shí)間。

1建模

圖1為目前應(yīng)用最廣泛的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)?，它包含三層結(jié)構(gòu)：核心交換機(jī)(Core switch)層，聚合交換機(jī)(Aggregation switch)層，以及柜頂交換機(jī)(Top of Rack switch， 或TOR switch)層，柜頂交換機(jī)又稱為TOR交換機(jī)。

SNMP是目前幾乎所有交換機(jī)普遍支持的網(wǎng)絡(luò)管理協(xié)議，也可以理解為交換機(jī)各個(gè)端口的包(或比特)的計(jì)數(shù)器。通過在不同的時(shí)間間隔(如1~30分鐘)提取交換機(jī)的SNMP數(shù)據(jù)可獲得交換機(jī)端口之間鏈路在相應(yīng)時(shí)間間隔內(nèi)所承載的總流量。本文研究的問題是：如何根據(jù)鏈路總流量計(jì)算得到每個(gè)TOR交換機(jī)之間的端到端流量。下面將把該問題轉(zhuǎn)換成數(shù)學(xué)模型中的求解線性方程組的問題。

圖1　傳統(tǒng)數(shù)據(jù)中心網(wǎng)絡(luò)架構(gòu)

假設(shè)網(wǎng)絡(luò)中共有m條鏈路，用L={l1,l2,…,lm}表示網(wǎng)絡(luò)中的鏈路，用Y={y1,y2,…,ym}表示每條鏈路所承載的流量。假設(shè)所有TOR交換機(jī)之間的總路徑個(gè)數(shù)為n，用X={x1,x2,…,xn}表示每個(gè)路徑所承載的流量。假設(shè)共測量了T個(gè)時(shí)間間隔，用t=1,2,…,T表示每個(gè)時(shí)間間隔。則xi(t)和yj(t)分別表示在第t個(gè)時(shí)間間隔內(nèi)相應(yīng)的流量。根據(jù)鏈路流量與端到端流量之間的關(guān)系，可以建立X(t)與Y(t)的線性方程組，如

Y(t)=AX(t)

(1)

其中，A={aij,1≤i≤m,1≤j≤n}為路由矩陣。矩陣中的每一行表示一條鏈路，每一列代表一個(gè)端到端路徑。當(dāng)aij=1時(shí)，表示第j個(gè)路徑經(jīng)過了第i條鏈路；相反，當(dāng)aij=0時(shí)則說明第j個(gè)路徑?jīng)]有經(jīng)過第i條鏈路。由于對大多數(shù)的網(wǎng)絡(luò)拓?fù)鋪碚f公式(1)并不滿秩，因此存在無數(shù)組解滿足此方程組。由于在數(shù)據(jù)中心網(wǎng)絡(luò)中存在大量的冗余路徑，這使得公式(1)不滿秩的情況更加嚴(yán)重。例如在圖1中，TOR層以上的鏈路總共有24條，而TOR之間的端到端路徑個(gè)數(shù)卻超過100。也就是說公式(1)存在上百個(gè)未知數(shù)，而約束條件僅有24個(gè)。當(dāng)網(wǎng)絡(luò)規(guī)模增大時(shí)，鏈路與路徑個(gè)數(shù)差也會急劇增加。因此，直接從公式(1)中求解未知數(shù)X(t)是不可取的。下一小節(jié)將提出一種數(shù)據(jù)中心網(wǎng)絡(luò)的拓?fù)浞纸夥椒?，可在一定程度上解決系統(tǒng)秩缺失的問題，從而為較準(zhǔn)確地推理得到未知數(shù)X(t)提供條件。

2網(wǎng)絡(luò)拓?fù)涞姆纸?/p>

數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)湎鄬τ谄渌?jì)算機(jī)網(wǎng)絡(luò)(如IP網(wǎng)，Internet等)，具有其獨(dú)有的特性，即網(wǎng)絡(luò)的分層結(jié)構(gòu)以及類似樹狀結(jié)構(gòu)。因此，網(wǎng)絡(luò)中的端到端流量是存在條件獨(dú)立性的：對于子集C1來說，若經(jīng)過交換機(jī)Agg1和Agg2的每個(gè)端到端流量是已知的，則所有經(jīng)過交換機(jī)TOR1～TOR4的端到端流量也是已知的。則根據(jù)交換機(jī)流量之間的條件獨(dú)立性，可將網(wǎng)絡(luò)拓?fù)浞纸鉃槿舾勺蛹＠?，對于圖1中的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)洌蓪⑵鋭澐譃?個(gè)子集C1和C2(如圖2所示)。

圖2　將圖1中的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)鋭澐譃閮蓚€(gè)子集

在網(wǎng)絡(luò)拓?fù)涞玫椒纸夂螅?jì)算TOR到TOR流量的問題可轉(zhuǎn)換成計(jì)算C1和C2之間的端到端流量，以及計(jì)算C1與C2子集內(nèi)部的端到端流量的問題。從圖2中可以看出， C1與C2之間的路徑個(gè)數(shù)為2，而兩個(gè)子集之間的鏈路個(gè)數(shù)為4，相對公式(1)，不滿秩的情況得到極大地改善。C1與C2內(nèi)部的端到端流量的計(jì)算也有相似的情況。

將拓?fù)溥M(jìn)行劃分一方面可處理端到端存在大量冗余路徑的問題，另一方面劃分子集后可根據(jù)下面提出的定理準(zhǔn)確計(jì)算出子集之間的粗粒度流量。

子集Ci內(nèi)部的總流量用Xintra(Ci)表示，從該子集流出的總流量用Xout(Ci)表示，流入該子集的流量用Xin(Ci)表示。每個(gè)TOR交換機(jī)負(fù)責(zé)本交換機(jī)下所有服務(wù)器流入和流出的流量交換，用Yout(TORi)表示TORi下所有服務(wù)器流出的流量，用Yin(TORi)表示流入TORi下所有服務(wù)器的流量。用Y(Aggi)表示經(jīng)過聚合交換機(jī)Aggi的總流量。

定理根據(jù)端到端流量的條件獨(dú)立性，可將分層的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)溥M(jìn)行劃分。其中，

(1)子集Ci內(nèi)部交換的總流量為：

(2)

(2)子集Ci流出的的總流量為：

(3)

(3) 流入子集Ci的總流量為：

(4)

證明所有流出Ci中TOR交換機(jī)的總流量可分為兩部分：一部在Ci內(nèi)部交換，另一部分流出Ci，因此有

(5)

所有流出Ci中TOR交換機(jī)的總流量也可分為兩部分：一部分來自Ci內(nèi)部TOR交換機(jī)，另一部分來自Ci外部TOR交換機(jī)，因此有

(6)

將公式(5)與公式(6)相加得到

(7)

而Ci中聚合交換機(jī)Aggi的總流量可分為三部分：Ci內(nèi)部交換的總流量、從Ci中流出的總流量、外部進(jìn)入Ci的總流量，因此有

(8)

用公式(7)減公式(8)可得到公式(2)成立。同理，用公式(8)分別減去公式(5)和公式(6)，可得到公式(3)和公式(4)成立。證畢。

粗粒度的流量特征可以為數(shù)據(jù)中心網(wǎng)絡(luò)設(shè)計(jì)提供重要參考依據(jù)：大多數(shù)數(shù)據(jù)中心網(wǎng)絡(luò)設(shè)計(jì)者傾向于將有較大流量交換需求的服務(wù)器放置在相臨位置，以減少網(wǎng)絡(luò)資源開銷。因此內(nèi)部交換總量較大的子集表明設(shè)計(jì)相對合理；若有子集長期與外界交換大量流量，而其內(nèi)部交換流量相對較少時(shí)，則表明該網(wǎng)絡(luò)設(shè)計(jì)存在改進(jìn)的空間。

3基于重力模型的流量推理算法

本節(jié)在上述定理的基礎(chǔ)上提出了一種基于重力模型的流量推理算法。與傳統(tǒng)計(jì)算機(jī)網(wǎng)的端到端流量推理算法相比，新算法將流量推理分為兩部分：子集與子集之間的端到端流量推理以及每個(gè)子集內(nèi)部的端到端流量推理。在每一步的推理中，首先根據(jù)重力模型計(jì)算出端到端流量的初始值，然后利用改進(jìn)的網(wǎng)絡(luò)層析算法將初始值優(yōu)化，從而得到最終的計(jì)算結(jié)果。

3.1網(wǎng)絡(luò)流量的重力模型

重力模型的原理是認(rèn)為質(zhì)量較大的物體具備較大的引力。網(wǎng)絡(luò)流量重力模型即假設(shè)流出(或流入)的總流量較大的節(jié)點(diǎn)所發(fā)出(或接收)流量的概率也較大[14]。根據(jù)流量重力模型原理，從第i個(gè)節(jié)點(diǎn)流向第j個(gè)節(jié)點(diǎn)的流量可表示為：

(9)

3.2子集之間的流量推理算法

從上述定理可得到每個(gè)子集流出和流入的總流量，根據(jù)流量重力模型，可通過公式(10)計(jì)算子集Ci到子集Cj的流量初始值，

(10)

在得到了子集之間流量的初始值后，可根據(jù)每個(gè)交換機(jī)上記錄的SNMP數(shù)據(jù)以及公式(1)表示的網(wǎng)絡(luò)層析方法對初始值進(jìn)行優(yōu)化，從而得到最接近真實(shí)值的一組解。

本文將初值的優(yōu)化問題建立成公式(11)所示的線性規(guī)劃模型，利用最小二乘法求解模型的最優(yōu)解。

(11)

3.3子集內(nèi)部的流量推理算法

(12)

(13)

(14)

(15)

而對于子集Ci內(nèi)部，從TORs到TORt的流量初值可用公式(16)計(jì)算，

(16)

(17)

其中ACi表示子集Ci內(nèi)的路由矩陣，Y(AggCi)和Y(TORCi)分別表示Ci內(nèi)部的聚合交換機(jī)和TOR交換機(jī)SNMP記錄的總流量。求得的最優(yōu)解Xi(TOR)即是細(xì)粒度的TOR交換機(jī)到TOR交換機(jī)之間的端到端流量。

4仿真實(shí)驗(yàn)

4.1實(shí)驗(yàn)環(huán)境設(shè)置

實(shí)驗(yàn)用NS-3構(gòu)建了兩個(gè)不同規(guī)模的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：

(1)較小規(guī)模拓?fù)?。拓?fù)渲邪?6個(gè)TOR交換機(jī)，8個(gè)聚合交換機(jī)，和4個(gè)核心交換機(jī)。每個(gè)機(jī)架下面有10臺服務(wù)器，從中隨機(jī)選擇1~5個(gè)服務(wù)器向其他所有服務(wù)器發(fā)送數(shù)據(jù)包。

(2)較大規(guī)模拓?fù)?。拓?fù)渲邪?2個(gè)TOR交換機(jī)，16個(gè)聚合交換機(jī)，和8個(gè)核心交換機(jī)。每個(gè)機(jī)架下面有20臺服務(wù)器，從中隨機(jī)選擇1~10個(gè)服務(wù)器向其他所有服務(wù)器發(fā)送數(shù)據(jù)包。

根據(jù)文獻(xiàn)[9-11]對云計(jì)算網(wǎng)絡(luò)流量特征的描述產(chǎn)生端到端流量：每條鏈路的帶寬設(shè)置為1Gbps，當(dāng)服務(wù)器向其他機(jī)架下的服務(wù)器發(fā)送數(shù)據(jù)包時(shí)，其發(fā)送的數(shù)據(jù)包個(gè)數(shù)服從對數(shù)正態(tài)分布；當(dāng)向相同機(jī)架下的服務(wù)器發(fā)送數(shù)據(jù)包時(shí)，所發(fā)送數(shù)據(jù)包的個(gè)數(shù)服從對數(shù)正態(tài)分布。每個(gè)數(shù)據(jù)包大小約1 400 個(gè)字節(jié)。端到端數(shù)據(jù)傳送采用TCP協(xié)議，路由策略采用數(shù)據(jù)中心網(wǎng)絡(luò)中最廣泛應(yīng)用的ECMP(等價(jià)多路徑路由協(xié)議)協(xié)議。采集各個(gè)交換機(jī)端口的SNMP數(shù)據(jù)的時(shí)間間隔設(shè)置為5分鐘。

4.2對比算法與衡量準(zhǔn)則

將新算法與基于流量重力模型的流量推理算法TomoGravity[14]和本文作者在文獻(xiàn)[16]提出的網(wǎng)絡(luò)層析算法ELIA作比較。并從以下兩方面來評價(jià)算法性能：(1)算法的計(jì)算準(zhǔn)確度；(2)算法的計(jì)算時(shí)間。

其中計(jì)算準(zhǔn)確度用相對誤差(RE)的累積分布函數(shù)和條件總體誤差(RMSE(τ) )來度量。相對誤差(RE)即推理得到的流量值與真實(shí)流量值之差與真實(shí)值相比，可用公式(18)來計(jì)算，

(18)

條件總體誤差(RMSE(τ))用公式(19)來計(jì)算，

(19)

算法的計(jì)算時(shí)間從輸入網(wǎng)絡(luò)拓?fù)浜蚐NMP數(shù)據(jù)開始，到算法輸出所有端到端流量為止。三個(gè)算法均用Matlab(R2012b)實(shí)現(xiàn)，運(yùn)行在本實(shí)驗(yàn)專用服務(wù)器上(6核3.2GHz處理器，16G內(nèi)存，Win7 64-bit操作系統(tǒng))。

4.3實(shí)驗(yàn)結(jié)果

圖3比較了三個(gè)算法在較小規(guī)模網(wǎng)絡(luò)中的推理準(zhǔn)確度。從圖3(a)中可以看出，新算法能將70%的推理結(jié)果控制在相對誤差0.5以內(nèi)，90%的推理結(jié)果在相對誤差1以內(nèi)，其表現(xiàn)明顯優(yōu)于Tomogravity算法和ELIA算法。在圖3(b)中，隨著τ值的增加，新算法的推理誤差緩慢下降，這也說明新算法能較準(zhǔn)確地推理出較大的端到端流量值，并且新算法推理得到的端到端流量總體誤差仍低于另外兩個(gè)算法。

圖4中三個(gè)曲線的表現(xiàn)與圖3類似，在圖4(a)中新算法能夠在較大規(guī)模的網(wǎng)絡(luò)中準(zhǔn)確計(jì)算出40%以上的端到端流量，這說明隨著網(wǎng)絡(luò)規(guī)模的增加，分解網(wǎng)絡(luò)拓?fù)淠軌蚋佑行У剌o助推理。圖4(b)中，新算法雖然在小流量的計(jì)算中總體誤差比另外兩個(gè)算法較高，但隨著τ值的增加呈較快地下降趨勢，并且τ值越大其優(yōu)勢越明顯。

(a) 相對誤差(re)的分布函數(shù)

(b) 不同τ值下算法的總體誤差

(a) 相對誤差(re)的分布函數(shù)

(b) 不同τ值下算法的總體誤差

以上實(shí)驗(yàn)結(jié)果表明，Tomogravity算法將數(shù)據(jù)中心網(wǎng)絡(luò)所有TOR交換機(jī)平等地參與重力模型的建模和計(jì)算，并不符合數(shù)據(jù)中心網(wǎng)絡(luò)流量的特點(diǎn)，因而計(jì)算準(zhǔn)確度較差；而ELIA能夠準(zhǔn)確計(jì)算部分端到端流量，因而其準(zhǔn)確度略優(yōu)于Tomogravity算法，但數(shù)據(jù)中心網(wǎng)絡(luò)的大量冗余路徑導(dǎo)致系統(tǒng)不滿秩的情況極其嚴(yán)重，因此能夠準(zhǔn)確計(jì)算出的流量個(gè)數(shù)非常有限，因而ELIA也不能達(dá)到理想的推理效果。而新算法先將數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行了分解，并初步得到準(zhǔn)確的粗粒度流量，在粗粒度流量的基礎(chǔ)上進(jìn)一步進(jìn)行重力流量模型的建模，從而能夠得到比較理想的推理結(jié)果。

表1比較了三個(gè)算法所需的計(jì)算時(shí)間。從表1可看出，本文提出的新算法相比其他兩個(gè)算法需要的計(jì)算時(shí)間更短。Tomogravity算法比本文提出的算法計(jì)算時(shí)間略長，這也說明拓?fù)浞纸夂笤诿總€(gè)子集中單獨(dú)應(yīng)用流量重力模型方法比直接應(yīng)用重力模型效率更高。而ELIA算法的計(jì)算時(shí)間最長，并且隨網(wǎng)絡(luò)規(guī)模擴(kuò)大呈較快增長，這是因?yàn)镋LIA算法在準(zhǔn)確計(jì)算一部分流量時(shí)需要近似指數(shù)級的時(shí)間復(fù)雜度。

從以上實(shí)驗(yàn)結(jié)果可得出，本文提出的新算法能夠在較短的時(shí)間內(nèi)推理得到更準(zhǔn)確的數(shù)據(jù)中心網(wǎng)絡(luò)端到端流量數(shù)據(jù)，因而能夠有效地應(yīng)用于現(xiàn)有的數(shù)據(jù)中心網(wǎng)絡(luò)。

表1　三個(gè)算法計(jì)算時(shí)間的比較

5結(jié)束語

獲取網(wǎng)絡(luò)的端到端流量對于數(shù)據(jù)中心網(wǎng)絡(luò)的設(shè)計(jì)與管理研究至關(guān)重要。直接采集端到端流量需要耗費(fèi)巨大的成本，而傳統(tǒng)網(wǎng)絡(luò)中的端到端流量推理技術(shù)無法直接應(yīng)用于現(xiàn)有的數(shù)據(jù)中心網(wǎng)絡(luò)。該文利用數(shù)據(jù)中心網(wǎng)絡(luò)的拓?fù)涮攸c(diǎn)將網(wǎng)絡(luò)劃分為若干子集，并提出本文定理計(jì)算得到粗粒度端到端流量，在此基礎(chǔ)上提出一種基于流量重力模型的高效端到端流量算法，能夠?qū)崟r(shí)準(zhǔn)確地推理計(jì)算出網(wǎng)絡(luò)中的所有端到端流量。實(shí)驗(yàn)結(jié)果表明，相比現(xiàn)有的端到端流量推理算法，新算法能夠在數(shù)據(jù)中心網(wǎng)絡(luò)中用更短的時(shí)間計(jì)算出更準(zhǔn)確的結(jié)果，能夠較好地應(yīng)用于現(xiàn)有的數(shù)據(jù)中心網(wǎng)絡(luò)中，從而為更有效地設(shè)計(jì)和管理數(shù)據(jù)中心網(wǎng)絡(luò)提供了重要參考。

參考文獻(xiàn)：

[1]Akella A,Benson T,Chandrasekaran B,et al.A Universal Approach to Data Center Network Design [C]//Proceedings of ACM International Conference on Distributed Computing and Networking (ICDCN),Goa,India,2015：41-46.

[2]朱桂明，謝向輝，郭得科等.一種高吞吐量、高可擴(kuò)展數(shù)據(jù)中心網(wǎng)絡(luò)結(jié)構(gòu)[J].軟件學(xué)報(bào),2014 ,25 (6): 1399-1351.

[3]Li D,Wu J.On the Design and Analysis of Data Center Network Architectures for Interconnecting Dual-port Servers [C]//Proceedings of IEEE INFOCOM,Toronto,ONT,CA,2014:1851-1859.

[4]Curtis A R,Kim W,Yalagandula P.Mahout: Low-overhead Datacenter Traffic Management Using End-host-based Elephant Detection [C]//Proc.of IEEE INFOCOM,Shanghai,China,2011:1629-1637.

[5]高飛.數(shù)據(jù)中心網(wǎng)絡(luò)迂回路由方法的研究[D].北京:北京交通大學(xué)計(jì)算機(jī)學(xué)院,2015.

[6]Belabed D,Secci S,Pujolle G,et al.On Traffic Fairness in Data Center Fabrics [C]//Procof IEEE CloudNet,Luxembourg,2014:40-45.

[7]Malboubi M,Wang L,Chuah C N,et al.Intelligent SDN Based Traffic (de)Aggregation and Measurement Paradigm (iSTAMP) [C]//Proceedings of IEEE INFOCOM,Toronto,CA,2014:934-942.

[8]羅亮，吳文峻，張飛.面向云計(jì)算數(shù)據(jù)中心的能耗建模方法[J].軟件學(xué)報(bào),2014(7): 1371-1387.

[9]Benson T,Akella A,Maltz D A.Network Traffic Characteristics of Data Centers in the Wild [C]//Procof ACM IMC,Melbourne,Australia,2010:267-280.

[10] BENSON T，ANAND A，AKELLA A，et al. Understanding Data Center Traffic Characteristics [C]//Proceedings of ACM SIGCOMM，New Delhi,2010：245-253．

[11] Kandula S,Sengupta S,Greenberg A.The Nature of Data Center Traffic: Measurements & Analysis [C]//Procof ACM IMC,Chicago,Illinois,2009:202-208.

[12] Hu Z,Qiao Y,Luo J.CREATE: CoRrelation Enhanced Traffic MaTrix Estimation in Data Center Networks [C]//Procof IFIP Networing,Trondheim,Norway,2014:1-9.

[13] Lara A,Kolasani A,Ramamurthy B.Network Innovation Using Openflow: A survey [J].Communications Surveys & Tutorials,IEEE,2014,16(1): 493-512.

[14] Zhang Y,Roughan M,Duffield N.Fast Accurate Computation of Large-scale IP Traffic Matrices from Link Loads [C]//Procof ACM SIGMETRICS,California,USA,2003:206-217.

[15] Roughan M,Zhang Y,Willinger W,et al.Spatio-temporal Compressive Sensing and Internet Traffic Matrices (extended version)[J].Networking,IEEE/ACM Transactions on,2012,20(3): 662-676.

[16] Qiao Yan,Qiu Xuesong,Meng Luoming.Efficient Loss Inference Algorithm Using Unicast End-to-End Measurements [J].Journal of Network and Systems Management,2013,21(2): 169-193.

[17] Nie L,Jiang D.A Compressive Sensing-based Network Tomography Approach to Estimating Origin-destination Flow Traffic in Large-scale Backbone Networks [J].International Journal of Communication Systems,2015,28(5):889-900.

[責(zé)任編輯：張永軍]

Traffic Inference for Data Center Network Base on Gravity Model

QIAO Yan,JIAO Jun,RAO Yuan

(School of Information and Computer, Anhui Agricultural University, Hefei 230061,China)

Abstract:Data Center Network (DCN) is the infrastructure of cloud computing and other distributed computing services. Understanding the characteristics of end-to-end traffic flows in DCNs is essential to DCN designs and operations.However,it is extremely difficult to measure the traffic flows directly.Inferring the end-to-end traffic follows from the SNMP counters on switches has been widely applied in traditional computer networks.But it still can not be utilized in DCNs directly yet.To address this problem,we propose an efficient traffic inference algorithm for DCNs based on gravity traffic model.It first decomposes the DCNs into several clusters according to the feature of conditional independence of DCN traffic,and then computers the coarse-grained traffic of each cluster based on some theorem that we state in section 3.Finally it utilizes the gravity traffic model and network tomography to refine the traffic on each cluster to obtain the fine-grained end-to-end traffic.We compare our new proposal with two classical traffic inference algorithms SRMF and ELIA on different scale of DCNs.The results show that our new algorithm outperforms the other two algorithms in both speed and accuracy.Thus the new proposal can provide vital reference to the area of DCN designs and operations.

Key words:datacenter Networks; Network measurement; traffic inference; traffic gravity model; Network tomography

中圖分類號：TN915.07

文獻(xiàn)標(biāo)識碼：A

文章編號：1673-162X(2016)01-0052-08

作者簡介：喬焰(1984—),女, 山東聊城人，安徽農(nóng)業(yè)大學(xué)信息與計(jì)算機(jī)學(xué)院講師，博士；研究方向：計(jì)算機(jī)網(wǎng)絡(luò)管理、網(wǎng)絡(luò)性能測量。

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61402013、61203217)、安徽省教育廳自然科學(xué)基金項(xiàng)目(KJ2014A074)、安徽省科技廳國際合作項(xiàng)目(1403062031)、安徽省經(jīng)信委財(cái)政專項(xiàng)資金項(xiàng)目(財(cái)企(2013) 1162)資助。

收稿日期：2015-10-10修回日期：2015-12-12