We want to note that all works about computing schedules robust against
permanent link failures are also robust against frame loss. Both
countermeasures against link failures are also effective against frame loss.
Another kind of reliability is considered in [CrOl21]. The authors compute
schedules robust against clock drift, i.e., clocks of different devices
running not with the same speed. They introduce gaps between frame
transmissions such that the maximum possible clock drift does not affect other
frame transmissions. Unknown hardware bugs or deviations from TSN standards
are treated by [ZhSa21b]. The proposed algorithm selects expensive bridges
with higher certification for paths of streams with higher safety
requirements.

####  V-A6 Multicast

Every algorithm in literature can be used for multicast streams, as a
multicast stream can be substituted by a set of unicast streams. However, the
number of streams negatively affects the solving time of a problem instance.
Tables 2 and 3 indicate multicast support only for works which include some
considerations for the efficient integration of multicast streams without
introducing a set of new streams. Most such works handle multicast streams by
scheduling only a single frame per link, regardless of the number of
consecutive links in the multicast tree of the respective stream. Examples for
such works are [OlCr18], [StCr18], [SaCa19], [FeYa21], [BaPo21]. An analysis
of the joint routing and scheduling problem with multicast streams is
presented in [ScTi20]. Yu et al. [YuWa20] compute routings and schedules for
multicast streams such that migrating a virtual machine sending or receiving
TT streams can be done easily.

####  V-A7 Task Scheduling

Only a few research works are concerned with the joint scheduling of streams
and tasks. Some of them have integrated dependencies between streams and
tasks, i.e., tasks can only be scheduled after some stream has arrived. Such
works are presented in [FeYa21], [BaZa20], and [BaPo21]. Other works focus on
the scheduling of tasks which produce TT streams while considering safety and
security considerations. Preliminary results for this scenario are presented
in [RePo20] and extended in [ReCr22].

Objective Category |  Research work
---|---
No objective |  Steiner [St10], Farzaneh et al. [FaKu17], Raagaard et al. [RaPo17] Falk et al. [FaDu18], Steiner et al. [StCr18], Mahfouzi et al. [MaAm18], Atallah et al. [AtBa18], Alnajim et al. [AlSa19], Santos et al. [SaCa19], Ansah et al. [AnAb19], Dobrin et al. [DoDe19], Falk et al. [FaDu20], Zhou et al. [ZhLi20], Atallah et al. [AtBa20], Li et al. [LiLi20], Zhou et al. [ZhSa21], Syed et al. [SyAy21] [SyAy21b], Mahfouzi et al. [MaAm21], Kim et al. [KiCh21], Dai et al. [DaWa21], Li et al. [LiJi22], Zhou et al. [ZhSa22], Xu et al. [XuXu22], Vlk et al. [VlBr22], Bujosa et al. [BuAs22]
Latency and Jitter |  Dürr et al. [DuNa16], Pahlevan et al. [PaOb18], [PaTa19], Arestova et al. [ArHi20], Hellmanns et al. [HeGl20], Houtan et al. [HoAs21], Wang et al. [WaYa22], Schweissguth et al. [ScDa17] [ScTi20], Vlk et al. [VlHa20], Feng et al. [FeCa21], Pang et al. [PaHu21], Oliver et al. [OlCr18], Barzegaran et al. [BaZa20], Barzegaran et al. [BaPo21], Zhou et al. [ZhWa21], Nie et al. [NiLi22], Huang et al. [HuWa21], Kim et al. [KiLe21][KiLe22]
Queuing |  Craciunas et al. [CrOl16], Pop et al. [PoRa16], Gavriluţ et al. [GaPo18], Vlk et al. [VlHa20], Vlk et al. [VlHa21b], Feng et al. [FeDe22]
Other Traffic |  Gavriluţ et al. [GaPo18] [GaZh18], Smirnov et al. [SmGl17], Reusch et al. [ReZh20], Houtan et al. [HoAs21], Berisa et al. [BeZh22], Barzegaran et al. [BaRe22]
Routing |  Schweissguth et al. [ScTi20], Wang et al. [WaCh20], Li et al. [LiXi22], Yu et al. [YuGu20], Li et al. [LiZh21], Yu et al. [YuWa20], Li et al. [LiCh21]
Topology Synthesis |  Gavriluţ et al. [GaZa17], Xu et al. [XuXu20], Zhou et al. [ZhSa21b], Reusch et al. [ReCr22]
Reliability |  Pozo et al. [PoRo18], Park et al. [PaSa19], Craciunas et al. [CrOl21]
GCL Synthesis |  Jin et al. [JiXi20], Kentis et al. [KeBe17]
Other |  Jin et al. [JiXi19], Ginthör et al. [GiGi20], Feng et al. [FeYa21], Syed et al. [SyAy20], Chaine et al. [CaBo22]
Table 5: Categorization of research works based on optimization objectives.

###  V-B Scheduling Objective

Objective functions are used to measure the quality of solutions and to
compare them. We discuss common objectives from the literature and classify
research works by their objective. Table 5 shows which research work features
which kind of objective.

####  V-B1 No Objective

Many research works have no scheduling objective and only try to find some
schedule which fulfills all constraints, e.g., [RaPo17], [FaDu18], and
[FaDu20]. We note that many SMT approaches feature no objective
[St10][StCr18][SaCa19][FaKu17][MaAm18][MaAm21]. In contrast to ILP solving,
SMT solvers were not originally designed for optimization. Therefore, many SMT
approaches focus on finding a feasible schedule.

####  V-B2 Latency and Jitter

TSN and the TAS were designed for traffic with hard real-time requirements.
Therefore, latency and jitter of streams are interesting properties of
schedules. Objective functions including them are the most common kind of
objectives in TSN schedule optimization. Oliver et al. [OlCr18] and Barzegaran
et al. [BaZa20] minimize the per-stream jitter. Minimizing the flowspan, i.e.,
the time all Time-Triggered (TT) stream arrive at their destination, is a
common objective. Examples of approaches using this objective include
[DuNa16], [HeGl20], [WaYa22], [HoAs21], [PaTa19], [ArHi20], and [PaOb18]. A
related but different objective is the minimization of end-to-end delays of TT
streams [ScDa17][VlHa20][PaHu21][ScTi20]. Kim et al. [KiLe21][KiLe22] minimize
multiple objectives weighted by constant factors. They take end-to-end delays,
jitter, and bandwidth occupation into account. Barzegaran et al. [BaPo21] use
a combination of jitter and end-to-end latency as measure of schedule quality.
Nie et al. [NiLi22] minimize end-to-end latency and transmission offsets
simultaneously. We remark that these objectives are not competing, as opposed
to most multi-criterion problems. Minimization of transmission offsets is also
pursued by [HuWa21] which is related but not equal to flowspan or end-to-end
latency minimization. Zhou et al. [ZhWa21] use a combination of jitter, end-
to-end delays, number of scheduled streams, and link utilization.

####  V-B3 Queuing

Research works which apply isolation constraints for queuing often use more
than one queue per egress port for scheduled traffic. In that way, they are
able to schedule more streams as isolation only concern streams in the same
egress queue. The assignment of streams to egress queues per egress port is a
degree of freedom in the respective scheduling problems. Therefore, they try
to minimize the number of queues reserved for TT streams per egress port, as
the remaining queues are available for other traffic. Examples for such works
include [CrOl16], [VlHa20], [PoRa16], [FeDe22], [VlHa21b], and [GaPo18].

####  V-B4 Other Traffic

The schedule of TT streams has an influence on the Quality of Service for
other traffic classes. Current approaches for scheduling in TSN focus on AVB
traffic and BE traffic. For the joint scheduling of TT and AVB streams,
Gavriluţ et al. [GaZh18][GaPo18] minimize the tardiness of AVB streams as
their deadlines are considered to be not strict. Another objective related to
AVB streams is used in [BeZh22]. The presented heuristic has the objective to
schedule as many AVB streams as possible. The authors of [ReZh20] minimize the
occupation percentage of egress ports, i.e., the percentage of a hyperperiod
with no active transmission window for TT traffic. The rational of this is
that low occupation corresponds to long and frequent time intervals available
to other traffic. A similar objective is used in [BaRe22] as the authors
minimize the average bandwidth occupied by transmission windows for scheduled
traffic. Smirnov et al. [SmGl17] use a multi-criterion objective for joint
routing and scheduling. They reduce the influence of scheduled traffic to
other traffic, and simultaneously minimize the number of GCL entries needed to
deploy a schedule. The work in [HoAs21] focuses on comparing the influence of
different objective functions to the QoS of BE traffic. They propose
minimization and maximization of frame offsets, hoping that grouping frames
together increases the QoS. Additionally, they also suggest two objectives
which maximize the gaps between consecutive frame transmissions on a link.
They assume that starvation of other traffic classes is reduced in this way.

####  V-B5 Routing

Research works about joint routing and scheduling often consider the quality
of the routing in their objective. All of them have in common that the length
of the paths is minimized. This is reasonable as longer paths correspond to
higher link utilizations, end-to-end latencies, and harder scheduling
instances. Schweissguth et al. [ScTi20] propose a multi-objective optimization
for joint routing and scheduling. First, routing and schedule with minimized
path lengths are computed. The obtained path lengths are used as maximum path
lengths per stream in a second run. The second run minimizes end-to-end
latencies. The joint routing approach of [WaCh20] minimizes the number of
links in the routing. Li et al. [LiXi22] simultaneously minimize the path
lengths and a measure for scheduling conflicts of streams routed over the same
link. Yu et al. [YuGu20] schedule and route streams one after another. They
minimize a weighted sum of the number of links used for the currently
scheduled stream, and the bandwidth utilization. Li et al. [LiZh21]
simultaneously minimize path lengths in the routing, and the flowspan. Yu et
al. [YuWa20] consider the migration of sources of TT streams. They minimize
the maximum distance from all possible source nodes of a stream to all
destination nodes in a multicast tree. Li et al. [LiCh21] maximize the number
of streams which are scheduled and routed, and also try to minimize the
maximum link load as a secondary objective.

####  V-B6 Topology Synthesis

In addition to joint routing and scheduling, some works also construct the
network topology. TSN bridges are expensive, and thus such objectives always
include costs for bridges. Gavriluţ et al. [GaZa17] minimize multiple
objectives weighted by constant factors. The first objective is the tardiness
of TT streams to guide their GRASP heuristic to solutions with no deadline
misses. The second objective is topology costs. A similar objective is used in
[ReCr22]. The weighted sum of routing and schedule costs is minimized. Routing
costs constitute of overlap penalties for redundant paths and path lengths.
Schedule costs constitute of punishments for not schedulable streams and
stream latencies. Another approach which minimizes topology costs is proposed
in [ZhSa21b]. Selecting bridges from a library is part of the presented
problem, which imposes costs for bridges and additional costs when multiple
vendors are used. Xu et al. [XuXu20] minimize the number of bridges needed to
schedule and route all streams such that the utilization is maximized.

####  V-B7 Reliability

Reliability requirements can be ensured by constraining the set of feasible
solutions. However, some works choose to maximize reliability for their
respective fault model. Pozo et al. [PoRo18] maximize the idle times of links
and frames, as such schedules are easier to repair upon link failure.
Craciunas et al. [CrOl21] maximize the allowed out-of-sync clock drift to cope
with synchronization problems and maximize robustness against clock drift.
Park et. al. [PaSa19] maximize the number of times a frame can be
retransmitted without missing its deadline, as they include preemption in
their model.

####  V-B8 GCL Synthesis

TSN bridges do not have an unlimited number of GCL entries per egress port.
The minimization of GCL entries is considered by [JiXi20]. The reason for this
is that the authors propose an incremental approach and the overall number of
needed GCL entries is not known in advance. Reducing the number of gate events
also reduces the number of guard bands which is beneficial for BE traffic.
Kentis et al. [KeBe17] minimize the GCL schedule duration. However, it is not
clear why schedule duration matters, as the limiting factor in TSN hardware is
the number of GCL entries.

####  V-B9 Others

Some research works use a problem specific objective not comparable to other
works. We present them for the sake of completeness. The authors of [JiXi19]
minimize the number of frames as they propose a joint approach for scheduling
and message fragmentation. Syed et al. [SyAy20] use a modelling specific
objective which is related to load balancing of ports in an in-vehicle
architecture with one central processing unit. Ginthör et al. [GiGi20]
minimize the wasted bandwidth for different link layer technologies, i.e.,
Ethernet and 5G links. Feng et al. [FeYa21] minimize the response time of
tasks which may be dependent on streams as they consider the joint scheduling
of streams and tasks. Chaine et al. [Ca18] maximize the length of transmission
time windows of streams at their respective talkers such that latency and
jitter requirements are met. This is the only work in TSN scheduling which
employs a quadratic objective function.

Research work |  Topology |  ES |  Bridges |  Streams
---|---|---|---|---
Steiner [St10] |  Star, Tree, Snowflake |  N/A |  N/A |  100 – 1000
Duerr et al. [DuNa16] |  ER, RRG, BA |  24–100 |  5–20 |  30–1500
Pop et al. [PoRa16] |  N/A |  3–5 |  1–2 |  3–5
Craciunas et al. [CrOl16] |  N/A |  3–7 |  1–5 |  5–1000
Farzaneh et al. [FaKu17] |  Snowflake |  12 |  2 |  14–100
Raagaard et al. [RaPo17] |  N/A | 4–402 |  15–290
Steiner et al. [StCr18] |  N/A |  50 |  10 |  10–50
Gavriluţ et al. [GaPo18] |  Star, Snowflake |  3–32 |  1–18 |  4–35
Oliver et al. [OlCr18] |  Line |  50 |  10 |  10–50
Jin et al. [JiXi19] |  N/A |  5–30 |  5–30 |  10–60
Santos et al. [SaCa19] |  N/A |  50 |  10 |  1 – 10
Park et al. [PaSa19] |  Automotive |  5 – 20 |  3 – 7 |  100 – 500
Hellmanns et al. [HeGl20] |  Ring of rings | 100–2500 |  10–2000
Jin et al. [JiXi20] |  N/A |  N/A |  6–20 |  10–10000
Reusch et al. [ReZh20] |  Snowflake |  3–256 |  1–146 |  14–316
Reusch et al. [RePo20] |  Various |  4–32 |  1–16 |  N/A
Li et al. [LiLi20] |  Various |  30 – 100 |  7 – 20 |  3 – 100
Barzegaran et al. [BaZa20] |  Various |  5 – 20 |  2 – 20 |  8 – 27
Ginthör et al. [GiGi20] |  N/A |  N/A |  N/A |  10
Zhou et al. [ZhLi20] |  Automotive |  5 |  16 |  N/A
Vlk et al. [VlHa20] |  Mesh, Ring, Tree |  4 – 16 |  1 – 4 |  6 – 450
Houtan et al. [HoAs21] |  Snowflake |  6 |  2 |  10
Kim et al. [KiCh21] |  Various |  7 |  5 |  6
Barzegaran et al. [BaPo21] |  Various |  6 – 20 |  2 – 20 |  8 – 27
Dai et al. [DaWa21] |  Link |  N/A |  N/A |  3
Hellmanns et al. [HeHa21] |  Ring of rings |  N/A |  N/A |  50–500
Kim et al. [KiLe21][KiLe22] |  Automotive |  17 |  4 |  27
Feng et al. [FeYa21] |  N/A |  50 |  10 |  11
Feng et al. [FeCa21] |  N/A |  2 – 8 |  2 – 5 |  2 – 16
Pang et al. [PaHu21] |  |  31 – 54 |  13 – 31 |  N/A
Vlk et al. [VlBr22] |  Ring of lines, Ring of trees, Avionics |  $\sim$ 20 – 1700 |  $\sim 20$ – 300 |  1500 – 12000
Craciunas et al. [CrOl21] |  Tree |  16 |  7 |  96
Feng et al. [FeDe22] |  N/A |  5 – 8 |  3 – 5 |  N/A
Wang et al. [WaYa22] |  N/A |  4 – 10 |  3 – 9 |  10 – 100
Chaine et al. [CaBo22] |  Line, Avionics |  2 – 31 |  4 – 15 |  15 – 304
Bujosa et al. [BuAs22] |  Line |  3 – 9 |  1 – 3 |  N/A
Barzegaran et al. [BaRe22] |  Various |  3 – 31 |  2 – 15 |  7 – 137
Table 6: Overview of investigated problem instances in the literature of the scheduling problem with fixed routing, sorted by publication year. Research work |  Topology |  ES |  Bridges |  Streams
---|---|---|---|---
Gavriluţ et al. [GaZa17] |  N/A |  4–20 |  N/A |  4–38
Schweissguth et al. [ScDa17] |  Ring, Mesh |  13 |  N/A |  60
Smirnov et al. [SmGl17] |  N/A |  N/A |  N/A |  5 – 75
Kentis et al. [KeBe17] |  Ring, Mesh |  12 |  12 |  20–52
Falk et al. [FaDu18] |  Line, Ring, BA, ER | 5–36 |  2–30
Gavriluţ et al. [GaZh18] |  Various |  3–256 |  2–146 |  4–427
Pozo et al. [PoRo18] |  Synthetic |  6–8 |  3–8 |  10–50
Pahlevan et al. [PaOb18] |  Grid, Ring |  27–45 |  9 |  30–40
Atallah et al. [AtBa18] |  N/A |  6 – 24 |  N/A |  30 – 600
Pahlevan et al. [PaTa19] |  Grid, Ring |  50 |  10 |  60–100
Alnajim et al. [AlSa19] |  N/A |  30–150 |  10–50 |  100–1500
Atallah et al. [AtBa20] |  N/A |  N/A |  3–21 |  20–60
Falk et al. [FaDu20] |  Ring w/ $k$ neighbors | 50–400 |  50–150
Wang et al. [WaCh20] |  N/A |  25 |  5 |  10–100
Syed et al. [SyAy20] |  Automotive |  N/A |  N/A |  20–90
Reusch et al. [RePo20] |  Various |  4–32 |  1–16 |  N/A
Xu et al. [XuXu20] |  Mesh |  5 |  1 – 23 |  4 – 12
Yu et al. [YuGu20] |  Mesh |  72 |  24 |  1 – 500
Schweissguth et al. [ScTi20] |  Ring, Mesh |  12 |  12 |  25 – 40
Yu et al. [YuWa20] |  BA |  72 |  24 |  10 – 350
Arestova et al. [ArHi20] |  N/A |  50 |  10 |  10 – 100
Syed et al. [SyAy21] |  Automotive |  N/A |  N/A |  100–500
Syed et al. [SyAy21b] |  Automotive |  N/A |  N/A |  100–500
Zhou et al. [ZhSa21] |  ER, Automotive |  16 |  6–10 |  50–380
Zhou et al. [ZhSa21b] |  ER, Automotive |  N/A |  6–10 |  50 – 240
Mahfouzi et al. [MaAm18][MaAm21] |  ER, Automotive |  20 |  10–45 |  19–106
Vlk et al. [VlHa21b] |  Ring, Mesh |  12 – 48 |  12 – 48 |  10 – 300
Li et al. [LiZh21] |  N/A |  39 |  16 |  10 – 40
Zhou et al. [ZhWa21] |  Mesh |  $\geq 4$ |  3 – 15 |  50 – 650
Huang et al. [HuWa21] |  Avionics, ER |  N/A |  N/A |  500 – 2000
Li et al. [LiCh21] |  ER, RRG, BA |  10 |  10 |  10 – 100
Nie et al. [NiLi22] |  Ring, Mesh |  11 – 14 |  4 – 15 |  10 – 40
Li et al. [LiJi22] |  Mesh, Automotive |  15 – 105 |  3 – 21 |  2 – 4000
Reusch et al. [ReCr22] |  Various |  4 – 128 |  2–64 |  2 – 144
Zhou et al. [ZhSa22] |  ER, Real-world |  16 |  4–64 |  30 – 220
Xu et al. [XuXu22] |  Mesh, Ring |  N/A |  7–15 |  40 – 80
Li et al. [LiXi22] |  Real-world |  31 |  13 |  100 – 300
Berisa et al. [BeZh22] |  Ring, Full mesh, Avionics |  13 – 31 |  4 – 15 |  222
Table 7: Overview of investigated problem instances in the literature of the
joint routing problem, sorted by publication year.

###  V-C Problem Instances

Before we describe evaluation results, we describe the problem instances used
for evaluations in the literature. We present an overview of used network
topologies, network sizes, and numbers of streams. Tables 6 and 7 compile this
information about the problem instances used for evaluations with fixed
routing and joint routing, respectively. Unfortunately, some research works do
not elaborate on the used topologies, which makes assessing and comparing the
results to other works harder. Most research works only use synthetic test
cases. Ring topologies are commonly used in evaluations, e.g., in [ScDa17],
[HeGl20], [FaDu18], [NiLi22], [PaTa19], [XuXu20], [PaOb18], [FaDu20],
[VlHa21b], and [ScTi20]. Hellmanns et al. [HeGl20] argue that rings are a
common topology in real-world industrial facilities. Other systematic
topologies used include line [OlCr18][FaDu18], grid [PaTa19][PaOb18], and
snowflake-like [ReZh20][HoAs21][FaKu17][GaPo18] networks. Various randomly
generated topologies are also used in evaluations. Erdős–Rényi graphs (ER) are
the most common ones [DuNa16][FaDu18][ZhSa21][ZhSa21b][ZhSa22][LiCh21], but
Barabási-Albert graphs (BA) [DuNa16][FaDu18][LiCh21][YuGu20] and random
regular graphs (RRG) [DuNa16][LiCh21] are also used. A few research works
features evaluations with real-world topologies. Syed et al.
[SyAy20][SyAy21][SyAy21b] use a real-world automotive architecture for their
evaluations. Other automotive architectures are used by Kim et al.
[KiLe21][KiLe22], Li et al. [LiJi22], and Mahfouzi et al. [MaAm18][MaAm21].
Zhou et al. [ZhSa21][ZhSa21b] conclude their evaluations by investigating a
real-world example from General Motors. Pang et al. [PaHu21] evaluate an
algorithm for schedule updates in a real-world in-train network. Vlk et al.
[VlBr22], Chaine et al. [CaBo22], Huang et al. [HuWa21], and Berisa et al.
[BeZh22], perform evaluations with real-world topologies from avionics. The
authors of [GaZa17] use a real-world problem instance from General Motors.
However, this instance is only a set of streams without topology. Barzegaran
et al. [BaRe22] also presents evaluations with real-world test cases from
General Motors and avionics.

All research works concerned with synthetic test cases use randomly generated
streams. Sources and destinations of these streams are selected uniformly from
the sets of talkers and listeners in the respective topology. The number of
streams varies considerably between different research works. It ranges from 2
streams in the smallest instance of Falk et al. [FaDu18] to up to 10812
streams in the largest instance of Vlk et al. [VlBr22]. All works, which
describe the placement of deadlines, place them at the end of the respective
stream’s period. No research work allows deadlines to be after the end of the
hyperperiod a frame was sent. Stream periods range from $32\,\mu s$ in
[JiXi20] to $500\,ms$ in [CrOl16].

###  V-D Scalability

Almost all research works about TSN scheduling include or even focus on
evaluations of the scalability of the respective proposed approach. These
evaluations measure the solving times for selected problem instances. Table 8
compiles the reported runtimes needed to solve the largest problem instance
for which a schedule was found in the respective research work. Table 9
reports the same results for research works which feature the joint
computation of schedules and routings. Both tables are divided in exact and
heuristic algorithms. The tables are meant to show general tendencies and
improvements over time, not to suggest one approach over the other. Caution is
needed when interpreting the table. It shows the reported times after which an
algorithm terminated, not the time until a first valid schedule was obtained,
as almost all papers do not report this time. This is a systematic
disadvantage of exact approaches as they only terminate when the optimal
solution is found or some timeout is reached, while heuristic algorithms
terminate much earlier with suboptimal solutions. Some research works deal
with more parameters than the size of the network and the number of streams,
e.g., Oliver et al. [OlCr18] present evaluations about the influence of the
number of transmission windows per egress port to scalability. Other works
handle problem extensions, e.g., AVB or task scheduling. Approximations are
given when results are not stated in the text and had to be estimated by the
presented figures. Ranges are given when multiple instances are considered to
be the largest. We identified two tendencies with respect to solving times.

First, heuristic approaches can handle larger instances than approaches with
exact solution methods. While the number of network nodes is approximately in
the same range, heuristic algorithms can schedule problem instances with more
streams compared to exact approaches. Typical numbers of streams in exact
approaches are less than 100, e.g., in [ScDa17], [CrOl21], and [FaDu18].
However, there are some notable exceptions. Craciunas et al. [CrOl16] present
an incremental scheduling algorithm with backtracking, which scheduled
instances with 1000 streams in their evaluations. Later works present
incremental approaches which were able to schedule as many as 2000 streams
[HuWa21]. Oliver et al. [OlCr18] assigned streams to transmission windows of
egress ports and report solved instances with 750 streams. Heuristic
approaches were able to schedule instances with more than 10000 streams, e.g.,
[VlBr22] and [JiXi20].

Second, exact approaches which solve the joint routing and scheduling problem
can only handle instances with smaller numbers of nodes compared to approaches
solely for scheduling. Typical networks in evaluations of joint routing
algorithms contain less than 50 nodes [AtBa20][RePo20][GaZa17]. This is due to
the solution space growing heavily with an increased number of possible paths
per stream. However, there are approaches able to compute routings and
schedules for problem instances with up to 96 nodes [VlHa21b][YuGu20]. Most
networks in the literature of scheduling with a fixed routing contain less
than 96 nodes. The range for the number of streams is approximately the same.

Research work |  Solution Approach |  Nodes |  Streams |  Runtime (s)
---|---|---|---|---
Steiner [St10] |  SMT |  N/A |  1000 |  $\sim 180$ – $1140$
Pop et al. [PoRa16] |  ILP |  7 |  5 |  $80.19$
Craciunas et al. [CrOl16] |  SMT |  12 |  1000 |  $<18000$
Farzaneh et al. [FaKu17] |  SMT |  14 |  100 |  $<240$
Oliver et al. [OlCr18] |  SMT |  20 |  750 |  $\sim 600$
Steiner et al. [StCr18] |  SMT |  60 |  50 |  $\sim 0.01$ – $100$
Santos et al. [SaCa19] |  SMT |  60 |  10 |  $<288000$
Jin et al. [JiXi19] |  SMT |  4 |  4 |  $<600$
Jin et al. [JiXi20] |  SMT |  6 |  50 |  $660$–$1080$
Li et al. [LiLi20] |  SMT |  120 |  100 |  $\sim 320$ – $450$
Barzegaran et al. [BaZa20] |  CP |  40 |  27 |  2563
Ginthör et al. [GiGi20] |  CP |  N/A |  10 |  N/A
Zhou et al. [ZhLi20] |  SMT |  21 |  N/A |  N/A
Vlk et al. [VlHa20] |  ILP |  20 |  414 |  $\leq 600$
Houtan et al. [HoAs21] |  SMT |  8 |  10 |  $0.37$–$1153.52$
Craciunas et al. [CrOl21] |  SMT |  23 |  96 |  $\sim 0.343$ – $0.437$
Feng et al. [FeCa21] |  SMT |  13 |  16 |  N/A
Dai et al. [DaWa21] |  CP |  N/A |  3 |  N/A
Feng et al. [FeYa21] |  SMT |  60 |  11 |  384 – 694
Pang et al. [PaHu21] |  ILP |  86 |  N/A |  $\sim$ 620 – 900
Nie et al. [NiLi22] |  ILP |  26 |  40 |  $\sim$ 0 – 10
Feng et al. [FeDe22] |  SMT |  13 |  N/A |  $\sim 900$
Chaine et al. [CaBo22] |  ILP |  46 |  304 |  $\sim 240$
Barzegaran et al. [BaRe22] |  CP |  120 |  500 |  N/A
Duerr et al. [DuNa16] |  Tabu Search |  120 |  1500 |  11520
Raagaard et al. [RaPo17] |  Heuristic |  402 |  290 |  20–54
Gavriluţ et al. [GaPo18] |  GRASP |  50 |  35 |  $612.8$
Atallah et al. [AtBa18] |  Heuristic |  24 |  600 |  $\sim 8$
Park et al. [PaSa19] |  GA |  $<$ 27 |  500 |  N/A
Jin et al. [JiXi20] |  Heuristic |  20 |  10000 |  $\sim 5100$
Hellmanns et al. [HeGl20] |  Tabu Search |  2500 |  2000 |  $\sim 4400$
Reusch et al. [ReZh20] |  Heuristic |  402 |  316 |  $10.52$
Barzegaran et al. [BaZa20] |  CP + Heuristic |  40 |  27 |  161
Kim et al. [KiCh21] |  Heuristic |  12 |  6 |  N/A
Barzegaran et al. [BaPo21] |  CP + Heuristic |  40 |  27 |  3553 – 9153
Kim et al. [KiLe21][KiLe22] |  GA |  21 |  27 |  12300
Vlk et al. [VlBr22] |  Heuristic |  2000 |  10812 |  $\sim 1000$
Wang et al. [WaYa22] |  Machine Learning |  19 |  100 |  $\sim 400$
Bujosa et al. [BuAs22] |  Heuristic |  12 |  N/A |  $<0.01$
Table 8: Overview of solving times of the respective largest reported problem
instance for which a schedule with a fixed routing was found.

Research work |  Solution Approach |  Nodes |  Streams |  Runtime (s)
---|---|---|---|---
Gavriluţ et al. [GaZa17] |  CP |  20 |  38 |  $172800$
Schweissguth et al. [ScDa17] |  ILP |  24 |  52 |  $1284.53$
Smirnov et al. [SmGl17] |  PBO |  N/A |  75 |  $\sim$ 42 – 78
Falk et al. [FaDu18] |  ILP |  8 |  30 |  $\sim 170$ – $1580$
Pozo et al. [PoRo18] |  ILP |  16 |  50 |  2–85
Atallah et al. [AtBa20] |  ILP |  14 |  60 |  $\sim 100$
Syed et al. [SyAy20] |  ILP |  N/A |  90 |  $\sim 21000$
Reusch et al. [RePo20] |  CP |  48 |  N/A |  $\sim 1800$
Xu et al. [XuXu20] |  SMT |  24 |  12 |  $\sim 144000$
Yu et al. [YuGu20] |  ILP |  96 |  450 |  N/A
Schweissguth et al. [ScTi20] |  ILP |  24 |  $\sim 46$ – 60 |  N/A
Zhou et al. [ZhSa21] |  SMT |  10 |  380 |  $\sim 2700$
Zhou et al. [ZhSa21b] |  SMT |  10 |  240 |  $\sim 3500$ – $4000$
Mahfouzi et al. [MaAm18][MaAm21] |  SMT |  65 |  45 |  $\sim 21$
Hellmanns et al. [HeHa21] |  ILP |  N/A |  N/A |  50–500
Vlk et al. [VlHa21b] |  CP |  96 |  300 |  $\sim$ 100
Li et al. [LiZh21] |  ILP |  55 |  40 |  $\sim 80$
Huang et al. [HuWa21] |  ILP |  44 |  2000 |  1620
Zhou et al. [ZhSa22] |  SMT |  24 |  220 |  $\sim$ 55 – 440
Xu et al. [XuXu22] |  SMT |  12 |  80 |  $\sim$ 850
Reusch et al. [ReCr22] |  CP |  48 |  33 |  $1500$
Gavriluţ et al. [GaZa17] |  GRASP |  20 |  38 |  $558$
|  Heuristic |  20 |  38 |  $130$
Kentis et al. [KeBe17] |  Heuristic |  $\geq 13$ |  60 |  N/A
Gavriluţ et al. [GaZh18] |  GRASP |  402 |  427 |  534.6
Pahlevan et al. [PaOb18] |  List scheduler |  45 |  40 |  $0.014$
|  Genetic algorithm |  45 |  40 |  $56.75$
Pahlevan et al. [PaTa19] |  List scheduler |  50 |  100 |  $0.103$
|  Heuristic |  50 |  100 |  $1.58$
Alnajim et al. [AlSa19] |  Heuristic |  200 |  1500 |  $2718$
Falk et al. [FaDu20] |  Heuristic |  400 |  400 |  $\sim 6000$ – $11000$
Wang et al. [WaCh20] |  Heuristic |  30 |  100 |  $72$
Yu et al. [YuWa20] |  Heuristic |  96 |  350 |  N/A
Arestova et al. [ArHi20] |  Genetic algorithm |  60 |  100 |  $\sim$ 470
Syed et al. [SyAy21] |  Heuristic |  N/A |  500 |  $0.170$
Syed et al. [SyAy21b] |  Heuristic |  N/A |  500 |  $0.41$
Zhou et al. [ZhWa21] |  Heuristic |  N/A |  650 |  $\sim 2700$
Li et al. [LiCh21] |  Heuristic |  20 |  100 |  N/A
Reusch et al. [ReCr22] |  SA + list scheduler |  192 |  144 |  $1200$
Li et al. [LiXi22] |  ILP + heuristic |  44 |  300 |  $\sim 0.3$
Li et al. [LiJi22] |  Heuristic |  126 |  4000 |  0.437 – 0.88
Berisa et al. [BeZh22] |  Heuristic |  46 |  222 |  602 – 7090
Table 9: Overview of solving times of the respective largest reported problem
instance for which a joint schedule and routing was found.

##  VI Publication History

We give an overview of the publication history of TSN scheduling. First, we
highlight seminal works from the literature. Then, we analyze the development
of the field with respect to the number of published papers per year.

###  VI-A Seminal Works

Early works about per-flow scheduling in Ethernet networks were presented by
Steiner [St10] and Schweissguth et al. [ScDa17]. While these works are not
specifically for TSN and abstract on the details of the real-time enhancement
for Ethernet. they influenced many later works presented in this survey. The
first works specifically about scheduling in TSN were presented in 2016. Dürr
et al. [DuNa16] presented an ILP for no-wait scheduling and identified the
problem of guard bands consuming bandwidth. Craciunas et al. [CrOl16] adapted
the work of Steiner [St10] for TSN. They introduced isolation constraints and
incremental scheduling to the domain of TSN. Gavrilut et al. [GaZa17] is the
first work which features joint routing and reliability considerations.
Raagard et al. [RaPo17] introduced reconfiguration of schedules to TSN
scheduling. Oliver et al. [OlCr18] proposed a scheduling approach with limits
the number of used GCL entries by computing them in a joint approach with
transmission offsets. All earlier works computed GCLs by a post-processing
after scheduling.

###  VI-B Published Papers

Figure 19 shows the number of papers about TSN scheduling per year. The first
papers about scheduling in TSN were published in 2016. The general trend is
that the field grows almost monotonously from one year to the next, with only
one exception in 2019. We observe a significant increase in published works
since the year 2020. Only preliminary results for 2022 are shown, as the scope
of this survey covers papers published until June 2022. Given the fast growth
of the last 2 years, we expect even more research works about TSN scheduling
in the future.

Figure 19: Number of published research works per year about TSN scheduling.
Only works published before June 2022 are counted.

##  VII Discussion

In this section, we discuss the results of the literature study. First, we
suggest improvements for future research works. Then, we highlight open
problems not handled sufficiently so far.

###  VII-A Suggestions for Improvement

The surveyed literature features many high quality research works. However,
there is room for improvement in the presentation of some of these works. We
suggest improvements in the hope that the overall quality of the TSN
scheduling literature can be improved even more in the future. First, we
discuss shortcomings and improvements in the presentation of evaluation
methodologies. Then, we suggest the use of the technical terminology used in
Ethernet bridging.

####  VII-A1 Evaluation Methodologies

The scalability of the proposed solutions from the literature was extensively
evaluated. Unfortunately, the impact of possible additional features and
changes in parameters to the various objective functions was mostly ignored so
far. Although scalability is an important property of a scheduling algorithm,
it would be interesting to see more evaluations regarding solution quality.
Most test cases in the literature are synthetically constructed, both network
topology and streams. Even though it is hard to obtain test cases from the
industry, let alone publish them, we would like to see more evaluations with
realistic instances. It is not clear whether the proposed algorithms are
suitable for large industry-scale instances or how they look like. It is also
extremely difficult to compare the results of different research works as
there is no public set of test cases for benchmarks. Consequently, there is
little research work available about which algorithm should be used in which
setting. Unfortunately, it is also hard to assess the significance of
evaluation results in some papers for two reasons. First, the instances solved
are not sufficiently described. At least the topology and a description of
assumed delays, e.g., processing and propagation delay, should be contained in
the description of the network. Important properties of streams like deadlines
or periods are often missing. Second, some evaluations report results for
individual problem instances and are thus more of anecdotal character. There
are easy and hard instances for every algorithm. Comparing multiple approaches
on the same selected instances can be useful, but this may have the taste of
picking specific instances in support of some conclusion. Instead of reporting
results for individual instances, average results for multiple instances with
the same evaluation setting should be reported. Another property covered by
many evaluations is the schedulability of the respective proposed approach.
These evaluations treat instances as infeasible when no schedule was found
before some timeout. Thus, comparing the schedulability of two scheduling
approaches which support different features is biased, as timeouts do not
prove infeasibility. This may lead to wrong conclusions in favor of some
algorithm or model, although schedulability is actually equal.

####  VII-A2 Terminology

Many works surveyed in this paper use a vocabulary loosely related to Ethernet
bridging. However, the standards and other relevant literature use a specific
technical terminology. We recommend that the scheduling community adopts this
jargon. Readers from adjacent research domains or who have prior knowledge in
Ethernet bridging can benefit from a consistent vocabulary. Therefore, the
word stream should be used instead of flow. Network devices which send or
receive data streams are denoted as end stations. The source end station of a
stream is denoted as talker, while the destination end station is denoted as
listener. Layer 2 switching devices are denoted as bridges instead of
switches. Frames are the units of data transmission, as TSN is a layer 2
technology. Although the meaning of the term packet is clear in the context of
scheduling, it is technically wrong. Routing is the process of path
computation on layer 3. Therefore, the term path selection is more appropriate
in TSN. However, we note that we used the term routing in this survey several
times. The reason for this is to ensure consistency with the reviewed
literature which solves the so-called joint routing problem.

###  VII-B Open Problems

The available literature is comprehensive with regard to solution approaches
to the unmodified scheduling problem in TSN. However, there is still a wide
field of relevant aspects which are not yet understood.

####  VII-B1 Impact of Guard Bands and GCL Entries

To the best of our knowledge, the impact of guard bands on bandwidth available
to lower-priority traffic was not evaluated in the literature. Likewise, the
impact of available GCL entries on available bandwidth for lower-priority
traffic is not investigated in detail. The evaluations so far suggest that AVB
streams benefit from schedules with many holes between TT streams with regard
to tardiness. However, such schedules may need more gate closings and thus
guard bands, which reduces the available bandwidth. It is not clear how AVB
and BE traffic can be simultaneously integrated in a unified approach for the
scheduling of TT streams.

####  VII-B2 Routing and Multicast

The joint routing and scheduling problem was explored in detail in the
literature. All research works about this topic agree that schedulability
benefits from joint routing and scheduling. However, solving the joint routing
problem is significantly harder compared to scheduling with a given routing.
Unfortunately, there is currently no exact and scalable approach known for
joint routing. Additionally, it is not understood which properties a routing
should have to benefit schedule synthesis and quality. TSN supports multicast
streams which are relevant in real use cases. Some of the algorithms presented
in research works covered by this survey can handle multicast streams.
However, the literature lacks evaluations and insights about the appropriate
integration of multicast streams in a schedule.

####  VII-B3 Online Reconfiguration

There is also little work about online schedule reconfiguration, though it is
important for operation. In some scenarios, e.g., automotive networks,
insertion and removal of streams at execution time of the schedule can be
important. So far it is not explored exhaustively what properties a schedule
should have such that reconfiguration can by computed efficiently.
Additionally, there are no reconfiguration algorithms for most of the problem
extensions from Section III-E.

####  VII-B4 Queuing and Handling of Non-Determinism

An important open problem in TSN is sufficient integration of queuing. Almost
all research works use isolation constraints from [CrOl16], i.e., they do not
allow frames of different streams to reside in the same queue at the same
time. However, this is not a requirement of the TAS. Some approaches even
separate streams by assigning them to different egress queues during
scheduling. The rational of this is to reduce the impact of non-determinism
like frame loss. Other attempts to reduce the influence of such causes of non-
determinism are not yet explored. The benefits of unrestricted queuing
regarding schedulability or solution quality has not yet been evaluated.

Real hardware bridges are subject to non-determinism. There is jitter in
processing delays, and clocks are not exactly synchronized in reality.
Additionally, frames that are scheduled to arrive approximately at the same
time at two ingress ports of the same bridge may cause race conditions, i.e.,
processing order is not deterministic. All research works covered by this
survey assume bridges are perfectly deterministic. Thus, the literature lacks
handling of such causes of non-determinism.

####  VII-B5 Support of PSFP

Per-Stream Filtering and Policing (PSFP) is a standard defined in IEEE
802.1Qci [802.1Qci] for filtering and policing in TSN. Currently, there are no
devices available implementing PSFP. However, filtering and policing could be
used to prevent violations of schedules through unexpected packets. Packets
not scheduled, delayed frames, and frames larger than expected can be filtered
at execution time of a schedule. Thus, PSFP requires configuration of
filtering entries that need to be derived from the schedule. A joint approach
may be needed as PSFP imposes additional restrictions, e.g., the number of
available filtering entries will be limited in bridges.

####  VII-B6 Use of TSN Mechanisms

TSN is not limited to scheduled traffic and the TAS. Other traffic classes may
have real-time requirements, but cannot be scheduled as the respective streams
are not periodic. Different traffic classes may have different sets of real-
time requirements, e.g., demanding bounded jitter instead of bounded latency.
TSN features more mechanisms which may be applied to fulfill these
requirements, such as Asynchronous Traffic Shaping [802.1Qcr] or Cyclic
Queuing and Forwarding [802.1Qch]. A major open problem in TSN is the
coexistence of multiple mechanisms and the assignment of streams to them.
Input may be a set of streams or traffic rates with their descriptors and
real-time requirements, and output is their assignment to appropriate TSN
mechanisms together with the complete network configuration. This problem goes
far beyond the TSN scheduling problem, but may impose additional constraints
on the latter. Some requirements can only be fulfilled by scheduling the
respective streams and computing GCLs for the TAS. Others may not even know
the traffic streams in advance and can be implemented by the CBS or even
simpler mechanisms. As even computing GCLs for the TAS is a challenging task
for current state-of-the-art scheduling and optimization algorithms, such a
comprehensive approach is currently unreachable. Hopefully, future works will
move towards such long term goals and enable users to exploit the full
potential of TSN.

####  VII-B7 Understanding of the TSN Problem

So far, scalability analyses have been conducted on special algorithms.
However, they do not provide insights in what makes the TSN problem hard. This
also pertains to all problem extensions like joint routing and multicast,
reliability, robustness, BE or ABE traffic, etc. Moreover, properties of
schedules such as tightness or average duration of open periods of the TAS
have not yet been investigated. It would be helpful to understand the impact
of problem extensions on the structure of schedules in an intuitive way. A
better understanding of extensions and their impact on schedule structure may
facilitate the development of heuristic algorithms that solve larger instances
of the TSN problem with acceptable quality compared to exact approaches.

##  VIII Conclusion

TSN is a set of standards to enable real-time transmission over switched
Ethernet networks. IEEE 802.1Qbv [802.1Qbv] defines traffic scheduling
combined with the Time-Aware Shaper (TAS), i.e., transmissions of periodic
high-priority streams are scheduled such that packets hardly interfere and
that ultra-low latency is achieved. Moreover, the TAS protects scheduled
traffic against traffic from other traffic classes. This approach requires the
configuration of transmission times for streams at the Talkers (source nodes)
as well as the configuration of the TAS on the switches.

In this paper, we first gave an introduction to TSN with focus on traffic
scheduling and the TAS. We defined the “TSN scheduling problem” and discussed
common extensions such as scheduling with fixed or joint routing, various
forms of queuing, support for reliability or lower-priority traffic, or
respecting technical restrictions. Some of these extensions lead to
optimization problems. We summarized frequently used scheduling and
optimization methods to tackle these challenges. Then we reviewed a large body
of literature about the TSN scheduling problem and classified it regarding the
mentioned extensions. Subsequently, we analyzed and compared the works with
respect to modelling assumptions, scheduling objectives, problem instances,
and scalability, and pointed out advances. We tracked seminal works and
identified popular publication venues for TSN scheduling. We discussed the
area by suggesting improvements and pointing out open problems.

This survey serves researchers to identify the current state of the art and
open problems in TSN scheduling. The many problem extensions suggest that the
construction of an efficient scheduling or optimization algorithm which
considers all relevant aspects is infeasible. We expect future work to provide
a better understanding of the complexity of the TSN scheduling problem to
cover more problem extensions while maintaining scalability.

### Acknowledgments

The authors thank Manuel Eppler and Lukas Wüsteney for valuable input and
stimulating discussions. This work has been supported by the German Federal
Ministry of Education and Research (BMBF) under support code 16KIS1161
(Collaborative Project KITOS). The authors alone are responsible for the
content of the paper.

  *[TSN]: Time-Sensitive Networking
  *[TAS]: Time-Aware Shaper
  *[ILP]: Integer Linear Programming
  *[SMT]: SAT Modulo Theory
  *[OMT]: Optimization Modulo Theory
  *[CP]: Constraint Programming
  *[PBO]: Pseudo-Boolean Optimization
  *[ILPs]: Integer Linear Programming
  *[GRASP]: Greedy Randomized Adaptive Search Procedure
  *[BE]: Best Effort
  *[AVB]: Audio Video Bridging
  *[QoS]: Quality of Service
  *[GCL]: Gate Control List
  *[TT]: Time-Triggered