Ph.D Thesis

Ph.D StudentShifrin Mark
SubjectAdmission and Scheduling Control in Cloud Computing -
Markov Decision Processes and Diffusion
DepartmentDepartment of Electrical and Computer Engineering
Supervisors PROFESSOR EMERITUS Israel Cidon
PROF. Rami Atar


Hybrid clouds, as an effective combination of public and private cloud, give rise to optimization challenges concerning computational needs and costs. It is particularly effective when a private computational infrastructure is present, and the task arrival rate is high or critical or has the structure of intermitting peaks.

In this thesis, we present a solution for optimal control problems in the hybrid cloud system. Two main methods are exploited for the analysis.

The first is a solution by Markov Decision Processes (MDP), which provides an exact optimal control policy.

We present a system design for optimal scheduling and cloudbursting and the corresponding analytical framework based on MDP using the structural properties of the value function. Our work presents proofs to threshold-type structure of the optimal policies.

The second method relies on diffusion approximation. We relax the Markovian assumptions in order to extend the control problem. To address a non-Markovian model, we analyze the system in a heavy traffic regime. We define the control policy and prove its asymptotic optimality.

We demonstrate that the problem undergoes a dimensionality reduction, in the form of a state space collapse. These results are extended to an additional problem, where the buffer constraints are replaced by the time delay constraints.

In addition, we address the cloud scenario that considers a framework with differentiated price levels, and analyze by MDP the dynamic pricing problem.