Power of d choices for large-scale bin packing: A loss model

Qiaomin Xie, Xiaobo Dong, Yi Lu, Rayadurgam Srikant

Research output: Contribution to journalConference article

Abstract

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 - λ)/√λ → α.

Original languageEnglish (US)
Pages (from-to)321-334
Number of pages14
JournalPerformance Evaluation Review
Volume43
Issue number1
DOIs
StatePublished - Jun 24 2015
EventACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2015 - Portland, United States
Duration: Jun 15 2015Jun 19 2015

Fingerprint

Bins
Servers
Blocking probability
Computer systems
Cloud computing
Data storage equipment
Fluids

Keywords

  • Fluid limit analysis
  • Loss model
  • Randomized algorithms
  • Resource allocation
  • Virtual machine assignment

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Power of d choices for large-scale bin packing : A loss model. / Xie, Qiaomin; Dong, Xiaobo; Lu, Yi; Srikant, Rayadurgam.

In: Performance Evaluation Review, Vol. 43, No. 1, 24.06.2015, p. 321-334.

Research output: Contribution to journalConference article

@article{3bca80e2e2174660bfc2bfd8e16c3d43,
title = "Power of d choices for large-scale bin packing: A loss model",
abstract = "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 - λ)/√λ → α.",
keywords = "Fluid limit analysis, Loss model, Randomized algorithms, Resource allocation, Virtual machine assignment",
author = "Qiaomin Xie and Xiaobo Dong and Yi Lu and Rayadurgam Srikant",
year = "2015",
month = "6",
day = "24",
doi = "10.1145/2796314.2745849",
language = "English (US)",
volume = "43",
pages = "321--334",
journal = "Performance Evaluation Review",
issn = "0163-5999",
publisher = "Association for Computing Machinery (ACM)",
number = "1",

}

TY - JOUR

T1 - Power of d choices for large-scale bin packing

T2 - A loss model

AU - Xie, Qiaomin

AU - Dong, Xiaobo

AU - Lu, Yi

AU - Srikant, Rayadurgam

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

VL - 43

SP - 321

EP - 334

JO - Performance Evaluation Review

JF - Performance Evaluation Review

SN - 0163-5999

IS - 1

ER -