Reliability, Rental-Cost and Energy-Aware Multi-Workflow Scheduling on Multi-Cloud Systems

• 科学工作流应用的需求多样且所需资源庞大，仅靠一个云服务提供商提供的云资源不足以满足需求，所以需要多云系统，用多云系统来满足大量且多样的用户需求。但是在多云系统中，有一些具有挑战性的问题，包括可靠性、租赁开销、能源消耗、多工作流调度、多云系统等，如何协调这些 “conflicting” 的因素，实现相对较优的调度，是这篇论文关注的问题。
• 输出单个最优解

Reliability, Rental-Cost and Energy-Aware Multi-Workflow Scheduling on Multi-Cloud Systems

• 创新点：既然要考虑可靠性、租赁开销、能耗等因素，那就把它们混合成一个参数，然后根据这个参数来对资源及资源的状态进行选择。
• 单调度解

introduction

• 科学工作流应用的需求多样且所需资源庞大，仅靠一个云服务提供商提供的云资源不足以满足需求，所以需要多云系统，用多云系统来满足大量且多样的用户需求。但是在多云系统中，有一些具有挑战性的问题，包括可靠性、租赁开销、能源消耗、多工作流调度、多云系统等，如何协调这些 “conflicting” 的因素，实现相对较优的调度，是这篇论文关注的问题。

problem formulation and modeling

multi-cloud resources

• 在多云系统中，由“broker”来对多个云服务商提供的资源进行管理，也由“broker”来进行工作流的调度处理。

  L. Heilig, E. Lalla-Ruiz, and S. Voß, “A cloud brokerage approach for solving the resource management problem in multi-cloud environments,” Computers & Industrial Engineering, vol. 95, pp. 16–26, 2016

• 云服务提供商计费机制：Amazon EC2 基于小时计费，Microsoft Azure 基于分钟计费，Google 前十分钟有个起步计费价，后面按分钟计费。

• 假设一个多云系统有 m 个云服务提供商，则总共能提供 m 种 IaaS，且对每一种 IaaS，有 k 种资源类型：。即第 m 个云服务提供商的第 k 种资源可以表示为。

• 资源处理器的不同性能状态：。、是资源处理器的频率和电压。

• 由此，一个资源实例的类型可以用来表示，性能状态可以用来表示，表示资源处于计算能力最高的性能状态。

multi-workflow

• 对于工作流应用，可以用来表示，是该工作流任务的集合，是工作流任务间关系的集合，是工作流应用的开始时间，是截止时间。

  

  • 表示任务是任务的前驱任务， 任务是任务的后继任务。

    、

workload

• 工作负载 = 所有工作流应用的总和。

  ，是工作流应用的总数。

task time

task execution time

• 任务执行时间和资源计算能力有直接的关系，所以对于异质的计算资源，资源实例处于不同的性能状态下，任务的执行时间也不同。假设是资源处理器在最佳性能时任务的处理时间，则对于资源处理器处于其他性能时，任务的执行时间可以用下式表示：，意味着资源处理器处于最佳性能，是一个小于 1 的数。

task transmission time

• 任务和之间的文件传输时间，表示需要传输的文件大小，任务运行在上，任务运行在上。

  表示提供资源的云服务提供商。

• 任务之间的传输时间有三种情况：

  • 任务在同一个云服务提供商的不同资源实例上：传输时间由云内的带宽计算
  • 任务在不同云服务提供商的资源实例上：传输时间由云间的带宽计算
  • 任务在同一个云服务提供商的同一个资源实例上：传输时间约等于 0

task start time

• 任务的最早开始执行时间：

• 指的是资源的结束时间，即资源开始可用的时间。

task expected finish time

• 任务的最早结束时间：

task latest finish time

• 任务的最晚结束时间：

• 也是任务的截止期限。等于直接后继任务的最晚完成时间 - 直接后继任务最短执行时间 - 任务传输时间

makespan

• 工作流应用的完工时间 makespan（MK）：

resource rental cost

• 租赁费用由 RB（Required Billing） 和单位计费时间的租赁价格决定。

• BI（Billing Interval） 是计费间隔；RB（Required Billing） 是该任务在相应资源上计费的总间隔；TC（Task Cost） 是租赁费用。

resource energy model

• 资源的能源消耗分为两种：静态的和动态的。

  • 是资源处理器的电流泄露。
  • 是资源处理器的动态系数。

  根据研究，CPU 的静态能源消耗是动态能源消耗的一部分，用这个静态能源系数来表示。

  由于工作时，CPU 的频率和电压也会随时间改变，所以加上时间的因素。

  最终，一段时间内任务在资源上执行的能源消耗可以用积分来表示：

reliability model

• 这篇文章用韦伯分布来对在多云系统资源上执行的任务的可靠性进行建模。

  θ 是比例参数：失效的平均时间。

  β 是显示资源的故障行为的斜率参数，通过调整 β 的值，可以展示资源的不同的故障行为，来得到多组实验数据。

  $\left{\right.$

  用故障率 λ 替代 1/θ，上式可以转变为：

  $\left{\right.$

• 处理器 processor 的故障率遵循泊松分布，可以用下式表示：

• 所以最后，任务在资源上执行的可靠性可以用下式表示：

  

  可以看到：

  • 当处理器的频率下降时，λ 会上升，任务的执行时间也会上升，所以任务执行的可靠性会下降。
  • 当处理器的频率上升时，任务执行的可靠性会上升，但是处理器的能耗会上升。

  所以任务执行的可靠性和能耗是相互 conflict 的因素。

task duplication

• 当任务的可靠性较低时，可以用任务复制（task duplicate）来提高任务执行的成功率，结果就是，对于某种任务，它的可靠性可以用下式来表示：

  

  更具体一点，由于任务副本会在不同的资源上执行，所以可靠性具体表示为：

  

  最终，一个工作流的可靠性即为其所有任务可靠性的乘积：

proposed algorithm

• 调度框架工作过程：

  1. 用户将工作流应用提交给 Apps 队列，等待被调度。
  2. Workflow Analyzer 会计算工作流应用的各种参数，包括 LFT、EST、EFT，然后给工作流的所有任务分配截止时间（deadline allocation），并将该工作流的就绪任务转移到任务池中。
  3. 接着由 Scheduler 基于定义好的算法进行调度，该调度会考虑到可靠性、能耗、租赁费用、截止时间约束、任务复制等。
  4. Scheduler 从多个云服务提供商那里选择合适的资源（通过考虑前面的各种因素）给任务进行执行。

• 将该调度框架和 workflowsim 作类比：

  1. 上面的第一步类似于用 WorkflowPlanner 的 WorkflowParser 对 DAX 文件进行转换，将 DAX 文件转换为工作流。

  2. 第二步类似于 WorkflowEngine 将准备执行的任务发送给 WorkflowScheduler 。

  3. 第三步类似于 WorkflowScheduler 根据调度算法对任务进行调度。

     在 PlanningAlgorithm 中，调度结果是在任务开始执行前就已经有的（由 WorkflowPlanner 得到调度结果），并不需要用到 WorkflowScheduler 的调度算法。

  4. 第四步类似于 WorkflowScheduler 将调度好的任务提交给 WorkflowDatacenter 执行。

deadline allocation

• 在分配截止时间时，每个工作流应用的截止时间都会被划分为其每个任务的截止时间。

  根据任务等级来划分截止时间。

  A. Taghinezhad-Niar, S. Pashazadeh, and J. Taheri, “Energy efficient workflow scheduling with budget-deadline constraints for cloud,” Computing, 2022.

• 工作流应用的所有任务会被划分为不同的等级，对于同一等级的任务，它们之间没有相互依赖的关系。

  每个任务的等级用下式来计算：

  

  对于任务的等级，开始任务的最大，为。结束任务的最小，为。

  对于同一等级的任务，其集合用下式表示：

• 对于每个工作流应用的总执行时间，用下式表示：

  • 表示拥有最高计算能力且在最佳性能状态时的资源。

  对于等级为的工作流的任务，其总执行时间为：

• 在有了每个等级的任务的总执行时间后，我们就可以给不同等级的任务分配截止时间：

  • 注意：任务的等级越大，越大。

  下面是一个 deadline allocation 的简单例子：

  

• deadline distribution 算法：

  

scheduler algorithm

• 调度任务的大概流程是：将之前计算好截止时间的每个任务进行排序，截止时间越早的任务排在越前面，然后 scheduler 将任务调度给资源执行，那么该把任务调度给那种资源呢？（毕竟有多个云服务提供商，每个云服务提供商都有多种资源），就要考虑到之前所说的租赁费用、能源消耗和可靠性。

  通过对这三种因素进行权重占比平衡，得到一个数值，通过数值的比较来决定到底将任务调度给哪个具体的资源。

• 首先来看租赁费用（rental cost）、能源消耗（energy consumption）和可靠性（reliability）的度量指标：

  

  另外，通过可以看到，一个工作流的可靠性取决于它的任务的数量，如果工作流的可靠性低，则为了保证任务的成功执行，可能相同的任务就要执行多次，反而会增大租赁开销和能耗，所以，对于任务数量多的工作流，可靠性因素的权重占比就应该高于租赁费用和能源消耗。

  • 考虑用变化的权重参数来动态展示可靠性的重要程度。引入来动态展示可靠性的重要程度：，是工作流的任务数量。

  • 因此，最终综合下来的评价指标可以用下式表示：

    

    这个指标的值越大的资源，越被优先分配给将要执行的任务。

• 还有任务的复制问题，对于那些可靠性低的任务，在该任务调度结束后，duplication algorithm 会评估是否与必要对该任务进行复制，我们用这么一个参数来进行评价：

  ，该参数考虑了工作流的任务数量，资源的故障行为、工作流在执行任务前的可靠性和在执行了任务后的可靠性。

  如果这个参数的值大于一个设定的值（duplication threshold），就对该任务进行复制。

• 最后调度算法如下：

  

experimental results and analysis

configurations

• dataset: scientific workflow

  

• 故障率 λ：

  • Amazon EC2：0.001
  • Google ：0.002
  • Microsoft Azure：0.003

  H. Hu, Z. Li, H. Hu, J. Chen, J. Ge, C. Li, and V. Chang, “Multi-objective scheduling for scientific workflow in multicloud environment,” Journal of Network and Computer Applications, vol. 114,no. February, pp. 108–122, 2018.

  K. K. Chakravarthi, P. Neelakantan, L. Shyamala, and V. Vaidehi,“**Reliable budget aware workflow scheduling strategy on multi-cloud environment,**” Cluster Computing, vol. 4, 2022.

• resource instances configuration：

  

  

  

• DVFS：

  

• 云内带宽、云间带宽。

• workloads：

  

  工作流应用的到达速率遵循泊松分布，到达率被认为是 1个工作流应用/分钟。

• 实验组设置：

  1. 工作负载相同，即工作流应用的个数相同（设置为 200，即），但是工作流应用的任务数不同，在此基础上对比算法间的租赁费用、可靠性和能耗。

  2. 工作负载不同，即工作流应用的个数不同，但是工作流应用的任务数相同（设置为 medium），在此基础上对比算法间的租赁费用、可靠性和能耗。

  3. 工作负载和工作流任务数相同（设置为 500，即），但是资源故障率和故障行为不同，即调整 β 的值，在此基础上对比算法间的租赁费用、可靠性和能耗。

     -> ？β越大，可靠性越高？

• 每次实验做十次，取平均值。

metrics

• the reliability of a workload：
• the rental cost：
• energy consumption

experimental results

• the same workload（）with different task sizes：
  • 在租赁计费方面：EERS > FCWS > REMSM-DVFS > REMSM，故 REMSM 最优
  • 在可靠性方面：REMSM ≈ EERS > REMSM-DVFS > FCWS，故 REMSM 最优
  • 在能耗方面：FCWS > EERS ≈ REMSM > REMSM-DVFS，故 REMSM-DVFS 最优
• different workload with medium workflow task sizes：
  • 在租赁计费方面：EERS > FCWS > REMSM-DVFS > REMSM，故 REMSM 最优
  • 在可靠性方面：REMSM ≈ EERS > REMSM-DVFS > FCWS，故 REMSM 最优
  • 在能耗方面：FCWS > EERS ≈ REMSM > REMSM-DVFS，故 REMSM-DVFS 最优
• different fault rate and resource reliability behavior inwith medium task sizes
  • 在租赁计费方面：EERS > FCWS > REMSM-DVFS > REMSM，故 REMSM 最优
  • 在可靠性方面：REMSM ≈ EERS > REMSM-DVFS > FCWS，故 REMSM 最优
  • 在能耗方面：FCWS > EERS ≈ REMSM > REMSM-DVFS，故 REMSM-DVFS 最优