混合云中基于截止时间和费用约束的调度模型及方法

摘要

本发明公开了一种混合云中基于截止时间和费用约束的调度模型及方法，针对混合云调度中私有云利用率不高和公有云费用偏高的问题，基于性能和费用目标提出了两个调度策略—截止时间优先和费用优先策略，建立了混合云中的任务和资源模型，能够根据用户提交的任务需求自适应选择合适的调度资源，对截止时间要求比较高的任务可以优先调度至公有云，对费用要求高的任务可以优先调度至私有云，而且两种策略均满足截止时间和一定的费用约束。本文的两种调度策略在调度完成时间、费用、截止时间超出率和私有云利用率等方面均有很好的表现，尤其是当任务量比较大的时候，两种调度策略表现出更好的自适应性和优势。

说明书

技术领域

本发明涉及云计算领域，具体涉及一种混合云中基于截止时间和费用约束 的调度模型及方法。

背景技术

目前随着企业应用的扩展和数据量的倍增，尤其是高峰时段，企业现有集群 无法满足全部需求，因此需要大量增加硬件设施投入。但是除高峰时段外，大 部分设备利用率不高，造成了大量硬件设备的浪费和操作成本的增加。因此为 了减少硬件投入和维护成本，越来越多的企业选择混合云作为企业应用部署平 台。混合云中除了有企业自己的本地私有云，在私有云的计算能力等不能满足 要求时可以直接访问计算能力更高的公有云，如一些需要更强计算能力和存储 能力的应用，或在高峰时段私有云资源过载，不能同时处理更多的应用任务。 对此很多学者提出了一些解决方案，如对负载进行管理，或对数据进行划分优 化等，但是无论是针对资源负载还是数据应用，调度问题都成为其中非常关键 的一环：哪些应用需调度到公有云？哪些可以在本地私有云完成？如何尽可能 最大化私有云利用率和最小化公有云的租用费用？如何保证时间与费用这两个 目标？

目前关于混合云调度的研究主要从以下三个方面进行描述。

1)单一云的调度：

关于混合云调度问题的研究，现有一些研究的调度定位与本文的有一定差 别，它们是在混合云中分别研究公有云和私有云的调度问题，而不是在混合云 中如何将任务调度至公有云或私有云的问题。如文献[1]Bossche V D B, Vanmechelen K,Broeckhove J.Cost-efficient scheduling heuristics for  deadline constrained workloads on hybrid clouds，2011 IEEE Third  International Conference on Cloud Computing Technology and Science公 开了一种调度方法，针对混合云中的工作负载提出一种截止时间约束的费用优 化调度方法。文献[2]Qiu X,Yeow W L,Wu C,Lau F C.Cost-minimizing  preemptive scheduling of mapreduce workloads on hybrid clouds，2013 IEEE/ACM 21st International Symposium on Quality of Service，为最小化 费用提出了一种混合云中的抢占式调度方法，考虑了QoS约束，但是它同样是 分别研究私有云和外包费用。文献[3]Van D B R,Vanmechelen K,Broeckhove  J.Cost-optimal scheduling in hybrid iaas clouds for deadline constrained  workloads，Cloud Computing(CLOUD),2010 IEEE 3rd International  Conference on.也是针对公有云和私有云分别制定的工作流调度方法。

2)侧重费用：

现有研究中有一部分是侧重于讨论在截止时间约束下的费用优化问题。如 文献[4]Chopra N,Singh S.Deadline and cost based workflow scheduling  in hybrid cloud，2013 International Conference on Advances in Computing, Communications and Informatics(ICACCI),从云用户的角度出发提出了一个 外包调度模型，来最小化费用，但是它侧重于讨论公有云中的费用优化问题， 而且它对解决问题的规模有一定限制。文献[5]Hoseinyfarahabady M R, Samani H R D,Leslie L M,et al.Handling Uncertainty:Pareto-Efficient  BoT Scheduling on Hybrid Clouds，201342nd International Conference on  Parallel Processing(ICPP),应用部分关键路径提出了一种费用驱动的工作流 调度方法。文献[6]Genez T A L,Bittencourt L F,Madeira E R M.On the  Performance-Cost Tradeoff for Workflow Scheduling in Hybrid Clouds， Proceedings of the 2013 IEEE/ACM 6th International Conference on Utility  and Cloud Computing提出了两种基于混合云架构的调度优化策略，但它主要侧 重于费用的分析。

3)费用与性能平衡：

更多的研究是讨论性能与费用的平衡问题。如文献[7]Abrishami S, Naghibzadeh M,Epema D H.Cost-driven scheduling of grid workflows using  partial critical paths针对混合云中的不确定因素，提出了一种动态资源分 配方法，应用帕累托优化方法，同时考虑了费用和截止时间约束问题，但它的 时间复杂度较高，两个算法都大于等于O(n²)(n为任务个数)。文献[8]

Shifrin M,Atar R,Cidon I.Optimal scheduling in the hybrid-cloud， 2013 IFIP/IEEE International Symposium on Integrated Network Management (IM 2013)公开了一个自适应启发式工作流调度方法，它考虑了费用和截止时间 约束问题，但它只是针对混合云中的数据分析工作流进行调度。文献[9]Duan R, Prodan R,Li X.Multi-Objective Game Theoretic Scheduling of Bag-of-Tasks  Workflows on Hybrid Clouds，IEEE TRANSACTIONS ON CLOUD COMPUTING, 2014.2(1)公开了一个多目标的调度优化方法。它将执行时间和成本作为优化目 标，带宽和存储作为约束条件。文献[10]Rahman M,Li X,Palit H.Hybrid  heuristic for scheduling data analytics workflow applications in hybrid  cloud environment，2011 IEEE International Symposium on Parallel and  Distributed Processing Workshops and Phd Forum(IPDPSW)公开了一种混合 云调度方法，侧重于提高私有云的利用率，以期取得性能与费用的平衡。文献 [11]Javadi B,Abawajy J,Buyya R.Failure-aware resource provisioning  for hybrid Cloud infrastructure，Journal of parallel and distributed  computing,2012,72(10)公开的研究成果主要研究了在混合云中，当资源请求 失败时，应将任务调度至公有云还是私有云的调度问题。文献[12]Zuo X,Zhang  G,Tan W.Self-Adaptive Learning PSO-Based Deadline Constrained Task  Scheduling for Hybrid IaaS Cloud，IEEE Transactions on Automation Science  and Engineering,2014,11(2)公开了一个基于粒子群算法的自适应混合云调 度算法，它将公有云和私有云资源作为一个集合，讨论了截止时间的优化和IaaS 提供方的收益，但该方法仅考虑了云提供方的收益，没有考虑用户的花费问题。

综上所述，现有研究主要存在以下问题：

(1)现有关于混合云调度的研究方法中很多是侧重于混合云中单一云的调 度问题，如侧重混合云中公有云的调度，或侧重私有云的调度；

(2)现有针对混合云的调度研究的目标很多侧重于费用和性能中某一个指 标，如侧重公有云费用的减少，或侧重私有云利用率的提高；

(3)很多研究也考虑了费用与性能平衡问题，但是考虑的是公有云资源提 供方的成本费用，而不是用户的费用。

针对以上分析，本专利将针对这些问题，从用户的角度出发，针对用户对 截止时间和费用的需求差异，研究混合云中的调度问题，以提高私有云的利用 率和最小化公有云的花费。本专利提出的调度方法较简单，不涉及微分、积分 运算，复杂度相对较低。

发明内容

为解决现有技术中的不足，本发明提供一种混合云中基于截止时间和费用 约束的调度模型及方法，解决了现有混合云调度中多侧重于单一云的调度、费 用和性能中某一个指标及未考虑用户方的成本费用的问题。

为了实现上述目标，本发明采用如下技术方案：。

一种混合云中基于截止时间和费用约束的调度模型，其特征在于：包括用 户接口、任务请求管理器和调度管理器；用户接口用于将用户提交的任务请求 送至请求管理器，任务请求管理器用于将任务请求信息传输至调度管理器，调 度管理器根据任务需求，结合保存在调度管理器中的公有云和私有云的资源信 息，运用混合云调度方法将任务调度至公有云或私有云上，完成任务处理后将 结果返回给用户。

前述的一种混合云中基于截止时间和费用约束的调度模型，其特征是：所 述任务请求信息包括任务大小、所需数据量、要求完成的截止时间及预算费用。

前述的一种混合云中基于截止时间和费用约束的调度模型，其特征是：所 述公有云和私有云资源的信息包括资源的计算能力、传输能力、计算价格和传 输价格。

一种基于上述任一所述的一种混合云中基于截止时间和费用约束的调度模 型的调度方法，其特征是：包括步骤：

1)资源描述：

定义公有云资源R_u为：

R_u＝＜C_u,L_u，P_u,S_u,Q_u＞        (1)

其中，C_u为公有云资源计算能力，影响任务的计算时间；L_u为传输能力， 影响任务的传输时间；P_u为计算价格，S_u为存储价格，Q_u为传输价格；

定义私有云资源为：

R_r＝＜C_r,L_r＞          (2)

其中，C_r为私有云资源计算能力，影响任务的计算时间；L_r为传输能力， 影响任务传输时间；

2)任务描述：

设任务T_i为任务请求的一个单位，每个资源一次处理一个任务，则任务T_i定 义为：

T_i＝＜TD_i,TC_i,TL_i,TM_i＞          (3)

其中，TD_i为任务的截止时间；TC_i为任务大小；TL_i为任务计算所需信息 量；TM_i为任务的预算花费；

3)调度约束描述：

在任务调度时有两个约束：截止时间和费用；任务完成时间由任务计算时 间和传输时间两部分组成；任务T_i分别在公有云和私有云中的完成时间t_iR_u、 t_iR_r如下：

$t_i{R}_u=\frac{{\mathrm{TC}}_i}{C_u}+\frac{{\mathrm{TL}}_i}{L_u}---\left(4\right)$

$t_i{R}_r=\frac{{\mathrm{TC}}_i}{C_r}+\frac{{\mathrm{TL}}_i}{L_r}---\left(5\right)$

截止时间约束条件为t_iR_u≤TD_i和t_iR_r≤TD_i；

任务T_i的花费F_i计算公式为：

F_i＝TC_i×P_u+TL_i×Q_u+TL_i×S_u        (6)

费用约束条件为F_i≤TM_i；

4)费用优先调度策略：

费用优先调度策略是在满足截止时间约束条件下优先将任务调度至私有 云；在调度时首先判断任务T_i在私有云的完成时间约束，若t_iR_r≤TD_i，则调度 至私有云，否则调度至公有云，调度至公有云时，要满足费用约束条件F_i≤TM_i； n个任务的花费问题转化为以下优化问题，相关优化及约束描述如下：

最小费用公式为：

$\mathrm{Min}\underset{i=1}{\overset{n}{\Sigma }}{F}_i=\mathrm{Min}\underset{i=1}{\overset{n}{\Sigma }}({\mathrm{TC}}_i\times P_u+{\mathrm{TL}}_i\times Q_u+{\mathrm{TL}}_i\times S_u)---\left(7\right)$

公有云截止时间约束条件：

$t_i{R}_u=\frac{{\mathrm{TC}}_i}{C_u}+\frac{{\mathrm{TL}}_i}{L_u}\le {\mathrm{TD}}_i---\left(8\right)$

私有云截止时间约束条件：

$t_i{R}_r=\frac{{\mathrm{TC}}_i}{C_r}+\frac{{\mathrm{TL}}_i}{L_r}\le {\mathrm{TD}}_i---\left(9\right)$

费用时间约束条件：

F_i＝TC_i×P_u+TL_i×Q_u+TL_i×S_u≤TM_i       (10)

5)截止时间优先调度策略：

截止时间优先调度策略是在满足费用约束条件下优先将任务调度至完成该 任务较快的资源上；首先判断任务在公有和私有云资源的完成时间，将任务调 度至能尽早完成的资源上，在同等条件下，兼顾私有云优先的原则；调度至公 有云时，首先需要判断费用约束条件，相关优化及约束描述如下公式：

最小时间公式：

$\min (\underset{i=1}{\overset{n}{\Sigma }}{t}_i{R}_u,\underset{i=1}{\overset{n}{\Sigma }}{t}_i{R}_r)=\mathrm{Min}(\underset{i=1}{\overset{n}{\Sigma }}(\frac{{\mathrm{TC}}_i}{C_u}+\frac{{\mathrm{TL}}_i}{L_u}),\underset{i=1}{\overset{n}{\Sigma }}(\frac{{\mathrm{TC}}_i}{C_r}+\frac{{\mathrm{TL}}_i}{L_r}))---\left(11\right)$

公有云截止时间约束条件：$t_i{R}_u=\frac{{\mathrm{TC}}_i}{C_u}+\frac{{\mathrm{TL}}_i}{L_u}\le {\mathrm{TD}}_i---\left(12\right)$

私有云截止时间约束条件：$t_i{R}_r=\frac{{\mathrm{TC}}_i}{C_r}+\frac{{\mathrm{TL}}_i}{L_r}\le {\mathrm{TD}}_i---\left(13\right)$

费用时间约束条件：

F_i＝TC_i×P_u+TL_i×Q_u+TL_i×S_u≤TM_i          (14)。

前述的一种混合云中基于截止时间和费用约束的调度方法，其特征是：所 述公式(3)中任务大小为任务代码量。

前述的一种混合云中基于截止时间和费用约束的调度方法，其特征是：所 述费用的产生在公有云的租用上，费用包括计算费用、存储费用和传输费用。

前述的一种混合云中基于截止时间和费用约束的调度方法，其特征是：所 述步骤5)中私有云优先的原则为：若公有云和私有云的完成时间相同或相似， 任务将优先调度至私有云，否则调度至公有云；完成时间的相似度由阈值λ决定。

本发明所达到的有益效果：本发明基于性能和费用目标提出了两个调度策 略—截止时间优先和费用优先策略，建立了混合云中的任务和资源模型，能够 根据用户提交的任务需求自适应选择合适的调度资源，对截止时间要求比较高 的任务可以优先调度至公有云，对费用要求高的任务可以优先调度至私有云， 而且两种策略均满足截止时间和一定的费用约束；本文的两种调度策略在调度 完成时间、费用、截止时间超出率和私有云利用率等方面均有很好的表现，尤 其是当任务量比较大的时候，两种调度策略表现出更好的自适应性和优势。

附图说明

图1是混合云调度模型示意图。

具体实施方式

下面结合附图对本发明作进一步描述。以下实施例仅用于更加清楚地说明 本发明的技术方案，而不能以此来限制本发明的保护范围。

如图1所示，一种混合云调度模型，包括用户接口、任务请求管理器和调 度管理器；用户接口用于将用户提交的任务请求送至任务请求管理器，任务请 求管理器用于将任务请求信息传输至调度管理器，调度管理器根据任务需求， 结合保存在调度管理器中的公有云和私有云的资源信息，运用混合云调度方法 将任务调度至公有云或私有云上，完成任务处理后将结果返回给用户。

任务请求信息包括任务大小、所需数据量、要求完成的截止时间及预算费 用等；公有云和私有云资源的信息，包括两种资源的计算能力、传输能力、计 算价格和传输价格等。

一种基于上述混合云调度模型的混合云中截止时间和费用约束的调度方 法，

1)资源描述：

混合云中的资源分为公有云资源和私有云资源，本发明所述的资源主要代 表虚拟机。

定义公有云资源：模拟亚马逊云服务的模式，定义公有云资源R_u为：

R_u＝＜C_u,L_u，P_u,S_u,Q_u＞         (1)

其中，C_u为公有云资源计算能力，影响任务的计算时间；L_u为传输能力， 影响任务的传输时间；P_u为计算价格，S_u为存储价格，Q_u为传输价格(在此 主要指外部传输价格，因亚马逊云服务中内部传输不收费)。

定义私有云资源：私有云资源R_r仅考虑计算能力和传输能力，不考虑价格 因素：

R_r＝＜C_r,L_r＞        (2)

其中，C_r为私有云资源计算能力，影响任务的计算时间；L_r为传输能力， 影响任务传输时间。

2)任务描述：

设任务T_i为任务请求的一个单位，每个资源一次处理一个任务，则任务T_i定 义为：

T_i＝＜TD_i,TC_i,TL_i,TM_i＞             (3)

其中，TD_i为任务的截止时间，任务必须在该截止时间之前完成，并返回结 果；如果超出该时间，则认为该任务执行失败；TC_i为任务大小，在本发明中 用任务代码量来代替，该参数关系到任务的计算完成时间；TL_i为任务计算所 需信息量，直接影响任务的传输时间；TM_i为任务的预算花费，如果采用公有 云，所需费用不能超过该参数。

3)调度约束描述：

由任务定义可知，在任务调度时有两个约束：截止时间和费用，要满足这 两个约束条件必须要计算在混合云调度模型中任务的完成时间和花费。

任务完成时间由任务计算时间和传输时间两部分组成。由任务和混合云资 源的定义可计算任务T_i分别在公有云和私有云中的完成时间t_iR_u、t_iR_r如下：

$t_i{R}_u=\frac{{\mathrm{TC}}_i}{C_u}+\frac{{\mathrm{TL}}_i}{L_u}---\left(4\right)$

$t_i{R}_r=\frac{{\mathrm{TC}}_i}{C_r}+\frac{{\mathrm{TL}}_i}{L_r}---\left(5\right)$

因此截止时间约束条件为t_iR_u≤TD_i和t_iR_r≤TD_i。

本发明假设费用产生主要在公有云的租用上，主要由计算费用、存储费用 和传输费用三部分组成，任务T_i在公有云上的花费F_i计算公式如下：

F_i＝TC_i×P_u+TL_i×Q_u+TL_i×S_u         (6)

因此费用约束条件为F_i≤TM_i。

根据不同应用对性能和费用的需求差异，提出了两种调度策略：一种是以 费用优先的调度策略(简称为Cost-First)，一种是以截止时间优先的调度策略 (简称为Time-First)。

4)费用优先调度策略：

费用优先调度策略是在满足截止时间约束条件下优先将任务调度至私有 云。该策略在调度时首先判断任务T_i在私有云的完成时间约束，若t_iR_r≤TD_i， 则调度至私有云，否则调度至公有云，调度至公有云时，也要满足费用约束条 件F_i≤TM_i；n个任务的花费问题转化为以下优化问题，相关优化及约束描述 如下：

最小费用公式为：

$\mathrm{Min}\underset{i=1}{\overset{n}{\Sigma }}{F}_i=\mathrm{Min}\underset{i=1}{\overset{n}{\Sigma }}({\mathrm{TC}}_i\times P_u+{\mathrm{TL}}_i\times Q_u+{\mathrm{TL}}_i\times S_u)---\left(7\right)$

公有云截止时间约束条件：

$t_i{R}_u=\frac{{\mathrm{TC}}_i}{C_u}+\frac{{\mathrm{TL}}_i}{L_u}\le {\mathrm{TD}}_i---\left(8\right)$

私有云截止时间约束条件：

$t_i{R}_r=\frac{{\mathrm{TC}}_i}{C_r}+\frac{{\mathrm{TL}}_i}{L_r}\le {\mathrm{TD}}_i---\left(9\right)$

费用时间约束条件：

F_i＝TC_i×P_u+TL_i×Q_u+TL_i×S_u≤TM_i       (10)

5)截止时间优先调度策略：

截止时间优先调度策略是在满足费用约束条件下优先将任务调度至完成该 任务较快的资源上。首先判断任务在公有和私有云资源的完成时间，将任务调 度至能尽早完成的资源上，在同等条件下，兼顾私有云优先的原则。也就是说 如果在公有云和私有云的完成时间相同或相似，任务将优先调度至私有云，否 则调度至公有云。完成时间的相似度由阈值λ决定，因为该阈值涉及到用户的费 用问题，所以该阈值可以根据用户需求灵活设定。调度至公有云时，首先需要 判断费用约束条件，相关优化及约束描述如下公式：

最小时间公式：

$\min (\underset{i=1}{\overset{n}{\Sigma }}{t}_i{R}_u,\underset{i=1}{\overset{n}{\Sigma }}{t}_i{R}_r)=\mathrm{Min}(\underset{i=1}{\overset{n}{\Sigma }}(\frac{{\mathrm{TC}}_i}{C_u}+\frac{{\mathrm{TL}}_i}{L_u}),\underset{i=1}{\overset{n}{\Sigma }}(\frac{{\mathrm{TC}}_i}{C_r}+\frac{{\mathrm{TL}}_i}{L_r}))---\left(11\right)$

公有云截止时间约束条件：

$t_i{R}_u=\frac{{\mathrm{TC}}_i}{C_u}+\frac{{\mathrm{TL}}_i}{L_u}\le {\mathrm{TD}}_i---\left(12\right)$

私有云截止时间约束条件：

$t_i{R}_r=\frac{{\mathrm{TC}}_i}{C_r}+\frac{{\mathrm{TL}}_i}{L_r}\le {\mathrm{TD}}_i---\left(13\right)$

费用时间约束条件：

F_i＝TC_i×P_u+TL_i×Q_u+TL_i×S_u≤TM_i    (14)

混合云调度实验方法：

本发明利用云仿真软件Cloudsim来进行混合云调度的实验方法。使用云仿 真软件Cloudsim3.0来实现，该软件是一个完全免费的软件，所以可以为混合 云实验节省一大笔开支。目前关于混合云的实验中，其公有云部分均是采用实 际的亚马逊云服务来实现的，但是这样的实验方法成本比较高。本发明采用云 仿真软件Cloudsim3.0创建了A、B、C三个数据中心，将数据中心A作为私有 云，B和C作为公有云，为充分模拟混合云环境中私有云与公有云的差别，三个 数据中心的参数设置有一定差别：A、C数据中心中有20个虚拟机，B中有200 个虚拟机，并且虚拟机的配置也有不同，具体参数设置如表1所示。

表1三个数据中心虚拟机参数设置

利用混合云调度模型，用户通过用户接口将任务请求送至请求管理器，请 求管理器将任务请求信息传输至调度管理器，调度管理器根据任务需求，结合 保存在调度管理器中的公有云和私有云的资源信息，运用本发明的混合云调度 方法将任务调度至公有云或私有云完成，并将结果返回给用户。

实验表明，本发明公开的费用优先调度策略和截止时间优先调度策略与经典 的启发式算法Min-Min算法和基准调度方法FIFO相比，在调度完成时间、费用、 截止时间超出率和私有云利用率方面表现良好，在最好情况下四个指标的表现 分别有近50％、15％、72％和75％的提高，尤其是当任务数增多时表现出更好的自 适应性。

本发明提出的混合云中基于截止时间和费用约束的调度方法简单实用，只 需要对任务进行条件判断，不涉及积分微分操作，算法复杂度及优化上下限分 析如下：

两种调度策略仅需要对资源任务进行条件判断，所以费用优先和截止时间 优先的算法复杂度均为线性的，即O(n)，其中n为任务个数。

关于优化上下限问题，对于费用优先，最优情况为全部可以在私有云中完成， 此时达最优化，费用为0，费用优化上限为F_i(即任务在公有云的所有花费)， 最坏情况为全部要在公有云执行，费用优化下限为0；截止时间的优化同样分 为全部到公有云和私有云两种，因为都要满足截止时间约束，所以时间优化上 限为TD_i-t_iR_r，时间优化下限为TD_i-t_iR_u。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通 技术人员来说，在不脱离本发明技术原理的前提下，还可以做出若干改进和变 形，这些改进和变形也应视为本发明的保护范围。