联合成本优化和队列稳定的数据中心调度算法

2019-01-10孙佑明

西安文理学院学报（自然科学版） 2018年6期

孙佑明

(巢湖学院信息工程学院，安徽巢湖 238000)

假设数据中心[1-2]是由一个中央控制器和N个服务器组成，每个服务器n有三种基本状态：活动状态，此时服务器n可用于服务请求并产生成本en；睡眠状态，此时服务器处于低成本的休眠状态，不提供任何服务请求；启动状态，此时服务器处于从空闲到活动状态的过渡期.通过选择特定的睡眠模式和睡眠时间，处于活动状态的服务器可以在任意时刻过渡到睡眠状态.例如，深度睡眠模式可以关闭更多的电子设备，从而节省更多的成本；但从深度睡眠状态过渡到活动状态需要更长的时间.每个服务器分别决定何时转换和使用什么睡眠模式，每个服务器的转换时间是异步的.中央控制器将请求调度至服务器，也可能拒绝请求.

1 问题建模

在每个时刻t∈{0,1,2,…}，新请求的到达率是λ(t)，其中：λ(t)∈Λ.Rn(t)表示服务器n接收到的请求数量，d(t)是被服务器n拒绝的请求数量，而c(t)∈C是每一个被拒绝请求的成本.Rn(t)和d(t)之间需要满足如下的关系：

(1)

(2)

每个服务器n都维护一个请求队列Qn(t)，Qn(t)的计算如下：

Qn(t+1)=max{Qn(t)+Rn(t)-μn(t)Hn(t),0}

(3)

Hn(t)是一个指示变量.若Hn(t)=1，则服务器n在时刻t处于活动状态；否则，Hn(t)=0.μn(t)是一个随机变量，表示时刻t请求的服务率，其平均值为μn.每个队列初始化为Qn(0)=0.

(4)

其中，In[f]是服务器处于睡眠状态的时间，τn[f]是服务器处于启动状态的时间.

本文的目标是最小化调度过程的总成本，同时保持系统的稳定，该优化问题如下所示：

(5)

(6)

其中，第一个约束条件要求平均服务率不能小于请求的平均达到率，这样一来队列就不会堆积，系统才能趋于稳定状态.接下来的目标是设计一种算法，该算法中每个服务器都可以独立地、分布式地进行调度，无需获取其他服务器的工作负载或调度决策，并能够依概率接近最优.

2 实时在线调度算法

(7)

对于每一个时刻t，通过求解以下的优化问题，我们能得到Rn(t)和d(t)：

(8)

此时，有

(9)

(10)

(11)

其中，B0=(Rmax+μmax)μmax/2.如果服务器选择转换成活动状态(即αn[f]=active)，那么就有

(12)

如果服务器转换为睡眠状态，则有

(13)

然后，服务器计算确定性优化问题(14)的最小值.对于αn∈Ln，对公式(14)关于In[f]求导，以得到最小解.然后将该最小解与式(12)的值进行比较，若式(12)的值小于最小解，则服务器进入活动状态；否则，服务器选择进入睡眠状态.

(14)

3 仿真实验

在本节中，我们将通过大量的仿真实验来验证算法的性能.本文的算法达到了Ο(1/V)接近最优.我们将本文算法与其他几种启发式算法进行了比较，结果表明，该算法确实具有较低的时延和较低的功耗.

图1 平均成本与V值的关系

在第一部分的仿真实验中，我们使用了一个较小规模的数据中心模型.服务器的数量N=5，请求率λ(t)服从[10,30]的均匀分布，拒绝成本c(t)服从[1,6]的均匀分布，Rmax=40.仿真实验的运行时间是10 000个时刻.图1展示了随着权衡参数V变大，时间平均成本逐渐接近最优值.当V值很小的时候，成本曲线迅速下降；当V值变大时，成本曲线变得平坦.这说明了本文算法以Ο(1/V)接近最优.

在第二部分的仿真实验中，我们采用真实数据中心流量[4-5]作为实验数据集.实验的总时间为1 500 s.图2和图3分别是随着V值的变大，系统平均功耗和队列长度的变化.由结果可以看出，V值对平均功耗没有太大的影响，但是队列长度却受V值影响.接下来，我们将本文算法与其他策略进行比较，图4和图5分别是平均功耗和队列长度的实验结果.在实验的开始部分，所有算法都表现良好.但在后半部分，随着流量增加，主动算法的队列长度剧烈增加.由于启动时间长，被动算法中处于活动状态的服务器数量无法适应不断增加的流量，因此队列长度也会增加.本文提出的算法在稳定队列的同时最小化了功耗，因此在性能上超过了主动算法和被动算法.