数据中心流量调度的分簇聚类算法仿真

屈 晓,刘 海

(1. 华南农业大学珠江学院,广东 广州 510900;2. 华南师范大学计算机学院,广东 广州 510631)

1 引言

数据中心网络中的流量传输与普通应用中数据流传输的需求不同,主要体现在截止时间、传输速率和响应速度等方面[1-2]。传输故障和网络拥塞是数据中心面临的主要问题,当数据中心出现上述问题时数据流的传输无法得到保障。因此,需要对数据中心流量调度算法展开分析和研究。

尹长川[3]等人首先计算数据中心的最小时隙,根据计算结果对数据中心的采样周期展开调整,将流偏移规划算法应用在奇偶映射方案中完成流量调度。该方法无法有效分类数据中心中存在的流量的类型,存在分簇精度低的问题。马枢清[4]等人首先分析了数据中心的拓扑结构,根据数据中心网络流量带宽和链路带宽资源建立流量调度目标函数,采用粒子群算法对函数求解,获得数据中心流量的最佳调度路径。该方法无法在规定时间内完成流量的调度,且调度速率无法得到保障。为了解决上述方法中存在的问题,提出面向数据中心流量调度的分簇聚类算法。

2 分簇聚类算法设计

2.1 数据中心拓扑结构

用十元组描述数据中心U

U=(F,V,C,Q,B,A1,A2,A,I,N)

(1)

式中,N表示网络带宽;F表示数据集合,由f个设备中的数据构成;I表示任务类型矩阵;V表示物理云节点;A表示节点执行任务时的功率集合;C表示虚拟机设备;A1表示节点峰值状态下的功率集合;A2表示节点空闲状态下的功率集合;集合Q由用户命令构成;B表示节点与任务块之间对应的矩阵,其表达式如下

(2)

式中,bmn表示虚拟机中任务块ti产生的执行结果。

在云计算服务和网络架构的基础上调整数据中心的拓扑结构,调整云节点中存在的流量,避免数据中心出现流量拥塞问题。

2.2 流量信息检测

(3)

当链路带宽小于链路负载时,流量在数据中心会发生拥塞现象,降低链路在数据中心中的利用率[5-6]。

设Nw(rxy)代表链路负载,Nu(rxy)代表链路利用率,其计算公式分别如下

(4)

式中,Dx表示链路端口在数据中心中发送的字节数;Nc(rxy)表示链路传输带宽,即容量;Tx表示链路端口在数据中心中接收的字节数。

链路在其利用率Nu(rxy)高于0.9或负载Nw(rxy)高于门限值时会出现拥塞现象,需要对流量展开调度。

2.3 数据中心流量去噪

用c表示数据中心内的流量数据,其表达式如下

c=u+b

(5)

式中,b表示噪声;u表示不存在噪声的流量数据。

在多层感知机中,输入含噪的流量数据c,输出不存在噪声的流量数据u,两者之间的关系可通过下式描述

u=J(c,ϑ)

(6)

式中,ϑ表示由多层感知机参数构成的集合;J表示多层感知机的网络结构。数据中心流量的去噪过程可以描述为在较少噪声的流量中映射存在噪声的流量,因此,需要建立多层感知机模型用于表示上述映射关系。

多层感知机由隐层、输出层和输入层构成,其中输入层不存在计算内容,只负责接收流量数据[7-8],按照权重大小将流量数据传输到隐层中,隐层建立了非线性激活函数,主要用于处理流量数据,并将处理结果传输到多层感知机的输出层中,获得数据中心流量的去噪结果。

设置激活函数s,用g(x)表示多层感知机,其表达式如下

g(x)=n2+E2s(n1+E1c)

(7)

式中,n1、n2表示偏置矩阵;E1、E2表示权重矩阵。

通过网络流量对多层感知机的参数展开调节,当多层感知机的输出接近不存在噪声的网络流量时,完成多层感知机的训练。多层感知机的训练需要多次循环,每次训练都存在两个阶段,分别是前向传播阶段和反向传播阶段,通过梯度下降方法[9-10]对多层感知机的参数展开调节。

1)前向传播阶段

用βj表示第j个神经元在多层感知机隐层中收到的输入,其表达式如下

(8)

式中,ck表示神经元的数据分量;ekj表示不同神经元在不同层次中的连接权重。

在隐层中采用Sigmoid激活函数处理数据βj,并向输出层传送处理结果,用χi表示第i个神经元在多层感知机输出层中收到的输入,其表达式如下

(9)

式中,bji表示输出层第i个神经元与隐层神经元之间的权重。通过上述过程,获得多层感知机的输出u′=[χ1,χ2,…,χm]T。

2)反向传播阶段

可用误差更新输出层在多层感知机中的权重,隐层在多层感知机中不存在误差,因此无法直接将梯度下降法应用在隐层中,通过反向传播在链式法则的基础上将误差传播到隐层,再采用上述方法展开处理。

设R代表的是多层感知机的均方误差,可通过下式计算得到

(10)

式中,ui表示第i个神经元在输出层的数据分量。在梯度下降策略的基础上误差逆传播算法通过下式调整权重

(11)

式中,ι存在于区间(0,1)内,表示学习率。

2.4 基于K-means的流量分簇聚类

面向数据中心流量调度的分簇聚类算法采用K-means算法[11-12]对数据中心的流量展开聚类优化处理,具体过程如下:

1)设置数据集F,由网络流量构成,通过下述公式获得流量包在F中对应的样本点分布密度g(i)以及距离因子均值Fis：

(12)

式中,n表示流量包的数量;h(xi,xj)表示度量因子。

2)设置数据集S,初始聚类中心选取g(i)值最大的流量包s1,将其存储到S中,当流量包与s1之间的距离因子小于距离因子均值Fis时,在集合F中剔除该流量包;

3)针对集合F中剩余的流量包,用λ表示其最大分布密度乘积,可通过下式计算得到

(13)

式中,ϑ(i)表示距离因子均值;f(xi,xj)表示距离度量因子。根据上式计算结果,第二个流量聚类中心s2选取最大λ对应的点i,并在数据集S中记录聚类中心s2,按照相同的方式剔除数据集F中的一部分流量包样本点。

4)计算流量包样本点s1、s2在数据集F中的最大分布密度乘积λ,选择最大λ对应的样本点i作为第三个流量数据的聚类中心s3,将其存储在数据集F中,同理,删除部分流量包样本点。

5)按照相同的方式选取聚类中心,在数据中心中获得流量数据的K个聚类中心。

6)通过上述过程确定聚类中心和初始聚类中心,完成数据中心流量的分簇聚类。

2.5 调度路径确定

根据网络流量的聚类结果,在调度过程中选取互相覆盖的多条大象流作为目标,分析数据中心的结构特点,当目的主机与源主机不在相同区域内时,两者之间存在K2/4条流量调度路径,在上述路径中选取流量数据传输调度的最优路径。在相同区域内,面向数据中心流量调度的分簇聚类算法采用分簇聚合交换机调度目的主机与源主机中存在的流量数据,获得K/2条流量数据的调度路径。

2.6 数据中心流量调度

1)网络带宽分配

数据中心网络带宽的分配结果体现在链路在数据中心中的拥塞程度,通过下式描述数据中心分配网络带宽的过程[13-14]

(14)

式中,γk表示数据中心预设的优先级;X表示物理链路在数据中心中的最大带宽。

2)调度约束

用户的网络接口速度在数据中心流量调度过程中是存在一定限制的,约束条件如下

(15)

式中,Bi表示数据中心需要传输的流量数据量;Li表示判断系数,其主要目的是判断虚拟机中节点是否存在任务传输请求。

3)流量分类调度

按照流量数据聚类结果,以及流量传输对数据中心链路的质量要求,确定不同流量簇集在数据中心中的优先等级[15],对其展开调度处理,如图1所示。

图1 数据中心流量调度

图1中ni表示网络流量聚类后的簇集,在数据中心中划分网络流量,获得G1、G2、G3三条流量。当流量在路径中出现负载现象时,可利用数据中心中存在的其它路径调度该条路径中存在的流量数据,实现数据中心的流量调度。

3 实验与分析

为了验证面向数据中心流量调度的分簇聚类算法的整体有效性,需要对其展开测试。本次测试的数据中心相关参数如表1所示。

表1 实验参数

流量在数据中心中的分布情况如图2所示。

图2 流量分布情况

图2中的方框属于老鼠流,浅色圆球属于大象流。根据图2可知,大象流和老鼠流混合分布在数据中心中,现采用面向数据中心流量调度的分簇聚类算法、文献[3]算法、文献[4]算法对数据中心展开流量分簇处理,分簇结果如图3所示。

图3 不同方法的流量分簇结果

由图3可知,所提方法可将数据中心中存在大象流和老鼠流分为两个簇,而文献[3]算法和文献[4]方法无法精准地将大象流和老鼠流分簇,验证了所提算法具有较高的分簇精度,因为所提算法对数据中心流量分簇处理之前,采用多层感知机对流量数据展开了去噪处理,在此基础上,分簇聚类流量数据,提高了流量数据的分簇精度。

在数据中心中存在不同优先级的流量包,需要优先调度优先级高的流量包,在本次测试过程中设置三个等级的流量包,优先级按照从大到小的排序为流量包1、流量包2、流量包3。将流量包1的传输时间设置为10s,流量包2的传输时间设置为20s,流量包3的传输时间设置为15s,现采用所提算法、文献[3]算法和文献[4]算法对三种流量包展开调度,调度结果如图4所示。

图4 不同算法的流量调度结果

分析图4可知,采用所提算法展开调度时,该算法根据流量包的优先级对流量包展开调度,并且调度三个流量包的速率相同,表明所提方法具有较高的稳定性,采用文献[3]算法和文献[4]算法调度流量包1花费了20s,表明这两种算法无法在规定时间内完成流量包的调度,且调度流量包的速率存在差异,表明以上两种算法的调度效果较差。

4 结束语

在网络流量不断增加的背景下,人们对数据中心的流量调度提出了更高的要求。目前流量调度方法存在分簇精度低和调度效果差的问题,提出面向数据中心流量调度的分簇聚类算法,该算法在流量调度过程中消除了流量数据中存在的噪声,并对流量展开了分簇处理,在此基础上,完成数据中心的流量调度,经实验验证可知,所提算法可有效避免数据中心出现拥塞现象。