Title: Task scheduling in budget-constrained cloud computing systems to maximise throughput

Authors: Weiming Shi; Bo Hong

Addresses: School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta 30332, USA. ' School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta 30332, USA

Abstract: We consider the problem of running a large amount of independent equal-sized tasks in the cloud with a budget constraint from the perspective of the cloud users. We model the cloud infrastructure by a node-weighted edge-weighted star-shaped graph and focus on the maximisation of the steady-state throughput. We show that the specific budget-constrained steady-state throughput maximisation problem can be formulated and solved as a linear programming (LP) problem. We incorporate the compute nodes of different communication capacity into our problem formulation in a unified way. We identify two modes of the system where closed-form solutions exist, i.e., the budget-bound mode and the communication-bound mode. The best scheduling scheme is benefit-first (resp. communication-first) when the system is budget-bound (resp. communication-bound), where tasks should be scheduled onto the compute nodes in the descending order of the effective benefit (resp. bandwidth). When the system is under conditions other than these two modes, we propose a simple heuristic to solve it instead of resolving to the conventional numerical algorithms for the LP. Simulation results show that the simple heuristic outperforms other intuitive heuristics under varied sampled system setups.

Keywords: cloud computing; resource allocation; task scheduling; steady-state throughput maximisation; budget constraints; simulation.

DOI: 10.1504/IJCSE.2012.049752

International Journal of Computational Science and Engineering, 2012 Vol.7 No.4, pp.319 - 328

Published online: 22 Sep 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article