韩　冰　宋正江　鲁　阳　陈建成

(浙江工业职业技术学院数字媒体与信息工程分院设计与艺术分院　浙江 绍兴 312000)



云计算数据中心网络的端到端流量计算

韩冰宋正江鲁阳陈建成

(浙江工业职业技术学院数字媒体与信息工程分院设计与艺术分院浙江 绍兴 312000)

摘要云计算数据中心网络的流量特征是研究和设计云计算网络的基础，现有的流量测量研究方法通常要求交换机支持额外功能模块或具备可编程能力，而目前大多数云计算数据中心网络的交换机并不满足此要求。提出一种基于网络层析技术的端到端流量推理算法，仅使用交换机普遍支持的SNMP(简单的网络管理协议)数据，就能快速准确地计算出端到端的流量信息。并通过仿真实验与已有的网络层析算法进行比较，结果表明新算法更适用于大规模的云计算数据中心网络，可以在较短的时间内得到更准确的计算结果，从而为云计算网络的设计和研究提供了重要的参考依据。

关键词云计算数据中心网络网络层析SNMP

END-TO-END TRAFFIC CALCULATION FOR CLOUD COMPUTING DATA CENTRE NETWORKS

Han BingSong ZhengjiangLu YangChen Jiancheng

(Department of Digital and Art, Zhejiang Industry Polytechnic College, Shaoxing 312000, Zhejiang, China)

AbstractTraffic characteristic of cloud computing data centre networks is the basis of research and design of cloud computing networks. Current study methods of traffic measurement techniques usually ask the switches supporting additional functional modules or being programmable, however not many of the cloud computing data centre networks can afford such switches. In this paper, we proposed an end-to-end traffic inference algorithm which is based on network tomography. It can rapidly calculate the end-to-end traffic information with high accuracy by only utilising SNMP (simple network management protocol) data ubiquitously supported by switches. Through simulation experiment the algorithm was compared with existing network tomography algorithm, and result showed that the new algorithm was more applicable to large-scale cloud computing data centre networks, and could gain more accurate computing results in short period, so as to provide important reference basis for the design and research of cloud computing networks.

KeywordsCloud computingData centre networkNetwork tomographySNMP

0引言

随着云计算技术的高速发展，云计算数据中心网络对可靠性的要求也越来越高，很多学者针对云计算数据中心网络的设计与管理展开研究，其中包括网络结构的设计[1-3]，路由策略的研究[4-6]，资源分配以及网络异常的检测与诊断[7,8]等。然而对数据中心网络流量的研究却存在明显不足，在一定程度上影响了其他云计算技术的研究进程。近些年来越来越多的学者开始注意到研究数据中心流量特征的重要性，部分学者开始研究如何测量并分析数据中心网络流量的主要特征[9-11]。 文献[9]重点研究了用于Web service和Mapreduce应用的云计算数据中心网络的流量特征，文献[10]给出了一般云计算数据中心网络的流量特征，文献[9,10]均通过在网络交换机上安装包跟踪器模块的方法来测量网络的端到端流量。包跟踪器需要捕捉每个包的源/目的地址信息并汇总到网络控制中心，占用了大量的存储成本和时间成本，当网络规模较大时，无法实时地呈现网络中所有端到端流量信息。并且无法保证所有的数据中心交换机都支持包跟踪器的模块安装。

另一种实时测量网络端到端流量的方法是网络层析技术。它通过收集交换机中的SNMP数据得到每条网络链路的总流量，并且建立链路总流量与端到端流量之间的线性关系，最终计算出每个端到端的流量。网络层析技术由于其操作成本低，计算准确已被广泛应用于IP网与ISP网的端到端流量测量问题中[12-14]。然而文献[11]的大量实验数据表明，已有的网络层析技术无法直接应用于云计算数据中心网络中。因为云计算数据中心网络中存在大量的端到端冗余路径，并且数据中心的网络流量特征更加复杂多变。

为了使用最低的成本计算出准确的端到端流量，本文根据云计算数据中心网络的拓扑特点，把网络划分为若干子集，将端到端的流量计算问题简化为 “子集与子集之间的流量”和“子集内部端到端流量”的计算，从而解决了云计算数据中心网络端到端冗余路径的问题。并在此基础上提出了一种适用于云计算网络流量计算的网络层析方法，新方法利用数据中心流量的时间相关性将算法问题建模成线性状态空间模型，通过改进的卡尔曼滤波算法最终计算得到每条路径所承载的流量。实验证明，相比已有的端到端流量计算方法，新方法更能适用于具有大量冗余路径和流量特征复杂的云计算数据中心网络中，并且计算时间的花费更少、计算的精确度更高。

1背景与问题描述

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

图1为目前应用最广泛的云计算网络中心拓扑，它包含三层结构：核心交换机(Core switch)层，聚合交换机(Aggregation switch)层，以及柜顶交换机(Top of Rack switch， 或TOR switch)层，柜顶交换机又称为TOR交换机。SNMP是当前几乎所有交换机都支持的网络管理协议，也可以理解为交换机各个端口的包(或比特)的计数器。通过在不同的时间间隔(如1~30分钟)提取交换机的SNMP数据可获得交换机端口之间链路在对应时间间隔内所承载的总流量。本文重点研究如何根据链路总流量计算得到每个TOR交换机之间的端到端流量。

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

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)是不可取的。本文下面将提出一种适用于云计算数据中心网络的流量推理方法，可准确地从式(1)推理计算出未知数X(t)。

2网络拓扑的分解

云计算数据中心网络拓扑相对于其他计算机网络(如IP网，Internet等)，具有其独有的特性，即网络的分层结构以及类似树状结构。因此，可根据数据中心网络端到端流量的条件独立性将网络拓扑分解为若干子集。例如，对于图1中的数据中心网络拓扑，可将其划分为2个子集C1和C2(如图2所示)。

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

条件独立性是指对于子集C1来说，若经过交换机Agg1和Agg2的每个端到端流量是已知的，则所有经过交换机TOR1~TOR4的端到端流量也是已知的。在分解了网络拓扑后，推理计算TOR到TOR流量的问题可转换成推理计算C1和C2之间的端到端流量，以及推理计算C1与C2子网内部的端到端流量问题。从图2中可以看出， C1与C2之间的路径个数为2，而两个子集之间的链路个数为4，相对式(1)，不满秩的情况得到很大地改善。C1与C2内部的端到端流量推理问题也有相似的情况。 在下一小节中将提出一种推理子集之间端到端流量以及子集内部端到端流量的高效推理算法。值得注意的是，本文提出的方法仅能推理出TOR在同一个子集时的端到端流量，两个TOR不在一个子集时的端到端流量推理方法会在将来的工作中继续研究。

3基于线性状态空间模型的端到端流量计算算法

文献[13,14]提出了在IP和ISP网络中，端到端流量在一定程度上具有时间相关性。本文通过对实际云计算数据中心的流量分析发现，在云计算数据中心网络中，端到端流量同样存在较强的时间相关性。因此，将端到端流量计算问题建立成线性状态空间模型，并在经典的卡尔曼滤波算法的基础上提出用于数据中心网络的端到端流量计算算法。

3.1建模

首先将流量计算问题建立成线性状态空间模型:

(2)

图3　建立流量计算的线性状态空间模型

在式(2)中， X(t)={x1(t),…,xn(t)}为路径流量， Y(t)={y1(t),…,ym(t)}为测量到的链路流量。F为X(t)与X(t-1)之间的关系矩阵，表示同一个路径在相邻两个时间间隔内流量的关联关系。 Q(t-1)为独立同分布的高斯过程，其均值为0，协方差矩阵为σQ，表示对关联关系F的不确定程度。 A为路由矩阵，表示X(t)与Y(t)之间的关联关系。 V(t)同样为独立同分布的高斯过程，其均值为0，方差为σV，表示网络的观测噪声。建立好的流量计算状态空间模型如图3所示。

3.2改进的卡尔曼滤波算法

卡尔曼滤波算法是线性状态空间模型算法中性能最好的算法之一，它能够在模型满足高斯过程的情况下达到最优解。在流量推理的状态空间模型中，假设路径流量状态xi(t)满足高斯分布N(μi,σi)，其中将μi作为对路径流量的估计，σi作为对此估计的不确定程度。根据高斯分布的性质，在xi(t)满足高斯分布时， yi(t)也同样满足高斯分布。这样卡尔曼滤波将会求出满足SNMP观测值的端到端流量的最优解。

现有的卡尔曼滤波算法包含两个步骤:预测和更新。预测阶段根据t时间间隔内的X(t)状态预测X(t+1)的状态，更新阶段根据观测到的Y(t+1)的状态调整X(t+1)的状态。本文为卡尔曼滤波算法添加了反馈的步骤，用更新后的X(t+1)反馈给X(t)，使得X(t)的状态得到优化调整。

3.2.1 预测算法

在预测阶段，根据X(t)通过式(3)预测X(t+1)的状态:

X(t+1)=FX(t)

(3)

式中,F为对角矩阵，对角线上的元素表示状态X(t)与X(t+1)的关联系数。本文将F设置为单位矩阵，并将σQ设置为较大值，此时的实验结果较为理想。

同时，用式(4)调整X(t+1)的协方差矩阵:

(4)

3.2.2 更新算法

首先根据式(5)计算预测值与真实值之间的差距:

I(t+1)=Y(t+1)-AX(t+1)

(5)

再根据差值I(t+1)调整变量X(t+1)的值，如式(6)所示:

(6)

(7)

同时通过式(8)更新X(t+1)的方差:

(8)

3.2.3 反馈算法

(9)

(10)

同时，调整X(t)的协方差为：

(11)

3.2.4 算法伪代码

输入:Y(1:T),A,F,X(0),σ(0),σQ(0:T),σV(1:T)输出:X(1:T)foreacht∈1:T[X(t),σ(t)]←Predict(X(t-1),σ(t-1),σQ(t-1),F);[X(t),σ(t)]←Update(X(t),Y(t),σ(t),σV(t),A)[X(t-1),σ(t-1)]←Smooth(X(t),X(t-1),σ(t),σ(t-1),σQ(t-1),F)endfor

算法输入T个时间间隔的SNMP数据Y(1∶T)，路由矩阵A，每个流量自身的关系矩阵F以及式(2)中Q和V的协方差矩阵σQ和σv。此外，还需要为X和X的方差σ以及σQ设置一个初始值。算法输出T个时间间隔所有路径所承载的端到端流量X(1∶T)。

4仿真实验

4.1实验设置

实验用NS-3构建了图1所示的拓扑结构，拓扑包含32个TOR交换机，16个聚合交换机和8个核心交换机。每个机架下面有20台服务器，每条链路的带宽设置为1 Gbps。在创建网络拓扑后，根据文献[9-11]对云计算数据中心网络流量特征的研究，产生端到端流量:在每个机架下随机选择1~10个服务器向其他所有服务器发送数据包。当服务器向其他机架下的服务器发送数据包时，其发送的数据包个数服从对数正态分布Log-N(4,1);当向相同机架下的服务器发送数据包时，发送数据包的个数服从对数正态分布Log-N(10,1)。每个数据包大小约1400 个字节。数据流量的路由策略采用数据中心网络普遍采用的ECMP(等价多路径路由协议)协议[15]。采集各个交换机端口的SNMP数据的时间间隔为5分钟。

4.2算法与评价准则

将新算法与经典的基于网络层析技术的算法SRMF[13]作比较。该算法是目前准确度最高的网络层析算法之一，并且也利用了流量的时间相关性特征。对两个算法的性能主要从两个方面来评价：算法的运算时间和算法的计算准确度。其中计算准确度用相对误差的累积分布函数(CDRE)来度量，用式(12)来衡量算法的相对误差(RE)。

(12)

4.3仿真结果

图4比较了两个算法在测量3个时间间隔与测量25个时间间隔SNMP数据时的计算误差。从图4(a)中可以看出当测量3个时间间隔的SNMP数据时，新算法与SRMF算法计算误差累计分布相差并不明显。而当图4(b)中测量了25个时间间隔时：新算法计算出的端到端流量，相对误差<0.5的占比90%以上，而已有SRMF算法计算出的端到端流量，相对误差<0.5的仅占比70%左右。说明随着时间的推移，新算法能不断地校准模型，使模型更符合当前的网络状况，从而能够得到更加准确的计算结果。

(a) 3个时间间隔

(b) 25个时间间隔

图4两个算法在不同时间间隔下的相对误差累计分布函数

表1列出了在不同时间间隔SNMP数据的条件下，两个算法的计算时间差异对比。从表1中可以看出，新算法在时间间隔较少时与SRMF算法的计算时间相差不多。而随着时间间隔的加大，端到端的流量数目也不断增加，SRMF的计算时间也远超新算法。当时间间隔个数增加到100时，SRMF无法在有限时间内得出结果，而新算法在此时仍可以在较短时间内得出计算结果。这也说明新算法能够应用于大规模的云计算数据中心网络。

表1　两个算法的计算时间(单位:秒)

5结语

云计算技术的发展研究越来越离不开对数据中心网络流量特征的深入研究。现有的数据中心流量测量技术对网络中的交换机有着较高的要求，无法适用于大多数的云计算数据中心网络。普遍应用于ISP网络的网络层析技术仅利用交换机的SNMP数据可推理得到网络的端到端流量，但由于数据中心网络中存在大量冗余路径，并且流量复杂多变，现有的网络层析算法无法直接应用于其中。为了解决以上问题，本文利用云计算数据中心网络的拓扑特征将网络划分为若干子集，从而大大简化了算法问题的复杂程度，并提出一种高效的端到端流量算法，利用流量的时间相关性，实时准确地推理计算出网络中的所有端到端流量。实验结果表明，相比于已有的网络层析算法，新算法能够在更短的时间内计算出更准确的结果。

参考文献

[1] Greenberg A,Hamilton J R,Jain N,et al．VL2: A Scalable and Flexible Data Center Network[C]//Proceedings of ACM SIGCOMM，Spain， August 17-21， 2009．

[2] Guo C,Lu G,Li D,et al．BCUBE：A High Performance，Server-centric Network Architecture for Modular Data Centers[C]//Proceedings of ACM SIGCOMM，Spain，August 17-21，2009．

[3] 刘晓茜，杨寿保，郭良敏，等．雪花结构：一种新型数据中心网络结构[J]．计算机学报，2011，34(1) :76-86．

[4] Al-Fares M,Radhakrishnan S，Raghavan B, et al．Hedera: Dynamic Flow Scheduling for Data Center Networks[C]//Proceedings of USENIX NSDI, California, April 28-30, 2010．

[5] Jiang J W,Lan T,Ha S，et al．Joint VM Placement and Routing for Data Center Traffic Engineering[C]//Proceedings of IEEE INFOCOM，Florida，March 25-30，2012．

[6] 罗腊咏，贺鹏，关洪涛，等．可编程虚拟路由器关键技术与原型系统[J]．计算机学报，2013，36(7) : 1349-1363．

[7] Gill P，Jain N,Nagappan N．Understanding Network Failures in Data Centers: Measurement，Analysis，and Implications[C]//Proceedings of ACM SIGCOMM，Toronto，August 15-19，2011．

[8] 金嘉晖，罗军舟，宋爱波，等．基于数据中心负载分析的自适应延迟调度算法[J]．通信学报，2011，32(7) : 47-56．

[9] Benson T，Anand A，Akella A，et al．Understanding Data Center Traffic Characteristics[C]//Proceedings of ACM SIGCOMM，New Delhi，August 30-September 3，2010．

[10] Benson T，Akellaa，D.Maltz A．Network Traffic Characteristics of Data Centers in the Wild[C]//Proceedings of ACM IMC, Melbourne, November 1-3, 2010．

[11] Kandula S，Sengupta S，Greenberg A，et al．The Nature of Data Center Traffic: Measurements & Analysis[C]//Proceedings of ACM IMC，Illinois，November 4-6，2009．

[12] Zhang Y，Roughan M，Duffield N，et al．Fast Accurate Computation of Large-scale IP Traffic Matrices from Link Loads[C]//Proceedings of ACM SIGMETRICS，California，June 9-14, 2003．

[13] Zhang Y，Roughan M，Willnger W，et al．Spatio-temporal Compressive Sensing and Internet Traffic Matrice[C]//Proceedings of ACM SIGCOMM， Barcelona，August 17-21，2009．

[14] Soule A，Lakhina A，Taft A，et al．Traffic Matrices: Balancing Measurements [C]//Inference and Modeling Proceedings of ACM SIGMETRICS，Alberta，June 6-10，2005．

[15] Hopps C. Analysis of an Equal-Cost Multi-Path Algorithm [M/OL].Nov 2000. http://www.hjp.at/doc/rfc/rfc2991.html.

中图分类号TP393.07

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.02.076

收稿日期：2014-01-21。浙江省自然科学基金项目(Y1100137)。韩冰，讲师，主研领域：云计算，人工智能，Web挖掘。宋正江，讲师。鲁阳，讲师。陈建成，讲师。