張嬋，馮國(guó)軍，肖云波

（湘潭職業(yè)技術(shù)學(xué)院，湖南　411102）

數(shù)據(jù)中心網(wǎng)絡(luò)結(jié)構(gòu)魯棒性指標(biāo)及研究

張嬋，馮國(guó)軍，肖云波

（湘潭職業(yè)技術(shù)學(xué)院，湖南411102）

0　引言

近年來，隨著云計(jì)算和數(shù)據(jù)密集型計(jì)算技術(shù)的飛速發(fā)展，數(shù)據(jù)中心網(wǎng)絡(luò)（DCN）作為底層基礎(chǔ)設(shè)施發(fā)揮了越來越重要的作用，越來越多的應(yīng)用構(gòu)建于數(shù)據(jù)中心網(wǎng)絡(luò)之上。然而網(wǎng)絡(luò)在運(yùn)行中經(jīng)常會(huì)受到干擾或破壞，從而導(dǎo)致其性能降低，一個(gè)小的網(wǎng)絡(luò)性能下降可能導(dǎo)致巨大損失。據(jù)谷歌數(shù)據(jù)統(tǒng)計(jì)，當(dāng)響應(yīng)時(shí)間額外延遲500毫秒將導(dǎo)致20%的收入損失；Amazon的數(shù)據(jù)也指出搜索結(jié)果額外延遲100毫秒將造成1%的銷售額下降［1］。2012年英國(guó)電信運(yùn)營(yíng)商因O2網(wǎng)絡(luò)的一個(gè)小故障就影響了約700萬(wàn)客戶；黑莓的網(wǎng)絡(luò)核心交換機(jī)故障導(dǎo)致了數(shù)百萬(wàn)的客戶三天不能訪問互聯(lián)網(wǎng)。由此可知網(wǎng)絡(luò)的魯棒性是確保云計(jì)算的性能和服務(wù)質(zhì)量達(dá)到預(yù)期水平的關(guān)鍵，所以研究并量化數(shù)據(jù)中心網(wǎng)絡(luò)的魯棒性顯得尤為重要。

網(wǎng)絡(luò)（或也稱為拓?fù)浣Y(jié)構(gòu)）的魯棒性是指當(dāng)網(wǎng)絡(luò)中的一個(gè)或多個(gè)組件故障時(shí)，網(wǎng)絡(luò)提供預(yù)期的性能水平的能力。網(wǎng)絡(luò)的魯棒性，在文獻(xiàn)［2-5，9-11］被廣泛討論，主要針對(duì)傳統(tǒng)的隨機(jī)網(wǎng)絡(luò)。然而，DCN與傳統(tǒng)的隨機(jī)網(wǎng)絡(luò)存在各種差異，如異構(gòu)性、多層圖模型和連接方式等。目前，針對(duì)數(shù)據(jù)中心網(wǎng)絡(luò)的魯棒性度量還未有充分研究，本文以數(shù)據(jù)中心網(wǎng)絡(luò)的魯棒性為主要研究?jī)?nèi)容，對(duì)3種典型的DCN架構(gòu)（ThreeTier、FatTree和DCell）進(jìn)行建模，并在不考慮網(wǎng)絡(luò)故障的前提下，對(duì)其魯棒性進(jìn)行分析比較。

1　種典型的DCN架構(gòu)

本文主要對(duì)ThreeTier架構(gòu)、FatTree架構(gòu)和DCell架構(gòu)3種典型DCN結(jié)構(gòu)進(jìn)行魯棒性分析。

1.1TbreeTien

ThreeTier是最常用的DCN架構(gòu)［6］，它是以交換機(jī)為中心的，網(wǎng)絡(luò)設(shè)備由三層構(gòu)成：①接入層，②匯聚層，③核心層。接入層交換機(jī)向下連接著幾十或上百臺(tái)服務(wù)器，向上則連接著多個(gè)匯聚層交換機(jī)，核心層交換機(jī)用來連接所有的匯聚層交換機(jī)。

1.2FatTree

Al-Fares等人提出了Fat-Tree結(jié)構(gòu)［7］。Fat-Tree結(jié)構(gòu)被分為k個(gè)pod，每個(gè)pod中包含一個(gè)兩層交換機(jī)結(jié)構(gòu)，一層為聚合層，一層為邊緣層。每層有k/2個(gè)交換機(jī)，每個(gè)交換機(jī)的端口數(shù)為k，邊緣層的交換機(jī)與底層的k/2個(gè)服務(wù)器連接，剩余的k/2個(gè)端口與聚合層的k/2個(gè)交換機(jī)連接，即邊緣層和聚合層的網(wǎng)絡(luò)設(shè)備之間實(shí)現(xiàn)全互聯(lián)。在核心層有（k/2）2個(gè)包含k個(gè)端口的核心交換機(jī)，每個(gè)核心交換機(jī)的k個(gè)端口分別連接k個(gè)pogd。

1.3DCell

Guo等人提出一種基于層次化全連接的DCell拓?fù)浣Y(jié)構(gòu)［8］。DCell使用遞歸方式定義，高層的DCell網(wǎng)絡(luò)由多個(gè)低層DCell網(wǎng)絡(luò)組成，此時(shí)將低層DCell網(wǎng)絡(luò)看做高層網(wǎng)絡(luò)的一個(gè)虛擬節(jié)點(diǎn)，則同一層的所有節(jié)點(diǎn)之間實(shí)現(xiàn)全連接結(jié)構(gòu)。DCell網(wǎng)絡(luò)最底層（DCell0）由n個(gè)服務(wù)器與一個(gè)n口普通交換機(jī)連接構(gòu)成，n+1個(gè)DCell0網(wǎng)絡(luò)構(gòu)成DCell1網(wǎng)絡(luò)，依次類推，若DCellk中有m個(gè)服務(wù)器，則DCellk+1是一個(gè)由m+1個(gè)DCellk互連形成的完全復(fù)合圖。

2　數(shù)據(jù)中心網(wǎng)絡(luò)模型

Kurant和Thiran提出了一個(gè)通用的多層圖模型［9］。作者將網(wǎng)絡(luò)定義為兩層:

物理層圖表示較低層拓?fù)洌壿媽訄D表示上層拓?fù)浣Y(jié)構(gòu)，每條邏輯邊eλ都在物理層中映射為一條路徑M（eλ）?g。因?yàn)閷訑?shù)是固定的，該模型并不適用于DCN架構(gòu)。此外，DCN中沒有邏輯層，所以，將一個(gè)層映射到另一層的想法是無法用來描述DCN的。

Dong等人［10］中定義了一個(gè)多層圖g，由M層構(gòu)成，每個(gè)層表示一個(gè)無向加權(quán)圖。因?yàn)槊繉拥墓?jié)點(diǎn)數(shù)需要相同，所以也不適用于DCN。此外，這個(gè)定義缺乏不同層之間的互連信息。因?yàn)榍懊嫣岢龅膱D的模型不適用于DCN，我們?yōu)槊糠NDCN架構(gòu)建立了其相應(yīng)的圖模型。

表1 DCN模型中各種標(biāo)記的定義

2.ThreeTierDON架構(gòu)

根據(jù)表1將ThreeTier結(jié)構(gòu)的圖模型定義為：

其中v表示節(jié)點(diǎn)，ε表示邊。

根據(jù)表1中的定義，得出每個(gè)pod中節(jié)點(diǎn)數(shù)：

由公式（5）得到拓?fù)涞墓?jié)點(diǎn)總數(shù)為：

令ξ表示服務(wù)器連接到接入層的邊集，α＇表示接入層連接到匯聚層的邊集，ζ表示匯聚層連接到核心層的邊集，Υ表示pod中匯聚層交換機(jī)之間互連的邊集，ThreeTier架構(gòu)的邊集為：

2.2FatTreeDON架構(gòu)

類似于ThreeTier，F(xiàn)atTree架構(gòu)也由單層計(jì)算服務(wù)器和三層網(wǎng)絡(luò)交換機(jī)組成，因?yàn)樗捎昧薈los拓?fù)浣Y(jié)構(gòu)［26］，網(wǎng)絡(luò)元素的數(shù)量和相互連接的邊數(shù)比ThreeTier架構(gòu)多得多。

FatTree架構(gòu)的圖模型描述為：

根據(jù)公式（10）得出總的邊數(shù)為：

因?yàn)槊總€(gè)Pi中每層的元素的個(gè)數(shù)基于k是固定的，n，m，q，r可表示為：

2.3DCell DCN架構(gòu)

DCell采用遞歸的方式，dcelll由xidcellsl-1構(gòu)成。在dcell0中，一個(gè)交換機(jī)連接所有服務(wù)器。DCell架構(gòu)的圖模型可以描述為：

其中0≤i≤l，?0代表dcell0，?l表示dcelll。設(shè)δ表示dcell0中的服務(wù)器集，s0表示中的服務(wù)器個(gè)數(shù)，sl表示dcelll中服務(wù)器個(gè)數(shù)，α表示dcell0中連接s0個(gè)服務(wù)器的交換機(jī)，xl是?l中?l-1的個(gè)數(shù)，由此推出：

DCell是一個(gè)高度可擴(kuò)展性的架構(gòu)，且支持任何層級(jí)的DCell。具有1層的DCell的節(jié)點(diǎn)數(shù)為：

具有1層的DCell的總鏈路數(shù)為：

具有3層的DCell就能容納數(shù)百萬(wàn)的服務(wù)器。3層的DCell中的節(jié)點(diǎn)數(shù)：

3層的DCell鏈路數(shù)為：

3　魯棒性指標(biāo)

本文中我們采用基于圖論的經(jīng)典魯棒性指標(biāo)來量化數(shù)據(jù)中心網(wǎng)絡(luò)的魯棒性，下面簡(jiǎn)單描述一下魯棒性指標(biāo)。

同配系數(shù)（Assortativity coefficient（r））［5］：描述網(wǎng)絡(luò)中的節(jié)點(diǎn)和與其度相同的節(jié)點(diǎn)連接的傾向性。若r＞0，網(wǎng)絡(luò)是同配的，表示節(jié)點(diǎn)傾向于和其度相同的節(jié)點(diǎn)連接；若r＜0表示網(wǎng)絡(luò)是異配的。

節(jié)點(diǎn)平均度（Average nodal degree（＜k＞））［5］：是指網(wǎng)絡(luò)中所有節(jié)點(diǎn)度的平均值，是一種粗糙的魯棒性評(píng)價(jià)指標(biāo)，k值越大網(wǎng)絡(luò)的魯棒性越高。

平均最短路徑長(zhǎng)度（Average shortest path length（＜l＞））：網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間的最短路徑的平均值［4］。＜l＞值越小魯棒性越高。

平均鄰居連接數(shù)（Average neighbor connectivity給定度節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的平均度。值提供聯(lián)合度分布統(tǒng)計(jì)，并被計(jì)為平均度為k的節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的平均度。

聚集系數(shù)（Clustering coefficient（＜C＞））［5］：刻畫網(wǎng)絡(luò)的聚類特性，0≤C≤1。如果節(jié)點(diǎn)v1連接于節(jié)點(diǎn)v2，節(jié)點(diǎn)v2連接于節(jié)點(diǎn)v3，那么節(jié)點(diǎn)v3很可能與v1相連接。

介數(shù)中心性（Betweenness centrality（＜b＞））：假設(shè)網(wǎng)絡(luò)中的信息總是選擇通過最短路徑進(jìn)行傳遞，那么經(jīng)過某個(gè)節(jié)點(diǎn)的最短路徑的數(shù)目就可以描述該節(jié)點(diǎn)在信息傳播方面的繁忙程度，同時(shí)也體現(xiàn)了該節(jié)點(diǎn)能直接控制的信息傳播量。這種刻畫了節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)傳播信息的控制能力的指標(biāo)就稱為介數(shù)中心性［11］，經(jīng)常用于估計(jì)節(jié)點(diǎn)/鏈路的信譽(yù)。

直徑（Diameter（D））［12］：網(wǎng)絡(luò)中所有最短路徑中最長(zhǎng)的路徑，一般來說，D值越小魯棒性越高。

節(jié)點(diǎn)連通性（Node connectivity（k））［2］：節(jié)點(diǎn)連通性是網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間的節(jié)點(diǎn)不相交路徑的最小數(shù)量，在應(yīng)對(duì)任何故障或攻擊（隨機(jī)或目標(biāo)）情況下，它提供了一個(gè)粗糙的網(wǎng)絡(luò)魯棒性指標(biāo)。該定義也同樣適應(yīng)于鏈路連通性ρ。

4　DCN的魯棒性分析

本節(jié)中，我們采用六個(gè)具有代表性的拓?fù)浣Y(jié)構(gòu)：

3個(gè)大型網(wǎng)絡(luò)（DCell30K，F(xiàn)atTree30K，ThreeTier30K）。

3個(gè)小型網(wǎng)絡(luò)（DCell2K，F(xiàn)atTree2K，ThreeTier2K）。

DCell拓?fù)渲性黾右慌_(tái)服務(wù)器就能以指數(shù)方式擴(kuò)展網(wǎng)絡(luò)。令dcell0中的服務(wù)器個(gè)數(shù)為2，則具有3層的DCell可容納2709個(gè)節(jié)點(diǎn)；令dcell0的服務(wù)器數(shù)量增加到3時(shí)，則網(wǎng)絡(luò)能容納32656個(gè)節(jié)點(diǎn)。因此，考慮2 k 和30 k的網(wǎng)絡(luò)拓?fù)洹?/p>

表2描述了三個(gè)大型網(wǎng)絡(luò)的一些特性。如表所示，所有的拓?fù)浣Y(jié)構(gòu)都有30000個(gè)以上的節(jié)點(diǎn)。FatTree30K的鏈路數(shù)最多。FatTree30K的密度大約是ThreeTier30K的3倍。鏈路數(shù)以及密度的值越大，魯棒性就越高。FatTree30K和ThreeTier30K中的平均最短路徑長(zhǎng)度的值＜l＞小于6，而DCell30K有更高的路徑長(zhǎng)度11。＜l＞值越大意味著DCell30K中的終端主機(jī)之間的通信比FatTree30K或ThreeTier30K更容易受到故障的影響，因?yàn)檫@樣的通信將被路由（平均）通過一個(gè)較長(zhǎng)的路徑，一個(gè)路徑中的鏈接和節(jié)點(diǎn)的數(shù)目越高，受故障影響的概率越高。同樣，DCell30K直徑D的值約是FatTree30K和ThreeTier30K的4倍。然而，DCell30K具有較高的平均節(jié)點(diǎn)度＜k＞說明對(duì)于故障的應(yīng)變能力強(qiáng)。此外，這三個(gè)大型網(wǎng)絡(luò)都是異構(gòu)的，因?yàn)閞＜0。

表2 30K DCN拓?fù)涮匦?/p>

表3 2K DCN拓?fù)涮匦?/p>

表4 2K DCN拓?fù)涮匦?/p>

表3、表4描述了3個(gè)小型網(wǎng)絡(luò)的拓?fù)涮匦浴Ｃ總€(gè)拓?fù)浣Y(jié)構(gòu)由大約2500到2700個(gè)節(jié)點(diǎn)構(gòu)成。正如前面30k網(wǎng)絡(luò)中，F(xiàn)atTree架構(gòu)同樣擁有最多的鏈路數(shù)。此外，所有的網(wǎng)絡(luò)節(jié)點(diǎn)和鏈路的連通性的最小值分別是k=1和ρ=1。k和ρ這樣的值，表明單個(gè)節(jié)點(diǎn)或鏈路故障會(huì)導(dǎo)致網(wǎng)絡(luò)分割。DCell2K因?yàn)榫哂凶畹偷膶?duì)稱比值其魯棒性則更高。由表3可知，F(xiàn)atTree2K和 ThreeTier2K較之DCell2K有較低的平均最短路徑長(zhǎng)度，因而魯棒性更高。DCell2K的介數(shù)中心性＜b＞值較大，個(gè)別節(jié)點(diǎn)的＜b＞值具有最小標(biāo)準(zhǔn)偏差。因此，可以推斷出，DCell2K中所有的節(jié)點(diǎn)有相似的介數(shù)中心值。另外，F(xiàn)atTree2K和ThreeTier2K中的＜b＞值低于DCell2K，但它有更高的標(biāo)準(zhǔn)偏差。聚類系數(shù)＜C＞測(cè)量顯示，DCell2K在鄰居節(jié)點(diǎn)發(fā)生故障的情況下缺乏兩跳路徑重路由流量，相反，F(xiàn)atTree2K和ThreeTier2K因具有較高的＜C＞值，表現(xiàn)出更好的魯棒性，說明了多個(gè)可供選擇的兩跳路徑的存在性。此外，這三個(gè)小型網(wǎng)絡(luò)都是異構(gòu)的，因?yàn)閞＜0。測(cè)試表明FatTree2K最稠密，魯棒性最好。

在不考慮網(wǎng)絡(luò)故障的前提下，通過對(duì)DCN拓?fù)涞聂敯粜苑治霭l(fā)現(xiàn)，沒有一個(gè)網(wǎng)絡(luò)可以被認(rèn)為是符合所有指標(biāo)的最健壯的架構(gòu)。針對(duì)各種指標(biāo)量化DCN的魯棒性的結(jié)果見表5，最、中和低描述網(wǎng)絡(luò)的魯棒性水平。從表中可以得出FatTree架構(gòu)針對(duì)大部分指標(biāo)表現(xiàn)出最高的魯棒性。因此，在沒有考慮網(wǎng)絡(luò)故障的情況下，基于最初的網(wǎng)絡(luò)分析FatTree比ThreeTier和DCell架構(gòu)具有更好的魯棒性。

表5三種DCN架構(gòu)的魯棒性比較

5　結(jié)語(yǔ)

本文中，我們根據(jù)經(jīng)典的魯棒性指標(biāo)度量了3種典型數(shù)據(jù)中心網(wǎng)絡(luò)（DCN）架構(gòu)的魯棒性。研究結(jié)果顯示，在不考慮所有的故障類型情況下，與DCell和ThreeTier架構(gòu)相比，F(xiàn)atTree架構(gòu)的魯棒性最高。在后續(xù)的研究工作中我們將研究在所有故障類型情況下，數(shù)據(jù)中心網(wǎng)絡(luò)的魯棒性。

［1］A.Greenberg，J.Hamilton，D.Maltz，P.Patel.The cost of a cloud:research problems in data center networks.ACM SIGCOMM Computer Comm.Rev.，2009，39（1）：68-79.

［2］A.H.Dekker，B.D.Colbert.Network robustness and graph topology.Proc.27th Australasian Conf.Computer Science，2004：359-368.

［3］A.H.Dekker，B.D.Colbert.The Symmetry Ratio of a Network.Proc.Australasian Symp.Theory of Computing，2005：13-20.

［4］C.Shannon，D.Moore.The spread of the witty worm.IEEE Security and Privacy，2004，2（4）：46-50，July.

［5］P.Mahadevan，D.Krioukov，M.Fomenkov，X.Dimitropoulos，K.C.Claffy，A.Vahdat.The Internet AS-Level Topology:Three Data Sources and One Definitive Metric.SIGCOMM Computer Comm.Rev.，vol.36，pp.17-26，Jan.2006.

［6］Cisco Data Center Infrastructure 2.5 Design Guide，Cisco，2010.

［7］M.Al-Fares，A.Loukissas，A.Vahdat.A scalable，commodity data center network architecture.ACM SIGCOMM Computer Comm. Rev.，2008，38（4）：63-74.

［8］C.Guo，H.Wu，K.Tan，L.Shi，Y.Zhang，S.Lu.DCell:A scalable and fault-tolerant network structure for data centers.SIGCOMM Computer Comm.Rev.，2008，38（4）：75-86.

［9］D.Chakrabarti，Y.Wang，C.Wang，J.Leskovec，C.Faloutsos.Epidemic thresholds in real networks.ACM Trans.Information and System Security，2008，10（4）：1-26.

［10］A.Jamakovic，S.Uhlig.Influence of the network structure on robustness.Proc.15th IEEE Int'l Conf.Networks（ICON'07），2007：278-2837.

［11］L.C.Freeman.A set of measures of centrality based upon betweenness.Sociometry，1977，40（1）：35-41.

［12］E.Weisstein，http://mathworld.wolfram.com/GraphDiameter.html，2013.

Data Center Network；Structural Robustness；Network Analysis；Multilayer Graphs Model

Research on Indices of DCN Structural Robustness

ZHANG Chan，F(xiàn)ENG Guo-jun，XIAO Yun-bo
（Xiangtan Vocational&Technical College，Hunan 411102）

1007-1423（2015）29-0030-06

10.3969/j.issn.1007-1423.2015.29.008

張嬋（1979-），女，湖南湘潭人，碩士，講師，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)

肖云波（1981-），女，講師，研究方向?yàn)榫W(wǎng)絡(luò)安全

馮國(guó)軍（1965-），男，高級(jí)工程師，研究方向?yàn)檐浖_發(fā)、計(jì)算機(jī)網(wǎng)絡(luò)

2015-08-27

2015-09-27

近年來，隨著云計(jì)算和數(shù)據(jù)密集型計(jì)算技術(shù)的飛速發(fā)展，數(shù)據(jù)中心網(wǎng)絡(luò)（DCN）作為底層基礎(chǔ)設(shè)施發(fā)揮著越來越重要的作用。DCN需要在面對(duì)故障和不確定性因素下具備良好的魯棒性，以提供所需的服務(wù)質(zhì)量（QoS）水平和滿足服務(wù)水平協(xié)議（SLA）。分別對(duì)3種典型的DCNS構(gòu)建了多層圖模型，并研究經(jīng)典的魯棒性指標(biāo)，在不考慮各種故障情況下進(jìn)行比較分析。目前，還沒有詳細(xì)的研究可定性DCN的魯棒性，因此，這項(xiàng)研究將為未來魯棒性研究提供理論依據(jù)。

數(shù)據(jù)中心網(wǎng)絡(luò)；結(jié)構(gòu)魯棒性；網(wǎng)絡(luò)分析；多層圖模型

In recent years，with the rapid development of Cloud Computing and Data-Intensive Super Computing（DISC），Data Center Network（DCN）is playing an increasingly important roles as the underlying infrastructure.The DCN needs to be robust to failures and uncertainties to deliver the required Quality-of-Service（QoS）level and satisfy service-level agreement（SLA）.Presents multilayered graph modeling of various DCNs，and Studies the classical robustness metrics performing a comparative analysis（for the whole network without failures）. Currently，there is no detailed study available centering the DCN robustness.Therefore，we believe that this study will provide a theoretical basis for the future DCN robustness research.