# Two-tiered Online Optimization of Region-wide Datacenter Resource Allocation
via Deep Reinforcement Learning

Chang-Lin Chen, Hanhan Zhou, Jiayu Chen, Mohammad Pedramfar, Vaneet Aggarwal,
Tian Lan, Zheqing Zhu, Chi Zhou, Tim Gasser, Pol Mauri Ruiz, Vijay Menon,
Neeraj Kumar, and Hongbo Dong Chang-Lin Chen, Jiayu Chen, Mohammad Pedramfar,
and Vaneet Aggarwal are with Purdue University, West Lafayette, IN 47907 USA.
E-mail: ({chen3365, chen3686, mpedramf and vaneet}@purdue.edu).Hanhan Zhou and
Tian Lan are with the George Washington University, Washington, DC 20052 USA.
E-mail: ({hanhan,tlan}@gwu.edu).Zheqing Zhu, Chi Zhou, Tim Gasser, Pol Mauri
Ruiz, Vijay Menon, Neeraj Kumar, Hongbo Dong are with Meta, Menlo Park, CA
94025 USA. E-mail:
<EMAIL_ADDRESS>
###### Abstract

This paper addresses the important need for advanced techniques in
continuously allocating workloads on shared infrastructures in data centers, a
problem arising due to the growing popularity and scale of cloud computing. It
particularly emphasizes the scarcity of research ensuring guaranteed capacity
in capacity reservations during large-scale failures. To tackle these issues,
the paper presents scalable solutions for resource management. It builds on
the prior establishment of capacity reservation in cluster management systems
and the two-level resource allocation problem addressed by the Resource
Allowance System (RAS). Recognizing the limitations of Mixed Integer Linear
Programming (MILP) for server assignment in a dynamic environment, this paper
proposes the use of Deep Reinforcement Learning (DRL), which has been
successful in achieving long-term optimal results for time-varying systems. A
novel two-level design that utilizes a DRL-based algorithm is introduced to
solve optimal server-to-reservation assignment, taking into account of fault
tolerance, server movement minimization, and network affinity requirements due
to the impracticality of directly applying DRL algorithms to large-scale
instances with millions of decision variables. This design involves a
reinforcement learning agent making sequential decisions at the higher level,
which are then converted into specific numbers of servers to reserve from the
Main Switch Boards (MSBs). At the lower level, a heuristic approach generates
the server-to-reservation mapping, considering the outcomes of the first
level’s reservations and environmental states. The paper explores the
interconnection of these levels and the benefits of such an approach for
achieving long-term optimal results in the context of large-scale cloud
systems. We further show in the experiment section that our two-level DRL
approach outperforms the MIP solver and heuristic approaches and exhibits
significantly reduced computation time compared to the MIP solver, making it
more efficient for practical implementation. Specifically, our two-level DRL
approach performs $15\%$ better than the MIP solver on minimizing the overall
cost. Also, it uses only $26$ seconds to execute $30$ rounds of decision
making, while the MIP solver needs nearly an hour.

##  I Introduction

Cluster resource managers, as discussed in [1, 2, 3], play a crucial role in
intelligent networks by efficiently distributing computing resources in real-
time. These managers are responsible for placing and managing containers or
virtual machines on servers. As cloud computing continues to gain popularity
and scale, the demand for more advanced techniques to allocate workloads on
shared infrastructures in data centers has grown. Specifically, the number of
servers within a region can surpass millions under a hierarchical
architecture, including datacenters, main switch boards, and racks [4].
Moreover, the arrival rate of workload can be up to a few thousands for a
region. It is challenging to optimally place containers to servers under such
large system.

Recent progress has been made in managing large-scale cluster systems.
Capacity reservation aims to provide reliable capacity guarantees [5, 6]. In
cloud systems, solutions have been developed to ensure capacity guarantee,
considering failures at various levels such as servers, racks, and
infrastructure lifecycle events like OS kernel upgrades [7]. Additionally, the
cluster manager must account for workload constraints, heterogeneous hardware,
and meeting service level objectives (SLOs). A resource allowance system (RAS)
has been proposed in [4], which periodically solves a two-level resource
allocation problem via mixed-integer programming (MIP). However, these
existing work primarily focus on an offline optimization of server assignment
and reservation management by considering system snapshots. They can be
suboptimal for practical cluster systems that require to maximize long-term
performance objectives in an online fashion, subject to various types of
dynamism. While existing work have also considered the use of deep
reinforcement learning (DRL) for optimizing long-term rewards through online
decision-making, it often lacks scalability since training DRL algorithms for
problems with a large action space (i.e., jointly over many control knobs in
large-scale cluster system management) is very difficult.

To this end, this paper proposes a novel two-tiered, scalable approach for
online optimization of cluster system management, which harnesses both DRL for
online decision making and MIP for scalability. Specifically, we consider the
problem of minimizing server movement, resource redundancy at the rack and MSB
levels, and the largest failure domain, under the constraints of capacity
guarantee and network affinity requirements. Motivated by the goal of
achieving optimal results over long-run under dynamism and overcoming the
limitation of RL approach for large scale system, we introduce a two-level
design that utilizes a DRL-based algorithm to address the optimization
problem. In the first level, a DRL agent is trained to make sequential
decisions for each reservation, which are then passed to a novel action
converter proposed in this paper and transformed into specific numbers of
servers to reserve from the available MSBs. The DRL agent’s action affects the
distribution of the servers gotten from the MSBs and the additional resource
given to ensure capacity guarantee. The action converter comprising a softmax
converter and an exponential converter also affects the distribution of
servers from the MSBs and the capacity guarantee. In the second level, we
present a low-level MILP that generates the server-to-reservation mapping,
considering minimizing resource redundancy at the rack level and server
movement. In this way, the DRL agent and the action converter decide the
amount of additional resource supply, the distribution of servers from the
MSBs and the low-level MILP gets the server-to-logical-cluster mapping
considering minimizing the resource supply exceeding rack spread goal and
server movement cost. The above design significantly reduces the number of
variables the DRL agent has to tackle and, thus, makes training the agent more
efficient.

In the experiment, several baselines include a MIP solver which RAS adopts, a
complete RL which each element of its action decides whether a server is
assigned to a reservation, and heuristic approaches are selected for
comparison with our algorithms. The heuristic approaches adopt our two-layer
design and our low-level MILP, and differ in how they determine the amount of
resources to be allocated from the MSBs. We compare all the algorithms on
minimizing the server movement cost, the resource spread cost, and the largest
failure domain. The result shows that our algorithms achieve the lowest
overall cost and subject to no constraint violations. Specifically, our
proposed algorithms perform $10\%$ and $15\%$ better than the uniform baseline
and the MIP solver on overall cost across all the percentile in $30$
experiments and induce the least capacity redundancy.

##  II Related Works

###  II-A Cluster manager scheduling and solvers

Server resource allocation problems are often solved as mathematical
optimization problems [8, 9, 10, 11, 12, 13, 4]. These problems involve
determining the allocation of available resources, such as accelerators,
servers, or network links, to clients, such as jobs, data shards, or traffic
commodities, based on their specific needs. However, these mathematical
optimization methods are frequently computationally expensive [14, 15].
Moreover, integer-linear programs for resource allocation problems can be even
more computationally expensive [16], particularly in large-scale systems where
the number of variables can reach millions (e.g., considering one variable for
each client-resource pair). Consequently, the solution times for these
problems can be long for solvers to generate a response (as a reference, SCS
[17] requires 8 minutes to allocate a cluster with 1000 jobs [18]).
Additionally, it is highly desirable for the system to make decision
considering the future, it is highly desirable for the system to make
decisions considering the future, while classical stochastic optimization
methods developed by math programming community are usually prohibitively more
expensive than deterministic problems [19]. Many existing production
solutions, such as the Gavel job scheduler [20], the Accordion load balancer
[21] for distributed databases, and BwE [11] for traffic engineering, can
experience performance bottlenecks with an increasing number of clients and
resources to allocate. Consequently, directly solving optimization problems
often becomes impractical [14], leading production systems to frequently
employ heuristic or meta-heuristic solutions (as in [12]) that are cheaper and
faster to compute for such problems.

###  II-B Deep Learning and Reinforcement Learning on Cluster Management

The time-varying nature and complex architecture of cloud systems make
resource allocation problems challenging. Deep Reinforcement Learning (DRL)
has demonstrated success in addressing dynamic and complex systems, including
robotics [22, 23, 24, 25], autonomous vehicle coordination [26, 27, 28, 29,
30], communication and network packet delivery [31, 32, 33], including works
through multi-agent reinforcement learning [34, 35, 36, 37]. Consequently, DRL
has also been adopted to solve resource allocation problems in cloud systems.
In the context of cloud systems, RL has been applied to design congestion
control protocols [38] and develop simple resource management systems by
treating the problem as learning packing tasks with multiple resource demands
[39]. Luan et al. [40] proposed a GPU cluster scheduler that leverages DRL for
intelligent locality-aware scheduling of deep learning training jobs. The
authors of [41] applied RL to minimize the makespan of a job set. [42]
proposed the use of actor-critic methods with input-dependent baselines for
distributing computation clusters. [43] proposed a deep Q-learning approach to
solve the CPU-GPU heterogeneous computing scheduling problem based on the
running state and task characteristics of the cluster environment. However, it
is important to note that our work significantly differs from these previous
works and works in Section II-A in the aspect that we focus on optimizing
server-to-logical-cluster assignment, considering failure tolerance, server
movement minimization, and network affinity requirements. Then, with our
solution, placing containers to servers can be more efficient since the
options of each container are refined to servers more likely to satisfy the
requirements.

###  II-C Capacity Reservation

A traditional approach to improving resource allocation efficiency is to group
servers into physical clusters, which reduces the number of candidate servers
for container placement [39, 44]. However, this method often leads to uneven
utilization of clusters, suboptimal server allocation, and challenges in
recovering from data center failures, causing difficulties for service owners
[45]. To address these issues, the authors of [3] introduced a novel approach,
Twine, by organizing servers into logistical clusters and creating a mega
server pool as a backup for each logistical cluster. This design allows for
flexible system management and eliminates the problem of stranded resources in
small physical clusters. Building upon Twine, the Resource Allowance System
(RAS) introduced in [4] further enhances resource allocation efficiency. RAS
separates the server-to-logical-cluster assignment from container placement,
allowing for more optimized resource allocation. It formulates the server
assignment problem, considering factors such as random and correlated hardware
failures, data center maintenance, and heterogeneous hardware. The problem is
then periodically solved using a Mixed Integer Programming (MIP) solver.

This work focuses on achieving long-term optimum for the server-to-logical-
cluster assignment, and any existing approaches can do the container placement
for each logical cluster. Since system management involves a series of
decision makings, optimizing the system considering only the current system
status could not achieve long-term optimum. Therefore, we proposed a two-level
DRL-based algorithm where a DRL agent and our proposed action converter
allocate resources for each logical cluster at the MSB level, and a low-level
MILP solver solves the server-to-logical-cluster mapping based on the results
from the first level.

##  III System Model

This paper considers resource allowance system (RAS) presented in [4]. RAS
abstracts the capacity of heterogeneous hardware and demand of a workload
through the relative resource units (RRUs), considering a workload’s relative
performance on different CPUs, memory, flash, and GPUs. RAS also introduces a
capacity abstraction called reservation. A reservation is a logical cluster of
servers and provides capacity to the workload of a business unit. To ensure
sufficient capacity for the business units, RAS optimizes the mapping between
servers and reservations according to the capacity requirements, random and
correlated failures, datacenter maintenance events, heterogeneous hardware
resources, datacenter topology, and workload requirements. However, the
complicated datacenter structures, capacity scale, and diverse workload
characteristics make efficient, guaranteed capacity provision in a region
challenging.

In Fig. 1, we show a region’s layout overview. The datacenters in a region are
connected by high-bandwidth network links. The main switch boards (MSBs) are
isolated power and network domains that can fail independently. Correlated
failures caused by common physical devices like power breakers and cooling
fans are at the MSB level. Failures that occur at the server or rack level are
considered random failures. We denote $D$ as the set of datacenters, $F$ as
the set of MSBs, $K$ as the set of racks, $B$ as the set of servers, and $L$
as a set of reservations. Considering hardware heterogeneity, the servers can
be categorized into $E$ types. In [4], users in a business unit send capacity
requests to RAS, telling RAS how many additional resources they need. Then,
RAS collects each reservation’s capacity requests and periodically optimizes
the mapping of servers and reservations.

Figure 1: Depiction of dynamic Resource Allowance System considered in this
paper, as well as a brief comparison of our two-tier approach, MIP solver, and
the complete RL approach. The capacity demand of a reservation is an
aggregation of the capacity requests over time.

We aim to optimize the server-to-reservation mapping in a dynamic environment.
In our system, time is divided into multiple time slots with equal duration
$\Delta t$. Let $\mathbb{T}=\\{1,2,\cdots,t,\cdots,\mathcal{T}\\}$ be the set
of time slots. The arrival of capacity requests for reservation $l$ is assumed
to follow the Poisson process with arrival rate $\lambda_{l}$. Let
$\mathbf{T}_{l}=\\{\tau_{l,1},\tau_{l,2},\cdots\\}$ be the set of capacity
requests arriving for reservation $l$. We denote the arrival time of the
capacity request $\tau_{l,i}$ as $t_{l,i}$, its capacity demand as
$\mathbf{c}_{l,i}=(c_{l,i,1},\cdots,c_{l,i,E})$ where $c_{l,i,e}$ is the
demand of $\tau_{l,i}$ for server type $e$, and its expiration time as
$t^{{}^{\prime}}_{l,i}$. The reservations’ demand varies with time as the
capacity requests come and leave. We denote $\mathbf{C}_{l}(t)$ as the total
capacity demand of the reservation $l$ at time $t$, and it is given as

$\mathbf{C}_{l}(t)=\sum_{i\in\Theta_{t}}\mathbf{c}_{l,i}-\sum_{j\in\Theta^{{}^{\prime}}_{t}}\mathbf{c}_{l,j},$
(1)

where $\Theta_{t}=\\{i|t_{l,i}\leq t\\}$ and
$\Theta^{{}^{\prime}}_{t}=\\{i|t^{{}^{\prime}}_{l,i}\leq t\\}$ are the indices
of the capacity requests arriving and expiring right before time $t$,
respectively. Note that $\mathbf{C}_{l}(t)=(C_{l,1}(t),\cdots,C_{l,E}(t))$,
where $C_{l,e}(t)$ is the capacity demand for the type $e$ servers. According
to the operation of RAS, the demand and supply of servers of one type are
independent of another type.

We use an one-hot vector $\mathbf{h}_{b}=(h_{b,1},\cdots,h_{b,E})$ to indicate
which type server $b$ is. Let $U_{b}$ be the RRU of server $b$ and
$x_{b,l}(t)$ be a binary variable equal to $1$ if server $b$ is assigned to
reservation $l$.

#### Server Assignment Constraint

Assuming a server can only be assigned to one reservation at a time, servers
at time slot $t$ should satisfy the following constraint,

$g_{1,b}(t)=1-\sum_{l\in L}x_{b,l}(t)\geq 0,\forall b\in B.$ (2)

The objectives of RAS are to minimize server movement and optimize server
spread across fault domains of various scopes.

#### Server Movement Cost

When RAS assigns a server to another reservation, the overhead of moving
containers running on the server burdens the system. The movement cost of
server $b$ at time $t$ is given as

$o_{1,b}(t)=\sum_{l=1}^{|L|}M_{b}\times\max(0,x_{b,l}(t-1)-x_{b,l}(t)),$ (3)

where $M_{b}$ is the movement cost of server $b$.

#### Outside Rack and MSB Goals

For fault tolerance purposes, RAS typically assign more capacity than the
reservations ask for, and aim to minimizes the amount of capacity that exceeds
the desired proportion of the capacity demand for each reservation and server
type,

$o_{2,k,l,e}(t)=\sum_{G\in\Psi^{K}}\max(0,\sum_{b\in G}(h_{b,e}\times
U_{b}\times x_{b,l}(t))-\alpha^{K}\times{C}_{l,e}(t)),$ (4)

and

$o_{3,f,l,e}(t)=\sum_{G\in\Psi^{F}}\max(0,\sum_{b\in
G}(h_{b,e}\times{U}_{b}\times x_{b,l}(t))-\alpha^{F}\times{C}_{l,e}(t)),$ (5)

where $\Psi^{K}$ and $\Psi^{F}$ are partitions of servers based on racks and
MSBs, and $\alpha^{K}$ and $\alpha^{F}$ are the spread parameters that decide
the threshold for fulfilling the capacity demand within a physical scope.
Making $\alpha^{K}$ and $\alpha^{F}$ small minimizes the effect of correlated
and random failures on a reservation while making them large gives RAS more
flexibility to optimize other objectives.

#### Cost of Largest Failure Domain

To minimize the impact of correlated failures, RAS also minimizes the largest
amount of resources reservation $l$ can get from the MSBs for server type $e$,

$o_{4,l,e}(t)=\max_{G\in\Psi^{F}}\left(\sum_{b\in G}h_{b,e}\times U_{b}\times
x_{b,l}(t)\right),$ (6)

for all $l$ and $e$.

#### Capacity Redundancy

Moreover, to guarantee that the supply of servers of a type is enough to
satisfy the capacity demand even if the MSB that provides the most capacity
fails, the server-to-reservation mapping generated by RAS should satisfy the
following constraint,

$g_{2,l,e}(t)=\sum_{b\in B}(h_{b,e}\times U_{b}\times
x_{b,l}(t))-\max_{G\in\Psi^{F}}\left(\sum_{b\in G}h_{b,e}\times U_{b}\times
x_{b,l}(t)\right)-C_{l,e}(t)\geq 0,$ (7)

for all $l$ and $e$.

#### Network Affinity Requirements

Considering that business units require different extents of network affinity,
RAS uses the following constraint,

$g_{3,d,l,e}(t)=\theta-\left|\frac{\sum_{b\in\Psi^{D}_{d}}(h_{b,e}\times
U_{b}\times x_{b,l}(t))}{{C}_{l,e}(t)}-{\bf A}_{d,l,e}\right|\geq 0,$ (8)

to enforce a reservation’s preference for physical datacenters. The RAS
updates the server-to-reservation assignment at the end of each time slot,
considering the above objectives and constraints. We summarize the notions in
Table V. The following section shows the optimization problem RAS considered
and how it is optimized.

##  IV Problem Formulation

This section presents the problem considered in this work. RAS formulates the
utility function considering the churn rate and allocation spread across MSBs
and racks as,

$\mathcal{U}(t)=\sum_{b\in B}o_{1,b}(t)+\sum_{e=1}^{E}\sum_{l\in
L}\Big{(}\beta\times\big{(}o_{2,l,e}(t)+o_{3,l,e}(t)\big{)}+\kappa\times
o_{4,l,e}(t)\Big{)},$ (9)

where $\beta$ and $\tau$ are the cost of capacity out of spread goals and the
cost of correlated failure buffer capacity.

In this work, we aim to obtain long-term optimal results under dynamism
considering the constraints of capacity guarantee and the network affinity
requirements for each reservation. We define our Dynamic Resource Allowance
System Optimization (DRASO) problem and present it as:

$\displaystyle\text{DRASO}:\min_{x_{b,l}(t),\forall l\in L,b\in B,t\geq 0}$
$\displaystyle\sum_{t=0}^{\infty}\gamma^{t}\mathcal{U}_{(}t)$ (10)
$\displaystyle s.t.\quad\quad$ $\displaystyle g_{1,b,e}(t)=1-\sum_{l\in
L}x_{b,l}(t)\geq 0,\forall b\in B,\text{ and }t\geq 0,$ (11) $\displaystyle
g_{2,l,e}(t)\geq 0,\forall l\in L,\text{ and }t\geq 0,$ (12) $\displaystyle
g_{3,d,l,e}(t)\geq 0,\;\;\forall d\in D,l\in L,\text{ and }t\geq 0,$ (13)

where $\gamma\in[0,1)$ is a discounting factor. The above problem is a mixed
integer programming (MIP) problem. Note that the number of variables in DRASO
can go beyond millions for a region given a time slot $t$. Moreover, the
capacity requests which are aggregated into $C_{l,e}(t)$ and the assignment of
servers can stay in the system and impact the decision-making for the next few
rounds of system optimization. RAS uses a MIP solver to optimize the server-
to-reservation mapping at a region level at a given $t$ and, thus, will not
give an optimal online solution. To achieve long-term optimal results, we
consider adopting Reinforcement Learning (RL), widely adopted to solve
sequential decision-making problems in a dynamic environment. Moreover,
considering the number of variables can be very large, we combine an action
converter and a low-level MILP with DRL to improve efficiency. The following
section will detail each component in our proposed algorithm.

##  V Proposed Framework Design

In this section, we present our proposed framework and hybrid DRL-based
approach to solving DRASO. Our framework comprises an agent, an environment,
an action converter, and a low-level MILP. In RL, an agent is trained to get
long-term optimal results by sequentially evaluating its decisions sent to the
environment representing our target system. The action converter and the low-
level MILP are components of our approach to efficiently solving the problem.
We begin with a comprehensive framework overview in Section V-A and
subsequently detail each component in Sections V-B, V-C, and V-D.

###  V-A Framework

Figure 2: A description of our proposed framework, where the PPO agent makes
decisions for every reservations and then transformed into number of servers
to take from the MSBs by the action converter. Finally, the numbers of servers
to take from the MSBs for all reservations are converted into server-to-
reservation mapping by the low-level MILP.

We start with dividing the system to decide where to apply the DRL algorithm.
We find that the utility function $\mathcal{U}(t)$ in DRASO can be decoupled
based on the server types and the utility function for server type $e$ can be
expressed as

$\mathcal{U}_{e}(t)=\sum_{b\in B_{e}}o_{1,b}(t)+\sum_{l\in
L}\Big{(}\beta\times\big{(}o_{2,l,e}(t)+o_{3,l,e}(t)\big{)}+\tau\times
o_{4,l,e}(t)\Big{)},$ (14)

where $B_{e}$ is the set of type $e$ servers. Moreover, as mentioned in
Section III, demand of a reservation is an aggregation of multiple capacity
requests which ask for multiple types of servers and can arrive and expire. As
shown in Eq. (1), each tuple of the capacity demand of a reservation
represents the demand for a server type, and satisfying each tuple is
independent according to the RAS operation. Therefore, the utility function
and the constraints can be fully decoupled according to the server types, and
the optimization can be done separately for each server type.

The proposed approach for solving the optimization problem DRASO in (10)
consists of two levels. In the first level, the agent is responsible for
making decisions, which are then passed to the action converter to transform
them into the actual number of servers to be allocated from the MSBs. In the
second level, a low-level MILP is employed to determine the server-to-
reservation mapping, taking into account the results obtained from the first
level for all reservations and the current states of the environment.

Fig. 2 shows the basic blocks of our proposed framework and communications
between them. The environment maintains the states of the servers,
reservations, and capacity requests, e.g., the capacity of the reservations,
previous server-to-reservation mapping, etc. These states are updated at every
time slot based on the arrival and expiration of the capacity requests and the
mapping decisions.

Input: {$D$, $F$, $K$, $B$, $L$, $\mathcal{T}$}

Output: $\\{x_{b,l}(t),\forall b\in B,\forall l\in L\\}$

1 $t\leftarrow 1$

2 repeat

3 for  _$e=1$ to $|E|$_ do

4 for  _$l=1$ to $|L|$_ do

5 Send $\mathbf{s}_{l,e}(t)$ to the trained PPO agent and get
$\mathbf{a}_{l,e}(t)$

6 Convert $\mathbf{a}_{l,e}(t)$ to numbers of servers to take by reservation
$l$, $n_{l,e,f}(t),\forall f\in F$, by (19)

7 Get numbers of servers to take from the rack $k$, $m_{l,e,k}(t),\forall k\in
K$, by Algorithm 3

8

9 end for

10 Get server-to-reservation mapping, $\\{x_{b,l}(t),\forall b\in
B_{e},\forall l\in L\\}$ by Algorithm 2 and send it to the environment

11

12 end for

13 $t\leftarrow t+1$

14

15until  _$t==\mathcal{T}$_

Algorithm 1 Proposed algorithm

Input: $\\{m_{l,e,k}(t),\forall l\in L,\forall k\in K\\}$

Output: $\\{x_{b,l}(t),\forall l\in L,\forall b\in B_{e}\\}$

1 Loop through the racks to get the difference between the total requests and
the capacity of the rack,
$u_{e,k}(t)\leftarrow\sum_{r=1}^{R}m_{l,e,k}(t)-|\Psi^{K}_{k}|$

2 Loop through the racks and collect the requests to make the total requests
less than the rack capacities

3 Loop through the collected requests to first reassign them to the racks in
the same MSB they were sent to

4 Assign the requests that cannot be fulfilled in the previous step to any
rack having vacancies

5 Loop through the servers to get server-to-reservation mapping

Algorithm 2 Description of how to get the server-to-reservation mapping for
all the reservations

###  V-B PPO Agent

In this section, we reframe RAS as a Markov Decision Process (MDP) that can be
effectively addressed using readily available RL algorithms. For this study,
we’ve selected PPO [46] as the algorithm because it requires less
hyperparameter tuning to get satisfactory results, as well as it can generate
continuous actions, and it is simple, efficient, and stable. An MDP comprises
key elements such as the state space, action space, and the reward function.
We present their definitions in the context of RAS as follows:

  1. 1.

_State_ : The state variables are defined to reflect the environment status
and thus affect the reward feedback of different actions. We denote
$\mathbf{s}_{l,e}(t)$ as the state variable sent to the agent to decide for
the reservation $l$ and the server type $e$. The state elements include the
index of the reservation, the usage of the MSBs at the current time slot, the
capacity demand of the reservation $l$, the number of servers in each MSB
previously assigned to the reservation $l$, the amount of demand that will
expire in the future $h$ slots, and the amount of demand that will arrive in
the future $h$ time slots. In addition, the states include the mean of the
other reservations’ capacity demand, the number of previously assigned servers
from the MSBs, to-be expired demand in the future $h$ time slots, and demand
arrivals in the future $h$ time steps. The state elements are combined in one
vector $\mathbf{s}_{l}(t)$.

  2. 2.

_Action_ : We denote the the agent’s output for reservation $l$ and server
type $e$ as $\mathbf{a}_{l,e}(t)=(a_{l,e,1}(t)$, $\cdots$, $a_{l,e,F}(t)$,
$a_{l,e,F+1}(t))$ where $\mathbf{a}_{l,e}(t)\in\mathbb{R}^{F+1}$.
$\mathbf{a}_{l,e}(t)$ will be sent to the action converter. At the action
converter, $a_{l,e,1}(t)$, $\cdots$, $a_{l,e,F}(t)$ will first be converted to
the fraction of capacity demand to take from the MSBs, and $a_{l,e,F+1}(t)$
will be converted to an over-provision factor. Then, the action converter will
further derive the numbers of servers of type $e$ to take from the MSBs.
$a_{l,e,1}(t)$, $\cdots$, $a_{l,e,F}(t)$ affect whether the servers taken are
evenly from the MSBs. $a_{l,e,F+1}(t)$ determines the additional servers for
the failure buffer. The conversion is detailed in Section V-C.

  3. 3.

_Reward_ : After converting a reservation’s action into a server-to-
reservation mapping, the reward for the reservation’s action is determined by
a weighted combination of the equations in the objective of the optimization
problem in (10) plus penalties for violation of the constraints. The reward
for reservation $l$ at time slot $t$ is given by

$\displaystyle r_{l,e}(t)=$ $\displaystyle
r(s_{l,e}(t),a_{l,e}(t))=w_{1}\times\sum_{b\in
B_{e}}o_{1,b}(t)+w_{2}\times\sum_{k\in K}o_{2,k,l,e}(t)+w_{3}\times\sum_{f\in
F}o_{3,f,l,e}(t)+$ (15) $\displaystyle w_{4}\times
o_{4,l,e}(t)+p_{2,l,e}\times\mathbf{1}\\{g_{2,l,e}(t)<0\\}+\sum_{d\in
D}p_{3,d,l,e}\times\mathbf{1}\\{g_{3,d,l,e}(t)<0\\}$

where $w_{1}$, $w_{2}$, $w_{3}$, and $w_{4}$ are the weights for the four
equations related to reservation $l$ in the objective, $p_{2}$ and $p_{3,d}$
are penalties for constraint violation, and $\mathbf{1}\\{\cdot\\}$ is an
indicator function equal to $1$ if the statement in the bracket holds. The
penalty for violating constraints $g_{1,b}(t)$ is not included in the reward
function because the proposed low-level MILP (introduced later) takes care of
it. To enhance training efficiency, a progressive training approach is
adopted. The agent is initially trained using only the first term of the
reward function. Once the agent’s performance converges, the next term is
added, and the agent is retrained. This process is repeated incrementally
until the agent is trained with the complete reward function. By gradually
introducing the reward components, the training process becomes more
efficient, allowing the agent to focus on learning each term sequentially.
This approach helps in achieving convergence and improving the overall
training performance.

The PPO agent takes actions sequentially for each reservation and server type
according to the environment’s state and learns from the records of actions,
states, and rewards. The order of the decision-makings for the reservations
matters in our design. The later reservations might not get enough resource to
satisfy its demand. To mitigate the effect, we introduce the reservation index
and the mean of the other reservations’ states into the state variables, so
that the agent is aware of which reservation it is making decision for and can
take decisions made for other reservations into account [34]. On the contrary,
the optimization of server assignment for the server types is independent of
each other, so we propose the following two training methods.

  * •

Single agent: We train a single agent for all the server types. To achieve
this, we add the server type to the states. Following the concept of
contextual MDP, we then train the agent to solve the optimization problem for
a server type and move on to the next one after finishing the current training
[47].

  * •

Parallel agents: We train $|E|$ agents, and each is for a server type.

The Parallel agents enables faster training by parallelizing the training
workload to multiple machines. We summarize the training of the PPO agent in
Algorithm 5 in Appendix A.

###  V-C Action Converter

In our system design, the PPO agent’s output undergoes a sequential procedure
involving our proposed action converter and low-level MILP to generate the
requisite server-to-reservation mapping.

The purpose of the action converter is to determine the number of servers a
reservation should get from every MSB given the actions from the PPO agent.
The conversion involves converting the action to fractions of capacity to take
from the MSBs and an over-provision factor and then getting the number of
servers to take from the MSBs. We pass $(a_{l,e,1}(t)$, $\cdots$,
$a_{l,e,F}(t))$, to the softmax function to get the
$(a^{{}^{\prime}}_{l,e,1}(t)$, $\cdots$, $a^{{}^{\prime}}_{l,e,F}(t))$ as
follows

$a^{{}^{\prime}}_{l,e,f}(t)=\frac{e^{\zeta a_{l,e,f}(t)}}{\sum_{f\in
F}e^{\zeta a_{l,e,f}(t)}},\forall f\in F,$ (16)

where $\zeta$ is the temperature parameter that affects the uniformity of
$(a^{{}^{\prime}}_{l,e,1}(t)$, $\cdots$, $a^{{}^{\prime}}_{l,e,F}(t))$. We get
the over-provision factor, $z_{l,e}(t)$, by $a_{l,e,F+1}$ and the following
equation,

$z_{l,e}(t)=\omega^{a_{l,e,F+1}(t)},$ (17)

where $\omega$ is manually set. The amount of type $e$ resource the
reservation $l$ should get from the MSB $f$ is given as:

$y_{l,e,f}(t)=a^{{}^{\prime}}_{l,e,f}(t)\times(1+z_{l,e}(t))\times
C_{l,e}(t).$ (18)

Then, the number of type $e$ servers that the reservation $l$ gets from the
MSB $f$ should be:

$n_{l,e,f}(t)=y_{l,e,f}(t)*\frac{|B_{e}|}{\sum_{b\in B_{e}}U_{b,l}}.$ (19)

By (16), (17), (18) and (19), the action converter gets the number of servers
a reservation should get from the MSBs.

###  V-D Integration with the Low-level MILP

With the results from the action converter, our low-level MILP derives the
server-to-reservation mapping. Since the resource spread across the MSBs and
the maximum correlated failure are handled by the PPO agent, our low-level
MILP is designed to minimize the movement cost of servers in (11) and the
resource spread across the racks in (4). The two essential steps in our low-
level MILP to get the server-to-reservation mapping are as follows:

  1. 1.

Given the number of servers the reservation $l$ should get from the MSB $f$,
$n_{l,e,f}(t)$, the reservation $l$ gets an even number of servers from the
racks in the MSB $f$. We use Algorithm 3 to decide how many servers the
reservation $l$ should get from all the racks.

  2. 2.

Based on the number of servers every reservation should take from the MSBs, we
can get the server-to-reservation mapping. The detailed steps are shown in
Algorithm 2, and the corresponding pseudocode can be found in Algorithm 4 in
A.

##  VI Simulation

We evaluate the performance of our proposed algorithm in this section. We
begin with the system setup in Section VI-A, clarify the baselines in Section
VI-B, and show the performance comparison in Section VI-C.

###  VI-A System Setup

Table I delineates the key parameters of our Resource Allowance System (RAS).
The counts of datacenters, MSBs, racks, reservations, servers, and server
types are symbolized as $|D|$, $|F|$, $|K|$, $|L|$, $|B|$, and $|E|$,
respectively. These symbols illustrate the regional datacenter topology
depicted in Fig. 1. $U_{b}$, representing the RRU of server $b$, is unified
since most of the servers of the same server type are homogeneous. This
datacenter setup is designed by domain experts among the authors,
approximating a real-life scenario. For one experiment/episode, we run the
system for $30$ steps. The other parameters in Table I are related to the
optimization problem, of which the definitions are provided in Table V.

TABLE I: Parameter Setup Parameter | $|D|$ | $|F|$ | $|K|$ | $|L|$ | $|B|$ | $|E|$ | $U_{b}$ | $T$ | $\alpha^{F}$ | $\alpha^{K}$ | $\kappa$ | $\beta$ | $M_{b}$ | $A_{l,d}$ | $\theta$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Value | 3 | 15 | 75 | 20 | 1000 | 10 | 150 | 30 | 1/15 | 1/75 | 1 | 1 | 5 | 1 | 2

The regional datacenter comprises $1000$ servers, differentiated into $10$
types based on count, mean request arrival rate, and capacity combination
type. A comprehensive summary of this heterogenous simulation setting,
designed by domain experts, is provided in Table II.

TABLE II: Summary of the Heterogeneous Hardware Server Type | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---|---
Count | 405 | 45 | 30 | 15 | 300 | 15 | 30 | 15 | 45 | 100
Mean Request Arrival Rate | 2 | 0.6 | 0.6 | 0.2 | 1.8 | 0.2 | 0.6 | 0.2 | 0.6 | 1.2
Capacity Combination Type | 5 | 2 | 1 | 0 | 4 | 1 | 2 | 1 | 2 | 3

There are in total $6$ types of capacity combinations. Each type corresponds
to a unique amalgamation of demands varying in size or duration, which is
summarized in Table III. The hardwares are evenly distributed in their higher
scopes _e.g.,_ , the racks have the same number of servers, and the MSBs have
the same number of racks. We build a simulator in Python based on the
described settings.

TABLE III: Summary of Different Capacity Requests Capacity Combination Type | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---
Demands | (150) | (300, 150) | (300, 150) | (300, 150) | (450, 300) | (900, 450, 150)
Percentage | (1.00) | (0.16, 0.84) | (0.25, 0.75) | (0.33, 0.67) | (0.33, 0.67) | (0.16, 0.33, 0.51)
Duration | (15) | (10, 15) | (10, 15) | (10, 15) | (10, 15) | (10, 15, 20)

###  VI-B Baseline Algorithms

This section describes the baseline algorithms. We include the MIP solver,
which RAS currently adopts, a complete RL agent, and some two-layer heuristic
methods. The descriptions of the baseline algorithms are given as follows.

  * •

MIP solver: It is implemented by the Python-MIP package [48]. The MIP solver
is configured to spend at most $10$ seconds to solve a problem.

  * •

Complete RL/vanilla: The action space of the agent is equal to the set of
variables in (10), where each output of the agent is then converted to $0$ or
$1$ to represent $x_{b,l}(t)$. We use the PPO algorithm to train the agent.

  * •

Random: It uniformly samples $|F|$ weights and an over-provision factor from
the range $[-1,1]$. Then, the $|F|+1$ values are sent to the action converter
and our low-level MILP to get the server-to-reservation mapping.

  * •

Uniform: Let the fractions of capacity demand to take from the MSBs be
$\frac{1}{|F|-1}$. The choice of the fraction will make (7) satisfied. The
fractions are sent to the action converter and our low-level MILP to obtain
the server-to-reservation mapping.

  * •

Proportional: It first generates $F$ scalars, $\delta_{1}$, $\cdots$,
$\delta_{F}$, proportional to the available resource of the MSBs. Assume that
$(\delta_{1}$, $\cdots$, $\delta_{F})$ are in the descending order and they
sum to one. Then, multiply all the scalars by $\frac{1}{1-\delta_{1}}$ to
satisfy (7). Finally, the scalars are sent to the action converter and our
low-level MILP to get the server-to-reservation mapping.

###  VI-C Main Results

We compare the performance of our proposed algorithms with the baseline
algorithms in this section. The convergence rate of our proposed algorithm is
presented in Figure 3. In Figures 4, 5, and 6, we compare the baselines and
our algorithm on the overall performance, resulting in server movement cost,
spread, size of the largest fault domain, and induced capacity redundancy. We
tested the performance as the system scale increases in Table IV. Finally, we
discuss the relationship between the terms in the objective function in Figure
7.

We first show the convergence rate in terms of the number of episodes required
to reach convergence. In Figures 3(a) and 3(b), we train the agent for server
type $1$ for $400$ episodes. Figure 3(a) shows the variation of the reward and
its moving average. We observe that the moving average converges after $100$
episodes. Similarly, in Figure 3(b), we observe that there is little variation
of the moving average of the objective value and constraint $6$ after $100$
episodes. Training plots for the rest server types are omitted for the sake of
repetition.

(a)

(b)

Figure 3: Algorithm convergence simulations for the server type $1$. Both our
proposed parallel agents and our proposed single agent algorithms show similar
convergence pattern. The result shows that the moving average of the reward,
the objective value, the capacity redundancy constraint, and the network
affinity constraint of our proposed algorithms converge after $100$ episodes.

In Figures 4, 5, 6, we compare the overall performance, key metrics, and the
resource utilization of the algorithms based on $30$ episodes of the
performance data. Two kinds of plots are used to show the performance
difference. The first kind compares the empirical cumulative distribution
function (CDF) of a metric, where the horizontal axis represents the metric
value and the vertical axis represents the percentile. The second kind
compares the performance induced at each time step within an episode, where
the horizontal axis represents the time steps and the vertical axis represents
the metric values.

In Figure 4(a) and 4(b), we compare the empirical CDF of the resulting
objective value. Because the complete RL and the random baseline performs much
worse than the other algorithms, we divide the comparison into two figures for
better comparison. A lower objective value is desired as it indicates better
performance. The horizontal axis represents the objective value accumulated in
an episode, while the vertical axis represents the percentile of an episode’s
accumulated objective value among all the episodes’ objective values generated
by a specific algorithm. The overall performance of the two proposed
algorithms is very close, indicating that using a single agent can achieve
similar performance to using parallel agents. The uniform and proportional
baselines show similar performance. This can be attributed to the fact that
the initial outputs of the proportional baseline are always uniform. The
slight differences in their outputs may not significantly affect the generated
server-to-reservation mappings by the action converter. The proposed
algorithms consistently achieve the lowest objective values across all
percentiles, outperforming the baselines. This demonstrates the effectiveness
of the proposed algorithms in optimizing the objective function. The medians
of our proposed algorithms, the uniform and proportional baselines, and the
MIP solver are $38000$, $42000$, and $44000$, respectively, to name a few. The
objective value obtained by complete RL ranges from $90000$ to $130000$, which
indicates that the training of the complete RL converges at a suboptimal point
and verifies that training an RL agent directly for a large-scale system is
impractical. Since the complete RL and the random baseline performs much worse
than the others, we omit their performance comparison with the proposed
algorithms for the following content.

In Figure 4(c), the variation of the objective value within an episode is
depicted, providing a different perspective for comparing performance. The
horizontal axis represents the time steps within an episode, while the
vertical axis displays the corresponding objective value. As the time steps
within an episode increase, the performance difference between the proposed
algorithms and the baseline algorithms becomes more pronounced. This suggests
that the proposed algorithms exhibit better optimization capabilities and
consistently improve the objective value over time compared to the baseline
algorithms. Figure 4(c) supports the conclusion made in Figure 4(a),
reinforcing the finding that the proposed algorithms outperform the baselines
in terms of objective value optimization. We can conclude that our proposed
algorithm performs better than the proportional baseline and the MIP by $10\%$
and $15\%$, respectively, at the median of the experiments.

(a) Objective Value Empirical CDF

(b) Objective Value Empirical CDF

(c) Objective Value Variation

Figure 4: Performance comparison with regards to the objective value
($\mathcal{U}(t)$). Lower objective value and outside MSB goal are desired.
The results shows that our proposed algorithms outperform the other algorithms
in the sense that (a) (b) they result in the lowest objective value across all
the percentile, and (c) their average remain the lowest within an episode.

Figure 5(a) illustrates that both the uniform and proportional baselines
result in the lowest server movement cost. Additionally, the two proposed
algorithms outperform the MIP solver significantly in terms of server movement
cost. The results of the uniform and proportional baselines imply that
uniformly getting resources for all the scopes renders the least server
movement cost. However, the objective function of the problem is primarily
influenced by the resource spread components as demonstrated in Figures 5(b)
and 4. Figure 5(c) shows that all the algorithms maintain the largest failure
domain equally well. It implies that these algorithms are comparable in terms
of their ability to handle failures effectively.

(a) Server Movement Cost

(b) Outside Rack Spread Goal

(c) Largest MSB

Figure 5: The empirical CDF comparison concludes that (a) the proportional and
uniform baselines induce the least server movement cost, (b) our proposed
algorithms use the least resource outside rack spread goal, and (c) all the
algorithms perform equally well in maintaining the size of the largest MSB.

We can also observe that our proposed algorithms use the least extra resource
to satisfy the demand from Figures 6(a) and 6(b). The results in Figures 6(a)
and 6(b) accord with what we deduce from Figure 5(b). Besides the overall
induced capacity redundancy, we also show the capacity redundancy violation in
Figure 6(c) which cannot be observed from Figures 6(a) and 6(b). Figure 6(c)
shows that the proportional and uniform baselines violates the capacity
redundancy constraint starting at step $5$ till the end. Note that we design
the outputs of the uniform and proportional to satisfy the capacity redundancy
constraint. We deduce that the violation might be due to competition of the
servers when the demand increases. In our low-level MILP, server requests
which cannot be fulfilled because of rack capacity limit will be redistribute
to other racks, and our low-level MILP does not guarantee constraint
satisfication when redistribution has to be made. We can also conclude that
our proposed agent can learn to avoid constraint violation.

(a) Capacity Redundancy

(b) Capacity Redundancy Variation

(c) Redundancy Violation

Figure 6: We conclude that the resource utilization of our proposed algorithms
is the most efficient and reliable by (a) their capacity redundancy is the
lowest across the percentile, (b) their average capacity redundancy is the
lowest for all time steps in an episode, and (c) they do not violate the
redundancy constraint.

Table IV compares the scalability of the proposed single agent algorithm with
the MIP solver based on testing time and training time, measured on the same
machine with $32$ CPU cores and $64$ GB RAM. The table includes results for
varying numbers of servers, ranging from $500$ to $10,000$. Testing time
represents the time required to finish one episode, _i.e.,_ , $30$ consecutive
decision-makings. On the other hand, the training time is the expected time
for training our RL agent for $1000$ episodes. The testing time in Table IV
are averaged over $30$ episodes, while the training time represents the time
required to train the agent for $1000$ episodes. Our proposed algorithm shows
manageable training times even with a system containing $10000$ servers.
Moreover, the proposed algorithm exhibits significantly lower testing times
compared to the MIP solver, highlighting greater flexibility in system
management. Though the training time may take hours or even days for very
large system, most of the training needs can be anticipated and planned in
advance. Moreover, updating the RL model is simple and convenient. Besides the
training and testing time, our proposed algorithm also outperforms the MIP as
indicated by both the table and the previous figures. Note that the training
time for our proposed parallel agents algorithm can be further reduced by
training each model on different devices simultaneously. The training time of
the proposed parallel agents can be $14$, $36$, $56$ minutes for systems with
$500$, $1000$, and $10000$ servers, respectively.

TABLE IV: Summary of the algorithm scalability (Algorithm, $|B|$) | (MIP, 500) | (MIP, 1000) | (Proposed, 500) | (Proposed, 1000) | (Proposed, 10000)
---|---|---|---|---|---
Testing time (sec) | 2329 | 3510 | 10 | 26 | 39
Training time (min) | N/A | N/A | 53 | 142 | 224
Performance $\mathcal{U}(t)$ | 25746 | 44213 | 21128 | 37795 | 1221747

In Figures 7, we examine the trade-off between metrics in the optimization
problem as the server movement cost ($M_{b}$) increases. Since the single
agent algorithm and parallel agents algorithm have close performance, we test
only the performance of the single agent. We plot Figure 7 based on $5$
episodes of performance data obtained at different server movement costs: $5$,
$10$, $25$, and $50$. Figure 7(a) indicates that the total number of server
movement decreases as the server movement cost increases. We also observe
slight rise on the resource spread and capacity redundancy as shown in Figures
7(a) and 7(b). This increase might be due to the utilization of additional
servers to satisfy incoming demands and avoid the high server movement cost.

(a)

(b)

Figure 7: The increase of the server movement cost helps further minimize the
server movements, but induces higher capacity redundancy and worse resource
spread.

##  VII Conclusion

This work considers optimizing server-to-reservation mapping for a dynamic
reservation allowance system (RAS) constituting datacenters, MSBs, racks, and
heterogeneous servers. At the first level, a DRL agent and an action converter
collaboratively determine the resource supply for each reservation
sequentially at the MSB level. The outputs from this level are then passed to
the second level, where a low-level MILP is employed to solve the server-to-
reservation mapping problem based on the results obtained from the first
level. To handle the heterogeneity of the servers, the optimization problem is
initially decoupled according to the different server types. This allows for
independent optimization for each server type, simplifying the overall
problem. Two variants of the proposed algorithm are presented: one utilizing a
single DRL agent and the other employing parallel agents for the DRL part.
Both variants are evaluated and compared with other algorithms, including
heuristic approaches and the Mixed Integer Programming (MIP) solver utilized
in the RAS. Simulation results demonstrate that the proposed algorithms
outperform the other methods in terms of performance. Additionally, the
proposed algorithms exhibit significantly reduced computation time compared to
the MIP solver, making them more efficient for practical implementation.
Future steps for this work include extending the optimization problem to
incorporate practical failure arrivals and addressing containers’ placement on
servers to satisfy specific service requirements. These extensions would
further enhance the practical applicability and effectiveness of the proposed
algorithms in real-world scenarios.

## References

  * [1] A. Verma, L. Pedrosa, M. R. Korupolu, D. Oppenheimer, E. Tune, and J. Wilkes, “Large-scale cluster management at Google with Borg,” in _Proceedings of the European Conference on Computer Systems (EuroSys)_ , Bordeaux, France, 2015.
  * [2] B. Hindman, A. Konwinski, M. Zaharia, A. Ghodsi, A. D. Joseph, R. Katz, S. Shenker, and I. Stoica, “Mesos: A platform for Fine-Grained resource sharing in the data center,” in _8th USENIX Symposium on Networked Systems Design and Implementation (NSDI 11)_. Boston, MA: USENIX Association, Mar. 2011.
  * [3] C. Tang, K. Yu, K. Veeraraghavan, J. Kaldor, S. Michelson, T. Kooburat, A. Anbudurai, M. Clark, K. Gogia, L. Cheng _et al._ , “Twine: A unified cluster management system for shared infrastructure,” in _Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation_ , 2020, pp. 787–803.
  * [4] A. Newell, D. Skarlatos, J. Fan, P. Kumar, M. Khutornenko, M. Pundir, Y. Zhang, M. Zhang, Y. Liu, L. Le _et al._ , “Ras: continuously optimized region-wide datacenter resource allocation,” in _Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles_ , 2021, pp. 505–520.
  * [5] AWS. (2023) On-demand capacity reservations. [Online]. Available: https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/ec2-capacity-reservations.html
  * [6] Google. (2023) Reservations of compute engine zonal resources. [Online]. Available: https://cloud.google.com/compute/docs/instances/reservations-overview
  * [7] A. Verbitski, A. Gupta, D. Saha, M. Brahmadesam, K. Gupta, R. Mittal, S. Krishnamurthy, S. Maurice, T. Kharatishvili, and X. Bao, “Amazon aurora: Design considerations for high throughput cloud-native relational databases,” in _SIGMOD 2017_ , 2017.
  * [8] F. Abuzaid, S. Kandula, B. Arzani, I. Menache, M. Zaharia, and P. Bailis, “Contracting wide-area network topologies to solve flow problems quickly.” in _NSDI_ , 2021, pp. 175–200.
  * [9] Y. Xiang, T. Lan, V. Aggarwal, and Y.-F. R. Chen, “Joint latency and cost optimization for erasure-coded data center storage,” _IEEE/ACM Transactions on Networking_ , vol. 24, no. 4, pp. 2443–2457, 2015.
  * [10] I. Gog, M. Schwarzkopf, A. Gleave, R. N. Watson, and S. Hand, “Firmament: Fast, centralized cluster scheduling at scale,” in _12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16)_ , 2016, pp. 99–115.
  * [11] A. Kumar, S. Jain, U. Naik, A. Raghuraman, N. Kasinadhuni, E. C. Zermeno, C. S. Gunn, J. Ai, B. Carlin, M. Amarandei-Stavila _et al._ , “Bwe: Flexible, hierarchical bandwidth allocation for wan distributed computing,” in _Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication_ , 2015, pp. 1–14.
  * [12] F. Stefanello, V. Aggarwal, L. S. Buriol, and M. G. Resende, “Hybrid algorithms for placement of virtual machines across geo-separated data centers,” _Journal of Combinatorial Optimization_ , vol. 38, pp. 748–793, 2019.
  * [13] X. Li and K. L. Yeung, “Traffic engineering in segment routing networks using milp,” _IEEE Transactions on Network and Service Management_ , vol. 17, no. 3, pp. 1941–1953, 2020.
  * [14] D. Narayanan, F. Kazhamiaka, F. Abuzaid, P. Kraft, A. Agrawal, S. Kandula, S. Boyd, and M. Zaharia, “Solving large-scale granular resource allocation problems efficiently with pop,” in _Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles_ , 2021, pp. 521–537.
  * [15] Y. Mei, H. Zhou, and T. Lan, “Remix: Regret minimization for monotonic value function factorization in multiagent reinforcement learning,” _arXiv preprint arXiv:2302.05593_ , 2023.
  * [16] Y. T. Lee and A. Sidford, “Efficient inverse maintenance and faster algorithms for linear programming,” in _2015 IEEE 56th Annual Symposium on Foundations of Computer Science_. IEEE, 2015, pp. 230–249.
  * [17] B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd, “SCS: Splitting conic solver, version 3.2.3,” https://github.com/cvxgrp/scs, Nov. 2022.
  * [18] B. O’donoghue, E. Chu, N. Parikh, and S. Boyd, “Conic optimization via operator splitting and homogeneous self-dual embedding,” _Journal of Optimization Theory and Applications_ , vol. 169, pp. 1042–1068, 2016.
  * [19] A. Shapiro and A. Philpott, “A tutorial on stochastic programming,” _Manuscript. Available at www2.isye.gatech.edu/ashapiro/publications.html_ , vol. 17, 2007.
  * [20] D. Narayanan, K. Santhanam, F. Kazhamiaka, A. Phanishayee, and M. Zaharia, “Heterogeneity-aware cluster scheduling policies for deep learning workloads,” in _Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation_ , 2020, pp. 481–498.
  * [21] M. Serafini, E. Mansour, A. Aboulnaga, K. Salem, T. Rafiq, and U. F. Minhas, “Accordion: Elastic scalability for database systems supporting distributed transactions,” _Proceedings of the VLDB Endowment_ , vol. 7, no. 12, pp. 1035–1046, 2014.
  * [22] H. Nguyen and H. La, “Review of deep reinforcement learning for robot manipulation,” in _IEEE International Conference on Robotic Computing (IRC)_ , 2019, pp. 590–595.
  * [23] J. Chen, T. Lan, and V. Aggarwal, “Option-aware adversarial inverse reinforcement learning for robotic control.” IEEE, 2023.
  * [24] J. Chen, D. Tamboli, T. Lan, and V. Aggarwal, “Multi-task hierarchical adversarial inverse reinforcement learning,” 2023.
  * [25] H. Zhou, T. Lan, and V. Aggarwal, “Value functions factorization with latent state information sharing in decentralized multi-agent policy gradients,” _arXiv preprint arXiv:2201.01247_ , 2022.
  * [26] Y. Hu, A. Nakhaei, M. Tomizuka, and K. Fujimura, “Interaction-aware decision making with adaptive strategies under merging scenarios,” in _2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2019, pp. 151–158.
  * [27] A. O. Al-Abbasi, A. Ghosh, and V. Aggarwal, “Deeppool: Distributed model-free algorithm for ride-sharing using deep reinforcement learning,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 20, no. 12, pp. 4714–4727, 2019.
  * [28] X. Luo, X. Ma, M. Munden, Y.-J. Wu, and Y. Jiang, “A multisource data approach for estimating vehicle queue length at metered on-ramps,” _Journal of Transportation Engineering, Part A: Systems_ , vol. 148, no. 2, p. 04021117, 2022\.
  * [29] X. Ma, “Traffic performance evaluation using statistical and machine learning methods,” Ph.D. dissertation, The University of Arizona, 2022.
  * [30] J. Chen, A. K. Umrawal, T. Lan, and V. Aggarwal, “Deepfreight: A model-free deep-reinforcement-learning-based algorithm for multi-transfer freight delivery,” in _Proceedings of the International Conference on Automated Planning and Scheduling_ , vol. 31, 2021, pp. 510–518.
  * [31] D. Ye, M. Zhang, and Y. Yang, “A multi-agent framework for packet routing in wireless sensor networks,” _sensors_ , vol. 15, no. 5, pp. 10 026–10 047, 2015.
  * [32] N. Geng, Q. Bai, C. Liu, T. Lan, V. Aggarwal, Y. Yang, and M. Xu, “A reinforcement learning framework for vehicular network routing under peak and average constraints,” _IEEE Transactions on Vehicular Technology_ , 2023\.
  * [33] G. Gonzalez, M. Balakuntala, M. Agarwal, T. Low, B. Knoth, A. W. Kirkpatrick, J. McKee, G. Hager, V. Aggarwal, Y. Xue _et al._ , “Asap: A semi-autonomous precise system for telesurgery during communication delays,” _IEEE Transactions on Medical Robotics and Bionics_ , vol. 5, no. 1, pp. 66–78, 2023.
  * [34] W. U. Mondal, V. Aggarwal, and S. V. Ukkusuri, “Can mean field control (mfc) approximate cooperative multi agent reinforcement learning (marl) with non-uniform interaction?” in _Uncertainty in Artificial Intelligence_. PMLR, 2022, pp. 1371–1380.
  * [35] H. Zhou, T. Lan, and V. Aggarwal, “Pac: Assisted value factorization with counterfactual predictions in multi-agent reinforcement learning,” in _Advances in Neural Information Processing Systems_ , vol. 35. Curran Associates, Inc., 2022, pp. 15 757–15 769.
  * [36] D. S. Gadiraju, V. Lalitha, and V. Aggarwal, “An optimization framework based on deep reinforcement learning approaches for prism blockchain,” _IEEE Transactions on Services Computing_ , 2023.
  * [37] Y. Mei, H. Zhou, T. Lan, G. Venkataramani, and P. Wei, “Mac-po: Multi-agent experience replay via collective priority optimization,” in _Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems_ , ser. AAMAS ’23. International Foundation for Autonomous Agents and Multiagent Systems, 2023, p. 466–475.
  * [38] K. Winstein and H. Balakrishnan, “Tcp ex machina: Computer-generated congestion control,” _ACM SIGCOMM Computer Communication Review_ , vol. 43, no. 4, pp. 123–134, 2013.
  * [39] H. Mao, M. Alizadeh, I. Menache, and S. Kandula, “Resource management with deep reinforcement learning,” in _Proceedings of the 15th ACM workshop on hot topics in networks_ , 2016, pp. 50–56.
  * [40] Y. Luan, X. Chen, H. Zhao, Z. Yang, and Y. Dai, “Sched2: Scheduling deep learning training via deep reinforcement learning,” in _2019 IEEE Global Communications Conference (GLOBECOM)_. IEEE, 2019, pp. 1–7.
  * [41] F. Li and B. Hu, “Deepjs: Job scheduling based on deep reinforcement learning in cloud data center,” in _Proceedings of the 4th International Conference on Big Data and Computing_ , 2019, pp. 48–53.
  * [42] H. Mao, M. Schwarzkopf, S. B. Venkatakrishnan, Z. Meng, and M. Alizadeh, “Learning scheduling algorithms for data processing clusters,” in _Proceedings of the ACM special interest group on data communication_ , 2019, pp. 270–288.
  * [43] H. Zhang, X. Geng, and H. Ma, “Learning-driven interference-aware workload parallelization for streaming applications in heterogeneous cluster,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 32, no. 1, pp. 1–15, 2020.
  * [44] C.-L. Chen, C. G. Brinton, and V. Aggarwal, “Latency minimization for mobile edge computing networks,” _IEEE Transactions on Mobile Computing_ , vol. 22, no. 4, pp. 2233–2247, 2023.
  * [45] S. Swarup, E. M. Shakshuki, and A. Yasar, “Task scheduling in cloud using deep reinforcement learning,” _Procedia Computer Science_ , vol. 184, pp. 42–51, 2021.
  * [46] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” _CoRR_ , vol. abs/1707.06347, 2017.
  * [47] A. Hallak, D. Di Castro, and S. Mannor, “Contextual markov decision processes,” _arXiv preprint arXiv:1502.02259_ , 2015.
  * [48] H. G. S. Túlio A. M. Toffolo. (2019) Python-mip. [Online]. Available: https://www.python-mip.com

###  -A NOMENCLATURE

Table V. below summarizes the common notations used in this paper.

TABLE V: Summary of Optimization Problem Parameters Notation | Description
---|---
$D$ | Set of datacenters
$F$ | Set of MSBs
$K$ | Set of racks
$B$ | Set of servers
$L$ | Set of all reservations
$E$ | Set of server types
$x_{b,l}(t)$ |  Assignment variable which is 1 if server $b$ is assigned to reservation $l$ and 0 otherwise
$\alpha_{b}(t)$ | The reservation that server $b$ is assigned to at time slot $t$
$M_{b}$ | Movement cost of server $b$
$\kappa$ | Cost of each correlated-failure-buffer server
$\beta$ | Cost of each server outside of spread goals
$\alpha^{K,F}$ | Proportional limit of reservation of spread in $K$ (rack) or $F$ (MSB fault domain)
$U_{b}$ | RRU of server $b$
$\mathbf{C}_{l}(t)$ | Capacity desired for reservation $l$
$\Psi^{K,F,D}$ | Partition of servers based on $K$ (rack), $D$ (datacenter), or $F$ (MSB fault domain)
$\Psi^{K}_{k}$, $\Psi^{F}_{f}$, $\Psi^{D}_{d}$ | Servers in rack $k$, in MSB $f$, or in datacenter $d$
$\Phi^{F}_{f}$ | Racks in MSB $F$ (MSB fault domain)
$A_{d,l,e}$ | Affinity of reservation $l$ to a datacenter regarding server type $e$

##  Appendix A Algorithms

Input: $r$, $\\{n_{l,e,f}(t),\forall l\in L,\forall f\in F\\}$

Output: $\\{m_{l,e,k}(t),\forall l\in L,\forall k\in K\\}$ — the number of
servers reservation $l$ should take from the racks.

1 for  _$f$ = 1 to $|F|$_ do

2 Sort the racks in the MSB $f$ according to the number of servers previously
assigned to reservation $l$ in the descending order

3 $p\leftarrow$ quotient of $n_{l,e,f}(t)$ by the number of racks in MSB $f$

4 $q\leftarrow$ modulus of $n_{l,e,f}(t)$ by the number of racks in MSB $f$

5 $counter\leftarrow 0$

6 for  _$k$ in $\Phi^{F}_{f}$_ do

7 if  _$counter <q$_ then

8 $m_{l,e,k}(t)\leftarrow p+1$

9

10 else

11 $m_{l,e,k}(t)\leftarrow p$

12

13 end if

14 $counter\leftarrow counter+1$

15

16 end for

17

18 end for

Algorithm 3 Get the number of servers to take from the racks in MSBs for
reservations

Input: $\\{m_{l,e,k}(t),\forall l\in L,\forall k\in K\\}$

Output: $\\{x_{b,l}(t),\forall b\in B_{e},\forall l\in L\\}$

1 for  _$k$ = 1 to $|K|$_ do

2 $u_{k}(t)\leftarrow\sum_{l=1}^{|L|}m_{l,k}(t)-|\Psi^{K}_{k}|$

3

4 end for

5for  _$f$ = 1 to $|F|$_ do

6 for  _$k$ in $\Phi^{F}_{f}$_ do

7 $i\leftarrow|R|$

8 while  _$u_{k}(t) >0$ and $i\geq 0$_ do

9 if  _$m_{i,k}(t) <=u_{k}(t)$_ then

10 $u_{k}(t)\leftarrow u_{k}(t)-m_{i,k}(t)$

11 $m_{i,k}(t)\leftarrow 0$

12

13 else

14 $u_{k}(t)\leftarrow 0$

15 $m_{i,k}(t)\leftarrow m_{i,k}(t)-u_{k}(t)$

16

17 end if

18 Try to first move $\min(u_{k}(t),m_{i,k}(t))$ requests to racks in
$\Phi^{F}_{f}$

19 If it is not possible, move them to the racks in the other MSBs.

20 $i\leftarrow i-1$

21

22 end while

23

24 end for

25

26 end for

27for  _$k$ = 1 to $K$_ do

28 for  _$b$ in $\Psi^{K}_{k}$_ do

29 if  _$\alpha_{b}(t-1)==1$ and $m_{\alpha_{b}(t-1),k}>0$_ then

30 $m_{\alpha_{b}(t-1),k}\leftarrow m_{\alpha_{b}(t-1),k}-1$

31 $x_{b,\alpha_{b}(t-1)}(t)\leftarrow 1$

32

33 else

34

35 end if

36

37 end for

38

39 end for

Algorithm 4 Pseudocode of Algorithm 2

1 Initialize the size of the memory, learning rate, etc.

2 Initialize one agent or $|E|$ agents

3 for  _$e=1$ to $|E|$_ do

4 Start training the $e-th$ agent if this is for the parallel agents case

5 for  _$episode=1$ to $\Gamma$_ do

6 Initialize the capacity requests, reservations, and servers

7 for  _$t=1$ to $\mathcal{T}$_ do

8 for  _$l=1$ to $|L|$_ do

9 Combine the information of the environment and actions of reservations
$1,...,l-1$, into $\mathbf{s}_{l,e}(t)$

10 Send $\mathbf{s}_{l,e}(t)$ to the PPO agent and get $\mathbf{a}_{l,e}(t)$

11 Convert $\mathbf{a}_{l,e}(t)$ to numbers of servers to take by reservation
$l$, $\\{n_{l,e,f}(t),\forall f\in F\\}$, by (19)

12 Get numbers of servers to take from the racks, $\\{m_{l,e,k}(t),\forall
l\in L,\forall k\in K\\}$, by Algorithm 3

13

14 end for

15 Get server-to-reservation mapping, $\\{x_{b,l}(t)\\}$ for all $b$ and $l$
by Algorithm 2

16 for  _$l=1$ to $|L|$_ do

17 Calculate the reward of reservation $l$ by (15)

18 Store the state, action, and reward in the memory of the PPO agent

19

20 end for

21 Update the environment with the server-to-reservation mapping,
$\\{x_{b,l}(t),\forall b\in B,\forall l\in L\\}$

22 $t\leftarrow t+1$

23

24 end for

25

26

27 end for

28

29

30 end for

31

Algorithm 5 Training the PPO agent