云平台中多宿主等待队列动态预测调度算法

吴 菲，徐平平

(1. 南京工业大学浦江学院，江苏 南京210000；2. 东南大学信息科学与技术学院，江苏 南京 210000；3. 东南大学移动通信国家重点实验室，江苏 南京 210000)

1 引言

云平台是基于分布式集群架构，用于处理和存储海量数据，并为用户提供服务的一种新技术[1-2]。由于使用需求的不断扩展，云平台在服务性能上存在着严峻的可靠性与安全性挑战，其中，云平台多宿主数据流处理就是其中之一。在云平台中，数据请求都会经过一些选择机制[3]，当网络环境不佳时，会自动执行数据抛弃，但是丢包率过高会影响云平台服务的处理质量。此外，对多宿主请求数据的处理能力不佳，将会发生网络阻塞，甚至导致网络功能瘫痪。针对这种情况，有学者[4]设计了流量感知调度策略，根据请求任务执行时间判断路由性能，并通过多种因素确定请求任务的转移分配。也有学者[5]采用虚拟等待队列，根据请求数据对资源的差异性需求，通过权值计算实现队列的调度处理。文献[6]针对数据流量相似性而引发的响应延时问题，通过引入分级预测，使队列调度结果更加符合任务需求。此外，文献[7]和[8]也将队列应用于云平台数据调度中，这是因为队列调度基于数据流，更接近请求数据，所以采用队列调度方式能够更有利于进行路由控制。但是，队列调度不好，将会导致数据流堆积，进而引发溢出[9]；而调度算法不好，则会导致数据转发速率慢，延时长，或者形成低等级队列被饿死。针对云平台中多宿主请求数据调度问题，本文提出了等待队列预测调度算法，主要优化队列处理时的数据转发效率和负载均衡性。

2 等待队列模型

在云平台中，传统的等待队列采用的是单队列请求方式[10]。当网络中存在新的请求服务，将其放入接收缓冲器，同时通过接收缓冲器判断等待队列当前的忙闲状态，从而判断请求任务能否入列。随着云平台上服务类型的增加，网络请求任务已经涵盖了图片、文本、音视频、网页等诸多种类，而且它们彼此具有不同的传输格式与请求频次。另外，由于用户类型的差异，网络请求被赋予不同优先级，传统的等待队列调度方式不能很好的为不同等级用户提供相应的服务。于是，本文采用如图1中所示的多宿主等待队列模型。

图1 多宿主等待队列模型

从模型中可以看出，在接收到网络请求后，利用分类器将不同宿主的请求放入到相应等待队列，从而获得更好的数据处理方案。对于多宿主的数据请求，可以将其等待队列集合表示为

Q={q1，q2，…，qn}

(1)

其中，n表示请求包数量；qi表示第i个请求包流，由这些请求包流构成了基队列，再利用分类处理得到子队列集合{qj}1

3 等待队列动态预测调度算法

3.1 入队预测

对于随时到达的网络请求包流，为了能够准确的为其分配资源，本文设计了一种入队预测方法，对正在处理的请求包流所对应的等待队列任务进行估计，估计模型表示如下

(2)

式中，pn(t)表示t时间请求包流n推进队列的概率。α表示泊松因子，用于控制请求包流的入队操作。在对队列进行调度的过程中，所需时间服从指数分布，β表示分布的均值倒数。在第一个请求包流推入队列时，其概率表示为

(3)

针对队列集合中的任意队列i采取分析，假定m=1条件成立，则时刻τ由该队列处理请求包j的概率表示为

(4)

根据计算的概率，可以对请求包流入队的情况进行预测，搜索出请求包流存在的可用等待队列。于是，令M=[mij]=[pij(0)]，可以得到连续时间的预测矩阵描述如下

(5)

利用离散求和的方式得到连续时间下的入队概率预测，可得

(6)

令τ等于0，结合微分方程得到关于预测矩阵的微分方程如下

(7)

至此，整理得出关于指数形式的预测矩阵

(8)

由于整个预测过程是关于t的马尔科夫链，因此，在等待队列动态预测时不受n的影响。当系统中请求包流与等待队列达到稳定状态，即MP(t)=0时，估计模型为0，此时可以解出

(9)

式中，α/β表示对固定时间内平均资源消耗的预测描述。等待队列处理的最大流量表示为(α/β)pn，此时需要满足的条件为

n(α/β)n-1-(n+1)(α/β)n=0

(10)

求解得到最大流量数如下

(11)

通过遍历，得到每个等待队列中的最大请求包数量预测边界，并通过比较确定当前时刻入队的请求包流，以及需要处理的队列任务。

3.2 迁移预测

对于入队的多宿主请求，为了尽可能保证优先级处理效果，每个等待队列应该利用其余所有等待队列调度请求作出相应资源整合，并把整合结果与其余等待队列进行交换，形成迁移行为。这样不仅有利于用户和服务优先级的有效处理，还有利于系统的负载均衡。这里引入马尔科夫对需要执行迁移行为的等待队列进行估计。假定某个状态空间集合表示为Z={Zi}，通过马尔科夫对状态Zn+1估计时，只根据Zn，而与Z0～Zn-1均没有联系。对应的迁移概率描述如下

pij(t)=P{Zn+1=zn+1|Zn}

(12)

这里的pij(t)为t时间由状态i变换至状态j的概率。当Z={Zi}服从λ={λi}分布时，由pij(t)构成概率矩阵记做A，于是，t时间对应的状态分布描述如下

λ(t)=Aλ(t+1)

(13)

该分布向量是由马尔科夫链构成，其中的最大值就是t时间迁移任务的最佳估计。根据每个等待队列的忙闲情况，划分成s个等级，对应的状态空间即为Z={0，1，…，s}。当某请求包推入状态i的等待队列中时，将此请求包与队列的映射关系采取标注，形成一组键值。把所有请求包与队列的映射键值对组合，就构成了马尔科夫链。如果在t时间等级i的等待队列工作于忙状态，此时的负载表示为Li，则应该遍历相邻时间其余等级的等待队列忙闲状态，得到请求包从等待队列i迁移至等待队列j的概率pij=Nij/N。式中的Nij是前一时刻请求包由i迁移至j上的次数。此时对应的概率矩阵表示如下

(14)

由于迁移行为都是从忙状态队列到闲状态队列，所以矩阵H实际上应为下三角。如果将请求迁移至等级j的等待队列上出现了Nj次，那么t-1时对应的状态分布如下

(15)

通过负载情况确定当前等待队列的忙闲，再根据转移概率预测出最佳迁移队列，从而完成请求任务的迁移，确保云服务的处理效果。为了准确判断等待队列的忙闲状态，这里采用流量等级作为判定依据。因为等待队列集合及其子集合都可看做是随机过程，所以在时间t观测到的流量表示为

(16)

(17)

在分布式集群架构的云平台中进行请求任务迁移，将涉及到多虚拟机之间的调度，因此，需要在预测调度之外，再加一层虚拟机状态衡量。本文从CPU资源、带宽流量，以及内存资源三个方面进行状态评价。假定云虚拟机中包含n个CPU，其中第i个CPU的资源占用率是ui，则CPU资源的可用情况描述如下

(18)

ucpu是CPU的累计资源。假定虚拟机k的带宽使用量为uband，累计带宽为wband，则计算出虚拟机k的可用带宽为

(19)

同样，可以计算虚拟机的可用内存如下：

(20)

4 仿真研究

基于CloudSim搭建云平台仿真环境，其中部署20台虚拟机，保持所有配置相同，设置虚拟机内存为1GB，CPU为2048000Mips，带宽为10000Mbps。仿真过程中，分别对多宿主等待队列调度算法的最大输入率、负载均衡性，以及响应延时三方面进行性能验证，并与文献[8]的算法采取对比。

首先，通过仿真得到最大输入率与丢包率之间的关系，结果曲线如图2所示。可以看出，在丢包率不断增加时，所提方法的输入率呈线性下降，且始终高于对比方法。这是由于在多宿主等待队列调度时，本文采取了动态预测算法。一方面对等待队列当前能够处理的最大请求流量进行预测，从而优化请求任务的入队操作；另一方面对请求任务的迁移进行预测，根据等待队列的忙闲状态和云计算资源的可用度，进一步优化不同等级请求任务的队列调度。两个阶段均考虑了多宿主请求时的用户等级与服务类型差异，并针对彼此差异采取相应的优化处理。通过实验结果，表明在相同丢包率的情况下，本文的动态预测调度算法具有更好的稳定性。

图2 最大输入率实验结果

再通过仿真多宿主等待队列调度过程中的负载均衡性，针对其中一个虚拟机进行观测分析，依次改变请求包的数量，得到对应的负载率曲线，结果如图3所示。经过结果对比分析发现，在请求包数量改变时，对各算法的影响并没有什么规律，这是由于多宿主发送来的请求类型是随机变化的，请求类型可能是图片请求、网页请求，或者音视频等请求中的任何一种。但是可以明显看出，在请求包数量改变的过程中，对比方法曾出现过较大的负载率，而本文算法始终保持较低的负载率。其原因是，当本文算法计算发现过去时段存在负载较低的等待队列或者虚拟机时，将会把新到来的请求任务以较大概率迁移过去，从而改善负载均衡，优化请求处理效率。

图3 负载均衡性实验结果

最后，通过仿真得到不同类型用户和不同类型服务组合情况下的平均调度响应延时。实验中，设置用户类型包括：企业级、VIP和普通三种；设置服务类型包括：图片、网页、音频和视频四种，由它们构成的请求任务类型编码如表1所示。各请求对应的平均响应延时结果如图4所示。

表1 请求任务类型

图4 平均响应延时实验结果

从响应延时结果对比发现，当用户类型不同时，本文算法的平均响应延时顺序依次为企业级

5 结束语

为了提高云平台中多宿主等待队列的调度能力，本文提出了一种动态预测迁移算法。该算法一方面根据每个等待队列中的最大请求包数量预测边界，经过比较确定当前时刻等待队列与请求包流之间的映射关系；另一方面根据负载情况确定当前等待队列的忙闲状态，经过迁移概率预测出最佳迁移队列，确保云服务的处理效果。仿真结果表明，本文提出的动态预测迁移算法能够有效满足云平台中多宿主场合的需求，具有良好的调度稳定性、负载均衡性，以及响应速度。