Scheduling Multi-Workflows Over Heterogeneous Virtual Machines With a Multi-Stage Dynamic Game-Theoretic Approach

Scheduling Multi-Workflows Over Heterogeneous Virtual Machines With a Multi-Stage Dynamic Game-Theoretic Approach

Lei Wu (School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu, China) and Yuandou Wang (College of Computer Science, Chongqing University, Chongqing, China)
Copyright: © 2018 |Pages: 15
DOI: 10.4018/IJWSR.2018100105

Abstract

Cloud computing, with dependable, consistent, pervasive, and inexpensive access to geographically distributed computational capabilities, is becoming an increasingly popular platform for the execution of scientific applications such as scientific workflows. Scheduling multiple workflows over cloud infrastructures and resources is well recognized to be NP-hard and thus critical to meeting various types of Quality-of-Service (QoS) requirements. In this work, the authors consider a multi-objective scientific workflow scheduling framework based on the dynamic game-theoretic model. It aims at reducing make-spans, cloud cost, while maximizing system fairness in terms of workload distribution among heterogeneous cloud virtual machines (VMs). The authors consider randomly-generated scientific workflow templates as test cases and carry out extensive real-world tests based on third-party commercial clouds. Experimental results show that their proposed framework outperforms traditional ones by achieving lower make-spans, lower cost, and better system fairness.
Article Preview
Top

Introduction

In recent years, increasing scientific fields employ workflows to analyze large amounts of data and to perform complex scientific computing applications. A process in such scientific applications is described as a workflow by partitioning it into atomic tasks. These tasks are further distributed to multiple computing resources (Rodriguez & Buyya, 2017). They are usually represented as directed graphs with their nodes representing discrete computational components and the edges representing connections along which data and results are passed. They have varying types and usually their execution needs computing platforms with different QoS requirements (Yunni Xia et al., 2015; Xia, Zhou, Luo, Pang, & Zhu, 2015; Xia, Zhou, Xin Luo, Pang & Zhu, 2015; Xia, Liu, Liu, & Zhu, 2012; Xia, Xin Luo, Jia Li, & Zhu, 2013)).

Recently, cloud computing is recognized as a suitable solution and paradigm for providing a flexible, on-demand computing infrastructure over the Internet for large-scale scientific-workflow-based applications. The services that can be provided from the cloud include Software-as-a-Service (SaaS), Platform-as-a-Service (PaaS), and Infrastructure-as-a-Service (IaaS). SaaS and PaaS clouds offer web applications/software over the Internet, running on cloud infrastructure. They are therefore less suitable for scientific workflows than IaaS ones because they mainly offer an environment to design, develop and test web-based applications. Instead, IaaS clouds offer an easily accessible, flexible, and scalable infrastructure suitable for the deployment of large-scale scientific applications based on on-demand and pay-per-use patterns (Buyya, 2009).

One of the most challenging NP-hard problems that researchers try to address is how to schedule large-scale scientific applications to distributed and heterogeneous computational nodes, e.g., IaaS clouds, such that quantitative goals such as process make-span are optimized, and certain constraints such as communication cost and storage requirements areas followed ((Wu, Zhou, Zhu, & Xia, 2018; Zheng, Trivedi, Qiu, & Xia, 2017; Deng, Wu, Taheri, Zomaya, & Wu, 2016)). From the end-user perspective, a low make-span is always preferred, whereas from the system’s perspective system-level efficiency and fairness are often considered as a good motivation such that the scientific applications and tasks are supposed to be fairly distributed among computational resources to avoid hot spots and performance bottle-necks. However, a careful investigation into related work indicates that only a few schemes are able to deal with both perspectives, such as optimizing user objectives (e.g., make-span) while fulfilling other constraints, and providing a fair workload distribution among physical computational resources of clouds.

The primary aim of the paper is thus to provide a multi-objective scheduling framework to address the real-time workflow-scheduling problem on multiple IaaS cloud. Specifically, we consider a multi-objective optimization workflow scheduling approach based on dynamic game-theoretic model. It aims at reducing workflow make-spans, reducing cost, and maximizing system fairness in terms of workload distribution among heterogeneous VMs. We conduct extensive case studies as well based on various randomly-generated scientific workflow templates and heterogeneous VMs created on real-world third-party commercial IaaS clouds, i.e., Amazon, Tencent, and Ali clouds. Experimental results clearly suggest that our proposed approach outperforms traditional ones by achieving lower workflow make-spans, lower cost, and better system fairness.

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 17: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 16: 4 Issues (2019)
Volume 15: 4 Issues (2018)
Volume 14: 4 Issues (2017)
Volume 13: 4 Issues (2016)
Volume 12: 4 Issues (2015)
Volume 11: 4 Issues (2014)
Volume 10: 4 Issues (2013)
Volume 9: 4 Issues (2012)
Volume 8: 4 Issues (2011)
Volume 7: 4 Issues (2010)
Volume 6: 4 Issues (2009)
Volume 5: 4 Issues (2008)
Volume 4: 4 Issues (2007)
Volume 3: 4 Issues (2006)
Volume 2: 4 Issues (2005)
Volume 1: 4 Issues (2004)
View Complete Journal Contents Listing