一种云计算资源的多目标优化的调度方法*

徐忠胜，沈苏彬

（南京邮电大学计算机学院，江苏南京210003）

一种云计算资源的多目标优化的调度方法*

徐忠胜，沈苏彬

（南京邮电大学计算机学院，江苏南京210003）

云计算通过虚拟化技术将基础设施硬件资源虚拟化，以动态可缩放的方式提供给用户。云计算基础设施规模不断增加导致资源调度系统负载不均衡，从而造成资源浪费等问题。提出多目标优化资源调度策略和相应的算法，试图同时满足多个资源调度优化目标，如减少资源浪费，降低服务等级约定（SLA）违背率、保持系统负载均衡等。通过仿真实验，验证了多目标优化资源调度的策略能够在多个相互冲突的目标之间实现最优权衡。

云计算；多目标优化；虚拟机；资源调度

0 引言

云计算是一种新的计算服务模式，可以在不同的抽象级别实现，这取决于云提供商提供的特定服务，如存储、计算等。本文主要研究基础设施作为服务（IaaS）[1]的云的资源调度，IaaS云主要通过虚拟化技术[2]将基础设施提供给用户，包括以虚拟机方式的计算服务、虚拟磁盘方式的存储服务、虚拟机交换机的网络服务。随着计算机与网络技术的高速发展，互联网用户不断增多，计算机基础设施规模也不断扩大，导致资源浪费不断增加，数据中心的负载失衡严重。云环境的动态特性使得云提供商向用户提供的云服务不能严格满足服务等级约定（SLA）。而大多数的解决方案只涉及某一方面的目标优化，比如通过服务器的整合降低数据中心的能源消耗，但是降低了用户需求的满意度。有的研究工作为了减少SLA违背率，将虚拟机分散放在尽可能多的服务器上，降低了资源的利用率，这是因为不同的优化目标之间是相互冲突的。

针对以上问题，本文提出了多目标优化的资源调度策略，该方法在多个相互冲突的目标之间实现最优权衡，如降低服务等级协议违背率、减少资源浪费和负载均衡等。

1 相关工作分析

在云计算基础设施中，虚拟机资源的分配是一个重要研究课题。目前已有一系列研究成果，比如参考文献[3-4]通过服务器的整合来降低数据中心的能源消耗，但是增加了服务等级约定违背率。参考文献[5]中提出了一种基于遗传算法的负载均衡调度策略，该算法计算出在部署请求的虚拟机资源之后对系统的影响，并选择最小影响的解决方案，避免进行在线迁移，但是在资源分配过程中存在资源浪费的问题。Wood[6]描述了动态监测系统中CPU、内存资源、网络带宽的利用率，提出了白盒测试与黑盒测试的方法，并重点研究了通过虚拟机迁移进行重映射解决负载失衡的问题，但是增加了SLA违背率。参考文献[7]中提出通过在虚拟机之间转移工作负载，优化各个虚拟机的资源需求，在任务执行之后减少虚拟机的迁移，避免系统性能的降低，但是同样存在资源浪费的问题。

现有研究中很少将资源浪费、保证服务等级约定和负载均衡进行综合考虑，实现虚拟机资源调度的多目标优化。大部分的研究只是将多目标优化问题转化为若干个单目标优化问题分阶段解决，很少是同时对多个目标进行优化的。

2 资源优化调度建模

2.1 数学模型

IaaS中虚拟机资源分配问题可以描述成在动态云环境中多维装箱问题。本文构建了数学模型，使用元组q=＜t，VMSET，ts＞表示各个虚拟机资源调度请求，其中t表示虚拟机资源请求到达的时刻，VMSET表示要申请的虚拟机集，ts表示虚拟机的生命周期。

一个简单的例子如图1所示。涉及到7个虚拟机资源请求，如虚拟机请求{2，{1，2}，6}表示请求在时刻2到达，申请了序号为1与2两个虚拟机，虚拟机的生命周期为6个时间单元。在时刻15时虚拟机6、7还在运行，1～5号虚拟机被删除了。

图1 虚拟机资源分配实例

本文考虑一个云数据中心的基础设施由M个不同的物理主机组成，每个物理主机由K种资源表示（如CPU，内存，网络带宽，磁盘等）。每个物理主机j对每种资源k有一个已知容量Cjk，其中j∈{1…M}，k∈{1…K}。例如规定CPU资源由索引值1表示，即k=1时表示为CPU资源。

2.2 资源调度的优化目标

（1）减少资源浪费：不同的虚拟机资源调度策略对物理主机的剩余资源影响程度不同。考虑到将来虚拟机资源请求，各个物理主机上的剩余资源应该在不同维度资源之间保持均衡。否则，可能会阻止未来的虚拟机资源请求，从而造成浪费资源。

（2）降低服务等级约定（SLA）违背率：满足用户服务质量是衡量云计算服务的重要指标。服务质量请求通常表示为服务等级约定（SLA），在云系统中服务等级约定由最大响应时间或者最小吞吐量决定。

（3）负载均衡：在云环境中将资源分配给虚拟机，要使得所有物理主机上的资源利用率均衡。

3 多目标优化的资源调度算法

多目标优化资源调度算法由两个资源调度过程组成：虚拟机资源初始化分配与虚拟机动态迁移。

3.1 综合权衡值

在提出多目标优化算法之前，本文引入多目标优化算法核心的计分函数，称为“综合权衡值”，其目的是为了衡量在过去的TM时间内服务等级约定（SLA）违背率程度、资源浪费的程度与数据中心负载均衡度。所以“综合权衡值”主要由服务等级约定（SLA）违背率、资源浪费的程度以及数据中心负载均衡度三部分的效用函数组成。

第一个是服务等级约定违背率的效用函数，在一个给定的时刻，定义函数U衡量服务等级约定的违背率，公式（1）表示当虚拟机集合V部署在物理主机h上时，函数U（H，V，T）衡量在t时刻对于物理主机h的CPU资源需求的不满意度。

式中，ri（t）表示虚拟机i请求的CPU资源量，ai（t）表示物理主机分配给虚拟机i请求的CPU资源量。它的范围值在[0，1]。

第二个是资源浪费程度的效用函数，如公式（2）所示，在一个给定的时刻，定义函数L衡量虚拟机集合V部署在物理主机h上时，物理主机h上的资源浪费程度。

式中，Rk代表第k种资源的归一化的剩余资源，即剩余资源占总资源的比率；用下标z表示多维资源中最小归一化的剩余容量的资源。在服务器上浪费的剩余资源被计算为最小的归一化剩余资源与其他剩余资源差异的总和，它的值范围为[0，1]。

最后一个是数据中心的负载均衡效用函数。更具体地说，就是数据中心中物理主机之间资源负载的均衡程度。在一个给定的时刻，定义函数B衡量数据中心的负载均衡度，如公式（3）表示虚拟机集V部署在物理主机h上时，数据中心的负载均衡程度。

式中，M为所有物理主机节点的数量，CPUj（t）表示物理主机j在t时刻的CPU利用率，CPUavg为M个物理主机节点的CPU利用率均值。

本文使用DR表示“综合权衡值”，如公式（4），表示

式中α1+α2+α3=1，α1、α2、α3是各个子目标的权衡值，通过设置α1、α2、α3的大小可以权衡各个子目标实现的程度。

3.2 虚拟机资源初始化调度算法

虚拟机资源调度初始化分配算法过程如图2所示。在过去的TM时间内多目标优化的综合效用函数性能指标。

图2 虚拟机资源初始化分配过程

（1）首先根据指定的过滤方法（例如物理主机剩余资源不能满足用户需求）对所有可用的物理主机节点进行过滤，得到满足过滤条件的物理主机节点集合。

（2）计算出过滤后所有物理主机“综合权衡值”，然后将所有过滤后的物理主机节点按照“综合权衡值”的大小进行升序排列。

（3）选择“综合权衡值”最小的物理主机给用户分配虚拟机资源。

3.3 虚拟机动态迁移算法

虚拟机的迁移涉及到确定迁移的时机、虚拟机的选择和虚拟机的放置问题。

通过实时监测物理主机，确定虚拟机迁移的时机。为了防止暂时的越界而发生的虚拟机迁移，在资源监测过程中可以设定一个固定大小的时间段，并且资源利用率在这个时间段内按照固定的时间间隔采样，如果在采样结果中资源利用率超过门限值的次数大于设定的次数，则开始预测下一次的资源利用率，当下一次资源利用率也超过了门限值时触发虚拟机的迁移。本文使用了时间序列预测技术[8]里的自回归模型AR（n），此模型可以预测未来的资源利用率。

在确定哪个物理主机需要迁移虚拟机后，系统会选择将该物理主机上的虚拟机迁移出去。此时，需要讨论虚拟机的选择与虚拟机的放置策略。关于虚拟机的选择以及放置，可以通过以下算法获得。

虚拟机动态迁移算法：

算法思路：在确定哪个物理主机需要迁移虚拟机之后，考虑该物理主机上哪一个虚拟机需要迁移，然后确定迁移到哪一个物理主机上。算法中第一层循环为遍历迁移源物理主机上的所有虚拟机，第二层循环是遍历除了迁移源物理主机之外的所有物理主机节点。经过两次循环，首先计算出在迁移之前，迁移源物理主机与迁移目的物理主机的综合权衡值的和值，然后计算出迁移之后源物理主机与目的物理主机的综合权衡值的和值，最后计算出虚拟机从源物理主机迁移到目的物理主机的迁移值。迁移值被定义为两个综合权衡和值之间的差异。最后，取出所有迁移值中的最高值，只有迁移值为正时才会考虑进行迁移。

4 测试及结果分析

4.1 仿真建立

本节采用CloudSim[9]云计算仿真平台进行多目标优化的资源调度算法的验证，并提供了多目标优化的资源调度算法与其他不同算法相比较的结果。CloudSim是由澳大利亚墨尔本大学的网格实验室和Gridbus项目推出的云计算仿真软件。

仿真实验的硬件环境：Intel Core i5，CPU主频为2.66 GHz，内存4 GB，硬盘500 GB。软件环境：Windows 7操作系统，MyEclipse 10.7和CloudSim-3.0.3，以及Java1.8.0开发工具。在多目标优化资源调度算法中设置门限值为80%，物理主机节点监测的周期为3 s，对系统资源的采样间隔为4 s，一次监测过程的时间长度为1 min，即一次监测过程中有20次历史监测数据。当超过门限值的次数大于等于10次就触发告警。任务的数量分三种情况模拟：200个、400个、600个。

这个实验主要分析本文提出的多目标优化算法的有效性，比较了以下4种算法：（1）单目标减少资源浪费算法；（2）单目标降低SLA违背率算法；（3）单目标负载均衡算法；（4）多目标优化资源调度算法。

4.2 仿真结果与分析

如图3、图4、图5所示描述了在不同的资源调度算法下的资源浪费程度、SLA违背率以及数据中心的不均衡度。资源浪费程度越高，表示各种资源利用的差距越大。SLA违背率越低说明用户的服务质量越高。数据中心负载均衡度越低代表负载均衡效果越好。由图可知采用减少资源浪费的算法时资源浪费的程度最低，使用减少SLA违背率算法时SLA违背率最低，使用负载均衡算法时数据中心不均衡度是最低的，这是因为在执行单目标优化问题时，单目标优化算法能得出最优解。由图3、图4、图5可知，虽然单目标优化算法在各自的优化目标上取得最优解，但是单目标算法在其他目标实现的效果上比较差，如虽然使用减少SLA算法时SLA违背率最低，但是资源利用率很低。这是因为在多目标优化的问题中，各个子目标之间有时是冲突的，一个解不能同时使所有的子目标达到最优，所以需要在各个目标之间做好协调权衡。

多目标优化算法就很好地解决了多个目标之间相互冲突的问题，虽然多目标优化算法不能使数据中心取得最低的资源浪费程度、最低的服务等级约定违背率与最低的不均衡度，但是在各个目标优化的效果比较好。如图5所示，多目标优化资源调度算法的数据中心的不均衡度比负载均衡算法的值高，但是低于减少SLA违背率算法与减少资源浪费算法的值。

图3 不同资源调度算法下资源浪费程度

图4 不同资源调度算法下SLA违背率

图5 不同资源调度算法下数据中心不均衡度

5 总结

本文针对多目标优化的资源调度问题，提出了多目标资源优化的资源调度策略。多目标优化资源调度的策略能够在多个相互冲突的目标之间实现最优权衡。通过仿真实验验证了多目标资源优化的资源调度策略的有效性。

[1]BHARDWAJ S，JAIN L，JAIN S.Cloud computing：a study of infrastructure as a service（IAAS）[J].International Journal of Engineering and Information Technology，2010，2（1）：60-63.

[2]UHLIG R，NEIGER G，RODGERS D，et al.Intel virtualization technology[J].Computer，2005，38（5）：48-56.

[3]CHEN Y，DAS A，QIN W，et al.Managing server energy and operational costs in hosting centers[C].ACM SIGMETRICS Performance Evaluation Review，ACM，2005，33（1）：303-314.

[4]KUSIC D，KEPHART J O，HANSON J E，et al.Power and performance management of virtualized computing environments via lookaheadcontrol[J].Cluster Computing，2009，12（1）：1-15.

[5]HU J，GU J，SUN G，et al.A scheduling strategy on load balancing of virtual machine resources in cloud computing environment[C].Parallel Architectures，Algorithms and Programming（PAAP），2010 Third International Symposium on.IEEE，2010：89-96.

[6]WOOD T，SHENOY P J，VENKATARAMANI A，et al. Black-box and Gray-box strategies for virtual machine migration[C].NSDI，2007：17-17.

[7]TANG C，STEINDER M，SPREITZER M，et al.A scalable application placement controller for enterprise data centers[C].Proceedings of the 16th International Conference on World Wide Web，ACM，2007：331-340.

[8]BOX G E P，JENKINS G M，REINSEL G C.Time series analysis：forecasting and control[M].New York：John Wiley &Sons，2013.

[9]CALHEIROS R N，RANJAN R，BELOGLAZOV A，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.

A multi-objective optim ization scheduling method in Cloud com puting

Xu Zhongsheng，Shen Subin
（School of Computer，Nanjing University of Posts and Telecommunications，Nanjing 210003，China）

Cloud computing infrastructure virtualizes hardware resource by virtualization technology，and provides it to users in scalable way.The increasing size of cloud computing infrastructure results in the waste of resources because of system load imbalance and other issues.This paper proposes a multi-objective optimization of resource scheduling policies and a related algorithm that can simultaneously achieve multiple objectives，such as reducing the waste of resources，reducing the service level agreement（SLA）and keep the system load balance.Simulation results show that the multi-objective optimization of resource scheduling method can achieve the optimal trade-offs among multiple conflicting goals.

Cloud computing；multi-objective optimization；virtual machine；resource scheduling

TP393

A

1674-7720（2015）13-0017-04

2015-03-02）

徐忠胜（1989-），通信作者，男，硕士研究生，主要研究方向：计算机网络。E-mail：xuzhongsheng722@sina.com。

江苏省未来网络前瞻性研究资助项目（BY2013095-1-08）

沈苏彬（1964-），男，研究员，博士生导师，主要研究方向：计算机网络、下一代电信网及网络安全。