Learning Distributed and Fair Policies for Network Load Balancing as Markov Potential Game
Authors: Zhiyuan YAO
Zihan Ding
Venue: NeurIPS 2022 Accept (2022)
Keywords: MARL
load balancing
distributed systems

Abstract: This paper investigates the network load balancing problem in data centers (DCs) where multiple load balancers (LBs) are deployed, using the multi-agent reinforcement learning (MARL) framework. The challenges of this problem consist of the heterogeneous processing architecture and dynamic environments, as well as limited and partial observability of each LB agent in distributed networking systems, which can largely degrade the performance of in-production load balancing algorithms in real-world setups. Centralised training and distributed execution (CTDE) RL scheme has been proposed to improve MARL performance, yet it incurs -- especially in distributed networking systems, which prefer distributed and plug-and-play design schemes -- additional communication and management overhead among agents. We formulate the multi-agent load balancing problem as a Markov potential game, with a carefully and properly designed workload distribution fairness as the potential function. A fully distributed MARL algorithm is proposed to approximate the Nash equilibrium of the game. Experimental evaluations involve both an event-driven simulator and a real-world system, where the proposed MARL load balancing algorithm shows close-to-optimal performance in simulations and superior results over in-production LBs in the real-world system.

Learning Distributed and Fair Policies for Network Load Balancing as Markov Potential Game
Zhiyuan Yao"
Zihan Ding" Princeton University zihand@princeton.. edu
École Polytechnique, Cisco Systems zhiyuan. zhiyuan. hatplya..yoolllyytocciiiuu.. edu
Abstract
This paper investigates the network load balancing problem in data centers (DCs) where multiple load balancers (LBs) are deployed, using the multi-agent rein- forcement learning (MARL) framework. The challenges of this problem consist of the heterogeneous processing architecture and dynamic environments, as well as limited and partial observability of each LB agent distributed networking systems, which largely degrade the performance of in in-production load balanc- ing algorithms in real-world setups. Centralised training- decennraliseee-exxeeeeeee (CTDE) RL scheme has been proposed to improve MARL performance, yet it incurs - especially in distributed networking systems, which prefer distributed and plug-and-play design schemes additional communication and management overhead among agents. We formulate the multi-agent load balancing problem Markov potential game, with carefully and properly designed workload distribution fairness as the potential function. A fully distributed MARL algorithm is proposed to approximate the Nash equilibrium of the game. Experimental eval- uations involve both an event-driven simulator and real-world system, where the proposed MARL load balancing algorithm shows dlosetto-optimn performance simulations, and superior results over in- in-production LBs in the real-world system.
1 Introduction
cloud data centers (DCs) and distributed networking systems, servers are deployed on infrastruc- tures with multiple processors to provide scalable services [T. To optimise workload distribution and reduce additional queuing delay, load balancers (LBs) play a significant role such systems. State-of-the-arr network LBs rely on heuristic mechanisms (35) under the low-latency and high- throughput constraints the data plane. However, these heuristics are not adaptive to dynamic environments and require human interventions, which can lead to most painful mistakes in the cloud - mis coniiiioniiuuriioon.. RL approaches have shown performance gains in distributed system and yet applying RL the network load balancing problem is challenging.
networking problems G
First, unlike traditional workload distribution or task scheduling problem 7 network LBs have limited observations over the system, including task sizes and actual server load states. Being aware of only the number of tasks they have distributed, servers can be overloaded by collided elephant tasks and have degraded quality of service (QoS).
Second, guarantee high service availability in the cloud, multiple LBs are deployed in DCs. Network traffic is split among all LBs. This multi-agent setup makes LBs have only partial observation over the system.
Third, modern DC' are based on heterogeneous hardware and elastic infrastructures 10 where server capacities vary. It is challenging assign correct weights servers according to their actual
"Equal contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

processing capacities, and this process conventionally requires human intervention which can lead error-prone configurations
3
Glient
Algorithm 1 LB System Transition Protocol
Workladd
1: Initialise server load, (0) + 0, E [M]
Load Balanzer
2: for each time step do
M304y Action
3: for each LB agent i [M] do
Choose action ax (t) for coming tasks (t(()
Application Servers
Processing Speed 1/y
5: end for
6: for each server do
7: Update workload:
(t(t) = (x(t-))+ ((())as(()-es(tt))
X,(1) X,(t 1)
m,(O),, 1t 1)
8: end for
Next Timestep: Update Server Load States
9:
end for
Figure Network load balancing.
Last but not least, given the low-latency and high-throughput constraints in the distributed networking setup, the interactive training procedure of RL models and the teriiiiedd-rrinng---.. decentralised- execution (CTDE) scheme I1 can incur additional communication and management overhead.
In this paper, study the network load balancing problem in multi-agent game theoretical approach, by formulating it as a Markov potential game through specifying the proper reward function, namely variance-based fairness. We propose distributed Multi-Agent RL (MARL) network load balancing mechanism that is able to exploit asynchronous actions based only on local observations and infer- ences. Load balancing performance gains are evaluated based on both event-based simulations and real-world experiment
2 Related Work
Network Load Balancing Algorithms. The main goal of network LBs is to fairly distribute workloads across servers. The system transition protocol of network load balancing system is deseribed in Alg. and depicted in Fig. Existing load balancing algorithms partial observations and inaccurate server weights. Equal-Cost Multi-Path (ECMP) LBs randomly assign servers Weighted-Coo -ost Multi-Path (WCMP) LBs assign weights to servers proportional to their provisioned resources (e.g. CPU power) 3 17 However, the statically assigned weights may correspond to the actual server processing capacity. As depicted in Fig. 2a servers with the same IO speed yet different CPU capacities have different actual processing speed when applications have different resource requirements. Active WCMP (AWCMP) is variant of WCMP and it periodically probe server utilisation information (CPU/memory/IO usage) 5 18 However, active probing can cause delayed observations and incur additional control messages, which degrades the performance of distributed networking systems. Local Shortest Queue (LSQ) assigns new requests the server with the minimal number of ongoing networking connections that are locally observed 19 20 It does not concern server processing capacity differences. Shortest Expected Delay (SED) derives the "expected delay" as locally observed server queue length divided by statically configured server processing speed [2). However, LSQ and SED are sensitive to partial observations and misconfigurations. As depicted in Fig. 25 the QoS performance of each load balancing algorithm degrades from the ideal setup (global observations and accurate server weight configurations) when network traffic is split across multiple LBs server weights are mis-configured which prevails in real-worid cloud DCs.
sensitive to
requests 14) which makes them agnostic to server load state differences.
In this paper, we propose distributed MARL-based load balaneing algorithm that considers dynami- cally changing queue lengths (e.g. sub-ms in modern DC networks (21 ). and autonomously adapts to actual server processing capacities, with no additional communications among LB agents or servers.
Markoy Potential Games. potential game (PG) 22 25 has a special function called potential
function, which specifies property that any individual deviation of the action for one player will
SSource code and data both simulation and roal-world experiment are open-sourced https//gituh.com//hhyuu htt.://////iiyuuaaa/aa//A... YaoJ/MARI.LB
Thee stochastic Markov model of the simulation is detailed in the App.

---

CPU Dift. Ratio
ECMP
WCMP
LSO
SED
10 Diff. Ratio
Qos (Latency)
QZcRu Q1CRP
10 Intensive
CPU-IO
CPU Intensive
Pure CPU
Balanced
Ideal 2 Ageinss 3 Agents
Weights
Wrong 2. Agenns 3 Agents
virong wrong
Application Profile
Weights Weights
(a) It is hard to accurately estimate the actual server
(h) The performance of existing network load balancing
processing speeds since it depends both provi- algorithms degrades when observation hecomes partial
sioned resources, and application profiee (App. F.T with multi-agents and weights are mis-configured.
Figure 2: Existing network load balancing algorithms are sub- sub-optimal under real-world setups.
Table I: Trade-offs among the probing frequency, measurement quality, and communication overhead.
Probing Frequency (/s)
2.22
2.86
4.00
6.67
20.00
CPU (%)
48.33
44.56
39.84
32.65
21.97
RMSE
#Job
2.07
1.85
1.61
1.31
0.91
CPU (%)
0.28
0.40
0.52
0.68
0.85
Spearman's 's Corr.
#Job
0.47
0.56
0.66
0.77
0.89
Communication
2LB-7server
2.15
2.76
3.86
6.44
9.32
Overhead (kbps)
6LB-20server
18.40
23.66
33.12
55.20
165.60
change the value of its own and the potential function equivalently. A desirable property of PG is that pure NE always exists and coincides with the maximum of potential function in norm-form setting.
Self-play [26] provably converged for PG. Markov games (MG) is extension of normal-form
game to multi-step sequential setting. A combination of PG and MG yields the Markov potential
games (MPG) [27 28]. where pure NE also proved exist. Some algorithms (27 29 30 lying
in the intersection of game theory and reinforcement learning are proposed for MPG. For example, independent nature policy gradient is proved to converge Nash equilibrium (NE) for MPG [27]
Multi-Agent RL. MARL 31 has been viewed as an important avenue for solving different types of games in recent years. For cooperative settings, a line of work based on joint-value factorisation
have been proposed, involving VDN (3) COMA (T. MADDPG (33] and QMIX (4]] For these works, global reward is assigned to players within the team, but individual policies are optimised to execute individual actions, known as the CTDE setting. MPG satisfies the assumptions of the value decomposition approach, with the well-specified potential function as the joint rewards. However, deploying CTDE RL models in real-world distributed system incurs additional communication latency and management overhead for synchronising agents and aggregating trajectories. These additional management and communication overheads can incur substantial performance degradation constrained throughput and increased latency - especially in data center networks. As listed in Table when we use active probing to measure server utilisation information, higher probing frequencies give improved measurement quality in terms of CPU usage and number of on-going jobs on the servers. However, higher probing frequencies also incur increased communication overhead, especially in large-scale data center networks. The detailed experimental setups, as well as both qualitative and quantitative analysis of the impact of communication overhead, are described in Sec. E.2.2 By leveraging the special structure of MPG, independent learning approach can be more efficient due to the decomposition of the joint state and action spaces, which is leveraged in the proposed methods. Methods like MATRPO 35 IPPO (36 follow a fully decentralised setting, but
for general cooperative games.
In terms of the distribution fairness, FEN 37 is proposed as decentralised approach for fair reward distribution in multi-agent systems. They defined the faimess as coefficient of variation and decompose for each individual agent. Another work (38) proposes a decentralised learning method for fair policies in cooperative games. However, the decentralised learning manner in these methods are not well justified, while in this paper the load balancing problem is formally characterised as MPG and the effectiveness of distributed training is verified.
3

---

3 Methods
3.1 Problem Description
We formulate the load balancing problem into a discrete-time dynamic game with strong distributed and concurrent settings, where centralised control mechanism exists among agents. We let M denote the number of LB agents ([M) denotes the set of LB agents (1....,)) and N denote the number of servers ([N] denotes the set of servers {1,..., N)). At each time step (or round) t E H in a horizon H of the game, each LB agent i receives a workload wy(t) E W. where W is the workload distribution, and the LB agent assigns server to the task using its load balancing policy म; E II. where II is the load balancing policy profile, At each time-step 6, a LB agent takes an action (t( {a))(t)} according which the tasks wi(() are assigned with distribution
(t).). (t)(() is the probability mass of assigning tasks to server Σラー Oig (iz(() = 1. Therefore, at each time step, the workload assigned to server j by the i-th LB is wy; (;;()) (t)- During each time interval, each server j is capable of processing a certain amount of workload Uy based on the property of each server (e-g- provisioned resources including CPU, memory, etc. ). We have server load state (remaining workload to process) (T) E max(0, E w,(t)aas(() - 0y} = ma Ei= Σn (t)(t);)(t)) vyT} = - (T Let Ij denote the time for a server j to process all remaining workloads, which is also the potential queuing time for new-coming tasks, (t(t) (,(t-1) 1)+ + Ei=1 my(t)aas(()) EM (((t-1)+a;;()aa.
M Di=1 biy (t). Then transition from
%
"i
time step to time step t + 1 is given in Alg. D Reward: ra(t)= = R(((t), 6,)),,)))) where R is the reward function, L(t) = -ー ((t) -
i== (t) denotes the estimated remaining time to process on each server, and (t) is random variable that makes the process stochastic.
Definition 1. (Makespan) In the selfish load balancing problem, the makespan is defined as:
MS 1 max((s),
ΣEA li5
The network load balancing problem is featured as nulti-commmoity flow problems and is NP-hard, which makes it hard to solve with trivial algorithmic solution within micro-second level [39]. This problem can be formulated as constrained optimisation problem for minimizing the makespan over an horizon E [M]]
minimize
max (1(
(2)
Σ M (X - 1) + 20 (t))
M Σ
s.t. (tt)
Σ (t) S
U/s 1y; my E (0, +00)
(3)
Vi
1=1
N
XT, Σ max w. (t),,,)(( E-
Σ (1) 11,
on [0.1]
M
In modern realistic network load balancing system, the arrival of network requests is usually un- predictable in both its arriving rate and the expected workload, which introduces large stochasticity into the problem. Moreover, due to the existence of noisy measurements and partial observations, the estimation of makespan can be inaccurate, which indicates the actual server load states or pro- cessing capacities are not correctly captured. Instant collisions of elephant workloads or bursts of mouse workloads often happen, which do not indicate server processing capacity thus misleading the observation. To solve this issue, we introduce fairness as an alternative of the original objective makespan. Specifically, makespan is estimated on per-server level, while the estimation of fairness can be decomposed to the LB level, which allows evaluating the individual LB performance without general loss. This is more natural in load balancing system due to the partial observability of LBs.
3.2 Distribution Fairness
We mainly introduce two types of load balancing distribution fairness: (1) variance- based fairness (VBF) and (2) product-based faimess (PBF). It will be proved that optimization over either faimesss will be sufficient but not necessary for minimising the makespan.
Xi)( Er. max(O, w: (t)au(()
3)

---

Definition 2. (Variance-based Fairness) For a vector of time to finish all remaining jobs = [4,....,yy [N] each server j E [N). let - =
& E lt)(t), the variance-based fairness for workload distribution is just the negative sample variance of the job time, which is defined as:
N
(00 (10)10))))))))))))))))) - 1 - E 500 +1))
F(I) - N
Σ
N
(5)
VBF defined per LB is: F((4)== - - (1)( (1). where L,(t) = tेr E 4.(1).
Lemma 3. The VBF for load balancing system satisfies the following property:
(L, F. - (i.) p (1))
F
(6)
This property makes VBF a good choice for the reward function in load balancing tasks. We will see more discussions in later sections. Proof of the lemma is provided in Appendix [B.I
Proposition 4. Maximising the VBF is sufficient for minimising the makespan, subjective to the load balancing problem constraints (Eq. B and 44): max F()) + min (4xx This also holds for per-I.B VBF as max Fi(4:) = min mlx)(14).
Definition 5. (Product-basse bosduct-based Fairness (401) For a vector of time to finish all remaining jobs each server [N], the product-based fairness for workload distribution is defined
as: F()) = F( = [[SE[N; maxity- PBF defined per LB is: F.(L,) = F(la,.....
[[jE[M] mmx(
Proposition 6. Maximising the product-based fairness is sufficient for minimising the makespan, subjective to the load balancing problem constraints (Eq. and J: max F(I) min max (1).
Proofs of proposition and 5 are in Appendix B. we know that the two types of fairness can serve as an effective alternative objective for optimising the makespan, which will be leveraged in proposed MARL method as valid reward functions.
respectively. From proposition 4 and 6
3.3 Game Theory Framework
where is the horizon the game, M the number of player in the game, S is the state space, Ax as is the joint action space of all players, A is the action space of player P = [PA h [H] is collection transition probability matrices PA : S x Ax + Pr(S), ), f {rali E [M]), r; S Ax IR. is the reward function for i-th player given the joint actions. The stochastic policy space for the i-th player in MG is defined as I1 S Pr(A;). II ) [M].
Markov game is defined as MG(H, M, S,A.M, PPT,PP
For the Markov game MMG, the state value function ViA. S + R and state-action value function 2T S x A + F. for the i-th player at step under policy π Ixx defined as:
(s),() = F..F
Σ
11
Taw an = =0] (T, = BT.F :BT.
=
Σ (awe
(ww..aw))))))))) an) an) s.
(7)
Definition 7. (e-approximate Nash equilibrium) Given MG(H, M, Ax ar, P., IIx,, MxMM).M. let T- be the policies of the players except for the i-th player, the policies (T) a is an c-Nash equilibrium if E [M] > O.
Markov game
V (s) ( V. - Vn; I..
(8)
Ife- = 0, it is an exact Nash equilibrium.
Definition (Markov Potential Game) A Markov game M(H, M, AxM,Pr (xM,TTMM is Markov potential game (MPG) ii [M], Ti, II, - E II_ E E.S.
ViT ((5) V,a. (ss) (s.) (s)
where o()) is the potential function independent of the player index. Lemma Pure NE (PNE) always exists for PG, local maximisers of potential function are PNE.
PNE also exists for MPG. (22)
5

---

LB Agent
LB Agent 0
BatchNom
BatchNorn
Mini-batch Transitions
LayerNorm
Guidling Critic-Net
Guiding
Linear
GRU
Linear
Soft Update
Critic-Net
Actions (
OnaHot
Guiding
Experience Replay
Koy
Guiding Actor-Net
Soft Update
Actor-Net
Actios
LB-Level Observations
{aistt - 1)1y
Obsservations
Generated Tranattions [a(f- (), o(t) +
inter-arivll time
duration)
arg min
HINSS
Par-Conneclingg ave Updane (sub-ms)
My
task duration
TCT
SYN ACK
Reply N Bytes
FIN ACK
Servers
LB
to
ft:
to
Client
SYN
ACK
GET
ACK
FIN
Time
Data Plane
Figure 3: Overview of the proposed distributed MARL framework for network LB.
Theorem 10, Multi-agent load balancing is MPG with the VBF F.(4:) as the reward for each LB
agent i [M]) then suppose for Vs step h E [H], the potential function is time-cumulative
total fairness: o (s) Σi= p (
The proof of the theorem based on Lemma 3 and it's provided in Appendix B.3 This theorem is essential for establishing our method, since it proves that multi-agent load balancing problem can be formulated as a MPG with the time-cumulative VBF as potential function. Also, the choice of per-LB VBF as reward function for individual agent is critical for making it MPG, it is easy to verify that PBF cannot guarantee such property. From Lemma
2 we know the maximiser of potential function is the NE of MPG, and from proposition it known that maximising the VBF gives the sufficient condition for minimising the makespan. Therefore, an effective independent optimisation with respect to the individual reward function specified in the above theorem will lead the minimiser of makespan for load balancing tasks. The effective independent optimisation here means the NE of MPG is achieved.
3.4 Distributed LB Method
With the above analysis, the load balancing problem can be formulated as an episodic version of multi-player partially observable Markov game, which we denote as POMG(H, H,, M, Ox 0xM, Ax., PxrxM)) where M, H. S, and follow the same definitions as in Markov game MG, OxM contains the observation space O, for each player, [H] is collection of observation emission matrices, 0g, Tx M = (rili E [M],r O Ax - R is the reward function for i-th LB agent given the joint actions. The stochastic policy space for the i-th agent POMG defined as II, O - Pr(A,). As discussed in Sec. P the partial observability comes from the fundamental configuration of network LBs in DC networks, which allows LBs to observe only a partial of network traffic and does not give LBs information about the tasks (e.g. expected workload) distributed from each LB, The reward functions in our experiments are variants of distribution fairness introduced Sec. 3.2 The potential functions can be defined accordingly based on the two fairness indices. The overview of the proposed distributed MARL framework is shown in Fig.
O [02].1 }.
- Pr(O,).
In MPG, independent policy gradient allows finding the maximum of the potential function, which is PNE for the game. This inspires us to leverage the policy optimisation a decomposed manner, i.e, distributed RI. for policy learning of each LB agent. However, due to the partial observability of system and the challenge of directly estimating the makespan (Eq. (T), each agent cannot have direct access to the global potential function. To address this problem, the aforementioned fairness

---

Algorithm 2 Distributed LB for MPG
1:
Initialise:
2: LB policy ne. and critic Qo, networks, replay buffer B,, Vi E [M];
3: server processing speed function vy, Vj E [M];
4: initial observed instant queue length server j by the i-th LB: 9. = 0, Vi [M], [N].
while not converge do
6: Reset server load state (1) + O, vj E [M]
7: Each I.B agent i (i E [M] receives individual observation (1)
8:
for = 1..... Hf do
Initialise distributed workload may, wx(t) 0, E [M]. [N]
10:
Get actions (1) <- {as (())}=1 Te, (t)), ( i [M]
11:
for job to arrived at I.B between timestep [t, f + 1) do
12:
LB assigns Vē to server j arg [in (1(++
13:
+ Mug + 1ū (t) + (x( + Smcg (t) + (
14:
15:
end for
16:
for cach server j do
17:
Update workload: (ty(+ 1) 1)+ max w. (1)=(((1) . (t ΣM (t)
18:
19:
end for
20:
Each agent receives individual reward rt)
21:
Each agent i collects observation ol + 1), i E [M]
22:
Update replay buffer: B, B, U(aill 1), (())))))()))))))))(() 1)), [M]
23:
end for
(0,, - (o)) )
24:
Update critics with gradients: Vo, (io,,anrr,))))
25:
where Vi, (of) = (B8, QQ (de, a') - a log TA, i E [M
26:
Update policies with gradients: -V,, BB Banty log ne, (a:lo:) - Qo, (o,, ai (M]
27:
end while
28:
return final models of learning agents
(Sec. 3.2 can be deployed as the reward function for each agent, which makes the value function as a valid alternative for the potential function an objective. This also transforms the joint objective (makespan or potential) to individual objectives (per LB fairness) for each agent. Proposition g and 6 verify that optimising towards these fairness indices is sufficient for minimising the makespan.
Alg. 2 shows the proposed distributed IBB for load balancing problem, which is a partially observ- able MPG. The distributed policy optimisation is based on Soft Actor-Critic (SAC) [4 algorithm, which is a type of meximum-entropp RL method. optimises the objective EE EE,, 7 (To)), whereas H.(-) is the entropy of the policy TT. Specifically, the critic Q network is updated with
gradient Vo (Qaso..a a) r(o,a) (V(o'))))))
where V²(0') E. (Q,(o aa)
log (a and Q3 is the target Q network; the actor policy my is updated with the gradient [o [Fa (or log No (alo) (o,o, a)]] Other key elements of RL methods involve the observation, action and reward function, which are detailed as following.
Observation. Each LB agent partially observes over the traffic that traverses through itself, including per-server-level and LB-level measurements. For each LB, per-server-level observations consist of for each server the number of on going tasks, and sampled task duration and task completion time (TCT). Specifically, in Alg. 2 line
12 14 wi is the coming workload on servers assigned by i-th LB, and not observable for LB. q.k
is the locally observed number of tasks on k-th server by i-th IB, due to the real-world constraints of limited observability at the Transport layer. The "+1" is for taking into account the new-coming task. Observations of task duration and TCT samples, along with LB-level measurements which sample the task inter-arrival time as an indication of overall system load state, are reduced scalars - i.e. average, 90th 90th-00rceee percentile, standard deviation, discounted average and weighted discounted averagd inputs for LB agents.
'Diccounted average weights are computed as 0.9* -t where is the sample timestamp and t' is the moment of caleulating the reduced scalar.
7

---

QMix/PBF
D
Makessan QMi
Distr-LBIVBF
Centr-I Bjvis
LSQ
Distr-LBIVBF +logVBF
Distr Laivar
Centr BiJvBF+
SED
QMix| PBF
Centralised VBF
1.0
0o5 TCT (9)
0.2
CDF
0.5
0.05
page
M3tic page
200
400
500
800
1000
10:
10
104
10-2
10-2
10
10
10
Iterations
QoS
TCT (S)
Qo5
TCT
(s)
(a) Learning curves.
(b) CDF of TCT.
Figure 4: Experimental results show that the proposed distributed RL framework using proposed VBF as rewards converges and effectively achieves better load balancing performance (lower TCT and better QoS) than existing LB algorithms and CTDE RL algorithms.
Action. To bridge the different timing constraints between the control plane and data plane, each LB agent assigns the j-th server to newly arrived tasks using the ratio of two factors, arg minge[N] 2at-1 where the number of on-going tasks que helps track dynamic system server occupation at per- connection level - which allows making load balancing decision at js-level speed and dsk is the periodically updated RL-inferred server processing speed. As in line 14 of Alg. (xay() (t) is
dsk
statistical estimation of workload assignment distribution at time interval [t. 1. 1).
Reward. The individual reward for distributed MPG LB is chosen as the VBF (as Def. 2 of the discounted average of sampled task duration measured on each LB agent, such that the L.B group jointly optimise towards the potential function defined in Eq. (TOp. Task duration information is gathered as the time interval between the end of connection initialisation (e.g. 3-way handshake for TCP traffic) and the acknowledgement to the first data packet (e.g. the first ACK packet for TCP traffic). Given the limited and partial observability of LB agents, task duration information approximates the remaining workload / by measuring the queuing and processing delay for new- coming tasks on each server. This PBF- and MS-based rewards are also implemented for CTDE MARL algorithm comparison.
Model. The architecture of the proposed RL framework is depicted in Fig. 3 Each LB agent consists of a replay buffer, and pair of actor-critic networks, whose architecture is depicted on the top right. There is also pair of guiding actor-critic networks, with the same network architectures but updated in a delayed and soft manner. Each LB agent takes observations (t) extracted from the data plane (e.g. numbers of ongoing tasks {4 J. task duration, TCT) and actions from previous timestep at(t - 1) as inputs, and periodically generates new actions a; (t),, which is used to update the server assignment function arg minje[M] applied for all agents to leverage the sequential history information for handling partial observability.
9.y+1 in the data plane. The gated recurrent units (GRU) [42 axy
Evaluation
We developed (i) an event-based simulator (App. to study the distance between the NE achieved by the proposed algorithm and the NE achieved by the theoretical optimal load balancing policy (with perfect observation), and (ii) realistic testbed (App. C2 on physical servers in DC network providing Apache web services, with real-world network traffic [43 to evaluate the real-world performance of the proposed algorithm, in comparison with in-production state-of-thh-aat L.B (
As depicted in Fig. 4a moderate-scale real-world DC network setup with 2 LB agents and servers, after 120 episodes of training, the proposed distributed LB (Distr-LB) algorithm able learn from the environment based on VBF as rewards, and converges to offer better QoS than QMix. Centralised RL agent (Centr-LB) has difficulties to learn within 120 episodes because of the increased state and action space. An empirical finding is that, by adding log term to the VBF-based reward for Distr-LB, we help LB agents to become more sensitive to close-to-0 VBF during training (V,, log /(x) > (a.((r) when f(x) < 1), therefore achieving when comparing with in-production IB algorithms (WCMP, LSQ, SED), Distr-LB shows clear performance gains and reduced TCT for both types of web pages Wikipedia pages require to query SQL databases thus they are more
Soderate-Scale Real-Worid Testbed:
better load balancing performance. As depicted in Fig-
8

---

Table 2: Comparison of average QoS (s) in moderate scale real-world network setup.
Period III (758.78) 758.787 queriests)
Peried IV (784.522 queries/s)
Method
Wiki
Static
Wiki
Statie
WCMP
0.412 1 0.101
0.134 1: 0.059
0.834 1: 0.323
0.492 1: 0.276
LSQ
0.620
0.442
0.339 + 0.316
0.357 : 0.373
0.173 4: 0.299
SED
0.215
0.210
0.051 1. 0.081
0.346 1 0.496
0.169 0.330
Jain
0.193 + 0.073
0.026 + 0.022
0.204 = 0.084
0.039 + 0.047
RLB-SAC
0.149 0.049
0.015 0.011
0.155 0.052
0.011 0.011
MS
0.211 + U.137
0.048 + 0.069
0.263 = U.202
0.073 + 0.092
QM
0.141
0.004
0.286 0.162
0.068 0.066
PRF
0.211 0.133
0.047 + 0.078
0.181 = 0.042
0.018 + 0.009
Distr-LB
VBF
0.159 0.054
0.017 = 0,009
0.190 = 0.091
0.032 0.033
(this paper)
VBF-logVBF
0.108 0.022
0.004 0.001
0.104 0.013
0.006 0.003
VBF
1.068 + 0.386
0.570 + 0.378
1.378 = 0.377
0.867 + 0.350
Centr-LB
VBF-log
0.759 0.254
0.306 0.222
0.320 0.167
Table 3: Comparison of average QoS (s) in moderate-scale simulator for different types of applica- tions.
508-CPU+308--0
75%-CPU+25%-10
100%-CPU
Oracle
6.437 1.000
1,469 0.
1.291 = 0.075
PBF
10.230 0.108
1.828
2.200 0.288
QMix-LB
VBF
10.936 1 0.470
2.023 1: 0.25
2.125 1 0.074
Distr-LB
0.362
1.695 0.104
1.643 0.016
(this paper)
VBF+logVBF
8.797 + 0.459
1.873 + 0.328
2.004 # 0.042
CPU-intensive, while static pages are 10-intensive. The comparison of average TCT using different
LB algorithms is shown in Table 2 (99th percentile TCT in Table 12p The proposed Distr-LB
also shows superior performance than the RL-based solution (RLB- SAC) 40 because of (i) well
designed MARL framework, and (ii) the use of recurrent neural network to handle load balancing problem sequential problem.
NE Gap Evaluation with Simulation: To evaluate the gap between the performance of Distr-LB and the theoretical optimal policy, we implement in the simulator an Oracle LB, which has perfect observation (inaccessible in real world) over the system and minimises makespan for each load balancing decision. Table g shows that, for different types of applications, Distr-LB is able to achieve closer-to-optimal performance than QMix. As the simulator is implemented based on the load balancing model formulated in this paper, theoretical analysis can be directly applied, and VBF- as a potential function - helps independent cooperative LB agents to achieve good performance. The additional log term shows empirical performance gains in real-world system, yet it is not necessarily the case in these simulation results. On one hand, the generated traffic of tasks in the simulation has higher expected workload (> 1s mean and stddev), while the log terms is more sensitive to close-to-O variances, which is the case real-world experimental setups. On the other hand, though the simulator models the formulated LB problem, it fails to captures the complexity in the real- world gystem-e.g Apache backlog, multi-processing optimisation, context switching. multi-level cache, network queues etc. For instance, batch processing 44] helps reduce cache and instruction misses, yet yields similar processing time for different tasks, thus the variance of task processing delay decreases and becomes closer in real-world system. The additional log term exaggerates the low variance differences to better evaluate load balancing decisions. More detailed description about the simulator implementation can be found in App C.I and ablation study on reward engineering presented in App E.2.1
Table 4: Comparison of average QoS (s) in large-scale real-world network setup.
Period (2022.855 queries/s)
Period (2071. 129 querics/s)
Method
Wiki
Statie
Waki
Static
WCMP
0.473 0.102
0.194 1 0.090
0.460 1 0.241
0.239 0.212
L.QQ
0.266 0.
0.063 1 0.065
0.218 4 0.246
0.082 0.132
SED
0.169 + 0.062
0.020 + 0.025
0.166 - 0.141
0.050 = 0.070
RLB-SAC-G
0.182
0.111 0.029
U.009
QMix-LB
VGE
0.181 1 0.062
0.019 1 0.020
0.188 1 0.147
0.052 1 0.075
0.210
0.013 1 0.006
0.104 0.009
0.005 0.003
Distr-LB
VBF
0.228 1: 0.055
0.019 1 0.011
0.174 0.102
0.035 0.039
(this paper)
VBF+logVRF
0.161 1: 0.033
0.008 1 0.003
1.94110015
0.004 0.001

---

Table 5: Comparison of 99-th percentile QoS (s) of Wiki pages under different traffic rates using large-scale real-world setup.
Traffic Rate (queries(s)
Method
731,334
1097.3
1463.067
1828.834
2194.601
23774884
2500.368
2743.251
2926.135
LSQ
0.175
0.212
0,249
0,342
0.827
2.103
10.602
17.656
17.999
+00011
=0.025
+0.04
+00121
+00572
+0.654
+2.557
#0.714
=0,253
0.201
0.261
0.322
0.360
0.618
2.175
11.444
22,086
22.727
SED
+00022
=0,079
20,099
+0,088
+02268
+1.328
+3.861
+4,892
+5.632
0,160
0.205
0.248
0,284
0.567
1.276
7,005
10.560
15.745
VBF
Distr-I.B
1.0.100
0.036
1..086
1.0.13
1.0.306
10.6447
11.147
1.1.44
1.0.554
(this paper)
VBF+log VBF
0.16T
0.216
0.249
0.348
0,439
1.33
4.427
9,391
15.347
+00008
=0.052
+0.068
+0012
20.121
#0.670
+0.44
+0.329
+0.572
Table 6: Comparison of 99-th percentile QoS (s) of static pages under different traffic rates using large-scale real-world setup.
Traflic Rate (queries(s)
Method
731,34
1097.3
146306
1828,33
2194.601
2377.484
2500.368
2741.251
2926.1M5 135
LSQ
0.015
0.856
16.874
17.155
1:0.001
-0.000
10.000
1.0000
+-0300
+:0.554
+.3.95
10.391
+0.217
0.014
0.015
0.016
0.018
0.071
1.252
11,272
21.941
20.708
SED
+0,000
=0.000
+0.001
+00001
+00066
+1.489
+3995
55.70
=5,423
VBF
0.014
0.015
0,016
0.017
0,041
0L338
6.670
9.743
15.506
Distr-LB
+0.000
=0.000
=0.001
1:0.00
+00025
+.0366
+1.15
+00863
-0005
(this paper) VBF+logVBi VBF
0.014
0,015
0,016
0.018
0,072
0.465
3,970
8.782
15.095
1:0.000
2 0.001
1,0.000
1.0.002
1.0.087
1:0.403
1.0.54
1: 1.0.87
1: 0.497
To evaluate the performance of Distr-LB in large-scale DC networks in real world, we scale up the real-world testbed to have 6 LB agents and 20 servers and apply heavier network traffic (> 2000 queries/s) evaluate the performance of the LBB algorithms that achieved the best performance in moderate scale setups, in comparison with in-production LB algorithms. The test results after 200 episodes of training are shown in Table 4 where Distr-LB achieves the best performance in all cases. QMix also outperforms in-production LB algorithms. But as CTDE algorithm, similar to the Centr-LB, it requires agents to communicate their trajectories, which after 200 episodes of training- become 221MiB communication overhead at the end of each episode (episodic training), whereas 95%-percet per- reeeddeiintiio-neee -rac flow rate is less than 1MiB/s [45].
Large-Scale Real-World Testbed:
Using the same large-scale real-world testbed with 6 LB agents and 20 servers, we conduct scaling experiments by applying network traces with different traffic rates, comparing 4 LB methods with the best performances. The 99-th percentile QoS for both Wiki and static pages are shown in Table 5 6 As listed in Table 5 and 6 under low traffic rates, when servers are all under utilised, the advantage of our proposed Distr-LB is not obvious because all resources are over-provisioned. With the increase of traffic rates (till servers are 100% saturated), our methods outperforms the best classical LB methods. More in-depth discussion and analaysis over the average job completion time for both types of pages in these scaling experiments are shown in Table [4] and 15 in App. E.2.2
Scaling Experiments:
More details regarding the real-world DC testhed implementation is in App. training details in App. D complete evaluation results (both moderate-scale and large-scale) in App. and ablation studies e.g. communication overhead of CTDE and centralised RI. in real-world system, robustness of MARL algorithms in dynamic DC network environments can be found in App.
5 Conclusion and Future Work
This paper proposes distributed MARL approach for multi-agent load balancing problem. based on Markov potential game formulation. The proposed variance-based fairness for individual LB agent critical for this formulation. Through this setting, the redundant communication overhead among LB agents is removed, thus improving the overall training and deployment efficiency in real- world systems, with the local observations only. Under such formulation, the effectiveness of our proposed distributed LB algorithm together with the proposed fairness are both theoretically justified and experimentally verified. It demonstrates a performance gain over another commonly applied fairness as well as centralised training methods like QMIX or centralised RI. agent, in both simulation and real-world tests with different scales.
10

---

References
[1] Nicola Dragoni, Saverio Giallorenzo, Alberto Lluch Lafuente, Manuel Mazzara, Fabrizio Montesi, Ruslan Mustafin, and Larisa Safina. Microservices: yesterday, today, and tomorrow.
In Present and Ulterior Software Engineering, pages 195-216. Springer, 2017.
[2] The Linux Virtual Server Project Linux Server Cluster for Load Balancing. http://wwwt /ww
1 innuvirtuaassererr. org/
[3] Daniel E Eisenbud, Cheng Yi, Carlo Contavalli, Cody Smith, Roman Kononov, Eric Mann- Hielscher, Ardas Cilingiroglu, Bin Cheyney, Wentao Shang, and Jinnah Dylan Hosein. Maglev: A fast and reliable software network load balancer. In NSDI, pages 523-535, 2016.
[4] Yoann Desmouceaux, Pierre Pfister, Jérôme Tollet, Mark Townsley, and Thomas Clausen. 6lb: Scalable and application-awarc load balancing with segment routing, /EEE/ACM Transactions on Networking. 26(2):819 9344,,447 2018.
[5] Ashkan Aghdai, Michael I-C Wang, Yang Xu, Charles H-P Wen, and H Jonathan Chao. In- network congestion-awee load balancing at transport layer. arXiv preprint 2018.
[6] Li Chen, Justinas Lingys, Kai Chen, and Feng Liu. Auto: Scaling deep reinforcement learning for datacenter-scale automatic traffic optimization. In Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, pages 191-205. ACM, 2018.
[7] Hongzi Mao, Malte Schwarzkopf, Shaileshh Bojja Venkatakrishhan, Zili Meng, and Moham- mad Alizadeh. Learning scheduling algorithms for data processing clusters. arXiv preprint arXiv:1810.01963. 2018.
[8] Yue Xu, Wenjun Xu, Zhi Wang, Jiaru Lin, and Shuguang Cui. Load balancing for ultra-dense networks: A deep reinforcement learning based approach. IEEE Internet of Things Journal, 6(6):9399 9412, Dec 2019. arXiv: 1906.00767.
[9] Viswanath Sivakumar, Tim Rocktäschel, Alexander Miller, Heinrich Küttler, Nantas Nardelli, Mike Rabbat, Joelle Pineau, and Sebastian Riedel. Mvfst-rl: An asynchronous rl framework for congestion control with delayed actions. arXiv preprint arXiv: 04054, 2019.
[10] Adithya Kumar, Tyswarya Narayanan, Timothy Zhu, and Anand Sivasubramaniam. The fast and the frugal: Tail latency aware provisioning for coping with load variations. Proceedings The The Web Conference 2020, pages 314-326, 2020.
[11] Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
[12] Theo Julienne. GL.: GitHub's open source load balancer, 2018
[13] João Taveira Araújo, Lorenzo Saino, Lennert Buytenhek, and Raul Landa. Balancing the edge: Transport affinity without network state. page 111-124, 2018.
[14] Rui Miao, Hongyi Zeng, Changhoon Kim, Jeongkeun Lee, and Minlan Yu. Silkroad: Making stateful layer-4 load balancing fast and cheap using switching asics. In Proceedings of the Conference of the ACM Special Interest Group on Data Communication, pages 15-28, 2017.
[15] Facebook Incubator, Apr 2020.
[16] Shouqian Shi, Ye Yu, Minghao Xie, Xin Li, Xiaozhou Li, Ying Zhang, and Chen Qian. Coneury: A fast and leigt software cloud load balancer. page 14, 2020.
[17] Reuven Cohen, Matty Kadosh, Alan Lo, and Qasem Sayah. Lb scalability: Achieving the right balance between being stateful and stateless. IEEE/ACM Transactions Networking, 2021.
[18) Ashkan Aghdai, Cing-Ya Yu Chu, Yang Xu, David Dai, Jun Xu, and Jonathan Chao. Spotlight: Scalable transport layer load balancing for data center networks. IEEE Transactions on Cloud Computing, 2020.
[19] Guy Goren, Shay Vargaftik, and Yoram Moses. Distributed dispatching in the parallel server model. arXiv:2008. 00793 [cs], Aug 2020. arXiv:
[20] Tom Barbette, Chen Tang, Haoran Yao, Dejan Kostié, Gerald Q Maguire Jr. Panagiotis Papadim- itratos, and Marco Chiesa A high-speed load-balancer design with guaranteed per-connection- consistency. In 17th {USENIX) Symposium on Networked Systems Design and Implementation ((NSDI) 20), pages 667-683, 2020.

---

[21] Chuanxiong Guo, Lihua Yuan, Dong Xiang, Yingnong Dang, Ray Huang, Dave Maltz, Zhaoyi Liu. Vin Wang. Bin Pang, Hua Chen, et al. Pingmesh: A large-scale system for data center network latency measurement and analysis. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, pages 1329155,,00 2015.
[22] Dov Monderer and Lloyd S Shapley. Potential games. Games and economic behavior, 14(1):124-
143, 1996.
[23]
William H Sandholm. Potential games with continuous player sets. Journal of Economic theory, 97(1):81-108, 2001.
[24] Jason R Marden, Gürdal Arslan, and Jeff S Shamma. Cooperative control and potential games. IEFE Transactions on Systems, Man, and Cyhernetics, Part B (Cyhernetics), 396)):1333-1407, 2009.
[25] Ozan Candogan, Ishai Menache, Asuman Ozdaglar, and Pablo A Parrilo. Flows and decom- positions of games: Harmonic and potential games. Mathematics of Operations Research, 36(3):474-003, 2011.
[26] Drew Fudenberg, Fudenberg Drew, David K Levine, and David K Levine. The theory of learning in games, volume 2. MIT press, 1998.
[27] Roy Fox, Stephen M Mcaleer, Will Overman, and loannis Panageas. Independent natural policy gradient always converges in markov potential games. In International Conference on Artificial Intelligence and Statistics, pages 4414-4425. PMLR, 2022.
[28) Stefanos Leonardos, Will Overman, loannis Panageas, and Georgios Piliouras. Global convergence of multi-agent policy gradient in markov potential games. arXiv preprint arXiv:2106.01960 2021.
[29] Sergio Valcarcel Macua, Javier Zazo, and Santiago Zazo. Learning parametric closed-loop policies for markov potential games. arXiv preprint 802.09980.. 2018.
[30] David H Mguni, Yutong Wu, Yali Du, Yaodong Yang, Ziyi Wang, Minne Li, Ying Wen, Joel Jennings, and Jun Wang. Learning in nonzero-sum stochastic games with potentials. In International Conference on Machine Learning, pages 7688-7699 PMLR, 2021. 2021.
[31] Yaodong Yang and Jun Wang. An overview of multi-agent reinforcement learning from game theoretical perspective. arXiv preprint arXiv:201 0.220011.0050 1.00583, 2020.
[32] Peter Sunchag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Leibo, Karl Tuyls, et al. Value- decomposition networks for cooperative multi-agent learning. arXiv preprint 170.vv/706..... 05296. 2017.
[33] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-compettiive environments. Advances in neural information processing systems, 30, 2017.
[34] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pages 4295-4304.
PMLR, 2018.
[35] Hepeng Li and Haibo He. Multi-agent trust region policy optimization. arXiv preprint arXiv:2010.07916. 2020.
[36] Christian Schroeder de Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip HS Torr, Mingfei Sun, and Shimon Whiteson. Is independent learning all you need in the starcraft multi-agent challenge? arXiv preprint arXiv:201 1.09533, 2020.
[37] Jiechuan Jiang and Zongging Lu. Learning faimess in multi-agent systems. Advances in Neural Information Processing Systems, 32, 2019.
[38] Matthieu Zimmer, Claire Glanois, Umer Siddique, and Paul Weng. Learning fair policies in decentralized cooperative multi-agent reinforcement learning. In International Conference on Machine Learning, pages 12967-12978. PMLR, 2021.
[39] Siddhartha Sen, David Shue, Sunghwan Ihm, and Michael Freedman. Scalable, optimal flow routing in datacenters via local link balancing. In Proceedings of the ninth ACM conference on Emerging networking experiments and technologies, pages 15 151-162, 2013.
12

---

[40] Zhiyuan Yao. Zihan Ding, and Thomas Clausen. Reinforced cooperative load balancing in data center. arXiv preprint arXiv:2201.1 2022.
[41] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on muchine learning, pages 1861-1870. PMLR, 2018.
[42] Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks sequence modeling. arXiv preprint arXiv:1412.355: 2014.
[43] Guido Urdaneta, Guillaume Pierre, and Maarten van Steen. Wikipedia workload analysis for decentralized hosting, Elsevier Computer Networks, 53(1 (1811)13001885,, July 2009.
[44]
The Fast Data Project (fd.io). Vector Packet Processing (VPP). https://wiki..fd.
VPP/
[45] Arjun Roy, Hongyi Zeng, Jasmeet Bagga, George Porter, and Alex Snoeren. Inside the social network's s (datacenter) network. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, SIGCOMM '15, page 123-137. ACM, 2015. event-place: London, United Kingdom.
[46] Mohammed Shabbir Ali, Pierre Coucheney, and Marceau Coupechoux. Reinforcement learning algorithm for load balancing in self-organizing networks, 2019.
[47] Apache Hadoop. Apache hadoop. URL http://hadoop. apache. org, 2011.
[48] Apache Spark. Apache spark. Retrieved January, 17:2018, 2018.
[49] Erik-Jan van Baaren. Wikibench: A distributed, wikipedia based web application benchmark.
Master's thesis, VU University Amsterdam, 2009.
[50] Parveen Patel, Deepak Bansal, Lihua Yuan, Ashwin Murthy, Albert Greenberg, David A Maltz, Randy Kern, Hemant Kumar, Marios Zikos, Hongyu Wu, et al. Ananta: Cloud scale load balancing. ACM SIGCOMM Computer Communication Review, 43(4))207-216 2013.
[51] Vladimir Olteanu, Alexandru Agache, Andrei Voinescu, and Costin Raiciu. Stateless datacenter load- balabcannning with beamer. In 15th {USENIX) Symposium on Networked Systems Design and Implementation ( ((NSDI) 18), pages 125-139, 2018
[52] Rohan Gandhi, Hongqiang Harry Liu, Y Charlie Hu, Guohan Lu, Jitendra Padhye, Lihua Yuan, and Ming Zhang. Duet: Cloud scale load balancing with hardware and software. ACM SIGCOMM Computer Communication Review, 44(4):27-38, 2015.
[53] Sai Qian Zhang, Qi Zhang, and Jieyu Lin. Efficient communication multi-agent reinforcement learning via variance based control. Advances in Neural Information Processing Systems, 32, 2019.
[54] Ziluo Ding, Tiejun Huang, and Zongqing Lu. Learning individually inferred communication for multi-agent cooperation. Advances in Neural Information P Processing Systems, 33:22069-22079, 2020.
[55] Jiao Zhang, F Richard Yu, Shuo Wang, Tao Huang, Zengyi Liu, and Yunjie Liu. Load balancing in data center networks: A survey. IEEE Communications Surveys & Tutorials, 20(3):2324-
2352, 2018.
[56] Rohan Gandhi, Hongqiang Harry Liu, Y Charlie Hu, Guohan Lu, Jitendra Padhye, Lihua Yuan. and Ming Zhang. Duet: Cloud scale load balancing with hardware and software. ACM SIGCOMM Computer Communication Review, 44(4):27-38, 2014.
[57] Noa Zilberman, Yury Audzevich, G Adam Covington, and Andrew W Moore. Netfpga sume: Toward 100 gbps as research commodity. IEEE micro, 34(5):32-41, 2014.
[58] Yong Li and Min Chen. Software-defined network function virtualization: A survey. IEEE Access, 3:2542-2553, 2015.
[59] ETSI. Open Source MANO (OSM) Project. htttss:/osm..eee. httpa:////seeessirrgg....
2019.
[60] OPNEV. Open Platform for NFV (OPNFV) Project Portal,
2019.
[61]
OpenStack. OpenStack Project Portal.
2019.
[62]
Jing Guo, Zihao Chang, Sa Wang, Haiyang Ding, Yihui Feng. Liang Mao, and Yungang Bao. Who limits the resource efficiency of my datacenter: An analysis of alibaba datacenter traces. In Proceedings of the International Symposium Quality of Service, pages 1-10, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See section
(c) Did you discuss any potential negative societal impacts of your work? [No] To our knowledge, the work has no potential negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] The proofs are provided in Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] The source code to reproduce both simulation and woaldw experimental results has been open- oper-souueed at http://ihuuu.oo//iiiiige
YaoJ/MARLLB
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [No] The error bars are replaced by cumulative distribution function (CDF).
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] This work is mainly based simulation and the information of computational resources are not relevant.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A] This work does not use existing assets.
(b) Did you mention the license of the assets? [N/A] This work does not use existing
assets.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A] This work does not use existing assets.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] This work does not use existing assets.
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] This work does not use existing assets.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A] It does not apply to this work.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A] does not apply to this work.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A] It does not apply to this work.
14


Reviews:
[{"review_id": "_y2ZS-JHGjb", "reviewer": "Reviewer_XheU", "summary": "This paper focuses on the network load balancing problem in data centers using multi-agent RL paradigm. The main goal in load balancing problems is to minimize the makespan\nThe authors prove various properties of the setting with the main result to be that such setting is a Markov Potential Game. They showed this result via properly defining a workload distribution fairness potential function. Moreover, using facts established in Leonardos et al, they design a distributed algorithm to approximate Nash equilibrium policies. The authors provide an extensive experimental section that suggest that the proposed algorithm is effective.", "questions": "What was the main technical difficulty that did not allow the authors to provide theoretical guarantees for their proposed algorithm?", "limitations": "This work has no negative societal impact as far as the reviewer can forsee.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros\nThe paper is interesting, with both theoretical and applied merits and an interesting modeling of the network load balancing prblems in data centers as a MARL system. \nCons: The result of the proposed framework to be a Markov potential game is not very surprising as load balancing games are known to be potential games (see [Koutsoupias, Papadimitriou 99]).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QJI81B1Ba-g", "reviewer": "Reviewer_Y8vv", "summary": "This paper proposes MPG-based MARL solution for the load-balancing problem. Applying RL directly for load-balancing is not favorable as the load balancers (i.e., multiple-agents) need to synchronize observations as well as the action space grows with number of agents (requiring re-training etc.)", "questions": "Please clarify the questions and limitations raised in the weakness section above. ", "limitations": "* Limited evaluation\n* Strong assumptions for a practical system\n* No comparison with other ML-based approaches. ", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. Does not require re-training with increasing number of multiple agents as the proposed approach decomposes\nthe joint state and action space.\n2. Does not require synchronization between the load balancers\n\n\n**Weakness**\n1. Poor evaluation\n  * No scaling experiments (i.e., increasing number of LBs or servers). Only 2 LBs in evaluation. If the paper had scaled the experiments more they would find that their approach may not be practical for real DCs (discussed later). \n  * No real traffic/workload. The supposedly real benchmark is a mocked up small testbed that does not mimic real distribution of traffic or scale. \n  * Experimentally weak: no variation in traffic and limited variation of IO/CPU\n  * What about QoS (99th percentile behavior, an important metric to evaluate for LBs)?\n2. Invalid and inconsistent assumptions wrt problem statement.\n  * In the intro, the paper claims that \"existing algorithms are not adaptive to due to dynamic environments\" yet the assumption made in this paper is that each server is capable of processing a certain amount of workload v_j, which is a number only dependent on server capabilities and not on the request (or traffic type itself). For example, a GET request of type X can take 2s whereas a another GET request of type Y can take 20s. The paper mentions collided elephants and yet does not provide any experiments that the proposed technique can handle such situations. In other words, v_j should be stochastic and not fixed on just the server but also on the request characristics. \n  * previous assumption invalidates most of the derivation presented later in the paper. \n\n  * Another assumption is that active probing is impractical. However, it is okay for LBs to communicate with severs to observe the server state, why? There is no citation or experiment showing that indeed that is a reasonable assumption. All of the work is based on this key assumption. \n\n3. Limited insights:\n  * why Markov Potential Games for handling the stated problem? Why not use mean-field theorem to approximate the behavior of all the other multi-agents using mean or median behavior. Overall the paper reads as an application of MPG rather than \"there is a nice solution\" to the load-balancing problem. Insights and analysis of different approaches are missing. \n * No evaluation of the overhead of the RL vs MARL solution in terms of performance as well as overhead (to justify MARL is needed over RL). There are several solutions proposed such as RLB-SAC (Neurips 2021) which reports similar high performance, and Park: An Open Platform for Learning-Augmented Computer Systems. \n * What happens if RL makes bad decisions (safety of RL: Towards safe online reinforcement learning in computer systems, NeurIPS 2021).\n\n4. Writing needs significant improvement esp. introduction and related work section.  \n     * citations on key assumptions/claims or experiments to make those statements\n    * Abbreviations introduced without describing what it stands for?: e.g. NE for MPG\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "M7eVHE-zY7T", "reviewer": "Reviewer_yzYr", "summary": "This paper proposes a distributed Multi-agent Reinforcement Learning based approach for load balancing at the network layer formulated as a Markov Potential game.\n\nCurrent network load balancers have limited observability over the workloads and servers performance and are prone to misconfiguration due to heterogeneity and elasticity. Centralized approaches (CTDE) incur an additional overhead from centralized communication. This work addresses this by using a local variance-based fairness function in each load balancer which, when maximized, can minimize the potential function of the Markov potential game. This approximates the Nash equilibrium of the game.\n", "questions": "* This work addresses load balancing in a single data center but I think it can easily be extended to a multi-DC setup by capitalizing on the low-observability approximation. Have you considered this?\n* Have you considered including some offline learning as the intial state? System logs from data centers usually provide good information about request patterns and existing data center hardware.\n* What is the rationale behind using 2/3 agents in Fig 2b?\n* Did you consider other kinds of traffic other than wiki (database heavy) and static? (video for example)\n* Are the numbers in Tables 1/2 mean or median?\n* Nitpick: Page 3, line 100 should say [M] denotes the set of LB agents {1,...,M} instead of set of servers\n* Nitpick: Specs for the real world setup would be helpful to compare to existing DCs\n", "limitations": "* The paper doesn't seem to address elastic setups even though their motivation included both heterogeneous and elastic infrastructures.\n* Simulator not as complex as real-world (addressed in paper). Still allows to test parts of the system without stochastic network parameters. These could be synthetically injected though.\n* Need for low communication overhead in DC is not motivated strongly. Centralized methods (QMix for example) still show comparable performance in some application setups.\n", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n* Significant gains by using proposed design over current in-production load balancing algorithms\n* Strong theoretical foundation of formulating load balancing as a multi-agent RL-based Markov potential game\n* Well written paper that puts the pieces of the design in an easy to understand order\n\n## Weaknesses\n* DCs typically have high bandwidth for internal communication. The paper states that centralized communication leads to heavy overhead which is not convincing in the main paper. The evaluation section mentions it in passing as being evaluated in the appendix but I feel it would be helpful to show in the main paper.\n* Not sure if I agree with \"large-scale\" DC networks having only 20 servers. The largest of data centers have thousands of servers and load balancers. This makes the real-world setup slightly less impressive.\n* Fault tolerance not evaluated in the paper (in terms of failed requests leading to incorrect job completion estimates for next time period, network partitions etc.)\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "H6oOOJwVT_d", "reviewer": "Reviewer_WwLw", "summary": "The paper explores the task of multi-agent network load balancing via formulation as a Markov potential game, using workload distribution fairness as a potential function. A MARL algorithm is proposed based on this formulation and provides for fully-decentralized learning. The paper further develops an event-based simulator which, along with a real-world network setup, is used to evaluate the proposed algorithm against several MARL baselines. ", "questions": "- Is there any reason why the work cannot compare against more recent CTDE schemes?\n- Comments on other concerns?\n", "limitations": "n/a", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ Rigorous formulation of network load balancing as MPG with proofs that appear sound.\n+ Generally interesting and well-motivated application for MARL with promising potential\n\nWeaknesses:\n- Concern regarding representativeness of baselines used for evaluation\n- Practical benefits in terms of communication overhead & training time could be more strongly motivated\n\nDetailed Comments:\n\nOverall, the paper was interesting to read and the problem itself is well motivated. Formulation of the problem as an MPG appears sound and offers a variety of important insights with promising applications. There are, however, some concerns regarding evaluation fairness and practical benefits.\n\nThe baselines used for evaluation do not seem to accurately represent the state-of-the-art in CTDE. In particular, there have been a variety of recent works that explore more efficient strategies (e.g., [1-3]) and consistently outperform QMix with relatively low inter-agent communication. Although the proposed work appears effective as a fully-decentralized approach, it is unclear how well it would perform against more competitive CTDE baselines. Comparison against these more recent works would greatly improve the strength of evaluation.\n\nBenefits in terms of reduced communication overhead could also be more strongly motivated. Presumably, communication between agents could be done over purpose-built inter-LB links, thus avoiding QoS degradation due to contention on links between LBs and servers. Even without inter-LB links, the increase in latency demonstrated in Appendix E.2.2 appears relatively low.\n\nRobustness against dynamic changes in network setup are discussed to some degree, but it’s unclear how significant this issue is in a real-world environment. Even in a large-scale setup, the number of LBs/servers is likely to remain fairly constant at the timescales considered in this work (i.e., minutes). Given this, it seems that the paper should at least discuss trade-offs with a longer training time, which could impact the relative benefits of various approaches. \n\nSome confusion in notation:\n-\tAlgorithm 2, L8 should be t = 1,…,H (for horizon)?\n-\tL100, [M] denotes the set of LBs?\n\nMinor notes:\n-\tSome abbreviations are not defined, e.g., “NE” on L73\n-\tSuperscript notation in Eq 6 is not defined until much later (L166), which hindered understanding in an initial read.\n\n[1] S. Zhang et al, “Efficient Communication in Multi-Agent Reinforcement Learning via Variance Based Control”, NeurIPS 2019.\n[2] Z. Ding et al, “Learning Individually Inferred Communication for Multi-Agent Cooperation”, NeurIPS 2020.\n[3] T. Wang et al, “Learning Nearly Decomposable Value Functions Via Communication Minimization”, ICLR 2020.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-a-U_ZPWd6z", "reviewer": "Reviewer_cVpL", "summary": "This paper considers the load balancing problem in a network of multiple heterogenous servers, and multiple load balancers.  The authors formulate the problem as a multi agent reinforcement learning problem, and specifically consider a Markova potential game.\n\nThe settings is that of multiple load balancers, each responsible for sending jobs to a set of servers.  There might be overlaps in the set of servers the various load balancers serve, and the load balancers thus have partial observability of the system state.  Using the cumulative total fairness as the potential function, where fairness is defined as either variance fairness or product fairness, the authors show that the job allocation game where the objective is to minimize the makespan while maximizing the variance fairness or product fairness, is a Markov potential game.  ", "questions": "Are all servers allocated jobs by all LBers? \nWhat do the results look like with partial overlaps? This seems to be a harder problem.  ", "limitations": "The experimentation doesn’t include comparison with classical methods such as LSQ.  It would be interesting to see how a distributed, blind, greedy LSQ compares to the distributed MARL method proposed here, especially since the computation costs are so vastly different.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "A network with multiple load balancers managing load to multiple and overlapping servers is a complex problem.  The interactions between the load balancers is such that a closed form solution to the balancing problem is not evident.  This approach of setting a potential game within a RL environment is interesting and seems novel.\n\nThe authors propose a distributed load balancing method where each agent independently learns a policy, through policy gradient methods. The reward function is set to be per-LB variance or product fairness.  The authors show that maximizing for these local fairness metrics is sufficient tor minimizing makespan, a global metric. \nThe exact model, with respect to overlap of servers among the load balancers, is not clear.  Are all servers allocated jobs by all LBers? What do the results look like with partial overlaps? This seems to be a harder problem.  \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept