Variational Optimization Methods for Resource Aware Scheduling in Cloud Computing Environments

Abstract

Resource scheduling methods for dynamic cloud computing environments must be robust in nature to adjust to workload uncertainty, resource contention, execution-time variation and deadline requirements. Deadline reliability is not guaranteed with existing deterministic scheduling techniques under changing execution conditions, and fixed chance constraints are not flexible enough to the changing priority of tasks and the uncertainty level. In this paper, we introduce an Adaptive Chance-Constrained Alternating Direction Method of Multipliers (AC-ADMM) framework for uncertainty-aware cloud resource scheduling. The framework combines a distributed ADMM optimization with probabilistic deadline requirements and proposes using adaptive risk tolerance based on the priority of the tasks and the uncertainty in the amount of work executed. ADMM penalty parameter is dynamically adjusted based on primal and dual residuals to improve consensus and convergence. The deterministic equivalent of the chance constraint is calculated, and a deadline reliability theorem is stated and proven in order to ensure the desired schedule reliability (probability of meeting the task deadlines) under the assumptions of a distribution for the execution time. Deadline success rate, SLA violation rate, makespan, energy consumption, scheduling cost, resource utilization and convergence behaviour are used to measure the performance of the framework. Convergence stability under increasing workload uncertainty and an 89.7% deadline success rate with a 10.3% SLA violation rate at AC-ADMM. The experiments show how theoretical deadline guarantees can be successfully combined with adaptive distributed optimization to guarantee reliable and resource-aware cloud scheduling.