Heavy Traffic Optimal Resource Allocation Algorithms for Cloud Computing Clusters

Date Added: Jun 2012
Format: PDF

Cloud computing is emerging as an important platform for business, personal and mobile computing applications. In this paper, the authors explain a stochastic model of cloud computing, where jobs arrive according to a stochastic process and request resources like CPU, memory and storage space. They consider a model where the resource allocation problem can be separated into a routing or load balancing problem and a scheduling problem. They explain the join-the-shortest-queue routing and power of-two-choices routing algorithms with Max Weight scheduling algorithm. It was known that these algorithms are throughput optimal. In this paper, they show that these algorithms are queue length optimal in the heavy traffic limit.