數據中心網絡結構魯棒性指標及研究

張嬋，馮國軍，肖云波

（湘潭職業技術學院，湖南　411102）

數據中心網絡結構魯棒性指標及研究

張嬋，馮國軍，肖云波

（湘潭職業技術學院，湖南411102）

0　引言

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

網絡（或也稱為拓撲結構）的魯棒性是指當網絡中的一個或多個組件故障時，網絡提供預期的性能水平的能力。網絡的魯棒性，在文獻［2-5，9-11］被廣泛討論，主要針對傳統的隨機網絡。然而，DCN與傳統的隨機網絡存在各種差異，如異構性、多層圖模型和連接方式等。目前，針對數據中心網絡的魯棒性度量還未有充分研究，本文以數據中心網絡的魯棒性為主要研究內容，對3種典型的DCN架構（ThreeTier、FatTree和DCell）進行建模，并在不考慮網絡故障的前提下，對其魯棒性進行分析比較。

1　種典型的DCN架構

本文主要對ThreeTier架構、FatTree架構和DCell架構3種典型DCN結構進行魯棒性分析。

1.1TbreeTien

ThreeTier是最常用的DCN架構［6］，它是以交換機為中心的，網絡設備由三層構成：①接入層，②匯聚層，③核心層。接入層交換機向下連接著幾十或上百臺服務器，向上則連接著多個匯聚層交換機，核心層交換機用來連接所有的匯聚層交換機。

1.2FatTree

Al-Fares等人提出了Fat-Tree結構［7］。Fat-Tree結構被分為k個pod，每個pod中包含一個兩層交換機結構，一層為聚合層，一層為邊緣層。每層有k/2個交換機，每個交換機的端口數為k，邊緣層的交換機與底層的k/2個服務器連接，剩余的k/2個端口與聚合層的k/2個交換機連接，即邊緣層和聚合層的網絡設備之間實現全互聯。在核心層有（k/2）2個包含k個端口的核心交換機，每個核心交換機的k個端口分別連接k個pogd。

1.3DCell

Guo等人提出一種基于層次化全連接的DCell拓撲結構［8］。DCell使用遞歸方式定義，高層的DCell網絡由多個低層DCell網絡組成，此時將低層DCell網絡看做高層網絡的一個虛擬節點，則同一層的所有節點之間實現全連接結構。DCell網絡最底層（DCell0）由n個服務器與一個n口普通交換機連接構成，n+1個DCell0網絡構成DCell1網絡，依次類推，若DCellk中有m個服務器，則DCellk+1是一個由m+1個DCellk互連形成的完全復合圖。

2　數據中心網絡模型

Kurant和Thiran提出了一個通用的多層圖模型［9］。作者將網絡定義為兩層:

物理層圖表示較低層拓撲，邏輯層圖表示上層拓撲結構，每條邏輯邊eλ都在物理層中映射為一條路徑M（eλ）?g。因為層數是固定的，該模型并不適用于DCN架構。此外，DCN中沒有邏輯層，所以，將一個層映射到另一層的想法是無法用來描述DCN的。

Dong等人［10］中定義了一個多層圖g，由M層構成，每個層表示一個無向加權圖。因為每層的節點數需要相同，所以也不適用于DCN。此外，這個定義缺乏不同層之間的互連信息。因為前面提出的圖的模型不適用于DCN，我們為每種DCN架構建立了其相應的圖模型。

表1 DCN模型中各種標記的定義

2.ThreeTierDON架構

根據表1將ThreeTier結構的圖模型定義為：

其中v表示節點，ε表示邊。

根據表1中的定義，得出每個pod中節點數：

由公式（5）得到拓撲的節點總數為：

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

2.2FatTreeDON架構

類似于ThreeTier，FatTree架構也由單層計算服務器和三層網絡交換機組成，因為它采用了Clos拓撲結構［26］，網絡元素的數量和相互連接的邊數比ThreeTier架構多得多。

FatTree架構的圖模型描述為：

根據公式（10）得出總的邊數為：

因為每個Pi中每層的元素的個數基于k是固定的，n，m，q，r可表示為：

2.3DCell DCN架構

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

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

DCell是一個高度可擴展性的架構，且支持任何層級的DCell。具有1層的DCell的節點數為：

具有1層的DCell的總鏈路數為：

具有3層的DCell就能容納數百萬的服務器。3層的DCell中的節點數：

3層的DCell鏈路數為：

3　魯棒性指標

本文中我們采用基于圖論的經典魯棒性指標來量化數據中心網絡的魯棒性，下面簡單描述一下魯棒性指標。

同配系數（Assortativity coefficient（r））［5］：描述網絡中的節點和與其度相同的節點連接的傾向性。若r＞0，網絡是同配的，表示節點傾向于和其度相同的節點連接；若r＜0表示網絡是異配的。

節點平均度（Average nodal degree（＜k＞））［5］：是指網絡中所有節點度的平均值，是一種粗糙的魯棒性評價指標，k值越大網絡的魯棒性越高。

平均最短路徑長度（Average shortest path length（＜l＞））：網絡中所有節點對之間的最短路徑的平均值［4］。＜l＞值越小魯棒性越高。

平均鄰居連接數（Average neighbor connectivity給定度節點的鄰居節點的平均度。值提供聯合度分布統計，并被計為平均度為k的節點的鄰居節點的平均度。

聚集系數（Clustering coefficient（＜C＞））［5］：刻畫網絡的聚類特性，0≤C≤1。如果節點v1連接于節點v2，節點v2連接于節點v3，那么節點v3很可能與v1相連接。

介數中心性（Betweenness centrality（＜b＞））：假設網絡中的信息總是選擇通過最短路徑進行傳遞，那么經過某個節點的最短路徑的數目就可以描述該節點在信息傳播方面的繁忙程度，同時也體現了該節點能直接控制的信息傳播量。這種刻畫了節點對網絡傳播信息的控制能力的指標就稱為介數中心性［11］，經常用于估計節點/鏈路的信譽。

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

節點連通性（Node connectivity（k））［2］：節點連通性是網絡中任意兩個節點之間的節點不相交路徑的最小數量，在應對任何故障或攻擊（隨機或目標）情況下，它提供了一個粗糙的網絡魯棒性指標。該定義也同樣適應于鏈路連通性ρ。

4　DCN的魯棒性分析

本節中，我們采用六個具有代表性的拓撲結構：

3個大型網絡（DCell30K，FatTree30K，ThreeTier30K）。

3個小型網絡（DCell2K，FatTree2K，ThreeTier2K）。

DCell拓撲中增加一臺服務器就能以指數方式擴展網絡。令dcell0中的服務器個數為2，則具有3層的DCell可容納2709個節點；令dcell0的服務器數量增加到3時，則網絡能容納32656個節點。因此，考慮2 k 和30 k的網絡拓撲。

表2描述了三個大型網絡的一些特性。如表所示，所有的拓撲結構都有30000個以上的節點。FatTree30K的鏈路數最多。FatTree30K的密度大約是ThreeTier30K的3倍。鏈路數以及密度的值越大，魯棒性就越高。FatTree30K和ThreeTier30K中的平均最短路徑長度的值＜l＞小于6，而DCell30K有更高的路徑長度11。＜l＞值越大意味著DCell30K中的終端主機之間的通信比FatTree30K或ThreeTier30K更容易受到故障的影響，因為這樣的通信將被路由（平均）通過一個較長的路徑，一個路徑中的鏈接和節點的數目越高，受故障影響的概率越高。同樣，DCell30K直徑D的值約是FatTree30K和ThreeTier30K的4倍。然而，DCell30K具有較高的平均節點度＜k＞說明對于故障的應變能力強。此外，這三個大型網絡都是異構的，因為r＜0。

表2 30K DCN拓撲特性

表3 2K DCN拓撲特性

表4 2K DCN拓撲特性

表3、表4描述了3個小型網絡的拓撲特性。每個拓撲結構由大約2500到2700個節點構成。正如前面30k網絡中，FatTree架構同樣擁有最多的鏈路數。此外，所有的網絡節點和鏈路的連通性的最小值分別是k=1和ρ=1。k和ρ這樣的值，表明單個節點或鏈路故障會導致網絡分割。DCell2K因為具有最低的對稱比值其魯棒性則更高。由表3可知，FatTree2K和 ThreeTier2K較之DCell2K有較低的平均最短路徑長度，因而魯棒性更高。DCell2K的介數中心性＜b＞值較大，個別節點的＜b＞值具有最小標準偏差。因此，可以推斷出，DCell2K中所有的節點有相似的介數中心值。另外，FatTree2K和ThreeTier2K中的＜b＞值低于DCell2K，但它有更高的標準偏差。聚類系數＜C＞測量顯示，DCell2K在鄰居節點發生故障的情況下缺乏兩跳路徑重路由流量，相反，FatTree2K和ThreeTier2K因具有較高的＜C＞值，表現出更好的魯棒性，說明了多個可供選擇的兩跳路徑的存在性。此外，這三個小型網絡都是異構的，因為r＜0。測試表明FatTree2K最稠密，魯棒性最好。

在不考慮網絡故障的前提下，通過對DCN拓撲的魯棒性分析發現，沒有一個網絡可以被認為是符合所有指標的最健壯的架構。針對各種指標量化DCN的魯棒性的結果見表5，最、中和低描述網絡的魯棒性水平。從表中可以得出FatTree架構針對大部分指標表現出最高的魯棒性。因此，在沒有考慮網絡故障的情況下，基于最初的網絡分析FatTree比ThreeTier和DCell架構具有更好的魯棒性。

表5三種DCN架構的魯棒性比較

5　結語

本文中，我們根據經典的魯棒性指標度量了3種典型數據中心網絡（DCN）架構的魯棒性。研究結果顯示，在不考慮所有的故障類型情況下，與DCell和ThreeTier架構相比，FatTree架構的魯棒性最高。在后續的研究工作中我們將研究在所有故障類型情況下，數據中心網絡的魯棒性。

［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，FENG 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-），女，湖南湘潭人，碩士，講師，研究方向為計算機網絡

肖云波（1981-），女，講師，研究方向為網絡安全

馮國軍（1965-），男，高級工程師，研究方向為軟件開發、計算機網絡

2015-08-27

2015-09-27

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

數據中心網絡；結構魯棒性；網絡分析；多層圖模型

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.