Optimal resource allocation algorithms for cloud computing

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

Maguluri, Siva Theja

关键词: Cloud Computing;    Resource Allocation Algorithms;    Scheduling;    Load Balancing;    Routing;    Throughput Optimal;    Heavy traffic Optimal;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/72901/Siva%20Theja_Maguluri.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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 resourcessuch 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 thenchooses 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 loadbalancing 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 saidto 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 schedulingalgorithm 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 knownand bounded, we present algorithms that achieve any arbitrary fraction of the capacity region of the cloud. We then relax these assumptions and presenta load balancing and scheduling algorithm that is throughput optimal when job sizes are unknown. In this case, job sizes (durations) are modeled asrandom 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 westudy the system in the asymptotic limit as the load approaches the boundary of the capacity region. This limit is called the heavy traffic regime. Assumingthat the jobs can be preempted once after several time slots, we present delay optimal resource allocation algorithms in the heavy traffic regime. We studydelay performance of our algorithms through simulations.