Running Noob

Do Something Meaningful

0%

Reliability-Aware Cost-Efficient Scientific Workflows Scheduling Strategy on Multi-Cloud Systems

发表于 更新于 分类于
本文字数： 7.3k 阅读时长 ≈ 7 分钟
  • 考虑了一个多云的环境，不同的云服务提供商有不同的计费机制。
  • 这篇论文考虑了多云场景下工作流调度的开销和可靠性（把传输可靠性也考虑进去了）。
  • 确定任务执行顺序用的是 Cost-Efficient Bottom Level，cb_level，可以看作是一个创新点。
  • 值得注意的是，Reliability, Rental-Cost and Energy-Aware Multi-Workflow Scheduling on Multi-Cloud Systems 参考了这篇论文，所以它们存在一些相似的地方，比如：在选择虚拟机时，将调度目标混合成一个参数，然后把任务调度给参数最小的那个虚拟机；在任务复制时，如果任务的 hazard rate 大于一个常数，就将任务备份。
  • 输出单个最优解

Reliability-Aware Cost-Efficient Scientific Workflows Scheduling Strategy on Multi-Cloud Systems

  • 考虑了一个多云的环境，不同的云服务提供商有不同的计费机制。
  • 这篇论文考虑了多云场景下工作流调度的开销和可靠性（把传输可靠性也考虑进去了）。
  • 确定任务执行顺序用的是 Cost-Efficient Bottom Level，cb_level，可以看作是一个创新点。
  • 值得注意的是，Reliability, Rental-Cost and Energy-Aware Multi-Workflow Scheduling on Multi-Cloud Systems 参考了这篇论文，所以它们存在一些相似的地方，比如：在选择虚拟机时，将调度目标混合成一个参数，然后把任务调度给参数最小的那个虚拟机；在任务复制时，如果任务的 hazard rate 大于一个常数，就将任务备份。

Introduction

  • 阐述了为什么要使用多云，多云系统下的系统可靠性以及由于是多云环境，会有多种付费机制，将这些机制整合起来，考虑如何对科学工作流进行调度以使得开销最小。

System Model

Multi-Cloud Systems Scheduling Architecture

  • 用户将他们的科学工作流应用请求提交给第三方机构（在 WorkflowSim 中对应 WorkflowPlanner + WorkflowEngine + WorkflowScheduler），该机构负责用户和云服务提供商之间资源的管理。

  1. 用户提交的科学工作流应用请求首先进入 Application Queue 模块，等待被第三方机构调度；

  2. Third party resources negotiation layer 模块可以监视、协商和管理云服务提供商的资源；

    • Reliability Analysis 模块可以评估多云系统中虚拟机实例上任务执行的可靠性；
    • Task Execution Cost Estimation 模块可以根据不同的
    • 云服务商的计费机制来评估任务执行的开销；
    • Schedule and Dispatch 模块可以根据任务执行可靠性信息来做出调度策略；

  3. Multi-Cloud 模块用来执行被调度过来的工作流任务。（在 WorkflowSim 中对应 WorkflowDatacenter）

  • 多云系统被建模为 m 个异构的 IaaS 云服务提供商的有限集合：

    Misplaced &\begin{matrix} \Psi = {vm_{1,1}, & vm_{1,2}, & …, & vm_{1,K1},\ \qquad vm_{2,1}, & vm_{2,2}, & …, & vm_{2,K2}, \ \qquad …,\ \qquad vm_{m,1}, & vm_{m,2}, & …, & vm_{m,Km} }\ \end{matrix}

    • 每台虚拟机都有相应的计算能力

    • 对于同一个云服务提供商的虚拟机，它们用虚拟通信网络进行通信。

      • 假设云服务提供商 k 内部的带宽为

      对于不同云服务提供商的虚拟机，它们用商业通信网络进行通信。

      • 假设云服务提供商 k、z 之间的带宽为

    • 假设云服务提供商有一个“已经工作时间”

Scientific Workflow Model

    • 代表的是任务的集合。
      • 表示任务的计算数据大小
    • 表示任务是任务的直接前驱任务，任务是任务的直接后继任务。
      • 表示任务和任务之间的传输数据大小
  • 任务在虚拟机上的执行时间
  • 任务在虚拟机上的开始时间（没有考虑虚拟机的资源空闲时间？）
    • 是边的数据传输完成时间
  • 任务在虚拟机上的结束时间
  • 假设任务在虚拟机上执行，任务在虚拟机上执行，则边的数据传输时间 $EC(e_{i,j})=\left{
    \right.$
  • 边的数据传输完成时间

Scheduling Problem

Task Execution Reliability Analysis

  • 这篇论文用的是韦伯分布来评估虚拟机上任务执行的可靠性。

    这篇论文假设传输也不一定是可靠的。

  • 多云系统中虚拟机的可靠性建模为 $\left{\right.$

    • 其中是可靠性函数，是 hazard rate function。
    • 、是韦伯分布的参数，对于每台虚拟机，都有其不同的、：
    • 相应的，对于云和云之间的传输可靠性，也有其韦伯分布参数：

  • 所以，任务在虚拟机上执行的可靠性为

Billing Mechanisms

  • 计费机制的不同组合可能会导致不一样的任务执行开销。
    • 微软的 Microsoft Azure 计费机制是按分钟收费
        • 任务在虚拟机上的执行开销为
        • processing time：
        • billing mechanism：
    • 亚马逊的 Amazon EC2 计费机制是按小时收费
      • $CE(v_j,vm_{k,l})=\left{
        \right.$ ——> 不是很懂？啥意思
        • 是计费间隔
    • 谷歌的 Google Compute Engine 计费机制是前十分钟有一个起步价，然后后面按分钟收费
  • 这篇论文采用的计费机制是前十分钟采用亚马逊的，后面采用微软的

Problem Formulation

  • 如果任务被调度给虚拟机，则，否则。

  • 工作流的总租赁开销

  • 另外，如果任务执行的 hazard rate 过高，就会对该任务进行备份，所以

    • 这篇论文认为如果任务已经有了一个备份任务，则该任务的可靠性就已经很高，设置为1

      所以 $R[v_i]=\left{
      \right.$

    最终，工作流执行的可靠性为

  • 这篇论文的问题描述为：

    • Minimize：

      makespan、Cost

    • Maximize：

      Reliab

    • Subject to

      $\left{
      \right.$

The Proposed Scheduling Algorithm

  • Fault-tolerant Cost-efficient Workflow Scheduling algorithm（FCWS）：容错型、经济高效的工作流调度算法。包含两个主要阶段：
    1. Cost-Efficient Bottom Level：用 cb_level 来对提交的任务进行优先级排序
    2. FCWS：对队列中的任务进行调度，对每个任务：要计算其在不同的云服务提供商的每个虚拟机上的开销、可靠性，由此得到指标SM（在计算 SM 时，α=0.8，β=0.2，为什么这么取，没有给出理由），然后将任务调度给 SM 最小的虚拟机；接着计算任务在该虚拟机上执行的失败率，如果失败率大于一个常数，就要将该任务备份到另外的虚拟机上。

Cost-Efficient Bottom Level

  • 这一阶段用于确定工作流中任务的执行顺序。

  • 这篇论文用任务执行的租赁开销（cost-efficient bottom level，cb_level）来确定任务的执行顺序。由于是多云场景，采用不同的云服务提供商的计费机制可能会有不同的执行顺序，所以这篇论文用 Microsoft Azure 的计费机制的中位数来作为确定执行顺序的依据。

FCWS algorithm

  • 这一阶段用于确定将任务调度给哪台虚拟机。

  • 因为调度目标是最小化 Cost、最大化 Reliability，所以将两种调度目标混合起来，提出一种 cost and reliability aware scheduling metric。

    $\left{
    \right.$

    • 、分别是任务在所有虚拟机上的最大和最小执行时间
    • 、分别是任务在所有虚拟机上的最大和最小可靠性

    越小，表示越好，越应该把任务调度给这台虚拟机。

  • 为了提高可靠性，当任务的 hazard rate 较高时，就要将任务备份到其他云服务提供商的虚拟机上，在该虚拟机上，执行租赁开销最小。

    时就备份。

  • 算法流程如下：

  • 如果对 k 个云服务提供商的所有虚拟机都遍历，则时间复杂度为

    对于任务数为 n 的工作流，计算和排序的时间复杂度为

    为了能给每个任务都找到最优的虚拟机，需要每个任务都对虚拟机遍历，所以时间复杂度为

    最终，算法总的时间复杂度为

Performance Evaluation

  • 用 Cloudsim 做的实验。

  • baseline：

    • CWS

      S. Kianpisheh, N. M. Charkari, and M. Kargahi, ”**Reliability-driven scheduling of time/cost-constrained grid workflows,**” Future Gen. Comput. Syst., vol. 55, pp. 1-16, Feb. 2016.

    • FR-MOS

      M. Farid, R. Latip, M. Hussin, and N. Hamid, ”Scheduling Scientific Workflow Using Multi-Objective Algorithm With Fuzzy Resource Utilization in Multi-Cloud Environment,” IEEE Access, vol. 8, pp. 24309-24322, Jan. 2020.

  • 评价指标：makespan、Cost、Reliability

Experimental Setting and Environment

  • 第一次模拟中的多云系统有 10 个云服务提供商，来自 three types of Microsoft Azure, Amazon EC2, and Google Compute Engine 。
  • 第二次模拟有 6 个多云系统，每个多云系统有不同类型的虚拟机。

Real-world Scientific Workflow

Comparison Results

  • 实验设置：

    • 工作流的任务个数不同的情况下和 baseline 比较 Cost、makespan 和 Reliability。
    • 工作流任务数相同，多云系统不同的情况下和 baseline 比较 Cost、makespan 和 Reliability。

  • 实验结果：

    对于 Epigenomics 和 LIGO 两种工作流，在工作流的规模不同时，FCWS 算法在开销和系统可靠性方面要优于 FR-MOS 和 CWS，但在完成时间方面要略劣于 FR-MOS。

    对于上面的两种工作流，在工作流的规模相同时，在各种不同的多云系统中，虚拟机的数量越多，三种算法在开销、系统可靠性和完成时间方面所得到的结果都要更优，原因在于这些调度算法有更多低开销的资源可以选择。在三种算法的对比上，FCWS 算法在开销和系统可靠性方面要优于 FR-MOS 和 CWS，但在完成时间方面要略劣于 FR-MOS。

---------------The End---------------