# An Input-Queueing TSN Switching Architecture to Achieve Zero Packet Loss for
Timely Traffic

Ming Li, Lei Deng, and Yunghsiang S. Han Ming Li is with the Department of
Electronic and Electrical Engineering, Southern University of Science and
Technology, Shenzhen 518055, China (email: mingli09117@gmail.com). Lei Deng is
with Theory Lab, 2012 Labs, Huawei Technology Co. Ltd, Hong Kong, China
(email: deng.lei2@huawei.com). Yunghsiang S. Han is with Shenzhen Institute
for Advanced Study, University of Electronic Science and Technology of China,
Shenzhen, China (yunghsiangh@gmail.com).

###### Abstract

Zero packet loss with bounded latency is necessary for many applications, such
as industrial control networks, automotive Ethernet, and aircraft
communication systems. Traditional networks cannot meet the such strict
requirement, and thus Time-Sensitive Networking (TSN) emerges. TSN is a set of
standards proposed by IEEE 802 for providing deterministic connectivity in
terms of low packet loss, low packet delay variation, and guaranteed packet
transport. However, to our knowledge, few existing TSN solutions can
deterministically achieve zero packet loss with bounded latency. This paper
fills in this blank by proposing a novel input-queueing TSN switching
architecture, under which we design a TDMA-like scheduling policy (called
M-TDMA) along with a sufficient condition and an EDF-like scheduling policy
(called M-EDF) along with a different sufficient condition to achieve zero
packet loss with bounded latency.

###### Index Terms:

Switch, zero packet loss, bounded latency, time-sensitive networking (TSN),
earliest-deadline first (EDF).

##  I Introduction

Many real-time applications require deterministic services in terms of
deterministic packet delay/latency,111In the paper, we use delay and latency
interchangeably, both of which refers to a time duration, while deadline
refers to a time instance. deterministic packet loss and/or deterministic
packet delay jitter. Zero packet loss with bounded latency is one of the most
challenging goals. Still, it is a must for many applications such as
industrial control networks, automotive Ethernet, and aircraft communication
systems. In such applications, all generated packets need to be delivered
successfully in a bounded delay without any loss to ensure extreme safety.

Traditional networks can only provide best-effort (BE) service and thus cannot
guarantee deterministic quality. Existing Fieldbus solutions, such as PROFIBUS
and CAN, and industrial-Ethernet solutions, such as PROFINET and EtherCAT, can
provide deterministic quality but encounter interoperation issue because they
adopt different sets of standards [1, 2]. To address this issue, IEEE 802
designed Time-Sensitive Networking (TSN) standards [3] mainly working in layer
2, and IETF proposed Deterministic Networking (DetNet) standards [4] primarily
working in layer 3, both of which aim at offering a unified solution over the
widely used Ethernet standards. In this work, we investigate layer-2 switching
solutions and thus pay attention to TSN. TSN is a set of standards proposed by
IEEE 802 for providing deterministic connectivity in terms of low packet loss,
low packet delay variation, and guaranteed packet transport. TSN has been
envisioned as a future solution in industrial communication, and automation
systems [5, 2].

However, to our knowledge, few existing TSN solutions can deterministically
achieve zero packet loss with bounded latency. First, some leading
telecommunication and industrial-automation giants have already marketed TSN
switch products, such as Cisco’s IE 4000 series [6] and Moxa’s TSN-G5008
series [7]. However, according to the public data sheets of these products,
they have only implemented part of TSN standards and have not mentioned that
they can achieve zero packet loss with bounded latency. Second, in the IEEE
802 TSN standards, bounded latency can be guaranteed by 802.1Qav, 802.1Qbu,
802.1Qbv, 802.1Qch, and 802.1Qcr, etc., and ultra-reliability can be secured
by 802.1CB, 802.1Qca, and 802.1Qci, etc. However, such standards cannot meet
the extreme requirement of zero packet loss with bounded latency. Finally,
even in the TSN research community, we only find very few research papers on
achieving zero packet loss with bounded latency. In particular, [8] proposed a
throughput-optimal switching scheduling policy for the particular frame-
synchronized delay-constrained traffic pattern, where statistically zero
packet loss can be achieved by setting the required timely throughput
$R_{i,j}=1/T$ in (6), where $T$ is the common arrival period and hard delay.

This paper fills this blank by proposing an input-queueing TSN switching
architecture to deterministically achieve zero packet loss with bounded
latency for time-sensitive (TS) flows. Specifically, we propose two different
scheduling policies along with two corresponding sufficient conditions to
achieve this goal. The first one is based on the TDMA (Time Division Multiple
Access) scheduling policy, which works for TS flows with arbitrarily different
start times. The second one is based on the EDF (Earliest-Deadline First) [9]
scheduling policy, originally designed for single-processor task execution. We
extend EDF from the many-to-one task-executing system to our many-to-many
switching system. We require that part of TS flows start simultaneously while
the rest of TS flows can begin at any time. These two sufficient conditions do
not have an inclusion relationship and work for different settings.

Figure 1: Our proposed input-queueing TSN switching architecture to achieve
zero packet loss with bounded latency.

In the rest of this paper, we use $[N]$ to denote set $\\{1,2,\cdots,N\\}$ for
any positive integer $N$.

##  II Our Proposed Input-Queueing Switching Architecture

In this section, we describe our proposed input-queueing switching
architecture to achieve zero packet loss for timely traffic, as shown in Fig.
1. Before that, we first describe some assumptions. If a data flow has a hard
delay constraint, we call it a time-sensitive (TS) flow; otherwise, we call it
a best-effort (BE) flow. We further assume that any TS flow is periodic and
the arrival period is equal to its hard delay, which well models practical
scenarios [5, 2, 8]. In addition, we assume that arriving packets of any TS or
BE flow are of fixed and equal length, called cells [11]. Each cell needs one
slot to be delivered from its input to its output in the switch. We now detail
the six critical components of Fig. 1.

Metadata Table. A TS flow from input port $i$ to output port $j$ is called TS
flow $f_{i,j}$. For any TS flow $f_{i,j}$, we associate three metadata fields:
Flow ID (FID), Period $T_{i,j}$, and Offset $\mathsf{offset}_{i,j}$. The
Metadata Table in Fig. 1 records all metadata fields of all TS flows.

TS Matrix. Since we require that the arrival period of any TS flow is equal to
its hard delay, at most one non-expired cell for any TS flow exists in the
switch at any slot. Then, we can construct a binary $N\times N$ matrix to
indicate whether there is a non-expired cell for each TS flow, which is called
the _TS Matrix_. If TS flow $f_{i,j}$ has a non-expired cell, then the entry
in the $i$-th row and $j$-th column, denoted by $c_{i,j}$, is 1; otherwise,
$c_{i,j}=0$. Of course, we should allocate a memory unit to store each non-
expired cell. Without introducing ambiguity, we also call that the TS matrix
stores all non-expired cells.

BE VOQs. For any BE flow, we create a virtual output queue (VOQ), which is a
first-in-first-out (FIFO) queue, to store its cells. Different from TS flows,
a BE flow could have multiple cells simultaneously in the system, since BE
cells will not expire and thus will be kept in the system forever till its
delivery. The VOQ to store the cells of the BE flow from input $i$ to output
$j$ is called VOQi,j. We have in total $N^{2}$ VOQs in the switch, as shown in
Fig. 1. Note that this is the classical input-queued VOQ switch architecture
[12, 11].

Arbiter. To achieve zero packet loss for all TS flows, we need to reduce the
contention level. Thus, not all TS flows can be allowed to enter the switch.
This decision component is called the _arbiter_. Specifically, the arbiter
first determine whether each arriving flow from input $i$ to output $j$ is a
TS flow or a BE flow. If it is a TS flow (called $f_{i,j}$), the arbiter will
look up the Metadata Table to see if it has already been subscribed (i.e., it
has been recorded in the Metadata Table). If it has already been subscribed,
the incoming cell of flow $f_{i,j}$ is directly stored in the TS matrix;
otherwise, the arbiter judges if Sufficient Condition 1 (SC1) as shown in
Theorem 2 or Sufficient Condition 2 (SC2) as shown in Theorem 3 holds when we
add $f_{i,j}$ into the Metadata Table. If either SC1 or SC2 holds, $f_{i,j}$
is subscribed, i.e., it is added to the Metadata Table otherwise, $f_{i,j}$ is
rejected, and the incoming cell is discarded. If this flow is a BE flow
(called $f^{\textsf{BE}}_{i,j}$), the arbiter checks if VOQi,j is full. If
VOQi,j is full, the incoming cell is discarded (i.e., an overflow occurs);
otherwise, it is added to VOQi,j.

Scheduler. The scheduler determines which TS flows and which BE flows are
scheduled at any slot. TS flows have higher priorities than BE flows. Thus,
the scheduler has two steps. In step 1, it selects TS flows. From the arbiter,
we know that all subscribed TS flows in the metadata table must satisfy either
SC1 or SC2. If SC1 holds, the scheduler runs the M-TDMA policy in Sec. III-B
to select some TS flows at this slot. Otherwise, if SC2 holds, the scheduler
runs the M-EDF policy in Sec. III-C to select some TS flows at this slot. If
TS flow $f_{i,j}$ is selected but $c_{i,j}=0$ in the TS matrix, $f_{i,j}$ is
not selected as it does not have a non-expired cell. In step 2, the scheduler
selects BE flows by running the well-known iSLIP policy [12]. If TS flow
$f_{i,j}$ is selected at this slot in step 1, then any BE flow
$f_{i,k}(\forall k)$ and $f_{k^{\prime},j}(\forall k^{\prime})$ cannot be
selected in step 2. Namely, step 2 only utilizes the rest of the available
ports to select BE flows without interfering with all selected TS flows in
step 1. If $X$ TS pairs are selected in step 1, then $N-X$ BE pairs are
selected in step 2. By convention, we require that iSLIP must schedule $N-X$
BE pairs even if some BE pairs have empty VOQs.

Crossbar. All $N$ input-output pairs selected by the scheduler, including $X$
TS flows and $N-X$ BE flows, will be switched by the crossbar fabric. The
delivery in this slot ends.

##  III Two Sufficient Conditions To Achieve Zero Packet Loss

We consider an $N\times N$ input-queued switch whose architecture is shown in
Fig. 1 where $N\geq 2$ is a positive integer. Time is slotted starting from
slot 0. Since TS flows have higher priorities than BE flows, and our goal is
to achieve zero packet loss for TS flows, we only consider TS flows in this
section. Later in Appendix D, we show an example of scheduling both TS flows
and BE flows. Recall that a TS flow from input port $i$ to output port $j$,
called flow $f_{i,j}$, is characterized its offset $\mathsf{offset}_{i,j}$ and
its period $T_{i,j}$, where $\mathsf{offset}_{i,j}\geq 0$ and $T_{i,j}\geq 1$
are both integers. Starting from slot $\mathsf{offset}_{i,j}$, flow $f_{i,j}$
has a new cell arrival every $T_{i,j}$ slots. All flow cells are of the same
size and need one slot to be delivered from its input to its output. In
addition, each cell of flow $f_{i,j}$ has a hard delay of $T_{i,j}$ slots.
Namely, if it cannot be scheduled in $T_{i,j}$ slots after its arrival, it
will be discarded from the switch. To achieve zero packet loss, we should
ensure that no cell will be discarded. We remark that no TS flow may exist
from input $i$ to output $j$. In the rest of this paper, we still call it flow
$f_{i,j}$ and set $\mathsf{offset}_{i,j}=\infty$ and $T_{i,j}=\infty$ by
convention.

Due to the physical limitation of crossbar fabric, in each slot, each input
port can transmit at most one cell to one output port, and each output port
can receive at most one cell from one input port. This is called the _crossbar
constraint_. Following [8], we can equivalently describe the crossbar
constraint by a matching characterized by a matrix222For simplicity, we call
it matching $\boldsymbol{M}$, instead of matching matrix $\boldsymbol{M}$.
$\boldsymbol{M}=(m_{i,j}\in\\{0,1\\}:i,j\in[N])$ of an $N$-by-$N$ bipartite
graph (see [8, Fig. 1(b)]), where $m_{i,j}=1$ means that flow $f_{i,j}$ is
selected/scheduled and $m_{i,j}=0$ means that flow $f_{i,j}$ is not
selected/scheduled. We also call that matching $\boldsymbol{M}$ contains flow
$f_{i,j}$ if $m_{i,j}=1$. Alternatively, we also call that flow $f_{i,j}$ is
in matching $\boldsymbol{M}$, denoted by $f_{i,j}\in\boldsymbol{M}$ with a
slight abuse of notation. A binary square matrix is a matching if and only if
each row or column contains at most one 1.

Thus, in each slot, the scheduler of Fig. 1 needs to select a matching
$\boldsymbol{M}\in\mathcal{M}$, where $\mathcal{M}$ is the set of all
matchings. In addition, a perfect matching $\boldsymbol{M}$ is a matching with
$N$ 1’s, i.e., $\sum_{i=1}^{N}\sum_{j=1}^{N}m_{i,j}=N$. The set of all perfect
matchings is denoted by $\mathcal{M}^{p}\subset\mathcal{M}$. It is also easy
to see that a binary square matrix is a perfect matching if and only if each
row or column contains exactly one 1. Next we first give the definition for
_flow decomposition sets_ and then propose our two scheduling policies along
with their corresponding sufficient conditions to achieve zero packet loss for
all TS flows.

###  III-A Flow Decomposition Set

A set of $N$ perfect matchings, denoted by
$\mathcal{D}=\\{\boldsymbol{M}_{1},\boldsymbol{M}_{2},\cdots,\boldsymbol{M}_{N}\\}$,
is called a _flow decomposition set_ if the result of sum of all
$M_{i}\in\mathcal{D}\subset\mathcal{M}^{p}$ is an $N\times N$ all-one matrix,
i.e., $\boldsymbol{M}_{i}\in\mathcal{D}\subset\mathcal{M}^{p},\forall
i\in[N]$, and

$\sum_{i=1}^{N}\boldsymbol{M}_{i}=\boldsymbol{1}_{N\times N}.$ (1)

The right-hand side of (1) is an $N\times N$ all-one matrix, and the addition
operation of the left-hand side of (1) is in the real number field. Constraint
(1) has two properties. First, any flow in a perfect matching
$\boldsymbol{M}_{i}\in\mathcal{D}$ is different from any flow in another
perfect matching $\boldsymbol{M}_{j}\in\mathcal{D}$ with $j\neq i$. Second,
any flow in the system (within total $N^{2}$ flows) exists in a matching of
set $\mathcal{D}$. In other words, if we schedule all matchings in
$\mathcal{D}$ once, any flow in the system is scheduled precisely once. Since
the set is unordered, it does not matter which perfect matching is called
$\boldsymbol{M}_{i}$ in $\mathcal{D}$. To facilitate further analysis, for any
flow decomposition set $\mathcal{D}$, we require that _the perfect matching in
$\mathcal{D}$, which contains flow $f_{1,i}$, is called $\boldsymbol{M}_{i}$
for any $i\in[N]$._

In addition, for ease of presentation, with a slight abuse of matrix notation,
we define a _perfect-matching matrix_ $\boldsymbol{L}$ as an $N$-by-$N$ matrix
whose entry in the $i$-th row and $j$-th column is a perfect matching in
$\mathcal{M}^{p}$ containing flow $f_{i,j}$.

For any flow decomposition set
$\mathcal{D}=\\{\boldsymbol{M}_{1},\boldsymbol{M}_{2},\cdots,\boldsymbol{M}_{N}\\}$,
we can construct a unique perfect-matching matrix whose entry is required to
be a perfect matching in $\mathcal{D}$, denoted by
$\boldsymbol{L}(\mathcal{D})$. For example, the flow decomposition set
represented by (12) in Appendix A yields to the following perfect-matching
matrix,

$\boldsymbol{L}(\mathcal{D})=(l_{i,j}:i,j\in[N])=\left(\begin{matrix}\boldsymbol{M}_{1}&\boldsymbol{M}_{2}&\boldsymbol{M}_{3}&\boldsymbol{M}_{4}\\\
\boldsymbol{M}_{4}&\boldsymbol{M}_{1}&\boldsymbol{M}_{2}&\boldsymbol{M}_{3}\\\
\boldsymbol{M}_{3}&\boldsymbol{M}_{4}&\boldsymbol{M}_{1}&\boldsymbol{M}_{2}\\\
\boldsymbol{M}_{2}&\boldsymbol{M}_{3}&\boldsymbol{M}_{4}&\boldsymbol{M}_{1}\\\
\end{matrix}\right).$

(2)

Later in Sec. III-B and Sec. III-C, we will construct a scheduling policy
according to $\boldsymbol{L}(\mathcal{D})$: in each slot, the scheduler of
Fig. 1 selects an $\boldsymbol{M}_{i}$ and schedules the flows $f_{i,j}$
according to the positions of $\boldsymbol{M}_{i}$ in
$\boldsymbol{L}(\mathcal{D})$. Clearly, the first row of
$\boldsymbol{L}(\mathcal{D})$ must be
$(\boldsymbol{M}_{1},\boldsymbol{M}_{2},\cdots,\boldsymbol{M}_{N})$ and each
row or column of $\boldsymbol{L}(\mathcal{D})$ contains all
$\boldsymbol{M}_{i}$’s for $i\in[N]$. Following [13], we know that
$\boldsymbol{L}(\mathcal{D})$ is a Latin square333Recall that a Latin square
of order $N$ is an $N\times N$ square matrix containing a set of $N$ different
symbols/numbers in every row and column. where the underlying symbol set is
$\mathcal{D}=\\{\boldsymbol{M}_{1},\boldsymbol{M}_{2},\cdots,\boldsymbol{M}_{N}\\}$.
On the contrary, we can also construct a unique flow decomposition set
$\mathcal{D}(\boldsymbol{L})$ for any Latin square $\boldsymbol{L}$ of order
$N$ whose first row is fixed as
$(\boldsymbol{M}_{1},\boldsymbol{M}_{2},\cdots,\boldsymbol{M}_{N})$.

###### Theorem 1

For any $N\times N$ switch, there exists a bijection between the set of all
its flow decomposition sets and the set of all Latin squares of order $N$
whose first rows are fixed as
$(\boldsymbol{M}_{1},\boldsymbol{M}_{2},\cdots,\boldsymbol{M}_{N})$.

###### Proof:

Please see Appendix B. ∎

Therefore, the total number of flow decomposition sets is equal to the total
number of Latin squares of order $N$ whose first rows are fixed as
$(\boldsymbol{M}_{1},\boldsymbol{M}_{2},\cdots,\boldsymbol{M}_{N})$. In the
research area of Latin squares, we can count the total number of Latin squares
and the total number of reduced-form Latin squares (whose first row and the
first column are both in the natural order) for up to $N=11$. It is
straightforward to obtain that the total number of Latin squares of order $N$
whose first row is fixed as
$(\boldsymbol{M}_{1},\boldsymbol{M}_{2},\cdots,\boldsymbol{M}_{N})$ is equal
to $(N-1)!$ times the total number of reduced-form Latin squares of order $N$.
Therefore, based on [13], we can count the total number of
$\boldsymbol{L}(\mathcal{D})$ for an $N\times N$ switch, denoted by
$\alpha(N)$ for up to $N=11$. Since the TSN switches are generally small, we
list $\alpha(N)$ for up to $N=7$ in Table I.

TABLE I: The total number of flow decomposition sets, $\alpha(N)$, for $N=1,2,\cdots,7$ $N$ | 2 | 3 | 4 | 5 | 6 | 7
---|---|---|---|---|---|---
$\alpha(N)$ | 1 | 2 | 24 | 1,344 | 1,128,960 | 12,198,297,600

###  III-B Sufficient Condition 1 and Matching-based TDMA (M-TDMA) Scheduling
Policy

We now propose our Sufficient Condition 1 (SC1) and its corresponding
scheduling policy to achieve zero packet loss for timely traffic, as shown in
Theorem 2 shortly.

First, for any flow decomposition set
$\mathcal{D}=\\{\boldsymbol{M}_{1},\boldsymbol{M}_{2},\cdots,\boldsymbol{M}_{N}\\}$,
we define a matching-based TDMA (M-TDMA) scheduling policy as follow444In
fact, we can schedule such $N$ perfect matchings in any permutation order as
long as the order is repeated every $N$ slots.: $\forall q=0,1,\cdots$

  * •

Schedule $\boldsymbol{M}_{1}$ at slots $qN$,

  * •

Schedule $\boldsymbol{M}_{2}$ at slots $qN+1$,

  * •

$\cdots$

  * •

Schedule $\boldsymbol{M}_{N}$ at slots $qN+(N-1)$,

where the M-TDMA scheduling policy starts at slot 0. Note that every $N$ slots
consist of a scheduling period and $q$ is the index of scheduling periods.
Matchings $(\boldsymbol{M}_{1},\cdots,\boldsymbol{M}_{N})$ are repeatedly
scheduled in order in every scheduling period. That is why we call it a
matching-based TDMA policy.

######  Theorem 2 (Sufficient Condition 1 (SC1))

For any $N\times N$ switch with TS traffic offset matrix
$\boldsymbol{\mathsf{offset}}=(\mathsf{offset}_{i,j}:i,j\in[N])$ and traffic
period matrix $\boldsymbol{T}=(T_{i,j}:i,j\in[N])$, if

$T_{i,j}\geq N,\quad\forall i,j\in[N],$ (3)

then the M-TDMA policy for any flow decomposition set
$\mathcal{D}=\\{\boldsymbol{M}_{1},\boldsymbol{M}_{2},\cdots,\boldsymbol{M}_{N}\\}$
achieves zero packet loss.

###### Proof:

We give a proof sketch here and defer the detailed proof to Appendix E in our.

M-TDMA policy guarantees that each flow is scheduled within $N$ slots staring
from any slot. Thus, any packet of any flow $f_{i,j}$ will be scheduled within
$N$ slots after its arrival, which happens before its expiration and the next
packet’s arrival of this flow due to (3). Thus, we achieve zero packet loss
for all timely flows. ∎

###  III-C Sufficient Condition 2 and Matching-based EDF (M-EDF) Scheduling
Policy

M-TDMA scheduling policy only works for the situation of $T_{i,j}\geq
N,\forall i,j\in[N]$. It cannot guarantee zero packet loss if there exists a
TS flow $f_{i,j}$ with period $T_{i,j}<N$. This does not mean that no policy
can achieve zero packet loss if some $T_{i,j}<N$. We now describe a different
sufficient condition on scheduling policy to address this issue. We first
define a $T$-vector as follows.

###### Definition 1

For any positive integer $N$, a $T$-vector is a 1-by-$N$ vector, denoted by
$\overrightarrow{T}=(T_{1},T_{2},\cdots,T_{N})$, if any $T_{k}$ is a positive
integer and

$\sum_{k=1}^{N}\frac{1}{T_{k}}\leq 1.$ (4)

For any $T$-vector $\overrightarrow{T}=(T_{1},T_{2},\cdots,T_{N})$, we
construct a _virtual_ single-processor task scheduling system [9].
Specifically, a single processor needs to execute $N$ periodic delay-
constrained tasks where task $k$ has period $T_{k}$ for all $k\in[N]$.
Starting from slot 0, task $k$ generates a request every $T_{k}$ slots. The
processor needs one slot to complete a request, and each request at task $k$
has a hard delay of $T_{k}$ slots. Thus, task $k$ is analogous to the timely
traffic with zero offset and period $T_{k}$. Liu and Layland in [9] proposed
the famous earliest-deadline first (EDF) scheduling policy and proved that EDF
completes all requests (equivalent to achieve zero packet loss) if
$\overrightarrow{T}=(T_{1},T_{2},\cdots,T_{N})$ is a $T$-vector (see [9,
Theorem 7]). At each slot, EDF schedules the request of all $N$ tasks, which
has the earliest deadline and breaks ties arbitrarily. We now define
$a^{\textsf{EDF}}_{t}(\overrightarrow{T})\in[N]$ as the index of the scheduled
task at slot $t$ when EDF schedules all $N$ tasks spanned by $T$-vector
$\overrightarrow{T}$. An example of
$\left(a^{\textsf{EDF}}_{t}(\overrightarrow{T}):t=0,1,2,\cdots\right)$
sequence is shown in Appendix C.

Now we propose Sufficient Condition 2 (SC2) and the corresponding matching-
based EDF (M-EDF) scheduling policy.

######  Theorem 3 (Sufficient Condition 2 (SC2))

For any $N\times N$ switch with TS traffic offset matrix
$\boldsymbol{\mathsf{offset}}=(\mathsf{offset}_{i,j}:i,j\in[N])$ and traffic
period matrix $\boldsymbol{T}=(T_{i,j}:i,j\in[N])$, if there exists a flow
decomposition set
$\mathcal{D}=\\{\boldsymbol{M}_{1},\boldsymbol{M}_{2},\cdots,\boldsymbol{M}_{N}\\}$
and a $T$-vector $\overrightarrow{T}=(T_{k}:k\in[N])$, where $T_{k}$ is the
corresponding scheduling period of $\boldsymbol{M}_{k}$, such that for any
flow $f_{i,j}\in\boldsymbol{M}_{k}$, either

$\quad T_{i,j}=T_{k}\text{ and }\mathsf{offset}_{i,j}=0$ (5)

or

$\quad T_{i,j}\geq 2T_{k}-1\text{ and }\mathsf{offset}_{i,j}\geq 0$ (6)

holds, then the M-EDF policy, which schedules matching
$\boldsymbol{M}_{a^{\textsf{EDF}}_{t}(\overrightarrow{T})}$ at any slot $t$,
achieves zero packet loss.

###### Proof:

We give a proof sketch here and defer the full proof to Appendix F.

If condition (5) holds, the $s$-th packet of flow $f_{i,j}$ in the real
switching system arrives and expires at exactly the same time as the $s$-th
request of task $k$ in the _virtual_ single-processor task scheduling system.
Since EDF achieves zero packet loss for any $T$-vector, M-EDF also achieves
zero packet loss for all timely flows.

If condition (6) holds, M-EDF policy guarantees that flow $f_{i,j}$ is
scheduled once within $2T_{k}-1$ slots staring from any slot. Thus, any packet
of any flow $f_{i,j}$ will be scheduled within $2T_{k}-1$ slots after its
arrival, which happens before its expiration and the next packet’s arrival of
this flow due to (6). Thus, we achieve zero packet loss for all timely flows.
∎

We remark that Sufficient Condition 2 in Theorem 3 is more difficult to check
than Sufficient Condition 1 in Theorem 2. For any offset matrix
$\boldsymbol{\mathsf{offset}}$ and any period matrix $\boldsymbol{T}$, we need
to find a $T$-vector and flow decomposition set $\mathcal{D}$ to satisfy (5)
or (6). In this paper, we propose a brute-force algorithm to find such a
$T$-vector and flow decomposition set $\mathcal{D}$, which works for small
$N$, e.g., when $N\leq 6$. Following Theorem 1, we first enumerate all flow
decomposition sets based on enumeration of all Latin squares of order $N$
whose first rows are fixed as
$(\boldsymbol{M}_{1},\boldsymbol{M}_{2},\cdots,\boldsymbol{M}_{N})$. For any
perfect matching $\boldsymbol{M}_{k}$ in each flow decomposition set
$\mathcal{D}=\\{\boldsymbol{M}_{1},\boldsymbol{M}_{2},\cdots,\boldsymbol{M}_{N}\\}$,
we set a $T_{k}$ value as follows. We first define two values,

$t_{1}=\min_{f_{i,j}\in\boldsymbol{M}_{k}:i,j\in[N],\mathsf{offset}_{i,j}=0}T_{i,j},$
(7)

which is set to be $\infty$ if $\mathsf{offset}_{i,j}>0$ for all $i,j\in[N]$,
and

$t_{2}=\min_{f_{i,j}\in\boldsymbol{M}_{k}:i,j\in[N]}\left\lfloor\frac{T_{i,j}+1}{2}\right\rfloor.$
(8)

We can see that $t_{1}\geq t_{2}$. It is also easy to verify that the maximum
$T_{k}$, such that either condition (5) or condition (6) for any flow
$f_{i,j}\in\boldsymbol{M}_{k}$, is either $t_{1}$ or $t_{2}$. Clearly, if we
set $T_{k}=t_{2}$, any flow $f_{i,j}\in\boldsymbol{M}_{k}$ satisfies condition
(6). Now we only need to check if we can set $T_{k}=t_{1}$. We need to
consider each flow $f_{i,j}\in\boldsymbol{M}_{k}$ and check whether condition
(5) or condition (6) holds when $T_{k}=t_{1}$. If so, we set $T_{k}=t_{1}$;
otherwise, we set $T_{k}=t_{2}$.

After that, we construct a vector
$\overrightarrow{T}=(T_{1},T_{2},\cdots,T_{N})$. We then check if it is a
$T$-vector based on (4). If so, we have found such a $T$-vector
$\overrightarrow{T}=(T_{1},T_{2},\cdots,T_{N})$ and a flow decomposition set
$\mathcal{D}$ to meet Sufficient Condition 2 in Theorem 3. If we cannot find
such a $T$-vector to meet (4) for all flow decomposition sets, the given
offset matrix $\boldsymbol{\mathsf{offset}}$ and period matrix
$\boldsymbol{T}$ cannot meet Sufficient Condition 2 in Theorem 3. How to find
more efficient algorithms to check sufficient condition 2 for large $N$ is
left as a future direction.

##  IV Examples

In the previous section, we have proposed two sufficient conditions. However,
we cannot say that one is more strict than the other. In this section, we will
illustrate two examples to justify this argument. The feasibility of these two
examples has been verified by the computer simulation.

###### Example 1

Consider a $4\times 4$ switch with TS traffic whose offset matrix and period
matrix are respectively set as follows,

(17)

Since $T_{i,j}\geq N=4$ for all flow $f_{i,j}$, (17) satisfies Sufficient
Condition 1 in Theorem 2, any M-TDMA policy of any flow decomposition set
(e.g., (2)) achieves zero packet loss for all TS flows. However, since
$\mathsf{offset}_{i,j}\geq 0$ for all flow $f_{i,j}$, for any matching
$\boldsymbol{M}_{k}$ of any flow decomposition $\mathcal{D}$, the resulting
$T_{k}$ is at least 2 according to (7) and (8), and thus
$\sum_{k=1}^{4}\frac{1}{T_{k}}\geq 2$. Hence, we cannot find a $T$-vector to
meet (4) for all flow decomposition sets. Therefore, Sufficient Condition 2
does not hold for this example.

###### Example 2

Consider a $4\times 4$ switch with TS traffic whose offset matrix and period
matrix are respectively set as follows,

(26)

We can see that this example cannot satisfy Sufficient Condition 1 since there
exists $T_{i,j}<N=4$. However, we can find the following flow decomposition
set in its corresponding Latin square,

$\boldsymbol{L}=\left(\begin{matrix}\boldsymbol{M}_{1}&\boldsymbol{M}_{2}&\boldsymbol{M}_{3}&\boldsymbol{M}_{4}\\\
\boldsymbol{M}_{4}&\boldsymbol{M}_{1}&\boldsymbol{M}_{2}&\boldsymbol{M}_{3}\\\
\boldsymbol{M}_{3}&\boldsymbol{M}_{4}&\boldsymbol{M}_{1}&\boldsymbol{M}_{2}\\\
\boldsymbol{M}_{2}&\boldsymbol{M}_{3}&\boldsymbol{M}_{4}&\boldsymbol{M}_{1}\\\
\end{matrix}\right),$ (27)

and its resulting $T$-vector $(2,4,8,8)$. We can check that either condition
(5) or condition (6) holds for any flow $f_{i,j}\in\boldsymbol{M}_{k}$. Thus,
this example satisfies Sufficient Condition 2 and the corresponding M-EDF
policy achieves zero packet loss for all TS flows. In fact, the scheduled
matching at each slot is shown in Appendix C.

We remark that our independent simulations confirm that M-TDMA (resp. M-EDF)
indeed achieves zero packet loss for all TS flows in Example 1 (resp. Example
2).

In addition, we also illustrate an example to schedule both TS and BE flows in
Appendix D.

##  V Conclusion

Achieving zero packet loss for timely traffic is an important but challenging
requirement in TSN applications. In this paper, for the first time, we propose
an input-queueing TSN switching architecture to achieve this goal.
Specifically, we propose two sufficient conditions and two corresponding
scheduling policies (called M-TDMA and M-EDF) to achieve zero packet loss for
all timely traffics. These two sufficient conditions have non-empty
intersections, and no one is more strict than the other. Thus, both conditions
are not necessary for achieving zero packet loss for timely traffic. It is
very interesting and important to characterize a sufficient and necessary
condition to achieve zero packet loss for timely traffic in the future.

## References

  * [1] J.-D. Decotignie, “The many faces of industrial Ethernet [past and present],” _IEEE Industrial Electronics Magazine_ , vol. 3, no. 1, pp. 8–19, 2009.
  * [2] D. Bruckner, M.-P. Stănică, R. Blair, S. Schriegel, S. Kehrer, M. Seewald, and T. Sauter, “An introduction to OPC UA TSN for industrial communication systems,” _Proceedings of the IEEE_ , vol. 107, no. 6, pp. 1121–1131, 2019.
  * [3] “TSN task group,” https://1.ieee802.org/tsn/.
  * [4] “DetNet,” https://datatracker.ietf.org/wg/detnet/about/.
  * [5] L. Lo Bello and W. Steiner, “A perspective on IEEE time-sensitive networking for industrial communication and automation systems,” _Proceedings of the IEEE_ , vol. 107, no. 6, pp. 1094–1120, 2019.
  * [6] “Cisco industrial Ethernet 4000 series switches data sheet,” https://www.cisco.com/c/en/us/products/collateral/switches/industrial-ethernet-4000-series-switches/datasheet-c78-733058.html.
  * [7] “TSN-G5008 series,” https://www.moxa.com/en/products/industrial-network-infrastructure/ethernet-switches/layer-2-managed-switches/tsn-g5008-series.
  * [8] L. Deng, W. S. Wong, P.-N. Chen, Y. S. Han, and H. Hou, “Delay-constrained input-queued switch,” _IEEE Journal on Selected Areas in Communications_ , vol. 36, no. 11, pp. 2464–2474, 2018.
  * [9] C. L. Liu and J. W. Layland, “Scheduling algorithms for multiprogramming in a hard-real-time environment,” _Journal of the ACM_ , vol. 20, no. 1, pp. 46–61, 1973.
  * [10] M. Li and L. Deng, “An input-queueing TSN switching architecture to achieve zero packet loss for timely traffic,” _arXiv preprint arXiv:2206.09759_ , 2022.
  * [11] N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand, “Achieving 100% throughput in an input-queued switch,” _IEEE Transactions on Communications_ , vol. 47, no. 8, pp. 1260–1267, 1999.
  * [12] N. McKeown, “The iSLIP scheduling algorithm for input-queued switches,” _IEEE/ACM Transactions on Networking_ , vol. 7, no. 2, pp. 188–201, 1999\.
  * [13] B. D. McKay and I. M. Wanless, “On the number of Latin squares,” _Annals of Combinatorics_ , vol. 9, no. 3, pp. 335–344, 2005.

###  -A An Example of Flow Decomposition Set and Its Corresponding Latin
Square

Consider a $4\times 4$ switch, i.e., $N=4$. We construct the following 4
perfect matchings,

$\displaystyle\boldsymbol{M}_{1}=\left(\begin{matrix}1&0&0&0\\\ 0&1&0&0\\\
0&0&1&0\\\ 0&0&0&1\\\
\end{matrix}\right),\boldsymbol{M}_{2}=\left(\begin{matrix}0&1&0&0\\\
0&0&1&0\\\ 0&0&0&1\\\ 1&0&0&0\\\ \end{matrix}\right),$
$\displaystyle\boldsymbol{M}_{3}=\left(\begin{matrix}0&0&1&0\\\ 0&0&0&1\\\
1&0&0&0\\\ 0&1&0&0\\\
\end{matrix}\right),\boldsymbol{M}_{4}=\left(\begin{matrix}0&0&0&1\\\
1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\ \end{matrix}\right).$ (28)

We can examine that

$\boldsymbol{M}_{1}+\boldsymbol{M}_{2}+\boldsymbol{M}_{3}+\boldsymbol{M}_{4}=\left(\begin{matrix}1&1&1&1\\\
1&1&1&1\\\ 1&1&1&1\\\ 1&1&1&1\\\ \end{matrix}\right),$ (29)

where the addition is operated in the real field. Thus,
$\mathcal{D}=\\{\boldsymbol{M}_{1},\boldsymbol{M}_{2},\boldsymbol{M}_{3},\boldsymbol{M}_{4}\\}$
is a flow decomposition set.

Now we can construct its Latin square whose entry in the $i$-th row and $j$-th
column is the perfect matching in $\mathcal{D}$ containing flow $f_{i,j}$,
i.e.,

$\displaystyle\boldsymbol{L}(\mathcal{D})=\left(\begin{matrix}\boldsymbol{M}_{1}&\boldsymbol{M}_{2}&\boldsymbol{M}_{3}&\boldsymbol{M}_{4}\\\
\boldsymbol{M}_{4}&\boldsymbol{M}_{1}&\boldsymbol{M}_{2}&\boldsymbol{M}_{3}\\\
\boldsymbol{M}_{3}&\boldsymbol{M}_{4}&\boldsymbol{M}_{1}&\boldsymbol{M}_{2}\\\
\boldsymbol{M}_{2}&\boldsymbol{M}_{3}&\boldsymbol{M}_{4}&\boldsymbol{M}_{1}\\\
\end{matrix}\right).$ (30)

Clearly, the constructed Latin square is unique because any flow belongs to
exactly one perfect matching in a flow decomposition set.

In addition, since $l_{i,j}$ is the perfect matching containing flow
$f_{i,j}$, we can easily see that all same entries of
$\boldsymbol{L}(\mathcal{D})$ in (30) reconstruct the corresponding perfect
matching. For example, in (30), we can see that
$l_{1,1}=l_{2,2}=l_{3,3}=l_{4,4}=\boldsymbol{M}_{1}$, and thus we can
reconstruct $\tilde{\boldsymbol{M}}_{1}$ as

$\tilde{\boldsymbol{M}}_{1}=\left(\begin{matrix}1&0&0&0\\\ 0&1&0&0\\\
0&0&1&0\\\ 0&0&0&1\\\ \end{matrix}\right),$ (31)

which is the same as $\boldsymbol{M}_{1}$ in (28). This reconstruction step
will be used to prove Theorem 1 in Appendix -B.

###  -B Proof of Theorem 1

First, according the construction procedure in Sec. III-A, it is easily to see
that for any flow decomposition set $\mathcal{D}$, its corresponding Latin
square $\boldsymbol{L}(\mathcal{D})$ is unique and the first row is
$(\boldsymbol{M}_{1},\boldsymbol{M}_{2},\cdots,\boldsymbol{M}_{N})$.

To prove Theorem 1, we now only need to show that for any Latin square
$\tilde{\boldsymbol{L}}$ of order $N$ whose first row is fixed as
$(\boldsymbol{M}_{1},\boldsymbol{M}_{2},\cdots,\boldsymbol{M}_{N})$, there
exists a unique flow decomposition set $\mathcal{D}$ such that

$\boldsymbol{L}(\mathcal{D})=\tilde{\boldsymbol{L}}.$ (32)

We first construct a flow decomposition set $\tilde{\mathcal{D}}$ such that
(32) holds. This can be done as follows. We construct an $N\times N$ matrix
$\tilde{\boldsymbol{M}}_{k}=(\tilde{m}_{i,j}\in\\{0,1\\}:i,j=1,2,\cdots,N)$
for any $k\in[N]$ where

$\tilde{m}_{i,j}=\left\\{\begin{array}[]{ll}1,&\hbox{If
$\tilde{l}_{i,j}=\boldsymbol{M}_{k}$;}\\\
0,&\hbox{Otherwise.}\end{array}\right.$ (33)

Namely, we extract all entries whose value is $\boldsymbol{M}_{k}$ in Latin
square $\tilde{\boldsymbol{L}}$ to construct the index matrix
$\tilde{\boldsymbol{M}}_{k}$ (see an example in (31)). Since
$\tilde{\boldsymbol{L}}$ is a Latin square whose any row or column does not
have the same entry, we can see that $\tilde{\boldsymbol{M}}_{k}$ is a perfect
matching. Then we construct the flow decomposition set
$\mathcal{\tilde{D}}=\\{\tilde{\boldsymbol{M}}_{1},\tilde{\boldsymbol{M}}_{2},\cdots,\tilde{\boldsymbol{M}}_{N}\\}$.
According the construction procedure in Sec. III-A, we can see that
$\boldsymbol{L}(\mathcal{\tilde{D}})=\tilde{\boldsymbol{L}}$. Namely, there
exists at least one flow decomposition set $\mathcal{\tilde{D}}$ such that
(32) holds.

Now we prove that for any two different flow decomposition sets
$\mathcal{D}^{\prime}$ and $\mathcal{D}^{\prime\prime}$, their constructed
Latin squares must be different, i.e.,

$\boldsymbol{L}(\mathcal{D}^{\prime})\neq\boldsymbol{L}(\mathcal{D}^{\prime\prime}).$
(34)

Let us denote

$\boldsymbol{L}^{\prime}\triangleq\boldsymbol{L}(\mathcal{D}^{\prime}),\quad\boldsymbol{L}^{\prime\prime}\triangleq\boldsymbol{L}(\mathcal{D}^{\prime\prime}).$
(35)

Since flow decomposition sets $\mathcal{D}^{\prime}$ and
$\mathcal{D}^{\prime\prime}$ are different, there must exist a flow $f_{i,j}$
such that the matching containing flow $f_{i,j}$ in $\mathcal{D}^{\prime}$,
denoted as $\boldsymbol{M}^{\prime}$, is different from the matching
containing flow $f_{i,j}$ in $\mathcal{D}^{\prime\prime}$, denoted as
$\boldsymbol{M}^{\prime\prime}$, i.e.,

$\boldsymbol{M}^{\prime}\neq\boldsymbol{M}^{\prime\prime}.$ (36)

According the construction procedure in Sec. III-A, the entry in the $i$-th
row and $j$-th column of the constructed Latin square is the perfect matching
containing flow $f_{i,j}$. Thus,

$l_{i,j}^{\prime}=\boldsymbol{M}^{\prime},\quad
l_{i,j}^{\prime\prime}=\boldsymbol{M}^{\prime\prime}.$ (37)

Therefore, $\boldsymbol{L}^{\prime}\neq\boldsymbol{L}^{\prime\prime}$ and thus
(34) holds. Hence, there exists a unique flow decomposition set $\mathcal{D}$
such that (32) holds.

The proof is thus completed.

###  -C An Example of Virtual Single-processor Task-execution System under EDF
Scheduling Policy

We consider $N=4$ and a $T$-vector

$\overrightarrow{T}=(T_{1},T_{2},T_{3},T_{4})=(2,4,8,8).$ (38)

Note that we can check that (4) holds and thus (38) is indeed a $T$-vector.
Based on this $T$-vector $\overrightarrow{T}$, we construct a virtual single-
processor task-execution system which has four tasks with periods specified by
$\overrightarrow{T}$. We illustrate the arrived requests of all four tasks in
the virtual single-processor system in Fig. 2.

At each slot, EDF scheduling policy schedules the request of all $N$ tasks who
has the earliest deadline and breaks ties arbitrarily. Then, we can construct
the index of the scheduled task at any slot $t$, i.e.,
$a^{\textsf{EDF}}_{t}(\overrightarrow{T})\in[N]$, as shown in the bottom of
Fig. 2.

Figure 2: An example of the virtual single-processor task-execution system.

###  -D An Example to Schedule both TS Flows and BE Flows

In the main parts of this paper, we consider that only TS flows exist in the
system. However, we remark that our proposed TSN switching architecture and
scheduling polices can co-schedule both TS flows and BE flows, as shown in
Fig. 1. We give higher priorities to TS flows than BE flows. If the M-TDMA or
M-EDF policy cannot fully utilize the switching ports to schedule TS flows in
Step 1, the iSLIP policy will schedule BE flows by utilizing the rest of
available ports in Step 2. Here we use a simple example to illustrate this
two-step scheduler of Fig. 1.

We again consider a $4\times 4$ switch but with only TS flows and BE flows
related to input 1. Specifically, there are three TS flows
$f_{1,1},f_{1,2},f_{1,3}$ with offset and period matrices,

(47)

In addition, we have four BE flows
$f^{\textsf{BE}}_{1,1},f^{\textsf{BE}}_{1,2},f^{\textsf{BE}}_{1,3},f^{\textsf{BE}}_{1,4}$,
whose arrivals can be arbitrary since no cell has a strict deadline. We show a
collection of arrivals of these four BE flows in Fig. 3.

Figure 3: An example to schedule both TS flows and BE flows.

We can see that (47) does not satisfy SC1 but satisfy SC2 by constructing the
following flow decomposition set (in its Latin-square form),

$\boldsymbol{L}=\left(\begin{matrix}\boldsymbol{M}_{1}&\boldsymbol{M}_{2}&\boldsymbol{M}_{3}&\boldsymbol{M}_{4}\\\
\boldsymbol{M}_{4}&\boldsymbol{M}_{1}&\boldsymbol{M}_{2}&\boldsymbol{M}_{3}\\\
\boldsymbol{M}_{3}&\boldsymbol{M}_{4}&\boldsymbol{M}_{1}&\boldsymbol{M}_{2}\\\
\boldsymbol{M}_{2}&\boldsymbol{M}_{3}&\boldsymbol{M}_{4}&\boldsymbol{M}_{1}\\\
\end{matrix}\right),$ (48)

and the $T$-vector,
$\overrightarrow{T}=(T_{1},T_{2},T_{3},T_{4})=(3,6,6,\infty).$ Clearly, we
have that TS flows $f_{1,1}\in\boldsymbol{M}_{1}$,
$f_{1,2}\in\boldsymbol{M}_{2}$, and $f_{1,3}\in\boldsymbol{M}_{3}$.

At any slot $t$, we first use the M-EDF policy to schedule TS flows and then
use the iSLIP policy to schedule BE flows. The index of the scheduled matching
by the M-EDF policy at any slot $t$, i.e.,
$a^{\textsf{EDF}}_{t}(\overrightarrow{T})\in[N]$, and the scheduled BE flow at
any slot $t$, denoted as
$b^{\textsf{iSLIP}}_{t}\in\\{f^{\textsf{BE}}_{1,1},f^{\textsf{BE}}_{1,2},f^{\textsf{BE}}_{1,3},f^{\textsf{BE}}_{1,4}\\}$,
are shown in the last two lines of Fig. 3, respectively.

For example, at slot 4, since all three TS flows do not have any cell in the
system, $a^{\textsf{EDF}}_{4}$ can be set arbitrarily and no TS flow will be
scheduled at this slot. Therefore, input 1 is not utilized by M-EDF and thus
can be utilized by iSLIP to schedule BE flows. Here, we have one cell of BE
flow $f^{\textsf{BE}}_{1,1}$, one cell of BE flow $f^{\textsf{BE}}_{1,2}$, one
cell of BE flow $f^{\textsf{BE}}_{1,3}$, and one cell of BE flow
$f^{\textsf{BE}}_{1,4}$ in the system. The iSLIP policy selects
$b^{\textsf{iSLIP}}_{4}=f^{\textsf{BE}}_{1,1}$ at slot 4. Later at slot 5,
again no TS cell exists in the system and iSLIP schedules
$b^{\textsf{iSLIP}}_{5}=f^{\textsf{BE}}_{1,2}$.

###  -E Proof of Theorem 2

Any flow $f_{i,j}$ is contained in one of perfect matchings in
$\mathcal{D}=\\{\boldsymbol{M}_{1},\boldsymbol{M}_{2},\cdots,\boldsymbol{M}_{N}\\}$,
say $\boldsymbol{M}_{k}$. According to the M-TDMA policy, perfect matching
$\boldsymbol{M}_{k}$ is scheduled at slots $qN+(k-1),q=0,1,\cdots$. Since
$T_{i,j}\geq N$, the $s$-th $(s=0,1,2,\cdots)$ cell (called cell $s$) of flow
$f_{i,j}$ arrives at the beginning of slot $\mathsf{offset}_{i,j}+sT_{i,j}$
and expires at the end of slot $\mathsf{offset}_{i,j}+(s+1)T_{i,j}-1$. Namely,
the lifetime of cell $s$ of flow $f_{i,j}$ is the interval
$[\mathsf{offset}_{i,j}+sT_{i,j},\mathsf{offset}_{i,j}+(s+1)T_{i,j}-1]$. Now
we set the index of a scheduling period to be

$q(s)\triangleq\left\lceil\frac{sT_{i,j}+\mathsf{offset}_{i,j}-(k-1)}{N}\right\rceil.$
(49)

Since $s\geq 0,\mathsf{offset}_{i,j}\geq 0,k\leq N$, we can derive that
$q(s)\geq 0$. Since $\boldsymbol{M}_{k}$ is scheduled at slot $q(s)N+(k-1)$ in
scheduling period $q(s)$, to ensure that cell $s$ of flow $f_{i,j}$ gets a
scheduling slot, we only need to show that

$\mathsf{offset}_{i,j}+sT_{i,j}\leq
q(s)N+(k-1)\leq\mathsf{offset}_{i,j}+(s+1)T_{i,j}-1,$ (50)

i.e.,

$\frac{sT_{i,j}+\mathsf{offset}_{i,j}-(k-1)}{N}\leq
q(s)\leq\frac{(s+1)T_{i,j}+\mathsf{offset}_{i,j}-k}{N}$ (51)

If $q(s)=\frac{sT_{i,j}+\mathsf{offset}_{i,j}-(k-1)}{N}$, then (51) holds
directly. Otherwise, if $q(s)>\frac{sT_{i,j}+\mathsf{offset}_{i,j}-(k-1)}{N}$,
then

$\displaystyle q(s)$
$\displaystyle=\left\lceil\frac{sT_{i,j}+\mathsf{offset}_{i,j}-(k-1)}{N}\right\rceil$
$\displaystyle<\frac{sT_{i,j}+\mathsf{offset}_{i,j}-(k-1)}{N}+1.$ (52)

Thus,

$q(s)N<sT_{i,j}+\mathsf{offset}_{i,j}-(k-1)+N.$ (53)

Since both sides of (53) are integers, we have

$q(s)N\leq sT_{i,j}+\mathsf{offset}_{i,j}-(k-1)+N-1.$ (54)

Since $T_{i,j}\geq N$, we thus have,

$\displaystyle q(s)$
$\displaystyle\leq\frac{sT_{i,j}+\mathsf{offset}_{i,j}-(k-1)+N-1}{N}$
$\displaystyle\leq\frac{sT_{i,j}+\mathsf{offset}_{i,j}-(k-1)+T_{i,j}-1}{N}$
$\displaystyle=\frac{(s+1)T_{i,j}+\mathsf{offset}_{i,j}-k}{N}.$ (55)

Thus, (51) holds. Therefore, cell $s$ of flow $f_{i,j}$ will be scheduled at
slot $q(s)N+(k-1)$ before expiration. Since $s$ is arbitrary, any cell of flow
$f_{i,j}$ will be allocated one scheduling slot. In addition, since
$T_{i,j}\geq N$, it is easy to see that $q(s)\neq q(s^{\prime})$ if $s\neq
s^{\prime}$. Thus, any two cells of flow $f_{i,j}$ will be not be scheduled at
the same slot. We thus know that any cell will be allocated one unique
scheduling slot before expiration.

Therefore, M-TDMA achieves zero packet loss for all flows.

###  -F Proof of Theorem 3

Any flow $f_{i,j}$ is contained in one of perfect matchings in
$\mathcal{D}=\\{\boldsymbol{M}_{1},\boldsymbol{M}_{2},\cdots,\boldsymbol{M}_{N}\\}$,
say $\boldsymbol{M}_{k}$. According to the M-TDMA policy, perfect matching
$\boldsymbol{M}_{k}$ is scheduled at slots $qN+(k-1),q=0,1,\cdots$. Since
$T_{i,j}\geq N$, the $s$-th $(s=0,1,2,\cdots)$ cell (called cell $s$) of flow
$f_{i,j}$ arrives at the beginning of slot $\mathsf{offset}_{i,j}+sT_{i,j}$
and expires at the end of slot $\mathsf{offset}_{i,j}+(s+1)T_{i,j}-1$. We
consider the $s$-th cell (called cell $s$) of the flow
$f_{i,j}\in\boldsymbol{M}_{k}$, whose lifetime is time interval
$[\mathsf{offset}_{i,j}+sT_{i,j},\mathsf{offset}_{i,j}+(s+1)T_{i,j}-1]$.

Case 1. If condition (5) holds, the lifetime of cell $s$ of flow $f_{i,j}$ is
$[sT_{k},(s+1)T_{k}-1]$, which is exactly the lifetime of the $s$-th request
(called request $s$) of task $k$ in the virtual single-processor task
scheduling system. Since EDF achieves zero packet loss for any $T$-vector,
request $s$ of task $T_{k}$ is executed at some slot
$t^{\prime}\in[sT_{k},(s+1)T_{k}-1]$, i.e.,
$a^{\textsf{EDF}}_{t^{\prime}}(\overrightarrow{T})=k$. Since the M-EDF policy
schedules matching $\boldsymbol{M}_{a^{\textsf{EDF}}_{t}(\overrightarrow{T})}$
at any slot $t$, it schedules matching
$\boldsymbol{M}_{a^{\textsf{EDF}}_{t^{\prime}}(\overrightarrow{T})}=\boldsymbol{M}_{k}$,
which contains flow $f_{i,j}$, at slot $t^{\prime}$. Therefore, cell $s$ of
flow $f_{i,j}$ must be scheduled within its lifetime.

Case 2. If condition (6) holds, we need to find a slot
$t^{\prime}\in[\mathsf{offset}_{i,j}+sT_{i,j},\mathsf{offset}_{i,j}+(s+1)T_{i,j}-1]$
such that

$a^{\textsf{EDF}}_{t^{\prime}}(\overrightarrow{T})=k.$ (56)

Namely, we should prove that the EDF policy schedules a request of task $k$ at
some slot
$t^{\prime}\in[\mathsf{offset}_{i,j}+sT_{i,j},\mathsf{offset}_{i,j}+(s+1)T_{i,j}-1]$
in the virtual single-processor task scheduling system. Define

$q(s)\triangleq\left\lceil\frac{sT_{i,j}+\mathsf{offset}_{i,j}}{T_{k}}\right\rceil.$
(57)

Note that $q(s)T_{k}$ is the arrival time of request $q(s)$ of task $T_{k}$ in
the virtual single-processor task scheduling system. Now we first prove that
$q(s)T_{k}$ is within the lifetime of cell $s$ of flow $f_{i,j}$ in the switch
system. We can see that

$\displaystyle q(s)T_{k}$
$\displaystyle=\left\lceil\frac{sT_{i,j}+\mathsf{offset}_{i,j}}{T_{k}}\right\rceil\times
T_{k}$
$\displaystyle<\left(\frac{sT_{i,j}+\mathsf{offset}_{i,j}}{T_{k}}+1\right)\times
T_{k}$ $\displaystyle=sT_{i,j}+T_{k}+\mathsf{offset}_{i,j}$ $\displaystyle\leq
sT_{i,j}+\frac{T_{i,j}+1}{2}+\mathsf{offset}_{i,j}$
$\displaystyle=\mathsf{offset}_{i,j}+(s+1)T_{i,j}-1+\frac{3-T_{i,j}}{2}$
$\displaystyle\leq\mathsf{offset}_{i,j}+(s+1)T_{i,j}-1,$ (58)

where the last inequality follows from (6) and $\overrightarrow{T}$ is a
$T$-vector as $T_{i,j}\geq 2T_{k}-1\geq 2\times 2-1=3.$

Thus, we have

$q(s)T_{k}\in[\mathsf{offset}_{i,j}+sT_{i,j},\mathsf{offset}_{i,j}+(s+1)T_{i,j}-1].$

Therefore, request $q(s)$ of task $T_{k}$ arrives at the virtual system within
$[\mathsf{offset}_{i,j}+sT_{i,j},\mathsf{offset}_{i,j}+(s+1)T_{i,j}-1]$. In
addition, since EDF achieves zero packet loss with respect to any $T$-vector,
this request must be scheduled at some slot $t^{\prime}$ before its
expiration, i.e.,

$t^{\prime}\leq[q(s)+1]T_{k}-1.$ (59)

Now let us prove

$[q(s)+1]T_{k}-1\leq\mathsf{offset}_{i,j}+(s+1)T_{i,j}-1,$

which is equivalent to

$\left\lceil\frac{sT_{i,j}+\mathsf{offset}_{i,j}}{T_{k}}\right\rceil
T_{k}\leq\mathsf{offset}_{i,j}+(s+1)T_{i,j}-T_{k}.$ (60)

If $\frac{sT_{i,j}+\mathsf{offset}_{i,j}}{T_{k}}$ is an integer, then

$\displaystyle\left\lceil\frac{sT_{i,j}+\mathsf{offset}_{i,j}}{T_{k}}\right\rceil
T_{k}=\frac{sT_{i,j}+\mathsf{offset}_{i,j}}{T_{k}}\cdot T_{k}$
$\displaystyle=sT_{i,j}+\mathsf{offset}_{i,j}\leq
sT_{i,j}+\mathsf{offset}_{i,j}+(T_{i,j}-T_{k})$
$\displaystyle=\mathsf{offset}_{i,j}+(s+1)T_{i,j}-T_{k}.$ (61)

Thus, (60) holds. Otherwise, if $\frac{sT_{i,j}+\mathsf{offset}_{i,j}}{T_{k}}$
is not an integer, then

$\displaystyle\left\lceil\frac{sT_{i,j}+\mathsf{offset}_{i,j}}{T_{k}}\right\rceil
T_{k}$
$\displaystyle<\left(\frac{sT_{i,j}+\mathsf{offset}_{i,j}}{T_{k}}+1\right)\times
T_{k}$ $\displaystyle=sT_{i,j}+\mathsf{offset}_{i,j}+T_{k}.$ (62)

Since both sides of (62) are integers, we have

$\displaystyle\left\lceil\frac{sT_{i,j}+\mathsf{offset}_{i,j}}{T_{k}}\right\rceil
T_{k}\leq sT_{i,j}+\mathsf{offset}_{i,j}+T_{k}-1$ $\displaystyle\leq
sT_{i,j}+\mathsf{offset}_{i,j}+(T_{i,j}-T_{k}+1)-1$
$\displaystyle=\mathsf{offset}_{i,j}+(s+1)T_{i,j}-T_{k},$ (63)

where the last inequality follows from (6). Thus, (60) holds.

Therefore, (59) holds. Namely, request $q(s)$ of task $T_{k}$ is scheduled at
slot
$t^{\prime}\in[\mathsf{offset}_{i,j}+sT_{i,j},\mathsf{offset}_{i,j}+(s+1)T_{i,j}-1]$
in the virtual system. Then, since the M-EDF policy schedules matching
$\boldsymbol{M}_{a^{\textsf{EDF}}_{t}(\overrightarrow{T})}$ at any slot $t$,
it will schedule matching
$\boldsymbol{M}_{a^{\textsf{EDF}}_{t^{\prime}}(\overrightarrow{T})}=\boldsymbol{M}_{k}$
containing flow $f_{i,j}$ at slot $t^{\prime}$. Therefore, cell $s$ of flow
$f_{i,j}$ must be scheduled within its lifetime.

Since $s$ is selected arbitrarily for any flow $f_{i,j}\in\boldsymbol{M}_{k}$,
Case 1 and Case 2 finish the proof.


# Transformer-based Value Function Decomposition for Cooperative Multi-agent
Reinforcement Learning in StarCraft

Muhammad Junaid Khan, Syed Hammad Ahmed, Gita Sukthankar

###### Abstract

The StarCraft II Multi-Agent Challenge (SMAC) was created to be a challenging
benchmark problem for cooperative multi-agent reinforcement learning (MARL).
SMAC focuses exclusively on the problem of StarCraft micromanagement and
assumes that each unit is controlled individually by a learning agent that
acts independently and only possesses local information; centralized training
is assumed to occur with decentralized execution (CTDE). To perform well in
SMAC, MARL algorithms must handle the dual problems of multi-agent credit
assignment and joint action evaluation.

This paper introduces a new architecture TransMix, a transformer-based joint
action-value mixing network which we show to be efficient and scalable as
compared to the other state-of-the-art cooperative MARL solutions. TransMix
leverages the ability of transformers to learn a richer mixing function for
combining the agents’ individual value functions. It achieves comparable
performance to previous work on easy SMAC scenarios and outperforms other
techniques on hard scenarios, as well as scenarios that are corrupted with
Gaussian noise to simulate fog of war.

## Introduction

StarCraft poses many exciting research challenges for AI agents (Ontañón et
al. 2013), stemming from both the myriad macromanagement (strategic gameplay
choices related to production and expansion) and micromanagement (tactics
related to movement and targeting) tasks that occur during full gameplay. Even
though humans typically play StarCraft in a centralized way in which the
single human player controls all the units, the StarCraft II Multi-agent
Challenge testbed (Samvelyan et al. 2019) treats engagements as a cooperative
multi-agent problem in which each AI agent controls a single unit and has
limited visibility. SMAC provides a set of battle scenarios as benchmarks for
cooperative multi-agent reinforcement learning (MARL), unlike PySC2 (Vinyals
et al. 2017) which is designed for a single learning agent controlling all the
units. During execution, each SMAC agent conditions its decisions on the
partially observable limited area of view; enemy units do not have the
opportunity to adapt and are controlled by the built-in heuristic controller.
Scenarios include the initial positions, count, and types of units, as well as
terrain feature information. Some of the SMAC scenarios are designed to
encourage learning agents to acquire a micro-trick such as kiting or focusing
fire. A scenario can be symmetric or asymmetric, based on the unit counts of
allies and enemies, and homogeneous or heterogeneous according to the unit
types of each side.

Multi-agent reinforcement learning is significantly more challenging than
single agent tasks due to the problem of credit assignment: it’s difficult for
agents to determine whether it was its own action selection that yielded
rewards or another agent’s choices. A naïve solution is to concatenate each
agent’s individual state-action spaces and treat it as a single-agent problem
(Gupta, Egorov, and Kochenderfer 2017). Both learning and execution are
centralized and a single joint reward is learnt which cannot be decomposed
into independent agents’ contributions. The primary concern with this approach
is the curse of dimensionality, as it creates a drastic growth in the total
number of unique global states resulting in exponential space and time
complexity.

With a decentralized paradigm, agents independently condition only on their
local observations without inter-agent communication and without a joint
action-value function (Tan 1993). Due to its decentralized nature, parallelism
can be exploited, leading to faster learning but with no convergence
guarantees. These limitations can be addressed by centralizing the learning
and decentralizing each agent’s execution — known as Centralized Training with
Decentralized Execution (CTDE) (Oliehoek, Spaan, and Vlassis 2011).

The release of the SMAC environment has spurred a burst of innovation in
multi-agent value learning algorithms, such as QMIX (Rashid et al. 2018),
QPLEX (Wang et al. 2021), QTran (Son et al. 2019), and Qatten (Yang et al.
2020). A key distinction between these algorithms is the credit assignment
process which factorizes joint action-values into individual action-values for
every agent. To do this many MARL techniques make limiting assumptions about
the value function to facilitate the learning process. Adhering to the IGM
(Individual-Global-Max) principle (Son et al. 2019) avoids incompatible agent
policies: an action selected using the joint action-value function should be
equivalent to the greedy action selections of individual agents.

This paper introduces a transformer-based mixing approach, TransMix111Code is
available at: https://github.com/junaiddk/transmix, for joint action-value
learning in cooperative MARL. TransMix is able to extract global as well as
local contextual interaction amongst individual agent Q-values, agent
histories, and global state information, and can deal with longer time
horizons which helps it achieve better performance on the hard SMAC scenarios,
as well as scenarios that are corrupted with Gaussian noise. The next section
presents background on the mathematical notation used throughout the rest of
the paper.

## Background

Decentralized Partially Observable MDP (Dec-POMDP): MARL tasks are typically
modeled as a Dec-POMDP (Oliehoek, Spaan, and Vlassis 2011), described by the
tuple
$\mathbf{\mathcal{M}=\mathcal{<}N,S,\mathcal{A},P,r,\Omega,O,n,\gamma\mathcal{>}}$
where $i\in N=\\{1,2,3,...\\}$ is the set of agents while $s\in S$ represents
the true or global state in the environment. For every time step, agent $i\in
N$ selects an action $a_{i}\in\mathcal{A}\equiv\mathcal{A}^{n}$ based on state
$s$. When the joint action $a$ is executed, a joint reward $r(s,a)$ is
received, resulting in a transition to the next state $s^{\prime}$ based on a
transition probability function $P(s^{{}^{\prime}}|s,a)$ with a discount
factor $\gamma[0,1)$.

To make it a partially observable process, each agent $i$ receives an
observation $o_{i}\in\Omega$ based on the observation probability function
$O(o_{i}|s,a_{i})$. In addition, not only does each agent maintain an action-
observation history function
$\tau_{i}\in\tau\equiv(\Omega\times\mathcal{A}^{*})$, it conditions its
stochastic policy $\pi_{i}(a_{i}|\tau_{i})$ on this history as well. The
agents seek to achieve a joint policy $\Pi$ that maximizes the joint value
function $\mathcal{V}^{\pi}(s)$ as well as joint action-value function
$\mathcal{Q}^{\pi}(s,a)$.

Deep Q-Learning: Q-learning algorithms maximize the action value function
$\mathcal{Q}^{*}(s,a)=r(s,a)+\gamma\mathbb{E}_{s}{{}^{\prime}}[\max_{a}^{{}^{\prime}}\mathcal{Q}^{*}(s^{{}^{\prime}},a^{{}^{\prime}})]$.
In deep Q-learning, this function is learned using a deep neural network with
parameters $\mathcal{\theta}$. This idea of deep Q-networks was first
introduced by Mnih et al. (2015) who used replay memory to store transition
tuples of the form $(s,a,r,s^{{}^{\prime}})$, where $r$ is the reward of
taking action $a$ resulting in a state transition from $s$ to
$s^{{}^{\prime}}$. The network parameters, $\theta$, are optimized by sampling
batches from this replay memory in order to eliminate correlations in the
tuple sequence.

Standard DQN-based approaches utilize the temporal difference (TD) loss to
optimize the network, given by the equation

$\mathcal{L}(\theta)=\sum_{i=1}^{b}[(y_{i}^{DQN}-Q(s,a;\theta)^{2}]$ (1)

where $y_{i}^{DQN}$ represents the target network which is updated at regular
intervals (rather than at each iteration) and $b$ is the batch size sampled
from the replay buffer.

In order to deal with the problem of partial observability, a recurrent
version of the Q-network (DQRN) (Hausknecht and Stone 2015), has been used
where a recurrent neural network (RNN) based agent learns temporal information
after each state transition. In this case, the replay memory stores the joint
action-observation history tuple $(\tau,a,r,\tau^{{}^{\prime}})$ and the
Q-value is calculated using $Q(\tau,a;\theta)$ instead of $Q(s,a;\theta)$.

Training and Execution: Recent MARL value factorization techniques benefit
from the usage of a Centralized Training and Decentralized Execution (CTDE)
paradigm (Oliehoek, Spaan, and Vlassis 2011). Tan (1993) demonstrated that by
sharing individual observations and policies, independent agents learn a
cooperative task substantially quicker at the cost of communication and space
overhead. Without cooperation, the independent Q-learners may not converge
even if exhaustive exploration is assumed. The Centralized Training with
Decentralized Execution paradigm addressed the issues with independent
learning agents (Russell and Zimdars 2003; Tan 1993) and fully-centralized
learning approaches (Foerster et al. 2018; Gupta, Egorov, and Kochenderfer
2017) by avoiding misleading agent reward assignments, and eliminating the
need for combined action and observation spaces.

In CTDE, agents are trained in a central setting where each agent has access
to global state information. At training time, each agent aims to maximize its
own action-value function which leads to the maximization of the team’s joint
action-value function. At execution time each agent selects its action based
on its own learned action-value functions. The Individual-Global Max (IGM)
concept was introduced by Son et al. (2019) who state that the optimal joint
actions of agents are dependent upon optimal actions of individual agents
i.e.,

$argmax_{\boldsymbol{a}}Q_{tot}(\boldsymbol{\tau,a})=\begin{pmatrix}argmax_{a_{1}}Q_{1}(\tau_{1},a_{1})\\\
argmax_{a_{2}}Q_{2}(\tau_{2},a_{2})\\\ \vdots\\\
argmax_{a_{N}}Q_{N}(\tau_{N},a_{N})\\\ \end{pmatrix}$ (2)

Value decomposition networks (Sunehag et al. 2018) calculate $Q_{tot}$ by
summing up the individual $Q_{i}$ of each agents while QMIX (Rashid et al.
2018) applies a monotonicity constraint. These simplifications to the
factorization process facilitate learning but are unable to represent some
classes of joint action-value functions. Our research attempts to address this
problem through the usage of a more complex transformer-based mixing function.

## Related Work

Playing a full game of StarCraft requires creating an AI that can rapidly make
both strategic (macromanagement) and tactical (micromanagement) decisions
against opponents shrouded by fog of war on a large changing map (see Ontañón
et al. (2013) for a comprehensive overview of StarCraft research challenges).
Much of the recent research on reinforcement learning in StarCraft II has been
conducted on micromanagement scenarios executed using either the StarCraft II
Learning Environment (SC2LE) (Vinyals et al. 2017) or the StarCraft II Multi-
agent Challenge testbed (Samvelyan et al. 2019), which is built on top of
SC2LE. SMAC models battles as being executed by multiple cooperative agents.
Rather than tackling the problem of learning policies for an entire game which
requires significant computational power (e.g., such as what was used for
DeepMind’s AlphaStar system (Vinyals et al. 2019)), SMAC evaluates the ability
of cooperative agents to learn micromanagement policies for a single battle.
The PyMARL framework was also released as part of SMAC to facilitate the
development and performance comparisons of newly proposed RL algorithms with
other popular implementations (Sunehag et al. 2018; Rashid et al. 2018, 2020;
Son et al. 2019; Wang et al. 2021). The next section provides an overview of
recent work on RL for SMAC.

### MARL in StarCraft

Value decomposition networks (VDN) (Sunehag et al. 2018) introduced the
seminal idea of learning a unified reward value and factorizing it into agent-
wise reward values; the algorithm assumes that the joint value function can be
additively decomposed into individual value functions for each agent. Since
VDN only considers linear value functions, it does not perform well for
complex benchmarks like the SMAC scenarios that have many agent
interdependencies (Samvelyan et al. 2019). Also unlike later MARL algorithms,
VDN does not leverage global state information.

In QMIX, Rashid et al. (2018), improved on VDN by incorporating global state
information during training and supporting a broader range of non-linear value
functions. The QMIX architecture includes a mixing network conditioned on the
state information which improves the representational complexity of the value
functions. The monotonicity of the joint value function is ensured through the
usage of positive weights and individual agent networks conditioned on local
observations only. However QMIX’s loss function tries to minimize loss across
all joint actions for every state; this can result in incorrect argmax
selections when decomposing non-monotonic functions. Weighted QMIX (Rashid et
al. 2020) fixes some issues with the original architecture by assigning
weights to the projected joint action-values instead of using equal weights as
was done in the original QMIX paper; these weight assignments can either be
done centrally or optimistically.

Son et al. (2019) identified some limitations with the usage of additivity
(VDN) and monotonicity (QMIX) constraints. They emphasize that an effective
factorization of optimal joint action-values must instead satisfy the IGM
(Individual-Global-Max) property such that the best joint action-value is the
aggregation of individual agents’ optimal action-values. Their algorithm QTRAN
uses an additional state-value network to compete a scalar value representing
the state. This value helps minimize the difference in the total joint reward
and the sum of each agent’s individual rewards, and therefore supports a
variety of non-monotonic joint action-value functions. QPLEX (Wang et al.
2021) ensures compliance to the IGM principle by introducing an advantage-
based function realized with a duplex dueling architecture (Wang et al. 2016);
it is one of the best performing SMAC algorithms. In this paper, we benchmark
our work against both QMIX and QPLEX.

Figure 1: Complete architecture of TransMix. (a) is the transformer encoder.
(b) is the overall architecture of the TransMix. (c) is the GRU-based agent
network. A stack of 2 to 6 transformer encoder layers are used based on the
complexity of the task.

As the number of agents in a multi-agent problem increases, the role of
context assumes greater importance since the agent must consider the states of
other agents, but only a small subset of the other agents are relevant to the
task on hand. To overcome this problem, Yang et al. (2020) proposed
incorporating a multi-headed attention module into the mixing network used for
joint Q-value estimation. Unlike convolutional and recurrent architectures,
attention mechanisms can model far-flung dependencies in input and output
sequences (Vaswani et al. 2017). Instead of proposing enhancements to the
mixing of agent network structures, Hao et al. (2022) sought to scale up to
larger multi-agent problems by improving input sample efficiency. They
realized that in a system with a small set of cooperating agents, sampling all
permutations of their ordered representations is redundant, hence the training
sample number can be reduced by forcing agent-ordering to be permutation
invariant.

Our work leverages the transformer model which relies exclusively on attention
to learn data dependencies; also it can be designed to support permutation
invariance. Khan, Hassan, and Sukthankar (2021) demonstrated promising results
on the usage of transformer networks for macromanagement task prediction in
StarCraft II; however, their work was done on a static dataset using
supervised learning. Unfortunately the basic transformer architecture has been
shown to be unstable with the shifting RL objective function (Parisotto et al.
2020) so embedding transformers into an online RL agent requires careful
training. Fine-tuning an offline-learnt transformer with online RL training
can improve both overall agent performance and sample efficiency (Zheng,
Zhang, and Grover 2022).

## Method

This paper introduces our transformer-based value decomposition and mixing
network, TransMix. Our transformer design is inspired by the approach of
Fastformer (Wu et al. 2021). Each agent is represented by a GRU-based DQRN
network. At every time step, agents receive observations $o^{i}_{t}\in\Omega$
and previous action $a^{i}_{t-1}\in\mathcal{A}$. Based on $o^{i}_{t}$ and
$a^{i}_{t-1}$ the agent network estimates the individual
$Q_{i}(\tau^{i},a^{i})$ where $\tau$ is the action-observation history and
selects the next actions for each agent by following an $\epsilon$-greedy
policy.

The transformer encoder consists of 2 to 6 transformer layers. The number of
transformer layers or depth is based on the complexity of the task at hand.
Once a batch of data is ready, it is fed to the transformer which ingests
individual $Q_{i}$, action-observation histories $h_{i}^{t}$ and global states
$S_{t}$.

We calculate the query vector, Q, from the global states by applying linear
transformation and self-attention. This operation ensures that the most
important states get attention and contribute more towards the global context
in learning the $Q_{tot}$. Similarly, we apply a separate linear
transformation to individual $Q_{i}$ and the resultant is then multiplied
element-wise with Q vector which gives a global context aware key vector
between $S_{t}$ and $Q_{i}$. Next, we apply self-attention to extract the most
relevant information in the form of global K vector. This K vector is then
element-wise multiplied with transformed $h_{i}^{t}$ that goes through further
linear transformation to produce global context aware V vector. Lastly, the
transformed states and V vectors are aggregated together to estimate the
$Q_{tot}$. The complete TransMix architecture is presented in Fig. 1.

Following the design guidelines of Fastformer, we also make use of additive
self-attention for calculating K and Q vectors rather than the standard self-
attention proposed by the vanilla transformer design (Vaswani et al. 2017).
The benefits of additive self-attention are many fold. Firstly this attention
mechanism is rather light weight. Second, it reduces the total complexity of
transformer encoder. Finally, it improves the inference time of the
transformer as well.

The matrices K, V, and Q $\in\mathbb{R}^{\mathcal{N}\times d}$, where
$\mathcal{N}$ $\in\mathbb{R}^{512}$ is the sequence length or the embedded
dimension of the transformation layers and $d\in\mathbb{R}^{2048}$ is the
hidden dimension. We also utilize 4 attention heads for our TransMix network.
The linear transformations with sequence length or hidden dimension
$\mathbb{R}^{512}$ ensure that we can provide a fixed length input to
transformer layers which helps to keep the complexity and computation under
control.

We train TransMix in online data collection settings in an end-to-end fashion.
The network is optimized with an Adam optimizer and standard TD loss (Equation
1). The learning rate is set to $0.001$ for most of the SMAC scenarios with
$\beta_{1}=0.9$ and $\beta_{2}=0.999$, and batch size is set to 96. We also
utilize a skip connection that consists of concatenated $Q_{i}$ and
$h_{i}^{t}$ which is passed through a bottleneck linear transformation. This
bottleneck skip connection provides training stability and helps the network
converge while reducing the dimensionality of the concatenated matrices.
Unlike many other methods, our approach does not use hypernetwork generated
weights extracted from global states. This makes our approach less dependent
on global states compared to others.

Maps |  Difficulty |  TransMix |  QMIX |  QPLEX
---|---|---|---|---
2m_vs_1z |  Easy |  99\. 7 |  95.3 |  100
3m |  Easy |  100 |  96.9 |  100
8m |  Easy |  100 |  97.7 |  100
2s3z |  Easy |  100 |  88.25 |  100
1c3s5z |  Easy |  97.62 |  93.37 |  97.2
MMM |  Easy |  100 |  95.3 |  96.9
bane_vs_bane |  Easy |  100 |  89.21 |  98.47
3s_vs_5z |  Hard |  95.91 |  88.7 |  99.1
3s5z |  Hard |  96.68 |  88.3 |  95.9
5m_vs_6m |  Hard |  77.41 |  69.2 |  73.4
8m_vs_9m |  Hard |  96.88 |  92.2 |  87.5
2c_vs_64zg |  Hard |  92.62 |  84.38 |  91.2
10m_vs_11m |  Hard |  91.77 |  89.2 |  90.12
Table 1: Median win rate on SMAC maps. We train our network for 2M training
timesteps on each map. TransMix outperforms QMIX and QPLEX on most hard SMAC
scenarios and ties on easy scenarios.

## Results

We evaluate TransMix on both easy and hard scenarios from the SMAC (Samvelyan
et al. 2019) challenge benchmark. In SMAC, the focus is on micromanagement
tasks in SC2 such as unit battles. During the battles, we train our RL agents
in an online fashion while the opponents are controlled by the built-in AI. A
battle is considered as “win” if the ally unit kills an opponent unit. On the
other hand a “loss” occurs if the opponent kills an ally unit or the maximum
number of episodes are reached. When an RL agent damages the opponent, a
reward is received proportional to damage done. Similarly, a reward of 10 is
received for killing an opponent’s agent; winning the battle accumulates a
reward of 200. The details of SMAC scenarios are provided in Table 3.

### Training and Evaluation

We follow the same evaluation metric proposed by Rashid et al. (2018). For
each SMAC map, the experiment is repeated 5 times. We train the model for 2M
timesteps on all the scenarios with a replay buffer capacity of 5000 episodes;
linear $\epsilon$ annealing from 1.0 to 0.05 is performed over 50k steps for
easy maps while for the hard maps the range varies from 250k to 500k steps.
After every 10k timesteps, we pause the training and test our method for 20
test episodes in a decentralized fashion. Moreover, after every 200 episodes,
we update our target network parameters.

The main results are summarized in Table 1. Since our approach is based on
transformer, which is highly scalable, we leverage the built-in parallel
episode runner environment for training and testing which substantially
reduces the training time for TransMix. We benchmark our work against both
QMIX (Rashid et al. 2018) and QPLEX (Wang et al. 2021) which provide a good
illustration of the performance of our method. QMIX is one of the oldest
methods to be successful at SMAC, whereas QPLEX is a recent top performer that
incorporates all the value function decomposition improvements proposed by
earlier authors. Our method always outperforms QMIX and performs better than
QPLEX in the majority of the hard scenarios.

### Effects of Noisy States

This paper also examines whether the usage of the transformer makes the MARL
agents more robust to fog of war by injecting noise into the global state
(Weber and Mateas 2009). For these experiments, we add Gaussian noise,
$\mathcal{N}(0,0.05)$, to global states and train our model, QMix and QPlex
from scratch. We follow the same training approach as discussed earlier and
record the win rate. We observe that our method is less prone to noisy states
compared to QMIX and QPlex, and that the performance drop of our method is
less significant compared to others on the same maps without noisy states.
These results are reported in Fig. 2 and Table 3. As the complexity of the map
grows, the performance drop becomes more significant.

Maps |  TransMix |  QMIX |  QPlex
---|---|---|---
3m |  99.82 |  95.31 |  97.41
8m |  96.87 |  93.75 |  93.75
2s3z |  93.75 |  81.67 |  89.15
1c3s5z |  93.75 |  78 |  83.88
3s5z |  84.18 |  65.76 |  72.62
Table 2: Noisy global state evaluation. TransMix conclusively outperforms QMIX and QPlex when the global states are corrupted by noise. Map |  Ally Unit |  Enemy Unit
---|---|---
2m_vs_1z |  2 Marines |  1 Zealot
3m |  3 Marines |  3 Marines
8m |  8 Marines |  8 Marines
2s3z |  2 Stalkers and 3 Zealots |  2 Stalkers and 3 Zealots
1c3s5z |  1 Colossi, 3 Stalkers and 5 Zealots |  1 Colossi, 3 Stalkers and 5 Zealots
MMM |  1 Medivac, 2 Marauders and 7 Marines |  1 Medivac, 2 Marauders and 7 Marines
bane_vs_bane |  20 Zerglings and 4 Banelings |  20 Zerglings and 4 Banelings
3s_vs_5z |  3 Stalkers |  5 Zealots
3s5z |  3 Stalkers and 5 Zealots |  3 Stalkers and 5 Zealots
5m_vs_6m |  5 Marines |  6 Marines
8m_vs_9m |  8 Marines |  9 Marines
2c_vs_64zg |  2 Colossi |  64 Zerglings
10m_vs_11m |  10 Marines |  11 Marines
Table 3: Details of SMAC Scenarios

## Discussion

The key to our method, TransMix, is the ability to learn the complex global
and local contextual interaction amongst individual agents’ Q-values, $Q_{i}$,
the agents’ histories, $h_{i}^{t}$, and the global states, $S_{t}$. The
transformer correctly learns the context surrounding the correct choice of
action, while remaining robust to noisy global states.

Figure 2: Win rate comparison between TransMix (labeled as TMix), QPlex, and
QMIX. The top row represents win rate with regular global states while bottom
row represents win rate with noisy global states.

Another aspect of our method is that the transformers are by design
permutation invariant and thus do not depend on ordering. For instance, QMIX
has to maintain the individual value function order which we do not require at
all. While TransMix achieved a better test win rate on hard scenarios and
comparable performance on easy scenarios, like other SMAC benchmarks, it
performs poorly on super hard scenarios.

The policies learnt by our method are very interesting. For instance, for the
MMM map, the approach is aggressive. Each side has a heterogeneous team of 1
medivac, 2 mauraders, and 7 marines. The medivac agent remains behind all
other agents while the marauders take the lead since they have heavy armors,
and marines cover up the marauders. This demonstrates that the transformer is
good at learning the appropriate role mapping for different types of units.

## Conclusion

This paper introduces TransMix, a value decomposition and mixing network for
cooperative MARL tasks. TransMix uses a stack of transformer encoder layers
trained in an end-to-end way, learning in a centralized fashion while
executing the learned policies in a totally decentralized fashion. Our method
is capable of representing non-linear value decomposition functions while
maintaining consistency.

Results show that our method always outperforms QMIX and bests QPLEX on the
majority of the hard StarCraft II Multi-agent Challenge scenarios.
Furthermore, TransMix can still achieve good performance when the global
states are perturbed with Gaussian noise, unlike QMIX. In future work we seek
to improve the performance on super hard scenarios by improving the
exploration policy.

## Acknowledgments

Research was partially sponsored by the Army Research Office and was
accomplished under Cooperative Agreement Number W911NF-21-2-0103. The views
and conclusions contained in this document are those of the authors and should
not be interpreted as representing the official policies, either expressed or
implied, of the Army Research Office or the U.S. Government. The U.S.
Government is authorized to reproduce and distribute reprints for Government
purposes notwithstanding any copyright notation herein.

## References

  * Foerster et al. (2018) Foerster, J.; Farquhar, G.; Afouras, T.; Nardelli, N.; and Whiteson, S. 2018.  Counterfactual multi-agent policy gradients.  In _Proceedings of the AAAI Conference on Artificial Intelligence_.
  * Gupta, Egorov, and Kochenderfer (2017) Gupta, J. K.; Egorov, M.; and Kochenderfer, M. 2017.  Cooperative Multi-agent Control Using Deep Reinforcement Learning.  In Sukthankar, G.; and Rodriguez-Aguilar, J. A., eds., _Autonomous Agents and Multiagent Systems_ , 66–83. Cham: Springer International Publishing.
  * Hao et al. (2022) Hao, X.; Wang, W.; Mao, H.; Yang, Y.; Li, D.; Zheng, Y.; Wang, Z.; and Hao, J. 2022\.  API: Boosting Multi-Agent Reinforcement Learning via Agent-Permutation-Invariant Networks.  _arXiv preprint arXiv:2203.05285_.
  * Hausknecht and Stone (2015) Hausknecht, M. J.; and Stone, P. 2015.  Deep Recurrent Q-Learning for Partially Observable MDPs.  In _AAAI Fall Symposia_.
  * Khan, Hassan, and Sukthankar (2021) Khan, M. J.; Hassan, S.; and Sukthankar, G. 2021.  Leveraging Transformers for StarCraft Macromanagement Prediction.  In _IEEE International Conference on Machine Learning and Applications (ICMLA)_ , 1229–1234.
  * Mnih et al. (2015) Mnih, V.; Kavukcuoglu, K.; Silver, D.; Rusu, A. A.; Veness, J.; Bellemare, M. G.; Graves, A.; Riedmiller, M. A.; Fidjeland, A.; Ostrovski, G.; Petersen, S.; Beattie, C.; Sadik, A.; Antonoglou, I.; King, H.; Kumaran, D.; Wierstra, D.; Legg, S.; and Hassabis, D. 2015.  Human-level control through deep reinforcement learning.  _Nature_ , 518: 529–533.
  * Oliehoek, Spaan, and Vlassis (2011) Oliehoek, F. A.; Spaan, M. T. J.; and Vlassis, N. 2011.  Optimal and Approximate Q-value Functions for Decentralized POMDPs.  _CoRR_ , abs/1111.0062.
  * Ontañón et al. (2013) Ontañón, S.; Synnaeve, G.; Uriarte, A.; Richoux, F.; Churchill, D.; and Preuss, M. 2013.  A Survey of Real-Time Strategy Game AI Research and Competition in StarCraft.  _IEEE Transactions onComputational Intelligence and AI in Games_ , 5(4): 293–311.
  * Parisotto et al. (2020) Parisotto, E.; Song, F.; Rae, J.; Pascanu, R.; Gulcehre, C.; Jayakumar, S.; Jaderberg, M.; Kaufman, R. L.; Clark, A.; Noury, S.; et al. 2020.  Stabilizing transformers for reinforcement learning.  In _International Conference on Machine Learning_ , 7487–7498. PMLR.
  * Rashid et al. (2020) Rashid, T.; Farquhar, G.; Peng, B.; and Whiteson, S. 2020.  Weighted QMIX: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning.  _Advances in Neural Information Processing Systems_ , 33: 10199–10210.
  * Rashid et al. (2018) Rashid, T.; Samvelyan, M.; de Witt, C. S.; Farquhar, G.; Foerster, J. N.; and Whiteson, S. 2018.  QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning.  _CoRR_ , abs/1803.11485.
  * Russell and Zimdars (2003) Russell, S. J.; and Zimdars, A. 2003.  Q-decomposition for reinforcement learning agents.  In _Proceedings of the 20th International Conference on Machine Learning (ICML-03)_ , 656–663.
  * Samvelyan et al. (2019) Samvelyan, M.; Rashid, T.; De Witt, C. S.; Farquhar, G.; Nardelli, N.; Rudner, T. G.; Hung, C.-M.; Torr, P. H.; Foerster, J.; and Whiteson, S. 2019.  The StarCraft multi-agent challenge.  _arXiv preprint arXiv:1902.04043_.
  * Son et al. (2019) Son, K.; Kim, D.; Kang, W. J.; Hostallero, D. E.; and Yi, Y. 2019.  QTRAN: Learning to factorize with transformation for cooperative multi-agent reinforcement learning.  In _International Conference on Machine Learning_ , 5887–5896. PMLR.
  * Sunehag et al. (2018) Sunehag, P.; Lever, G.; Gruslys, A.; Czarnecki, W. M.; Zambaldi, V.; Jaderberg, M.; Lanctot, M.; Sonnerat, N.; Leibo, J. Z.; Tuyls, K.; and Graepel, T. 2018.  Value-Decomposition Networks For Cooperative Multi-Agent Learning Based On Team Reward.  In _Proceedings of the International Conference on Autonomous Agents and MultiAgent Systems_ , 2085–2087.
  * Tan (1993) Tan, M. 1993.  Multi-agent reinforcement learning: Independent vs. cooperative agents.  In _Proceedings of the International Conference on Machine Learning_ , 330–337.
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, Ł.; and Polosukhin, I. 2017.  Attention is all you need.  _Advances in Neural Information Processing Systems_ , 30.
  * Vinyals et al. (2019) Vinyals, O.; Babuschkin, I.; Czarnecki, W. M.; Mathieu, M.; Dudzik, A.; Chung, J.; Choi, D. H.; Powell, R.; Ewalds, T.; Georgiev, P.; et al. 2019.  Grandmaster level in StarCraft II using multi-agent reinforcement learning.  _Nature_ , 575(7782): 350–354.
  * Vinyals et al. (2017) Vinyals, O.; Ewalds, T.; Bartunov, S.; Georgiev, P.; Vezhnevets, A. S.; Yeo, M.; Makhzani, A.; Küttler, H.; Agapiou, J. P.; Schrittwieser, J.; Quan, J.; Gaffney, S.; Petersen, S.; Simonyan, K.; Schaul, T.; van Hasselt, H.; Silver, D.; Lillicrap, T. P.; Calderone, K.; Keet, P.; Brunasso, A.; Lawrence, D.; Ekermo, A.; Repp, J.; and Tsing, R. 2017.  StarCraft II: A New Challenge for Reinforcement Learning.  _CoRR_ , abs/1708.04782.
  * Wang et al. (2021) Wang, J.; Ren, Z.; Liu, T.; Yu, Y.; and Zhang, C. 2021.  QPLEX: Duplex Dueling Multi-Agent Q-Learning.  In _International Conference on Learning Representations, ICLR_.
  * Wang et al. (2016) Wang, Z.; Schaul, T.; Hessel, M.; Hasselt, H.; Lanctot, M.; and Freitas, N. 2016\.  Dueling network architectures for deep reinforcement learning.  In _International Conference on Machine Learning_ , 1995–2003. PMLR.
  * Weber and Mateas (2009) Weber, B. G.; and Mateas, M. 2009.  A Data Mining Approach to Strategy Prediction.  In _Proceedings of the International Conference on Computational Intelligence and Games_ , 140–147. IEEE Press.  ISBN 9781424448142.
  * Wu et al. (2021) Wu, C.; Wu, F.; Qi, T.; and Huang, Y. 2021.  Fastformer: Additive Attention Can Be All You Need.  _ArXiv_ , abs/2108.09084.
  * Yang et al. (2020) Yang, Y.; Hao, J.; Liao, B.; Shao, K.; Chen, G.; Liu, W.; and Tang, H. 2020.  Qatten: A general framework for cooperative multiagent reinforcement learning.  _arXiv preprint arXiv:2002.03939_.
  * Zheng, Zhang, and Grover (2022) Zheng, Q.; Zhang, A.; and Grover, A. 2022.  Online Decision Transformer.  _arXiv preprint arXiv:2202.05607_.