重力模型的数据中心网络流量推理算法

乔　焰,焦　俊,饶　元

(安徽农业大学　信息与计算机学院，合肥　230061)



重力模型的数据中心网络流量推理算法

乔焰,焦俊,饶元

(安徽农业大学信息与计算机学院，合肥230061)

摘要：数据中心网络是云计算等大型分布式计算服务的基础，有效地设计与管理数据中心网络需要遵循该网络的流量特征。而目前直接对数据中心网络进行端到端地流量测量是非常困难的，间接地通过SNMP数据推理得到端到端流量的方法已在传统计算机网络中得到认可，但无法直接应用于现有的数据中心网络。为了解决以上问题，提出一种基于重力模型的数据中心网络流量推理算法，首先根据数据中心网络流量的条件独立性将网络拓扑分解为若干子集，在此基础上提出相关定理可准确地计算出网络中的粗粒度流量，最后利用重力模型和网络层析技术得到细粒度端到端流量。通过与现有的流量推理算法SRMF和ELIA在NS3搭建的不同规模的数据中心网络中做性能对比，实验结果表明新算法能有效地利用数据中心拓扑结构特点，在保证计算效率的前提下，将计算准确度大幅提升，可满足当前数据中心网络实时获取端到端流量数据的需求，为今后数据中心网络的设计和研究提供了重要参考依据。

关键词：数据中心网络；网络测量；流量推理；重力模型；网络层析

数据中心是云计算的核心基础设施，而数据中心网络是连接用于云计算的大规模服务器进行大型分布式计算的桥梁。随着云计算和大数据应用的飞速发展，数据中心网络已成为学术界的研究热点。近几年，众多研究者纷纷将研究重心转向对数据中心网络的设计与管理，其中包括网络结构的设计[1-3]，网络传输协议及路由策略的研究[4-5]，资源分配与负载均衡[6]，自定义网络[7]，以及网络能耗[8]等方面。然而，截止到目前，学者对数据中心网络流量特征(包括网络中端到端流量的源与宿，流量的大小等)的研究却非常匮乏，这主要是因为：(1)测量困难，目前在交换机上广泛应用的SNMP模块仅能够统计交换机转发的总流量，无法得到流量具体的源端和目的端；(2)现有的流量推理方法无法直接应用，由于数据中心网络结构的特殊性，传统计算机网络中的流量推理方法无法应用于现有的数据中心网络。

众所周知，了解一个网络的流量特征能够为更有效地设计网络结构，研究传输策略和检测网络异常提供重要的参考条件。因此，众多学者在致力于研究数据中心网络的同时，也渐渐意识到测量数据中心网络流量特征的重要性。近年来，国外一部分学者率先总结了对自己所管理数据中心网络流量的典型特征[9-12]，从而为其他研究者的研究工作提供了参考。在这些文献中，端到端流量的获取是通过在交换机上部署额外的测量模块，或者部署具有可编程能力的交换机(例如Openflow[13]) 来实现的，因此并不能作为一种通用的流量测量方法。然而不同数据中心网络所承载的应用各有不同，其流量特征也千差万别，如何为众多现有的数据中心网络提供一种通用的流量测量方法是目前数据中心网络研究领域亟待解决的问题。

近些年来，已有众多研究者提出了传统计算机网络中的端到端流量推理技术，仅利用普通交换机上的SNMP数据即可推理得到所有的端到端流量的大小，这些方法主要分为两大类：基于流量重力模型的流量推理技术[14-15]，以及基于网络层析的流量推理技术[16-17]。S.Kandula等人在文献[11]中尝试将这两类方法应用在一般的数据中心网络中，却并没有得到理想的推理结果。这是由于数据中心网络中的终端是进行海量计算的服务器，并不等同于传统计算机网络中的终端，因此并不能直接应用流量重力模型；网络层析技术要求网络的端到端路径尽可能少，而为了保证可靠性，数据中心网络却存在大量的冗余路径，因此无法通过网络层析的方法得到较准确的计算结果。

在以上背景下，该文利用数据中心网络拓扑中流量的条件独立性将网络拓扑进行了分解，并通过改进的流量重力模型和网络层析技术推理得到较准确的端到端流量。总结来说，本文为数据中心网络的研究领域做了以下三点贡献。

(1)根据数据中心网络端到端流量的条件独立性，把网络拓扑分解为若干子集，并提出相关定理。通过相关定理可准确计算得到网络的粗粒度端到端流量。实验表明，数据中心网络的粗粒度流量相对细粒度流量更符合流量重力模型。

(2)在相关定理的基础上提出高效的端到端流量推理算法，利用粗粒度的流量重力模型将粗粒度流量特征逐步细化到所有端到端流量特征上，并通过改进的网络层析算法优化计算结果，最终得到最近接真实情况的细粒度流量特征。

(3)用NS3搭建了较大规模和较小规模的数据中心网络，并用Matlab实现了新算法以及基于重力模型的经典流量推理算法Tomogravity[15]和本文作者提出的基于网络层析的流量推理算法ELIA[16]，将三个算法计算得到的数据中心网络端到端流量与实际产生的端到端流量做对比，结果表明新算法相比Tomogravity以及ELIA具有更高的计算准确度和更短的计算时间。

1建模

图1为目前应用最广泛的数据中心网络拓扑，它包含三层结构：核心交换机(Core switch)层，聚合交换机(Aggregation switch)层，以及柜顶交换机(Top of Rack switch， 或TOR switch)层，柜顶交换机又称为TOR交换机。

SNMP是目前几乎所有交换机普遍支持的网络管理协议，也可以理解为交换机各个端口的包(或比特)的计数器。通过在不同的时间间隔(如1~30分钟)提取交换机的SNMP数据可获得交换机端口之间链路在相应时间间隔内所承载的总流量。本文研究的问题是：如何根据链路总流量计算得到每个TOR交换机之间的端到端流量。下面将把该问题转换成数学模型中的求解线性方程组的问题。

图1　传统数据中心网络架构

假设网络中共有m条链路，用L={l1,l2,…,lm}表示网络中的链路，用Y={y1,y2,…,ym}表示每条链路所承载的流量。假设所有TOR交换机之间的总路径个数为n，用X={x1,x2,…,xn}表示每个路径所承载的流量。假设共测量了T个时间间隔，用t=1,2,…,T表示每个时间间隔。则xi(t)和yj(t)分别表示在第t个时间间隔内相应的流量。根据链路流量与端到端流量之间的关系，可以建立X(t)与Y(t)的线性方程组，如

Y(t)=AX(t)

(1)

其中，A={aij,1≤i≤m,1≤j≤n}为路由矩阵。矩阵中的每一行表示一条链路，每一列代表一个端到端路径。当aij=1时，表示第j个路径经过了第i条链路；相反，当aij=0时则说明第j个路径没有经过第i条链路。由于对大多数的网络拓扑来说公式(1)并不满秩，因此存在无数组解满足此方程组。由于在数据中心网络中存在大量的冗余路径，这使得公式(1)不满秩的情况更加严重。例如在图1中，TOR层以上的链路总共有24条，而TOR之间的端到端路径个数却超过100。也就是说公式(1)存在上百个未知数，而约束条件仅有24个。当网络规模增大时，链路与路径个数差也会急剧增加。因此，直接从公式(1)中求解未知数X(t)是不可取的。下一小节将提出一种数据中心网络的拓扑分解方法，可在一定程度上解决系统秩缺失的问题，从而为较准确地推理得到未知数X(t)提供条件。

2网络拓扑的分解

数据中心网络拓扑相对于其他计算机网络(如IP网，Internet等)，具有其独有的特性，即网络的分层结构以及类似树状结构。因此，网络中的端到端流量是存在条件独立性的：对于子集C1来说，若经过交换机Agg1和Agg2的每个端到端流量是已知的，则所有经过交换机TOR1～TOR4的端到端流量也是已知的。则根据交换机流量之间的条件独立性，可将网络拓扑分解为若干子集。例如，对于图1中的数据中心网络拓扑，可将其划分为2个子集C1和C2(如图2所示)。

图2　将图1中的数据中心网络拓扑划分为两个子集

在网络拓扑得到分解后，计算TOR到TOR流量的问题可转换成计算C1和C2之间的端到端流量，以及计算C1与C2子集内部的端到端流量的问题。从图2中可以看出， C1与C2之间的路径个数为2，而两个子集之间的链路个数为4，相对公式(1)，不满秩的情况得到极大地改善。C1与C2内部的端到端流量的计算也有相似的情况。

将拓扑进行划分一方面可处理端到端存在大量冗余路径的问题，另一方面划分子集后可根据下面提出的定理准确计算出子集之间的粗粒度流量。

子集Ci内部的总流量用Xintra(Ci)表示，从该子集流出的总流量用Xout(Ci)表示，流入该子集的流量用Xin(Ci)表示。每个TOR交换机负责本交换机下所有服务器流入和流出的流量交换，用Yout(TORi)表示TORi下所有服务器流出的流量，用Yin(TORi)表示流入TORi下所有服务器的流量。用Y(Aggi)表示经过聚合交换机Aggi的总流量。

定理根据端到端流量的条件独立性，可将分层的数据中心网络拓扑进行划分。其中，

(1)子集Ci内部交换的总流量为：

(2)

(2)子集Ci流出的的总流量为：

(3)

(3) 流入子集Ci的总流量为：

(4)

证明所有流出Ci中TOR交换机的总流量可分为两部分：一部在Ci内部交换，另一部分流出Ci，因此有

(5)

所有流出Ci中TOR交换机的总流量也可分为两部分：一部分来自Ci内部TOR交换机，另一部分来自Ci外部TOR交换机，因此有

(6)

将公式(5)与公式(6)相加得到

(7)

而Ci中聚合交换机Aggi的总流量可分为三部分：Ci内部交换的总流量、从Ci中流出的总流量、外部进入Ci的总流量，因此有

(8)

用公式(7)减公式(8)可得到公式(2)成立。同理，用公式(8)分别减去公式(5)和公式(6)，可得到公式(3)和公式(4)成立。证毕。

粗粒度的流量特征可以为数据中心网络设计提供重要参考依据：大多数数据中心网络设计者倾向于将有较大流量交换需求的服务器放置在相临位置，以减少网络资源开销。因此内部交换总量较大的子集表明设计相对合理；若有子集长期与外界交换大量流量，而其内部交换流量相对较少时，则表明该网络设计存在改进的空间。

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

本节在上述定理的基础上提出了一种基于重力模型的流量推理算法。与传统计算机网的端到端流量推理算法相比，新算法将流量推理分为两部分：子集与子集之间的端到端流量推理以及每个子集内部的端到端流量推理。在每一步的推理中，首先根据重力模型计算出端到端流量的初始值，然后利用改进的网络层析算法将初始值优化，从而得到最终的计算结果。

3.1网络流量的重力模型

重力模型的原理是认为质量较大的物体具备较大的引力。网络流量重力模型即假设流出(或流入)的总流量较大的节点所发出(或接收)流量的概率也较大[14]。根据流量重力模型原理，从第i个节点流向第j个节点的流量可表示为：

(9)

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

从上述定理可得到每个子集流出和流入的总流量，根据流量重力模型，可通过公式(10)计算子集Ci到子集Cj的流量初始值，

(10)

在得到了子集之间流量的初始值后，可根据每个交换机上记录的SNMP数据以及公式(1)表示的网络层析方法对初始值进行优化，从而得到最接近真实值的一组解。

本文将初值的优化问题建立成公式(11)所示的线性规划模型，利用最小二乘法求解模型的最优解。

(11)

3.3子集内部的流量推理算法

(12)

(13)

(14)

(15)

而对于子集Ci内部，从TORs到TORt的流量初值可用公式(16)计算，

(16)

(17)

其中ACi表示子集Ci内的路由矩阵，Y(AggCi)和Y(TORCi)分别表示Ci内部的聚合交换机和TOR交换机SNMP记录的总流量。求得的最优解Xi(TOR)即是细粒度的TOR交换机到TOR交换机之间的端到端流量。

4仿真实验

4.1实验环境设置

实验用NS-3构建了两个不同规模的数据中心网络拓扑结构：

(1)较小规模拓扑。拓扑中包含16个TOR交换机，8个聚合交换机，和4个核心交换机。每个机架下面有10台服务器，从中随机选择1~5个服务器向其他所有服务器发送数据包。

(2)较大规模拓扑。拓扑中包含32个TOR交换机，16个聚合交换机，和8个核心交换机。每个机架下面有20台服务器，从中随机选择1~10个服务器向其他所有服务器发送数据包。

根据文献[9-11]对云计算网络流量特征的描述产生端到端流量：每条链路的带宽设置为1Gbps，当服务器向其他机架下的服务器发送数据包时，其发送的数据包个数服从对数正态分布；当向相同机架下的服务器发送数据包时，所发送数据包的个数服从对数正态分布。每个数据包大小约1 400 个字节。端到端数据传送采用TCP协议，路由策略采用数据中心网络中最广泛应用的ECMP(等价多路径路由协议)协议。采集各个交换机端口的SNMP数据的时间间隔设置为5分钟。

4.2对比算法与衡量准则

将新算法与基于流量重力模型的流量推理算法TomoGravity[14]和本文作者在文献[16]提出的网络层析算法ELIA作比较。并从以下两方面来评价算法性能：(1)算法的计算准确度；(2)算法的计算时间。

其中计算准确度用相对误差(RE)的累积分布函数和条件总体误差(RMSE(τ) )来度量。相对误差(RE)即推理得到的流量值与真实流量值之差与真实值相比，可用公式(18)来计算，

(18)

条件总体误差(RMSE(τ))用公式(19)来计算，

(19)

算法的计算时间从输入网络拓扑和SNMP数据开始，到算法输出所有端到端流量为止。三个算法均用Matlab(R2012b)实现，运行在本实验专用服务器上(6核3.2GHz处理器，16G内存，Win7 64-bit操作系统)。

4.3实验结果

图3比较了三个算法在较小规模网络中的推理准确度。从图3(a)中可以看出，新算法能将70%的推理结果控制在相对误差0.5以内，90%的推理结果在相对误差1以内，其表现明显优于Tomogravity算法和ELIA算法。在图3(b)中，随着τ值的增加，新算法的推理误差缓慢下降，这也说明新算法能较准确地推理出较大的端到端流量值，并且新算法推理得到的端到端流量总体误差仍低于另外两个算法。

图4中三个曲线的表现与图3类似，在图4(a)中新算法能够在较大规模的网络中准确计算出40%以上的端到端流量，这说明随着网络规模的增加，分解网络拓扑能够更加有效地辅助推理。图4(b)中，新算法虽然在小流量的计算中总体误差比另外两个算法较高，但随着τ值的增加呈较快地下降趋势，并且τ值越大其优势越明显。

(a) 相对误差(re)的分布函数

(b) 不同τ值下算法的总体误差

(a) 相对误差(re)的分布函数

(b) 不同τ值下算法的总体误差

以上实验结果表明，Tomogravity算法将数据中心网络所有TOR交换机平等地参与重力模型的建模和计算，并不符合数据中心网络流量的特点，因而计算准确度较差；而ELIA能够准确计算部分端到端流量，因而其准确度略优于Tomogravity算法，但数据中心网络的大量冗余路径导致系统不满秩的情况极其严重，因此能够准确计算出的流量个数非常有限，因而ELIA也不能达到理想的推理效果。而新算法先将数据中心网络拓扑结构进行了分解，并初步得到准确的粗粒度流量，在粗粒度流量的基础上进一步进行重力流量模型的建模，从而能够得到比较理想的推理结果。

表1比较了三个算法所需的计算时间。从表1可看出，本文提出的新算法相比其他两个算法需要的计算时间更短。Tomogravity算法比本文提出的算法计算时间略长，这也说明拓扑分解后在每个子集中单独应用流量重力模型方法比直接应用重力模型效率更高。而ELIA算法的计算时间最长，并且随网络规模扩大呈较快增长，这是因为ELIA算法在准确计算一部分流量时需要近似指数级的时间复杂度。

从以上实验结果可得出，本文提出的新算法能够在较短的时间内推理得到更准确的数据中心网络端到端流量数据，因而能够有效地应用于现有的数据中心网络。

表1　三个算法计算时间的比较

5结束语

获取网络的端到端流量对于数据中心网络的设计与管理研究至关重要。直接采集端到端流量需要耗费巨大的成本，而传统网络中的端到端流量推理技术无法直接应用于现有的数据中心网络。该文利用数据中心网络的拓扑特点将网络划分为若干子集，并提出本文定理计算得到粗粒度端到端流量，在此基础上提出一种基于流量重力模型的高效端到端流量算法，能够实时准确地推理计算出网络中的所有端到端流量。实验结果表明，相比现有的端到端流量推理算法，新算法能够在数据中心网络中用更短的时间计算出更准确的结果，能够较好地应用于现有的数据中心网络中，从而为更有效地设计和管理数据中心网络提供了重要参考。

参考文献：

[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]朱桂明，谢向辉，郭得科等.一种高吞吐量、高可扩展数据中心网络结构[J].软件学报,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]高飞.数据中心网络迂回路由方法的研究[D].北京:北京交通大学计算机学院,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].软件学报,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.

[责任编辑：张永军]

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

文献标识码：A

文章编号：1673-162X(2016)01-0052-08

作者简介：乔焰(1984—),女, 山东聊城人，安徽农业大学信息与计算机学院讲师，博士；研究方向：计算机网络管理、网络性能测量。

基金项目：国家自然科学基金项目(61402013、61203217)、安徽省教育厅自然科学基金项目(KJ2014A074)、安徽省科技厅国际合作项目(1403062031)、安徽省经信委财政专项资金项目(财企(2013) 1162)资助。

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