# A Survey of Scheduling in Time-Sensitive Networking (TSN)

Thomas Stüber, Lukas Osswald, Steffen Lindner, Michael Menth
Chair of Communication Networks, University of Tuebingen, Germany
{thomas.stueber, lukas.osswald, steffen.lindner<EMAIL_ADDRESS>
###### Abstract

Time-Sensitive Networking (TSN) is an enhancement of Ethernet which provides
various mechanisms for real-time communication. Time-triggered (TT) traffic
represents periodic data streams with strict real-time requirements. Amongst
others, TSN supports scheduled transmission of TT streams, i.e., the
transmission of their packets by edge nodes is coordinated in such a way that
none or very little queuing delay occurs in intermediate nodes. TSN supports
multiple priority queues per egress port. The Time-Aware Shaper (TAS) uses so-
called gates to explicitly allow and block these queues for transmission on a
short periodic timescale. The TAS is utilized to protect scheduled traffic
from other traffic to minimize its queuing delay. In this work, we consider
scheduling in TSN which comprises the computation of periodic transmission
instants at edge nodes and the periodic opening and closing of queue gates.

In this paper, we first give a brief overview of TSN features and standards.
We state the TSN scheduling problem and explain common extensions which also
include optimization problems. We review scheduling and optimization methods
that have been used in this context. Then, the contribution of currently
available research work is surveyed. We extract and compile optimization
objectives, solved problem instances, and evaluation results. Research domains
are identified, and specific contributions are analyzed. Finally, we discuss
potential research directions and open problems.

###### Index Terms:

Time-sensitive networking (TSN), Time-aware shaper (TAS), Scheduling,
Optimization, Ethernet Bridging

###  -A List of Frequently Used Acronyms

The following acronyms are used in this paper.

AVB

    Audio Video Bridging
BE

    Best Effort
CP

    Constraint Programming
CBS

    Credit-Based Shaper
GCL

    Gate Control List
FIFO

    First-In-First-Out
GRASP

    Greedy Randomized Adaptive Search Procedure
ILP

    Integer Linear Programming
OMT

    Optimization Modulo Theory
PBO

    Pseudo-Boolean Optimization
QoS

    Quality of Service
SMT

    SAT Modulo Theory
SRP

    Stream Reservation Protocol
TAS

    Time-Aware Shaper
TSA

    Transmission Selection Algorithm
TSN

    Time-Sensitive Networking
TT

    Time-Triggered
VLAN

    Virtual LAN

##  I Introduction

Modern applications, e.g., Industry 4.0 factory automation and motion control,
demand highly deterministic network service. Exceeding latency and jitter
bounds can result in immediate degradation of manufacturing quality or
endanger health of machinery and operators.  Some of these applications have
to exchange data streams with precise timing to keep application-specific
deadlines. Time-Sensitive Networking (TSN) is an emerging technology which
enhances Ethernet networks with real-time properties. In TSN, talkers send
uni- or multicast streams, called streams, to traffic sinks, called listeners.
The network admits streams and guarantees quality of service (QoS). Time-
triggered (TT) traffic constitutes periodic data streams with real-time
requirements such as bounded latency or jitter. The transmission times of TT
streams at their respective talkers must be scheduled such that excessive
queuing in the network is avoided and their requirements are met. Although TT
traffic has high priority, it is delayed by low-priority frames in
transmission blocking links for short time. To ensure that links are not
occupied by low-priority traffic when needed for TT traffic, the Time-Aware
Shaper (TAS) is introduced in IEEE Std 802.1Qbv [802.1Qbv]. It defines
periodic time slices during which queues may send traffic to an output port
and delays the respective traffic. In TSN, TAS is used to protect TT traffic
from other traffic classes. Therefore, TSN requires that appropriate TAS time
slices are scheduled for output queues on all switches, in addition to the
transmission times of all TT streams at their talkers. This combination
guarantees very short delays for TT streams in TSN.

Standardization does not yet cover methods for computing such schedules.
However, the topic has been examined by many publications. These research
works use different methods for schedule synthesis, evaluation, and objectives
for optimization. We survey the currently available literature for TSN
schedule computation. The paper focuses on publications published until June
of 2022 about TSN schedule planning with the TAS. Works about stream
scheduling related to other technologies than TSN are not covered in this
survey.

Paper | Date | References |  Focus |  # Common referenced papers with this survey
---|---|---|---|---
Nasrallah et al. [NaTh19] | 2018 | 407 |  Overview of TSN, DetNet, and 5G standards |  14
Minaeva et al. [MiHa21] | 2021 | 126 |  Scheduling in periodic systems |  6
Seol et al. [SeHy21] | 2021 | 207 |  Broad overview of TSN |  29
Deng et al. [DeXe22] | 2022 | 128 |  Broad overview of all topics related to AVB and TSN |  17
This paper | 2022 | 110 |  Traffic scheduling in TSN with the TAS |  -
Table 1: Surveys covering related topics to this paper.

To the best of our knowledge, no other review covers scheduling algorithms for
TSN as its main topic. In fact, there is no survey about scheduling for TT
streams for Ethernet networks, regardless of the used standard. However, there
are surveys which intersect with the content of this work. Table 1 compiles
the focus and the relationship of these surveys to this paper. Nasrallah et
al. [NaTh19] survey standards for low-latency communication. Besides DetNet
and 5G, they also give a tutorial on the TSN standards. They reference a small
number of papers related to traffic scheduling in TSN. However, they do not
elaborate on the content of these papers and the vast majority of the
literature about traffic scheduling is not even referenced. Minaeva et al.
[MiHa21] give a literature summary for scheduling time-triggered real-time
systems. They highlight research works from 1968 to 2020. As opposed to this
work, they not only consider scheduling of streams in networks, but all
systems with periodic schedules. Seminal works for TNS scheduling algorithms
in the literature are mentioned, e.g., [St10] and [ScDa17]. Out of 126
references, only 6 of them intersect with this work. Deng et al. [DeXe22]
review a wide range of topics about AVB and TSN from the literature of 2007 –
2021. Besides scheduling approaches, they also give an overview of reliability
and security modeling, and delay analysis in the mentioned areas. As a wider
range of topics is covered, only a small part of the survey is concerned with
scheduling. This part is rather superficial, summarizes only 15 works, and is
mostly in tabular form. The algorithms and evaluation results presented in
these 15 works are not discussed. Summing up, only 17 out of the 128 discussed
works intersect with this survey. Seol et al. [SeHy21] review TSN as a whole.
The authors cover publications of the years 2014 – 2020. An overview of active
research directions is given, including computing routings and schedules in
TSN. Not only the literature about scheduling for the TAS is summarized, but
also work concerned with other queuing mechanisms, hardware, and simulation
frameworks. Therefore, only a small fraction of the literature about
scheduling for TAS-based queuing in TSN is surveyed. They cover 207 research
works, of which 29 are included in this work. These works are merely mentioned
in their review, and the authors do not elaborate on their content.

In contrast to the mentioned surveys of Table 1, we focus on papers about
scheduling algorithms and related topics which use the TAS. This survey claims
the following contributions:

  * •

We give a tutorial on TSN basics.

  * •

We define the TSN scheduling problem for TAS and modifications to it.
Additionally, we introduce common solution methods used in the literature

  * •

We survey currently available TSN literature about scheduling for the TAS.

  * •

We identify research directions, categorize the available literature, and
highlight contributions to these topics.

  * •

We compare the available algorithms and the presented evaluations to derive
open research questions in this area.

This paper is structured as follows. In Section II we present a brief
introduction to TSN with a special focus on the TAS. Then, we formally define
the scheduling problem in TSN and give a tutorial to common solutions methods
from literature in Section III. Section IV gives an overview of the state-of-
the-art of TSN scheduling and categorizes the presented literature. Section V
compares the presented research work with regard to modelling assumptions,
optimization objective, problem instances and scalability. Furthermore, we
present the publication history of the surveyed literature in Section VI. We
discuss issues and open research questions in Sections VII. Finally, we
conclude the paper in Section VIII.

##  II Foundations of TSN

TSN is a set of standards for deterministic data transmission with real-time
requirements over Ethernet networks. In this section, we present a short
tutorial about TSN. First, we present AVB based on which TSN was developed.
Then, we introduce TSN with a special focus on scheduling and the TAS.

###  II-A Audio Video Bridging (AVB)

Historically, multimedia equipment was interconnected with half-duplex point-
to-point links for data transmission. These links were often dedicated to a
single purpose, i.e., the transmission of one specific data stream. This
results in a large number of links which is expensive, hard to maintain, and
error prone. Switched computer networks solved these problems. The most widely
adopted technology for switched local area networks today is Ethernet.
However, professional audio and video applications need bounded latencies and
jitter, i.e., real-time guarantees for data streams. Switching in Ethernet
networks was not designed for real-time transmissions. Therefore, the Audio
Video Bridging (AVB) task group of the IEEE was founded to develop a standard
to meet the requirements of multimedia applications in switched Ethernet
networks.

AVB is organized in standards for time synchronization, admission control, and
traffic shaping.

####  II-A1 Time Synchronisation

Network devices need a common understanding of time to ensure that all end
stations in a network are able to coordinate their actions. Every AVB-capable
device is equipped with a clock. The standard IEEE 802.1AS [802.1AS] defines a
protocol to synchronize the clocks of all devices in an AVB network. This
protocol is based on the Precise Time Protocol (PTP) introduced in IEEE 1588
[IEEE1588] and is denoted as generalized Precise Time Protocol (gPTP). The
gPTP defines an algorithm to select a so-called Grandmaster among the
participating nodes of the protocol. The internal clock of the Grandmaster is
used as reference clock. All other devices synchronize their clocks to the
clock of the Grandmaster with time information sent from the Grandmaster.
Intermediate nodes adjust the received time information to compensate
propagation delays, processing delays, and different clock speeds before
retransmitting them. The gPTP allows sub-microsecond precision for devices
with at most seven hops distance to each other. This is needed for
applications running on different end stations to synchronize their actions.

####  II-A2 Admission Control

The Stream Reservation Protocol (SRP) introduced in IEEE 802.1Qat [802.1Qat]
allows senders of periodic data streams, denoted as talkers, to reserve
bandwidth in a multi-hop Ethernet network. A talker which wants to send data
advertises a new data stream to its connected bridge. This advertisement
contains information about bandwidth and real-time requirements, the
periodicity of the stream, and the destination MAC address. The destination
may be a multicast group. The bridge forwards the advertisement if the
requested resources are available. Worst-case latencies are calculated at
every bridge. When the request reaches the destination of a data stream,
denoted as listener, the listener acknowledges that it is ready, and the
bandwidth is reserved along the path.

####  II-A3 Traffic Shaping

Traffic shaping is the generic term for techniques that distribute packet
transmissions in time. The AVB working group defines the so-called Credit-
Based Shaper (CBS) in IEEE 802.1Qav [802.1Qav]. It can be leveraged to smooth
out bursts such that receiving devices are not overwhelmed. This reduces
buffering and congestion in the network. The CBS is a leaky bucket traffic
shaper with at least two FIFO queues for two traffic classes. These classes
are denoted as class A and class B. Both queues have a credit measured in bit.
Dispatching and transmitting a frame from a queue is only allowed if the
credit of the respective queue is non-negative. Credit increases linearly
during times no frame is transmitted and decreases linearly during
transmissions. Latency bounds for streams can be guaranteed by using a special
configuration for the CBS defined in IEEE 802.1BA [802.1BA]. These are
specific to the requirements of the AVB domain, guaranteeing 2 ms and 50 ms
for class A and B traffic in networks with at most 7 hops. However, the
average delay of a frame increases to up to $250\,\mu s$ per hop in the worst
case when the CBS is used.

###  II-B Time-Sensitive Networking (TSN)

Ethernet networks are used in a wide range of industrial use cases as Ethernet
is cheap and easy to implement. However, use cases such as industrial
automation, in-vehicle communication or avionics have hard real-time
requirements and need reliability. Data streams not meeting their deadlines
may not only be worthless but impose safety risks. The latency guarantees and
average delays offered by AVB fail to comply with the requirements of such use
cases.

Time-Sensitive Networking (TSN) is a set of standards enhancing AVB for
deterministic and reliable transmission of data over switched Ethernet
networks. TSN is currently developed in the IEEE 802.1 TSN task group and adds
new mechanisms for scheduling, traffic shaping, path selection, stream
reservation, filtering and policing, and fault-tolerance. Most of the
standards are enhancements of IEEE 802.1Q [802.1Q] which defines bridges and
Virtual LANs (VLANs). We give a brief tutorial on the standards and mechanisms
relevant for the scope of this survey, i.e., traffic scheduling in TSN with
the TAS.

####  II-B1 Similarities to AVB

Similar to AVB, every device in TSN is equipped with a clock. TSN also uses
the gPTP defined in IEEE 802.1AS [802.1AS] to synchronize clocks of all
network devices. The CBS and an enhancement of the SRP are also part of TSN.

####  II-B2 Path Selection

TSN introduces a new mechanism for path selection in IEEE 802.1Qca [802.1Qca].
In contrast to traditional Ethernet networks, it is not necessary to use
Spanning Tree Protocols or Shortest Path Bridging. Paths can be computed by an
arbitrary algorithm and are only limited to be trees. Thus, frames can be
forwarded on an arbitrary path. Forwarding information of these so-called
Explicit Trees are distributed with the Intermediate System to Intermediate
System (IS-IS) protocol and stored in bridges. The Explicit Tree for the
forwarding of a frame is determined by the MAC address of the root bridge of
the Explicit Tree and the VLAN ID in the frame’s header.

####  II-B3 Priorities

Every egress port of a TSN bridge is equipped with up to eight egress queues.
These queues are First-In-First-Out (FIFO) queues. They correspond to the
eight VLAN priorities defined in IEEE 802.1Q [802.1Q]. The VLAN tag in the
header of an Ethernet frame determines the egress queue in which the frame
waits for transmission. Every queue is equipped with a so-called Transmission
Selection Algorithm (TSA). The TSA signals whether a frame is ready for
transmission to a transmission selection mechanism. This mechanism selects the
next queue from which a frame is dispatched and sent. TSN uses strict priority
as transmission selection, i.e., the next frame is dispatched from the highest
priority queue which signals a frame is ready for transmission.

####  II-B4 Frame Preemption

High-priority traffic can be delayed due to conflicts with lower-priority
traffic. IEEE 802.1Qbu [802.1Qbu] describes a mechanism for frame preemption
in TSN which reduces such delays. Traffic is divided into preemptable frames
and so-called express frames. The transmission of preemptable frames is paused
and finished later if an express frame is ready for transmission.
Consequently, a preempted frame is divided into fragments which are
reassembled by the receiving node. The minimum size of a frame fragment is
defined to be 64 byte. However, every fragment of a frame except for the last
one has a trailer containing a 4 byte check sequence for error detection.
Therefore, a frame can only be preempted after at least 60 byte were
transmitted and the last 63 byte of a frame cannot be preempted.

####  II-B5 Traffic Scheduling

Time-triggered (TT) traffic, also denoted as scheduled traffic, consists of
periodic data streams with hard real-time requirements such as bounded
latencies and jitter. The properties of TT streams such as period, maximum
frame size, packets per period, as well as the range of possible transmission
offsets from their respective talkers, are known in advance. The transmission
times of these streams at their respective talkers can be controlled and must
be coordinated to ensure that all streams meet their real-time requirements.
The computation of their periodic transmission times is denoted as traffic
scheduling.

####  II-B6 Traffic Shaping

TSN introduces new traffic shapers in addition to the CBS. Examples for other
shapers which can be used instead of the CBS are Asynchronous Traffic Shaping
(ATS) defined in IEEE 802.1Qcr [802.1Qcr] and Cyclic Queuing and Forwarding
(CQF) defined in IEEE 802.1Qch [802.1Qch]. The Time-Aware Shaper (TAS) is
introduced in IEEE 802.1Qbv [802.1Qbv] and allows protecting TT traffic from
other traffic such as AVB traffic or best-effort (BE) traffic. Additionally,
the transit of TT streams through a network can be scheduled. Every egress
queue has a so-called transmission gate or simply gate. Gates are either open
or closed. Frames can only be dispatched and sent from an egress queue if the
respective gate is open. The closing and opening of a gate is controlled by a
so-called Gate Control List (GCL). A GCL entry consists of a time interval
$[T_{i},T_{i+1}]$ and a bit-vector. The bit-vector indicates which gates are
opened or closed during the time interval $[T_{i},T_{i+1}]$. Therefore, a GCL
entries defines a time slice exclusively available to traffic with a priority
corresponding to an open queue. These GCLs are executed periodically for an
indefinite number of times. The computation of GCLs and appropriate cycle
times, i.e., periods of these GCLs, is denoted as scheduling or GCL synthesis.
The number of available GCL entries in an egress port is limited and depends
on the used bridge. Figure 1 depicts the architecture of a typical TSN bridge
port according to IEEE 802.1Q [802.1Q], including the components of the TAS.

Figure 1: Components of an egress port implementing the TAS. Every egress
ports has eight egress queues guarded by a transmission gate (G). The GCL
controls the timed opening and closing of these gates.

The TAS can be used to protect traffic by scheduling the GCLs accordingly.

If the transmission of a frame is not finished until the end of the time slice
the transmission started, a frame in the next time slice may be forced to wait
until transmission finishes. Thus, it would be possible that a frame of a TT
stream must wait because of a frame of BE traffic. This problem is avoided in
TSN. TSN bridges only start the transmission of a frame if the transmission
finishes before the next gate closing. A guard band is a time interval with
the length of the transmission of a maximum sized standard Ethernet frame. The
duration of a guard band at the end of a time slice may not be available for
transmissions to comply with closed gates.

Figure 2: Time slices, GCL entries, and guard bands. The duration of a guard
band may be not available for BE traffic as a frame can only be sent if
transmission finishes before the respective gate is closed.

Figure 2 depicts a guard band which restricts the transmission of BE traffic
before the respective gate is closed. If frame preemption is used, the maximum
size of a frame that cannot be preempted is 123 byte. This is due to the
minimum size of a frame fragment, i.e., 60 byte of the frame and an additional
4 byte check sequence. A frame with 123 byte cannot be preempted until the
first 60 byte are transmitted as the resulting first fragment would be too
small otherwise. However, the last 63 byte also cannot be preempted as the
resulting last fragment would be too small. Therefore, guard bands can be
reduced to the length of a transmission of 123 byte if frame preemption is
used. In TSN, it is not necessary to insert guard bands explicitly.

The challenge in planning a TSN network is to compute the schedules that
coordinate the transmission times for all streams at their respective talkers
and the GCLs of bridges such that the requested real-time requirements of all
TT streams are met. This problem is formally defined in the next section.

##  III The TSN Scheduling Problem

First, we introduce a common network model, relevant properties of TT streams,
and the definition of schedules. Second, we state constraints for valid
schedules. Then, we discuss scheduling and optimization in the context of TSN
and the computational complexity of these problems. Furthermore, we present
common problem extensions solved in the literature. Finally, we give an
introduction to common solution techniques that have been applied to the
scheduling problem.

###  III-A Nomenclature

A node of a TSN network is either an end station or a TSN-capable bridge. End
stations are sources and destinations of data streams. Bridges switch frames
based on their header. Links are full-duplex Ethernet connections between an
end station and a bridge or between two bridges. TSN bridges are inevitably
subject to multiple delays. These delays must be considered to ensure
deterministic transmissions according to a schedule. The processing delay of a
bridge is the time between a frame arrives at an ingress port, and it is put
in an egress queue. The transmission rate of an egress port is the rate at
which data can be transmitted over a link. The propagation delay of a link is
the time needed for electrical signals to traverse the link. The queuing delay
of a frame is the time the frame waits in an egress queue for transmission.
Ethernet uses a preamble before of a frame transmission to signal a new
transmission starts, and an inter-frame gap between two frame transmissions to
ensure that the receiver can process a new frame. The maximum size of a frame
in TSN is 1542$\,B$, including inter-frame gap and preamble. A TT stream is a
periodically repeated data stream with real-time requirements. Every stream
has a talker as source and possibly multiple Listeners as destinations. The
earliest and latest transmission offsets describe the time range during which
a talker can start transmission relative to the start of a period. The
deadline of a stream is the time at which all frames of the stream must have
arrived at all destinations, also relative to the start of a period. The
entire payload of a stream must be delivered before the deadline. The payload
of a stream may be sent with multiple frames.

The hyperperiod $H$ of a set of streams $\mathcal{S}$ is the least common
multiple of the periods of the streams. Let $s\in\mathcal{S}$ be a stream with
period $p_{s}$. A schedule for all streams in $\mathcal{S}$ contains
$\frac{p_{s}}{H}$ consecutive replications of $s$, each having the hyperperiod
as period. Scheduling algorithms typically consider transmission times,
earliest and latest transmission offsets, and deadlines relative to the
beginning of the hyperperiod. Figure 3 depicts an example with two streams A
and B. The period of stream A is three times the period of stream B. A
schedule for both streams thus contains only one period of stream A and three
periods of stream B. A schedule for a set of TT streams in a TSN network
consists of the transmission offsets of all streams at their respective
talkers, and GCL configurations for all bridges. Transmission offsets of
frames at bridges along their path follow implicitly. Schedules must be
periodic, i.e., repeatable an indefinite number of times. The hyperperiod of a
set of streams is the period of schedules for these streams.

Figure 3: The period of stream A is three times the period of stream B. For
modelling purposes, the hyperperiod is introduced, i.e., all streams are
assumed to have that larger period. To cover the full duration of the
hyperperiod, B is modelled by three consecutive copies B1, B2, and B3.

###  III-B Scheduling Constraints

Given a problem instance for the TSN scheduling problem, i.e., a set of TT
streams and a network topology. Every schedule which complies with the real-
time requirements of all TT streams is considered a valid solution of the TSN
scheduling problem. Such schedules are denoted as valid schedules in the TSN
scheduling literature. The following constraints restrict the set of all
possible schedules to the set of valid schedules.

####  III-B1 Bridge Design

TSN bridges are currently assumed to be store-and-forward bridges. Frames
cannot be forwarded by a bridge before they have arrived at the egress queue.
The duration of a transmission depends on the transmission rate of the sending
egress port, the size of the frame, and the propagation delay of the used
link. The processing delay of the bridge must also be considered.

####  III-B2 Exclusive Link Usage

No two frames can be in transmission over a link in the same direction at the
same time.

####  III-B3 Deadlines

A stream meets its deadline when all of its frames arrive at the stream’s
destination before its deadline. For multicast streams, this holds for all
destinations.

####  III-B4 Routing

The frames of a stream follow some routing. Every instance of the same stream
follows the same routing.

####  III-B5 Frame Order

There is no reordering of frames of the same stream. Frames that are sent
earlier arrive earlier than frames sent later. This holds hop-by-hop and end-
to-end. The source node of a stream sends frames of a stream in-order. There
are no duplicates, i.e., a frame cannot be replicated by a bridge.

####  III-B6 FIFO Queues

The order of frame arrivals at an egress queue must match the order at which
frames are sent.

####  III-B7 Queue Size

Frames of scheduled traffic must not be dropped for any reason.

####  III-B8 Gate Control

If a frame waits in an egress queue, it can only be sent when the respective
gate is open. The gate must stay open until transmission finishes.

####  III-B9 Transmission Selection

If multiple gates of an egress port are open and frames in the respective
queues are waiting for transmission, the queue with the highest priority is
the next queue to dispatch a frame.

####  III-B10 Additional Features

Various modifications of the problem are presented in the literature.
Additional constraints may be needed to model these problems. For example,
multiple queues can be reserved for TT traffic per egress port. Queue
assignment of streams must be modeled in this case. We discuss these problem
modifications in Section III-E.

###  III-C Finding a Schedule vs. Optimization

There may be multiple schedules for a given problem instance. In fact, most
problem instances have a large number of schedules as possible solutions. So
far, the definition of the scheduling problem does not differentiate between
these solutions. A common way to compare solutions is to introduce an
objective function. Such a function maps solutions to real numbers. The
solution to an optimization problem is the schedule which minimizes or
maximizes the objective function, i.e., has a smaller or larger objective
value than any other schedule. Examples for objectives are minimizing end-to-
end delays or jitter of TT streams. Another possible objective is minimizing
the flowspan, i.e., the duration such that all frames have arrived at their
respective destinations.

###  III-D Computational Complexity

The problem of deciding whether there is a valid schedule for a set of TT
streams in a TSN network is known to be NP-complete [St10] in general as Bin
Packing can be reduced to it. This even holds without queuing [DuNa16]. NP is
a class of decision problems, i.e., contains only problems which can be
answered by either yes or no. Finding a schedule or finding an optimal
schedule are not decision problems. Therefore, they are not contained in NP.
However, they are computationally at least as hard as the question whether
there is a schedule.

###  III-E Problem Extensions and Restrictions

The definition of the basic problem in Section III-B only describes the common
properties of the problems in the literature reviewed in this survey. Much
research work focuses on special cases or problem extensions with additional
constraints. This section introduces these problem variations in a general way
such that they are clear in the remainder of this survey.

####  III-E1 Joint Routing

The definition of Section III-B assumes that the routing of every stream is a
predefined part of the input and fixed. Much research work is dedicated to a
variation of the scheduling problem with joint routing, which relaxes this
assumption. In contrast to the basic problem, the routing of streams is
variable and computed simultaneously with the schedule. This gives the
scheduling algorithm more flexibility, as streams can be routed to omit
heavily loaded links and thus conflicting scheduling constraints. A common
approach is that the algorithm gets a set of possible paths as input for every
stream, and it selects one per stream as the stream’s routing. Other
algorithms select arbitrary paths. Both approaches are possible due to IEEE
802.1Qca [802.1Qca] as the standard allows arbitrary paths to be configured
for every stream.

####  III-E2 Reliability

Research work dedicated to joint routing and scheduling can take reliability
considerations into account. Such works define a model of possible faults and
their probabilities. Scheduling algorithms can compute schedules which meet
the real-time requirements of all streams with high probability for a given
fault model. These schedules are denoted as robust schedules relative to a
given fault model. For instance, scheduling approaches can compute schedules
which are robust against single link failures. This can be achieved by
introducing redundant streams with the same payload and routing them through
disjoint paths.

####  III-E3 GCL Synthesis

GCLs for all egress ports must be constructed. One possible approach is to
open the gates for scheduled traffic at the beginning of a hyperperiod and
never closing them. However, this approach comes with the drawback that no
other queue can send. This may be necessary to protect other TT streams with
tighter bounds by avoiding congestion in the queues for TT traffic.

Another common approach is to use a postprocessing scheme after scheduling
transmission offsets. GCLs are constructed such that the gate of a queue is
opened when a transmission from this queue should start according to the
schedule. The respective gate is closed when the transmission is finished
according to the schedule. This approach allows a scheduler to use gates to
delay frames. However, the number of available GCL entries is limited in real
hardware bridges. Therefore, scheduling transmission offsets and synthesizing
GCLs can also be considered in a joint scheduling algorithm instead of a
postprocessing.

####  III-E4 Queuing

Queuing can cause serious problems for schedules of streams with real-time
requirements. Frames can get lost in non-deterministic events, such as link or
end station failure. A frame missing in an egress queue may result in another
frame being dispatched earlier than expected and scheduled. As a result, this
frame may change the arrival order in some egress queue, ultimately resulting
in a stream missing its deadline. Such problems can be avoided in two ways.
First, by avoiding queuing at all. Second, by not allowing frames to wait in
the same egress queue at the same time. In this way, it is not possible that
some frame is dispatched earlier than scheduled due to a missing frame in an
egress queue. These restrictions are not imposed by bridges according to IEEE
802.1Q [802.1Q]. Instead, they are considered during scheduling such that a
scheduling algorithm only computes schedules robust against these non-
deterministic events. In the following, we discuss problem extensions and
restrictions from the literature.

##### Unrestricted Queuing

Allowing frames of different streams to be in the same queue at the same time
is denoted as unrestricted queuing. Figure 4(a) depicts a schedule by showing
frame arrivals and transmissions of a single bridge. The schedule shows two
streams, A and B, with two frames per period. The queuing state is shown
implicitly. A frame is queued at the same time with all other frames that
arrive before the frame is transmitted. Thus, the frames A1 and B1 are in the
egress queue at the same time. If A1 does not arrive according to the
schedule, e.g., due to a permanent link failure, B1 is transmitted earlier
than scheduled. This is the case in the second period depicted in Figure 4(a).
Consequently, B1 arrives earlier than scheduled in some other egress queue.
This may result in some other frame experiencing more queuing delay than
scheduled, ultimately leading to a missed deadline.

##### Isolation

The problems of queuing in case of non-deterministic events can be solved by
not allowing frames of different streams to be in the same queue at the same
time. If a frame is missing in a queue and no other frame is scheduled to be
queued at the same time, no other frame can be transmitted earlier than
scheduled. This approach is denoted as frame isolation in the literature. It
was introduced in [CrOl16]. Figure 4(c) shows a schedule valid with frame
isolation. If A1 does not arrive at the bridge, the schedule of B1 and B2 is
unaffected.

##### No-Wait Scheduling

In no-wait scheduling, frames are dispatched and sent immediately after
arriving at an egress queue. Queuing is not allowed. The rational of this
constraint is to avoid all consequences of non-deterministic events related to
queuing. Figure 4(d) depicts a no-wait schedule for two streams. All frames
are sent immediately after arrival. For example, B1 is received and
transmitted after A1 and before A2 in the same period.

##### Queue Assignment

Instead of restricting queue usage, the scheduling problem can also be
extended by allowing more than one queue per egress port for TT streams. A
scheduling algorithm for such a problem not only schedules transmission
offsets and GCL entries, but also assignments of TT streams to egress queues.
This is especially interesting with respect to frame isolation, as frames of
multiple streams can simultaneously wait for transmission by the same egress
port in different queues.

(a) Unrestricted queuing without fault. Frames A and B wait in the egress
queue at the same time.

(b) Unrestricted queuing with fault. Frame B is sent earlier than scheduled if
frame A was lost.

(c) Frame isolation. Frame A waits at a closed gate for some time before
transmission.

(d) No-wait scheduling. Frames are transmitted immediately after arrival.

Figure 4: Queuing restrictions from TSN scheduling literature. Frame arrivals
at an ingress port and transmissions at an egress port of the same bridge are
shown. Processing delays are omitted to increase comprehensibility.

####  III-E5 Integration of Audio Video Bridging

TT streams and AVB traffic can coexist in the same network at the same time.
TSN bridges may support to use the CBS and the TAS in parallel. TT streams and
AVB streams compete for the same links, but use different queues in the egress
ports. Therefore, the scheduling problem can be extended to also include a set
of AVB streams as input. They are scheduled at their respective talkers, and
considerations for the behavior of the CBS must be included during scheduling.

####  III-E6 Integration of BE Traffic

BE streams have no real-time requirements, they are generally aperiodic and
unknown a priori such that they cannot be scheduled. However, some schedules
may be beneficial for BE traffic. For instance, large bursts of TT traffic
within a long hyperperiod could be avoided to facilitate frequent transmission
opportunities for BE traffic, which may reduce the delay of BE traffic.
Another example is avoiding GCL entries unless they save substantial capacity
for other traffic. For each GCL entry, a guard band is needed within which
packet transmissions cannot start. Therefore, compact schedules maximize
capacity for BE traffic.

####  III-E7 Dynamic Reconfiguration

An entirely different problem related to the basic problem is dynamic
reconfiguration of existing schedules. Such reconfigurations are necessary
when streams are removed or new streams should be integrated into a schedule.
While removing streams is rather easy, adding new streams to an existing
schedule can be complicated for two reasons. First, the transmission offsets
of already scheduled streams may have to be changed. Second, links and egress
queues are occupied by earlier scheduled streams, which places constraints on
possible transmission offsets for new streams. The runtime of a scheduler
during reconfiguration must be very low in many scenarios, such as in
automotive use cases. This is due to fast changing real-time requirements and
traffic patterns of safety-critical applications. Recomputing the whole
schedule with offline algorithms is computationally infeasible in such cases.

####  III-E8 Multicast

Multicast streams have more than one Listener as destinations. Therefore, the
routing of a multicast stream is a tree. A multicast stream can be modelled by
a set of unicast streams. However, only a single copy of a frame is
transmitted per hop in TSN. Thus, this modelling is not appropriate.
Scheduling algorithms may contain considerations for multicast streams instead
of assuming all streams to be unicast. Joint routing approaches must compute
trees instead of paths for every stream.

####  III-E9 Task Scheduling

Tasks are applications running on end stations. They are executed
periodically. Their execution depends on data received via TT streams.
Additionally, they can send TT streams after they processed some received
data. Scheduling algorithms for TSN can schedule tasks and TT streams in a
joint approach.

###  III-F Optimization Methods

We classify the scheduling algorithms in the literature in exact and heuristic
approaches. Exact approaches compute a schedule, or an optimal schedule if an
objective is given, if one exists, or prove the problem instance infeasible.
Heuristic approaches do not guarantee to find an optimal schedule. Instead,
they try to find reasonably good solutions within short time. In the common
case, they cannot deduce whether a problem instance is infeasible, nor is
finding a solution guaranteed if one exists. In this section, we introduce
common solution techniques and explain their basics.

####  III-F1 Exact Approaches

As the Scheduling Problem for TSN is NP-complete, there is probably no
polynomial-time algorithm to compute TSN schedules. Therefore, it is
reasonable to rely on the advances of the past decades in mathematical and
combinatorial optimization. All exact solution approaches in the literature
are based on the following four techniques.

#####  Integer Linear Programming (ILP)

An ILP describes the space of possible solutions to a problem with linear
inequalities. Every assignment of variables which fulfills all inequalities
corresponds to a solution of the problem and vice versa. Some variables may be
restricted to take only integer values. A linear objective function may
describe the quality of solutions. Figure 5 depicts an ILP which minimizes an
objective function.

Figure 5: Example of an ILP model.

ILP solvers compute a feasible assignment which minimizes the objective
function. Every encountered solution in the solution process corresponds to an
upper bound on the objective value of the optimal solution. Additionally, the
solver can infer lower bounds for the objective value of the optimal solution
during the solution process. So even when finding the optimal solution is not
possible in reasonable time, ILP solvers yield estimations of the maximum gap
to the optimum. Widely used state-of-the-art ILP solvers are CPLEX [cplex] and
Gurobi [gurobi].

#####  SAT Modulo Theory (SMT)

SMT solvers find solutions to problems described by first-order formulas.
Formulas model a problem with variables and predicates which are connected by
logical operators. Besides Boolean variables, SMT solvers allow formulating
predicates in other logical theories and use them as atomic formulas. SMT
solvers have an interface for theory-specific solvers so that the problem can
be modelled with the best suitable theory. Examples of theories are the theory
of linear arithmetic with integers or the theory of bit vectors. Figure 6
depicts a formula with predicates from the theory of linear arithmetic with
integers. The basic structure of a model is a formula from propositional
logic, but predicates from integer arithmetic are used as atomic formulas.

Figure 6: Example of a formula used in SMT solving. The basic structure is a
formula from propositional logic, but predicates from other theories may be
used as atomic formulas instead of Boolean variables.

The solver searches for an assignment of the variables that evaluate the
formula to true. It uses techniques from SAT solving to reason about
satisfiability, combined with theory-specific solvers for conjunctions of
predicates. SMT solving is only about finding some satisfying solution. When
the best assignment regarding some objective function is computed, the term
Optimization Modulo Theory (OMT) is used. Z3 [z3] is a widely used SMT solver
which can also be used for optimization.

Figure 7: Classification of the surveyed research works in the scope of TSN
scheduling.

#####  Constraint Programming (CP)

Constraint Programming is a general solution approach to combinatorial
problems. The set of feasible solutions to a problem is described in a
declarative way. In this sense, ILP and SMT solving are special cases of CP
solving. However, CP solvers use backtracking, local search, and constraint
propagation techniques to solve CP models as opposed to ILP solvers. Another
relevant case of CP is the restriction of variable domains to a finite set.
CP-SAT is a widely used CP solver [ortools].

#####  Pseudo-Boolean Optimization (PBO)

Similar to ILPs the solution space of a problem in PBO is modelled with linear
inequalities, but all variables must be binary. However, instead of using
mathematical optimization as in ILP solving, techniques from SAT solving like
propagation and conflict refinement are employed. A linear objective function
can be minimized by adding it as a constraint to the model with some bound.
The solver is called multiple times with different bounded objective
constraints. Every infeasible solver run gives a lower bound on the optimal
objective values. Every solution yields an upper bound on the optimal
solution. The optimal solution is found, with respect to some minimal
precision, when the gap between lower and upper bound is smaller than the
minimal precision provided by the user.

####  III-F2 Heuristic Approaches

Because finding optimal solutions for realistic problem instances is
infeasible in many cases, heuristic algorithms are used. Such algorithms are
used to find suitable solutions in reasonable time, generally without knowing
whether there are better solutions. Metaheuristic approaches are common
algorithms that can be applied for a wide range of problems. Alternatively,
there are heuristics that use problem-specific knowledge for many problems,
and there may be combinations of both.

#####  Greedy Randomized Adaptive Search Procedure (GRASP)

GRASP is a metaheuristic which can be adapted to various problems. Its
building blocks are a greedy-randomized algorithm to construct initial
feasible solutions, and a local search algorithm. The greedy randomized
algorithm incrementally constructs a solution by making random decisions among
the set of decisions with the smallest increase in cost until a feasible
solution is found. The local search explores neighboring solutions, i.e.,
solutions with minimal changes, to the intermediate solution. It explores the
solution space until it finds a local optimum. Both steps are repeated a
predefined number of times and the best encountered solution is returned. To
adapt GRASP for a specific problem, a greedy randomized algorithm to generate
initial solutions and a local search algorithm must be constructed.

##### Tabu Search

Tabu Search is a metaheuristic to systematically explore the solution space.
It uses an initial solution as start and moves to the best neighboring
solution. The algorithm keeps a tabu list of previously visited solutions or
changes to solutions to avoid walking cycles in the solution space. Only
neighboring solutions or changes to solutions which are not contained in the
tabu list are considered for the move. The best encountered solution after a
specific number of moves is returned. To construct a problem-specific
heuristic, a heuristic to generate an initial solution and a function
returning the possible changes to some given solution must be built.

##### Simulated Annealing (SA)

is a metaheuristic used to find good approximations of the global optimum of
an optimization problem. It is inspired by cooling processes in physics. A
global variable for temperature is used. Temperature decreases slowly to 0 in
discrete steps. In each step, a neighboring solution is randomly selected, and
the objective function is evaluated. The probability of moving to a
neighboring solution depends on the current temperature and the objective
value of the considered solution. A move to a neighboring solution which is
worse than the current solution is possible with small probability to escape
from local optima. As temperature decreases, the probability of moving to
solutions with worse objective value vanishes. The best solution encountered
after some acceptance criterion holds is returned. To adapt SA to a specific
problem, a heuristic to generate an initial solution and a function returning
the possible changes to some given solution must be built. Additionally, the
way the temperature is decreased and the acceptance criterion must be
selected.

##### Genetic Algorithms (GA)

Genetic algorithms are a metaheuristic approach inspired by evolution
processes and natural selection in biology. Candidate solutions are considered
as individuals. Chromosomes represent properties of these individuals and are
coded into bitstrings. At every point in time, there is a pool of individuals,
i.e., the population. New individuals are constructed from two or more
existing solutions, i.e., genetic crossover is performed. Individuals may be
altered randomly, i.e., their chromosomes are mutated. When transiting to the
next generation, some individuals die and are removed from the population. The
probability of dying for an individual depends on its fitness. The fitness
function is the optimization objective of the modeled problem. The best
individual encountered after some number of generations is returned. As in
biology, high-quality solutions have a higher probability to survive and
reproduce, which in terms yields new high-quality solutions. To construct a
problem-specific heuristic, a heuristic to generate initial solutions must be
constructed. Suitable crossover as well as mutation and selection mechanisms
have to be used. Parameters like population size, stopping criterion, and
probabilities for selection and mutation must be designed.

##### List Schedulers (LS)

are a metaheuristic to schedule tasks on identical machines. The tasks are
sorted in a list according to some measure of priority. In every step, the
first task in the list is selected. If a suitable machine is available, the
task is executed on this machine, otherwise the next task in the list is
selected. These steps are repeated until all tasks are executed. Streams as
tasks and end stations as machines yields a heuristic for TSN scheduling. A
well-known heuristic from general scheduling literature can be considered to
be special cases of list schedulers. As-soon-as-possible (ASAP) scheduling
orders streams by priority and schedules them one by one at the earliest
possible time along their paths.

##  IV Literature Overview

In the following section, we give an overview of the literature about TSN
scheduling. We categorize research work based on whether scheduling with fixed
routing or joint routing is considered. Both sections are further grouped by
the main topics of the respective papers. Comparability of techniques and
results of research works in the same group is ensured by this classification.
Figure 7 depicts this classification.

###  IV-A Scheduling w/ Fixed Routing

We give an overview of research works which only deal with the scheduling of
TT streams. In all papers presented in this section, the routing of TT streams
is fixed and given as input to the scheduling algorithm. Such scheduling
algorithms cannot change the routing during scheduling in case of conflicting
streams. We group publications in categories based on similar topics, like
model assumptions or problem extensions.

####  IV-A1 Scheduling w/o Problem Extensions

We discuss publications solving the unmodified scheduling problem.

Figure 8: Incremental approach of Steiner [St10]. Similar ideas were used by
other approaches, e.g., in [CrOl16].

Early work about scheduling of TT traffic in Ethernet networks was conducted
by Steiner [St10]. Even though this work is not specific to TSN, it influenced
many research works covered by this survey. The author proposes the use of SMT
solving for the scheduling of TT streams. An incremental approach is
presented. Figure 8 depicts this approach. Streams are scheduled one after
another. Schedules of already scheduled streams are fixed in later iterations.
Backtracking is used in case of infeasibility, i.e., the schedule of some
stream is unfixed and the stream is scheduled again simultaneously with the
new stream. Backtracking is repeated until a schedule is found, or no stream
schedules are left to unfix. This idea was adopted by many later works for TSN
scheduling.

Oliver et al. [OlCr18] give an SMT model based on mapping streams to
transmission time windows of egress queues. The number of these transmission
windows is fixed per egress port, and their placement and size is computed by
the scheduling algorithm. As a side effect of using a fixed number of
transmission windows, the number of gate events and thus guard bands is
limited, even though the authors do not explore this matter. The authors use
isolation to restrict the problems imposed non-deterministic behavior, e.g.,
frame loss. Two queues per egress port are dedicated for TT traffic. They
evaluate the solving time of their approach with respect to the number of
streams and the number of transmission windows per egress port. Their results
indicate that the solving time increases exponentially with the number of
streams. However, for reasonable numbers of streams and transmission windows,
solving time is more sensible to the number of transmission windows. A
comparison to the SMT from [CrOl16] shows that the window-based approach with
one window per egress port is faster in finding a schedule. The average jitter
is significantly reduced when the number of transmission windows per egress
port is increased.

Figure 9: Multi-layered ring topology used in [HeGl20].

Steiner et al. [StCr18] use the SMT model from [OlCr18] as a starting point
for the standardization of TSN scheduling mechanisms. They demonstrate their
model by reporting the same evaluation results as in [OlCr18] with a reduced
number of transmission windows.

Hellmanns et al. [HeGl20] extend the Tabu Search algorithm of [DuNa16] for no-
wait scheduling. They construct a 2-stage approach for hierarchical networks
which consist of multiple rings on different layers. They argue that such
topologies are common in factory automation. Figure 9 depicts a model of such
a topology. First, they schedule streams with talker and listener in the same
ring. This step is done individually for every ring. No queuing is allowed in
these schedules. Then, they simulate the transmission of all other streams as
if they were sent at the same time from their respective talkers. If all
streams meet their deadlines in this simulation, the simulated behavior is
used as schedule. They compare this approach with scheduling all streams at
once with the Tabu Seach algorithm. Their evaluations demonstrate that the
proposed 2-stage scheduling scales better for problem instances with many
streams compared to the original Tabu Search approach. The latter does not
produce results for more than 1000 streams due to memory limitations. The
2-stage scheduling is two orders of magnitude faster in the special case of
multi-layered ring topologies. The authors report that the number of needed
GCL entries is significantly reduced by the 2-stage approach.

Kim et al. [KiCh21] give a heuristic algorithm to compute valid schedules, and
a post-processing to reduce end-to-end delays. Streams are ordered by priority
and are scheduled one after another. The individual frames of a stream are
scheduled along the stream’s path. The hyperperiod is divided into intervals
and every frame is assigned to the earliest unoccupied interval. The presented
evaluations indicate that end-to-end delays are reduced by up to one third per
stream in the evaluation scenarios.

Kim et al. [KiLe21][KiLe22] propose a genetic algorithm to schedule TT traffic
in automotive scenarios. Genes encode the scheduling order of frames. Frames
are scheduled as soon as possible according to this order and along the
respective stream’s path. The objective function used to compare scheduling
orders is the weighted sum of end-to-end delays, jitter, and bandwidth
utilization of the corresponding schedule. As in [DuNa16], a schedule
compression algorithm is employed to reduce the bandwidth occupation of guard
bands. The proposed approach outperformed random schedules regarding all three
metrics in almost all evaluation scenarios. The approach from [KiCh21] is also
outperformed with regard to the used objective.

Ansah et al. [AnAb19] present a scheduling algorithm in the special case of a
line topology where all talkers converge in a single bridge. Based on this
method, they also give an algorithm to compute GCLs in such a topology if the
streams are schedulable.

Vlk et al. [VlBr22] propose a heuristic algorithm to schedule very large-scale
problem instances. The algorithm shares many similarities with the well known
DPLL algorithm from SAT solving [DaLo62], e.g., probing, backtracking in the
case of conflicts, and restarts. Frames are scheduled one by one. If a
conflict arises, all decisions are reverted up to the conflicting frame. The
authors compare the heuristic with SMT-, ILP-, and GRASP-based algorithms. The
schedulability of an approach with respect to some set of problem instances is
the fraction of solvable problem instances within some time limit. The
proposed heuristic outperforms all other approaches regarding schedulability
and solving time. In fact, they were able to schedule instances with up to
10812 streams in a tree-like topology with 2000 nodes. This result outperforms
all other approaches in the literature. Evaluations with a real-world instance
from avionics are also presented.

Wang et al. present a deep reinforcement learning approach for no-wait
scheduling in [WaYa22]. They train machine learning models for various network
topologies. The model aims to reduce the maximum arrival time among all frames
to reduce the number of guard bands. For networks with up to 9 bridges and 10
end stations, the authors report solving times of at most 400 s.

####  IV-A2 Research Work about Queuing

We highlight works which allow or deal with the implications of queuing.

Craciunas et al. [CrOl16] construct an incremental SMT model to schedule TT
streams based on [St10]. They define flow isolation and frame isolation as
properties of a schedule to prevent some sources of non-determinism, e.g.,
single link failures. They present models to compute schedules with either
flow or frame isolation. Besides isolation in the time domain, they also
employ isolation in the spatial domain by the possibility of assigning
different streams to different queues. The authors identified the problem of
clock synchronization errors and introduce gaps between frame transmission to
cope with this problem. They compare the impact of frame and flow isolation to
the solving time of their SMT model. Their evaluations indicate that flow
isolation reduces solving times compared to frame isolation. However, more
problem instances can be scheduled with frame isolation.

Vlk et al. [VlHa20] investigate the effect of the isolation constraints from
[CrOl16] on schedulability. When a frame is lost during transmission and does
not reach the next egress queue as scheduled, another frame may be dispatched
earlier than scheduled from this queue. This frame in term can cause more non-
determinism on its path. Not allowing frames of different streams to be in the
same queue at the same time solves this problem, but reduces the solution
space considerably. A modification for bridges implementing the TAS is
proposed to cope with this conflict. Queues with this modification check
whether the next frame is the correct one with respect to the schedule. If
this is not the case, the queue idles until the next frame transmission is
scheduled. A comparison shows clear benefits regarding schedulability. The
number of streams which are scheduled to arrive before their deadline is also
significantly increased compared to isolation models.

The authors of [ReZh20] present a heuristic to schedule streams with queuing.
The heuristic is based on transmission windows similar to [OlCr18]. In
contrast to earlier works which include queuing in their model
[CrOl16][OlCr18], they drop isolation constraints. Network calculus is
employed for a worst-case end-to-end latency analysis. They minimize the
occupation percentage of egress ports, i.e., the percentage of the hyperperiod
which is reserved for TT traffic. In this way, long and frequent time
intervals for lower-priority traffic are scheduled. Their evaluations indicate
that their approach is superior regarding end-to-end delay and schedulability
of streams compared to earlier works from the same authors.

Chaine et al. [CaBo22] use queuing for jitter control. They propose to
schedule streams without queuing at all egress ports except for egress ports
connected to end stations. Frames are buffered in these egress ports and are
released such that jitter constraints are satisfied. The authors present a
novel isolation approach, denoted as size based isolation. Frames must be
buffered in increasing frame size order if they are stored in the same queue.
Two GCL entries are used to close and open the corresponding gate between two
frame transmissions. In this way, frames cannot be transmitted during an
earlier time slice than scheduled if another frame is missing in the queue, as
earlier time slices are too short. Figure 10 depicts such a scenario.

Figure 10: Size based isolation proposed in [CaBo22]. Frame transmissions from
an egress port connected to an end station are shown. Assume F1 and F2 are
scheduled to wait some time in the same egress queue. If the first frame F1
has not arrived at the egress queue, F2 cannot be transmitted in the time
slice dedicated for F1 as it is too short.

The authors give an ILP model to compute schedules with their approach. A
comparison of their approach to an unspecified approach for latency
minimization demonstrates that their approach reduces scheduling time
significantly. However, this comes with the cost of higher latencies.

Bujosa et al. [BuAs22] propose a heuristic scheduling algorithm which handles
queue assignment of streams. Instead of scheduling frames or streams one after
another on their entire path, they schedule all transmissions over a single
link before scheduling the transmissions over another link. They present
results about the scalability and schedulability of their approach compared to
a CP approach from the literature [ReCr22]. Not surprisingly, scheduling is
significantly slower with a CP approach compared to a heuristic.

####  IV-A3 Scheduling w/ Other Traffic

The schedule of TT streams may affect other traffic classes. AVB and BE
traffic cannot be scheduled, but QoS metrics of these classes can be
influenced when they are taken into account during the scheduling of TT
streams. We summarize works with such considerations.

Dürr et al. [DuNa16] present an ILP and a Tabu Search algorithm to compute no-
wait schedules for TT streams. They model the problem with job-shop
scheduling, a widely used modelling framework in the scheduling literature.
The authors measure the solving times of their Tabu Search and conclude that
the network topology and size have no impact on solving times. They minimize
the flowspan to construct a large time slice for BE traffic at the end of the
computed schedules. They propose a compression algorithm as post-processing
for schedules which aims to reduce the number of GCL entries needed to deploy
a schedule. The authors note that this increases the available bandwidth for
Best Effort (BE) traffic as the number of guard bands is reduced. Figure 11
depicts the effect of the schedule compression algorithm.

Figure 11: Effect of the schedule compression algorithm from [DuNa16].
Scheduled frame transmissions (F) and guard bands (GB) over a single link are
shown.

They report that the number of GCL entries can be reduced by 24% on average.
Parts of the content of this work are also featured in the PhD thesis of Nayak
[Na18].

The authors of [PoRa16] give an ILP to compute schedules for TT streams and
additionally present a GRASP heuristic to schedule Audio Video Bridging (AVB)
streams. They restrict queuing by enforcing frame isolation. Their heuristic
computes a routing for AVB streams such that they meet their deadlines. It
reduces the search space by only considering a fixed number of shortest paths
for every pair of nodes as possible routings. The schedule of TT streams,
computed by their ILP model, serves as input for the heuristic and cannot be
changed. They compare their AVB routing with the naïve approach of always
selecting the shortest path. The comparison demonstrates that more AVB streams
can be scheduled with their approach. A comparison of solving times of their
ILP to the SMT from [CrOl16] is conducted. They state that their proposed ILP
does not scale well for industrial-size instances and further efforts to
create a suitable heuristic are needed.

Santos et al. [SaCa19] present an extensive SMT-based modelling of the
scheduling problem with openly accessible implementation. Their model contains
a range of features known from previous works, e.g., transmission windows,
multicast, guard bands, and bandwidth considerations for BE traffic which were
not covered by a single approach in the past. The starvation of BE traffic is
prevented by restricting a user-defined fraction of a hyperperiod exclusively
to be used by other traffic which is related to the approach of minimizing the
flowspan [DuNa16]. Additionally, unrestricted queuing is integrated which is
uncommon in exact approaches so far. The authors mention the limitation of
only one gate opening per queue per hyperperiod in the presented model which
reduces the available bandwidth for other traffic classes. They evaluate their
approach on a realistic sized network and report successful scheduling for up
to 10 multicast streams. The model is also used in the well known simulation
framework OMNeT++ [OMNeT]. The thesis of Santos [Sa20] explains the model in
detail.

Houtan et al. [HoAs21] compare schedules computed with various objectives for
the same SMT model with respect to the Quality of Service (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
over a link. They integrate frame and flow isolation in their SMT model.
Unfortunately, their work lacks a description which one was used in the
evaluations. A comparison of the different objective functions indicates that
larger gaps between frame transmissions of TT streams increase the QoS of BE
streams. For instance, BE traffic may experience less starvation and average
latencies are reduced. Figure 12 depicts how BE traffic may benefit from
maximizing the gaps between TT frame transmissions.

Figure 12: Effects of different objective functions to BE traffic in [HoAs21].
Frame transmissions of TT and BE traffic over a single link are shown.

However, we note that the used system model features deadlines for BE traffic,
and they measure the number of deadline misses, so a comparison with the other
mentioned research works is not possible. The solving time for their SMT
depends heavily on the objective function used.

Zhou et al. [ZhLi20] use the model of [CrOl16] in an in-vehicle setting and
present simulation results with typical traffic patterns in such a scenario.
They compare end-to-end delays for schedules using the TAS to schedules using
the strict priority mechanism. Their results indicate that scheduling with the
TAS can ensure real-time requirements of TT streams while the performance of
lower-priority traffic is less affected compared to the strict priority
mechanism.

Barzegaran et al. [BaRe22] give a CP approach to compute transmission windows
for TT streams. In contrast to other window-based approaches [OlCr18][StCr18],
they assume that not all end stations support TSN. They use a worst-case delay
analysis to eliminate solutions that may violate the real-time requirements of
the given problem instance. They compare their approach to the algorithms
presented in [CrOl16], [OlCr18], [ReZh20], and [PoRa16]. They outperform these
approaches in terms of solving time, but end-to-end delays and bandwidth
utilization are significantly worse compared to [CrOl16] and [OlCr18]. They
also perform simulation runs of their schedules with OMNeT++. The results
indicate that their worst-case analysis for end-to-end delays holds but
overestimates the simulated delays considerably.

####  IV-A4 Scheduling w/ Reliability

Reliable transmission of data streams is one of the design goals of TSN.
Additionally, to hardware features ensuring reliability, schedules can be
assembled to mitigate the effects of various faults. We discuss publications
which take such considerations into account.

The clock frequencies of two clocks are not exactly equal for technical
reasons. This results in so-called clock drift, i.e., clocks running with
different speeds. Figure 13 depicts this problem.

Figure 13: Timing signals of two clock oscillators. Clock 1 runs slower than
clock 2. Therefore, the difference between both clocks increases over time.

Craciunas et al. [CrOl21] extend their model from [CrOl16] to cope with clock
drift during scheduling. They introduce a parameter for the maximum allowed
clock drift into all equations which contain transmission offsets or reception
times of frames. Effectively, they merely increase the gap between frame
transmissions which is already contained in the model of [CrOl16]. Clocks are
resynchronized after some predefined out-of-sync detection timeout. The
authors present a design space study which investigates the relationship
between the maximum allowed clock drift, the worst-case clock drift rate, the
maximum possible diameter of the synchronization spanning tree, and the out-
of-sync detection timeout. Their findings on a number of test networks
indicate that shorter out-of-sync detection timeouts are needed for higher
clock drift rates. The maximum possible diameter of the synchronization
spanning tree is negatively affected by higher clock drift rates. Evaluations
for a test case regarding schedulability, end-to-end latency, and solving time
are conducted. The results show that end-to-end latency increases for higher
allowed clock drifts. Maximizing the allowed clock drift yields a maximal
robust schedule for a given problem instance, but solving time increases by an
order of magnitude compared to setting a fixed maximum clock drift in advance.

Feng et al. [FeCa21] consider the scheduling problem in the presence of frame
loss. Instead of scheduling redundant streams over disjoint paths, like in
[AtBa20], [RePo20], and [GaZa17], reliability is achieved by multiple
transmissions of a stream over the same path. The research work focuses on
choosing an appropriate number of repetitions per stream for a trade-off of
reliability and network utilization. In contrast to similar works,
considerations for AVB and BE streams are also included in the algorithm, as
repeated transmissions of TT streams deplete the available bandwidth and may
lead to starvation of other traffic otherwise. The presented algorithm uses
the SMT model from [CrOl16] as a sub-routine. Their results show that
increasing the fault probability leads to a higher number of retransmissions
which in turn results in less available bandwidth for BE traffic.

In later works, Feng et al. [FeDe22] studied a similar problem, but also
considered ACK and NACK messages and queue assignment of streams. In contrast
to [FeCa21], every TT stream is sent exactly twice. Transmission windows for
BE streams are computed after the scheduling of TT streams. The scheduled
transmission intervals for the retransmissions can be used to transmit BE
traffic when no retransmissions are needed.

Dobrin et al. [DoDe19] present a heuristic scheme to schedule streams with
reliability considerations. They consider transmission losses for frames such
that only one frame is affected by a fault at a time and the fault is fixed by
some predefined number of retransmissions. Their approach first tightens the
deadlines to take some number of retransmissions into account. Then, they
schedule streams in earliest deadline first order. Additional considerations
for rate constrained traffic are also included in their scheme, following the
scheduling of the TT streams. Unfortunately, no evaluations are presented. The
authors note that future works will address more realistic fault models.

####  IV-A5 Reconfiguration of Schedules

Adding and removing streams from an existing schedule is necessary in
dynamically changing environments, e.g., automotive use cases. While removing
a stream is straightforward, adding new streams may require more effort. We
summarize research works concerned with this problem extension.

Raagaard et al. [RaPo17] propose an algorithm for online scheduling of new TT
streams in an existing schedule. They use a heuristic which schedules streams
as early as possible such that schedules comply with isolation. When a new
stream should be added to an existing schedule, they calculate whether there
is a starting offset such that the stream can be scheduled without changing
the existing schedule. If this is not possible, the stream is assigned to
unused queues of the egress ports along the stream’s path. They evaluate how
many streams can be added to an existing schedule in a specific time. The
authors report that their heuristic is able to schedule about 1300 frames per
second in medium-sized test cases.

Pang et al. [PaHu21] compute schedules with an ILP such that updating a
schedule does not lead to frame loss or additional update overhead. In
contrast to [DuNa16] and [PoRa16], their approach is not limited to TSN and
streams are scheduled one by one. Schedules of streams from previous
iterations are fixed in later iterations. When some stream cannot be
scheduled, backtracking is used by removing some stream of an earlier
iteration from the schedule. The authors prove that a set of additional
constraints of the ILP imply no conflicts during schedule updates. They
evaluate their algorithm with respect to frame loss during updates and update
duration on real-world train and automotive networks. The results confirm that
no frames are lost and no time overhead is needed for schedule updates.

####  IV-A6 GCL Synthesis

Most research works use a post-processing to compute GCLs from transmission
offsets. However, this comes with the drawback that GCLs have limited size in
bridges and a schedule may not be deployable. We present literature which
discusses explicit GCL generation.

Jin et al. [JiXi20] present an SMT approach to schedule TSN streams with a
fixed number of gate openings. Reducing the number of gate events also reduces
the number of guard bands, such that more bandwidth is available for lower-
priority traffic. Their modelling assumptions regarding queuing are even more
restrictive than frame isolation as only exactly one frame is allowed to be in
a queue at any given time. Their approach allows multiple queues for TT
traffic per egress port, but assigning streams to queues is not part of the
SMT model. This is done before solving the SMT model by a greedy heuristic
which aims to balance the workload of all queues of an egress port. As their
SMT model cannot be solved in reasonable time, they use an iterative scheme to
schedule small groups of streams separately. Subsets of streams are scheduled
one after another such that the schedules of previously scheduled subsets are
fixed in later iterations. The objective when optimizing a subset is to
minimize the maximal number of Gate Control List (GCL) entries for all egress
ports. They also propose a heuristic algorithm which complies with a limited
number of GCL entries. Their evaluations show that the heuristic algorithm is
an order of magnitude faster than naïve heuristics while reducing the number
of GCL entries considerably. Instances with up to 10000 streams were scheduled
in reasonable time while the SMT approach has not produced a feasible schedule
for an instance with 100 streams within 2 days.

Another iterative SMT scheme which aims to reduce the number of GCL entries is
given in [LiLi20]. Their approach divides the hyperperiod into slices, which
are scheduled individually. GCLs are updated for at the beginning of every
slice. The authors compare the number of GCL entries needed with schedules
computed for an entire hyperperiod. Their results demonstrate that the number
of GCL entries can be reduced while keeping end-to-end delays in reasonable
bounds. However, it is not a surprise that fewer GCL entries are required when
updating the GCLs regularly is allowed, as even a single entry per GCL is
sufficient with frequent updates.

A rather simple CP model for scheduling on a single link with only four types
of constraints is presented in [DaWa21]. However, they propose a post-
processing to reduce the number of GCL entries needed in a schedule. For a
small test case of only three streams, the authors report a reduction of
bandwidth loss due to guard bands by 42.8%.

####  IV-A7 Task Scheduling

Tasks are applications running on end stations. We highlight publications
which consider the scheduling of tasks on end stations, additionally to
scheduling data streams between these tasks.

In [FeYa21], Feng et al. compute schedules for streams and tasks sending or
receiving streams simultaneously. The model includes dependencies between
streams and tasks, e.g., an application can only be executed when all frames
of some stream were received. The authors scheduled instances with 11 streams
and more than 100 tasks. As many other works, the authors note the exponential
increase of solving times for larger instances.

The authors of [BaZa20] present a CP model for scheduling of TT traffic which
takes characteristics of control applications into account. Control
applications have an execution interval and can only produce output streams
for actuators when certain input streams of sensors have arrived. Although the
quality of control application execution covers multiple aspects, the only one
taken into account is jitter. Queuing is allowed in their model, but is
restricted to frame isolation. They compare exact and heuristic search
strategies to find solutions to the proposed CP model. For all presented test
cases, both search strategies find the optimal solution with zero jitter, but
the heuristic approach is orders of magnitude faster.

These preliminary works were extended in [BaPo21]. In contrast to [BaZa20], a
more realistic quality measure for streams of control applications is
integrated into the CP model. It constitutes of jitter and end-to-end delays
of input and output streams of control applications, and jitter for control
application execution. They compare their model with the model from [CrOl16]
which is extended to include stream precedence for input and output streams of
control applications. The authors report that the presented model outperforms
the model from [CrOl16] with respect to the proposed quality measure by up to
a factor of two on the test cases under consideration. Additionally, they
compute a schedule for a realistic test case of an automotive mobile robot and
validate their algorithm on a simulation platform and on real hardware. The
PhD thesis of Barzegaran [Ba21] features this work.

####  IV-A8 Other Topics

This section summarizes research works with unique topics that fit not well
into the previous groups.

Jin et al. propose an SMT model which also handles an optimized fragmentation
of messages in [JiXi19]. Messages can be transmitted with multiple frames. How
messages are split into frames is an additional degree of freedom in the
presented optimization. Due to performance reasons when solving the model,
they also give heuristics for message fragmentation and scheduling. The
presented evaluations demonstrate that schedulability increases considerably
by up to 50% when message fragmentation is also taken into account.

Figure 14: Transmissions of two frames A and B over a link to a listener. B
cannot be scheduled to be transmitted at another time. In this case,
scheduling is only possible when the scheduler splits A into two frames.

Figure 14 depicts an example of how schedulability can benefit from message
fragmentation. Additionally, the presented heuristic algorithms can schedule
instances an order of magnitude larger than the SMT approach.

A genetic algorithm approach which takes frame preemption into account is
presented in [PaSa19]. Their model contains different kinds of MAC interfaces
for preemptable and non-preemptable frames. Consequently, the presented
synthesis problem not only covers the assignment of streams to queues, but
also the assignment of queues to interfaces. Queues are strictly prioritized,
i.e., frames contained in a higher-priority queue always preempt frames of a
lower-priority queue. The proposed GA aims to maximize the reliability of a
schedule. Reliability of a stream is defined as the maximum number of allowed
retransmissions without missing the deadline, and the reliability of a
schedule is the minimum reliability of all streams. The authors present a
comparison of the proposed GA with well-known approaches from automotive
traffic scheduling. The baseline approaches are outperformed with respect to
schedulability and reliability. The authors explain this result with the fact
that their algorithm is specifically constructed to use all the available TSN
queues and to utilize them in a way suitable for preemption.

Figure 15: Example of a converged network with 5G and Ethernet links as
considered in [GiGi20].

The authors of [GiGi20] give a CP model for TSN in joint converged wired and
wireless networks. Their model integrates Ethernet and 5G links
simultaneously. Figure 15 depicts an example for such a converged network.
Frames transmitted over a 5G link must be scheduled to fit into predefined
transmission slots. They aim to minimize unusable resources in both types of
links, i.e., time occupied by guard bands for Ethernet links and unused
bandwidth resources for 5G links. The presented evaluations indicate that
minimizing only one kind of unusable resources leads to unsatisfying results
for the respective other kind.

The authors of [FaKu17] propose a graphical modelling tool for TSN scheduling.
They use logic programming to deduce facts about the given problem instance.
These facts are in term used for constraint generation of an SMT model. If an
instance is infeasible, the conflict refinement capabilities of the SMT solver
is leveraged to guide the user in changing the network configuration
appropriately. Three test scenarios are presented where the streams causing
infeasibility are identified.

Machine learning techniques were introduced to the domain of TSN scheduling in
[TuXu21]. Tu et al. present a semi-supervised machine learning model to
partition streams in groups before scheduling. They compare their approach
with the partitionings in [AtBa20] and [MaAm18], and state that they are
outperformed regarding schedulability. However, it is not clear how this
statement is backed by the actual computation of schedules with the resulting
stream groups.

###  IV-B Scheduling w/ Joint Routing

In this section, we give an overview of research work which inspects the joint
routing and scheduling problem. In contrast to works in IV-A, algorithms
proposed by publications in this section compute a routing and a schedule for
a given set of streams simultaneously. Again, we group the literature based on
the main topic of the respective papers.

####  IV-B1 Joint Scheduling and Routing w/o Problem Extensions

This section compiles publications which handle the joint routing and
scheduling problem. Research works are only included when they do not focus on
an additional topic highlighted in this survey.

An early ILP model which addresses the problem of joint routing and scheduling
is presented in [ScDa17]. Although it is not exclusively for TSN, the authors
state it is applicable for such networks. Their evaluations show that
schedulability increases considerably compared to the same test cases with a
fixed routing. They compare the solving time of their ILP for joint routing
and scheduling with ILPs solely for scheduling. As expected, the solving time
is larger for joint routing and scheduling compared to scheduling with a fixed
routing. Nevertheless, they still recommend joint routing as solution quality
increases considerably.

Falk et al. [FaDu18] extend the ILP from [DuNa16] to simultaneously compute
routing and schedule of TT streams. They analyze the scalability of the joint
routing and scheduling problem using ILPs. The authors report that solving
time is more influenced by the number of streams than the size of the network
topology for their ILP. The evaluations show that the network topology has an
impact on scalability. Network topologies with more paths between any pair of
nodes tend to yield harder problem instances, as more routings are possible
for any stream.

Nie et al. [NiLi22] schedule and route streams iteratively. Streams are
grouped by divisibility of their periods, such that streams in the same group
can share the same links. In contrast to similar works, e.g., [AtBa20] and
[HuWa21], they consider only no-wait scheduling. Time is divided into time
slots whose lengths equal the greatest common divisor of the periods of all
streams. Although many evaluations are performed for different network
topologies, network sizes, and traffic types, no results not seen in other
works were presented.

Xu et al. [XuXu22] propose an iterative SMT scheme similar to
[AtBa20][HuWa21]. However, they partition streams with machine learning using
some of the ideas from [TuXu21]. The authors compare this partitioning
approach with the partitioning algorithms from [AtBa20], [TuXu21], [MaAm18],
and [PaTa19]. The best schedulability was obtained for the proposed
partitioning method, second to the methods from [AtBa20] and [TuXu21].
Schedulability is slightly increased when more streams are scheduled
simultaneously, as more conflicting streams are handled in the same iteration.
Additionally, the authors compare the iterative scheme with their global
scheduling approach from [XuXu20]. The iterative scheme outperforms the global
approach with respect to schedulability and scalability. The difference in
schedulability between both methods increases for higher link utilization.

The authors of [SmGl17] present a PBO model for joint routing and scheduling.
They compare the solving time of their PB approach with the solving time when
routing and scheduling are computed in separate steps by the same model. Their
initial evaluations indicate that solving routing and scheduling in separate
steps reduces the overall solving time. Surprisingly, their evaluations also
show that the 2-step approach performs significantly worse for larger
instances compared to the joint approach. They explain this behavior by the
capability of SAT solvers to learn from conflicts. Whenever the solver runs
into a conflicting variable assignment, it interferes the cause of the
conflict and adds a clause to the model which prevents the conflict
explicitly. The learned clauses are dropped after the routing step in the
2-step approach. Schedulability increases when routing and scheduling are
performed in a single step. They state that instances with more routing
options lead to easier solvable scheduling problems as streams can be
distributed over the network.

Arestova et al. [ArHi20] construct a genetic algorithm for joint routing and
scheduling. In contrast to other works with genetic algorithms
[PaOb18][PaTa19], the authors focus on elaborating on the construction for
such an approach in detail. They combine the genetic algorithm with a
neighborhood search heuristic to find better solutions efficiently. They allow
queuing with flow isolation constraints from [CrOl16]. Additionally, a
schedule compression algorithm similar to the one in [DuNa16] is presented,
which is used to reduce the number of guard bands. In a brief evaluation
section, they compare their approach with the well-known NEH algorithm [NEH]
from job-shop scheduling. The proposed approach finds feasible schedules
faster, while the resulting schedules have comparable flowspans. The authors
report that scheduling with joint routing takes only slightly more time than
scheduling with fixed routing with the genetic algorithm.

Kentis et al. [KeBe17] investigate the relation of port utilization and GCL
schedule duration. They employ a simple heuristic for scheduling which is not
further explained, and compare the resulting schedule duration with shortest-
path routing and the proposed congestion-aware routing. For most test cases,
the duration of the schedule is reduced. However, they do not motivate why
shorter schedule durations are beneficial.

The authors of [WaCh20] present an algorithm based on ant colony optimization.
They give the fundamental building blocks of such an algorithm and demonstrate
that it can be suitable for TSN scheduling, but also note that further
investigation is needed. Unfortunately, they do not elaborate on the routing,
and the only related evaluation indicates that increasing the number of edges
increases the solving time.

Falk et al. propose a joint routing and scheduling algorithm in [FaDu20] which
is not based on constraints for frame transmissions. Their approach constructs
a conflict graph where each vertex represents a schedule for a single stream.
Vertices are connected by an edge if and only if the corresponding stream
schedules are conflicting. This reduces the scheduling problem to finding an
independent set in a conflict graph, i.e., a set of vertices which are
pairwise not connected by an edge.

Figure 16: Example of a conflict graph used in [FaDu20] for a single link
topology. Assume the transmission of each frame takes 5 time units. Edges
indicate stream schedules which are not compatible. The black circled vertices
are an independent set and induce a schedule.

Figure 16 depicts an example for a conflict graph and an independent set. The
authors use incremental heuristics to construct independent sets in such
graphs. Their evaluations demonstrate that the conflict graph approach has
advantages regarding runtime and memory consumption compared to ILPs. They
remark that their implementation is just a proof of concept, and more
efficient algorithms to find independent sets are known. They further note
that this approach is cheap, as no expensive ILP solver is needed.

An enhanced CP approach for routing and scheduling is presented by Vlk et al.
[VlHa21b]. The authors present separate models for routing and scheduling, and
use them in a problem decomposition algorithm. First, they compute a routing
for the given streams. A schedule is computed using this routing. If no
schedule was found, constraints are added to the routing model to prohibit the
last routing solution. These steps are repeated until a schedule is found.
Alternatively, it may be the case that all possible routings for some stream
lead to a conflict while scheduling. In that case, an instance is deemed as
infeasible. Figure 17 depicts a flow diagram of the proposed approach.

Figure 17: Flow diagram of the proposed approach in [VlHa21b].

Most other research works which performs routing and scheduling in separate
steps considers an instance infeasible after only one pass of routing and
scheduling. The model also includes queue assignment of streams as additional
degrees of freedom. The authors substitute their scheduling model with the
algorithms from [DuNa16], [CrOl16], and [Ca18], and compared schedulability of
the resulting algorithms with their approach. Their CP model was able to
schedule the most instances, while the SMT model scheduled significantly fewer
instances than all other algorithms. Scheduling time was similar for all
algorithms except for the SMT model, which needed multiple times longer for
most instances.

####  IV-B2 Scheduling w/ Reliability

Reliability is an important topic in the literature of joint routing and
scheduling. The possibility of selecting disjoint paths for redundant stream
copies further increases reliability in these research works.

Pozo et al. [PoRo18] present an ILP for joint routing which considers
reliability constraints. After a single link failure, all streams over this
link must be rescheduled and rerouted. The authors propose a fast heuristic
for this case. They also evaluate which properties of a schedule are
beneficial for the repairability in case of a failure. The results indicate
that schedules which maximize the gaps between frame transmissions are much
easier to repair than schedules which minimize the flowspan, even for three
simultaneous link failures.

Atallah et al. [AtBa18] give a heuristic for fault-tolerant joint scheduling,
routing, and topology generation. Their algorithm starts with a full mesh
topology. Streams are routed and scheduled one after another. A k-shortest-
paths algorithm is used to enumerate possible paths for a stream. If a path
with available time slots is found, schedule and routing are fixed for later
iterations. This is repeated multiple times with disjoint paths for redundant
copies of a stream to ensure reliability. Links and bridges are only included
in the final topology when they are used by some stream. The algorithm also
selects bridges such that more expensive bridges are only used when necessary.
Figure 18 depicts this approach for topology generation. The authors compare
their algorithm to another approach which realizes redundant paths through
multiple copies of the network topology. The proposed algorithm scheduled all
problem instances, while it reduced topology costs considerably.

Figure 18: Topology generation approach of [AtBa18]. A full mesh topology is
used during routing and scheduling. Links used in the final routing are
indicated in red. Only these links are included in the final topology. The
approach covers the selection of bridges from a library depending on the
generated topology. More expensive bridges with a higher number of ports are
indicated in dark blue.

The authors of [AtBa20] propose an incremental ILP scheme to comply with
requirements for the robustness against single link failures. First, the
authors present a GRASP heuristic for routing which considers reliability
constraints. Streams are replicated and routed over disjoint paths to comply
with requirements regarding robustness to single link failures. The resulting
routing is used as input to the iterative ILP approach. Streams are
partitioned into groups by introducing a conflict metric and computing a
weighted cut in the conflict graph. Groups of streams are scheduled one after
another. The computed schedules are fixed when the next group is scheduled.
They model egress ports with only one queue for TT traffic and frame
isolation. A comparison of the presented ILP with the ILPs from [ScDa17] and
[SmGl17] demonstrates that it outperforms both approaches regarding solving
times.

Instead of robustness against link failures, Zhou et al. [ZhSa21] consider
reliability against frame loss, i.e., frames that are lost spontaneously
during transmission without a permanent link failure. They integrate
constraints regarding the loss probability along the routed path of a stream
in their SMT model. However, these probabilities are only approximated, as the
used theory solver cannot handle exponentials. An incremental scheme similar
to [AtBa20] is used. Subsets of streams are scheduled and routed one after
another until all streams are scheduled. Stream schedules are fixed in
subsequent iterations. They use redundant copies of streams to further reduce
the probability of frame loss, as there may be no single path with the
required reliability. In contrast to other works, e.g., [AtBa20], [RePo20],
and [GaZa17], they do not enforce paths to be link disjoint. Their evaluations
show that schedulability with a given level of reliability against frame loss
increases with a higher number of redundant copies per stream.

Another incremental scheme for scheduling and routing in safety-critical
automotive applications is presented by Zhou et al. [ZhSa21b]. They consider
possibly undetected systematic faults of bridges, i.e., implementation bugs or
divergence from specifications, instead of randomly arising errors like frame
loss. Messages and bridges have an Automotive Safety Integrity Level (ASIL)
assigned [Iso26262] which defines reliability constraints of the respective
component. A higher ASIL corresponds to higher reliability. Additionally, to
computing routing and scheduling, their algorithm also selects which bridges
to use from a library. Messages can be decomposed into redundant message
copies with lower ASIL to be sent over bridges with lower ASIL. A comparison
of the presented algorithm with and without message decomposition shows that
the total costs for bridges can be reduced by up to 23.55% in the evaluation
scenarios. The authors note that higher ASILs increase the required number of
message copies, which leads to more congestion in the network and thus higher
end-to-end delays. Evaluations on a real-life automotive test case are
presented. Synthesis time increases considerably with ASIL decomposition.
However, the selected bridges cost only a third compared to using only bridges
with the highest ASIL. The PhD thesis of Zhou [Zh22] compiles the content of
[ZhSa21], [ZhSa21b], and [ZhSa22].

The authors of [RePo20] present separate CP models to compute schedules and
routings as work-in-progress. These models take security and reliability
considerations into account. The routing computed with the first model is used
as fixed input for the scheduling model, similar to [AtBa20]. Redundant
streams with disjoint paths are added if needed to comply with security and
reliability constraints.

The ideas from [RePo20] are extended in [ReCr22]. Besides the CP model, a
simulated annealing algorithm combined with a list scheduler is given.
Additionally, a post-processing for latency reduction of scheduled streams is
applied after scheduling. Their evaluations without security and reliability
constraints indicate that the SA approach is able to find a feasible schedule
in reasonable time, even for huge problem instances. However, they also
introduce a measure for schedule and routing costs. This measure contains
stream latencies, penalties for streams which were not scheduled, and
penalties for overlapping paths. The results demonstrates that schedules
computed by SA have up to three times higher costs compared to schedules
computed by the CP approach. Introducing the security and reliability
constraints to the same problem instances increased the costs of schedules
computed by SA by up to a factor of $\sim 3.5$. Nevertheless, the authors
state that the SA approach can be useful in comparing costs and reliability
capabilities of topologies, or to reconfigure the network in case of link
failures.

Li et al. [LiCh21] propose a heuristic for joint routing and scheduling with
reliability constraints. A greedy algorithm is used to select paths for
redundant copies of streams such that link utilization is balanced. Frames are
scheduled as soon as possible. Both algorithms are combined in an iterative
local search scheme. Already scheduled and routed streams are randomly removed
from time to time, and the remaining streams are rescheduled and rerouted in
random order. While the authors report a reduction in frame losses by their
approach, end-to-end delays are significantly larger compared to schedules
with routings computed by Dijkstra’s algorithm.

####  IV-B3 Scheduling w/ Other Traffic

This section presents research works concerned with scheduling in the presence
of other traffic classes.

Gavriluţ et al. [GaZh18] construct a GRASP heuristic to schedule TT streams
while taking AVB traffic into account. In contrast to [PoRa16], their approach
handles TT and AVB streams simultaneously. The routing of AVB streams is given
and cannot be changed. In the first evaluation, the authors use a shortest
paths algorithm to compute the routing. The results show that using the GRASP
heuristic with an objective that considers tardiness of AVB streams leads to
AVB streams meeting their deadlines. In contrast to that, the GRASP heuristic
with other objectives not considering AVB streams results in schedules with
late AVB streams. Even better results are obtained when a routing with load
balancing is used before scheduling, which also decreases overall runtime.
They report that AVB traffic does not benefit from minimizing the number of
queues for TT streams. However, this is rather obvious, as their system model
assumes that AVB streams already have an assignment to AVB queues. Solving
time of the GRASP heuristic increases considerably when AVB streams are taken
into account. A short preview of these results was previously published in
[GaPo18].

Berisa et al. [BeZh22] propose a heuristic for the joint routing and
scheduling of TT streams in the presence of AVB streams. They make use of
frame preemption to increase the schedulability of AVB streams. To that end,
they present a worst-case response-time analysis of AVB streams with
preemption. The heuristic is based on prior works by Gavriluţ et al. [GaZh18].
Their evaluations demonstrate that the schedulability of AVB streams can be
increased by allowing frame preemption while the runtime of the heuristic also
increases significantly in this case.

Alnajin et al. [AlSa19] give a QoS-aware routing algorithm for TSN streams
with respect to various metrics. They present four scheduling heuristics
combined with these routings. They compare these algorithms regarding the
number of guard bands needed in the resulting schedules. Their evaluations
show that their heuristics can reduce the number of guard bands significantly.
They note that reducing the number of guard bands is beneficial for BE
traffic.

Li et al. [LiJi22] present a heuristic for joint routing and scheduling to
eliminate non-deterministic queuing delay in networks with mixed time-critical
traffic. Their scheduling algorithm divides the bandwidth resources into time
slots and assigns streams to these slots such that transmission conflicts
cannot arise. Similar to [OlCr18], the maximum length of the resulting GCLs is
bounded instead of being computed by a post-processing from transmission
offsets. The solving time with the heuristic is compared to [AtBa20],
[FaDu18], and [ArHi20]. Solving time is the only inspected metric as the
presented algorithm, and the three compared approaches have no objective
functions. In the presented scenarios, all three methods were outperformed by
multiple orders of magnitude. The authors report schedules for 4000 streams
with just 12 GCL entries per egress port on average.

####  IV-B4 Multicast

This section highlights research works specifically concerned with multicast
streams in a joint routing and scheduling approach.

The joint routing and scheduling model from [ScDa17] is extended for multicast
support in [ScTi20]. The authors state that while this extension is trivial
for pure scheduling models, joint routing and scheduling with multicast is
more complicated as additional constraints for the routing are needed. Various
pre-processing steps are presented to reduce the solution space and thus
solving time. The authors report that the time to find a feasible solution was
reduced by up to 82.4% while the overall solving time was reduced by up to
47.6%.

Another approach for joint routing and scheduling with multicast streams is
presented by Li et al. [LiZh21]. Similar to [ScTi20], the authors use pre-
processing to simplify solving of the model. The streams are divided into
groups by spectral clustering based on their properties. Similar to [AtBa20]
and [RePo20], these groups are routed and scheduled one after another such
that previously computed schedules and routes are fixed. The authors report
that random clustering result in slightly longer flowspans. As in similar
iterative approaches, reduced overall solving times and increased
schedulability are reported.

Yu et al. [YuGu20] propose an incremental approach with ILPs. In contrast to
[ScTi20], they route and schedule multicast streams one by one. Multiple
queues per egress port and queue assignment are also integrated in their
model. Additionally, they propose a pre-processing scheme which aims to
simplify the topology. The pre-processing merges cliques in the topology to a
single link. If routing and schedule can be computed, both are modified for
the original graph. Otherwise the conflicting links are expanded and routing
and scheduling are repeated. Compared to [St10] with a Steiner tree as fixed
routing, the proposed approach can schedule significantly more instances.

A biology-inspired algorithm is given by Pahlevan et al. [PaOb18]. They
construct a genetic algorithm for joint routing and scheduling which also
comprises features like multicast streams and dependencies between streams.
The authors state multicast capabilities as one of their main contributions,
but consider multicast streams simply as multiple unicast streams. Their model
allows queuing, but restricts it to isolation. In contrast to [CrOl16],
[OlCr18], and [GaPo18], only a single queue per egress port is dedicated to TT
traffic. While their evaluations indicate that solving time increases compared
to scheduling with a fixed routing, they show that schedulability increases by
joint routing and scheduling.

In later works, Pahlevan et al. [PaTa19] present a heuristic list scheduling
algorithm for the same purpose. They model queuing and multicast streams in
the same way as in [PaOb18]. Their evaluations again demonstrate that joint
routing and scheduling increases schedulability.

####  IV-B5 Reconfiguration

Reconfiguration of streams can benefit from modifying not only a schedule, but
also the respective routing. Newly added streams can be routed over paths with
low utilization. This section compiles the literature about reconfiguration in
joint routing and scheduling apporaches.

Research work from Syed et al. [SyAy20] deals with joint routing and
scheduling in in-vehicle networks. They propose an ILP model for static
streams which takes load balancing into account. They compute schedules and
routings for static streams such that as many streams as possible can later be
added dynamically.

Following their work in [SyAy20], Syed et al. present multiple heuristics for
the dynamic scheduling of new streams in an existing schedule [SyAy21]. Their
heuristics are based on modelling the scheduling problem as a vector bin
packing problem. They evaluate the time needed for adding new streams in an
automotive use case, as reconfiguration in such scenarios has strict timing
requirements.

The authors of [SyAy21b] construct multiple heuristics for dynamic scheduling
and routing with reliability constraints. All heuristics are based on the same
idea as in [SyAy21]. Every stream is replicated twice when added to an
existing schedule to ensure reliability. The best heuristic is able to
schedule 500 streams in about 410 ms. The authors state this is a reasonable
response time in automotive use cases.

Yu et al. [YuWa20] developed a heuristic for online rescheduling in scenarios
with virtual machines as communication endpoints. Virtual machines in a cloud
computing environment may be migrated from one physical device to another such
that schedules and routings must be updated. Additionally, all streams are
multicast streams, which complicates rescheduling after a VM migration.
Therefore, the multicast tree for a stream is computed such that the maximal
distance from any possible device where a VM could run to any destination is
minimized. The authors state that this will reduce conflicts when a VM is
migrated, as the new paths are short. Given a schedule and a stream that is
migrated, a greedy heuristic computes the new schedule based on the
precomputed multicast tree. The authors compare their proposed routing
heuristic with an optimal routing obtained by an ILP. Solving times are
significantly reduced, while the routing objective grows only slightly
compared to the optimal routing. Schedulability in case of a migration is
considerably increased in comparison to the same scheduling heuristic used
with a routing computed by the KMB algorithm [KMB].

Li et al. [LiXi22] consider the reconfiguration of routing, scheduling, and
mapping of applications to end stations in case of permanent end station
failure. They extend the ILP of [NaDu18] to schedule applications to end
stations for global reconfiguration. As the resulting ILP instances are hard
to solve, they propose a heuristic routing and mapping algorithm as
alternative. The results of this heuristic are fixed in the ILP model, such
that only a schedule is computed. The heuristic approach is able to
reconfigure almost all instances, while the ILP times out for most of them in
their evaluations. While both algorithms have exponential runtime in the
number of streams, the heuristic is two orders of magnitude faster for the
considered instances.

An iterative approach which schedules streams one by one is presented in
[HuWa21]. In contrast to [YuGu20], the computed schedules are constrained to
no-wait scheduling, i.e., no queuing delays are allowed. The authors compare
the proposed approach with [ScDa17] and [AtBa20] with respect to
schedulability and show that schedulability is slightly increased. The
proposed pre-processing for the routing approach gives only minor improvements
regarding schedulability. The authors report that 97.5% of the streams in an
instance with 2000 streams were scheduled in less than 10 seconds per stream.
They state this is fast enough for online scenarios.

####  IV-B6 Other Topics

This sections summarizes research works with unique topics that do not fit
well into the previous groups.

The authors of [ZhSa22] propose a heuristic model to schedule streams in the
presence of frame preemption similar to [PaSa19]. Additionally, they also
include route computation in their algorithm. They present an SMT model for
this purpose and use it in an iterative approach, similar to
[MaAm18][MaAm21][SmGl17]. The presented results show that scheduling time not
only increases with the network size and the number of streams, but also with
the maximum number of allowed preemptions and retransmissions. However,
allowing more preemptions increases schedulability only to some instance-
specific threshold.

Gavriluţ et al. [GaZa17] give multiple algorithms to simultaneously compute
scheduling and routing of TT streams. In contrast to [AtBa20], [RePo20], and
[FaDu18], these algorithms additionally generate the network topology with
minimized costs. They present a problem-specific heuristic, a GRASP heuristic,
and a CP approach, and compare them to each other regarding solving time and
solution quality. Their optimization objective captures worst-case end-to-end
delays as well as topology costs, i.e., costs for links and bridges which are
selected from a library. Redundant copies of streams are included for
reliability considerations. Their evaluations focus on a comparison of the
three presented algorithms. As expected, the CP approach does not scale well.
The GRASP heuristic finds better solutions in minutes compared to the CP
approach in two days.

An SMT model which includes scheduling, routing, and queue assignment of
streams simultaneously is presented by [XuXu20]. The authors state that saving
bandwidth by not using the same GCL cycle for all egress ports is also novel
to their approach. However, this is not true as other works even schedule GCL
closing events, e.g. [StCr18], [JiXi20]. They propose to minimize the number
of bridges used by scheduled traffic in order to maximize utilization. In
comparison to the list scheduler of [PaTa19], schedulability is increased
while the solving time approaches the timeout after 40 h for fairly small
instances.

Zhou et al. [ZhWa21] construct a heuristic which allows different routes for
frames of the same stream to enable load balancing. The required mechanism is
implemented by an SDN architecture. The scheduling procedure is a mix of
evolutionary algorithm and greedy algorithm. Multiple variations of the
heuristic are compared in the evaluations. In the presented scenarios,
scheduling time increased linearly with the number of streams.

Another incremental scheme for scheduling and routing is presented by Mahfouzi
et al. [MaAm18][MaAm21]. The authors investigate the stability of control
applications, i.e., latency and jitter of messages sent by these applications.
Instead of grouping streams by some conflict measure, they divide the network
period in slices and group the streams by the time slice in which their
transmission can start. They allow routing only over some fixed number of
precomputed shortest paths per source-destination pair, similar to [GaZh18]
and the AVB routing in [PoRa16]. Their model allows unrestricted queuing
without further discussion of this topic. Their evaluations indicate that the
number of allowed paths has a huge impact to solving time. However, they note
that three paths per pair of nodes may be sufficient, as schedulability is
over 90% in this case. They conclude that the search space can be considerably
reduced with negligible impact on schedulability.

Hellmanns et al. [HeHa21] focus their work not on the ability to compute
schedules, but analyze how input pre-processings and solver configuration
influence the scalability of solving a joint routing and scheduling ILP model.
They categorize optimizations by whether they are input pre-processing, e.g.,
topology reduction, model generation related, e.g., tighter variable bounds,
or solver configurations, e.g. the use of value hints for variables. They give
an ILP without any optimizations as baseline for their evaluations. Different
combinations of the proposed optimizations are tested on the same set of
problem instances and compared with respect to scalability and schedulability.
Their evaluations indicate that solving time can greatly benefit from input
pre-processings, but the effects of model generation optimizations and solver
configurations are negligible. Some of the optimizations even increase solving
time. However, queuing is not supported by their base model. Thus, the
observations only hold for the no-wait case without queuing delay. It is not
clear whether these results can be transferred to other problem extensions
from the literature.

##  V Comparison

We compare the presented research work from Section IV. First, we compile
modelling assumptions and problem extensions. Second, we present common
scheduling objectives. Then, we investigate problem instances used for
evaluations. Finally, we summarize results regarding the scalability of the
presented approaches.

###  V-A Modelling Assumptions and Problem Extensions

Research work |  AVB |  BE |  Queuing |  Fixed GCL length |  Reconfiguration |  Reliability |  Multicast |  Task Scheduling
---|---|---|---|---|---|---|---|---
Steiner [St10] |  - |  - |  ✓ |  - |  - |  - |  ✓ |  -
Duerr et al. [DuNa16] |  - |  ✓ |  - |  - |  - |  - |  - |  -
Pop et al. [PoRa16] |  ✓ |  - |  (✓) |  - |  - |  - |  Only AVB |  -
Craciunas et al. [CrOl16] |  - |  - |  (✓) |  - |  - |  - |  - |  -
Farzaneh et al. [FaKu17] |  - |  - |  - |  - |  - |  - |  - |  -
Raagaard et al. [RaPo17] |  - |  - |  (✓) |  - |  ✓ |  - |  - |  -
Steiner et al. [StCr18] |  - |  (✓) |  (✓) |  ✓ |  - |  - |  ✓ |  -
Gavriluţ et al. [GaPo18] |  ✓ |  - |  (✓) |  - |  - |  - |  - |  -
Oliver et al. [OlCr18] |  - |  (✓) |  (✓) |  ✓ |  - |  - |  ✓ |  -
Jin et al. [JiXi19] |  - |  - |  - |  - |  - |  - |  - |  -
Santos et al. [SaCa19] |  - |  ✓ |  ✓ |  ✓ |  - |  - |  ✓ |  -
Park et al. [PaSa19] |  - |  - |  ✓ |  - |  - |  ✓ |  - |  -
Ansah et al. [AnAb19] |  - |  - |  ✓ |  - |  - |  - |  - |  -
Dobrin et al. [DoDe19] |  - |  - |  ✓ |  - |  - |  ✓ |  - |  -
Hellmanns et al. [HeGl20] |  - |  (✓) |  (✓) |  - |  - |  - |  - |  -
Jin et al. [JiXi20] |  - |  (✓) |  (✓) |  ✓ |  - |  - |  - |  -
Reusch et al. [ReZh20] |  - |  (✓) |  ✓ |  ✓ |  - |  - |  - |  -
Barzegaran et al. [BaZa20] |  - |  - |  (✓) |  - |  - |  - |  - |  ✓
Ginthör et al. [GiGi20] |  - |  ✓ |  ✓ |  ✓ |  - |  - |  - |  -
Zhou et al. [ZhLi20] |  - |  - |  (✓) |  - |  - |  - |  - |  -
Vlk et al. [VlHa20] |  - |  - |  ✓ |  - |  - |  - |  - |  -
Houtan et al. [HoAs21] |  - |  ✓ |  (✓) |  - |  - |  - |  - |  -
Barzegaran et al. [BaPo21] |  - |  - |  (✓) |  - |  - |  - |  ✓ |  ✓
Kim et al. [KiCh21] |  - |  (✓) |  ✓ |  - |  - |  - |  - |  -
Dai et al. [DaWa21] |  - |  (✓) |  - |  - |  - |  - |  - |  -
Kim et al. [KiLe21][KiLe22] |  - |  (✓) |  ✓ |  - |  - |  - |  - |  -
Craciunas et al. [CrOl21] |  - |  - |  (✓) |  - |  - |  ✓ |  - |  -
Feng et al. [FeCa21] |  ✓ |  ✓ |  (✓) |  - |  - |  ✓ |  - |  -
Feng et al. [FeYa21] |  - |  - |  (✓) |  - |  - |  - |  ✓ |  ✓
Pang et al. [PaHu21] |  - |  - |  ✓ |  - |  ✓ |  - |  ✓ |  -
Vlk et al. [VlBr22] |  - |  - |  (✓) |  - |  - |  - |  - |  -
Feng et al. [FeDe22] |  - |  ✓ |  ✓ |  - |  - |  ✓ |  - |  -
Wang et al. [WaYa22] |  - |  (✓) |  - |  - |  - |  - |  - |  -
Chaine et al. [CaBo22] |  - |  - |  (✓) |  - |  - |  - |  - |  -
Bujosa et al. [BuAs22] |  - |  - |  ✓ |  - |  - |  - |  ✓ |  -
Barzegaran et al. [BaRe22] |  - |  (✓) |  ✓ |  ✓ |  - |  - |  - |  -
Table 2: Overview of considered problem extensions and restrictions in the literature of scheduling approaches with a fixed routing.  Research work |  AVB |  BE |  Queuing |  Fixed GCL length |  Reconfiguration |  Reliability |  Multicast |  Task Scheduling
---|---|---|---|---|---|---|---|---
Gavriluţ et al. [GaZa17] |  - |  - |  - |  - |  - |  ✓ |  ✓ |  -
Schweissguth et al. [ScDa17] |  - |  - |  - |  - |  - |  - |  - |  -
Smirnov et al. [SmGl17] |  - |  ✓ |  - |  - |  - |  - |  ✓ |  -
Kentis et al. [KeBe17] |  - |  - |  ✓ |  - |  - |  - |  - |  -
Falk et al. [FaDu18] |  - |  - |  - |  - |  - |  - |  - |  -
Gavriluţ et al. [GaZh18] |  ✓ |  - |  (✓) |  - |  - |  - |  - |  -
Pozo et al. [PoRo18] |  - |  - |  - |  - |  - |  ✓ |  ✓ |  -
Pahlevan et al. [PaOb18] |  - |  (✓) |  (✓) |  - |  - |  - |  - |  -
Mahfouzi et al. [MaAm18][MaAm21] |  - |  - |  ✓ |  - |  - |  - |  - |  ✓
Atallah et al. [AtBa18] |  - |  - |  - |  - |  - |  ✓ |  - |  -
Pahlevan et al. [PaTa19] |  - |  (✓) |  (✓) |  - |  - |  - |  - |  -
Alnajim et al. [AlSa19] |  - |  ✓ |  ✓ |  - |  - |  - |  - |  -
Atallah et al. [AtBa20] |  - |  - |  (✓) |  - |  - |  ✓ |  - |  -
Falk et al. [FaDu20] |  - |  - |  - |  - |  - |  - |  - |  -
Wang et al. [WaCh20] |  - |  - |  - |  - |  - |  - |  - |  -
Syed et al. [SyAy20] |  - |  - |  - |  - |  - |  - |  - |  -
Reusch et al. [RePo20] |  - |  - |  - |  - |  - |  ✓ |  - |  ✓
Li et al. [LiLi20] |  - |  |  - |  - |  - |  - |  - |  -
Xu et al. [XuXu20] |  - |  - |  (✓) |  ✓ |  - |  - |  - |  -
Yu et al. [YuGu20] |  - |  - |  (✓) |  ✓ |  - |  - |  ✓ |  -
Schweissguth et al. [ScTi20] |  - |  - |  - |  - |  - |  - |  ✓ |  -
Yu et al. [YuWa20] |  - |  - |  (✓) |  - |  ✓ |  - |  ✓ |  -
Arestova et al. [ArHi20] |  - |  - |  (✓) |  - |  - |  - |  - |  -
Syed et al. [SyAy21] |  - |  - |  - |  - |  ✓ |  - |  - |  -
Syed et al. [SyAy21b] |  - |  - |  - |  - |  ✓ |  ✓ |  - |  -
Zhou et al. [ZhSa21] |  - |  - |  - |  - |  - |  ✓ |  - |  -
Zhou et al. [ZhSa21b] |  - |  - |  - |  - |  - |  ✓ |  - |  -
Vlk et al. [VlHa21b] |  - |  - |  (✓) |  - |  - |  - |  - |  -
Li et al. [LiZh21] |  - |  - |  (✓) |  - |  - |  - |  ✓ |  -
Zhou et al. [ZhWa21] |  - |  - |  (✓) |  - |  - |  - |  - |  -
Huang et al. [HuWa21] |  - |  - |  - |  - |  ✓ |  - |  - |  -
Li et al. [LiCh21] |  - |  - |  ✓ |  - |  - |  ✓ |  ✓ |  -
Nie et al. [NiLi22] |  - |  - |  - |  - |  - |  - |  - |  -
Reusch et al. [ReCr22] |  - |  - |  (✓) |  - |  - |  ✓ |  ✓ |  ✓
Zhou et al. [ZhSa22] |  - |  - |  ✓ |  - |  - |  - |  - |  -
Xu et al. [XuXu22] |  - |  - |  (✓) |  - |  - |  - |  - |  -
Li et al. [LiXi22] |  - |  - |  - |  - |  ✓ |  - |  - |  -
Li et al. [LiJi22] |  - |  ✓ |  ✓ |  ✓ |  - |  - |  - |  -
Berisa et al. [BeZh22] |  ✓ |  - |  ✓ |  - |  - |  - |  - |  -
Table 3: Overview of considered problem extensions and restrictions in the
literature of joint routing approaches.

Table 2 compiles important modelling assumptions and problem extensions in the
surveyed research works with fixed routings. Table 3 shows the same
information for research works about the joint routing problem. In the
following section, we compile the contributions to each of these topics.

####  V-A1 Other Traffic

Only five works examine TT and AVB streams simultaneously. Pop et al. [PoRa16]
present a GRASP heuristic for the handling of AVB streams. The heuristic gets
a schedule of TT streams as input and cannot change it. The authors of
[GaPo18] present a short preview of AVB-aware scheduling, which was later
extended in [GaZh18]. Feng et al. [FeYa21] consider the bandwidth available to
AVB and BE traffic in their approach as they consider repeated frame loss
which may result in starvation. Berisa et al. [BeZh22] use frame preemption
and a worst-case end-to-end delay analysis to increase the schedulability of
AVB streams. Other research works handle BE traffic by minimizing the flowspan
which yields a large time slot at the end of a schedule exclusively for other
traffic, e.g., [DuNa16], [HoAs21], and [HeGl20]. The tables indicate works
that do not mention BE traffic, but use objective functions that are
beneficial to other traffic or that limit the number of guard bands with (✓).
For instance, Oliver et al. [OlCr18] limit the number of guard bands
indirectly by introducing a fixed number of transmission time windows per
egress port.

####  V-A2 Queuing

Queuing is a controversial topic in the TSN scheduling literature as non-
determinism, e.g., frame loss, may cause serious problems. Some research works
do not allow queuing at all, e.g., [DuNa16], [FaDu18], and [AtBa20]. The
majority of the algorithms in the literature uses frame isolation introduces
by [CrOl16]. These works are indicated by (✓) in the Tables 2 and 3. Vlk et
al. [VlHa20] discuss the effects of isolation constraints. They report results
indicating that isolation constraints reduce schedulability significantly.
However, they propose a different solution to deal with non-determinism,
effectively modifying the TAS. Thus, their results are not applicable to
current TSN implementations. There are some research works which allow
unrestricted queuing, e.g., [DoDe19] and [SaCa19]. Most of these works do not
elaborate on the consequences of unrestricted queuing. Examples for the
opposite are Reusch et al. [ReZh20], Barzegaran et al. [BaRe22], and Berisa et
al. [BeZh22]. The authors include a worst-case end-to-end delay analysis in
their algorithms such that even in the case of non-determinism, deadlines are
met.

####  V-A3 Fixed GCL Length

Most algorithms presented in the literature handle the generation of GCLs
indirectly. They schedule transmission offsets of frames at end stations and
intermediate bridges. The GCLs are generated by a post-processing after
scheduling. This step is only mentioned, and the respective authors do not
elaborate on it. Examples for such works are [CrOl16], [ReCr22], and [VlBr22].
However, computing GCLs by a post-processing comes with two drawbacks. First,
GCLs have limited size in bridges. Thus, GCLs obtained by a post-processing
may not be deployable. Second, the scheduling algorithm cannot include
considerations for guard bands. There are some exceptions to this in the
literature. Jin et al. [JiXi20] present a heuristic to compute schedules with
a limited number of GCL entries per egress port. Santos et al. [SaCa19] give a
detailed SMT model for TSN scheduling which includes the explicit
representation of GCLs. Some works limit the number of GCL entries indirectly
by introducing transmission windows for egress ports. Streams are mapped to
these transmission windows and their number is fixed before scheduling.
Examples of such works are [StCr18], [OlCr18], and [ReZh20]. All schedules for
no-wait scheduling can be deployed with a fixed number of GCL entries. As no
queuing delay is allowed, frames cannot be scheduled to wait at closed gates.
Such a schedule can be deployed by opening all gates for TT traffic at the
start of a hyperperiod and never closing them.

####  V-A4 Reconfiguration

In some scenarios it may be infeasible to compute new schedules every time a
stream should be integrated into or removed from an existing schedule. For
instance, automotive scenarios may include ad-hoc connections between cars and
infrastructure. Computing new schedules every time a new stream is added may
take too much time, even with heuristic algorithms. Syed et al. [SyAy21]
[SyAy21b] consider reconfiguration in such automotive scenarios. Additionally,
they also present preliminary work about computing schedules suitable for
later reconfiguration in [SyAy20]. Raagaard et al. [RaPo17] present a
heuristic to add streams to an existing schedule. When the heuristic fails,
they assign the new stream to other egress queues which were unused before.
Pang et al. [PaHu21] present work about deploying an updated schedule to a
network already executing another schedule. Their approach allows updating the
schedule without frame loss or new streams interfering with the old schedule.
Another use case for reconfiguration is the reallocation of tasks sending and
receiving TT streams. Yu et al. [YuWa20] use virtual machines as end stations
in their model. These virtual machines may be migrated from one physical
device to another, which requires updating schedules and routings. A similar
example for reconfiguration is presented in [LiXi22]. The authors propose an
approach for updating a schedule in case of a permanent end station failure.
Schedules and routings must be updated in this case as in [YuWa20].

####  V-A5 Reliability

Fault Model |  Research work
---|---
Permanent link failure |  Gavriluţ et al. [GaZa17], Pozo et al. [PoRo18], Atallah et al. [AtBa18], Atallah et al. [AtBa20], Reusch et al. [RePo20], Reusch et al. [ReCr22], Syed et al. [SyAy21b]
Frame loss |  Gavriluţ et al. [GaZa17], Park et al. [PaSa19], Dobrin et al. [DoDe19], Reusch et al. [RePo20], Reusch et al. [ReCr22], Atallah et al. [AtBa18], Atallah et al. [AtBa20], Zhou et al. [ZhSa21], Li et al. [LiCh21], Syed et al. [SyAy21b], Feng et al. [FeCa21] [FeDe22]
Clock drift |  Craciunas et al. [CrOl21]
Hardware bugs |  Zhou et al. [ZhSa21b]
Table 4: Fault models in research works dedicated to reliability.

Table 4 compiles fault models used in the literature. The listed research
works construct schedules robust in the respective fault model. Computing
schedules robust against frame loss is the most common kind of reliability in
the TSN scheduling literature. Park et al. [PaHu21] handle frame loss by
allowing the retransmission of frames. Schedules for such a scenario must
schedule enough time between frame transmissions such that retransmissions do
not interfere with other frames. Another way to deal with frame loss is
proposed by Feng et al. [FeCa21][FeDe22]. In contrast to [PaHu21], they do not
use retransmissions, but they schedule redundant copies of the same stream
over the same path. Zhou et al. [ZhSa21] approximate the probability of frame
loss in a joint routing and scheduling model. Redundant copies of streams are
routed over not necessarily disjoint paths to reduce the probability of frame
loss. Robustness against permanent single link failures are also covered in
several works. There are two approaches in the TSN scheduling literature to
handles such failures. First, redundant copies of streams are scheduled and
routed over link-disjoint paths before a link failure arises. Examples for
such works are [AtBa18], [AtBa20], [GaZa17], and [SyAy21b]. Second, streams
can be rescheduled and rerouted after a link failure occurred. Pozo et al.
[PoRo18] present a heuristic for fast rescheduling and rerouting in this case.