基于队列理论的云资源分配收益最大化算法

郑宇超 夏学文 艾冬梅

1(华东交通大学软件学院 江西 南昌 330013) 2(北京科技大学数理学院 北京 100083)

基于队列理论的云资源分配收益最大化算法

郑宇超1夏学文1艾冬梅2

1(华东交通大学软件学院 江西 南昌 330013)2(北京科技大学数理学院 北京 100083)

为了优化资源分配收益，提出基于时间服务因子TSF资源定价机制下的资源分配算法。首先，算法将资源分配问题形式化为队列模型，并构建了收益最大化函数。然后，通过Lagrange乘子法求解最优化函数的解。利用时间服务因子，算法分别通过安全满意度因子ASF和响应满意度因子RSF定义了资源的定价方式，并同步考虑定价、请求到达率、资源服务率及可用资源量，得到了使收益最大化的资源分配方式。实验结果表明，与传统的启发式资源分配算法比较，该算法得到的收益更高，且尤其在云资源数量较稀少的场景下，算法将更加具有优势。

队列理论 资源分配 云计算 收益最大化

0 引 言

云计算旨在通过虚拟化技术将IT资源整合成为大规模可扩展的资源池，并且以Internet作为载体提供软件(SaaS)、平台(PaaS)及基础设施(IaaS)等形式的服务[1]。以服务提供者角度来讲，云计算可以为终端用户提供池化的资源，提供者的目标是租用各类服务并获得收益。云服务的使用模式通常以预先支付或即付即用为主，用户方只需要对请求服务或消费服务进行付费[2]。服务提供过程中，服务等级协议SLA供求双方协作的重要问题。消费者主要通过服务质量QoS参数明确请求服务的等级。SLA通常根据可用性、响应时间等对资源分配的责任、担保或性能等级进行具体描述。本文将以定价机制描述供求双方需要服从的SLA。

对于服务提供者，在用户服务实例间进行合理资源分配对最终获得收益是至关重要的，即使对于相同的资源分配，收益也会随着不同的分配策略产生极大变化。因此，本文将重点关注于如何基于SLA和可度量的服务属性，管理资源分配并提供可区分的性能等级，以便最大化收益。

相关研究中，文献[3]将云资源配置多目标优化定义为博弈问题，以服务质量和柔性指标多目标函数作为资源方和用户方博弈双方的收益函数，并通过GA算法对收益函数进行了求解。文献[4]对任务类型偏好与资源服务能力差异进行了区分，在此基础上提出了一种基于区分服务的演化博弈调度算法，可以极大提高用户QoS。文献[5]为了实现总利益最大化，通过建立服务提供商间的合作关系，提出了一种云资源分配的协作博弈模型。文献[6]采用时间矩阵和费用矩阵作为云任务效益的衡量指标，提出一种基于效益博弈的资源动态可协调分配算法，通过构建效益博弈模型，以一种动态协调机制对博弈进行了求解。文献[7]为解决资源竞争问题，提出通过建立用户联盟增加用户效用，提高资源分配效率，但作者缺乏对模型的实验验证与分析。

不同于以上工作，本文的研究主要集中于：1)以队列理论对云资源分配问题进行建模，模型综合考虑了资源量、请求到达率、服务时间及资源定价等QoS参数。2)基于时间服务设计了两种定价机制下的资源分配算法，目标是最大化资源提供收益。

1 系统模型

1.1 数学模型

假设云数据中心的服务器数量为N，服务提供者与m个用户间以SLAs的形式签订服务协议，每个用户(服务实例)可以通过服务器的资源分配获得相应服务。考虑分配给每个服务实例i的ni个服务器可作为一个超级服务器，超级服务器的能力正比于其服务器数量。设系统中的服务实例请求服从泊松分布，其平均服务到达率为λ，服务器对其处理时间服从负指数分布，其平均服务率为1/μ，其中，μ表示单位时间内处理请求的数量。服务器对服务请求的执行由于运行环境的转换需要付出代价，如：花费时间从外部存储中读取新到用户的相关数据，因此，与单个服务实例相关的一组服务器可构建为基于FIFO的M/M/1队列模型，定义服务强度ρ为请求到达率与单个服务器的服务率之比。系统模型的相关参数说明如表1所示。

(1)

表1 符号说明

1.2 基于定价模型的时间服务因子TSF

1.2.1 服务性能指标

通常，云服务通过性能完成情况收取费用。为了评估性能，通常有两种与响应时间相关的常用指标：平均响应时间MRT与时间服务因子TSF。其中，MRT是评估服务性能的常用指标，但无法反映响应时间出现大范围波动的情况；而TSF可定义为确定时间间隔(时间槽)内的服务百分比，不仅可以反映响应时间，还可以精确描述响应时间的分布。本文将TSF定义为一个二元组，其中，r表示响应时间，a表示响应时间低于r时的服务百分比，因此，a可视为一个安全因子。

基于用户需求与TSF，本文设计了两种指标：安全满意度因子ASF和响应满意度因子RSF。同时，ASF与RSF均可以反映获取性能与用户服务需求之间的偏差。根据TSF定义用户需求为二元组，则需求的服务实例的ASF可表示为：

(2)

其中：a表示在响应时间要求为R时实际获取的安全因子，即响应时间小于R时的服务率，fA表示实际获取性能与用户要求间的偏差。式(2)表明，若fA大于或等于0，获取性能可满足用户要求，若获取性能无法满足用户要求，则fA小于0。

同样地，根据TSF定义用户需求为，需求的服务实例的RSF为：

(3)

其中：r表示获得的安全因子要求为A时的响应时间。式(3)表明，若fR大于或等于0，获取性能可满足用户要求，若获取性能无法满足用户要求，则fA小于0。

为了计算在一个时间槽内单个服务实例的第A个百分位响应时间，需要：

1) 记录单个服务实例在一个时间槽内所有服务对应所有响应时间；

2) 对以上所有记录进行升序排列；

3) 选择有序序列中第A个记录作为最终结果。

1.2.2 定价模型

本文基于ASF和RSF设计了两种需求驱动的资源定价模型。将服务实例的服务提供时间划分为固定步长的时间段，如表示用户的计划需求，可以根据ASF和RSF获得其服务性能。若获得的服务性能满足用户需求，服务按基准价格付费。若获得的服务性能无法满足需求，服务提供者将按基准价格进行惩罚。基准价格b由服务实例的属性决定，具体计算方法见下节。

根据ASF和RSF定义以下两种定价模型：

(4)

或

(5)

其中：服务提供价格B分别表示fA与fR的线性函数。两种定价模型如图1所示。

图1 基于时间服务因子的定价模型

1.2.3 基准价格

根据M/M/1模型的队列理论，服务滞留时间的累积分布时间为：

w(t)=1-e(λ-μ)t

(6)

假设需求为的服务实例被分配n台服务器，将代入式(6)：

A=1-e(λ-nμ)R

(7)

(8)

式(8)表明n台服务器可确保用户性能需求。若假设c表示单位资源的预期边际收益，则b为来自n台服务器的预期收益：

(9)

由于服务请求到达率是动态变化的，可通过采样统计获取平均到达率。

2 资源分配最优化

2.1 基于ASF的资源分配最优化

假设服务实例i分配ni台服务器，其性能需求为，安全因子为服务请求响应时间小于或等于Ri的概率，由式(6)，安全因子ai可表示为：

ai=1-e(λi-niμi)Ri

(10)

将式(10)代入式(2)，服务实例i的性能由指标ASF表示为：

(11)

根据定价模型式(4)，服务实例i的服务提供获得的平均收益为：

(12)

则单位时间内服务实例i获得的总收益为：

(13)

因此，最优化问题可形式为：

(14)

构造Lagrange函数:

(15)

其中：λ表示Lagrange乘子。

令dL/dni=0，i=0,1,2,…,m，则:

(16)

(17)

将式(17)代入式(14)中的约束条件中：

(18)

(19)

将式(19)代入式(17)，则：

(20)

假设每个服务实例的请求到达率以式(6)建立模型，然而，只有当服务实例请求到达率小于服务处理速率时式(6)才是有效的。否则，基于FIFO队列的响应时间将无法收敛，且响应时间会随着时间增加。因此，只有当到达率小于服务处理速率时，式(20)才成立。

λi

(21)

ni>ρi

(22)

图1(a)表明若ai等于Ai，收益将不再增长。因此，一旦响应需求被满足，对于服务实例i则无须继续增加资源量。由式(8)可知：

(23)

因此，式(22)与式(23)分别表示服务实例i对资源请求的下限与上限。

2.2 基于RSF的资源分配最优化

假设服务实例i分配ni台服务器，其性能需求为，设服务实例i的Ai响应时间为ri。根据式(6)，有：

ai=1-e(λi-niμi)ri

(24)

服务实例i的第Ai个响应时间为：

(25)

将式(25)代入式(5)，服务实例i的性能为：

(26)

根据定价模型式(5)，服务实例i的服务提供获得的平均收益为：

(27)

则单位时间内服务实例i获得的总收益为：

(28)

因此，最优化问题可形式为：

(29)

构造Lagrange函数：

(30)

其中：λ表示Lagrange乘子。

令dL/dni=0，i=0,1,2,…,m，

(31)

(32)

将式(32)代入式(29)中的约束条件：

(33)

(34)

将式(34)代入式(32)，则:

(35)

基于同样的原因，式(32)与式(35)分别表示服务实例i对资源请求的下限与上限。

3 实验分析

本节通过仿真实验对算法性能进行分析，实验工具为CloudSim[9]。实验中分别以合成数据集与追踪数据集作为两种服务请求类型进行实验测试。选择文献[10]中的Heuristic算法作为比较，服务收益作为算法性能比较的主要指标。ASF与RSF算法分别表示基于ASF与RSF的最优分配算法。相关参数与取值如表2所示。

表2 合成数据集测试参数

3.1 合成数据集测试分析

图2和图3表示三种算法在不同的定价机制下服务器资源量与收益间的关系。实验中时间间隔设置为1小时。可以看出，ASF与RSF算法均优于Heuristic算法。当服务器数量为70和80时，Heuristic算法得到的收益分别比ASF算法低75.5%和16.2%，服务器数据为70时，RSF算法收益比Heuristic算法高53.4%。同时，随着服务器数量的增加，Heuristic算法的曲线走势基本与ASF与RSF算法是接近的。当服务器数量到达90后，三种算法的收益接近相等，这主要是由于当云数据中心有充足的服务器资源提供给服务实例时，大多数服务实例将分配以上限值定义的相同资源量。明显地，当资源量相对不充足时，ASF与RSF算法具有更加明显的优势。因此，当资源量较少或服务实例量较大时，ASF与RSF算法可以优化资源分配得到更大的收益。

图2 ASF定价下的收益

图3 RSF定价下的收益

3.2 追踪数据集测试分析

追踪数据集选取文献[11]中互联网HTTP请求WWW服务器的相关数据集，如表3所示。本文将追踪时间划分为时间槽，步长为5 min。执行过程中，将每个时间槽中的到达请求进行统计，并根据先前记录预测下一时间槽的平均到达率，预测机制可形式化为：

λpost=λ+(λ-λpre)

(36)

其中：λpost表示下一时间槽的到达率，λpre和λ分别表示前一个时间槽的测量到达率和当前时间槽的测量到达率。

表3 追踪元数据

对于每个服务实例，服务器被划分为10组，每组作为一个FIFO等待队列。每个时间槽结束时，系统根据下一时间槽预测的到达率，重新在服务实例间进行资源分配。具体参数如表4所示。

表4 追踪数据集测试参数

图4和图5表明实验中部署90个服务器时每5 min收益变化的情况。总体看来，ASF与RSF算法均是优于Heuristic算法的。ASF与Heuristic算法每5 min的平均收益约为8.2 k＄和1.6 k＄，ASF算法约是Heuristic算法的4倍。RSF与Heuristic算法每5 min的平均收益约为8.7 k＄和6.6 k＄，前者约比后者高32%。同时可以看出，当资源量较少或服务实例量较大时，ASF与RSF算法可以优化资源分配得到更大的收益。在第47个时间槽时ASF与RSF算法的收益急剧减少，甚至低于Heuristic算法，这主要是由于服务到达率极端波动变化导致的。正如图6中，在第42至45个时间槽时到达率正在降低，而在46个时间槽又急剧增加。因此，通过式(36)预测到达率并非一定准确，可能会导致资源分配的不合理。同时，由于ASF和RSF算法的准确性及Heuristic算法可能出现的不合理性，ASF和RSF算法将更加依赖于对到达率准确的预测。

图4 ASF算法的收益进化过程

图5 RSF算法的收益进化过程

图6 服务请求到达

4 结 语

为了促进终端用户与服务提供者之间的协作关系，基于SLA形式的时间服务因子TSF，提出了基于定价机制的收益最大化算法。算法以队列理论建立了服务到达与服务提供模型，并通过Lagrange乘子法构建了最优化目标函数，并对函数进行了求解。实验结果表明，所提算法性能优于传统启发式分配算法，尤其在资源短缺的云计算环境下，算法具有更加明显的优势。

[1] Cusumano M. Cloud computing and SaaS as new computing platform[J].Communication of the ACM, 2011,53(4):27-29.

[2] Guo L, Zhao S, Shen S,et al. Task scheduling optimization in cloud computing based on heuristic algorithm[J].Journal of Networks, 2012,7(3):547-553.

[3] 苏凯凯,徐文胜,李建勇. 云制造环境下基于非合作博弈的资源优化配置方法[J].计算机集成制造系统,2015,21(8):2228-2239.

[4] 李陶深,张希翔. 云计算下区分服务的演化博弈调度算法[J]. 北京邮电大学学报,2013,36(1):41-45.

[5] 朱匆,刘元君,彭自然,等. 移动云计算中基于协作式博弈模型的资源分配方案[J].计算机应用研究,2014,31(3):912-916.

[6] 李卫平，武海燕，杨杰. 基于效益博弈的云计算资源动态可协调分配策略研究[J].计算机工程与科学，2016,38(1):57-61.

[7] Ergu D, Kou G, Peng Y,et al. The analytic hierarchy process: task scheduling and resource allocation in cloud computing environment[J]. The Journal of Supercomputing, 2013,64(3):835-848.

[8] Xu Zhongsheng, Shen Subin. A multi-objective optimization scheduling method in cloud computing[J]. Microcomputer Its Application, 2015,34(13):17-20.

[9] Rodrigo C, Rajiv R, Anton B, et al. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software: practice and experience, 2011,41(1):23-50.

[10] Mazzucco M. Revenue maximization problems in commecial data centers[D].PhD Thesis,University of Newcastle, Newcastle,UK,2014.

[11] Internet Traffic Archive[OL]. 2011-8-23. Http://ita.ee.lbl.gov/html/traces.html.

PROFITMAXIMIZATIONALGORITHMFORCLOUDRESOURCEALLOCATIONBASEDONQUEUETHEORY

Zheng Yuchao1Xia Xuewen1Ai Dongmei2

1(SchoolofSoftware,EastChinaJiaotongUniversity,Nanchang330013,Jiangxi,China)2(SchoolofMathematicsandPhysics,UniversityofScienceandTechnologyBeijing,Beijing100083,China)

For optimizing the profit of resource allocation, a resource allocation algorithm in resource pricing mechanism based on time service factor is proposed. First, the resource allocation problem was formalized as the queue model, and the profit maximization function was constructed. Then, the profit maximization function was solved by Lagrange multiplier method. Using the time service factor, our algorithm defined the pricing mode respectively by the assurance satisfaction factor and responded satisfaction factor. In addition, resource allocation was maximized by considering pricing, request arrival rates, resource service rates, and available resources. Experimental results show that compared with the traditional heuristic allocation algorithm, our algorithm yields higher returns, especially in the context of the scarcity of cloud resources. The proposed algorithm will have more advantages.

Queue theory Resource allocation Cloud computing Profit maximization

2017-01-09。江西省教育厅科研项目(GJJ150539)。郑宇超，讲师，主研领域：云计算及应用。夏学文，副教授。艾冬梅，高工。

TP393

A

10.3969/j.issn.1000-386x.2017.11.047