数据中心网络结构鲁棒性指标及研究

张婵，冯国军，肖云波

（湘潭职业技术学院，湖南　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.