Scheduling and resource allocation for clouds: novel algorithms, state space collapse and decay of tails

Xie, Qiaomin

Permalink

https://hdl.handle.net/2142/95280 Copy

Description

Title

Scheduling and resource allocation for clouds: novel algorithms, state space collapse and decay of tails

Author(s)

Xie, Qiaomin

Issue Date

2016-09-14

Director of Research (if dissertation) or Advisor (if thesis)

Lu, Yi

Doctoral Committee Chair(s)

Lu, Yi

Committee Member(s)

• Hajek, Bruce
• Srikant, R.
• Viswanath, Pramod

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Scheduling
• Resource Allocation
• Cloud Computing
• Data Locality
• Virtual Machine Assignment

Abstract

"Scheduling and resource allocation in cloud systems is of fundamental importance to system efficiency. The focus of this thesis is to study the fundamental limits of the scheduling and resource allocation problems in clouds, and design provably high-performance algorithms. In the first part, we consider data-centric scheduling. Data-intensive applications are posing increasingly significant challenges to scheduling in today's computing clusters. The presence of data induces an extremely heterogeneous cluster where processing speed depends on the task-server pair. The situation is further complicated by ever-changing technologies of networking, memory, and software architecture. As a result, a suboptimal scheduling algorithm causes unnecessary delay in job completion and wastes system capacity. We propose a versatile model featuring a multi-class parallel-server system that readily incorporates different characteristics of a variety of systems. The model has been studied by Harrison, Williams and Stolyar, respectively. However, delay optimality in heavy traffic with unknown arrival rate vectors has remained an open problem. We propose novel algorithms that achieve delay optimality with unknown arrival rates. This enables the application of proposed algorithms to data-centric clusters. New proof techniques are required including construction of an ideal load decomposition. To demonstrate the effectiveness of the proposed algorithms, we implement a Hadoop MapReduce scheduler and show that it achieves more than 10 times improvement over existing schedulers. The second part studies the resource allocation problem for clouds that provide infrastructure as a service, in the form of virtual machines (VMs). Consolidation of multiple VMs on a single physical machine (PM) has been advocated for improving system utilization. VMs placed on the same PM are subject to resource ""packing constraint,"" leading to stochastic dynamic bin packing models for the real-time assignment of VMs to PMs in a data center. Due to finite-sized pools of servers, incoming requests might not be fulfilled immediately and such requests are typically rejected. Hence a meaningful metric in practice is the blocking probability for arriving VM requests. We analyze the power-of-d-choices algorithm, a well-known stateless randomized routing policy with low scheduling overhead. We establish an explicit upper bound on the equilibrium blocking probability, and further demonstrate that the blocking probability exhibits distinct behaviors in different load regions: doubly-exponential decay in the heavy-traffic regime and exponential decay in the critically loaded regime."

Graduation Semester

2016-12

Type of Resource

text

Permalink

http://hdl.handle.net/2142/95280

Copyright and License Information

Copyright 2016 Qiaomin Xie

Owning Collections