Overcommitment in Cloud Services – Bin packing
with Chance Constraints
Maxime C. Cohen
Google Research, New York, NY 10011, maxccohen@google.com

Philipp W. Keller

arXiv:1705.09335v1 [] 25 May 2017

Google, Mountain View, CA 94043, pkeller@google.com

Vahab Mirrokni
Google Research, New York, NY 10011, mirrokni@google.com

Morteza Zadimoghaddam
Google Research, New York, NY 10011, zadim@google.com

This paper considers a traditional problem of resource allocation, scheduling jobs on machines. One such
recent application is cloud computing, where jobs arrive in an online fashion with capacity requirements
and need to be immediately scheduled on physical machines in data centers. It is often observed that the
requested capacities are not fully utilized, hence offering an opportunity to employ an overcommitment
policy, i.e., selling resources beyond capacity. Setting the right overcommitment level can induce a significant
cost reduction for the cloud provider, while only inducing a very low risk of violating capacity constraints.
We introduce and study a model that quantifies the value of overcommitment by modeling the problem as
a bin packing with chance constraints. We then propose an alternative formulation that transforms each
chance constraint into a submodular function. We show that our model captures the risk pooling effect and
can guide scheduling and overcommitment decisions. We also develop a family of online algorithms that are
intuitive, easy to implement and provide a constant factor guarantee from optimal. Finally, we calibrate
our model using realistic workload data, and test our approach in a practical setting. Our analysis and
experiments illustrate the benefit of overcommitment in cloud services, and suggest a cost reduction of 1.5%
to 17% depending on the provider’s risk tolerance.
Key words : Bin packing, Approximation algorithms, Cloud computing, Overcommitment

1.

Introduction

Bin packing is an important problem with numerous applications such as hospitals, call centers,
filling up containers, loading trucks with weight capacity constraints, creating file backups and
more recently, cloud computing. A cloud provider needs to decide how many physical machines to
purchase in order to accommodate the incoming jobs efficiently. This is typically modeled as a bin
packing optimization problem, where one minimizes the cost of acquiring the physical machines
subject to a capacity constraint for each machine. The jobs are assumed to arrive in an online
fashion according to some vaguely specified arrival process. In addition, the jobs come with a
specific requirement, but the effective job size and duration are not exactly known until after the
1

2

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

actual scheduling has occurred. In practice, job size and duration can be estimated from historical
data. One straightforward way to schedule jobs is to assume that each job will fully utilize its
requirement (e.g., if a job requests 32 CPU cores, the cloud provider allocates this exact amount for
the job). However, there is empirical evidence, that most of the virtual machines do not use the full
requested capacity. This offers an opportunity for the cloud provider to employ an overcommitment
policy, i.e., to schedule sets of jobs with the total requirement exceeding the respective capacities
of physical machines. On one hand, the provider faces the risk that usage exceeds the physical
capacity, which can result in severe penalties (e.g., acquiring or reallocating machines on the fly,
canceling and rescheduling running jobs, mitigating interventions, etc.). On the other hand, if
many jobs do not fully utilize their requested resources, the provider can potentially reduce the
costs significantly. This becomes even more impactful in the cloud computing market, which has
become increasingly competitive in recent years as Google, Amazon, and Microsoft aim to replace
private data centers. “The race to zero price” is a commonly used term for this industry, where
cloud providers have cut their prices very aggressively. According to an article in Business Insider
in January 2015: “Amazon Web Services (AWS), for example, has cut its price 44 times during
2009-2015, while Microsoft and Google have both decreased prices multiple times to keep up with
AWS”. In January 2015, RBC Capital’s Mark Mahaney published a chart that perfectly captures
this trend and shows that the average monthly cost per gigabyte of RAM, for a set of various
workloads, has dropped significantly: AWS dropped prices 8% from Oct. 2013 to Dec. 2014, while
both Google and Microsoft cut prices by 6% and 5%, respectively, in the same period. Other
companies who charge more, like Rackspace and AT&T, dropped prices even more significantly.
As a result, designing the right overcommitment policy for servers has a clear potential to increase
the cloud provider profit. The goal of this paper is to study this question, and propose a model
that helps guiding this type of decisions. In particular, we explicitly model job size uncertainty to
motivate new algorithms, and evaluate them on realistic workloads.
Our model and approaches are not limited to cloud computing and can be applied to several
resource allocation problems. However, we will illustrate most of the discussions and applications
using examples borrowed from the cloud computing world. Note that describing the cloud infrastructure and hardware is beyond the scope of this paper. For surveys on cloud computing, see, for
example Dinh et al. (2013) and Fox et al. (2009).
We propose to model the problem as a bin packing with chance constraints, i.e., the total load
assigned to each machine should be below physical capacity with a high pre-specified probability.
Chance constraints are a commonly used modeling tool to capture risks and constraints on random variables (Charnes and Cooper (1963)). Introducing chance constraints to several continuous
optimization problems was extensively studied in the literature (see, e.g., Calafiore and El Ghaoui

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

3

(2006) and Delage and Ye (2010)). This paper is the first to incorporate capacity chance constraints
in the bin packing problem, and to propose efficient algorithms to solve the problem. Using some
results from distributionally robust optimization (Calafiore and El Ghaoui (2006)), we reformulate
the problem as a bin packing with submodular capacity constraints. Our reformulations are exact
under the assumption of independent Gaussian resource usages for the jobs. More generally, they
provide an upper bound and a good practical approximation in the realistic case where the jobs’
usages are arbitrarily distributed but bounded.
Using some machinery from previous work (see Goemans et al. (2009), and Svitkina and Fleischer
(2011)), we show that for the bin packing problem with general monotone submodular constraints,
it is impossible to find a solution within any reasonable factor from optimal (more precisely,

√
N
,
ln(N )

where N is the number of jobs). In this paper, we show that our problem can be solved using a class
of simple online algorithms that guarantee a constant factor of 8/3 from optimal (Theorem 2). This
class of algorithms includes the commonly used Best-Fit and First-Fit heuristics. We also develop
an improved constant guarantee of 9/4 for the online problem (Theorem 4), and a 2-approximation
for the offline version (Theorem 6). We further refine our results to the case where a large number
of jobs can be scheduled on each machine (i.e., each job has a small size relative to the machine
capacity). In this regime, our approach asymptotically converges to a 4/3 approximation. More
importantly, our model and algorithms allow us to draw interesting insights on how one should
schedule jobs. In particular, our approach (i) translates to a transparent recipe on how to assign
jobs to machines; (ii) explicitly exploits the risk pooling effect; and (iii) can be used to guide an
overcommitment strategy that significantly reduces the cost of purchasing machines.
We apply our algorithm to a synthetic but realistic workload inspired by historical production workloads in Google data centers, and show that it yields good performance. In particular,
our method reduces the necessary number of physical machines, while limiting the risk borne by
the provider. Our analysis also formalizes intuitions and provides insights regarding effective job
scheduling strategies in practical settings.
1.1.

Contributions

Scheduling jobs on machines can be modeled as a bin packing problem. Jobs arrive online with
some requirements, and the scheduler decides how many machines to purchase and how to schedule
the jobs. Assuming random job sizes and limited machine capacities, one can formulate the problem
as a 0/1 integer program. The objective is to minimize the number of machines required, subject
to constraints on the capacity of each machine. In this paper, we model the capacity constraints as
chance constraints, and study the potential benefit of overcommitment. The contributions of the
paper can be summarized as follows.

4

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

• Formulating the overcommitment bin packing problem.

We present an optimization formulation for scheduling jobs on machines, while allowing the provider
to overcommit. We first model the problem as Bin Packing with Chance Constraints (BPCC). Then,
we present an alternative Submodular Bin Packing (SMBP) formulation that explicitly captures
the risk pooling effect on each machine. We show that the SMBP is equivalent to the BPCC under
common assumptions (independent Gaussian usage distributions), and that it is distributionally
robust for usages with given means and diagonal covariance matrix). Perhaps most importantly
from a practical perspective, the SMBP provides an upper bound and a good approximation under
generic independent distributions over bounded intervals (see Proposition 1). This last setting is
most common in today’s cloud data centers, where virtual machines are sold as fixed-size units.
• Developing simple algorithms that guarantee a constant factor approximation from optimal.

We show that our (SMBP) problem can be solved by well-known online algorithms such as First-Fit
and Best-Fit, while guaranteeing a constant factor of 8/3 from optimal (Theorem 2). We further
refine this result in the case where a large number of jobs can be scheduled on each machine, and
obtain a 4/3 approximation asymptotically (Corollary 1). We also develop an improved constant
guarantee of 9/4 for the online problem using First-Fit (Theorem 4), and a 2 approximation for
the offline version (Theorem 6). We then use our analysis to infer how one should assign jobs to
machines, and show how to obtain a nearly optimal assignment (Theorem 5).
• Using our model to draw practical insights on the overcommitment policy.

Our approach translates to a transparent and meaningful recipe on how to assign jobs to machines
by clustering similar jobs in terms of statistical information. In addition, our approach explicitly
captures the risk pooling effect: as we assign more jobs to a given machine, the “safety buffer”
needed for each job decreases. Finally, our approach can be used to guide a practical overcommitment strategy, where one can significantly reduce the cost of purchasing machines by allowing a
low risk of violating capacity constraints.
• Calibrating and applying our model to a practical setting.

We use realistic workload data inspired by Google Compute Engine to calibrate our model and test
our results in a practical setting. We observe that our proposed algorithm outperforms other natural
scheduling schemes, and realizes a cost saving of 1.5% to 17% relative to the no-overcommitment
policy.
1.2.

Literature review

This paper is related to different streams of literature.
In the optimization literature, the problem of scheduling jobs on virtual machines has been
studied extensively, and the bin packing problem is a common formulation. Hundreds of papers

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

5

study the bin packing problem including many of its variations, such as 2D packing (e.g., Pisinger
and Sigurd (2005)), linear packing, packing by weight, packing by cost, online bin packing, etc.
The basic bin packing problem is NP-hard, and Delorme et al. (2016) provide a recent survey of
exact approaches. However, several simple online algorithms are often used in practice for largescale instances. A common variation is the problem where jobs arrive online with sizes sampled
independently from a known discrete distribution with integer support and must be immediately
packed onto machines upon arrival. The size of a job is known when it arrives, and the goal is
to minimize the number of non-empty machines (or equivalently, minimize the waste, defined as
the total unused space). For this variation, the sum-of-squares heuristic represents the state-ofthe-art. It is almost distribution-agnostic, and nearly universally optimal for most distributions by
achieving sublinear waste in the number of items seen (see, Csirik et al. (2006)). In Gupta and
Radovanovic (2012), the authors propose two algorithms based on gradient descent on a suitably
√
defined Lagrangian relaxations of the bin packing linear program that achieve additive O( N )
waste relative to the optimal policy. This line of work bounds the expected waste for general classes
of job size distribution in an asymptotic sense.
Worst-case analysis of (finite, deterministic) bin packing solutions has received a lot of attention
as well. For deterministic capacity constraints, several efficient algorithms have been proposed.
They can be applied online, and admit approximation guarantees in both online and offline settings. The offline version of the problem can be solved using (1 + )OP T + 1 bins in linear time
(de La Vega and Lueker (1981)). A number of heuristics can solve large-scale instances efficiently
while guaranteeing a constant factor cost relative to optimal. For a survey on approximation algorithms for bin packing, see for example Coffman Jr et al. (1996). Three such widely used heuristics
are First-Fit (FF), Next-Fit (NF) and Best-Fit (BF) (see, e.g., Bays (1977), Keller et al. (2012) and
Kenyon et al. (1996)). FF assigns the newly arrived job to the first machine that can accommodate
it, and purchase a new machine only if none of the existing ones can fit the new job. NF is similar to
FF but continues to assign jobs from the current machine without going back to previous machines.
BF uses a similar strategy but seeks to fit the newly arrived job to the machine with the smallest
remaining capacity. While one can easily show that these heuristics provide a 2-approximation
guarantee, improved factors were also developed under special assumptions. Dósa and Sgall (2013)
provide a tight upper bound for the FF strategy, showing that it never needs more than 1.7OP T
machines for any input. The offline version of the problem also received a lot of attention, and
the Best-Fit-Decreasing (BFD) and First-Fit-Decreasing (FFD) strategies are among the simplest
(and most popular) heuristics for solving it. They operate like BF and FF but first rank all the
jobs in decreasing order of size. Dósa (2007) show that the tight bound of FFD is 11/9OP T + 6/9.

6

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

Our problem differs as our goal is to schedule jobs before observing the realization of their size. In
this case, stochastic bin packing models, where the job durations are modeled as random variables,
are particularly relevant. Coffman et al. (1980) consider the problem and study the asymptotic and
convergence properties of the Next-Fit online algorithm. Lueker (1983) considers the case where
the job durations are drawn uniformly from intervals of the form [a, b], and derive a lower bound
on the asymptotic expected number of bins used in an optimum packing. However, unlike this and
other asymptotic results where the jobs’ sizes are known when scheduling occurs, we are interested
in computing a solution that is feasible with high probability before observing the actual sizes.
Our objective is to assign the jobs to as few machines as possible such that the set of jobs assigned
to each machine satisfies the capacity constraint with some given probability (say 99%). In other
words, we are solving a stochastic optimization problem, and studying/analyzing different simple
heuristic solutions to achieve this goal. To make the difference with the worst case analysis clear,
we note that the worst case analysis becomes a special case of our problem when the objective
probability threshold is set to 100% (instead of 99%, or any other number strictly less than 1). The
whole point of our paper is to exploit the stochastic structure of the problem in order to reduce
the scheduling costs via overcommitment.
In this paper, we consider an auxiliary deterministic bin packing problem with a linear cost but
non-linear modified capacity constraints. In Anily et al. (1994), the authors consider general cost
structures with linear capacity constraints. More precisely, the cost of a machine is assumed to
be a concave and monotone function of the number of jobs in the machine. They show that the
Next-Fit Increasing heuristic provides a worst-case bound of no more than 1.75, and an asymptotic
worst-case bound of 1.691.
The motivation behind this paper is similar to the overbooking policy for airline companies and
hotels. It is very common for airlines to overbook and accept additional reservations for seats on a
flight beyond the aircraft’s seating capacity1 . Airline companies (and hotels) employ an overbooking
strategy for several reasons, including: (i) no-shows (several passengers are not showing up to their
flight, and the airline can predict the no-show rate for each itinerary); (ii) increasing the profit
by reducing lost opportunities; and (iii) segmenting passengers (charging a higher price as we get
closer to the flight). Note that in the context of this paper, the same motivation of no-shows
applies. However, the inter-temporal price discrimination is beyond the scope of our model. Several
academic papers in operations research have studied the overbooking problem within the last forty
years (see, e.g., Rothstein (1971), Rothstein (1985), Weatherford and Bodily (1992), Subramanian
et al. (1999) and Karaesmen and Van Ryzin (2004)). The methodology is often based on solving
1

http://www.forbes.com/2009/04/16/airline-tickets-flights-lifestyle-travel-airlines-overbooked.html

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

7

a dynamic program incorporating some prediction of the no-show rate. In our problem, we face a
large-scale bin packing problem that needs to be solved online. Rather than deciding how many
passengers (jobs) to accept and at what price, cloud providers today usually aim to avoid declining
any reasonable workloads at a fixed list price2 .
This paper is also related to the robust optimization literature, and especially to distributionally
robust optimization. The goal is to solve an optimization problem where the input parameter distribution belongs to a family of distributions that share some properties (e.g., all the distributions
with the same mean and covariance matrix) and consider the worst-case within the given family
(concrete examples are presented in Section 2.4). Examples of such work include: Ghaoui et al.
(2003), Bertsimas and Popescu (2005), Calafiore and El Ghaoui (2006) and Delage and Ye (2010).
That work aims to convert linear or convex (continuous) optimization problems with a chance constraint into tractable formulations. Our paper shares a similar motivation but considers a problem
with integer variables. To the best of our knowledge, this paper is the first to develop efficient algorithms with constant approximation guarantees for the bin packing problem with capacity chance
constraints.
Large-scale cluster management in general is an important area of computer systems research.
Verma et al. (2015) provide a full, modern example of a production system. Among the work
on scheduling jobs, Sindelar et al. (2011) propose a model that also has a certain submodular
structure due to the potential for sharing memory pages between virtual machines (in contrast
to the risk-pooling effect modeled in this paper). Much experimental work seek to evaluate the
real-world performance of bin packing heuristics that also account for factors such as adverse
interactions between jobs scheduled together, and the presence of multiple contended resources
(see for example Rina Panigrahy (2011) and Alan Roytman (2013)). While modeling these aspects
is likely to complement the resource savings achieved with the stochastic model we propose, these
papers capture fundamentally different efficiency gains arising from technological improvements
and idiosyncratic properties of certain types (or combinations) of resources. In this paper, we limit
our attention to the benefit and practicality of machine over-commitment in the case where a single
key resource is in short supply. This applies directly to multi-resource settings if, for example, the
relatively high cost of one resource makes over-provisioning the others worthwhile, or if there is
simply an imbalance between the relative supply and demand for the various resources making one
of the resources scarce.
Structure of the paper. In Section 2, we present our model and assumptions. Then, we
present the results and insights for special cases in Section 3. In Section 4, we consider the general
2

The ”spot instances” provided by Amazon and other heavily discounted reduced-availability services are notable
exceptions.

8

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

case and develop a class of efficient approximation algorithms that guarantee a constant factor
from optimal. In Section 5, we exploit the structure of the problem in order to obtain a nearly
optimal assignment and to draw practical insights. In Sections 6 and 7, we present extensions and
computational experiments using realistic data respectively. Finally, our conclusions are reported
in Section 8. Most of the proofs of the Theorems and Propositions are relegated to the Appendix.

2.

Model

In this section, we present the model and assumptions we impose. We start by formulating the
problem we want to solve, and then propose an alternative formulation. As we previously discussed,
job requests for cloud services (or any other resource allocation problem) come with a requested
capacity. This can be the memory or CPU requirements for virtual machines in the context of
cloud computing, or job duration in more traditional scheduling problems where jobs are processed
sequentially3 . We refer to Aj as the size of job j and assume that Aj is a random variable. Historical
data can provide insight into the distribution of Aj . For simplicity, we first consider the offline
version of the problem where all the jobs arrive simultaneously at time 0, and our goal is to pack
the jobs onto the minimum possible number of machines. Jobs cannot be delayed or preempted.
The methods we develop in this paper can be applied in the more interesting online version of
the problem, as we discuss in Section 4. We denote the capacity of machine i by Vi . Motivated by
practical problems, and in accordance with prior work, we assume that all the machines have the
same capacity, i.e., Vi = V ; ∀i. In addition, each machine costs ci = c, and our goal is to maximize
the total profit (or equivalently, minimize the number of machines), while scheduling all the jobs
and satisfying the capacity constraints. Note that we consider a single dimensional problem, where
each job has one capacity requirement (e.g., the number of virtual CPU cores or the amount of
memory). Although cloud virtual machine packing may be modeled as a low-dimensional vector bin
packing problem (see for example, Rina Panigrahy (2011)), one resource is often effectively binding
and/or more critical so that focusing on it offers a much larger opportunity for overcommitment4 .

3

Although there is also a job duration in cloud computing, it is generally unbounded and hence, even less constrained
than the resource usage from the customer’s perspective. The duration is also less important than the resource usage,
since most virtual machines tend to be long-lived, cannot be delayed or pre-empted, and are paid for by the minute.
In contrast, over-allocating unused, already paid-for resources can have a large impact on efficiency.
4

Insofar as many vector bin packing heuristics are actually straightforward generalizations of the FF, NF and BF
rules, it will become obvious how our proposed algorithm could similarly be adapted to the multi-resource setting in
Section 4, although we do not pursue this idea in this paper.

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

2.1.

9

Bin packing problem

For the case where Aj is deterministic, we obtain the classical deterministic bin packing problem:
B = min

xij ,yi

s.t.

N
X

yi

i=1
N
X
j=1
N
X

Aj xij ≤ V yi

∀i

(DBP)
xij = 1

∀j

i=1

xij ∈ {0, 1}
yi ∈ {0, 1}

∀i, j
∀i

For the offline version, we have a total of N jobs and we need to decide which machines to
use/purchase (captured by the decision variable yi that is equal to 1, if machine i is purchased
and 0 otherwise). The solution is a B-partition of the set {1, 2, . . . , N } that satisfies the capacity
constraints. The decision variable xij equals one if job j is assigned to machine i and zero otherwise.
As we discussed in Section 1.2, there is an extensive literature on the DBP problem and its many
variations covering both exact algorithms as well and approximation heuristics with performance
bounds.
The problem faced by a cloud provider is typically online in nature since jobs arrive and depart
over time. Unfortunately, it is not possible to continually re-solve the DBP problem as the data is
updated for both practical and computational reasons. Keeping with the majority of prior work,
we start by basing our algorithms on static, single-period optimization formulations like the DBP
problem, rather than explicitly modeling arrivals and departures. The next section explains how,
unlike prior work, our single-period optimization model efficiently captures the uncertainty faced
by a cloud provider. We will consider both the online and offline versions of our model.
We remark that, while our online analysis considers sequentially arriving jobs, none of our results
explicitly considers departing jobs. This is also in line with the bin-packing literature, where results
usually apply to very general item arrival processes {Aj }, but it is typically assumed that packed
items remain in their assigned bins. In practice, a large cloud provider is likely to be interested
in a steady-state where the distribution of jobs in the systems is stable over time (or at least
predictable), even if individual jobs come and go. Whereas the online model with arrivals correctly
reflects that the scheduler cannot optimize to account for unseen future arrivals, it is unclear if
and how additionally modeling departures would affect a system where the overall distribution of
jobs remains the same over time. We therefore leave this question open. Note that several works
consider bin-packing with item departures (see, e.g., Stolyar and Zhong (2015) and the references
therein). In this work, the authors design a simple greedy algorithm for general packing constraints
and show that it can be asymptotically optimal.

10

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

2.2.

Chance constraints

The DBP problem suffers from the unrealistic assumption that the jobs’ sizes Aj are deterministic. In reality, jobs’ requirements (or durations) can be highly unpredictable and quite volatile,
especially from the perspective of a cloud provider with no control over the software executed in
a virtual machine. Ensuring that the capacity constraints are satisfied for any realization of Aj
generally yields a conservative outcome. For example, if the jobs’ true requirements are Bernoulli
random variables taking on either 0.3 or 1.0 with equal probability, one needs to plan as if each
job consumes a capacity of 1.0. By overcommitting resources, the provider can reduce the cost
significantly. Caution is required however, since overcommitting can be very expensive if not done
properly. Planning according to the expected value (in the previous simple example, 0.65), for
instance, would result in capacity being too tight on many machines. Specifically, for large machines,
the realized requirements could exceed capacity up to half of the time. Depending on the specific
resource and the degree of violation, such performance could be catastrophic for a cloud service
provider. Concretely, sustained CPU contention among virtual machines would materially affect
customers’ performance metrics, whereas a shortage of available memory could require temporarily
“swapping” some data to a slower storage medium with usually devastating consequences on performance. Other mitigations are possible, including migrating a running virtual machine to another
host, but these also incur computational overhead for the provider and performance degradation for
the customer. In the extreme case where overly optimistic scheduling results in inadequate capacity
planning, there is even a stock-out risk where it is no longer possible to schedule all customers’ jobs
within a data center. With this motivation in mind, our goal is to propose a formulation that finds
the right overcommitment policy. We will show that by slightly overcommitting (defined formally
in Section 2.3), one can reduce the costs significantly while satisfying the capacity constraints with
high probability.
While not strictly required by our approach, in practice, there is often an upper bound on Aj ,
denoted by Āj . In the context of cloud computing, Āj is the requested capacity that a virtual
machine is not allowed to exceed (32 CPU cores, or 128 GB of memory, say). However, the job
may end up using much less, at least for some time. If the cloud provider schedules all the jobs
according to their respective upper bounds Āj , then there is no overcommitment. If the cloud
provider schedules all the jobs according to some sizes smaller than the Āj , then some of the
machines may be overcommitted.
We propose to solve a bin packing problem with capacity chance constraints. Chance constraints
are widely used in optimization problems, starting with Charnes and Cooper (1963) for linear

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

11

programs, and more recently in convex optimization (see, e.g., Nemirovski and Shapiro (2006)) and
in finance (see, e.g., Abdelaziz et al. (2007)). In this case, the capacity constraints are replaced by:

P

N
X


Aj xij ≤ V yi ≥ α,

(1)

j=1

where α represents the confidence level of satisfying the constraint (α = 0.999, say) and is exogenously set by the cloud provider depending on considerations such as typical job’s running time
and contractual agreements. Note that when α = 1, this corresponds to the setting with no overcommitment, or in other words, to the worst-case solution that covers all possible realizations of
all the Aj ’s. One of our goals is to study the trade-off between the probability of violating physical
capacity and the cost reduction resulting from a given value of α.
The problem becomes the bin packing with chance constraints, parameterized by α:
B(α) = min

N
X

xij ,yi

s.t.

yi

i=1

P

N
X


Aj xij ≤ V yi ≥ α

∀i

j=1
N
X

xij = 1

(BPCC)
∀j

i=1

xij ∈ {0, 1}
yi ∈ {0, 1}
2.3.

∀i, j
∀i

Overcommitment

One can define the overcommitment level as follows. Consider two possible (equivalent) benchmarks. First, one can solve the problem for α = 1, and obtain a solution (by directly solving the
IP or any other heuristic method) with objective B(1). Then, we solve the problem for the desired
value α < 1. The overcommitment benefit can be defined as 0 < B(α)/B(1) ≤ 1. It is also interesting
to compare the two different jobs assignments.
The second definition goes as follows. We define the overcommitment factor as the amount of
sellable capacity divided by the physical capacity of machines in the data center, that is:
P
j Āj
OCF (α) , P
.
i V yi
Since we assume that all the machines have the same capacity and cost, we can write:
P

P
Āj
j Āj
OCF (α) =
≥
= OCF (1).
V B(α) V B(1)
j

12

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

Note that OCF(1) is (generally strictly) less than one, as the bin packing overhead prevents the
sale of all resources5 . Then, we have:
OCF (1) B(α)
=
.
OCF (α) B(1)
For illustration purposes, consider the following simple example with N = 70 1-core jobs. The jobs
are independent and Bernoulli distributed with probability 0.5. In particular, the jobs are either
high usage (i.e., fully utilize the 1 core), or low usage (in this case, idle). Each machine has a
capacity V = 48 cores. Without overcommitting, we need 2 machines, i.e., B(1) = 2. What happens
if we schedule all the jobs in a single machine? In this case, one can reduce the cost (number of
machines) by half, while satisfying the capacity constraint with probability 0.9987. In other words,
B(0.99) = 1. The overcommitment benefit in this simple example is clear. Our goal is to formalize
a systematic way to overcommit in more complicated and realistic settings.
Note that overcommitment may lead to Service Level Agreement (SLA) violations. This paper
does not discuss in detail the SLAs (with some possible associated metrics), and the corresponding
estimation/forecast procedures as they are usually application and resource specific. Instead, this
research treats a general Virtual Machine (VM) scheduling problem. More precisely, our context
is that of a cloud computing provider with limited visibility into the mix of customer workloads,
and hard SLAs. While the provider does track numerous service-level indicators, they are typically
monotonic in the resource usage on average (we expect more work to translate to worse performance). Therefore, we believe that it is reasonable to rely on resource utilization as the sole metric
in the optimization problem.
2.4.

A variant of submodular bin packing

In this section, we propose an alternative formulation that is closely related to the (BPCC) problem.
Under some mild assumptions, we show that the latter is either exactly or approximately equivalent
to the following submodular bin packing problem:
BS (α) = min

xij ,yi

s.t.

N
X

yi

i=1

PN

j=1 µj xij + D(α)

N
X

qP

N
j=1 bj xij

≤ V yi

∀i

(SMBP)
xij = 1

∀j

i=1

xij ∈ {0, 1}
yi ∈ {0, 1}
5

∀i, j
∀i

Technical note: other production overheads such as safety stocks for various types of outages and management
overheads, are generally also included in the denominator. For the purpose of this paper, we omit them.

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

13

The difference between the (BPCC) and the (SMBP) problems is the way the capacity constraints
are written. Here, we have replaced each chance constraint with a linear term plus a square root
term. These constraints are submodular with respect to the vector x. The variable µj denotes the
expected value of Aj . In what follows, we will consider different definitions of bj and D(α) in three
different settings. The first two are concrete motivational examples, whereas the third one is a
generalization. In each case, we formally show the relation between the (BPCC) and the (SMBP)
problems.
1. Gaussian case: Assume that the random variables Aj are Gaussian and independent. In this
PN
case, the random variable Z = j=1 Aj xij for any given binary vector x is Gaussian, and therefore,
one can use the following simplification:
P

N
X




Aj xij ≤ V yi = P Z ≤ V yi ≥ α.

j=1

For each machine i, constraint (1) becomes:
N
X

v
u N
uX
−1
σj2 xij ≤ V yi ,
µj xij + Φ (α) · t

(2)

j=1

j=1

where Φ−1 (·) is the inverse CDF of a normal N (0, 1), µj = E[Aj ] and σj2 = Var(Aj ). Note that we
have used the fact that x is binary so that x2ij = xij . Consequently, the (BPCC) and the (SMBP)
problems are equivalent with the values bj = σj2 and D(α) = Φ−1 (α).
When the random variables Aj are independent but not normally distributed, if there are a
large number of jobs per machine, one can apply the Central Limit Theorem and obtain a similar
approximate argument. In fact, using a result from Calafiore and El Ghaoui (2006), one can extend
this equivalence to any radial distribution6 .
2. Hoeffding’s inequality: Assume that the random variables Aj are independent with a finite
support [Aj , Aj ], 0 ≤ Aj < Aj with mean µj . As we discussed, one can often know the value of Aj
and use historical data to estimate µj and Aj (we discuss this in more detail in Section 7). Assume
PN
that the mean usages fit on each machine, i.e.,
j=1 xij µj < yi Vi . Then, Hoeffding’s inequality
states that:
P

N
X



Aj xij ≤ V yi ≥ 1 − e

P
2
−2[V yi − N
j=1 µj xij ]
PN
2
(A −Aj )
j=1 j

.

j=1

Equating the right hand side to α, we obtain:
PN
−2[V yi − j=1 µj xij ]2
= ln(1 − α),
PN
b
x
j
ij
j=1
6

Radial distributions include all probability densities whose level sets are ellipsoids. The formal mathematical definition can be found in Calafiore and El Ghaoui (2006).

14

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

where bj = (Aj − Aj )2 represents the range of job j’s usage. Re-arranging the equation, we obtain
for each machine i:
N
X

v
u N
uX
µj xij + D(α)t
bj xij ≤ V yi ,

j=1

where in this case, D(α) =

p

(3)

j=1

−0.5 ln(1 − α). Note that in this setting the (BPCC) and the (SMBP)

problems are not equivalent. We only have that any solution of the latter is a feasible solution for
the former. We will demonstrate in Section 7 that despite being very conservative, this formulation
based on Hoeffding’s inequality actually yields good practical solutions.
The next case is a generalization of the last two.
3. Distributionally robust formulations: Assume that the random variables Aj are independent with some unknown distribution. We only know that this distribution belongs to a family
of probability distributions D. We consider two commonly used examples of such families. First,
we consider the family D1 of distributions with a given mean and (diagonal) covariance matrix,
µ and Σ, respectively. Second, we look at D2 , the family of generic distributions of independent
random variables over bounded intervals [Aj , Aj ].
In this setting, the chance constraint is assumed to be enforced robustly with respect to the
entire family D of probability distributions on A = (A1 , A2 , . . . , AN ), meaning that:
inf P

A∼D

N
X


Aj xij ≤ V yi ≥ α.

(4)

j=1

In this context, we have the following result.
Proposition 1. Consider the robust bin packing problem with the capacity chance constraints
(4) for each machine i. Then, for any α ∈ (0, 1), we have:
• For the family D1 of distributions with a given mean and diagonal covariance matrix, the
p
robust problem is equivalent to the (SMBP) with bj = σj2 and D1 (α) = α/(1 − α).
• For the family D2 of generic distributions of independent random variables over bounded inter-

vals, the robust problem can be approximated by the (SMBP) with bj = (Aj − Aj )2 and D2 (α) =
p
−0.5 ln(1 − α).
The details of the proof are omitted for conciseness. In particular, the proof for D1 is analogous to
an existing result in continuous optimization that converts linear programs with a chance constraint
into a linear program with a convex second-order cone constraint (see Calafiore and El Ghaoui
(2006) and Ghaoui et al. (2003)). The proof for D2 follows directly from the fact that Hoeffding’s
inequality applies for all such distributions, and thus for the infimum of the probability.

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

15

We have shown that the (SMBP) problem is a good approximation for the bin packing problem
with chance constraints. For the case of independent random variables with a given mean and
covariance, the approximation is exact and for the case of distributions over independent bounded
intervals, the approximation yields a feasible solution. We investigate practical settings in Section
7, and show that these approximate formulations all yield good solutions to the original problem.
From now on, we consider solving the (SMBP) problem, that is repeated here for convenience:

BS (α) = min

xij ,yi

s.t.

N
X

yi

i=1

PN

j=1 µj xij + D(α)

N
X

qP

N
j=1 bj xij

≤ V yi

∀i

(SMBP)
xij = 1

∀j

i=1

xij ∈ {0, 1}
yi ∈ {0, 1}

∀i, j
∀i

As discussed, the capacity constraint is now replaced by the following equation, called the modified
capacity constraint:
N
X
j=1

v
u N
uX
µj xij + D(α)t
bj xij ≤ V yi .

(5)

j=1

One can interpret equation (5) as follows. Each machine has a capacity V . Each job j consumes
capacity µj in expectation, as well as an additional buffer to account for the uncertainty. This
buffer depends on two factors: (i) the variability of the job, captured by the parameter bj ; and (ii)
the acceptable level of risk through D(α). The function D(α) is increasing in α, and therefore we
impose a stricter constraint as α approaches 1 by requiring this extra buffer to be larger.
Equation (5) can also be interpreted as a risk measure applied by the scheduler. For each machine
PN
i, the total (random) load is j=1 Aj xij . If we consider that µj represents the expectation and bj
qP
PN
N
corresponds to the variance, then j=1 µj xij and
j=1 bj xij correspond to the expectation and
the standard deviation of the total load on machine i respectively. As a result, the right hand side of
equation (5) can be interpreted as an adjusted risk utility, where D(α) is the degree of risk aversion
of the scheduler. The additional amount allocated for job j can be interpreted as a safety buffer to
account for the uncertainty and for the risk that the provider is willing to bear. As we discussed,
this extra buffer decreases with the number of jobs assigned to the same machine. In Section 4, we
develop efficient methods to solve the (SMBP) with analytical performance guarantees.

16

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

2.5.

Two naive approaches

In this section, we explore the limitations of two approaches that come to mind. The first attempt
is to rewrite the problem as a linear integer program: the decision variables are all binary and the
non-linearity in (SMBP) can actually be captured by common modeling techniques, as detailed
in Appendix A. Unfortunately, solving this IP is not a viable option. Similarly as for the classical
deterministic bin packing problem, solving even moderately large instances with commercial solvers
takes several hours. Moreover, applying the approach to smaller, specific toy instances provides
little insight about the assignment policy, and how the value of α affects the solution. Since our
goal is to develop practical strategies for the online problem, we chose not to further pursue exact
solutions.
The second potential approach is to develop an algorithm for a more general problem: the
bin packing with general monotone submodular capacity constraints. Unfortunately, using some
machinery and results from Goemans et al. (2009) and Svitkina and Fleischer (2011), we next show
that it is in fact impossible to find a solution within any reasonable factor from optimal.
Theorem 1. Consider the bin packing problem with general monotone submodular capacity constraints for each machine. Then, it is impossible to guarantee a solution within a factor better than
√
N
ln(N )

from optimal.

The proof can be found in Appendix A. We will show that the (SMBP) problem that we consider
is more tractable as it concerns only a specific class of monotone submodular capacity constraints
that capture the structure of the chance-constrained problem. In the next session, we start by
addressing simple special cases in order to draw some structural insights.

3.

Results and insights for special cases

In this section, we consider the (SMBP) problem for some given µj , bj , N and D(α). Our goals are
to: (i) develop efficient approaches to solve the problem; (ii) draw some insights on how to schedule
the different jobs and; (iii) study the effect of the different parameters on the outcome. This will
ultimately allows us to understand the impact of overcommitment in resource allocation problems,
such as cloud computing.
3.1.

Identical distributed jobs

We consider the symmetric setting where all the random variables Aj have the same distribution,
such that µj = µ and bj = b in the (SMBP) problem. By symmetry, we only need to find the number
of jobs n to assign to each machine. Since all the jobs are interchangeable, our goal is to assign as

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

17

many jobs as possible in each machine. In other words, we want to pick the largest value of n such
that the constraint (5) is satisfied, or equivalently:
√
nµ + D(α) nb ≤ V
[V − nµ]2
D(α)2 ≤
.
nb

For a given value of α, this is the largest integer smaller than:
n(α) =

p

1 
V
+ 2 bD(α)2 − b2 D(α)4 + 4bD(α)2 V µ .
µ 2µ

(6)

• For a given value of α, the number of jobs n(α) increases with V /µ. Indeed, since µ represents

the expected job size, increasing the ratio V /µ is equivalent to increasing the number of ”average”
jobs a machine can host. If the jobs are smaller or the machines larger, one can fit more jobs per
machine, as expected.
• For a given value of V /µ, n(α) is a non-increasing function of α. When α increases, it means

that we enforce the capacity constraint in a stricter manner (recall that α = 1 corresponds to the
case without overcommitment). As a result, the number of jobs per machine cannot increase.
• For given values of α and V /µ, n(α) is a non-increasing function of b. Recall that the parameter

b corresponds to some measure of spread (the variance in the Gaussian setting, and the range for
distributions with bounded support). Therefore, when b increases, it implies that the jobs’ resource
usage is more volatile and hence, a larger buffer is needed. Consequently, the number of jobs cannot
increase when b grows.
• For given values of α and V , n(α) is non-increasing with

√

b/µ. The quantity

√

b/µ represents

the coefficient of variation of the random job size in the Gaussian case, or a similarly normalized
measure of dispersion in other cases. Consequently, one should be able to fit less jobs, as the
variability increases.
The simple case of identically distributed jobs allows us to understand how the different factors
affect the number of jobs that one can assign to each machine. In Figure 1, we plot equation (6)
for an instance with A = 1, A = 0.3, µ = 0.65, V = 30 and 0.5 ≤ α < 1. The large dot for α = 1
in the figure represents the case without overcommitment (i.e., α = 1). Interestingly, one can see
that when the value of α approaches 1, the benefit of allowing a small probability of violating the
capacity constraint is significant, so that one can increase the number of jobs per machine. In this
case, when α = 1, we can fit 30 jobs per machine, whereas when α = 0.992, we can fit 36 jobs,
hence, an improvement of 20%. Note that this analysis guarantees that the capacity constraint is
satisfied with at least probability α. As we will show in Section 7 for many instances, the capacity
constraint is satisfied with an even higher probability.

18

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

Figure 1

Parameters: A = 1, A = 0.3, µ = 0.65, V = 30

Alternatively, one can plot α as a function of n (see Figure 2a for an example with different
values for V /µ). As expected, the benefit of overcommitting increases with V /µ, i.e., one can fit a
larger number of jobs per machine. In our example, when V /µ = 25, by scheduling jobs according
to A (i.e., α = 1, no overcommitment), we can schedule 14 jobs, whereas if we allow a 0.1%
violation probability, we can schedule 17 jobs. Consequently, by allowing 0.1% chance of violating
the capacity constraint, one can save more than 20% in costs.

(a) Parameters: A = 1, A = 0.3, µ = 0.65
Figure 2

(b) Parameters: V = 30

Example for identically distributed jobs

We next discuss how to solve the problem for the case with a small number of different classes
of job distributions.

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

3.2.

19

Small number of job distributions

We now consider the case where the random variables Aj can be clustered in few different categories.
For example, suppose standard clustering algorithms are applied to historical data to treat similar
jobs as a single class with some distribution of usage. For example, one can have a setting with
four types of jobs: (i) large jobs with no variability (µj is large and bj is zero); (ii) small jobs with
no variability (µj is small and bj is zero); (ii) large jobs with high variability (both µj and bj are
large); and (iv) small jobs with high variability (µj is small and bj is high). In other words, we
have N jobs and they all are from one of the 4 types, with given values of µj and bj . The result for
this setting is summarized in the following Observation (the details can be found in Appendix C).
Observation 1. In the case where the number of different job classes is not too large, one can
solve the problem efficiently as a cutting stock problem.
The resulting cutting stock problem (see formulation (14) in Appendix C) is well studied in many
contexts (see Gilmore and Gomory (1961) for a classical approach based on linear programming,
or the recent survey of Delorme et al. (2016)). For example, one can solve the LP relaxation of
(14) and round the fractional solution. This approach can be very useful for cases where the cloud
provider have enough historical data, and when the jobs can all be regrouped into a small number
of different clusters. This situation is sometimes realistic but not always. Very often, grouping all
possible customer job profiles into a small number of classes, each described by a single distribution
is likely unrealistic in many contexts. For example, virtual machines are typically sold with 1, 2, 4,
8, 16, 32 or 64 CPU cores, each with various memory configurations, to a variety of customers with
disparate use-cases. Aggregating across these jobs is already dubious, before considering differences
in their usage means and variability. Unfortunately, if one decides to use a large number of job
classes, solving a cutting stock problem is not scalable. In addition, this approach requires advance
knowledge of the number of jobs of each class and hence, cannot be applied to the online version
of our problem.

4.

Online constant competitive algorithms

In this section, we analyze the performance of a large class of algorithms for the online version of
problem (SMBP). We note that the same guarantees hold for the offline case, as it is just a simpler
version of the problem. We then present a refined result for the offline problem in Section 6.1.
4.1.

Lazy algorithms are 38 -competitive

An algorithm is called lazy, if it does not purchase/use a new machine unless necessary. The formal
definition is as follows.
Definition 1. We call an online algorithm lazy if upon arrival of a new job, it assigns the job
to one of the existing (already purchased) machines given the capacity constraints are not violated.

20

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

In other words, the algorithm purchases a new machine if and only if non of the existing machines
can accomodate the newly arrived job.
Several commonly used algorithms fall into this category, e.g., First-Fit, Best-Fit, Next-Fit,
greedy type etc. Let OP T be the optimal objective, i.e., the minimum number of machines needed
to serve all the jobs {1, 2, · · · , N }. Recall that in our problem, each job 1 ≤ j ≤ N , has two characteristics: µj and bj which represent the mean and the uncertain part of job j respectively. For a
qP
P
set of jobs S, we define the corresponding cost Cost(S) to be j∈S µj +
j∈S bj . Without loss of
generality, we can assume (by normalization of all µj and bj ) that the capacity of each machine is
1 and that D(α) is also normalized to 1. We call a set S feasible, if its cost is at most the capacity
limit 1. In the following Theorem, we show that any lazy algorithm yields a constant approximation
for the (SBBP) problem.
Theorem 2. Any lazy algorithm ALG purchases at most 83 OP T machines, where OP T is the
optimum number of machines to serve all jobs.
Proof.

Let m be the number of machines that ALG purchases when serving jobs {1, 2, · · · , N }.

For any machine 1 ≤ i ≤ m, we define Si to be the set of jobs assigned to machine i. Without loss
of generality, we assume that the m machines are purchased in the order of their indices. In other
words, machines 1 and m are the first and last purchased ones respectively.
For any pair of machines 1 ≤ i < i0 ≤ m, we next prove that the set Si ∪ Si0 is infeasible for the
qP
P
modified capacity constraint, i.e., j∈Si ∪S 0 µj +
j∈Si ∪S 0 bj > 1. Let j be the first job assigned
i

i

to machine i0 . Since ALG is lazy, assigning j to machine i upon its arrival time was not feasible,
i.e., the set {j } ∪ Si is infeasible. Since we only assign more jobs to machines throughout the course
of the algorithm, and do not remove any job, the set Si0 ∪ Si is also infeasible.
In the next Lemma, we lower bound the sum of µj + bj for the jobs in an infeasible set.
Lemma 1. For any infeasible set T , we have

P

j∈T (µj

+ bj ) > 34 .

qP
P
Proof. For any infeasible set T , we have by definition j∈T µj +
j∈T bj > 1. We denote
qP
P
x = j∈T µj , and y =
j∈T bj . Then, y > 1 − x. If x is greater than 1, the claim of the lemma
holds trivially. Otherwise, we obtain:
1
3 3
x + y 2 > x + (1 − x)2 = x2 − x + 1 = (x − )2 + ≥ .
2
4 4
We conclude that

P

j∈T (µj

+ bj ) > 43 . 

As discussed, for any pair of machines i < i0 , the union of their sets of jobs Si ∪ Si0 is an infeasible
set that does not fit in one machine. We now apply the lower bound from Lemma 1 for the infeasible

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

set Si ∪ Si0 and imply

P

j∈Si ∪Si0 (µj

+ bj ) > 34 . We can sum up this inequality for all

m
2



21

pairs of

machines i and i0 to obtain:
X

X

1≤i<i0 ≤m j∈Si ∪Si0

 
3 m
(µj + bj ) >
.
4 2

We claim that the left hand side of inequality (7) is equal to (m − 1)

(7)
PN

j=1 (µj

+ bj ). We note that

for each job j ∈ Sk , the term µj + bj appears k − 1 times in the left hand side of inequality (7) when
i0 is equal to k. In addition, this term also appears m − k times when i is equal to k. Therefore,
every µj + bj appears k − 1 + m − k = m − 1 times, which is independent of the index k of the
machine that contains job j. As a result, we obtain:
N
X
(µj + bj ) >
j=1

 
m
3m
3
.
=
4(m − 1) 2
8

On the other hand, we use the optimal assignment to upper bound the sum

PN

j=1 (µj +bj ),

and relate

m to OP T . Let T1 , T2 , · · · , TOP T be the optimal assignment of all jobs to OP T machines. Since Ti is
qP
P
P
a feasible set, we have j∈Ti µj +
j∈Ti bj ≤ 1, and consequently, we also have
j∈Ti (µj + bj ) ≤ 1.
PN
POP T P
Summing up for all the machines 1 ≤ i ≤ OP T , we obtain: j=1 (µj + bj ) = i=1
j∈Ti (µj + bj ) ≤
OP T . We conclude that:
OP T ≥

N
X
j=1

This completes the proof of m <

8OP T
3

(µj + bj ) >

3m
.
8

.

Theorem 2 derives an approximation guarantee of 8/3 for any lazy algorithm. In many practical
settings, one can further exploit the structure of the set of jobs, and design algorithms that achieve
better approximation factors. For example, if some jobs are usually larger relative to others, one
can incorporate this knowledge into the algorithm. We next describe the main intuitions behind the
8/3 upper bound. In the proof of Theorem 2, we have used the following two main proof techniques:
P
• First, we show a direct connection between the feasibility of a set S and the sum j∈S (µj + bj ).
P
In particular, we prove that j∈S (µj + bj ) ≤ 1 for any feasible set, and greater than 3/4 for any
infeasible set. Consequently, OP T cannot be less than the sum of µj + bj for all jobs. The gap of
4/3 between the two bounds contributes partially to the final upper bound of 8/3.
• Second, we show that the union of jobs assigned to any pair of machines by the lazy algorithm

is an infeasible set, so that their sum of µj + bj should exceed 3/4. One can then find m/2 disjoint
pairs of machines, and obtain a lower bound of 3/4 for the sum µj + bj for each pair. The fact
that we achieve this lower bound for every pair of machines (and not for each machine) contributes
another factor of 2 to the approximation factor, resulting to

4
3

× 2 = 83 .

22

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

Note that the second loss of a factor of 2 follows from the fact that the union of any two machines
forms an infeasible set and nothing stronger. In particular, all machines could potentially have a
cost of 1/2 +  for a very small , and make the above analysis tight. Nevertheless, if we assume
that each machine is nearly full (i.e., has Cost close to 1), one can refine the approximation factor.
Theorem 3. For any 0 ≤  ≤ 0.3, if the lazy algorithm ALG assigns all the jobs to m machines
such that Cost(Si ) ≥ 1 −  for every 1 ≤ i ≤ m, we have m ≤ ( 34 + 3)OP T , i.e., a ( 43 + 3) approximation guarantee.
P
To simplify the analysis, we denote β to be 1 − . For a set Si , we define x = j∈Si µj
qP
and y =
j∈Si bj . Since Cost(Si ) is at least β, we have x + y ≥ β. Assuming x ≤ β, we have:
Proof.


2β − 1 2
1
1 3
(µj + bj ) = x + y 2 ≥ x + (β − x)2 = x −
+ β − ≥ β − = − ,
2
4
4 4
j∈S
X

i

where the first equality is by the definition of x and y, the second inequality holds by x + y ≥ α,
P
and the rest are algebraic manipulations. For x > β, we also have j∈Si (µj + bj ) ≥ x > β > 43 − .
PN
PN
We conclude that j=1 (µj + bj ) ≥ m × ( 34 − ). We also know that OP T ≥ j=1 (µj + bj ), which
implies that m ≤

OP T
3/4−

≤ OP T ( 43 + 3) for  ≤ 0.3. 

A particular setting where the condition of Theorem 3 holds is when the capacity of each machine
p
is large compared to all jobs, i.e., max1≤j≤N µj + bj is at most . In this case, for each machine
i 6= m (except the last purchased machine), we know that there exists a job j ∈ Sm (assigned to the
last purchased machine m) such that the algorithm could not assign j to machine i. This means
that Cost(Si ∪ {j }) exceeds one. Since Cost is a subadditive function, we have Cost(Si ∪ {j }) ≤
Cost(Si ) + Cost({j }). We also know that Cost({j }) ≤  which implies that Cost(Si ) > 1 − .
Remark 1. As elaborated above, there are two main sources for losses in the approximation
factors: non-linearity of the cost function that can contribute up to 4/3, and machines being only
partially full that can cause an extra factor of 2 which in total implies the 8/3 approximation
guarantee. In the classical bin packing case (i.e., bj = 0 for all j), the cost function is linear, and
the non-linearity losses in approximation factors fade. Consequently, we obtain that (i) Theorem
2 reduces to a 2 approximation factor; and (ii) Theorem 3 reduces to a (1 + ) approximation
factor, which are both consistent with known results from the literature on the classical bin packing
problem.
Theorem 3 improves the bound for the case where each machine is almost full. However, in
practice machines are often not full. In the next section, we derive a bound as a function of the
minimum number of jobs assigned to the machines.

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

4.2.

23

Algorithm First-Fit is 94 -competitive

So far, we considered the general class of lazy algorithms. One popular algorithm in this class
(both in the literature and in practice) is First-Fit. By exploring the structural properties of
allocations made by First-Fit, we can provide a better competitive ratio of

9
4

< 83 . Recall that

upon the arrival of a new job, First-Fit purchases a new machine if the job does not fit in any of
the existing machines. Otherwise, it assigns the job to the first machine (based on a fixed ordering
such as machine IDs) that it fits in. This algorithm is simple to implement, and very well studied
in the context of the classical bin packing problem. First, we present an extension of Theorem 2
for the case where each machine has at least K jobs.
Corollary 1. If the First-Fit algorithm assigns jobs such that each machine receives at least
K jobs, the number of purchased machines does not exceed

4
(1
3

+

1
)OP T ,
K

where OP T is the

optimum number of machines to serve all jobs.
One can prove Corollary 1 in a similar fashion as the proof of Theorem 2 and using the fact that
jobs are assigned using First-Fit (the details are omitted for conciseness). For example, when
K = 2 (resp. K = 5), we obtain a 2 (resp. 1.6) approximation. We next refine the approximation
factor for the problem by using the First-Fit algorithm.
Theorem 4. The number of purchased machines by Algorithm First-Fit for any arrival order
of jobs is not more than 94 OP T + 1.
The proof can be found in Appendix D. We note that the approximation guarantees we developed
in this section do not depend on the factor D(α), and on the specific definition of the parameters
µj and bj . In addition, as we show computationally in Section 7, the performance of this class of
algorithm is not significantly affected by the factor D(α).

5.

Insights on job scheduling

In this section, we show that guaranteeing the following two guidelines in any allocation algorithm
yields optimal solutions:
• Filling up each machine completely such that no other job fits in it, i.e., making each machine’s

Cost equal to 1.
• Each machine contains a set of similar jobs (defined formally next).

We formalize these properties in more detail, and show how one can achieve optimality by
qP
P
satisfying these two conditions. We call a machine full if j∈S µj +
j∈S bj is equal to 1 (recall
that the machine capacity is normalized to 1 without loss of generality), where S is the set of jobs
assigned to the machine. Note that it is not possible to assign any additional job (no matter how
small the job is) to a full machine. Similarly, we call a machine -full, if the the cost is at least 1 − ,

24

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

i.e.,

P

j∈S µj +

qP
j∈S

bj ≥ 1 − . We define two jobs to be similar, if they have the same b/µ ratio.

Note that the two jobs can have different values of µ and b. We say that a machine is homogeneous,
if it only contains similar jobs. In other words, if the ratio bj /µj is the same for all the jobs j
assigned to this machine. By convention, we define bj /µj to be +∞ when µj = 0. In addition, we
introduce the relaxed version of this property: we say that two jobs are δ-similar, if their b/µ ratios
differ by at most a multiplicative factor of 1 + δ. A machine is called δ-homogeneous, if it only
contains δ-similar jobs (i.e., for any pair of jobs j and j 0 in the same machine,

bj /µj
b0j /µ0j

is at most

1 + δ).
Theorem 5. For any  ≥ 0 and δ ≥ 0, consider an assignment of all jobs to some machines
with two properties: a) each machine is -full, and b) each machine is δ-homogeneous. Then, the
number of purchased machines in this allocation is at most

OP T
.
(1−)2 (1−δ)

The proof can be found in Appendix E.
In this section, we proposed an easy to follow recipe in order to schedule jobs to machines. Each
arriving job is characterized by two parameters µj and bj . Upon arrival of a new job, the cloud
provider can compute the ratio rj = bj /µj . Then, one can decide of a few buckets for the different
values of rj , depending on historical data, and performance restrictions. Finally, the cloud provider
will assign jobs with similar ratios to the same machines and tries to fill in machines as much as
possible. In this paper, we show that such a simple strategy guarantees a good performance (close
to optimal) in terms of minimizing the number of purchased machines while at the same time
allowing to strategically overcommit.

6.

Extensions

In this section, we present two extensions of the problem we considered in this paper.
6.1.

Offline 2-approximation algorithm

Consider the offline version of the (SMBP) problem. In this case, all the N jobs already arrived,
and one has to find a feasible schedule so as to minimize the number of machines. We propose
the algorithm Local-Search that iteratively reduces the number of purchased machines, and
also uses ideas inspired from First-Fit in order to achieve a 2-approximation for the offline
problem. Algorithm Local-Search starts by assigning all the jobs to machines arbitrarily, and
then iteratively refines this assignment. Suppose that each machine has a unique identifier number.
We next introduce some notation before presenting the update operations. Let a be the number of
machines with only one job, A1 be the set of these a machines, and S1 be the set of jobs assigned to
these machines. Note that this set changes throughout the algorithm with the update operations.

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

25

We say that a job j ∈
/ S1 is good, if it fits in at least 6 of the machines in the set A1 7 . In addition,
we say that a machine is large, if it contains at least 5 jobs, and we denote the set of large machines
by A5 . We say that a machine is medium size, if it contains 2, 3, or 4 jobs, and we denote the set
of medium machines by A2,3,4 . We call a medium size machine critical, if it contains one job that
fits in none of the machines in A1 , and the rest of the jobs in this machine are all good. Following
are the update operations that Local-Search performs until no such operation is available.
• Find a job j in machine i (i is the machine identifier number) and assign it to some other

machine i0 < i if feasible (the outcome will be similar to First-Fit).
• Find a medium size machine i that contains only good jobs. Let j1 , · · · , j` (2 ≤ ` ≤ 4) be the

jobs in machine i. Assign j1 to one of the machines in A1 that it fits in. Since j1 is a good job,
there are at least 6 different options, and the algorithm picks one of them arbitrarily. Assign j2 to
a different machine in A1 that it fits in. There should be at least 5 ways to do so. We continue
this process until all the jobs in machine i (there are at most 4 of them) are assigned to distinct
machines in A1 , and they all fit in their new machines. This way, we release machine i and reduce
the number of machines by one.
• Find a medium size machine i that contains one job j that fits in at least one machine in A1 ,

and the rest of the jobs in i are all good. First, assign j to one machine in A1 that it fits in. Similar
to the previous case, we assign the rest of the jobs (that are all good) to different machines in A1 .
This way, we release machine i and reduce the number of purchased machines by one.
• Find two critical machines i1 and i2 . Let j1 and j2 be the only jobs in these two machines

that fit in no machine in A1 . If both jobs fit and form a feasible assignment in a new machine,
we purchase a new machine and assign j1 and j2 to it. Otherwise, we do not change anything
and ignore this update step. There are at most 6 other jobs in these two machines since both are
medium machines. In addition, the rest of the jobs are all good. Therefore, similar to the previous
two cases, we can assign these jobs to distinct machines in A1 that they fit in. This way, we release
machines i1 and i2 and purchase a new machine. So in total, we reduce the number of purchased
machines by one.
We are now ready to analyze this Local-Search algorithm that also borrows ideas from
First-Fit. We next show that the number of purchased machines is at most 2OP T + O(1), i.e., a
2-approximation.
Theorem 6. Algorithm Local-Search terminates after at most N 3 operations (where N is
the number of jobs), and purchases at most 2OP T + 11 machines.
7

The reason we need 6 jobs is technical, and will be used in the proof of Theorem 6.

26

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

The proof can be found in Appendix F.
We conclude this section by comparing our results to the classical (deterministic) bin packing
problem. In the classical bin packing problem, there are folklore polynomial time approximation
schemes (see Section 10.3 in Albers and Souza (2011)) that achieve a (1 − )-approximation factor
by proposing an offline algorithm based on clustering the jobs into 1/2 groups, and treating them
as equal size jobs. Using dynamic programming techniques, one can solve the simplified problem
with 1/2 different job sizes in time O(npoly(1/) ). In addition to the inefficient time complexity of
these algorithms that make them less appealing for practical purposes, one cannot generalize the
same ideas to our setting. The main obstacle is the lack of a total ordering among the different
jobs. In the classical bin packing problem, the jobs can be sorted based on their sizes. However,
this is not true in our case since the jobs have the two dimensional requirements µj and bj .
6.2.

Alternative constraints

Recall that in the (SMBP) problem, we imposed the modified capacity constraint (5). Instead, one
can consider the following family of constraints, parametrized by 0.5 ≤ p ≤ 1:
N
X
j=1

µj xij + D(α)

N
X

bj xij

p

≤ V yi ,

(8)

j=1

Note that this equation is still monotone and submodular in the assignment vector x, and captures
some notion of risk pooling. In particular, the “safety buffer” reduces with the number of jobs
already assigned to each machine. The motivation behind such a modified capacity constraint lies
in the shape that one wishes to impose on the term that captures the uncertain part of the job. In
one extreme (p = 1), we consider that the term that captures the uncertainty is linear and hence,
as important as the expectation term. In the other extreme case (p = 0.5), we consider that the
term that captures the uncertainty behaves as a square root term. For a large number of jobs per
machine, this is known to be an efficient way of handling uncertainty (similar argument as the
central limit theorem). Note also that when p = 0.5, we are back to equation (5), and when p = 1
we have a commonly used benchmark (see more details in Section 7). One can extend our analysis
and derive an approximation factor for the online problem as a function of p for any lazy algorithm.
Corollary 2. Consider the bin packing problem with the modified capacity constraint (8).
Then, any lazy algorithm ALG purchases at most

2
OP T
f (p)

machines, where OP T is the optimum

number of machines to serve all jobs and f (p) is given by:
1

f (p) = 1 − (1 − p)p p −1 .
The proof is in a very similar spirit as in Theorem 2 and is not repeated due to space limitations.
p
PN
PN
Intuitively, we find parametric lower and upper bounds on
in terms of j=1 bj xij .
j=1 bj xij

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

27

Note that when p = 0.5, we recover the result of Theorem 2 (i.e., a 8/3 approximation) and as p
increases, the approximation factor converges to 2. In Figure 3, we plot the approximation factor
as a function of 0.5 ≤ p ≤ 1.

Figure 3

Approximation factor

2
f (p)

as a function of p

Finally, one can also extend our results for the case where the modified capacity constrain is


PN
PN
given by: j=1 µj xij + D(α) log 1 + j=1 bj xij ≤ V yi .

7.

Computational experiments

In this section, we test and validate the analytical results developed in the paper by solving
the (SMBP) problem for different realistic cases, and investigating the impact on the number of
machines required (i.e., the cost). We use realistic workload data inspired by Google Compute
Engine, and show how our model and algorithms can be applied in an operational setting.
7.1.

Setting and data

We use simulated workloads of 1000 jobs (virtual machines) with a realistic VM size distribution
(see Table 1). Typically, the GCE workload is composed of a mix of CPU usages from virtual
machines belonging to cloud customers. These jobs can have highly varying workloads, including
some large ones and many smaller ones.8 More precisely, we assume that each VM arrives to the
cloud provider with a requested number of CPU cores, sampled from the distribution presented in
Table 1.
8

The average distribution of workloads we present in Table 1 assumes small percentages of workloads with 32 and
16 cores, and larger percentages of smaller VMs. A “large” workload may consist of many VMs belonging to a single
customer whose usages may be correlated at the time-scales we are considering, but heuristics ensure these are spread
across different hosts to avoid strong correlation of co-scheduled VMs. The workload distributions we are using are
representative for some segments of GCE. Unfortunately, we cannot provide the real data due to confidentiality.

28

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

Table 1

Example distribution of VM sizes in one Google data center

Number of cores 1
2
4
8
16 32
% VMs
36.3 13.8 21.3 23.1 3.5 1.9
In this context, the average utilization is typically low, but in many cases, the utilization can be
highly variable over time. Although we decided to keep a similarl VM size distribution as observed
in a production data center, we also fitted parametric distributions to roughly match the mean and
the variance of the measured usage. This allows us to obtain a parametric model that we could vary
for simulation. We consider two different cases for the actual CPU utilization as a fraction of the
requested job size: we either assume that the number of cores used has a Bernoulli distribution, or
a truncated Gaussian distribution. As discussed in Section 2.4, we assume that each job j has lower
and upper utilization bounds, Aj and Aj . We sample Aj uniformly in the range [0.3, 0.6], and Aj
in the range [0.7, 1.0]. In addition, we uniformly sample µ0j and σj0 ∈ [0.1, 0.5] for each VM to serve
as the parameters for the truncated Gaussian (not to be confused with its true mean and standard
deviation, µj and σj ). For the Bernoulli case, µ0j = µj determines the respective probabilities of the
realization corresponding to the lower or upper bound (and the unneeded σj0 is ignored).
For each workload of 1000 VMs generated in this manner, we solve the online version of the
(SMBP) problem by implementing the Best-Fit heuristic, using one of the three different variants
for the values of D(α) and bj . We solve the problem for various values of α ranging from 0.5 to
0.99999. More precisely, when a new job arrives, we compute the modified capacity constraint
in equation (5) for each already-purchased machine, and assign the job to the machine with the
smallest available capacity that can accommodate it9 . If the job does not fit in any of the already
purchased machines, the algorithm opens a new machine. We consider the three variations of the
(SMBP) discussed earlier:
• The Gaussian case introduced in (2), with bj = σj2 and D(α) = Φ−1 (α). This is now also

an approximation to the chance constrained (BPCC) formulation since the true distributions are
truncated Gaussian or Bernoulli.
• The Hoeffding’s inequality approximation introduced in (3), with bj = (Aj − Aj )2 and D(α) =

p

−0.5 ln(1 − α). Note hat the distributionally robust approach with the family of distributions D2

is equivalent to this formulation.
• The distributionally robust approximation with the family of distributions D1 , with bj = σj2
p
and D1 (α) = α/(1 − α).
9


P
Note that we clip the value of the constraint at the effective upper bound
j xij Aj , to ensure that no trivially
feasible assignments are excluded. Otherwise, the Hoeffding’s inequality-based constraint may perform slightly worse
relative to the policy without over-commitment, if it leaves too much free space on the machines.

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

7.2.

29

Linear benchmarks

We also implement the following four benchmarks which consist of solving the classical (DBP)
problem with specific problem data. First we have:
• No overcommitment – This is equivalent to setting α = 1 in the (SMBP) problem, or solving

the (DBP) problem with sizes Aj .
Three other heuristics are obtained by replacing the square-root term in constraint (5) by a linear
term, specifically we replace the constraint with:
N
X

µj xij + D(α)

j=1

N
X
p
j=1

bj xij =

N 
X

p 
µj + D(α) bj xij ≤ V yi

(9)

j=1

to obtain:
• The linear Gaussian heuristic that mimics the Gaussian approximation in (2).
• The linear Hoeffding’s heuristic that mimics the Hoeffding’s approximation in (3).
• The linear robust heuristic that mimics the distributionally robust approach with the family

of distributions D1 .
Notice that the linearized constraint (9) is clearly more restrictive for a fixed value of α by concavity
of the square root, but we do of course vary the value of α in our experiments. We do not expect
these benchmarks to outperform our proposed method since they do not capture the risk-pooling
effect from scheduling jobs concurrently on the same machine. They do however still reflect different
relative amounts of ”padding” or ”buffer” above the expected utilization of each job allocated due
to the usage uncertainty.
The motivation behind the linear benchmarks lies in the fact that the problem is reduced to the
standard (DBP) formulation which admits efficient implementations for the classical heuristics.
For example, the Best-Fit algorithm can run in time O(N log N ) by maintaining a list of open
machines sorted by the slack left free on each machine (see Johnson (1974) for details and linear time approximations). In contrast, our implementation of the Best-Fit heuristic with the non-linear
constraint (5) takes time O(N 2 ) since we evaluate the constraint for each machine when each new
job arrives. Practically, in cloud VM scheduling systems, this quadratic-time approach may be
preferred anyway since it generalizes straightforwardly to more complex “scoring” functions that
also take into account additional factors besides the remaining capacity on a machine, such as
multiple resource dimensions, performance concerns or correlation between jobs (see, for example,
Verma et al. (2015)). In addition, the computational cost could be mitigated by dividing the data
center into smaller “shards”, each consisting of a fraction of the machines, and then trying to assign
each incoming job only to the machines in one of the shard. For example, in our experiments we
found that there was little performance advantage in considering sets of more than 1000 jobs at

30

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

a time. Nevertheless, our results show that even these linear benchmarks may provide substantial
savings (relative to the no-overcommitment policy) while only requiring very minor changes to
classical algorithms: instead of Aj , we simply use job sizes defined by µj , bj and α.
7.3.

Results and comparisons

We compare the seven different methods in terms of the number of purchased machines and show
that, in most cases, our approach significantly reduces the number of machines needed.
We consider two physical machine sizes: 32 cores and 72 cores. As expected, the larger machines
achieve a greater benefit from modeling risk-pooling. We draw 50 independent workloads each
composed of 1000 VMs as described above. For each workload, we schedule the jobs using the BestFit algorithm and report the average number of machines needed across the 50 workloads. Finally,
we compute the probability of capacity violation as follows: for each machine used to schedule each
of the workloads, we draw 5000 utilization realizations (either from a sum of truncated Gaussian
or a sum of Bernoulli distributions), and we count the number of realizations where the total CPU
usage of the jobs scheduled on a machine exceeds capacity.
The sample size was chosen so that our results reflect an effect that is measurable in a typical
data center. Since our workloads require on the order of 100 machines each, this corresponds to
roughly 50 × 100 × 5000 = 25, 000, 000 individual machine-level samples. Seen another way, we
schedule 50 × 1000 = 50, 000 jobs and collect 5000 data points from each. Assuming a sample is
recorded every 10 minutes, say, this corresponds to a few days of traffic even in a small real data
center with less than 1000 machines10 . The sample turns out to yield very stable measurements,
and defining appropriate service level indicators is application-dependent and beyond the scope of
this paper, so we do not report confidence intervals or otherwise delve into statistical measurement
issues. Similarly, capacity planning for smaller data centers may need to adjust measures of demand
uncertainty to account for the different scheduling algorithms, but any conclusions are likely specific
to the workload and data center, so we do not report on the variability across workloads.
In Figure 4, we plot the average number of machines needed as a function of the probability
that a given constraint is violated, in the case where the data center is composed of 72 CPU core
machines. Each point in the curves corresponds to a different value of the parameter α. Without
overcommitment, we need an average of over 54 machines in order to serve all the jobs. By allowing
10

The exact time needed to collect a comparable data set from a production system depends on the data center size
and on the sampling rate, which should be a function of how quickly jobs enter and leave the system, and of how
volatile their usages are. By sampling independently in our simulations, we are assuming that the measurements from
each machine are collected relatively infrequently (to limit correlation between successive measurements), and that
the workloads are diverse (to limit correlation between measurements from different machines). This assumption is
increasingly realistic as the size of the data center and the length of time covered increase: in the limit, for a fixed
sample size, we would record at most one measurement from each job with a finite lifetime, and it would only be
correlated with a small fraction of its peers.

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

31

a small chance of violation, say a 0.1% risk (or equivalently, a 99.9% satisfaction probability), we
only need 52 machines for the Bernoulli usage, and 48 machines for the truncated Gaussian usage.
If we allow a 1% chance of violation, we then only need 50 and 46 machines, respectively. The
table of Figure 6 summarizes the relative savings, which are roughly 4.5% and 11.5% with a 0.1%
risk, and roughly 8% and 14% with a 1% risk, for the Bernoulli and truncated Gaussian usages,
respectively. In terms of the overcommitment factor defined in Section 2.3, the reported savings
translate directly to the fraction of the final capacity that is due to overcommitment,
B(1) − B(α) OCF (α) − OCF (1)
=
.
B(1)
OCF (α)
Figure 4 shows that all three variations of our approach (the Gaussian, Hoeffding’s, and the
distributionally robust approximations) yield very similar results. This suggests that the results
are robust to the method and the parameters. The same is true for the corresponding linear
benchmarks, though they perform worse, as expected. We remark that although the final performance tradeoff is nearly identical, for a particular value of the α parameter, the achieved violation
probabilities vary greatly. For example, with α = 0.9 and the truncated normal distribution, each
constraint was satisfied with probability 0.913 when using the Gaussian approximation, but with
much higher probabilities 0.9972 and 0.9998 for the Hoeffding and robust approximations, respectively. This is expected, since the latter two are relatively loose upper bounds for a truncated
normal distribution, whereas the distributions N (µj , σj ) are close approximations to the truncated
Gaussian with parameters µ0j and σj0 . (This is especially true for their respective sums.) Practically,
the normal approximation is likely to be the easiest to calibrate and understand in cases where the
theoretical guarantees of the other two approaches are not needed, since it would be nearly exact
for normally-distributed usages.
In Figure 5, we repeat the same tests for smaller machines having only 32 physical CPU cores. The
smaller machines are more difficult to overcommit since there is a smaller risk-pooling opportunity,
as can be seen by comparing the columns of Table 6. The three variations of our approach still
yield similar and significant savings, but now they substantially outperform the linear benchmarks:
the cost reduction is at least double with all but the largest values of α. We highlight that with
the “better behaved” truncated Gaussian usage, we still obtain a 5% cost savings at 0.01% risk,
whereas the linear benchmarks barely improve over the no-overcommit case.
As mentioned in Section 2.2, the value of α should be calibrated so as to yield an acceptable
risk level given the data center, the workload and the resource in question. Any data center has
a baseline risk due to machine (or power) failure, say, and a temporary CPU shortage is usually
much less severe relative to such a failure. On the other hand, causing a VM to crash because of a
memory shortage can be as bad as a machine failure from the customer’s point of view. Ultimately,

32

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

(a) Bernoulli usage
Figure 4

(b) Truncated Gaussian usage

Average number of 72-core machines needed to schedule a workload, versus the probability that any
given machine’s realized load exceeds capacity

(a) Bernoulli usage
Figure 5

(b) Truncated Gaussian usage
Results for 32 core machines

the risk tolerance will be driven by technological factors, such as the ability to migrate VMs or
swap memory while maintaining an acceptable performance.
7.4.

Impact

We conclude that our approach allows a substantial cost reduction for realistic workloads. More
precisely, we draw the following four conclusions.
• Easy to implement: Our approach is nearly as simple to implement as classical bin packing

heuristics. In addition, it works naturally online and in real-time, and can be easily incorporated
to existing scheduling algorithms.

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

Figure 6

33

Percentage savings due to overcommitment for two CPU usage distributions, using the three

proposed variants of the chance constraint. The linear Gaussian benchmark is shown for comparison

• Robustness: The three variations we proposed yield very similar results. This suggests that

our approach is robust to the type of approximation. In particular, the uncertain term bj and the
risk coefficient D(α) do not have a strong impact on the results. It also suggests that the method
is robust to estimation errors in the measures of variability that define bj .
• Significant cost reduction: With modern 72-core machines, our approach allows a 8-14%

cost savings relative to the no overcommitment policy. This is achieved by considering a manageable
risk level of 1%, which is comparable to other sources of risk that are not controllable (e.g., physical
failures and regular maintenance operations).
• Outperforming the benchmarks: Our proposals show a consistent marked improvement

over three different “linear” benchmarks that reduce to directly apply the classical Best-Fit heuristic. The difference is most substantial in cases where the machines are small relative to the jobs
they must contain, which is intuitively more challenging. Although our approach does not run in
O(n log n) time, ”sharding” and (potentially) parallelization mitigate any such concerns in practice.

8.

Conclusion

In this paper, we formulated and practically solved the bin-packing problem with overcommitment. In particular, we focused on a cloud computing provider that is willing to overcommit when
allocating capacity to virtual machines in a data center. We modeled the problem as bin packing
with chance constraints, where the objective is to minimize the number of purchased machines,
while satisfying the physical capacity constraints of each machine with a very high probability.
We first showed that this problem is closely related to an alternative formulation that we call the
SMBP (Submodular Bin Packing) problem. Specifically, the two problems are equivalent under
the assumption of independent Gaussian job sizes, or when the job size distribution belongs to the
distributionally robust family with a given mean and (diagonal) covariance matrix. In addition, the

34

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

bin packing problem with chance constraints can be approximated by the SMBP for distributions
with bounded supports.
We first showed that for the bin packing problem with general monotone submodular capacity
constraints, it is impossible to find a solution within any reasonable factor from optimal. We then
developed simple algorithms that achieve solutions within constant factors from optimal for the
SMBP problem. We showed that any lazy algorithm is 8/3 competitive, and that the First-Fit
heuristic is 9/4 competitive. Since the First-Fit and Best-Fit algorithms are easy to implement and
well understood in practice, this provides an attractive option from an implementation perspective.
Second, we proposed an algorithm for the offline version of the problem, and showed that it
guarantees a 2-approximation. Then, we used our model and algorithms in order to draw several
useful insights on how to schedule jobs to machines, and on the right way to overcommit. We
convey that our method captures the risk pooling effect, as the “safety buffer” needed for each job
decreases with the number of jobs already assigned to the same machine. Moreover, our approach
translates to a transparent and meaningful recipe on how to assign jobs to machines by naturally
clustering similar jobs in terms of statistical information. Namely, jobs with a similar ratio b/µ
(the uncertain term divided by the expectation) should be assigned to the same machine.
Finally, we demonstrated the benefit of overcommitting and applied our approach to realistic
workload data inspired by Google Compute Engine. We showed that our methods are (i) easy to
implement; (ii) robust to the parameters; and (iii) significantly reduce the cost (1.5-17% depending
on the setting and the size of the physical machines in the data center).

Acknowledgments
We would like to thank the Google Cloud Analytics team for helpful discussions and feedback. The first
author would like to thank Google Research as this work would not have been possible without a one year
postdoc at Google NYC during the year 2015-2016. The authors would also like to thank Lennart Baardman,
Arthur Flajolet and Balasubramanian Sivan for their valuable feedback that has helped us improve the
paper.

References
Abdelaziz FB, Aouni B, El Fayedh R (2007) Multi-objective stochastic programming for portfolio selection.
European Journal of Operational Research 177(3):1811–1823.
Alan Roytman SGJLSN Aman Kansal (2013) Algorithm design for performance aware vm consolidation. Technical report, URL https://www.microsoft.com/en-us/research/publication/
algorithm-design-for-performance-aware-vm-consolidation/.
Albers S, Souza A (2011) Combinatorial algorithms lecture notes: Bin packing. URL https://www2.
informatik.hu-berlin.de/alcox/lehre/lvws1011/coalg/bin_packing.pdf.

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

35

Anily S, Bramel J, Simchi-Levi D (1994) Worst-case analysis of heuristics for the bin packing problem with
general cost structures. Operations research 42(2):287–298.
Bays C (1977) A comparison of next-fit, first-fit, and best-fit. Communications of the ACM 20(3):191–192.
Bertsimas D, Popescu I (2005) Optimal inequalities in probability theory: A convex optimization approach.
SIAM Journal on Optimization 15(3):780–804.
Calafiore GC, El Ghaoui L (2006) On distributionally robust chance-constrained linear programs. Journal
of Optimization Theory and Applications 130(1):1–22.
Charnes A, Cooper WW (1963) Deterministic equivalents for optimizing and satisfying under chance constraints. Operations research 11(1):18–39.
Coffman EG, So K, Hofri M, Yao A (1980) A stochastic model of bin-packing. Information and Control
44(2):105–115.
Coffman Jr EG, Garey MR, Johnson DS (1996) Approximation algorithms for bin packing: a survey. Approximation algorithms for NP-hard problems, 46–93 (PWS Publishing Co.).
Csirik J, Johnson DS, Kenyon C, Orlin JB, Shor PW, Weber RR (2006) On the sum-of-squares algorithm
for bin packing. Journal of the ACM (JACM) 53(1):1–65.
de La Vega WF, Lueker GS (1981) Bin packing can be solved within 1+ ε in linear time. Combinatorica
1(4):349–355.
Delage E, Ye Y (2010) Distributionally robust optimization under moment uncertainty with application to
data-driven problems. Operations research 58(3):595–612.
Delorme M, Iori M, Martello S (2016) Bin packing and cutting stock problems: Mathematical models and
exact algorithms. European Journal of Operational Research 255(1):1 – 20, ISSN 0377-2217, URL
http://dx.doi.org/http://dx.doi.org/10.1016/j.ejor.2016.04.030.
Dinh HT, Lee C, Niyato D, Wang P (2013) A survey of mobile cloud computing: architecture, applications,
and approaches. Wireless communications and mobile computing 13(18):1587–1611.
Dósa G (2007) The tight bound of first fit decreasing bin-packing algorithm is f f d ≤ 11/9opt + 6/9. Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, 1–11 (Springer).
Dósa G, Sgall J (2013) First fit bin packing: A tight analysis. LIPIcs-Leibniz International Proceedings in
Informatics, volume 20 (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik).
Fox A, Griffith R, Joseph A, Katz R, Konwinski A, Lee G, Patterson D, Rabkin A, Stoica I (2009) Above the
clouds: A berkeley view of cloud computing. Dept. Electrical Eng. and Comput. Sciences, University
of California, Berkeley, Rep. UCB/EECS 28(13):2009.
Ghaoui LE, Oks M, Oustry F (2003) Worst-case value-at-risk and robust portfolio optimization: A conic
programming approach. Operations Research 51(4):543–556.

36

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Operations
research 9(6):849–859.
Goemans MX, Harvey NJ, Iwata S, Mirrokni V (2009) Approximating submodular functions everywhere.
Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 535–544 (Society
for Industrial and Applied Mathematics).
Gupta V, Radovanovic A (2012) Online stochastic bin packing. arXiv preprint arXiv:1211.2687 .
Johnson DS (1974) Fast algorithms for bin packing. Journal of Computer and System Sciences 8(3):272 – 314,
ISSN 0022-0000, URL http://dx.doi.org/http://dx.doi.org/10.1016/S0022-0000(74)80026-7.
Karaesmen I, Van Ryzin G (2004) Overbooking with substitutable inventory classes. Operations Research
52(1):83–104.
Keller G, Tighe M, Lutfiyya H, Bauer M (2012) An analysis of first fit heuristics for the virtual machine
relocation problem. Network and service management (cnsm), 2012 8th international conference and
2012 workshop on systems virtualiztion management (svm), 406–413 (IEEE).
Kenyon C, et al. (1996) Best-fit bin-packing with random order. SODA, volume 96, 359–364.
Lueker GS (1983) Bin packing with items uniformly distributed over intervals [a, b]. Foundations of Computer
Science, 1983., 24th Annual Symposium on, 289–297 (IEEE).
Nemirovski A, Shapiro A (2006) Convex approximations of chance constrained programs. SIAM Journal on
Optimization 17(4):969–996.
Pisinger D, Sigurd M (2005) The two-dimensional bin packing problem with variable bin sizes and costs.
Discrete Optimization 2(2):154–167.
Rina Panigrahy KTUWRR Vijayan Prabhakaran (2011) Validating heuristics for virtual machines
consolidation. Technical report, URL https://www.microsoft.com/en-us/research/publication/
validating-heuristics-for-virtual-machines-consolidation/.
Rothstein M (1971) An airline overbooking model. Transportation Science 5(2):180–192.
Rothstein M (1985) Or forum – or and the airline overbooking problem. Operations Research 33(2):237–248.
Sindelar M, Sitaraman R, Shenoy P (2011) Sharing-aware algorithms for virtual machine colocation. Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures, 367–378 (New
York, NY, USA).
Stolyar AL, Zhong Y (2015) Asymptotic optimality of a greedy randomized algorithm in a large-scale service
system with general packing constraints. Queueing Systems 79(2):117–143.
Subramanian J, Stidham Jr S, Lautenbacher CJ (1999) Airline yield management with overbooking, cancellations, and no-shows. Transportation Science 33(2):147–167.
Svitkina Z, Fleischer L (2011) Submodular approximation: Sampling-based algorithms and lower bounds.
SIAM Journal on Computing 40(6):1715–1737.

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

37

Verma A, Pedrosa L, Korupolu MR, Oppenheimer D, Tune E, Wilkes J (2015) Large-scale cluster management at Google with Borg. Proceedings of the European Conference on Computer Systems (EuroSys)
(Bordeaux, France).
Weatherford LR, Bodily SE (1992) A taxonomy and research overview of perishable-asset revenue management: yield management, overbooking, and pricing. Operations Research 40(5):831–844.

38

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

Appendix A:

Details for Section 2.5

IP formulation
By taking the square on both sides of the submodular capacity constraint (5), we obtain:
V 2 yi +

N
X

µj xij

2

− 2V yi

j =1

N
X

µj xij ≥ D(α)2 ·

j =1

N
X

bj xij .

j =1

Note that since yi is binary, we have yi2 = yi . We next look at the term: yi

PN

j =1

µj xij . One can linearize this

term by using one of the following two methods.
1. Since yi = 1 if and only if at least one xij = 1, we have the constraint:

PN

j =1

xij ≤ M yi , for a large

positive number M (actually, one can take M = N ). Consequently, one can remove the yi in the above term.
2. One can define a new variable tij , yi xij and add the four following constraints:

Next, we look at the term:

tij ≤ yi ; tij ≤ xij ; tij ≥ 0; tij ≥ xij + yi − 1.
2
N
µ
x
. Since x2ij = xij , we remain only with the terms xij · xik for k > j.
j
ij
j =1

P

One can now define a new variable for each such term, i.e., zijk , xij · xik with the four constraints as before:
zijk ≤ xij ; zijk ≤ xik ; zijk ≥ 0; zijk ≥ xij + xik − 1.
The resulting formulation is a linear integer program. Note that the decision variables tij and zijk are
continuous, and only xij and yi are binary.

Appendix B:
Proof.

Proof of Theorem 1

In this proof, we make use of the submodular functions defined by Svitkina and Fleischer (2011)

for load balancing problems. Denote the jobs by 1, 2, · · · , N , and for every subset of jobs S ⊆ [N ], let f (S) be
the cost of the set S (i.e., the capacity cost induced by the function f ). We use two submodular functions f
and f 0 (defined formally next) which are proved to be indistinguishable with a polynomial number of value
oracle queries (see Lemma 5.1 of Svitkina and Fleischer (2011)). Let denote x = ln(N ). Note that Svitkina
and Fleischer (2011) require x to be any parameter such that x2 dominates ln(N ) asymptotically and hence,
√

5 N
x

, α0 =

N
m0

2

, and β0 = x5 . We choose N such
P
that m0 takes an integer value. Define f (S) to be min{|S|, α0 }, and f 0 (S) to be min{ i min{β0 , |S ∩ Vi |}, α0 }

includes the special case we are considering here. Define m0 =

0
where {Vi }m
i=1 is a random partitioning of [N ] into m0 equal sized parts. Note that by definition, both set

functions f and f 0 are monotone and submodular.
As we mentioned, it is proved in Svitkina and Fleischer (2011) that the submodular functions f and
0

f cannot be distinguished from each other with a polynomial number of value oracle queries with high
probability. We construct two instances of the bin packing problem with monotone submodular capacity
constraints by using f and f 0 as follows. In both instances, the capacity of each machine is set to β0 .
In the first instance, a set S is feasible (i.e., we can schedule all its jobs in a machine) if and only if
f (S) ≤ β0 . By definition, f (S) is greater than β0 if |S| is greater than β0 . Therefore, any feasible set S in
this first instance consists of at most β0 jobs. Consequently, in the first instance, any feasible assignment of
jobs to machines requires at least

N
β0

machines.

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

39

We define the second instance of the bin packing problem based on the submodular function f 0 . A set S
is feasible in the second instance, if and only if f 0 (S) ≤ β0 . Since f 0 (Vj ) is at most β0 for each 1 ≤ j ≤ m0 ,
each set Vj is a feasible set in this second instance. Therefore, we can assign each Vj to a separate machine
to process all jobs, and consequently, m0 machines suffice to do all the tasks in the second instance. We note
that with our parameter setting, m0 is much smaller that

N
β0

. We then conclude that the optimum solutions

of these two instances differ significantly.
We next prove the claim of Theorem 1 by using a contradiction argument. Assume that there exists a
polynomial time algorithm ALG for the bin packing problem with monotone submodular capacity constraints
√

with an approximation factor better than

N

ln(N )

. We next prove that by using ALG, we can distinguish

0

between the two set functions f and f with a polynomial number of value oracles, which contradicts the
result of Svitkina and Fleischer (2011). The task of distinguishing between the two functions f and f 0 can
be formalized as follows. We have value oracle access to a set function g, and we know that g is either the
same as f or the same as f 0 . The goal is to find out whether g = f or g = f 0 using a polynomial number of
value oracle queries. We construct a bin packing instance with N jobs, capacity constraints g, and ask the
algorithm ALG to solve this instance. If ALG uses less than

N
β0

machines to process all jobs, we can say

that g is the same as f 0 (since with capacity constraints f , there does not exist a feasible assignment of all
jobs to less than

N
β0

machines). On the other hand, if ALG uses at least

N
β0

machines, we can say that g is

0

equal to f . This follows from the fact that if g was equal to f , the optimum number of machines would have
√

been at most m0 . Since ALG has an approximation factor better than
√

by ALG should have been less than m0 ×

N
ln(N )

=

√
5 N
x

√

×

N
ln(N )

=

N
β0

N

ln(N )

, the number of machines used

. Therefore, using at least

N
β0

machines

by ALG is a sufficient indicator of g being the same as f . This argument implies that an algorithm with an
√

approximation factor better than

N

ln(N )

for the bin packing problem with monotone submodular constraints

yields a way of distinguishing between f and f 0 with a polynomial number of value oracle queries (since
ALG is a polynomial time algorithm), which contradicts the result of Svitkina and Fleischer (2011). 

Appendix C:

Details related to Observation 1

For ease of exposition, we first address the case with two job classes. Classes 1 and 2 have parameters (µ1 , b1 )
and (µ2 , b2 ) respectively. For example, an interesting special case is when one class of jobs is more predictable
relative to the other (i.e., µ1 = µ2 = µ, b2 = b and b1 = 0). In practice, very often, one class of jobs has low
variability (i.e., close to deterministic), whereas the other class is more volatile. For example, class 1 can
represent loyal recurring customers, whereas class 2 corresponds to new customers.
We assume that we need to decide the number of machines to purchase, as well as how many jobs of types
1 and 2 to assign to each machine. Our goal is to find the right mix of jobs of classes 1 and 2 to assign to
each machine (note that this proportion can be different for each machine). Consider a given machine i and
denote by n1 and n2 the number of jobs of classes 1 and 2 that we assign to this machine. We would like to
ensure that the chance constraint is satisfied in each machine with the given parameter α. Assuming that
V > n1 µ1 + n2 µ2 , we obtain:
[V − n1 µ1 − n2 µ2 ]2
= D(α)2 .
n 1 b1 + n 2 b2

(10)

40

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

For a given α, one can find the value of n1 as a function of n2 that satisfies equation (10):
q

V − n2 µ2
1 
n1 (n2 ) =
+ 2 b1 D(α)2 − b21 D(α)4 + 4b1 D(α)2 (V − n2 µ2 )µ1 + 4µ21 n2 b2 D(α)2 .
µ1
2µ1

(11)

As we discussed, an interesting special case is when both classes of jobs have the same expectation, i.e.,
µ1 = µ2 = µ but one type of jobs is much more predictable (i.e., smaller range or variance). In the extreme
case, one can assume that class 1 jobs are deterministic, (i.e., b1 = 0). In this case, equation (11) becomes:
√
V − n2 µ
2n2 b2 B
n1 (n2 ) =
−
.
(12)
µ
2µ
Alternatively, by directly looking at the modified capacity constraint (5) for this special case, we obtain:
p
V = (n1 + n2 )µ + D(α) n2 b2 .

(13)

Equation (13) can be interpreted as follows. Any additional job of type 1 takes µ from the capacity budget
V , whereas any additional job of type 2 is more costly. The extra cost depends on both the uncertainty of
the job (through b2 ) and the overcommitment policy (through D(α)). The higher is one of these two factors,
the larger is the capacity we should plan for jobs of type 2 (i.e., “safety buffer”). Note that the submodular
nature of constraint (5) implies that this marginal extra cost decreases with the number of jobs n2 . In other
words, when n2 becomes large, each additional job of type 2 will converge to take a capacity of µ, as the
central limit theorem applies. More generally, by taking the derivative of the above expression, any additional
√ √
job of type 2 will take µ + 0.5D(α) b2 / n2 (where n2 here represents how many jobs of type 2 are already
assigned to this machine).
In Figure 7, we plot equation (12) for a specific instance with V = 30 and different values of α. As expected,
if n2 = 0, we can schedule n1 = 50 jobs of class 1 to reach exactly the capacity V , no matter what is the
value of α. On the other hand, for α = 0.99, if n1 = 0, we can schedule n2 = 38 jobs of class 2. As the value
of n2 increases, the optimal value of n1 decreases. For a given value of α, any point (n1 , n2 ) on the curve
(or below) guarantees the feasibility of the chance constraint. The interesting insight is to characterize the
proportion of jobs of classes 1 and 2 per machine. For example, if we want to impose n1 = n2 in each machine,
what is the optimal value for a given α? In our example, when α = 0.99, we can schedule n1 = n2 = 21 jobs.
If we compare to the case without overcommitment (i.e., α = 1), we can schedule 18 jobs from each class.
Therefore, we obtain an improvement of 16.67%. More generally, if the cost (or priority) of certain jobs is
higher, we can design an optimal ratio per machine so that it still guarantees to satisfy the chance constraint.
To summarize, for the case when V = 30, µ = 0.65, A = 1, A = 0.3 and α = 0.99, one can schedule either 50
jobs of class 1 or 38 jobs of class 2 or any combination of both classes according to equation (12). In other
words, we have many different ways of bin packing jobs of classes 1 and 2 to each machine.
We next consider solving the offline problem when our goal is to schedule N1 jobs of class 1 and N2 jobs of
class 2. The numbers N1 and N2 are given as an input, and our goal is to minimize the number of machines
denoted by M ∗ , such that each machine is assigned a pair (n1 , n2 ) that satisfies equation (11). Since n1 and
n2 should be integer numbers, one can compute for a given value of α, all the feasible pairs that lie on the
curve or just below (we have at most K = mini=1,2 max ni such pairs). In other words, for each k = 1, 2, . . . , K,

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

Figure 7

41

Parameters: A = 1, A = 0.3, µ = 0.65, V = 30.

we compute a pair of coefficients denoted by (βk , γk ). The optimization problem becomes a cutting stock
problem:
M ∗ = min
zk

s.t.

K
X

zk

k=1
K
X

βk zk ≥ N1

(14)

k=1
K

X

γ k z k ≥ N2

k=1

zk ≥ 0, integer

∀k.

The decision variable zk represents the number of times we use the pair (βk , γk ), and M ∗ denotes the optimal
number of machines. As a result, assuming that we have only two classes of jobs (with different µs and bs),
one can solve the deterministic linear integer program in (14) and obtain a solution for problem (SMBP).
Note that the above treatment can easily be extended to more than two classes of jobs.

Appendix D:
Proof.

Proof of Theorem 4

Let n1 be the number of machines purchased by First-Fit with only a single job, and S1 be the

set of n1 jobs assigned to these machines. Similarly, we define n2 to be the number of machines with at least
two jobs, and S2 be the set of their jobs. The goal is to prove that n1 + n2 ≤ 49 OP T + 1. We know that
any pair of jobs among the n1 jobs in S1 does not fit in a single machine (by the definition of First-Fit).
Therefore, any feasible allocation (including the optimal allocation) needs at least n1 machines. In other
words, we have OP T ≥ n1 . This observation also implies that the sum of µj + bj for any pair of jobs in S1 is
greater than

3
4

(using Lemma 1). If we sum up all these inequalities for the different pairs of jobs in S1 , we

P
have: (n1 − 1) j∈S1 (µj + bj ) > n21 43 . We note that the n1 − 1 term on the left side appears because every job

j ∈ S1 is paired with n1 − 1 other jobs in S1 , and the n21 term on the right side represents the total number
P
of pairs of jobs in S1 . By dividing both sides of this inequality by n1 − 1, we obtain j∈S1 (µj + bj ) > 3n8 1 .
P
We also lower bound
j∈S2 (µj + bj ) as a function of n2 as follows. Let m1 < m2 < · · · < mn2 be the
machines that have at least two jobs, and the ordering shows in which order they were purchased (e.g.,

42

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

m1 was purchased first). Define Mi to be the set of jobs in machine mi . By definition of First-Fit, any
job j in machine mi+1 could not be assigned to machine mi because of the feasibility constraints for any
1 ≤ i < n2 . In other words, the set of jobs Mi with any job j ∈ Mi+1 form an infeasible set. Therefore, we
P
have µj + bj + j 0 ∈Mi (µj 0 + bj 0 ) > 43 . For each 1 ≤ i < n2 , one can pick two distinct jobs j1 and j2 from Mi+1 ,
and write the following two inequalities:
X

µj1 + bj1 +

(µj 0 + bj 0 ) >

j 0 ∈Mi

3
4

and

µj2 + bj2 +

X
j 0 ∈Mi

Summing up these two inequalities implies that: µj1 + bj1 + µj2 + bj2 + 2

3
(µj 0 + bj 0 ) > .
4

P

j 0 ∈Mi

(µj 0 + bj 0 ) > 32 . Since j1 and

j2 are two distinct jobs in Mi+1 , we have:
X

(µj + bj ) + 2

X
j 0 ∈Mi

j∈Mi+1

3
(µj 0 + bj 0 ) > .
2

Now we sum up this inequality for different values of i ∈ {1, 2, · · · , n2 − 1} to achieve that:
n2 −1

X

2

(µj + bj ) + 3

X X
i=2 j∈Mi

j∈M1

Pn2 P

X

(µj + bj ) +

(µj + bj ) >

j∈Mn2

3
× (n2 − 1),
2

3
2

P
× (n2 − 1). This is equivalent to j∈S2 (µj + bj ) >
P
1
× (n2 − 1). Combining both inequalities, we obtain: j∈S1 ∪S2 (µj + bj ) > 38 n1 + 12 (n2 − 1). On the other
2
P
hand, OP T is at least j∈S1 ∪S2 (µj + bj ). We then have the following two inequalities:
and consequently, we have 3

i=1

j∈Mi

(µj + bj ) >

OP T ≥ n1 ,
1
3
OP T > n1 + (n2 − 1).
8
2
We can now multiply (15) by

1
4

and (16) by 2, and sum them up. We conclude that

(15)
(16)
9
OP T
4

+ 1 is greater

than n1 + n2 , which is the number of machines purchased by Algorithm First-Fit. 

Appendix E:

Proof of Theorem 5

We first state the following
√ Lemma that provides a lower bound on OP T . For any a, b ≥ 0, we define the
2a+b+ b(4a+b)
.
function f (a, b) =
2
Lemma 2. For any feasible set of jobs S, the sum
P

µj

bj

j∈S

f (µj , bj ) is at most 1.

and b̄ = j∈S
. Since the function f is concave with respect to both a and
|S|
P
b, using Jensen’s inequality we have j∈S f (µj , bj ) ≤ |S|f (µ̄, b̄). Since S is a feasible set, Cost(S) = |S|µ̄ +
p
p
|S|b̄ ≤ 1. The latter is a quadratic inequality with variable x = |S|, so that we we can derive an upper
√
bound on |S| in terms of µ̄ and b̄. Solving the quadratic form µ̄X + b̄X = 1 yields:
p
√
− b̄ ± b̄ + 4µ̄
X=
.
2µ̄
√
√
p
4µ̄+b̄− b̄
4q
1
We then have |S| ≤
= q 2 √ . Therefore, |S| ≤
= f (µ̄,
, where the equality
2µ̄
b̄)
4µ̄+b̄+b̄+2 b̄(4µ̄+b̄)
(4µ̄+b̄)+ b̄
P
follows by the definition of the function f . Equivalently, |S|f (µ̄, b̄) ≤ 1, and hence j∈S f (µj , bj ) ≤ 1. 
Proof.

Define µ̄ =

j∈S

P

P

|S|

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

43

Proof of Theorem 5.

For any arbitrary allocation of jobs, applying Lemma 2 to all the machines implies
PN
that the number of machines is at least j =1 f (µj , bj ). So it suffices to upper bound the number of machines
PN
as a function of j =1 f (µj , bj ). For any given machine, we prove that the sum of f (µj , bj ) for all jobs j
assigned to this machine is at least 1 − O( + δ). Consider the set of jobs S assigned to a given machine.
P

Similar to the proof of Lemma 2, we define µ̄ =

j∈S

µj

|S|

P

and b̄ =

j∈S

|S|

bj

P

. Define r =

P j∈S
j∈S

bj
µj

= µ̄b̄ . We start by

lower bounding f (µj , bj ) as a function of f (µj , rµj ). Recall that each machine is δ-homogeneous, i.e., for all
pairs of jobs in the same machine, the ratios
other. Hence, any ratio

bj
µj

f (µj , bj ) ≥ f

r

is at least

(1+δ )

bj
µj

are at most a multiplicative factor of 1 + δ away from each

. Consequently, we have bj ≥

rµj

1+δ

which implies that:


µj
rµj 
1
µj
, bj ≥ f
,
=
f (µj , rµj ) ≥ (1 − δ)f (µj , rµj ).
1+δ
1+δ 1+δ
1+δ

The first and second inequalities follow from the monotonicity of the function f , the equality follows from
P
the definition of f , and the last inequality holds since δ ≥ 0. It now suffices to lower bound j∈S f (µj , rµj )
P
so as to obtain a lower bound for j∈S f (µj , bj ). We note that for any η ≥ 0, we have f (ηµ, ηb) = ηf (µ, b)
by the definition of f . Applying η = µj , µ = 1 and b = r, we obtain f (µj , rµj ) = µj f (1, r) which implies:
X
X
f (µj , rµj ) =
µj f (1, r) = f (A, B),
j∈S

where A =

P

A0 =

and B 0 =

µj , and B = r

P

µj =

j∈S

P

bj . The last equality above follows from f (ηµ, ηb) = ηf (µ, b)
√
with η = A. Recall that each machine is -full, i.e., Cost(S) ≥ 1 −  or equivalently, A + B ≥ 1 − . Let
A

(1−)2

j∈S

B

(1−)2

j∈S

j∈S

. Then, we have:
√
√
A
+
B
B
A
+
≥
≥ 1.
A + B0 =
(1 − )2 1 − 
1−
0

√

√
Since B = rA, we also have B 0 = rA0 , and the lower bound can be rewritten as follows: A0 + rA0 ≥ 1, which
is the same quadratic form as in the proof of Lemma 2. Similarly, we prove that A0 ≥
is equal to

1
.
f (1,r )

0

0

0

0

0

4
√
4+2r+2

r (4+r )

We also know that f (A , B ) = f (A , rA ) = A f (1, r). We already proved that A ≥

which
1
f (1,r )

,

so we have f (A0 , B 0 ) ≥ 1. By definition of A0 and B 0 , we know thatf (A, B) = (1 − )2 f (A0 , B 0 ) ≥ (1 − )2 .
P
We conclude that the sum j∈S f (µj , bj ) ≥ (1 − δ)f (A, B) ≥ (1 − δ)(1 − )2 . As a result, for each machine
the sum of f (µj , bj ) is at least (1 − δ)(1 − )2 . Let m be the number of purchased machines. Therefore, the
PN
sum j =1 f (µj , bj ) is lower bounded by (1 − δ)(1 − )2 m, and at the same time upper bounded by OP T .
Consequently, m does not exceed

Appendix F:
Proof.

OP T
(1−δ )(1−)2

and this concludes the proof. 

Proof of Theorem 6

We first prove that the algorithm terminates in a finite number of iterations. Note that all the

update operations (except the first one) reduce the number of purchased machines, and hence, there are
no more than N of those. As a result, it suffices to upper bound the number of times we perform the first
update operation. Since we assign jobs to lower id machines, there cannot be more than N 2 consecutive first
update operations. Consequently, after at most N × N 2 = N 3 operations, the algorithm has to terminate.
Next, we derive an upper bound on the number of purchased machines at the end of the algorithm. Note
that all the machines belong to one of the following four categories:
• Single job machines, i.e., the set A1 .

44

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

• Medium machines with only one non-good job – denoted by the set B.
• Medium machines with at least two non-good jobs – denoted by the set C.
• Large machines, i.e., the set A5 .
Let a, b, c, and d be the number of machines in A1 , B, C, and A5 respectively. Since no update operation is
possible (as the algorithm already terminated), the b non-good jobs assigned to the machines in the set B
do not fit in any of the single job machines, and no pair of them fit together in a new machine. Consider
these b non-good jobs in addition to the a jobs in the machines of the set A1 . No pair of these a + b jobs fit
in one machine together and therefore, OP T ≥ a + b.
PN
We also know that OP T ≥ j =1 (µj + bj ). Next, we derive a more elaborate lower bound on OP T by
writing the sum of µj + bj as a linear combination of the sizes of the sets A1 , B, C, and A5 . For each machine
i, let Mi be the set of jobs assigned to this machine. Let i1 < i2 < · · · < id be the indices of machines in the
set A5 , where d = |A5 |. Since we cannot perform the first update operation anymore, we can say that no
P
job in machine i`+1 fits in machine i` for any 1 ≤ ` < d. Therefore, µj + bj + j 0 ∈Mi (µj 0 + bj 0 ) > 34 for any
`

j ∈ Mi`+1 (using Lemma 1). We write this inequality for 5 different jobs (arbitrarily chosen) in Mi`+1 (recall
that there are at least 5 jobs in this machine), and for all the values of 1 ≤ ` < d. If we sum up all these
5(d − 1) inequalities, then the right hand side would be 5(d − 1) × 43 . On the other hand, the term µj + bj for
every job in these d machines appears on the left hand side at most 5 + 1 = 6 times. Therefore, by summing
P
P
1)
1)
= 5(d−
.
up these inequalities, we obtain: i∈A5 j∈Mi (µj + bj ) > 34 × 5(d−
6
8
Each machine in A5 has at least 5 jobs. Therefore, the term

5
6

appears in the lower bound. With a similar

argument, each machine in either B or C has at least 2 jobs and hence, this term is now replaced by 32 . The
P
P
1)
= b−2 1 , and
inequalities for every pair of machines in B and C are then: i∈B j∈Mi (µj + bj ) > 34 × 2(b−
3
P
P
2(c−1)
3
= c−2 1 .
i∈C
j∈Mi (µj + bj ) > 4 ×
3
P
P
Next, we lower bound i∈A1 ∪C j∈Mi (µj + bj ) as a function of a and c in order to complete the proof.
Recall that each machine in C has at least two non-good jobs. If we pick one of these non-good jobs j, and a
random machine i from A1 , with probability at least

a−5
a

, job j does not fit in machine i. This follows from

the fact that a non-good job fits in at most 5 machines in A1 and hence, a random machine in A1 would
P
not be be able to fit job j with probability at least a−a 5 . Therefore, µj + bj + j 0 ∈Mi (µj 0 + bj 0 ) ≥ 34 with
probability at least

a−5
a

. We next consider two different cases depending on the value of c.

If c is at least a2 , we pick a random machine in C, and two of its non-good jobs j1 and j2 arbitrarily. We
also pick a random machine in A1 . For each of these two jobs, the sum µj + bj of the non-good job and the
single job in the selected machine in A1 is greater than

3
4

with probability at least

a−5
a

. Summing up these

two inequalities, we obtain:
i 1hX X
i a−5 3
2h X X
(µj + bj ) +
(µj + bj ) >
× .
a i∈A j∈M
c i∈C j∈M
a
2
1

i

(17)

i

The left hand side of the above equation is composed of two terms. The first term is obtained through
picking a random machine in A1 (i.e., with probability a1 ), and once the machine is picked, we sum up both
equations so we obtain

2
a

. For the second term, every machine in the set C is chosen with probability

1
c

.

Cohen, Keller, Mirrokni and Zadimoghaddam: Overcommitment in Cloud Services - Bin packing with Chance Constraints

45

When the machine is picked, we sum up on all the jobs and hence get an upper bound. As we have shown,
P
P
(µj + bj ) ≥ c−2 1 . Combining these two inequalities leads to (using c ≥ a2 ):
i∈C
j∈Mi
X

X

(µj + bj ) >

i∈A1 ∪C j∈Mi

a
c − 1 3a 15 c a 1 a + c
a 3(a − 5)
×
+ (1 − ) ×
≥
−
+ − − =
− 4.25.
2
2a
2c
2
4
4
2 4 2
2

PN
By combining the three different bounds (on A1 ∪C, B and A5 ), we obtain j =1 (µj +bj ) ≥ a+2b+c + 58d −5.875.
PN
Since OP T ≥ j =1 (µj + bj ), we conclude that the number of purchased machines a + b + c + d is no more
than 2OP T + 11.
In the other case, we have c < a2 . Note that inequality (17) still holds. However, since the coefficient 1 − 2ac
becomes negative, we cannot combine the two inequalities as before. Instead, we lower bound the sum µj + bj
of jobs in A1 . We know that there is no pair of a jobs in the A1 machines that fit together in one machine.
P
P
Therefore, i∈A1 j∈Mi (µj + bj ) ≥ 38a . Next, we multiply inequality (17) by c, and combine it with this new
P
P
lower bound on i∈A1 j∈Mi (µj + bj ), to obtain (using c < a2 ):
X

X

i∈A1 ∪C j∈Mi

(µj + bj ) > c ×

3(a − 5)
2c
3a 3c 5 3a 3c 3a 3c 5
+ (1 − ) ×
>
− +
−
=
+
− .
2a
a
8
2
4
8
4
8
4
4

Combining this inequality with similar ones on the sets B and A5 , we obtain OP T ≥
3a
8

PN

j =1

(µj + bj ) >

+ 2b + 34c + 58d − 19
. Finally, combining this with OP T ≥ a + b leads to a + b + c + d ≤ 85 OP T + 52 OP T + 19
=
8
5

2OP T + 3.75, which concludes the proof. 

