Power of d choices for large-scale bin packing: a loss model
Dong, Xiaobo
Loading…
Permalink
https://hdl.handle.net/2142/88185
Description
Title
Power of d choices for large-scale bin packing: a loss model
Author(s)
Dong, Xiaobo
Issue Date
2015-07-14
Director of Research (if dissertation) or Advisor (if thesis)
Srikant, R.
Department of Study
Electrical & Computer Engineering
Discipline
Electrical & Computer Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
