A family of heuristics for agent-based elastic Cloud bag-of-tasks concurrent scheduling

Sim, Kwang Mong and Gutierrez-GArcia, J. Octavio (2013) A family of heuristics for agent-based elastic Cloud bag-of-tasks concurrent scheduling. Future Generation Computer Systems, 29 (7). pp. 1682-1699. ISSN 0167-739X. (Full text available)

PDF
Download (3MB) Preview
[img]
Preview
Official URL
http://dx.doi.org/10.1016/j.future.2012.01.005

Abstract

The scheduling and execution of bag-of-tasks applications (BoTs) in Clouds is performed on sets of virtualized Cloud resources that start being exhausted right after their allocation disregarding whether tasks are being executed. In addition, BoTs may be executed in potentially heterogeneous sets of Cloud resources, which may be either previously allocated for a different and fixed number of hours or dynamically reallocated as needed. In this paper, a family of 14 scheduling heuristics for concurrently executing BoTs in Cloud environments is proposed. The Cloud scheduling heuristics are adapted to the resource allocation settings (e.g., 1-hour time slots) of Clouds by focusing on maximizing Cloud resource utilization based on the remaining allocation times of Cloud resources. Cloud scheduling heuristics supported by information about BoT tasks (e.g., task size) and/or Cloud resource performances are proposed. Additionally, scheduling heuristics that require no information of either Cloud resources or tasks are also proposed. The Cloud scheduling heuristics support the dynamic inclusion of new Cloud resources while scheduling and executing a given BoT without rescheduling. Furthermore, an elastic Cloud resource allocation mechanism that autonomously and dynamically reallocates Cloud resources on demand to BoT executions is proposed. Moreover, an agent-based Cloud BoT scheduling approach that supports concurrent and parallel scheduling and execution of BoTs, and concurrent and parallel dynamic selection and composition of Cloud resources (by making use of the well-known contract net protocol) from multiple and distributed Cloud providers is designed and implemented. Empirical results show that BoTs can be (i) efficiently executed by attaining similar (in some cases shorter) makespans to commonly used benchmark heuristics (e.g., Max–min), (ii) effectively executed by achieving a 100% success execution rate even with high BoT execution request rates and executing BoTs in a concurrent and parallel manner, and that (iii) BoTs are economically executed by elastically reallocating Cloud resources on demand.

Item Type: Article
Uncontrolled keywords: Scheduling heuristics; Bag-of-tasks applications; Cloud computing; Multi-agent systems; Agent-based Cloud computing; Elastic Cloud resource allocation
Subjects: Q Science > Q Science (General) > Q335 Artificial intelligence
Q Science > QA Mathematics (inc Computing science) > QA 75 Electronic computers. Computer science
Divisions: Faculties > Science Technology and Medical Studies > School of Computing > Future Computing Group
Central Services > Templeman Library
Central Services > Research Services
Depositing User: Kwang Mong Sim
Date Deposited: 29 Oct 2012 14:18
Last Modified: 18 Sep 2013 07:50
Resource URI: http://kar.kent.ac.uk/id/eprint/32019 (The current URI for this page, for reference purposes)
  • Depositors only (login required):

Downloads

Downloads per month over past year