Files in this item

FilesDescriptionFormat

application/pdf

application/pdfDONG-THESIS-2015.pdf (476kB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:Power of d choices for large-scale bin packing: a loss model
Author(s):Dong, Xiaobo
Advisor(s):Srikant, R.
Department / Program:Electrical & Computer Engineering
Discipline:Electrical & Computer Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(s):Resource allocation
Markov process
Cloud computing
Queueing
Abstract:A system with N parallel servers is considered in our thesis. Each server consists of B units of a resource and jobs arrive at this system according to a Poisson process. Each job stays in the system for an exponentially distributed amount of time. Moreover, each job may request different units of the resource from the system. Our goal is to understand how to route arriving jobs to the servers to minimize the probability that an arriving job does not find the required amount of resource at the server, i.e., the goal is to minimize blocking probability. Our motivation arises from the design of cloud computing systems in which the jobs are virtual machines (VMs) that request resources such as memory from a large pool of servers. In our thesis, we consider power-of-d-choices routing, where a job is routed to the server with the largest amount of available resources among d 2 randomly chosen servers. We consider a fluid model that corresponds to the limit as N goes to infinity, and use numerical methods to approximate the blocking probability. Moreover, we also show the simulation for the system.
Issue Date:2015-07-14
Type:Thesis
URI:http://hdl.handle.net/2142/88185
Rights Information:Copyright 2015 Xiaobo Dong
Date Available in IDEALS:2015-09-29
Date Deposited:August 201


This item appears in the following Collection(s)

Item Statistics