Optimal resource allocation algorithms for cloud computing

Maguluri, Siva Theja

Permalink

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

Description

Title

Optimal resource allocation algorithms for cloud computing

Author(s)

Maguluri, Siva Theja

Issue Date

2015-01-21

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

Srikant, R.

Doctoral Committee Chair(s)

Srikant, R.

Committee Member(s)

• Hajek, Bruce
• Viswanath, Pramod
• Lu, Yi
• Ying, Lei

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)

• Cloud Computing
• Resource Allocation Algorithms
• Scheduling
• Load Balancing
• Routing
• Throughput Optimal
• Heavy traffic Optimal

Abstract

Cloud computing is emerging as an important platform for business, personal and mobile computing applications. We consider a stochastic model of a cloud computing cluster, where jobs arrive according to a random process and request virtual machines (VMs), which are specified in terms of resources such as CPU, memory and storage space. The jobs are first routed to one of the servers when they arrive and are queued at the servers. Each server then chooses a set of jobs from its queues so that it has enough resources to serve all of them simultaneously. There are many design issues associated with such systems. One important issue is the resource allocation problem, i.e., the design of algorithms for load balancing among servers, and algorithms for scheduling VM configurations. Given our model of a cloud, we define its capacity, i.e., the maximum rates at which jobs can be processed in such a system. An algorithm is said to be throughput-optimal if it can stabilize the system whenever the load is within the capacity region. We show that the widely-used Best-Fit scheduling algorithm is not throughput-optimal. We first consider the problem where the jobs need to be scheduled nonpreemptively on servers. Under the assumptions that the job sizes are known and bounded, we present algorithms that achieve any arbitrary fraction of the capacity region of the cloud. We then relax these assumptions and present a load balancing and scheduling algorithm that is throughput optimal when job sizes are unknown. In this case, job sizes (durations) are modeled as random variables with possibly unbounded support. Delay is a more important metric then throughput optimality in practice. However, analysis of delay of resource allocation algorithms is difficult, so we study the system in the asymptotic limit as the load approaches the boundary of the capacity region. This limit is called the heavy traffic regime. Assuming that the jobs can be preempted once after several time slots, we present delay optimal resource allocation algorithms in the heavy traffic regime. We study delay performance of our algorithms through simulations.

Graduation Semester

2014-12

Permalink

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

Copyright and License Information

Copyright 2014 Siva Theja Maguluri

Owning Collections