A Robust Algorithm for Deadline Constrained Scheduling in IaaS Cloud Environment

Bilkisu Larai MUHAMMAD-BELLO; Masayoshi ARITSUGI

doi:10.1587/transinf.2018PAP0016

IEICE TRANSACTIONS on Information

A Robust Algorithm for Deadline Constrained Scheduling in IaaS Cloud Environment

Bilkisu Larai MUHAMMAD-BELLO, Masayoshi ARITSUGI

Full Text Views

0

Cite this

Summary :

The Infrastructure as a Service (IaaS) Clouds are emerging as a promising platform for the execution of resource demanding and computation intensive workflow applications. Scheduling the execution of scientific applications expressed as workflows on IaaS Clouds involves many uncertainties due to the variable and unpredictable performance of Cloud resources. These uncertainties are modeled by probability distribution functions in past researches or totally ignored in some cases. In this paper, we propose a novel robust deadline constrained workflow scheduling algorithm which handles the uncertainties in scheduling workflows in the IaaS Cloud environment. Our proposal is a static scheduling algorithm aimed at addressing the uncertainties related to: the estimation of task execution times; and, the delay in provisioning computational Cloud resources. The workflow scheduling problem was considered as a cost-optimized, deadline-constrained optimization problem. Our uncertainty handling strategy was based on the consideration of knowledge of the interval of uncertainty, which we used to modeling the execution times rather than using a known probability distribution function or precise estimations which are known to be very sensitive to variations. Experimental evaluations using CloudSim with synthetic workflows of various sizes show that our proposal is robust to fluctuations in estimates of task runtimes and is able to produce high quality schedules that have deadline guarantees with minimal penalty cost trade-off depending on the length of the interval of uncertainty. Scheduling solutions for varying degrees of uncertainty resisted against deadline violations at runtime as against the static IC-PCP algorithm which could not guarantee deadline constraints in the face of uncertainty.

Publication: IEICE TRANSACTIONS on Information Vol.E101-D No.12 pp.2942-2957

Publication Date: 2018/12/01

Publicized: 2018/09/18

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2018PAP0016

Type of Manuscript: Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking)

Category: Cloud Computing

Authors

Bilkisu Larai MUHAMMAD-BELLO
Kumamoto University,Information & Media Technology Dept. Federal University of Technology Minna
Masayoshi ARITSUGI
Kumamoto University

Keyword

handling resource performance uncertainty, deadline-constrained workflow scheduling, IaaS cloud environment, robust scheduling, uncertain processing time

Cite this

Copy

Bilkisu Larai MUHAMMAD-BELLO, Masayoshi ARITSUGI, "A Robust Algorithm for Deadline Constrained Scheduling in IaaS Cloud Environment" in IEICE TRANSACTIONS on Information, vol. E101-D, no. 12, pp. 2942-2957, December 2018, doi: 10.1587/transinf.2018PAP0016.
Abstract: The Infrastructure as a Service (IaaS) Clouds are emerging as a promising platform for the execution of resource demanding and computation intensive workflow applications. Scheduling the execution of scientific applications expressed as workflows on IaaS Clouds involves many uncertainties due to the variable and unpredictable performance of Cloud resources. These uncertainties are modeled by probability distribution functions in past researches or totally ignored in some cases. In this paper, we propose a novel robust deadline constrained workflow scheduling algorithm which handles the uncertainties in scheduling workflows in the IaaS Cloud environment. Our proposal is a static scheduling algorithm aimed at addressing the uncertainties related to: the estimation of task execution times; and, the delay in provisioning computational Cloud resources. The workflow scheduling problem was considered as a cost-optimized, deadline-constrained optimization problem. Our uncertainty handling strategy was based on the consideration of knowledge of the interval of uncertainty, which we used to modeling the execution times rather than using a known probability distribution function or precise estimations which are known to be very sensitive to variations. Experimental evaluations using CloudSim with synthetic workflows of various sizes show that our proposal is robust to fluctuations in estimates of task runtimes and is able to produce high quality schedules that have deadline guarantees with minimal penalty cost trade-off depending on the length of the interval of uncertainty. Scheduling solutions for varying degrees of uncertainty resisted against deadline violations at runtime as against the static IC-PCP algorithm which could not guarantee deadline constraints in the face of uncertainty.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018PAP0016/_p

Copy

@ARTICLE{e101-d_12_2942,
author={Bilkisu Larai MUHAMMAD-BELLO, Masayoshi ARITSUGI, },
journal={IEICE TRANSACTIONS on Information},
title={A Robust Algorithm for Deadline Constrained Scheduling in IaaS Cloud Environment},
year={2018},
volume={E101-D},
number={12},
pages={2942-2957},
abstract={The Infrastructure as a Service (IaaS) Clouds are emerging as a promising platform for the execution of resource demanding and computation intensive workflow applications. Scheduling the execution of scientific applications expressed as workflows on IaaS Clouds involves many uncertainties due to the variable and unpredictable performance of Cloud resources. These uncertainties are modeled by probability distribution functions in past researches or totally ignored in some cases. In this paper, we propose a novel robust deadline constrained workflow scheduling algorithm which handles the uncertainties in scheduling workflows in the IaaS Cloud environment. Our proposal is a static scheduling algorithm aimed at addressing the uncertainties related to: the estimation of task execution times; and, the delay in provisioning computational Cloud resources. The workflow scheduling problem was considered as a cost-optimized, deadline-constrained optimization problem. Our uncertainty handling strategy was based on the consideration of knowledge of the interval of uncertainty, which we used to modeling the execution times rather than using a known probability distribution function or precise estimations which are known to be very sensitive to variations. Experimental evaluations using CloudSim with synthetic workflows of various sizes show that our proposal is robust to fluctuations in estimates of task runtimes and is able to produce high quality schedules that have deadline guarantees with minimal penalty cost trade-off depending on the length of the interval of uncertainty. Scheduling solutions for varying degrees of uncertainty resisted against deadline violations at runtime as against the static IC-PCP algorithm which could not guarantee deadline constraints in the face of uncertainty.},
keywords={},
doi={10.1587/transinf.2018PAP0016},
ISSN={1745-1361},
month={December},}

Copy

TY - JOUR
TI - A Robust Algorithm for Deadline Constrained Scheduling in IaaS Cloud Environment
T2 - IEICE TRANSACTIONS on Information
SP - 2942
EP - 2957
AU - Bilkisu Larai MUHAMMAD-BELLO
AU - Masayoshi ARITSUGI
PY - 2018
DO - 10.1587/transinf.2018PAP0016
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E101-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2018
AB - The Infrastructure as a Service (IaaS) Clouds are emerging as a promising platform for the execution of resource demanding and computation intensive workflow applications. Scheduling the execution of scientific applications expressed as workflows on IaaS Clouds involves many uncertainties due to the variable and unpredictable performance of Cloud resources. These uncertainties are modeled by probability distribution functions in past researches or totally ignored in some cases. In this paper, we propose a novel robust deadline constrained workflow scheduling algorithm which handles the uncertainties in scheduling workflows in the IaaS Cloud environment. Our proposal is a static scheduling algorithm aimed at addressing the uncertainties related to: the estimation of task execution times; and, the delay in provisioning computational Cloud resources. The workflow scheduling problem was considered as a cost-optimized, deadline-constrained optimization problem. Our uncertainty handling strategy was based on the consideration of knowledge of the interval of uncertainty, which we used to modeling the execution times rather than using a known probability distribution function or precise estimations which are known to be very sensitive to variations. Experimental evaluations using CloudSim with synthetic workflows of various sizes show that our proposal is robust to fluctuations in estimates of task runtimes and is able to produce high quality schedules that have deadline guarantees with minimal penalty cost trade-off depending on the length of the interval of uncertainty. Scheduling solutions for varying degrees of uncertainty resisted against deadline violations at runtime as against the static IC-PCP algorithm which could not guarantee deadline constraints in the face of uncertainty.
ER -

IEICE TRANSACTIONS on Information