Cost-Conscious Scheduling for Large Graph Processing in the Cloud

Abstract

In recent years large graph processing has emerged to be a popular application for companies because of the increasing large Web graph and social networks. The ever growing scale of graphs and recent emergence of cloud computing poses challenges to their efficient and cost-conscious scheduling approach for processing tasks. In this paper, we focus on the use of cloud resources for dispatching large graph processing tasks. We design a novel framework EComer that can be easily integrated into existing cloud infrastructure. The key component of this framework is a cost-conscious scheduling heuristic, called CCSH, which is an extension of Heterogeneous Earliest Finish Time (HEFT). Our algorithm CCSH first constructs a priority list of tasks and then assigns the task with the highest priority value to the cost-efficient virtual machine in a cloud setting. The comparison study, based on randomly generated large graphs and a real-life astronomy application model, demonstrates that our algorithm outperforms HEFT by exhibiting significant monetary cost savings at a reasonable increase in overall execution time.