2020 journal article

Power-Aware Allocation of Graph Jobs in Geo-Distributed Cloud Networks

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 31(4), 749–765.

co-author countries: United States of America πŸ‡ΊπŸ‡Έ
author keywords: Resource management; Cloud computing; Power demand; Servers; Task analysis; Twitter; Distributed algorithms; Big-data; graph jobs; geo-distributed cloud networks; datacenter power consumption; job allocation; integer programming; convex optimization; online learning
Source: Web Of Science
Added: February 10, 2020

In the era of big-data, the jobs submitted to the clouds exhibit complicated structures represented by graphs, where the nodes denote the sub-tasks each of which can be accommodated at a slot in a server, while the edges indicate the communication constraints among the sub-tasks. We develop a framework for efficient allocation of graph jobs in geo-distributed cloud networks (GDCNs), explicitly considering the power consumption of the datacenters (DCs). We address the following two challenges arising in graph job allocation: i) the allocation problem belongs to NP-hard nonlinear integer programming; ii) the allocation requires solving the NP-complete sub-graph isomorphism problem, which is particularly cumbersome in large-scale GDCNs. We develop a suite of efficient solutions for GDCNs of various scales. For small-scale GDCNs, we propose an analytical approach based on convex programming. For medium-scale GDCNs, we develop a distributed allocation algorithm exploiting the processing power of DCs in parallel. Afterward, we provide a novel low-complexity (decentralized) sub-graph extraction method, based on which we introduce cloud crawlers aiming to extract allocations of good potentials for large-scale GDCNs. Given these suggested strategies, we further investigate strategy selection under both fixed and adaptive DC pricing schemes, and propose an online learning algorithm for each.