TY - JOUR
T1 - Power of d choices for large-scale bin packing
T2 - ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2015
AU - Xie, Qiaomin
AU - Dong, Xiaobo
AU - Lu, Yi
AU - Srikant, Rayadurgam
N1 - Funding Information:
Qiaomin Xie and Yi Lu were supported by NSF grant CNS-1150080. The work of Xiaobo Dong and R. Srikant was supported in part by NSF Grant ECCS-1202065 and ARO MURIW911NF-12-1-0385. We thank Prof. RaviMazumdar for pointing out a gap in the proof of Lemma 1 in an earlier version of the paper.
Publisher Copyright:
© Copyright 2015 ACM.
PY - 2015/6/24
Y1 - 2015/6/24
N2 - We consider a system of N parallel servers, where each server consists of B units of a resource. Jobs arrive at this system according to a Poisson process, and each job stays in the system for an exponentially distributed amount of time. Each job may request different units of the resource from the system. The 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. The motivation for this problem 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 this paper, we consider power-ofdchoices routing, where a job is routed to the server with the largest amount of available resource among d ≥ 2 randomly chosen servers. We consider a fluid model that corresponds to the limit as N goes to infinity and provide an explicit upper bound for the equilibrium blocking probability. We show that the upper bound exhibits different behavior as B goes to infinity depending on the relationship between the total traffic intensity λ and B. In particular, if (B - λ)/√λ → α, the upper bound is doubly exponential in √λ and if (B - λ)/logd λ → β, β > 1, the upper bound is exponential in λ. Simulation results show that the blocking probability, even for small B, exhibits qualitatively different behavior in the two traffic regimes. This is in contrast with the result for random routing, where the blocking probability scales as O(1/√λ) even if (B - λ)/√λ → α.
AB - We consider a system of N parallel servers, where each server consists of B units of a resource. Jobs arrive at this system according to a Poisson process, and each job stays in the system for an exponentially distributed amount of time. Each job may request different units of the resource from the system. The 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. The motivation for this problem 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 this paper, we consider power-ofdchoices routing, where a job is routed to the server with the largest amount of available resource among d ≥ 2 randomly chosen servers. We consider a fluid model that corresponds to the limit as N goes to infinity and provide an explicit upper bound for the equilibrium blocking probability. We show that the upper bound exhibits different behavior as B goes to infinity depending on the relationship between the total traffic intensity λ and B. In particular, if (B - λ)/√λ → α, the upper bound is doubly exponential in √λ and if (B - λ)/logd λ → β, β > 1, the upper bound is exponential in λ. Simulation results show that the blocking probability, even for small B, exhibits qualitatively different behavior in the two traffic regimes. This is in contrast with the result for random routing, where the blocking probability scales as O(1/√λ) even if (B - λ)/√λ → α.
KW - Fluid limit analysis
KW - Loss model
KW - Randomized algorithms
KW - Resource allocation
KW - Virtual machine assignment
UR - http://www.scopus.com/inward/record.url?scp=84955609288&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84955609288&partnerID=8YFLogxK
U2 - 10.1145/2796314.2745849
DO - 10.1145/2796314.2745849
M3 - Conference article
AN - SCOPUS:84955609288
SN - 0163-5999
VL - 43
SP - 321
EP - 334
JO - Performance Evaluation Review
JF - Performance Evaluation Review
IS - 1
Y2 - 15 June 2015 through 19 June 2015
ER -