Eugene Furman, Arik Senderovich, Shane Bergsma, J. Christopher Beck

Capacity Allocation for Clouds with Parallel Processing, Batch Arrivals, and
Heterogeneous Service Requirements

Capacity Allocation for Clouds with Parallel Processing, Batch Arrivals, and
Heterogeneous Service Requirements

Eugene Furman Operations and Decision Sciences, Alba Graduate Business School,
American College of Greece, Athens, Greece
<EMAIL_ADDRESS>Arik Senderovich School of Information Technology, York
University, Toronto, Ontario
<EMAIL_ADDRESS>Shane Bergsma Toronto Research Center, Huawei Cloud, Markham,
Ontario
<EMAIL_ADDRESS>J. Christopher Beck Department of Mechanical &
Industrial Engineering, University of Toronto, Toronto, Ontario
<EMAIL_ADDRESS>
Problem Definition: Allocating sufficient capacity to cloud services is a
challenging task, especially when demand is time-varying, heterogeneous,
contains batches, and requires multiple types of resources for processing. In
this setting, providers decide whether to reserve portions of their capacity
to individual job classes or to offer it in a flexible manner.
Methodology/results: In collaboration with Huawei Cloud, a worldwide provider
of cloud services, we propose a heuristic policy that allocates multiple types
of resources to jobs and also satisfies their pre-specified service level
agreements (SLAs). We model the system as a multi-class queueing network with
parallel processing and multiple types of resources, where arrivals (i.e.,
virtual machines and containers) follow time-varying patterns and require at
least one unit of each resource for processing. While virtual machines leave
if they are not served immediately, containers can join a queue. We introduce
a diffusion approximation of the offered load of such system and investigate
its fidelity as compared to the observed data. Then, we develop a heuristic
approach that leverages this approximation to determine capacity levels that
satisfy probabilistic SLAs in the system with fully flexible servers.
Managerial Implications: Using a data set of cloud computing requests over a
representative 8-day period from Huawei Cloud, we show that our heuristic
policy results in a 20% capacity reduction and better service quality as
compared to a benchmark that reserves resources. In addition, we show that the
system utilization induced by our policy is superior to the benchmark, i.e.,
it implies less idling of resources in most instances. Thus, our approach
enables cloud operators to both reduce costs and achieve better performance.

##  1 Introduction

Remote operational processes require large quantities of computing resources
such as Central Processing Units (CPUs), Random Access Memory (RAM), etc. By
2025, the amount of data generated worldwide is to exceed 200 zettabytes with
more than a half of it to be processed by cloud platforms (Enterprise IT
World, 2018; Gartner, 2019; Cloudwards, 2022).

Often, Virtual Machines (VMs), i.e., software-based remote computers within
another computer’s operating system, deliver remote applications and services
to end users (Cloudflare, n.d.; Cloudwards, 2022). Once hardware resources are
provisioned to a VM, its users are permitted to run applications in real time
as if they were stored on their local systems. Unfortunately, VMs require
expertise to set up and manage. Alternatively, containerized applications,
i.e., lightweight software packages with all the dependencies required for
their execution, have been gaining popularity as they may run directly on the
server (Atlassian, n.d.). Notice that although we model containers as running
directly on the server, cloud providers may execute containers inside special
lightweight “microVMs” in order to ensure security isolation (Verma et al.,
2015; Cortez et al., 2017).

In 2020, a Cloud Native Computing Foundation survey found that the use of
containers had grown 300% since 2016 (CNCF, 2020). Later, in 2021, the
International Data Corporation highlighted an ongoing operational shift of the
cloud computing industry to a paradigm where 80% of global cloud computing
needs will be met by containerized solutions (CIO, 2021). According to
Gartner, the usage of containers across enterprises is already on the rise as
90% of global organizations are to run containerized applications by 2026 (up
from 40% in 2021) (Gartner, 2021).

Unsurprisingly, to satisfy strict service-level agreements (SLAs), VMs and
containers require cloud computing infrastructure with near zero-latency
capabilities that has become an essential commodity for many corporations
(Bruckner and Tjoa, 2002). In particular, our partner organization, Huawei
Cloud, a provider of a wide range of cloud-computing services worldwide, would
like to complement their VM-based platforms with containerized solutions, such
that the underlying hardware resources can be dynamically shared without a
necessity to dedicate them to VMs or containers. However, effective deployment
of the fully flexible resources requires smart capacity allocation algorithms
that allow providers to adapt to the dynamically changing demand.

Motivated by the challenge of setting capacity levels in a time-varying
environment, we consider operations of Huawei Cloud which offers remote
computing functionality for internal company use and to external subscribers
on-demand. Any dynamic provisioning of capacity is linked to optimal
determination of quantities of CPU and RAM units required to satisfy
heterogeneous SLAs of VMs and multiple classes of containers to be running
jointly on a cloud platform.

We represent an aggregate capacity of the company’s cloud computing
infrastructure by the total number of homogeneous CPU cores, i.e., individual
processors within a CPU, and gigabytes of memory. Without loss of generality,
we assume that CPU cores are the most constraining resource with a higher cost
of shortages (i.e., dominant). Further, VMs and containers arrive
stochastically to the system; they simultaneously require multiple CPU cores
and units of memory with a random service duration associated with their size.
Typically, VMs are large infinitely impatient jobs, (i.e., they must begin
processing upon arrival to the system) and may spend up to several years in
service. In contrast, containers join a queue if needed, and their service
times rarely exceed 8 hours.

To capture the non-stationarity in demand, we assume jobs arrive according to
a compound non-homogeneous Poisson process, i.e., batch arrivals are allowed.
Resource requirements and service durations are generally distributed. Our
objective is to determine the minimum non-stationary capacity (i.e., quantity
of CPU cores and units of RAM) such that pre-specified service level
agreements are satisfied over a planning horizon. To the best of our
knowledge, exact analysis of the time-varying stochastic system with batches
and multiple resources is intractable, and thus, we develop a three-stage
procedure that sets the desired capacity levels heuristically. In the first
stage (the $\infty$ stage), we determine the probability distribution of the
system’s stochastic offered load (SOL) and propose a corresponding diffusion
model. In the second stage (the $\alpha$ stage), by collapsing all jobs into a
single fictitious class and by adapting a square-root-staffing rule, we set a
capacity level for the dominant resource. Finally, in the last stage (the
$\epsilon$ stage), we employ the square-root-staffing rule again to determine
quantities of non-dominant resources.

Using a data set of cloud computing requests for VMs over a representative
period of 8 days, provided to us by Huawei Cloud, we motivate our modelling
choices by showing that demand for VMs is time-varying and exhibits
periodicity throughout the course of a single week. We also confirm that batch
arrivals of requests for VMs can be modelled by a non-homogeneous Poisson
process reasonably well. Further, we conduct a simulation study to demonstrate
the practicality of our methodology. We first verify that the 80-percentile
interval of the generated stochastic paths of the SOL confines the CPU-core
workload in the infinite capacity system parameterised by the observed data.
Then, using a data-driven parameterization, we generate workload for a system
with 5 classes of jobs (i.e., VMs and four types of containers) with
heterogeneous service requirements. We apply our three-stage procedure to set
capacity levels in such system. In particular, we perform a set of near-
stationary and time-varying experiments that compare performance of our
heuristic policy with a benchmark, which emulates Huawei Cloud’s existing
operations by dedicating capacity to job classes (Ke et al., 2021). We find
that, in both regimes, the proposed heuristic outperforms the benchmark by
requiring at least 20% fewer resources while respecting pre-specified SLAs.
Thus, Huawei Cloud can potentially reduce their aggregate cloud computing
capacity while also improving quality of their service by sharing resources
instead of dedicating them to various types of workload.

We contribute to the operations research literature by extending previous work
on non-stationary staffing policies for queueing systems with parallel
processing, batch arrivals, and time-varying, periodic demand. Our approach of
combining a diffusion model with a state-of-the-art square-root-staffing rule
can be applied to many systems, where practitioners are able to determine
which resource is dominant; it can also accommodate a broad class of arrival
functions that are general enough to describe most periodic demand processes
in service settings. In addition, our methodology is computationally efficient
as it leverages closed-form expressions for the SOL. Thus, our service policy
can dynamically adapt to changes in demand and remains deployable in practice.

##  2 Motivation: Exploratory Data Analysis

Huawei Cloud delivers services to consumers around the world. Although each
service has a specific business focus, the typical demand is heterogeneous,
time-varying, and contains batches (i.e., jobs can be submitted for processing
at the same time). Our data set includes arrival times, service durations, and
capacity requirements of requests for virtual machines (VMs) over a period of
8 days for one such service. It accounts for 196,770 arrivals where the
service times range from approximately 10 milliseconds to 8 days. Each VM
requires at least 1 CPU core and 1 gigabyte of memory. In this section, we
explore this data set to motivate our modelling choices. Specifically, we
visualize the service requirements of jobs and demonstrate that jobs belonging
to the same batch have low variability in their service times. We also show
that the observed arrivals are time-varying and periodic with a period of 1
day. Further, we confirm that counts of job batches arriving over a weekday
satisfy the statistical non-homogeneous Poisson test as described in Brown et
al. (2005).

###  2.1 Descriptive Summary of Service Requirements

To summarize resource requirements of jobs in our data, we present their
distributions in Figure 1, where the x-axes describe counts of resources,
while the y-axes correspond to their frequencies in percentage. According to
Figure 1a–1b, 90% of VMs require less than 5 CPU cores for processing, while
approximately 70% of VMs require less than 5 gigabytes of memory. However,
less than 1% of jobs need as many as 200 CPU cores, and/or 3000 gigabytes of
RAM for their service.

Figure 1: Service Requirements: (a) CPU cores; and (b) RAM in Gigabytes.

(a)

(b)

Our data set is characterized by a large fraction of jobs with short service
durations. According to Figure 2a, almost 85% percent of VMs require less than
5 hours to get serviced, and only a few jobs occupy cloud computing capacity
for as long as 7 days. Further, our data set accounts for the total of 123,815
batches of jobs. We summarize variability in service times of jobs belonging
to the same batch in Figure 2b, which represents a frequency plot of their
standard deviations. According to this figure, these standard deviations do
not exceed 1 minute in nearly 90% of instances.

Figure 2: Summary: (a) Service Times; (b) Variability of Service Times amongst
Jobs in the Same Batch.

(a)

(b)

###  2.2 Understanding the Arrival Process

In Figure 3a, we express counts of arriving to the system VMs as a percentage
of the total demand recorded in the data set over the planning horizon (i.e.,
8 days or 192 hours). According to this figure, the typical intensity of
arrivals to the cloud computing servers follows a periodic quasiconcave
pattern on each day from Sunday to Sunday, i.e., it reaches a maximum in every
24-hour period. Further, the magnitude of the maxima is consistent from Monday
to Saturday with fewer VMs recorded on Sundays and a relatively taller spike
in demand observed on Tuesday. We also notice that the arrival count rarely
reduces below a base-level, i.e., approximately 0.3% of the total demand, and
it typically exceeds this quantity fourfold at the maxima over the week days.

Figure 3: Arrival Process: (a) Histogram of Arrival Times; (b) Non-homogeneous
Poisson Process Test.

(a)

(b)

We follow the procedure described in Brown et al. (2005) to test the null
hypothesis that batch arrivals to the cloud computing servers follow a Poisson
distribution with a piecewise constant rate. To this end, we break up the
planning horizon into non-overlapping time intervals (approximately 5 minutes)
and test the hypothesis of stationarity by applying the Kolmogorov-Smirnov
(KS) test and confirming that, for each time interval, the logarithmically
transformed arrival times can be modeled by independent standard exponential
random variables. In Figure 3b, we show that the 5-minute intervals over
individual days typically pass the test in 80% of instances. For example, the
logarithmically transformed arrival times in nearly 85% of 5-minute intervals
on Monday can be modeled by independent standard exponential random variables.

###  2.3 Modelling Implications and Choices

Our exploratory data analysis shows that distributions of service requirements
of individual jobs in our data set typically have a thin tail, i.e., a
majority of VMs request only a few CPU cores or units of RAM and remain in
service for less than 5 hours. Further, jobs arrive in small batches with an
average size of approximately 1.59. This reduces the effect of outliers on the
expected demand estimated from the data set. Because the standard deviation of
service durations within each batch tends to be smaller than 1 minute, we
believe that complex modelling solutions accounting for an arbitrary
variability in service times within a batch of jobs are not justified. To
avoid unnecessary complexity, we build our analysis under the assumption that
service times of jobs belonging to the same batch are identical. To deal with
few instances of batches that have larger variability in respective service
durations, we split them into several groups of jobs.

According to Figure 3a, arrivals to our system follow a time-varying and
periodic pattern (with a period of 1 day). We describe the distribution of
demand in Section 2.2. Because jobs arrive for processing in relatively
consistent quantities across weekdays, we choose a typical 24-hour period as a
planning horizon for our modelling approach. To this end, we assume that our
system has been in continuous operation for a long time, i.e., it is ergodic.
Finally, our implementation of the statistical test set in Brown et al. (2005)
demonstrates that batch arrivals to Huawei Cloud’s servers on a typical
weekday can be modelled by a non-homogeneous Poisson process reasonably well.
According to Figure 3b, the average test statistic exceeds 80%. Thus,
modelling demand by a compound non-homogeneous Poisson process is an
appropriate choice.

##  3 Literature Review and Contributions

Our paper introduces a stochastic model for a parallel processing system with
heterogeneous workload and multiple types of resources, one of which is
assumed to be dominant (i.e., most expensive or constraining). We modify this
notion of a dominant resource borrowed from the communications literature (see
Ghodsi et al., 2011; Zhang and Ansari, 2013; Wang et al., 2014; Li et al.,
2017, for instance), which links it to proportions of the total demand in a
system with multiple resources. In our system, jobs simultaneously occupy
multiple units of resources and release them at service completion. Similarly
to Green (1981), our queueing discipline complements the FIFO (first-in-first-
out) service policy with utilization maximization to avoid service starvation
(see Bramson (1994); Gurvich and Van Mieghem (2018); Zychlinski et al. (2020a)
for more details).

Pioneering work on queues with parallel processing is presented in Gimpelson
(1965); Wolman (1972). The former models a facility carrying two types of
calls that require multiple transmission channels, while the latter analyzes a
system where messages wait in parallel queues until they are transmitted to
all receivers. Seminal applications of queues with parallel processing are
discussed in Green (1978, 1980); Kaufman (1981). Further, Reiman (1991)
studies a multi-class loss system with parallel processing and derives its
blocking probabilities. Parallel processing systems with an infinite buffer
are considered in Bambos and Walrand (1993). Several researchers refer to
queues with parallel processing as simultaneous resource possession systems
(see Jacobson and Lazowska, 1982; Kaufman and Wang, 1989; Kaufman and Wong,
1990; Visschers et al., 1999, for instance). In general, deriving analytical
results for parallel processing queues is challenging (Papadimitriou and
Tsitsiklis, 1994). Thus, stochastic simulations (Feldman and Mandelbaum, 2010;
Ma and Whitt, 2016; Zychlinski et al., 2020a, b) have been employed in recent
years. We contribute to the literature by proposing a diffusion approximation
(e.g., Halfin and Whitt, 1981; Yao, 1985; Whitt, 2004) of a periodic time-
varying offered load in a system with parallel processing and a dominant
resource. Our analysis builds on the stochastic offered load (SOL) for an
$M_{t}/G/\infty$ queue (Eick et al., 1993; Whitt, 2013), which we employ for
making subsequent capacity allocation decisions.

Since customers can submit multiple jobs to be processed at the same time, our
paper contributes to the literature on queues with batch arrivals (see
Chaudhry and Templeton, 1983; Chaudhry and Gupta, 1999; Economou and Fakinos,
1999; Afèche et al., 2014, for instance). We model arrivals to our system by a
non-homogeneous compound Poisson process with a general distribution of batch
size. While many authors investigate multi-class queueing systems with
arrivals that follow a non-homogeneous Poisson process (see the survey papers
by Defraeye and Van Nieuwenhuyse (2016) and Whitt (2016)), time-varying queues
with batch arrivals remain less prevalent in the queueing literature. Fakinos
(1984), for instance, considers a queue with batch arrivals and infinite
capacity and obtains the transient distribution of the queue length and of the
departure process. For additional information on queues with batch arrivals
refer, for instance, to Chatterjee and Mukherjee (1989); Suhasini et al.
(2014); Kumar et al. (2017); Hemanth Kumar et al. (2020). We contribute to
this stream of literature by developing a modelling approach that adds batch
arrivals to the queues with parallel processing and remains tractable at the
same time. We achieve this goal by assuming that jobs within each batch share
identical service times, while service duration of jobs from different batches
is generally distributed. We show that under such assumption, the workload in
our system follows a non-homogeneous compound Poisson process (this result
does not hold in general, see Economou and Fakinos (1999)). In addition, while
we fit a time-varying batch arrival rate over a typical weekday using a family
of polynomial functions, our methodology accommodates other functional forms,
such as an exponential decay (Furman et al., 2021), polynomial splines
(Anderson and Jones, 1995), or the sum of generalized sine functions (Yom-Tov
and Mandelbaum, 2014).

We employ the SOL to develop a three-stage capacity allocation procedure that
determines the optimal non-stationary allocation of several types of resources
to multiple classes of workload while meeting a set of pre-specified service
level agreements (SLAs). Thus, we also contribute to the literature on
capacity planning for queueing systems with parallel processing, time-
dependent arrivals with batches, and fully flexible servers. In general,
several studies investigate stationary or near-stationary staffing of queueing
systems with time-dependent arrival processes; see Bassamboo and Zeevi, 2009;
Defraeye and Van Nieuwenhuyse, 2013 and Niyirora and Pender (2016) for
example. The problem of staffing for a dynamic service system has also been an
active area of research (e.g., Henderson et al., 1999; Akcali et al., 2006;
Gans et al., 2012). However, literature on capacity planning for systems with
parallel processing is scarce. Several authors propose an integer program to
manage different types of idleness in such systems (Gurvich and Van Mieghem,
2015; Zychlinski et al., 2020b). This type of research is generally oblivious
to the patterns in the arrival rate and assumes that batch arrivals are not
allowed. Our capacity allocation approach builds on the infinite server
approximation (ISA) by Feldman et al. (2008) and the square-root staffing
(SRS) rule (see, e.g., Janssen et al., 2011; Liu, 2018) that we apply over a
planning horizon of an arbitrary length. To the best of our knowledge, this is
the first approach that incorporates batch arrivals and time-varying demand in
systems with parallel processing while preserving tractability and allowing
practitioners to make capacity allocation decisions in real time.

In addition, we contribute to research on capacity allocation for
technological services by proposing a methodology that is motivated by the
operations of Huawei Cloud, a major provider of cloud computing services
around the world. Setting levels of cloud capacity in an environment with high
volatility in demand has been studied by many researchers. For instance, Jiang
et al. (2012), Dorsch and Häckel (2014), and de Assunção et al. (2016) propose
real-time capacity allocation schemes that can be dynamically adjusted
depending on the utilization of servers. The objective of these methods is to
maximize revenue or minimize costs by solving a stochastic dynamic program.
Several studies model cloud computing operations as a queueing system (for
example, Khazaei et al., 2011; Vilaplana et al., 2014; Chiang and Ouyang,
2014). This literature focuses on classical queueing-theoretic approaches that
model cloud services as open networks. Further, Furman and Diamant (2021)
models a private cloud service as a queueing system with retrials, homogeneous
workload and a single type of capacity. They propose a stationary optimal
policy allocating CPU cores in order to meet a pre-specified SLA. Bergsma et
al. (2021) combine elements of queueing framework with recurrent neural
networks to predict future demand of a cloud service provider. Other authors
focus on establishing dynamic pricing policies to maximize cloud’s revenue
(e.g., Wang et al., 2010; Jin et al., 2014; Chen et al., 2019). Our work
extends these studies by proposing a queueing-based methodology that
incorporates more realistic assumptions (e.g., time-varying demand, batch
arrivals, and multiple types of resources) and equips cloud service operators
with a computationally efficient tool allowing them not only to determine the
optimal non-stationary capacity of CPU cores and basic units of memory but
also to forecast future workload.

##  4 Model Formulation

Consider a parallel processing system $\mathcal{QN}$ with $I+1$ classes of
jobs: virtual machines (class $0$) and $I$ classes of containers. Class-$0$
jobs leave unserved if capacity is not available. If a container-type job is
not served immediately, it joins an infinite queue with a pooled structure and
a priority discipline, i.e., a job at the head of the queue is admitted to
service if enough resources are provisioned, otherwise, to avoid unnecessary
idleness, following jobs in order of their arrival can be serviced.
Abandonment is not allowed and service contains $N$ types of resources, e.g.,
CPU cores and memory. We define index sets $\mathcal{I}$ and $\mathcal{N}$,
such that $|\mathcal{I}|=I+1$ and $|\mathcal{N}|=N$. Then, the scarcest or
most expensive resource $\tilde{n}\in\mathcal{N}$ (as determined by a cloud
operator) is considered dominant.

Further, we assume that class-$i$ jobs, $i\in\mathcal{I}$, follow a compound
non-homogeneous Poisson arrival process $\\{\Gamma_{i}(t)|t\geq 0\\}$, i.e.,
contain independent and identically distributed (i.i.d.) batch sizes with mean
$v_{i}<\infty$ and standard deviation $\beta_{i}<\infty$. Define
$\boldsymbol{s}(t)\coloneqq(s_{1}(t),s_{2}(t),...,s_{N}(t))\in\mathbb{Z}^{N}_{+}$
to be the total capacity of each type provisioned in the system at time $t$. A
class-$i$ job requires resources of all types in order to start service, and
its type-$n\in\mathcal{N}$ resource requirements are i.i.d. random variables;
they are generally distributed with mean $r_{in}<\infty$ and standard
deviation $\delta_{in}<\infty$. Preemption is not allowed, and jobs release
resources allocated to them at the end of their service.

We denote the service duration of class-$i$ jobs from different batches by
$S_{i}$, i.i.d. random variables with cdf $G_{i}$, mean $1/\mu_{i}<\infty$,
and standard deviation $\sigma_{i}<\infty$. According to the data set provided
to us by Huawei Cloud, class-$i$ jobs in the same batch have similar durations
of service (see Section 2.1). To ensure tractability, we assume that their
durations are identical. Finally, let $\\{X_{in}(t)\ |\ t\geq 0\\}$ be a
stochastic process that describes the number of type-$n$ servers occupied by
class-$i$ jobs at time $t$. The workflow of such system is presented in Figure
4. The yellow area in the figure represents service capacity, while the grey
rectangles visualize capacity occupied by a single job. For example, the first
job in Figure 4 requires two type-1 resources, one type-2 resource, and 2
type-$N$ resources. Note that multiple jobs can be serviced at the same time.
The red and blue squares represent units of dominant and non-dominant
resources, respectively.

Figure 4: Dynamics of the Service System$1$$2$…$N$$1$$2$…$N$⋮Containers, Class
$1,2,...,I$Served JobsServed JobsUnserved JobsVirtual Machines, Class $0$Total
Capacity

Our partner organization would like to determine the minimum capacity
$\boldsymbol{s}^{*}(t)$, such that a pre-specified service level agreement
(SLA) is satisfied. Denote the stochastic process measuring the time to access
service (i.e., the service delay) experienced by class-$i$ jobs arriving to
the system at time $t$ by $\\{D_{i}(t,\boldsymbol{s}(t))\ |\ t>0\\}$. Then, on
average, for any time $t$, $i\in\mathcal{I}$, $\alpha_{i}\in(0,1)$, and
$\tau_{i}\in[0,\infty)$, no more than fraction $\alpha_{i}$ of type-$i$ jobs
should experience a service delay longer than $\tau_{i}$ over a planning
horizon $T>0$. Due to independence of increments of a non-stationary compound
Poisson process, the lack of anticipation assumption (LAA) holds (Wolff, 1982;
Melamed and Whitt, 1990), and arrivals to the system observe time averages
(ASTA). Thus, a fraction of jobs that wait for service longer than a pre-
specified threshold $\tau_{i}$ can be represented by a proportion of time or
probability that $D_{i}(t,\boldsymbol{s}(t))$ exceeds $\tau_{i}$. Then, we
formulate the following optimization problem

$\displaystyle\underset{\boldsymbol{s}(t)\in\mathbb{R}^{N}_{>0}}{\min}\boldsymbol{s}(t)$
subject to (OPT)
$\displaystyle\mathbb{P}(D_{i}(t,\boldsymbol{s}(t))>\tau_{i})\leq\alpha_{i}\quad\forall
t\in[0,T],\quad\forall i\in\mathcal{I}.$ (SLA)

The form of SLA employed by OPT has been studied in the call centre
literature, and it is a preferred choice of modelling quality of service
constraints (see Soh and Gurvich, 2017, for instance). Unfortunately, solving
OPT is challenging because it is a multi-dimensional, nonlinear minimization
problem. In addition, the probability distribution of the service delay in a
queue with parallel processing is not tractable in closed form. To overcome
these difficulties, in the following sections, we introduce a capacity
allocation approach that constructs a heuristic solution to OPT in three
stages. Specifically, in stage 1 ($\infty$-stage), we determine the
probability distribution of the stochastic offered load (SOL) and propose its
approximation. In stage 2 ($\alpha$-stage), we employ our workload
approximation to set capacity of the dominant resource independently of other
resource requirements. Finally, in stage 3 ($\epsilon$-stage), we assign
capacity levels to non-dominant resources.

##  5 The Capacity Allocation Procedure

In the first stage ($\infty$-stage) of our procedure, we consider the dynamics
of $\mathcal{QN}$ in an uncapacitated regime to derive its stochastic offered
load (SOL). Deriving the SOL involves several challenges, as jobs arrive in
batches and require multiple units of resources at the same time. Thus, we
decompose $\mathcal{QN}$ into queueing networks with tractable dynamics.
Consider a pair of systems $\mathcal{QN}^{e}$ and
$\mathcal{QN}^{\mathbbm{1}e}$ that are embedded in $\mathcal{QN}$. Arrival
times of $\mathcal{QN}^{e}$ represent batch arrival times of $\mathcal{QN}$,
i.e., an individual job arriving to $\mathcal{QN}^{e}$ is a batch of jobs
observed in $\mathcal{QN}$. In addition, as opposed to $\mathcal{QN}^{e}$, all
jobs in $\mathcal{QN}^{\mathbbm{1}e}$ require a single unit of type-$n$
capacity. Then, type-$i$ jobs arriving to these auxiliary systems follow a
non-homogeneous Poisson process $\\{\Lambda_{i}(t)\ |\ t>0\\}$ with rate
$\lambda_{i}(t)\in\mathbb{C}^{1}$.

Denote $\mathcal{QN}$ with infinite capacity by $\mathcal{QN}_{\infty}$. In
such system, jobs do not interfere with each other, thus,
$\mathcal{QN}^{e}_{\infty}$ and $\mathcal{QN}^{\mathbbm{1}e}_{\infty}$ can be
decomposed into $I+1$ independent components. The $i^{th}$ component of
$\mathcal{QN}^{\mathbbm{1}e}_{\infty}$ is an independent $M_{t}/G/\infty$
queue. Let $\\{N_{i}(t)\ |\ t\geq 0\\}$ be a stochastic process describing a
type-$n$ SOL generated by the $i^{th}$ component of
$\mathcal{QN}^{\mathbbm{1}e}_{\infty}$. Notice that, for any
$n\in\mathcal{N}$, the SOL is represented by the same stochastic process.
Further, for any $i\in\mathcal{I}$, $N_{i}(t)$ is well studied in the
literature – it is a non-homogeneous Poisson process with mean $m_{i}(t)$
(Eick et al., 1993)

$m_{i}(t)=\int_{0}^{\infty}\left(\int_{t-\tau}^{t}\lambda_{i}(u)du\right)dG_{i}(\tau)\approx\lambda_{i}(t)\mathbb{E}[S_{i}].$
(1)

In the following Lemma, we leverage this result to determine the probability
distribution of a type-$n$ SOL of $\mathcal{QN}$ generated by class-$i$ jobs.
We also obtain its first two moments in closed form.

######  Lemma 5.1 (Stochastic Offered Load)

Suppose $X^{\infty}_{in}(t)$ denotes utilization of type-$n$ capacity by
class-$i$ jobs in $\mathcal{QN}_{\infty}$. Then, $X^{\infty}_{in}(t)$ is a
compound non-homogeneous Poisson process. Further,

$\mathbb{E}[X^{\infty}_{in}(t)]=v_{i}r_{in}m_{i}(t),\quad
Var[X^{\infty}_{in}(t)]=m_{i}(t)\left(\delta_{in}^{2}v_{i}+r_{in}^{2}\beta_{i}^{2}+v_{i}^{2}r_{in}^{2}\right).$
(2)

In general, a compound non-homogeneous Poisson process exhibits mathematically
convenient properties. However, because it is defined as a stochastic sum of
random quantities, it is difficult to specify (or simulate) without making
additional assumptions. Thus, in the following proposition, by applying Lemma
5.1 and by scaling up the arrival process in $\mathcal{QN}_{\infty}$ by factor
$\xi$, we derive a diffusion approximation of $X^{\infty}_{in}(t)$ that is
easy to use and is not burdened by such limitations.

######  Proposition 5.2 (Diffusion Approximation of the SOL)

Suppose, for any fixed pair $i\in\mathcal{I}$ and $n\in\mathcal{N}$,
$W_{in}(t)$ is the standard Wiener process, then, for $t>0$, the asymptotic
relationship holds

$X^{\infty}_{in}(t)\simeq\hat{X}^{\infty}_{in}(t)=X^{\infty}_{in}(0)-\mathbb{E}[X^{\infty}_{in}(0)]+\mathbb{E}[X^{\infty}_{in}(t)]+\sqrt{Var[X^{\infty}_{in}(t)]}W_{in}(t).$
(3)

To complete the $\infty$-stage of our approach, we specify the probability
distribution of $\hat{X}^{\infty}_{in}(t)$ and the equation of its
$\gamma$-percentile path. To prove these results, we adapt the square-root
staffing rule.

###### Corollary 5.3

Denote the CDF of a standard normal random variable by $\Phi$. Then, for
$t>0$,

  1. 1.

$\hat{X}^{\infty}_{in}(t)$ is normally distributed; its expectation and
variance admit closed-form expressions

$\mathbb{E}[\hat{X}^{\infty}_{in}(t)]=X^{\infty}_{in}(0)-\mathbb{E}[X^{\infty}_{in}(0)]+\mathbb{E}[X^{\infty}_{in}(t)],\quad
Var[\hat{X}^{\infty}_{in}(t)]=tVar[X^{\infty}_{in}(t)].$

  2. 2.

For $\alpha\in[0,1]$, the $\alpha$-percentile path of
$\hat{X}^{\infty}_{in}(t)$ follows the equation

$x_{in}^{\alpha}(t)=X^{\infty}_{in}(0)-\mathbb{E}[X^{\infty}_{in}(0)]+\mathbb{E}[X^{\infty}_{in}(t)]+\sqrt{tVar[X^{\infty}_{in}(t)]}\Phi^{-1}(\alpha).$
(4)

In the following section, we present the $\alpha$-stage of our approach, where
we apply the SOL approximation to determine capacity of the dominant resource
required to satisfy a pre-specified SLA.

###  5.1 The $\alpha$-Stage of the Capacity Allocation

In the $\alpha$-stage of our approach, we determine capacity of the dominant
resource $\tilde{n}\in\mathcal{N}$ independently of other resource
requirements given pre-specified SLAs. We achieve this goal by collapsing the
entire system workload into a fictitious class. Then, we solve $I+1$ non-
linear optimization problems with a single decision variable to determine
capacity levels required for a job of such fictitious class to satisfy each of
the pre-specified SLAs in the original problem. Finally, we construct a convex
combination of these solutions weighted by the SOL generated by respective job
classes.

As mentioned in Section 4, solving OPT necessitates the closed-form expression
of $D_{i}(t,\boldsymbol{s}(t))$ that is difficult to obtain. To this end, we
show the relationship between the SOL and the delay process. Notice that
$\sum_{i=0}^{I}\hat{X}_{i\tilde{n}}^{\infty}(t)-s_{\tilde{n}}(t)$ quantifies
the aggregated amongst job classes workload waiting for the dominant resource
to get serviced at time $t$. Then, following Kim and Whitt (2013), we employ
the instantaneous Little’s Law to approximate the delay experienced by an
“average” job in the system, should all jobs be collapsed into a single
fictitious class

$D_{\cdot\tilde{n}}(t,s_{\tilde{n}}(t))=\left(\sum_{i=0}^{I}\hat{X}_{i\tilde{n}}^{\infty}(t)-s_{\tilde{n}}(t)\right)/\sum_{i=0}^{I}v_{i}r_{i\tilde{n}}\lambda_{i}(t).$
(5)

Then, by substituting $s_{\tilde{n}}(t)$ with
$\nu_{i\tilde{n}}(t)\in\mathbb{C}^{1}$ in (5), i.e., the quantity of the
dominant resource required by jobs of the fictitious class to satisfy the SLA
of class $i\in\mathcal{I}$, we re-write OPT as follows

$\displaystyle\underset{\nu_{i\tilde{n}}(t)\in\mathbb{R}_{\geq
0}}{\min}\nu_{i\tilde{n}}(t)$ subject to (OPTα)
$\displaystyle\mathbb{P}(D_{\cdot\tilde{n}}(t,\nu_{i\tilde{n}}(t))>\tau_{i})\leq\alpha_{i}.\quad\forall
t,$ (SLAα)

As opposed to the original optimization problem, OPTα is a nonlinear problem
with a single decision variable, thus, its solution can be obtained in closed
form. We would like to solve OPTα for all $i\in\mathcal{I}$ and to weight its
solutions by the offered load of respective job classes. In the following
result, we generalize Corollary 5.3, to quantify the aggregated workload in
the system.

###### Corollary 5.4

For $t>0$, $\sum_{i=0}^{I}\hat{X}^{\infty}_{in}(t)$ is normally distributed.
Further, we have that

$\mathbb{E}\left[\sum_{i=0}^{I}\hat{X}^{\infty}_{in}(t)\right]=\sum_{i=0}^{I}\left(X^{\infty}_{in}(0)-\mathbb{E}[X^{\infty}_{in}(0)]+\mathbb{E}[X^{\infty}_{in}(t)]\right),\quad
Var\left[\sum_{i=0}^{I}\hat{X}^{\infty}_{in}(t)\right]=\sum_{i=0}^{I}tVar[X^{\infty}_{in}(t)].$

Similarly to Corollary 5.3, we denote an $\alpha$-percentile path of the
aggregated SOL by $x_{\cdot{}n}^{\alpha_{i}}(t)$. In the following
proposition, we combine the square-root staffing rule with the aggregated SOL
approximation to solve OPTα in closed form. Notice that solutions to OPTα are
only optimal with respect to a specific choice of the SLA corresponding to
class $i$. Thus, we call these solutions fictitious.

######  Proposition 5.5 (Fictitious Quantity of the Dominant Resource)

Define $\gamma_{i}\coloneqq 1-\alpha_{i}$. Then, by Proposition 5.2 and
Corollary 5.4, the solution to OPTα admits the following expression

$\hat{\nu}_{i\tilde{n}}(t)=x_{\cdot{}\tilde{n}}^{\gamma_{i}}(t)-\tau_{i}\sum_{j=0}^{I}v_{j}r_{j\tilde{n}}\lambda_{j}(t),\quad
i\in\mathcal{I}.$ (6)

To conclude the $\alpha$-stage of our approach, we define a time-varying
heuristic that provisions a quantity of the dominant resource given a set of
pre-specified SLAs as a convex combination of the fictitious solutions
obtained in Proposition 5.5. Define
$\omega_{i}(t)\coloneqq\frac{X_{i\tilde{n}}^{\infty}(t)}{\sum_{i=0}^{I}X_{i\tilde{n}}^{\infty}(t)}$,
then we have that

$\hat{s}_{\tilde{n}}(t)\coloneqq\sum_{i=0}^{I}\omega_{i}(t)\hat{\nu}_{i\tilde{n}}(t),\quad\forall
t.$ (7)

In the analysis so far, we have proposed a heuristic that sets the capacity of
the dominant resource given pre-specified SLAs. However, our results do not
prescribe capacity levels to the rest of the resources. In the
$\epsilon$-stage of our capacity allocation procedure, we determine $s_{n}(t)$
for any $n\neq\tilde{n}\in\mathcal{N}$.

###  5.2 The $\epsilon$-Stage of the Capacity Allocation

In the last stage of our approach, we would like to set the service capacity
of resource $n\neq\tilde{n}$ high enough to allow jobs to get serviced once a
sufficient quantity of the dominant resource becomes available. For an
arbitrary small $\epsilon>0$ and $n\neq\tilde{n}$, we consider the following
minimization problem

$\displaystyle\underset{s_{n}(t)\in\mathbb{R}^{N}_{\geq 0}}{\min}s_{n}(t)$
subject to (OPTϵ)
$\displaystyle\mathbb{P}\left(\sum_{i=0}^{I}X_{in}^{\infty}(t)>s_{n}(t)\bigg{|}\sum_{i=0}^{I}X_{i\tilde{n}}^{\infty}(t)\leq\hat{s}_{\tilde{n}}(t)\right)\leq\epsilon,$
$\displaystyle\forall n\neq\tilde{n},\forall t,\forall i.$ (SLAϵ)

In the proposition below, we show that when the capacity of non-dominant
resources is set according to the solution to OPTϵ, only the solution to OPTα
determines if the SLAs in OPT are satisfied.

######  Proposition 5.6 (Setting Quantities of Non-dominant Resources)

Suppose that $\hat{s}_{\tilde{n}}(t)$ satisfies SLA at any time $t\in[0,T]$
and $\alpha\coloneqq 1-\epsilon$. Then, for the solutions to OPTϵ, such that
$n\neq\tilde{n}$,
$\boldsymbol{\hat{s}}(t)\coloneqq(\hat{s}_{1}(t),\hat{s}_{2}(t),...,\hat{s}_{N}(t))$
is the solution to OPT. Further, $\hat{s}_{n}(t)$ admits the following
expression

$\hat{s}_{n}(t)=x_{\cdot{}n}^{\alpha}(t),\quad i\in\mathcal{I},\quad\forall
n\neq\tilde{n}\in\mathcal{N}.$ (8)

Proposition 5.6 sets the capacity levels of non-dominant resources so that
they do not hinder servicing of jobs which have observed a sufficient quantity
of the dominant resource specified in the $\alpha$-stage of the procedure.
Overall, by assigning capacity to the dominant and non-dominant resources, our
approach produces a heuristic solution to OPT that aggregates workload in the
system and results in a “pooled” policy. In the following section, we discuss
an alternative procedure that is closer to the current practices of Huawei
Cloud and is driven by aggregating resources that are dedicated to individual
job classes. In our numerical study, we employ this policy as a benchmark.

###  5.3 Benchmark Approach: Current Practices at the Partner Organization

As mentioned in Section 1, offerings of containerized services have become a
trendy feature amongst cloud computing providers. Combining them with
traditional virtual machines on an integrated platform is even more desirable.
Huawei Cloud has been offering computing virtualization software to support VM
functionality (Elastic Cloud Server) as well as a dedicated cloud container
engine, i.e., their Kubernetes service, to clients on demand.

The objective, however, is to ensure seamless availability of resources to a
wide range of the company’s offerings powered by VMs and containers alike,
without a necessity to dedicate resources to a specific class of jobs (Ke et
al., 2021).

One way to compute the total capacity available in a system with resources
that are dedicated to job classes is to combine them in a single pool. As
opposed to our pooled policy, this approach (the benchmark policy) aggregates
dedicated resources instead of doing so with respective workloads prior to
making any capacity allocation decision. Define a dedicated to class-$i$
capacity of type-$n$ by $\pi_{in}(t)$, such that
$\pi_{n}(t)\coloneqq\sum_{i=0}^{I}\pi_{in}(t)$. Then, for a resource
$n\in\mathcal{N}$ we rewrite (5)

$D_{in}(t,\pi_{in}(t))=\left(\hat{X}_{in}^{\infty}(t)-\pi_{in}(t)\right)/v_{i}r_{in}\lambda_{i}(t).$
(9)

In the following Corollary, we determine capacity levels
$\boldsymbol{\pi}(t)\coloneqq(\pi_{1}(t),\pi_{2}(t),...,\pi_{n}(t))$
provisioned in the system such that pre-specified SLAs are satisfied for a
class-$i\in\mathcal{I}$ and time $t\in[0,T]$.

###### Corollary 5.7

For $\gamma_{i}\coloneqq 1-\alpha_{i}$ and $i\in\mathcal{I}$, using
Proposition 5.5 and Corollary 5.3, we have that

  1. 1.

The optimal capacity of the dominant resource admits the following expression

$\hat{\pi}_{i\tilde{n}}^{\gamma_{i}}(t)=x_{i\tilde{n}}^{\gamma_{i}}(t)-\tau_{i}v_{i}r_{i\tilde{n}}\lambda_{i}(t),\quad\hat{\pi}_{\tilde{n}}(t)\coloneqq\sum_{i=0}^{I}\hat{\pi}_{i\tilde{n}}^{\gamma_{i}}(t).$
(10)

  2. 2.

For $\gamma\coloneqq 1-\epsilon$, the optimal capacity of a non-dominant
resource $n\neq\tilde{n}\in\mathcal{N}$ follows the equations

$\hat{\pi}_{in}^{\gamma}(t)=x_{in}^{\gamma}(t),\quad\hat{\pi}_{n}(t)\coloneqq\sum_{i=0}^{I}\hat{\pi}_{in}^{\gamma}(t).$
(11)

In a setting where capacity is reserved for job classes, equations (10) and
(11) specify optimal quantities of dominant and non-dominant resources,
respectively. We estimate the total capacity of type-$n$ by aggregating its
quantity amongst all job classes. In the following section, we discuss the
modelling assumptions of the proposed pooled policy as well as the suggested
benchmark.

###  5.4 Model Discussion

Our pooled policy enables practitioners to determine quantities of multiple
resources in accordance with pre-specified SLAs in a time-varying setting with
heterogeneous demand and batch arrivals. Capacity allocation in systems with
multiple resources is typically challenging and often employs a single
resource abstraction, i.e., bundles of resources (or slots). However, in a
realistic setting with heterogeneous service requirements, this abstraction is
inefficient (Parkes et al., 2015). Instead, we borrow the notion of the
dominant resource from the Dominant Resource Fairness (DRF) algorithm proposed
in Ghodsi et al. (2011) and modify it to denote the most constraining
resource.

According to the DRF, a resource with the maximum proportion of respective
demand to the available in the system capacity is dominant. Further, the DRF
framework assumes a fixed number of customers who submit jobs with
deterministic service requirements. At the end, to determine the optimal
assignment of existing capacity to clients, the DRF procedure solves a linear
program that maximizes minimum shares of dominant resources available to each
customer. Contrary to the DRF, our model focuses solely on individual jobs
that belong to the same or different batches. As the workload in our system is
time-varying and stochastic, determination of the dominant resource is driven
by the historical data and an expert opinion, i.e., we disentangle this notion
from individual jobs and re-define it as an exogenous property of a cloud
computing system. This allows us to set levels of flexible (rather than
dedicated) capacity myopically and respect probabilistic SLAs. In addition,
our approach requires that jobs belonging to the same batch have identical
service durations. This assumption is required to preserve tractability, and,
thus, our data exploration in Section 2 has shown that service durations of
such jobs are indeed similar.

Further, the delay process in the constraints of OPTα and OPTϵ is constructed
by the application of the Little’s Law to a time-varying environment.
According to Kim and Whitt (2013), this natural approximation of the waiting
time may exhibit a significant bias in highly time-varying systems with long
service durations. Their study shows that the bias is proportional to three
separate quantities: variability of the waiting time distribution, the
relative slope of the arrival function, and the magnitude of the estimated
waiting time. Further, given an adequate approximation of the system workload,
under a time-dependent square-root-staffing rule, the waiting time
distribution remains near stationary even though the arrival rate is time
varying. By aggregating arrival rates across all job classes, our approach
ensures greater uniformity of the arrival process (which in turn reduces
variability of the waiting time distribution) and decreases the relative slope
of the arrival rate. In addition, the magnitude of the waiting time is
influenced by service quality, and, thus, our methodology is to perform better
in a setting with stricter SLAs. On the contrary, approaches that dedicate
capacity to individual job classes do not benefit from pooling arrivals, i.e.,
they are more vulnerable to the estimation bias of the delay process in a
time-varying setting.

Finally, any prediction of system dynamics that uses first or second order
techniques is sensitive to changes in initial conditions. In a time-varying
setting, this sensitivity may become a concern. Because our pooled policy
requires the total start-of-the-day quantities of class-$i$ jobs observed in
the system, its accuracy is influenced by variability in workloads at the end
of a 24-hour period. However, aggregating offered load at the $\alpha$ and
$\epsilon$ stages of our procedure smoothens this effect especially if demand
of a class that contributes the most work to the system is the least time
varying.

##  6 Numerical Study

In this section, we apply our three-stage procedure to a hypothetical cloud
service and compare its performance to a benchmark policy described in
Corollary 5.7. We first show that, in the uncapacitated system parameterized
by the data, our approximation of the stochastic offered load (SOL), as
derived in Proposition 5.2, confines the utilization of CPU cores within the
80-percentile range of its realizations. Then, we determine the levels of
capacity required to satisfy the pre-specified SLAs in two practical
scenarios. We consider a setting with 4 classes of containers that exhibit
near stationary demand and contrast it with an environment where such demand
is highly time-varying. Our experiments suggest that the heuristic solution to
OPT (i.e., the pooled policy) assigns approximately 20% fewer resources than
the benchmark while achieving better service quality.

For both time-varying and near stationary configurations of our discrete event
simulations, we fix $\alpha_{0}$ and $\tau_{0}$ to 0.01 and 0, respectively,
because the probability of waiting of the VMs approaches 0 asymptotically.
Further, for $i\neq 0$, we fix $\alpha_{i}$ to 0.2. This ensures that SLAs of
containers only differ in their waiting thresholds $\tau_{i}$. We distinguish
4 classes of containers with different levels of tolerance for waiting: low,
moderate, and high. In particular, two classes of containers with strict SLAs
have relatively low waiting thresholds of 90 minutes ($\tau_{1}=\tau_{2}$),
while the other two classes have their waiting thresholds set to 450 minutes
($\tau_{3}$) and 900 minutes ($\tau_{4}$), respectively.

Following the argument in Section 2.3, since the arrival process is periodic
and can be modelled by a non-homogeneous Poisson process, without loss of
generality, we select individual arrivals of the VMs over a weekday and use
the curve fitting toolbox in MatLab R2021a to fit the mean of the
corresponding batch arrival process by a polynomial of the third order (see
Figure 5a). For confidentiality, the counts of batch arrivals on the y-axis
are displayed in percentage of the total quantity. We repeat this arrival
pattern over the planning horizon of 7 days and generate batch arrivals with
the fitted mean using a standard thinning algorithm (see Figure 5b).

Figure 5: Fitted Batch Arrival Rate of VMs

(a)

(b)

We model the batch arrivals of containers by independent non-homogeneous
Poisson processes with their means defined as quadratic functions. As advised
by the partner organization, we parameterize them such that the total daily
demand of each class accounts for 19,000 batches or approximately 29,000
individual jobs (see Appendix 8). Figure 6 presents their batch arrival rates
over a typical 24-hour period. Specifically, in the near-stationary
experiments, $\lambda_{1}(t)$ is decreasing, $\lambda_{2}(t)$ and
$\lambda_{4}(t)$ are increasing, and $\lambda_{3}(t)$ has a concave shape (see
Figure 6a). In the time-varying setting, $\lambda_{1}(t)$, $\lambda_{2}(t)$,
and $\lambda_{4}(t)$ are characterized by the spikes over two-hour intervals
in the morning, afternoon, and evening, respectively (there are no arrivals
otherwise), while $\lambda_{3}(t)$ has a spike of a lesser height, but remains
positive over the period of 12 hours in the daytime (see Figure 6b).

Figure 6: Batch Arrival Rates of Containers: (a) Near-stationary Setting; (b)
Time-varying Setting.

(a)

(b)

We generate service durations of VMs and containers using a uniform sampling
with replacement, i.e., we employ a bootstrap distribution of service times
from the data set provided to us by Huawei Cloud. Because containers are
relatively short-lived jobs as opposed to the VMs, we truncate their service
time distributions, such that all realizations that exceed 8 hours are
substituted by this maximum value. Further, we fit the probability mass
functions (pmf) of the CPU-core and RAM requirements of VMs in the data set by
employing a standard frequency-based technique. We assume that service
requirements of VMs and containers are described by the same pmf and provide a
summary of the parameters used in our discrete event simulations in Appendix
8.

We conduct simulations of the service system in Figure 4 operating under our
heuristic (pooled) policy $\boldsymbol{s}(t)$, governed by equations (7) and
(8), and the benchmark $\boldsymbol{\pi}(t)$ as described in Corollary 5.7.
Because the latter reserves capacity for job classes, each experiment under
such policy is equivalent to simulating systems with a single class $i$ for
all $i\in\mathcal{I}$ (i.e., 5 simulations in total). We implement these time-
varying policies by updating the total number of resources available in the
system once per minute. Then, we perform 10 independent sets of these 6
experiments in the near-stationary and time-varying settings that account for
120 trials in total. At the end of each trial, we record the time-varying
distribution of system utilization in percentage, the total number of VMs that
leave the system unserved, and the times individual containers spend waiting
to be serviced.

###  6.1 Fidelity of the SOL Approximation

In this section, we confirm that our SOL approximation as derived in
Proposition 5.2 tracks the workload observed in the data set with relatively
high fidelity. To this end, applying equation (3) and Corollary 5.3 to the
offered load of the dominant resource (CPU cores), we generate 200 stochastic
paths over a planning horizon of 5 days. Then, we discretize it into 7200 one-
minute intervals. We rank these paths, so that the realization with most
arrivals over the largest number of one-minute intervals is labeled first,
i.e., a 99.5-percentile path. According to Figure 7a, the respective 10 and
90-percentile paths constructed by this ranking procedure confine the CPU-core
workload observed in the Huawei Cloud’s data set (see the red line in the
figure).

Figure 7: Data Driven CPU-core Workload: (a) 80-Percentile Range of Ranked
Paths; (b) Percentile Translation.

(a)

(b)

In addition, using the same set of 200 stochastic paths, we construct their
empirical distributions, i.e., at a given minute, the largest number in the
array of 200 values is marked as a 100-percentile. Then, on the y-axis of
Figure 7b, we translate the offered load of the CPU cores observed in the data
set into the values of empirical percentiles. We find that workload implied by
the data set oscillates between 70 and 90-percentile thresholds once it
reaches a steady state.

###  6.2 Discrete Event Simulation: Containers with Near Stationary Demand

In this setting, the demand of containers slowly increases or decreases over a
typical day, i.e., customers submit their requests for service with a near-
uniform intensity over the planning horizon (see Figure 6a). We first compare
the capacity levels allocated by our pooled policy and the benchmark described
in Section 5.3. We then investigate the system utilization under these
policies and plot survival functions of waiting times for all classes of
containers in order to verify that their SLAs are satisfied in the discrete
event simulations. Our results suggest that, in the near-stationary setting,
the proposed fully flexible heuristic dominates the benchmark by achieving
better quality of service while assigning fewer units of capacity to the cloud
computing system.

According to Figure 8, the combined capacity reserved by the benchmark
contains at least 20% and 50% more CPU cores and units of memory,
respectively, compared to the quantities assigned by our pooled policy. We
notice that the capacity allocated to VMs by the benchmark (see the red curve
in the figure) imposes a lower bound on the total capacity levels.

Figure 8: Near-stationary Setting: Dynamics of the Total Capacity Allocation
over a Typical Day.

(a)

(b)

Further, in Figure 9a, we show that both policies may result in idling of
resources. However, the utilization of CPU-cores under the pooled policy
rarely exceeds the 75% mark and remains below 100% at all times, i.e., no job
has to wait for service.

Figure 9: Near-stationary Setting: Distributions of the Capacity Utilization
over a Typical Day.

(a)

(b)

In contrast, dedicating resources results in service congestion. While
containers with stricter SLAs ($\tau_{1}=90$ and $\tau_{2}=90$) experience
idling of resources, jobs with a higher waiting threshold ($\tau_{4}=900$)
fail to get serviced due to insufficient quantity of CPU cores. Notice that
the capacity reserved for these jobs remains idle as no CPU core is
provisioned to them. According to Figure 9b, the non-dominant resource does
not hinder servicing of jobs under any of the policies.

In addition, we investigate class-specific distributions of service delay to
verify if the pre-specified SLAs are respected in simulations. We show in
Figure 10a that dedicated to job-classes capacity may result in poor
performance (recall that under the pooled policy, all jobs access service
immediately). Under the benchmark policy, jobs with lower tolerance for delays
(i.e., 90, 90, and 450 minutes) meet their SLAs. However, the containers of
class 4 remain in the system indefinitely. According to Figure 10b, while
service of $0.02\%$ and $0.04\%$ of jobs with stricter SLAs ($\tau_{1}=90$,
$\tau_{2}=90$, respectively) is delayed, approximately 90% of containers of
class 3 enter a congested system.

Figure 10: Near-Stationary Setting: (a) Likelihood of Delays; (b) Counts of
Delayed Jobs.

(a)

(b)

###  6.3 Discrete Event Simulation: Containers with Time-varying Demand

In this setting, the amount that demand varies with time is driven by the
magnitude of spikes observed during the peak hours of containers arriving to
the system over the morning, evening and night times (see Figure 6b). By
conducting similar tests to Section 6.2, we find that, in the time-varying
setting, our policy outperforms the benchmark once again. In particular, we
observe qualitatively similar results to the near-stationary setting in Figure
11, i.e., our approach provisions significantly less capacity at most times
over a typical day. However, influenced by class-4 containers
($\tau_{4}=900$), the pooled policy assigns more CPU cores than the benchmark
at the end of the day. This is because the workload generated by VMs dominates
the rest of job classes, and, thus, weight $\omega_{0}$ associated with the
service quality that is required by VMs admits a relatively large value (see
Section 5.1). In contrast, due to the high tolerance of delays of class-4
containers, the benchmark policy neglects them at the time of arrival and
serves them during the following day, instead.

Figure 11: Time-varying Setting: Dynamics of the Total Capacity Allocation
over a Typical Day.

(a)

(b)

Further, according to Figure 12, the dynamics of service utilization favour
the pooled policy as it induces less pronounced resource idling compared to
the benchmark (see the capacity reserved for VMs, for instance). Similarly to
the near-stationary setting, all jobs access service immediately under the
pooled policy.

Figure 12: Time-varying Setting: Distributions of the Capacity Utilization
over a Typical Day.

(a)

(b)

In contrast, under the benchmark, classes with peak arrivals in the morning,
evening, and night experience congestion, and containers with arrivals spread
over the daytime observe a busy system at all times. According to the dynamics
of RAM utilization in Figure 12b, a shortage of memory may cause delays to
containers arriving in the morning. We also observe that there is a time lag
between the intensity of arrivals and the system utilization. For instance,
morning arrivals increase the cloud workload in the afternoon.

Finally, in Figure 13a, we show that under the benchmark policy, containers
with most variability in demand wait for service significantly less than their
pre-specified thresholds (i.e., 90, 90, and 900 minutes), and jobs arriving
more uniformly over the daytime do not meet their SLA. In addition, similar to
Section 6.2, few containers of class 1 and 2 experience service delays, while
nearly all jobs of class 3 and 4 join a queue in order to get serviced (see
Figure 13b).

Figure 13: Time-varying Setting: (a) Likelihood of Delays; (b) Counts of
Delayed Jobs.

(a)

(b)

##  7 Discussion and Conclusions

In this paper, we analyze a cloud computing service with parallel processing,
heterogeneous workload with batches (i.e., VMs and containers), and multiple
resources one of which is considered dominant. If VMs do not immediately begin
service, they leave the system, while containers are infinitely patient and
join the queue if needed. However, the duration of their wait must respect a
set of pre-specified SLAs. All jobs in our system require multiple types of
resources to get serviced and release them at service completion. Exact
analysis of this system with time-varying arrivals is intractable. Thus, we
develop a diffusion model of the corresponding stochastic offered load (SOL).
In our subsequent analysis we construct a stochastic approximation of the SOL
in the system with parallel processing. Then, we propose a three-stage
procedure that employs this approximation and modifies the time-varying
square-root-staffing rule to make capacity allocation decisions.

Our methodology overcomes challenges associated with the analysis of queues
with parallel processing, multiple types of resources, and heterogeneous jobs
that are typically analysed in stochastic simulations (Zychlinski et al.,
2020b). Leveraging the approximation of the SOL derived in the $\infty$ stage,
we apply an intuitive aggregation rule to individual workloads in order to
analyze multi-class service systems with flexible resources (the $\alpha$ and
$\epsilon$ stages). Because our approximation of the SOL has a closed-form
expression for a large class of arrival patterns, the approach is general and
remains tractable for arrival functions that admit basic algebraic operations,
i.e., demand complexity is not inherited by the capacity allocation stages of
our method. In addition, as we link the capacity levels that respect
heterogeneous SLAs of jobs at each time instant to the percentile curves of
the SOL available in closed-form, our approach is computationally efficient -
albeit, under some assumptions - such as jobs belonging to a single batch have
identical durations of service.

Our analysis suggests that in settings where demand is near-stationary or
highly time-varying, transitioning to a resource sharing from reserving
capacity is beneficial. That is, services with pooled capacity may achieve
better performance while provisioning fewer resources. Specifically, we show
that our policy does not violate the SLAs and requires at least 20% less
capacity than the benchmark, i.e., savings are achievable together with a
positive service impact.

Further, results from our simulation study suggest that there is a relatively
high fidelity between the SOL approximation and the workload induced by the
data. In addition, the SOL-based weights that we incorporate in our heuristic
policy improve its overall performance in the near-stationary setting, which
results in meeting the SLAs and maintaining high utilization of the dominant
resource (see Figure 9a). To the contrary, the benchmark policy that dedicates
resources to job classes completely neglects jobs with the largest tolerance
for service delays.

We also find that our heuristic handles variability in demand better than the
benchmark. In particular, in Figure 11a and 12a, the heuristic policy assigns
sufficient resources to process containers with peak arrivals during the night
time and does not neglect jobs of other classes (see the time interval from
8pm to 12am). However, the capacity levels set by the benchmark are
insufficient, which results in a violation of the SLA of containers whose
arrivals are spread over the daytime. Nevertheless, our pooled policy is
influenced by a high proportion of workload contributed to the system by VMs.
Their intolerance for delays results in over-provisioning of resources
ensuring that service denial does not occur in the stochastic regime. Because
capacity unused by VMs can be employed by containers, the utilization of a
cloud system operating under such policy remains smaller than one at all
times, which guaranties that all arrivals can access service immediately.

Similarly to Furman and Diamant (2021), our study suggests that cloud
computing providers require large amounts of capacity to satisfy challenging
service level agreements, which results in the resource idling (see Forbes,
2015; FLEXERA, 2019, for instance). To this end, we encourage cloud service
operators to pursue configurations that do not dedicate resources but share
them amongst jobs in a flexible manner. Discussions with our partner
organization indicate that they share these conclusions, i.e., there is a
general consensus amongst major cloud computing providers that resource
pooling constitutes a superior design and must be pursued if possible.

Finally, our approach applies to cases where managers are concerned with the
long-term behavior of the system because cloud computing services operate 24
hours a day and quickly achieve their steady state. Further, as variability in
the system workload increases farther away from its initial state, our
approach tends to assign less capacity at the beginning of the day than in the
late evening. Thus, we recommend that cloud operators interpret the proposed
capacity levels over the first hour of a typical 24-hour period with greater
care. In addition, our method requires providers to be familiar with dynamics
of the offered load in their service system. This information is required to
set the weights in the heuristic policy and can be obtained from the
historical data.

## References

  * Afèche et al. (2014) Afèche P, Diamant A, Milner J (2014) Double-sided batch queues with abandonment: Modeling crossing networks. _Operations Research_ 62(5):1179–1201.
  * Akcali et al. (2006) Akcali E, Côté MJ, Lin C (2006) A network flow approach to optimizing hospital bed capacity decisions. _Health Care Management Science_ 9(4):391–404.
  * Anderson and Jones (1995) Anderson SJ, Jones RH (1995) Smoothing splines for longitudinal data. _Statistics in Medicine_ 14(11):1235–1248.
  * Atlassian (n.d.) Atlassian (n.d.) Containers vs. virtual machines. _Atlassian_ Retrieved from https://www.cloudflare.com/en-ca/learning/cloud/what-is-a-virtual-machine/.
  * Bambos and Walrand (1993) Bambos N, Walrand J (1993) Scheduling and stability aspects of a general class of parallel processing systems. _Advances in Applied Probability_ 25(1):176–202.
  * Bassamboo and Zeevi (2009) Bassamboo A, Zeevi A (2009) On a data-driven method for staffing large call centers. _Operations Research_ 57(3):714–726.
  * Bergsma et al. (2021) Bergsma S, Zeyl T, Senderovich A, Beck JC (2021) Generating complex, realistic cloud workloads using recurrent neural networks. _Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles_ , 376–391.
  * Bramson (1994) Bramson M (1994) Instability of fifo queueing networks. _The Annals of Applied Probability_ 4(2):414–431.
  * Brown et al. (2005) Brown L, Gans N, Mandelbaum A, Sakov A, Shen H, Zeltyn S, Zhao L (2005) Statistical analysis of a telephone call center: A queueing-science perspective. _Journal of the American statistical association_ 100(469):36–50.
  * Bruckner and Tjoa (2002) Bruckner RM, Tjoa AM (2002) Capturing delays and valid times in data warehouses—towards timely consistent analyses. _Journal of Intelligent Information Systems_ 19(2):169–190.
  * Chatterjee and Mukherjee (1989) Chatterjee U, Mukherjee S (1989) On the non-homogeneous service system mx/g/$\inf$. _European journal of operational research_ 38(2):202–207.
  * Chaudhry and Templeton (1983) Chaudhry M, Templeton JG (1983) First course in bulk queues. .
  * Chaudhry and Gupta (1999) Chaudhry ML, Gupta UC (1999) Modelling and analysis of m/g a, b/1/n queue–a simple alternative approach. _Queueing Systems_ 31(1):95–100.
  * Chen et al. (2019) Chen S, Lee H, Moinzadeh K (2019) Pricing schemes in cloud computing: Utilization-based vs. reservation-based. _Production and Operations Management_ 28(1):82–102.
  * Chiang and Ouyang (2014) Chiang YJ, Ouyang YC (2014) Profit optimization in sla-aware cloud services with a finite capacity queuing model. _Mathematical Problems in Engineering_ 2014\.
  * CIO (2021) CIO (2021) Why enterprise it organizations will benefit from application containerization. _CIO_ Retrieved from https://www.cio.com/article/189567/why-enterprise-it-organizations-will-benefit-from-application-containerization.html.
  * Cloudflare (n.d.) Cloudflare (n.d.) What is a virtual machine? _Cloudflare_ Retrieved from https://www.cloudflare.com/en-ca/learning/cloud/what-is-a-virtual-machine/.
  * Cloudwards (2022) Cloudwards (2022) 26 cloud computing statistics, facts & trends for 2022. _Cloudwards_ Retrieved from https://www.cloudwards.net/cloud-computing-statistics/#:
:text=Public%20Cloud%20Services%20Spending%20Is,will%20rise%20to%20%24397.5%20billion.

  * CNCF (2020) CNCF (2020) Cloud native computing foundation: Survey. _CNCF_ Retrieved from https://www.cncf.io/wp–content/uploads/2020/11/CNCF_Survey_Report_2020.pdf.
  * Cortez et al. (2017) Cortez E, Bonde A, Muzio A, Russinovich M, Fontoura M, Bianchini R (2017) Resource central: Understanding and predicting workloads for improved resource management in large cloud platforms. _Proceedings of the 26th Symposium on Operating Systems Principles_ , 153–167.
  * de Assunção et al. (2016) de Assunção MD, Cardonha CH, Netto MA, Cunha RL (2016) Impact of user patience on auto-scaling resource capacity for cloud services. _Future Generation Computer Systems_ 55:41–50.
  * Defraeye and Van Nieuwenhuyse (2013) Defraeye M, Van Nieuwenhuyse I (2013) Controlling excessive waiting times in small service systems with time-varying demand: an extension of the isa algorithm. _Decision Support Systems_ 54(4):1558–1567.
  * Defraeye and Van Nieuwenhuyse (2016) Defraeye M, Van Nieuwenhuyse I (2016) Staffing and scheduling under nonstationary demand for service: A literature review. _Omega_ 58:4–25.
  * Dorsch and Häckel (2014) Dorsch C, Häckel B (2014) Combining models of capacity supply to handle volatile demand: The economic impact of surplus capacity in cloud service environments. _Decision Support Systems_ 58:3–14.
  * Economou and Fakinos (1999) Economou A, Fakinos D (1999) The infinite server queue with arrivals generated by a non-homogeneous compound poisson process and heterogeneous customers. _Stochastic Models_ 15(5):993–1002.
  * Eick et al. (1993) Eick SG, Massey WA, Whitt W (1993) The physics of the $M_{t}/G/\infty$ queue. _Operations Research_ 41(4):731–742.
  * Enterprise IT World (2018) Enterprise IT World (2018) Cloud to drive 95 percent of total datacenter traffic by 2021: Cisco global cloud index. _Forbes_ https://www.enterpriseitworld.com/cloud–to–drive–95–percent–of–total–datacenter–traffic–by–2021–cisco–global–cloud–index/.
  * Fakinos (1984) Fakinos D (1984) The infinite server queue with arrivals generated by a non-homogeneous compound poisson process. _Journal of the Operational Research Society_ 35(5):439–445.
  * Feldman and Mandelbaum (2010) Feldman Z, Mandelbaum A (2010) Using simulation-based stochastic approximation to optimize staffing of systems with skills-based-routing. _Proceedings of the 2010 Winter Simulation Conference_ , 3307–3317 (IEEE).
  * Feldman et al. (2008) Feldman Z, Mandelbaum A, Massey WA, Whitt W (2008) Staffing of time-varying queues to achieve time-stable performance. _Management Science_ 54(2):324–338.
  * FLEXERA (2019) FLEXERA (2019) Research report, 2019 state of the cloud report: See the latest cloud trends. _FLEXERA_ Retrieved from https://info.flexera.com/SLO-CM-WP-State-of-the-Cloud-2019.
  * Forbes (2015) Forbes (2015) 30% of servers are sitting ”comatose“ according to research. _Forbes_ https://www.forbes.com/sites/benkepes/2015/06/03/30-of-servers-are-sitting-comatose-according-to-research/#484c37d759c7.
  * Furman and Diamant (2021) Furman E, Diamant A (2021) Optimal capacity planning for cloud service providers with periodic, time-varying demand. _Available at SSRN 3648442_ .
  * Furman et al. (2021) Furman E, Diamant A, Kristal M (2021) Customer acquisition and retention: A fluid approach for staffing. _Production and Operations Management_ 30(11):4236–4257.
  * Gans et al. (2012) Gans N, Shen H, Zhou Y (2012) Parametric stochastic programming models for call-center workforce scheduling. genesys telecommunications laboratories.
  * Gartner (2019) Gartner (2019) Gartner forecasts worldwide public cloud revenue to grow 172020. _Gartner_ Retrieved from https://www.gartner.com/en/newsroom/press-releases/2019-11-13-gartner-forecasts-worldwide-public-cloud-revenue-to-grow-17-percent-in-2020.
  * Gartner (2021) Gartner (2021) The innovation leader’s guide to navigating the cloud-native container ecosystem. _Gartner_ Retrieved from https://www.gartner.com/en/documents/4004870.
  * Ghodsi et al. (2011) Ghodsi A, Zaharia M, Hindman B, Konwinski A, Shenker S, Stoica I (2011) Dominant resource fairness: Fair allocation of multiple resource types. _8th USENIX Symposium on Networked Systems Design and Implementation (NSDI 11)_.
  * Gimpelson (1965) Gimpelson L (1965) Analysis of mixtures of wide-and narrow-band traffic. _IEEE Transactions on Communication Technology_ 13(3):258–266.
  * Green (1978) Green L (1978) _Queues which Allow a Random Number of Servers per Customer._ Ph.D. thesis, Yale University.
  * Green (1980) Green L (1980) Comparing operating characteristics in queues in which customers require a random number of servers (to appear in management science). _GreenManagement Science1980_ .
  * Green (1981) Green L (1981) Comparing operating characteristics of queues in which customers require a random number of servers. _Management Science_ 27(1):65–74.
  * Gurvich and Van Mieghem (2015) Gurvich I, Van Mieghem JA (2015) Collaboration and multitasking in networks: Architectures, bottlenecks, and capacity. _Manufacturing & Service Operations Management_ 17(1):16–33.
  * Gurvich and Van Mieghem (2018) Gurvich I, Van Mieghem JA (2018) Collaboration and multitasking in networks: Prioritization and achievable capacity. _Management science_ 64(5):2390–2406.
  * Halfin and Whitt (1981) Halfin S, Whitt W (1981) Heavy-traffic limits for queues with many exponential servers. _Operations research_ 29(3):567–588.
  * Hemanth Kumar et al. (2020) Hemanth Kumar M, Ganesh T, Venkateswaran M, Reddy P (2020) Compound intervened poisson distribution through one server queuing model with non-homogeneous compound poisson arrivals in bulk and its service rates. _Journal of Statistics and Management Systems_ 23(8):1427–1444.
  * Henderson et al. (1999) Henderson S, Mason A, Ziedins I, Thomson R (1999) A heuristic for determining efficient staffing requirements for call centres. Technical report, Citeseer.
  * Jacobson and Lazowska (1982) Jacobson PA, Lazowska ED (1982) Analyzing queueing networks with simultaneous resource possession. _Communications of the ACM_ 25(2):142–151.
  * Janssen et al. (2011) Janssen A, Van Leeuwaarden JS, Zwart B (2011) Refining square-root safety staffing by expanding erlang c. _Operations Research_ 59(6):1512–1522.
  * Jiang et al. (2012) Jiang Y, Perng Cs, Li T, Chang R (2012) Self-adaptive cloud capacity planning. _2012 IEEE Ninth International Conference on Services Computing_ , 73–80 (IEEE).
  * Jin et al. (2014) Jin H, Wang X, Wu S, Di S, Shi X (2014) Towards optimized fine-grained pricing of iaas cloud platform. _IEEE Transactions on cloud Computing_ 3(4):436–448.
  * Kaufman (1981) Kaufman J (1981) Blocking in a shared resource environment. _IEEE Transactions on communications_ 29(10):1474–1481.
  * Kaufman and Wang (1989) Kaufman JS, Wang Y (1989) A conservation law based approximate analysis for a class of simultaneous resource possession problems. _Performance evaluation_ 10(4):263–280.
  * Kaufman and Wong (1990) Kaufman JS, Wong WS (1990) Approximate analysis of a cyclic queuing network with applications to a simultaneous resource possession problem. _Performance evaluation_ 11(3):187–200.
  * Ke et al. (2021) Ke X, Guo C, Ji S, Bergsma S, Hu Z, Guo L (2021) Fundy: A scalable and extensible resource manager for cloud resources. _2021 IEEE 14th International Conference on Cloud Computing (CLOUD)_ , 540–550 (IEEE).
  * Khazaei et al. (2011) Khazaei H, Misic J, Misic VB (2011) Performance analysis of cloud computing centers using m/g/m/m+ r queuing systems. _IEEE Transactions on parallel and distributed systems_ 23(5):936–943.
  * Kim and Whitt (2013) Kim SH, Whitt W (2013) Estimating waiting times with the time-varying little’s law. _Probability in the Engineering and Informational Sciences_ 27(4):471–506.
  * Kumar et al. (2017) Kumar H, Venkateswaran M, Ganesh T, Reddy P (2017) Single-server queueing model with non-homogeneous compound poisson bulk arrivals with intervened poisson distribution. _Research & Reviews: Journal of Statistics_ 6(3):1021.
  * Li et al. (2017) Li W, Liu X, Zhang X, Zhang X (2017) A further analysis of the dynamic dominant resource fairness mechanism. _International Workshop on Frontiers in Algorithmics_ , 163–174 (Springer).
  * Liu (2018) Liu Y (2018) Staffing to stabilize the tail probability of delay in service systems with time-varying demand. _Operations Research_ 66(2):514–534.
  * Ma and Whitt (2016) Ma N, Whitt W (2016) Efficient simulation of non-poisson non-stationary point processes to study queueing approximations. _Statistics & Probability Letters_ 109:202–207.
  * Melamed and Whitt (1990) Melamed B, Whitt W (1990) On arrivals that see time averages: a martingale approach. _Journal of applied probability_ 27(2):376–384.
  * Niyirora and Pender (2016) Niyirora J, Pender J (2016) Optimal staffing in nonstationary service centers with constraints. _Naval Research Logistics (NRL)_ 63(8):615–630.
  * Papadimitriou and Tsitsiklis (1994) Papadimitriou CH, Tsitsiklis JN (1994) The complexity of optimal queueing network control. _Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory_ , 318–322 (IEEE).
  * Parkes et al. (2015) Parkes DC, Procaccia AD, Shah N (2015) Beyond dominant resource fairness: Extensions, limitations, and indivisibilities. _ACM Transactions on Economics and Computation (TEAC)_ 3(1):1–22.
  * Reiman (1991) Reiman MI (1991) A critically loaded multiclass erlang loss system. _Queueing Systems_ 9(1):65–81.
  * Soh and Gurvich (2017) Soh SB, Gurvich I (2017) Call center staffing: Service-level constraints and index priorities. _Operations Research_ 65(2):537–555.
  * Suhasini et al. (2014) Suhasini A, Srinivasa Rao K, Reddy PR (2014) Queueing model with non-homogeneous bulk arrivals having state-dependent service rates. _International Journal of Operational Research_ 21(1):84–99.
  * Verma et al. (2015) Verma A, Pedrosa L, Korupolu M, Oppenheimer D, Tune E, Wilkes J (2015) Large-scale cluster management at google with borg. _Proceedings of the Tenth European Conference on Computer Systems_ , 1–17.
  * Vilaplana et al. (2014) Vilaplana J, Solsona F, Teixidó I, Mateo J, Abella F, Rius J (2014) A queuing theory model for cloud computing. _The Journal of Supercomputing_ 69(1):492–507.
  * Visschers et al. (1999) Visschers J, Adan I, Wessels J (1999) _Product form solutions to production systems with simultaneous resource possession_ (Eindhoven University of Technology, Department of Mathematics and Computing …).
  * Wang et al. (2010) Wang H, Jing Q, He B, Qian Z, Zhou L (2010) Distributed systems meet economics: pricing in the cloud .
  * Wang et al. (2014) Wang W, Li B, Liang B (2014) Dominant resource fairness in cloud computing systems with heterogeneous servers. _IEEE INFOCOM 2014-IEEE Conference on Computer Communications_ , 583–591 (IEEE).
  * Whitt (2004) Whitt W (2004) A diffusion approximation for the g/gi/n/m queue. _Operations Research_ 52(6):922–941.
  * Whitt (2013) Whitt W (2013) Om forum—offered load analysis for staffing. _Manufacturing & Service Operations Management_ 15(2):166–169.
  * Whitt (2016) Whitt W (2016) Queues with time-varying arrival rates: A bibliography. _Available on http://www. columbia. edu/~ ww2040/TV_bibliography_091016. pdf_ .
  * Wolff (1982) Wolff RW (1982) Poisson arrivals see time averages. _Operations research_ 30(2):223–231.
  * Wolman (1972) Wolman E (1972) The camp-on problem for multiple-address traffic. _Bell System Technical Journal_ 51(6):1363–1422.
  * Yao (1985) Yao DD (1985) Refining the diffusion approximation for the m/g/m queue. _Operations research_ 33(6):1266–1277.
  * Yom-Tov and Mandelbaum (2014) Yom-Tov GB, Mandelbaum A (2014) Erlang-r: A time-varying queue with reentrant customers, in support of healthcare staffing. _Manufacturing & Service Operations Management_ 16(2):283–299.
  * Zhang and Ansari (2013) Zhang Y, Ansari N (2013) Heterogeneity aware dominant resource assistant heuristics for virtual machine consolidation. _2013 IEEE Global Communications Conference (GLOBECOM)_ , 1297–1302 (IEEE).
  * Zychlinski et al. (2020a) Zychlinski N, Chan CW, Dong J (2020a) Managing queues with different resource requirements.
  * Zychlinski et al. (2020b) Zychlinski N, Chan CW, Dong J (2020b) Scheduling queues with simultaneous and heterogeneous requirements from multiple types of servers. _2020 Winter Simulation Conference (WSC)_ , 2365–2376 (IEEE).

Appendices and Proofs of Statements

##  8 Simulation Parameters

Table 4 and 4 present the arrival functions of 4 classes of containers in a
near stationary and time-varying setting, respectively.

Table 4 and 4 provide a summary of the generated data that we employ to
parameterize our experiments. Specifically, we generate 10 sets of data using
bootstrap distributions of service times, fitted probability mass functions of
capacity requirements, and non-homogeneous Poisson batch arrival processes
with mean rates presented in Table 4 and 4. For example, 666.424 in Column 2,
is the grand average of mean service times of VMs observed in 10 stochastic
experiments in a near-stationary setting.

Table 1: Near-stationary Containers

| Batch Arrival Function
---|---
Container 1 | $\lambda_{1}(t)=-\frac{1}{3,568,896}t^{2}-\frac{155}{297,408}t+\frac{191,875}{13,941}$
Container 2 | $\lambda_{2}(t)=-\frac{19}{81,544,320}t^{2}+\frac{19}{28,512}t+\frac{729,125}{56,628}$
Container 3 | $\lambda_{3}(t)=-\frac{19}{92,314,944}t^{2}+\frac{1235}{5,769,684}t+\frac{25,353,125}{1,923,228}$
Container 4 | $\lambda_{4}(t)=-\frac{19}{85,578,624}t^{2}+\frac{29,165}{21,394,656}t+\frac{33,071,875}{2,674,332}$

Table 2: Time-varying Containers

| Batch Arrival Function
---|---
Container 1 | $\lambda_{1}(t)=-\frac{19}{288}t^{2}+\frac{665}{12}t-11,400$
Container 2 | $\lambda_{2}(t)=-\frac{19}{288}t^{2}+\frac{1615}{12}t-68,400$
Container 3 | $\lambda_{3}(t)=-\frac{19}{62,208}t^{2}+\frac{95}{216}t-118.75$
Container 4 | $\lambda_{4}(t)=-\frac{19}{288}t^{2}+\frac{1045}{6}t-114,712.5$

Table 3: Average Queueing Parameters: Near-stationary Setting

Column 1 |  Column 2 VMs, $i=0$ |  Column 3 Containers, $i=1$ |  Column 4 Containers, $i=2$ |  Column 5 Containers, $i=3$ |  Column 6 Containers, $i=4$
---|---|---|---|---|---
Mean Service Time, $1/\mu_{i}$, in Minutes | 666.424 | 89.589 | 89.439 | 89.744 | 89.417
St. Dev. Service Time, $\sigma_{i}$, in Minutes | 1,681 | 172.306 | 172.170 | 172.293 | 171.969
Mean Batch Size, $v_{i}$ | 1.439 | 1.439 | 1.438 | 1.438 | 1.440
St. Dev. Batch Size, $\beta_{i}$ | 1.344 | 1.338 | 1.341 | 1.340 | 1.340
Mean CPU-core Req., $r_{i1}$ | 4.108 | 4.103 | 4.110 | 4.010 | 4.099
St. Dev. CPU-core Req., $\delta_{i1}$ | 7.812 | 7.785 | 7.802 | 7.785 | 7.763
Mean RAM Req., $r_{i2}$, in GBs | 11.542 | 11.488 | 11.504 | 11.495 | 11.510
St. Dev. RAM Req., $\delta_{i2}$, in GBs | 34.505 | 33.946 | 34.255 | 34.528 | 34.288

Table 4: Average Queueing Parameters: Time-varying Setting

Column 1 |  Column 2 VMs, $i=0$ |  Column 3 Containers, $i=1$ |  Column 4 Containers, $i=2$ |  Column 5 Containers, $i=3$ |  Column 5 Containers, $i=4$
---|---|---|---|---|---
Mean Service Time, $1/\mu_{i}$, in Minutes | 667.588 | 89.671 | 89.412 | 89.631 | 90.043
St. Dev. Service Time, $\sigma_{i}$, in Minutes | 1,682 | 172.326 | 172.547 | 172.321 | 171.691
Mean Batch Size, $v_{i}$ | 1.439 | 1.440 | 1.439 | 1.436 | 1.438
St. Dev. Batch Size, $\beta_{i}$ | 1.342 | 1.354 | 1.339 | 1.334 | 1.335
Mean CPU-core Req., $r_{i1}$ | 4.120 | 4.106 | 4.093 | 4.106 | 4.104
St. Dev. CPU-core Req., $\delta_{i1}$ | 7.831 | 7.805 | 7.746 | 7.819 | 7.782
Mean RAM Req., $r_{i2}$, in GBs | 11.497 | 11.469 | 11.549 | 11.508 | 11.520
St. Dev. RAM Req., $\delta_{i2}$, in GBs | 34.278 | 33.587 | 34.747 | 34.130 | 34.884

## Summary of the Results: System Utilization

Tables 8 \- 8 and Tables 8 \- 8 accompany the bar plots of the system
utilization in Section 6 in the near-stationary and time-varying setting,
respectively. In these tables, the first column specifies a capacity
allocation policy. For example, “Pooled policy” refers to the proposed
heuristic, while “VMs” represents resources dedicated to virtual machines
under the benchmark policy. The remaining columns correspond to the values
over a weekday with 2-hour intervals. We present the largest values of the
utilization below 90% in bold, while the instances when the system operates
closer to full capacity are highlighted in red.

Table 5: System Utilization of the Dominant Resource (%): Near-stationary
Setting

Column 1 |  Column 2 2 am |  Column 3 4 am |  Column 4 6 am |  Column 5 8 am |  Column 6 10 am |  Column 7 12 am |  Column 8 2 pm |  Column 9 4 pm |  Column 10 6 pm |  Column 11 8 pm |  Column 12 10 pm |  Column 13 12 pm
---|---|---|---|---|---|---|---|---|---|---|---|---
Pooled Policy | 60.256 | 83.712 | 71.311 | 65.396 | 62.666 | 61.959 | 62.432 | 63.683 | 64.921 | 65.472 | 65.294 | 63.384
VMs | 40.369 | 57.154 | 47.340 | 42.963 | 41.279 | 40.949 | 42.037 | 43.436 | 45.054 | 46.136 | 46.224 | 44.198
Container 1 | 37.311 | 79.653 | 66.305 | 58.741 | 54.745 | 50.139 | 46.860 | 44.826 | 42.819 | 41.204 | 39.596 | 38.868
Container 2 | 39.150 | 76.624 | 63.365 | 55.764 | 49.881 | 47.362 | 44.324 | 42.612 | 41.263 | 40.595 | 38.818 | 38.277
Container 3 | 99.970 | 99.736 | 99.779 | 99.566 | 100.000 | 100.000 | 100.000 | 100.000 | 99.979 | 99.950 | 99.981 | 99.975
Container 4 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000

Table 6: System Utilization of the Non-dominant Resource: Near-stationary
Setting

Column 1 |  Column 2 2 am |  Column 3 4 am |  Column 4 6 am |  Column 5 8 am |  Column 6 10 am |  Column 7 12 am |  Column 8 2 pm |  Column 9 4 pm |  Column 10 6 pm |  Column 11 8 pm |  Column 12 10 pm |  Column 13 12 pm
---|---|---|---|---|---|---|---|---|---|---|---|---
Pooled Policy | 28.600 | 48.715 | 39.868 | 35.614 | 33.272 | 32.200 | 31.711 | 31.696 | 31.598 | 31.810 | 31.201 | 30.397
VMs | 24.953 | 42.453 | 33.905 | 30.160 | 28.266 | 27.592 | 27.806 | 28.263 | 28.949 | 29.393 | 29.215 | 27.756
Container 1 | 9.679 | 25.779 | 19.689 | 17.189 | 15.262 | 13.629 | 12.113 | 11.259 | 10.451 | 10.598 | 9.804 | 9.966
Container 2 | 10.271 | 26.412 | 19.626 | 15.829 | 14.027 | 12.648 | 11.430 | 10.978 | 10.607 | 10.599 | 10.017 | 10.038
Container 3 | 10.998 | 18.393 | 9.040 | 3.993 | 7.701 | 10.320 | 13.249 | 15.531 | 17.331 | 15.661 | 14.134 | 12.923
Container 4 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000

Table 7: System Utilization of the Dominant Resource (%): Time-varying Setting

Column 1 |  Column 2 2 am |  Column 3 4 am |  Column 4 6 am |  Column 5 8 am |  Column 6 10 am |  Column 7 12 am |  Column 8 2 pm |  Column 9 4 pm |  Column 10 6 pm |  Column 11 8 pm |  Column 12 10 pm |  Column 13 12 pm
---|---|---|---|---|---|---|---|---|---|---|---|---
Pooled Policy | 66.531 | 62.351 | 54.965 | 44.964 | 60.426 | 57.655 | 59.824 | 64.315 | 54.055 | 72.419 | 63.468 | 36.849
VMs | 39.347 | 55.095 | 45.989 | 41.955 | 40.046 | 39.851 | 40.570 | 42.171 | 43.706 | 44.995 | 45.033 | 43.219
Container 1 | 39.844 | 39.844 | 39.844 | 0.000 | 99.223 | 99.972 | 99.956 | 99.993 | 0.000 | 0.000 | 0.000 | 0.000
Container 2 | 99.913 | 0.091 | 0.091 | 0.091 | 0.091 | 0.091 | 0.091 | 0.091 | 0.000 | 87.603 | 99.949 | 99.244
Container 3 | 99.110 | 100.000 | 100.000 | 100.000 | 99.300 | 99.902 | 100.000 | 100.000 | 100.000 | 99.836 | 99.881 | 99.555
Container 4 | 100.000 | 98.656 | 87.908 | 82.828 | 20.120 | 1.874 | 0.287 | 0.287 | 0.287 | 0.287 | 0.287 | 98.286

Table 8: System Utilization of the Non-dominant Resource (%): Time-varying
Setting

Column 1 |  Column 2 2 am |  Column 3 4 am |  Column 4 6 am |  Column 5 8 am |  Column 6 10 am |  Column 7 12 am |  Column 8 2 pm |  Column 9 4 pm |  Column 10 6 pm |  Column 11 8 pm |  Column 12 10 pm |  Column 13 12 pm
---|---|---|---|---|---|---|---|---|---|---|---|---
Pooled Policy | 37.521 | 43.287 | 35.938 | 28.052 | 31.652 | 29.490 | 30.071 | 31.879 | 27.399 | 39.301 | 36.194 | 17.874
VMs | 25.119 | 43.274 | 34.379 | 30.416 | 28.606 | 27.693 | 27.719 | 28.267 | 28.692 | 29.278 | 29.112 | 27.641
Container 1 | 36.969 | 36.969 | 36.969 | 0.000 | 75.767 | 99.973 | 99.946 | 99.991 | 0.000 | 0.000 | 0.000 | 0.000
Container 2 | 98.720 | 0.044 | 0.044 | 0.044 | 0.044 | 0.044 | 0.044 | 0.044 | 0.000 | 36.911 | 99.965 | 97.592
Container 3 | 89.549 | 91.575 | 92.223 | 92.283 | 3.795 | 1.734 | 2.806 | 4.522 | 9.128 | 74.826 | 99.819 | 99.931
Container 4 | 99.989 | 99.154 | 89.110 | 83.289 | 19.547 | 2.203 | 1.132 | 1.132 | 1.132 | 1.132 | 1.132 | 0.018

## Proofs of the results

### Proof of Lemma 5.1

###### Proof 8.1

Proof Let $M_{in}$ be a random variable representing type-$n$ capacity
requirement of a class-$i$ job. Consider an infinite capacity system
$\mathcal{QN}^{e}_{\infty}$ and write out its type-$n$ utilization by
class-$i$ jobs

$X^{e\infty}_{in}(t)=\sum_{k=1}^{N_{i}(t)}M_{ink},$

where, for fixed $i$ and $n$, $M_{ink}$ and $M_{in}$ are i.i.d. for any $k$,
and $N_{i}(t)$ is a type-$n$ offered load generated by class-$i$ jobs in
$\mathcal{QN}^{\mathbbm{1}e}_{\infty}$. Recall that each job in
$\mathcal{QN}^{e}_{\infty}$ is a batch of jobs observed in
$\mathcal{QN}_{\infty}$, thus, for a random variable $V_{i}$ denoting a batch
size of class-$i$ jobs, we have that

$X^{\infty}_{in}(t)=\sum_{k=1}^{N_{i}(t)}\sum_{l=1}^{V_{ik}}M_{inkl},$

where, for fixed $i$ and $n$, $M_{inkl}$ and $M_{in}$ are i.i.d. and $V_{ik}$
and $V_{p}$ are i.i.d. for any $k$ and $l$. Let
$B_{ink}\coloneqq\sum_{l=1}^{V_{ik}}M_{inkl}$, then because $\\{V_{ik}\\}_{k}$
are i.i.d., and $\\{M_{inkl}\\}_{kl}$ are i.i.d. for any $k$ and $l$,
$\\{B_{ink}\\}_{k}$ are also i.i.d. Further, because
$\mathbb{E}[V_{i}]<\infty$, $Var[V_{i}]<\infty$, $\mathbb{E}[M_{in}]<\infty$,
and $Var[M_{in}]<\infty$, both expectation and variance of $B_{ink}$ are
finite for any $k$. Thus, for fixed $i$ and $n$, because $N_{i}(t)$ is a non-
homogeneous Poisson process, and $B_{ink}$ are i.i.d. for any $k$, we have
that

$X^{\infty}_{in}(t)=\sum_{k=1}^{N_{i}(t)}B_{ink}$

is a compound non-homogeneous Poisson process, and its expectation and
variance are well known:

$\mathbb{E}[X^{\infty}_{in}(t)]=\mathbb{E}[N_{i}(t)]\mathbb{E}[B_{in1}]=m_{i}(t)\mathbb{E}[B_{in1}]$

and

$Var[X^{\infty}_{in}(t)]=m_{i}(t)\left(Var[B_{in1}]+\mathbb{E}[B_{in1}]^{2}\right).$

To complete the proof, we derive $\mathbb{E}[B_{in1}]$ and $Var[B_{in1}]$.
$\mathbb{E}[B_{in1}]$ immediately follows from Wald’s equation

$\mathbb{E}[B_{in1}]=\mathbb{E}[M_{in11}+M_{in12}+...+M_{in1V_{ik}}]=\mathbb{E}[V_{ik}]\mathbb{E}[M_{in}]=v_{i}r_{in}.$

Then, we apply the law of total variance to obtain $Var[B_{in1}]$

$\displaystyle Var[B_{in1}]$
$\displaystyle=\mathbb{E}[Var[B_{in1}|V_{i1}]]+Var[\mathbb{E}[B_{in1}|V_{i1}]]$
$\displaystyle=\mathbb{E}[V_{i1}Var[M_{in}]]+Var[V_{i1}\mathbb{E}[M_{in}]]$
$\displaystyle=Var[M_{in}]\mathbb{E}[V_{i1}]+\mathbb{E}[M_{in}]^{2}Var[V_{i1}]$
$\displaystyle=\delta_{in}^{2}v_{i}+r_{in}^{2}\beta_{i}^{2}.$

Therefore,

$\mathbb{E}[X^{\infty}_{in}(t)]=v_{i}r_{in}m_{i}(t),\quad
Var[X^{\infty}_{in}(t)]=m_{i}(t)\left(\delta_{in}^{2}v_{i}+r_{in}^{2}\beta_{i}^{2}+v_{i}^{2}r_{in}^{2}\right).$

$\square$

### Proof of Proposition 5.2

###### Proof 8.2

Proof We scale the arrival process to $\mathcal{QN}^{e}_{\infty}$ up by factor
$\xi$, i.e., the scaled intensity of class-$i$ batch arrivals equals
$\xi\lambda_{i}(t)$, and the scaled $X^{\infty}_{in}(t)$ is denoted by
$X^{\xi\infty}_{in}(t)$. Applying the functional law of large numbers, we have
the following fluid limit

$lim_{\xi\to\infty}\frac{X^{\xi\infty}_{in}(t)}{\xi}=\mathbb{E}[X^{\infty}_{in}(t)].$

Let $\bar{X}^{\infty}_{in}(t;\xi)=\frac{1}{\xi}(X^{\xi\infty}_{in}(t))$. Then,
by the functional central limit theorem,

$\lim_{\xi\to{\infty}}\sqrt{\xi}(\bar{X}^{\infty}_{in}(t;\xi)-\mathbb{E}[X^{\infty}_{in}(t)])=\sqrt{Var[X^{\infty}_{in}(t)]}W_{in}(t),$

where $W_{in}(t)$ is the standard Wiener process.

We have that
$dX^{\infty}_{in}(t)\simeq\left(\mathbb{E}[X^{\infty}_{in}(t)]\right)^{\prime}dt+\sqrt{Var[X^{\infty}_{in}(t)]}dW_{in}(t)$.
By integrating both sides, for $t>0$, the desired result is obtained,

$\displaystyle X^{\infty}_{in}(t)$
$\displaystyle\simeq\hat{X}^{\infty}_{in}(t)=X^{\infty}_{in}(0)-\mathbb{E}[X^{\infty}_{in}(0)]+\mathbb{E}[X^{\infty}_{in}(t)]+\sqrt{Var[X^{\infty}_{in}(t)]}W_{in}(t)$
$\displaystyle=X^{\infty}_{in}(0)-v_{i}r_{in}m_{i}(0)+v_{i}r_{in}m_{i}(t)+\sqrt{m_{i}(t)\left(\delta_{in}^{2}v_{i}+r_{in}^{2}\beta_{i}^{2}+v_{i}^{2}r_{in}^{2}\right)}W_{in}(t).$

$\square$

### Proof of Corollary 5.3

###### Proof 8.3

Proof Because $W_{np}(t)\sim N(0,t)$, we re-write (3)

$\hat{X}^{\infty}_{in}(t)=X^{\infty}_{in}(0)-\mathbb{E}[X^{\infty}_{in}(0)]+\mathbb{E}[X^{\infty}_{in}(t)]+\sqrt{tVar[X^{\infty}_{in}(t)]}Z,$

where $Z$ is a standard normal random variable.

Clearly, $\hat{X}^{\infty}_{in}(t)\sim
N(X^{\infty}_{in}(0)-\mathbb{E}[X^{\infty}_{in}(0)]+\mathbb{E}[X^{\infty}_{in}(t)],tVar[X^{\infty}_{in}(t)])$.
The result in (4) immediately follows. $\square$

### Proof of Corollary 5.4

###### Proof 8.4

Proof Because $\hat{X}^{\infty}_{in}(t)$ are independent stochastic processes
for $i\in\mathcal{I}$ and $n\in\mathcal{N}$, the result follows immediately
from Corollary 5.3. $\square$

### Proof of Corollary 5.7

###### Proof 8.5

Proof Follows from Corollary 5.3 and Proposition 5.5. $\square$

### Proof of Proposition 5.5

###### Proof 8.6

Proof

  1. 1.

For a fixed $t$, we consider SLAα
$\mathbb{P}\left(\sum_{i=0}^{I}X_{i\tilde{n}}^{\infty}(t)>\tau_{i}\sum_{j=0}^{I}v_{j}r_{j\tilde{n}}\lambda_{j}(t)+\nu_{i\tilde{n}}(t)\right)\simeq\mathbb{P}\left(\sum_{i=0}^{I}\hat{X}_{i\tilde{n}}^{\infty}(t)>\tau_{i}\sum_{j=0}^{I}v_{j}r_{j\tilde{n}}\lambda_{j}(t)+\nu_{i\tilde{n}}(t)\right)$.
Per Corollary 5.4, $\sum_{i=0}^{I}\hat{X}^{\infty}_{i\tilde{n}}(t)\sim
N\left(\sum_{i=0}^{I}X^{\infty}_{i\tilde{n}}(0)-\mathbb{E}[X^{\infty}_{i\tilde{n}}(0)]+\mathbb{E}[X^{\infty}_{i\tilde{n}}(t)],\sum_{i=0}^{I}tVar[X^{\infty}_{i\tilde{n}}(t)]\right)$.
We have that

$\mathbb{P}\left(\sum_{i=0}^{I}\hat{X}_{i\tilde{n}}^{\infty}(t)>\tau_{i}\sum_{j=0}^{I}v_{j}r_{j\tilde{n}}\lambda_{j}(t)+\nu_{i\tilde{n}}(t)\right)=\mathbb{P}\left(Z>\frac{\tau_{i}\sum_{j=0}^{I}v_{j}r_{j\tilde{n}}\lambda_{j}(t)+\nu_{i\tilde{n}}(t)-\mathbb{E}\left[\sum_{i=0}^{I}\hat{X}^{\infty}_{i\tilde{n}}(t)\right]}{\sqrt{\sum_{i=0}^{I}tVar[X^{\infty}_{i\tilde{n}}(t)]}}\right),$

where $Z\sim N(0,1)$. Denote

$\zeta_{i\tilde{n}}(t)=\frac{\tau_{i}\sum_{j=0}^{I}v_{j}r_{j\tilde{n}}\lambda_{j}(t)+\nu_{i\tilde{n}}(t)-\sum_{i=0}^{I}\left(X^{\infty}_{i\tilde{n}}(0)-\mathbb{E}[X^{\infty}_{i\tilde{n}}(0)]+\mathbb{E}[X^{\infty}_{i\tilde{n}}(t)]\right)}{\sqrt{\sum_{i=0}^{I}tm_{i}(t)\left(\delta_{i\tilde{n}}^{2}v_{i}+r_{i\tilde{n}}^{2}\beta_{i}^{2}+v_{i}^{2}r_{i\tilde{n}}^{2}\right)}},$

then, we have
$\mathbb{P}\left(\sum_{i=0}^{I}\hat{X}_{i\tilde{n}}^{\infty}(t)>\tau_{i}\sum_{j=0}^{I}v_{j}r_{j\tilde{n}}\lambda_{j}(t)+\nu_{i\tilde{n}}(t)\right)=1-\Phi(\zeta_{i\tilde{n}}(t))$.
We set $1-\Phi(\zeta_{i\tilde{n}}(t))=\alpha_{i}$ and solve for
$\nu_{i\tilde{n}}(t)$. Thus,

$\displaystyle\hat{\nu}_{i\tilde{n}}(t)$
$\displaystyle=\Phi^{-1}(1-\alpha_{i})\sqrt{\sum_{i=0}^{I}tm_{i}(t)\left(\delta_{i\tilde{n}}^{2}v_{i}+r_{i\tilde{n}}^{2}\beta_{i}^{2}+v_{i}^{2}r_{i\tilde{n}}^{2}\right)}+\sum_{i=0}^{I}\left(X^{\infty}_{i\tilde{n}}(0)-v_{i}r_{i\tilde{n}}m_{i}(0)+v_{i}r_{i\tilde{n}}m_{i}(t)\right)$
$\displaystyle-\tau_{i}\sum_{j=0}^{I}v_{j}r_{j\tilde{n}}\lambda_{j}(t).$ (12)

Define

$x_{\cdot{}\tilde{n}}^{\gamma_{i}}(t)\coloneqq\Phi^{-1}(\gamma_{i})\sqrt{\sum_{i=0}^{I}tm_{i}(t)\left(\delta_{i\tilde{n}}^{2}v_{i}+r_{i\tilde{n}}^{2}\beta_{i}^{2}+v_{i}^{2}r_{i\tilde{n}}^{2}\right)}+\sum_{i=0}^{I}\left(X^{\infty}_{i\tilde{n}}(0)-v_{i}r_{i\tilde{n}}m_{i}(0)+v_{i}r_{i\tilde{n}}m_{i}(t)\right),$

where $1-\alpha_{i}=\gamma_{i}$, which completes the proof. $\square$

### Proof of Proposition 5.6

###### Proof 8.7

Proof Because $\sum_{i=0}^{I}X_{in}^{\infty}(t)$ and
$\sum_{i=0}^{I}X_{i\tilde{n}}^{\infty}(t)$ are independent for any
$n\neq\tilde{n}$ and time $t\in[0,T]$, using the SOL approximation of
$X_{in}^{\infty}(t)$, we require that the following inequality holds

$\mathbb{P}\left(\sum_{i=0}^{I}X_{in}^{\infty}(t)>s_{in}(t)\right)\approx\mathbb{P}\left(\sum_{i=0}^{I}\hat{X}_{in}^{\infty}(t)>s_{in}(t)\right)\leq\epsilon,\quad\forall
i\in\mathcal{I},\quad\forall n\neq\tilde{n}\in\mathcal{N}.$

Similarly to Proposition 5.5, we have that

$\hat{s}_{n}(t)=\Phi^{-1}(1-\epsilon)\sqrt{\sum_{i=0}^{I}tm_{i}(t)\left(\delta_{i\tilde{n}}^{2}v_{i}+r_{i\tilde{n}}^{2}\beta_{i}^{2}+v_{i}^{2}r_{i\tilde{n}}^{2}\right)}+\sum_{i=0}^{I}\left(X^{\infty}_{i\tilde{n}}(0)-v_{i}r_{i\tilde{n}}m_{i}(0)+v_{i}r_{i\tilde{n}}m_{i}(t)\right)=x_{\cdot
n}^{\alpha}(t).$

Notice that when there is sufficient quantity of the dominant resource,
$\hat{s}_{n}(t)$ ensures that non-dominant resources do not increase service
delay. However, at times, when the quantity of the dominant resource is not
sufficient, availability of the other resources does not impact service
quality. Thus, because $\hat{s}_{\tilde{n}}(t)$ is the solution to OPTα, we
have that
$\boldsymbol{\hat{s}}(t)=(\hat{s}_{1}(t),\hat{s}_{2}(t),...,\hat{s}_{n}(t))$
solves OPTϵ and satisfies SLA as long as $\hat{s}_{\tilde{n}}(t)$ does so,
which completes the proof. $\square$