PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey of Scheduling Algorithms for the Time-Aware Shaper in Time-Sensitive Networking (TSN)

Thomas Stüber, Lukas Osswald, Steffen Lindner, Michael Menth

arXiv:2211.10954v2cs.NI

TL;DR

The paper addresses TSN scheduling and related extensions, including an open problem of assigning streams to suitable TSN mechanisms. It synthesizes and compares existing scheduling research, concluding that coexistence among mechanisms and evaluation quality remain open concerns.

  • Problem

    A major open TSN problem is assigning streams with differing real-time requirements to appropriate mechanisms and producing the corresponding network configuration.

    Source: 6) Use of TSN Mechanisms · p. 33

  • Method

    The paper defines TSN scheduling and its extensions, summarizes solution methods, and reviews and compares literature by assumptions, objectives, instances, and scalability.

    Source: §VIII · p. 33

  • Results

    The survey classifies and compares a broad body of TSN scheduling work across modelling assumptions, scheduling objectives, problem instances, and scalability.

    Source: §VIII · p. 33

  • Takeaways & Limitations

    Coexistence among TSN mechanisms and assignment of streams to them remain major open problems.

    Source: 6) Use of TSN Mechanisms · p. 33

    Evaluations often use synthetic instances, and limited instance descriptions and isolated-case results make significance and cross-approach comparisons difficult to assess.

    Source: 1) Evaluation Methodologies · p. 32

Abstract

from arXiv · show

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 frames by end stations 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 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 end stations 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.

I. INTRODUCTION

The paper surveys TAS-based TSN scheduling, an area for which standardization does not yet provide schedule-computation methods and which prior reviews cover only in part. It defines the scheduling problem and common solution methods, reviews and categorizes the literature, compares its assumptions and evaluations, and identifies open questions.

A. Related Surveys

  • Earlier surveys address broader topics or only briefly cover scheduling, and the authors report that no other review focuses on TSN scheduling algorithms as its main topic.The survey compares their scope and overlap with this work.Source: A. Related Surveys · pp. 1–2

B. Contribution

  • The paper defines the TAS-based TSN scheduling problem and its common extensions, and introduces solution methods used in the literature.Some extensions lead to optimization problems.Source: B. Contribution · p. 2
  • The survey reviews currently available literature on scheduling for the TAS.Its stated scope excludes work on other technologies or TSN traffic shapers.Source: §I · p. 1, B. Contribution · p. 2
  • The authors categorize the literature, identify research directions, and highlight contributions across those topics.Source: B. Contribution · p. 2
  • The paper compares algorithms and evaluations to derive open research questions.The comparisons address modelling assumptions, optimization objectives, problem instances, and scalability.Source: B. Contribution · p. 2, C. Survey Structure · p. 2

C. Survey Structure

  • The paper proceeds from TSN foundations to the scheduling problem and solution methods, then surveys, compares, and discusses the literature before concluding.Source: C. Survey Structure · p. 2, §II · p. 2

A. Audio Video Bridging (AVB)

AVB and TSN add mechanisms for real-time communication over switched Ethernet, including synchronized clocks, stream admission, and traffic shaping. The TSN overview also covers path selection, priorities, frame preemption, and frame replication for reliability.

A. Audio Video Bridging (AVB)

  • AVB was developed to meet multimedia applications’ need for bounded latency and jitter in switched Ethernet, and organizes its standards around synchronization, admission control, and traffic shaping.Source: A. Audio Video Bridging (AVB) · pp. 2–3

1) Time Synchronisation:

  • gPTP synchronizes device clocks to a Grandmaster and allows sub-microsecond precision for devices within seven hops.Intermediate nodes adjust time information for propagation and processing delays and clock-speed differences.Source: 1) Time Synchronisation · p. 3

2) Admission Control:

  • SRP lets talkers advertise stream bandwidth and real-time requirements; bridges forward requests when resources are available and reserve bandwidth after listener acknowledgment.Source: 2) Admission Control · p. 3

3) Traffic Shaping:

  • CBS permits transmission when a queue’s credit is non-negative and can guarantee 2 ms and 50 ms bounds for class A and B traffic in networks of at most seven hops.Its worst-case average delay can reach 250 μs per hop, and the cited AVB guarantees do not meet the requirements of some industrial use cases.Source: 3) Traffic Shaping · p. 3, B. Time-Sensitive Networking (TSN) · p. 3

B. Time-Sensitive Networking (TSN)

2) Path Selection:

  • TSN path selection can use computed tree paths rather than relying on Spanning Tree Protocols or Shortest Path Bridging, while egress ports use up to eight priority queues with strict-priority selection.Source: 2) Path Selection · p. 3, 3) Priorities · p. 3

4) Frame Preemption:

  • Frame preemption lets an express frame interrupt a preemptable frame, but preemption cannot begin until 60 bytes have been transmitted and cannot affect the final 63 bytes.Fragments have a minimum size of 64 bytes, with a four-byte error-check sequence in all but the last fragment.Source: 4) Frame Preemption · pp. 3–4

5) Frame Replication and Elimination for Reliability (FRER):

6) Traffic Scheduling:

TSN scheduling coordinates periodic transmission times for time-triggered streams with bridge gate-control lists so streams meet real-time requirements. Schedules use a shared hyperperiod and must satisfy network and transmission constraints.

6) Traffic Scheduling:

  • TAS scheduling computes periodic TT transmission times and GCLs, whose entries specify gate states over time intervals.Each open gate permits its priority queue to send; GCLs execute periodically, and available GCL entries are limited by the bridge.Source: 6) Traffic Scheduling · p. 4

III. THE TSN SCHEDULING PROBLEM

  • The scheduling problem coordinates stream transmission times and bridge GCLs to meet every stream’s real-time requirements.The network model includes end stations, bridges, full-duplex links, and processing, propagation, and queuing delays.Source: 6) Traffic Scheduling · p. 5, A. Nomenclature · p. 5

A. Nomenclature

  • A schedule combines talker transmission offsets with bridge GCL configurations and repeats indefinitely over the streams’ hyperperiod.The hyperperiod is the least common multiple of stream periods; streams with shorter periods are represented by consecutive copies within it.Source: 6) Traffic Scheduling · p. 4, A. Nomenclature · p. 5

B. Scheduling Constraints

3) Deadlines:

A valid schedule must respect stream deadlines, routing, ordering, FIFO queues, and gate behavior. The literature also studies optimization objectives and extensions, including joint routing.

3) Deadlines:

  • All frames of a stream must reach every destination before its deadline, including for multicast streams.The payload must be delivered before the deadline; a stream may send its payload in multiple frames.Source: 3) Deadlines · p. 5

4) Routing

8) Gate Control

  • A queued frame can transmit only while its gate is open, and the gate must remain open through transmission; when several queues are open, the highest-priority waiting queue goes next.Scheduled frames must not be dropped, and additional problem variants may assign TT streams among multiple queues.Source: 8) Gate Control · p. 6, 9) Transmission Selection · p. 6, 7) Queue Size · p. 6

C. Finding a Schedule vs. Optimization

  • Optimization distinguishes among valid schedules by minimizing or maximizing an objective, such as end-to-end delay, jitter, or flowspan.Flowspan is the duration until all frames have arrived at their destinations.Source: C. Finding a Schedule vs. Optimization · p. 6

D. Computational Complexity

  • The decision problem of whether a valid schedule exists is NP-complete in general, including without queuing.The result follows because Bin Packing can be reduced to the scheduling problem.Source: D. Computational Complexity · p. 6

1) Joint Routing

  • Joint routing relaxes fixed routes by computing stream routes and schedules together, allowing streams to avoid heavily loaded links and scheduling conflicts.Algorithms may choose among provided paths or select arbitrary paths.Source: 1) Joint Routing · p. 6

2) Reliability:

Scheduling research extends the basic problem to reliability, GCL construction, queueing restrictions, traffic integration, dynamic reconfiguration, and multicast. These variants add distinct constraints or decisions to schedule synthesis.

2) Reliability:

  • Robust scheduling can account for modeled faults and their probabilities, for example by routing redundant streams over disjoint paths to withstand single-link failures.Robustness is defined relative to a fault model and concerns meeting stream requirements with high probability.Source: 2) Reliability · p. 6

3) GCL Synthesis:

  • GCLs may be synthesized after transmission offsets by opening gates for scheduled transmissions, or constructed jointly because hardware limits GCL entries.Leaving scheduled-traffic gates open throughout the hyperperiod prevents other queues from sending.Source: 3) GCL Synthesis · pp. 6–7

4) Queuing:

  • Queuing can make schedules vulnerable to missing frames: an unexpectedly early transmission may alter later arrival order and contribute to missed deadlines.Frame isolation avoids simultaneous queueing of different streams; no-wait scheduling disallows queueing altogether.Source: 4) Queuing · p. 7

5) Integration of Audio Video Bridging:

  • Integrating AVB streams adds them to the scheduling input and requires accounting for CBS behavior while TT and AVB streams share links.The traffic classes use different egress queues.Source: 5) Integration of Audio Video Bridging · p. 8

6) Integration of BE Traffic:

  • BE traffic is not scheduled, but schedules can favor it by avoiding large TT bursts or unnecessary GCL entries that require guard bands.Compact schedules maximize capacity for BE traffic.Source: 6) Integration of BE Traffic · p. 8

7) Dynamic Reconfiguration:

  • Adding streams during dynamic reconfiguration can require changing existing offsets and fitting new transmissions around occupied links and queues.In scenarios such as automotive use, reconfiguration may require very low runtime, while recomputing the entire schedule offline is computationally infeasible.Source: 7) Dynamic Reconfiguration · p. 8

8) Multicast:

  • Multicast scheduling must account for destination trees because each frame is transmitted only once per hop, rather than modeled as separate unicast copies.Joint-routing approaches compute trees instead of paths.Source: 8) Multicast · p. 8

9) Task Scheduling:

The survey distinguishes exact optimization techniques from heuristics and also notes joint scheduling of applications and streams. Exact methods seek feasible or optimal schedules; heuristics seek good solutions without optimality guarantees.

9) Task Scheduling:

  • Task scheduling can be combined with TSN scheduling by jointly scheduling periodic end-station applications and the streams that carry their data.Tasks can send TT streams after processing received data.Source: 9) Task Scheduling · p. 8

F. Optimization Methods

  • Exact approaches can find a schedule or establish infeasibility, whereas heuristics seek good solutions quickly without guaranteeing optimality or feasibility detection.Realistic instances often make finding optimal solutions infeasible, motivating heuristic use.Source: F. Optimization Methods · p. 8, 2) Heuristic Approaches · p. 9

1) Exact Approaches:

  • Exact TSN methods include ILP, SMT/OMT, constraint programming, and pseudo-Boolean optimization.ILP uses linear inequalities and may include an objective; SMT combines logical formulas with predicates from other theories, while OMT optimizes an objective.Source: 1) Exact Approaches · pp. 8–9

2) Heuristic Approaches:

  • GRASP repeatedly builds randomized greedy feasible solutions and applies local search, returning the best solution encountered.A problem-specific implementation needs procedures for constructing initial solutions and exploring local changes.Source: 2) Heuristic Approaches · p. 9
  • Tabu search moves among neighboring solutions while excluding moves or solutions on a tabu list to avoid cycles.It returns the best solution found after a specified number of moves.Source: 2) Heuristic Approaches · p. 9
  • Simulated annealing sometimes accepts worse neighboring solutions early, with that probability diminishing as temperature decreases.The approach aims to escape local optima and requires choices for the initial solution, neighborhood, temperature schedule, and acceptance criterion.Source: 2) Heuristic Approaches · p. 9
  • Genetic algorithms evolve a population through crossover, mutation, and fitness-based selection, while list scheduling orders streams by priority and places them when resources permit.ASAP scheduling is a list-scheduling special case that places streams one by one at the earliest possible time along their paths; machine learning is also identified as a heuristic approach.Source: 2) Heuristic Approaches · pp. 9–10

IV. LITERATURE SURVEY

This survey groups fixed-routing TT scheduling research by topic and reviews approaches for the unmodified scheduling problem. Reported methods range from incremental SMT and heuristics to genetic algorithms, with results spanning scalability, delay, and solving time.

1) Scheduling w/o Problem Extensions:

  • Steiner’s incremental SMT approach schedules streams one at a time, fixes earlier schedules, and uses backtracking when infeasibility arises; later TSN work adopted similar ideas,,.Under fixed routing, the scheduling algorithm cannot change a stream’s route to resolve conflicts.Source: 1) Scheduling w/o Problem Extensions · p. 11, A. Scheduling w/ Fixed Routing · p. 11
  • The window-based SMT approach in found schedules faster than the SMT model in with one window per egress port, while more windows significantly reduced average jitter.Its solving time increased exponentially with stream count and was more sensitive to the number of windows for reasonable instance sizes.Source: 1) Scheduling w/o Problem Extensions · p. 11
  • The two-stage approach for multi-layered rings scaled better than Tabu Search, ran two orders of magnitude faster in that topology, and significantly reduced needed GCL entries.It schedules within-ring streams first, then simulates the remaining streams together and accepts the simulated behavior if deadlines are met.Source: 1) Scheduling w/o Problem Extensions · pp. 11–12, Figure 9 · p. 11
  • The heuristic scheduled 1200 streams, compared with about 1000 for the ILP and about 300 for the SMT in the evaluation scenario.The heuristic derives possible transmission-offset ranges from frame conflicts.Source: 1) Scheduling w/o Problem Extensions · p. 12
  • End-to-end delays were reduced by up to one third per stream in the evaluation scenarios for the heuristic in.It orders streams by priority and assigns each frame to the earliest unoccupied hyperperiod interval along the stream’s path.Source: 1) Scheduling w/o Problem Extensions · p. 12
  • The genetic algorithm outperformed random schedules on weighted end-to-end delay, jitter, and bandwidth utilization in almost all scenarios, and beat on its objective [40].Genes encode frame-scheduling order; frames are scheduled as soon as possible along their stream paths, followed by schedule compression to reduce guard-band occupation.Source: 1) Scheduling w/o Problem Extensions · p. 12
  • The single-hop in-vehicle case in assumes continuous traffic across different classes and queues, so its authors caution that more complex real in-vehicle networks limit the insights.The approach essentially implements round-robin traffic shaping with TAS.Source: 1) Scheduling w/o Problem Extensions · p. 12
  • 10812 streams were scheduled in a 2000-node tree topology by Vlk et al.’s heuristic, which outperformed other approaches in schedulability and solving time.The evaluation also included a real-world avionics instance.Source: 1) Scheduling w/o Problem Extensions · p. 12

2) Research Work about Queuing:

The survey covers queuing extensions and scheduling that accounts for other traffic classes. Across these works, authors explore isolation, transmission windows, coexistence with CQF, and schedule objectives that trade TT requirements against lower-priority traffic performance.

2) Research Work about Queuing:

  • For queuing, flow isolation reduced solving time relative to frame isolation, but frame isolation allowed more instances to be scheduled; a modified queue that idles for an unexpected frame improved schedulability.The modified queue checks whether the next frame matches the schedule, avoiding the reduced solution space associated with isolation constraints.Source: 2) Research Work about Queuing · p. 12
  • A queuing heuristic using transmission windows dropped isolation constraints and used network calculus for worst-case latency analysis, reporting better end-to-end delay and schedulability than earlier work by the same authors.It minimizes the fraction of the hyperperiod reserved for TT traffic.Source: 2) Research Work about Queuing · pp. 12–13

3) Scheduling w/ Other Traffic:

  • Schedule compression reduced GCL entries by 24% on average in, with fewer guard bands noted as increasing available bandwidth for BE traffic.The approach uses an ILP or Tabu Search to compute no-wait schedules and minimizes flowspan to leave a large BE time slice.Source: 3) Scheduling w/ Other Traffic · p. 13, Figure 11 · p. 13
  • Maximizing gaps between consecutive TT transmissions increased BE QoS in, including less starvation and lower average latency, but its BE-deadline model prevents comparison with the other surveyed studies.The SMT solving time also depended heavily on the objective function.Source: 3) Scheduling w/ Other Traffic · p. 14, Figure 12 · p. 14
  • The TAS ensured TT real-time requirements while affecting lower-priority traffic less than strict priority in the in-vehicle simulation study.The study used typical in-vehicle traffic patterns and compared end-to-end delays.Source: 3) Scheduling w/ Other Traffic · p. 14
  • Barzegaran et al.’s CP approach outperformed algorithms [28],,, and in solving time, while its end-to-end delays and bandwidth utilization were significantly worse than and.It assumes not all end stations support TSN and uses worst-case delay analysis to eliminate solutions that may violate the instance’s real-time requirements.Source: 3) Scheduling w/ Other Traffic · p. 14
  • Joint scheduling of scheduled and rate-constrained streams with CQF resulted in higher schedulability than scheduling scheduled traffic alone.The streams are scheduled in least-laxity-first order.Source: 3) Scheduling w/ Other Traffic · p. 14
  • Earliest-deadline-first ordering improved schedulability when scheduling multiple traffic classes with TAS and CQF, while sorting by frame size or period reduced it considerably.The setting also includes uncritical periodic streams and best-effort traffic.Source: 3) Scheduling w/ Other Traffic · p. 14

4) Scheduling w/ Reliability:

The surveyed work extends scheduling to clock drift and frame loss, schedule updates, explicit GCL synthesis, and application-task timing. These approaches report trade-offs in robustness, schedulability, update behavior, GCL size, and solution time.

4) Scheduling w/ Reliability:

  • Higher allowed clock drift increased end-to-end latency, while maximizing the allowed drift produced a maximal robust schedule but increased solving time by an order of magnitude over a fixed maximum.Shorter out-of-sync detection timeouts were needed at higher drift rates, which also negatively affected the possible synchronization-tree diameter.Source: 4) Scheduling w/ Reliability · pp. 14–15, Figure 13 · p. 15
  • Increasing frame-loss probability led to more retransmissions and less bandwidth for BE traffic in.The approach selects repetitions per stream to trade reliability against network utilization and also considers AVB and BE traffic.Source: 4) Scheduling w/ Reliability · p. 15

5) Reconfiguration of Schedules:

  • Pang et al. proved their ILP constraints prevent conflicts during schedule updates, and evaluations on train and automotive networks found no frame loss or time overhead.The schedules are updated without additional update overhead.Source: 5) Reconfiguration of Schedules · p. 15
  • The incremental schedule-update algorithm in [73] was faster than its comparison algorithm but had poor schedulability at higher network utilization.The update heuristic omits frame loss during updates.Source: 5) Reconfiguration of Schedules · p. 15
  • The flexcurve-based reconfiguration algorithm had linear solving time up to 100 streams in the evaluation, while schedules from had lower flexibility and were less suitable for dynamic reconfiguration.It adds streams incrementally to favor subsequent reconfigurations.Source: 5) Reconfiguration of Schedules · pp. 15–16

6) GCL Synthesis:

  • Jin et al.’s GCL-limited heuristic was an order of magnitude faster than naïve heuristics and scheduled instances with up to 10000 streams, while their SMT model found no feasible schedule for 100 streams within two days.The SMT model minimizes the maximum number of GCL entries across egress ports and uses an incremental scheme after it proved difficult to solve directly.Source: 6) GCL Synthesis · p. 16

7) Task Scheduling:

  • The CP search strategies in both found optimal zero-jitter solutions for all presented test cases, while the heuristic was orders of magnitude faster.The model accounts for control-application characteristics and restricts queuing to frame isolation.Source: 7) Task Scheduling · p. 16
  • The control-application model in outperformed the extended model by up to a factor of two on the proposed quality measure and was validated for an automotive mobile robot in simulation and on real hardware.Its quality measure includes jitter and end-to-end delays of input and output streams, plus execution jitter.Source: 7) Task Scheduling · p. 16

8) Other Topics:

The surveyed work explores specialized scheduling topics and joint routing-and-scheduling methods, including fragmentation, reliability, traffic integration, and alternative search formulations. Results range from improved schedulability to scalability trade-offs, with some evaluations or claimed benefits left insufficiently motivated.

8) Other Topics:

  • Up to 50% higher schedulability is reported when message fragmentation is optimized, and the heuristics handle instances an order of magnitude larger than the SMT approach.Fragmentation lets a message use multiple frames; the optimization jointly chooses the split and schedule.Source: 8) Other Topics · p. 16
  • The GA for preemptive traffic outperforms automotive scheduling baselines in schedulability and reliability by using TSN queues for preemption.Reliability is the minimum across streams of the maximum retransmissions allowed without missing a deadline.Source: 8) Other Topics · pp. 16–17
  • Minimizing unusable resources jointly across Ethernet and 5G links matters: optimizing only one link type produces unsatisfying results for the other.The model targets Ethernet guard-band time and unused 5G bandwidth; 5G transmissions must fit predefined slots.Source: 8) Other Topics · p. 17
  • The network-cycle heuristic reports its highest schedulability when the cycle equals the greatest common divisor of stream periods.Stream periods are integer multiples of the cycle, and transmissions align to it.Source: 8) Other Topics · p. 17
  • The machine-learning partitioning approach is reported to underperform alternatives, but the survey says schedule computation does not clearly substantiate that comparison.The approach partitions streams into groups before scheduling.Source: 8) Other Topics · p. 17

1) Joint Scheduling and Routing w/o Problem Extensions:

  • Joint routing and scheduling can improve schedulability over fixed routing, while increasing solving time; more available paths can also make ILP instances harder.The ILP scalability study reports that stream count affects solving time more than topology size, though topologies with more paths tend to be harder.Source: 1) Joint Scheduling and Routing w/o… · p. 17
  • The conflict-graph method reduces scheduling to finding an independent set and shows runtime and memory advantages over ILPs, though its implementation is a proof of concept [102].Vertices represent schedules for individual streams; edges connect incompatible schedules.Source: 1) Joint Scheduling and Routing w/o… · p. 18, Figure 16 · p. 18
  • A routing-scheduling decomposition that retries routing after scheduling failure schedules the most instances among tested alternatives, while the SMT alternative takes multiple times longer on most instances.The decomposition adds constraints to exclude failed routings and repeats until a schedule is found or all routings fail.Source: 1) Joint Scheduling and Routing w/o… · pp. 18–19

2) Scheduling w/ Reliability:

Reliability-oriented scheduling research addresses link failures, frame loss, component faults, and redundant transmission. The approaches trade resource use, delays, costs, and solving time against reliability and repairability.

2) Scheduling w/ Reliability:

  • For single-link failures, schedules maximizing gaps between transmissions are easier to repair than schedules minimizing flowspan, even with three simultaneous failures.A fast heuristic is proposed to reschedule and reroute streams after a link failure.Source: 2) Scheduling w/ Reliability · p. 19
  • The topology-generation heuristic schedules all evaluated instances while considerably reducing topology costs against a replicated-network approach.It starts from a full mesh, selects bridges and links used by streams, and uses disjoint paths for redundant copies.Source: 2) Scheduling w/ Reliability · p. 19, Figure 18 · p. 19
  • For frame-loss reliability, schedulability at a given reliability level increases with more redundant copies, although path-loss probabilities are approximated in the SMT model.Unlike several related works, the model does not require link-disjoint paths.Source: 2) Scheduling w/ Reliability · p. 20
  • A network-coding scheme tolerates one lost frame using two data paths and a third XOR path, requiring 3/2 n transmissions rather than 2n with FRER.The third path carries XORed data that can reconstruct either lost frame.Source: 2) Scheduling w/ Reliability · p. 20
  • Decomposing messages into redundant copies reduces bridge costs by up to 23.55%, but higher ASIL requirements increase copies, congestion, and end-to-end delays.For the evaluated real-life automotive case, selected bridges cost one third as much as using only the highest-ASIL bridges.Source: 2) Scheduling w/ Reliability · p. 20
  • The SA approach finds feasible schedules for huge instances in reasonable time, but its costs reach up to three times CP costs and rise by up to ∼3.5 under reliability constraints.The cost measure includes latency, penalties for unscheduled streams, and penalties for overlapping paths.Source: 2) Scheduling w/ Reliability · p. 20

3) Scheduling w/ Other Traffic:

The surveyed approaches account for other traffic classes, multicast, and schedule reconfiguration in different ways. Their reported gains include improved AVB schedulability, faster multicast solving, and online or failure-triggered updates, each within stated model assumptions.

3) Scheduling w/ Other Traffic:

  • Considering AVB tardiness in the GRASP objective yields deadline-meeting AVB streams, whereas objectives that ignore AVB leave streams late.Load-balanced routing before scheduling further improves results and reduces runtime; AVB routing is fixed during scheduling.Source: 3) Scheduling w/ Other Traffic · pp. 20–21
  • Allowing frame preemption increases AVB schedulability but significantly increases heuristic runtime.The approach includes worst-case response-time analysis for preempted AVB streams.Source: 3) Scheduling w/ Other Traffic · p. 21
  • The time-slot heuristic outperforms three compared methods by multiple orders of magnitude in solving time and reports schedules for 4000 streams with 12 GCL entries per egress port on average.The comparison inspects solving time only; the methods have no objective functions.Source: 3) Scheduling w/ Other Traffic · p. 21

4) Multicast:

  • For multicast joint routing and scheduling, preprocessing reduces feasible-solution time by up to 82.4% and overall solving time by up to 47.6%.The extension requires additional routing constraints, unlike multicast extensions to pure scheduling models.Source: 4) Multicast · p. 21
  • Spectral clustering and incremental multicast scheduling report reduced overall solving times and increased schedulability, while random clustering yields slightly longer flowspans.Previously computed routes and schedules are fixed as stream groups are processed.Source: 4) Multicast · p. 21

5) Reconfiguration:

  • For online rescheduling after VM migration, a precomputed multicast tree raises schedulability over KMB routing, while its routing objective is only slightly above the ILP optimum.The tree minimizes the maximum distance from any possible VM device to any destination.Source: 5) Reconfiguration · p. 22
  • For permanent end-station failures, a heuristic reconfigures almost all evaluated instances and is two orders of magnitude faster than the ILP.Both approaches have exponential runtime in stream count; the heuristic fixes routing and mapping before the ILP schedules.Source: 5) Reconfiguration · p. 22

6) Other Topics:

This section surveys additional scheduling methods and compares modeling assumptions, objectives, evaluation instances, and scalability. The comparison highlights limited treatment of other traffic classes and divergent queuing assumptions across the literature.

6) Other Topics:

  • Allowing more preemptions increases schedulability only up to an instance-specific threshold, while scheduling time also rises with streams, network size, preemptions, and retransmissions.The approach combines SMT scheduling and routing in an incremental scheme.Source: 6) Other Topics · p. 22
  • The GRASP topology-generation heuristic finds better solutions in minutes than the CP approach does in two days, while CP does not scale well.The objective includes worst-case end-to-end delays and topology costs, with redundant stream copies for reliability.Source: 6) Other Topics · p. 22
  • Joint routing and scheduling can raise schedulability but may approach a 40-hour timeout even on fairly small instances.The SMT model also assigns queues and seeks to reduce the number of bridges used by scheduled traffic.Source: 6) Other Topics · p. 22
  • Three precomputed paths per node pair may retain over 90% schedulability while considerably reducing search space in the incremental control-application approach [133].The number of allowed paths has a large impact on solving time.Source: 6) Other Topics · p. 22
  • Input preprocessing can greatly benefit solving time, but model-generation optimizations and solver configurations have negligible effects or can increase it; these findings concern no-wait models without queuing.The survey notes that transfer to other problem extensions is unclear.Source: 6) Other Topics · p. 23

2) Queuing:

  • Queuing assumptions range from no queuing to unrestricted queuing; frame-isolation constraints can reduce schedulability, but reported results use a modified TAS not applicable to current implementations.Some works instead analyze worst-case end-to-end delay to meet deadlines under non-determinism.Source: 2) Queuing · p. 23

3) Fixed GCL Length:

The survey examines how TSN scheduling research handles fixed GCL limits and related extensions, including reconfiguration, reliability, multicast, and task scheduling. It also categorizes optimization objectives, noting that many approaches seek only a feasible schedule.

3) Fixed GCL Length:

  • Postprocessing GCLs after scheduling can produce schedules that exceed bridge entry limits and cannot model guard-band considerations.Exceptions explicitly limit GCL entries or represent them in the scheduling model; no-wait schedules can use a fixed number of entries by opening TT gates for the hyperperiod.Source: 3) Fixed GCL Length · pp. 23–24

4) Reconfiguration:

  • Reconfiguration work addresses adding streams, deploying updates without frame loss or interference, and adapting schedules after endpoint migration or failure.Other approaches seek flexible schedules for future updates or align transmissions to the greatest common divisor to facilitate later additions.Source: 4) Reconfiguration · pp. 24–25

5) Reliability:

  • Reliability approaches cover frame loss, permanent link failures, clock drift, hardware faults, and lost-frame recovery through retransmission, redundancy, rerouting, or encoding.Schedules may reserve time for retransmissions or use redundant copies; permanent link failures are handled either with preplanned disjoint paths or rescheduling after failure.Source: 5) Reliability · pp. 25–26

6) Multicast:

  • Multicast can be represented as multiple unicast streams, but this increases problem size; efficient approaches often schedule one frame per link in the multicast tree.Other work studies joint multicast routing and scheduling or supports multicast for virtual-machine migration.Source: 6) Multicast · p. 26

7) Task Scheduling:

  • Only a few works jointly schedule streams and tasks, including models with stream-to-task dependencies and work considering safety and security for tasks producing TT streams.The survey identifies,,, and for dependencies, and and for safety and security considerations.Source: 7) Task Scheduling · p. 26

B. Scheduling Objective

  • Scheduling objectives measure solution quality; common categories include latency and jitter, queue use, other-traffic effects, routing, topology, reliability, and GCL synthesis.The survey also identifies problem-specific objectives that are not directly comparable across works.Source: B. Scheduling Objective · p. 27

1) No Objective:

  • Many approaches, including many SMT models, seek any feasible schedule without an optimization objective.The survey notes that SMT solvers were not originally designed for optimization, unlike ILP solving.Source: 1) No Objective · p. 27

2) Latency and Jitter:

The survey organizes scheduling objectives around stream performance, resource use, and effects on other traffic, then describes the problem instances used to evaluate approaches. Objectives and evaluation settings vary widely across the literature.

2) Latency and Jitter:

  • Latency and jitter are common objectives: works minimize per-stream jitter, flowspan, end-to-end delay, transmission offsets, or combinations of these measures.The survey notes that the objectives are not competing in the way objectives in most multi-criterion problems are.Source: 2) Latency and Jitter · p. 27

3) Queuing:

  • Where queue isolation is modeled, some works minimize the number of queues reserved for TT streams, leaving remaining egress queues available for other traffic.Queue assignment per egress port is a decision variable in these approaches.Source: 3) Queuing · p. 27

4) Other Traffic:

  • Other-traffic objectives include reducing AVB tardiness, scheduling more AVB streams, balancing CQF slots, and leaving transmission windows available for non-TT traffic.Additional approaches seek to reduce scheduled traffic's impact on other classes or use frame grouping and transmission gaps to improve BE traffic QoS.Source: 4) Other Traffic · p. 27

5) Routing:

  • Joint routing and scheduling objectives commonly minimize path length, sometimes alongside end-to-end latency, flowspan, link use, or scheduling conflicts.Some approaches also maximize the number of streams routed and scheduled or account for source migration in multicast trees.Source: 5) Routing · p. 27

6) Topology Synthesis:

  • Topology-synthesis objectives include bridge costs, routing and scheduling costs, and the number of bridges needed to route and schedule all streams.Some formulations also account for vendor diversity or maximize utilization while minimizing bridge count.Source: 6) Topology Synthesis · pp. 27–28

7) Reliability:

  • Reliability objectives maximize schedule slack for repair, tolerated clock drift, or retransmissions that can occur without missing deadlines.Source: 7) Reliability · p. 28

8) GCL Synthesis:

  • GCL synthesis objectives include minimizing gate-entry count, which can reduce guard bands, while the motivation for minimizing schedule duration is unclear to the survey authors.Source: 8) GCL Synthesis · p. 28

9) Others; C. Problem Instances

  • Other objectives target problem-specific goals, while evaluations use synthetic and real-world topologies and vary substantially in stream counts and traffic parameters.Synthetic cases use randomly generated streams; reported instance sizes range from 2 to 10,812 streams, periods from 32 μs to 500 ms, and port rates of 100 Mb/s or 1 Gb/s.Source: 9) Others · p. 28, C. Problem Instances · p. 29

D. Scalability

The survey finds that heuristic approaches generally handle larger scheduling instances than exact methods, while exact joint routing and scheduling is constrained by network size. It traces the field's growth and identifies evaluation gaps, including limited realistic benchmarks and incomplete reporting.

D. Scalability

  • Heuristics handle larger instances than exact methods: reported heuristics exceed 10,000 streams, while exact approaches typically handle fewer than 100, with notable incremental-method exceptions.Incremental approaches with backtracking reached 1,000 streams, later incremental work reached 2,000, and a transmission-window approach reported 750.Source: D. Scalability · p. 30
  • Exact joint routing and scheduling typically evaluates networks with fewer than 50 nodes, though some approaches reach 96 nodes; fixed-routing evaluations are generally below 96 nodes.The survey attributes the smaller joint-routing instances to growth in possible paths per stream; stream-count ranges are approximately similar across fixed- and joint-routing work.Source: D. Scalability · p. 30

A. Seminal Works

  • Early influential work preceded TSN-specific scheduling papers in 2016, which introduced no-wait scheduling, guard-band concerns, isolation, incremental scheduling, reliability, reconfiguration, and joint GCL computation.Earlier work computed GCLs as postprocessing after scheduling.Source: A. Seminal Works · p. 31

B. Published Papers

  • TSN scheduling papers began appearing in 2016 and grew almost monotonously year to year, with one exception in 2019 and a significant increase since 2020.The paper's publication-count figure includes works published before June 2022.Source: Figure 19 · p. 31, B. Published Papers · p. 31

A. Suggestions for Improvement

  • The survey recommends stronger evaluation methodology and use of Ethernet-bridging terminology to improve presentation in future TSN scheduling research.Source: A. Suggestions for Improvement · p. 32

1) Evaluation Methodologies:

  • Although scalability is widely evaluated, solution quality, realistic industry-scale suitability, and shared benchmarks remain limited; incomplete instance descriptions and single-instance results also hinder assessment.Timeout-based schedulability comparisons can be biased when approaches support different features, because a timeout does not prove infeasibility.Source: 1) Evaluation Methodologies · p. 32

2) Terminology:

The survey uses precise Ethernet-bridging terminology while mapping TSN/TAS scheduling research. It identifies unresolved extensions and complexity questions that limit comprehensive, scalable scheduling.

2) Terminology:

  • The survey recommends “stream,” “talker,” “listener,” “bridge,” “frame,” and “path selection” as consistent Ethernet-bridging terms, retaining “routing” when matching reviewed work.The paper notes that “packet” is technically incorrect for this Layer 2 technology.Source: 2) Terminology · p. 32

1) Impact of Guard Bands and GCL Entries:

  • Despite comprehensive work on the unmodified problem, guard-band and GCL-entry effects on lower-priority bandwidth remain underexplored, as does unified AVB/BE integration.Schedules with many gaps between TT streams may benefit AVB tardiness, but can require more gate closings and guard bands, reducing available bandwidth.Source: 1) Impact of Guard Bands and GCL Entries · p. 32, B. Open Problems · p. 32

2) Routing and Multicast:

  • Joint routing can improve schedulability, but is significantly harder than scheduling with fixed routes; no exact scalable approach or clear routing properties are known.The survey also finds insufficient evaluation and insight into integrating multicast streams into schedules.Source: 2) Routing and Multicast · p. 32

3) Online Reconfiguration:

  • Online reconfiguration remains sparsely studied, including efficient schedule properties for runtime stream changes and algorithms for most problem extensions.Insertion and removal of streams during execution can matter in settings such as automotive networks.Source: 3) Online Reconfiguration · p. 32

4) Queuing and Handling of Non-Determinism:

  • Most surveyed work isolates streams in queues and assumes deterministic bridges, leaving unrestricted queuing benefits and real-hardware nondeterminism unevaluated.Real bridges can exhibit processing-delay jitter, imperfect clock synchronization, and race conditions between frames arriving at different ingress ports.Source: 4) Queuing and Handling of… · p. 33

5) Support of PSFP:

  • PSFP filtering entries must be derived from schedules, but their limited availability in bridges may require joint configuration with scheduling.The survey reports that no devices then implemented PSFP.Source: 5) Support of PSFP · p. 33

6) Use of TSN Mechanisms:

  • Combining TSN mechanisms requires assigning streams to mechanisms and producing network configuration, a broader problem that can impose constraints on scheduling.The survey describes this comprehensive approach as currently unreachable given the difficulty of computing TAS gate-control lists.Source: 6) Use of TSN Mechanisms · p. 33

VIII. CONCLUSION

  • The survey classifies and compares work by assumptions, objectives, instances, and scalability, and calls for better complexity insight to support broader extensions at acceptable scale.It notes that schedule properties and the effects of extensions on schedule structure remain insufficiently understood, while efficient algorithms covering all relevant aspects appear infeasible.Source: §VIII · p. 33, 7) Understanding of the TSN Problem · p. 33
Loading 2211.10954v2…