Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-12273
Authors: Glavackij, Alexander
Title: Tracing-based scheduling of isochronous traffic in time-sensitive networks
Issue Date: 2020
metadata.ubs.publikation.typ: Abschlussarbeit (Bachelor)
metadata.ubs.publikation.seiten: 77
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-122901
http://elib.uni-stuttgart.de/handle/11682/12290
http://dx.doi.org/10.18419/opus-12273
Abstract: Time-Sensitive Networking (TSN) is a set of standards defined by the IEEE 802.1 TSN Task Group and aims at making IEEE 802.3 Ethernet real-time capable. TSN employs a Time Division Multiple Access (TDMA) scheme to achieve temporal isolation between data streams, and thus, provides bounds on worst-case latencies and real-time guarantees. The TDMA scheme divides access to transmission links into slots. Calculating the slots of the TDMA scheme is referred to as scheduling. Scheduling is known to be NP-complete. Current approaches are mainly based on constraint programming and optimization problems, and thus, do not scale well for large problem instances. In previous work Scaling TSN Scheduling for Factory Automation Networks [HGF+20], Hellmanns et al. developed a novel fast scheduling approach to schedule data streams in a TSN network. It significantly outperformed current approaches in execution time. They use a discrete-event network simulator to simulate stream transmissions and to derive a schedule from the simulation results, sacrificing the optimality of the schedule for calculation speed. The authors refer to this approach as tracing-based scheduling. We expand the tracing-based scheduling approach to a full-blown scheduling algorithm. To do that, we propose a novel formulation of the scheduling problem: scheduling as a search problem. Using this formulation, we develop four novel scheduling approaches: Tracing-based Scheduling (TBS) Naive approach, TBS Link Time Remaining Time, TBS Link Time Late Streams, and TBS Link Time Monte Carlo Tree Search (MCTS). We evaluate each approach along the following properties: execution rates, scheduling runtimes, and scheduling capabilities. The MCTS approach exhibits the best performance. It outperforms two contemporary schedulers and can schedule the majority of problem instances in under 1200 s.
Time-Sensitive Networking (TSN) ist eine Sammlung von Standards, die von der IEEE 802.1 TSN Task Group definiert wurde und IEEE 802.3 Ethernet echtzeitfähig macht. TSN benutzt ein Zeitmultiplexverfahren (TDMA) um Datenverkehr zu isolieren und somit Echtzeit Garantien geben zu können. Das TDMA Verfahren unterteilt den Zugang zu Übertragungsverbindungen in Zeitschlitze. Die Berechnung dieser Zeitschlitze wird im sogenannten Scheduling durchgeführt. Das Scheduling ist NP-vollständig. Aktuelle Ansätze basieren auf Constraint Programmierung und Optimierungsproblemen und skalieren daher nicht für größere Problem Instanzen. In einer vorausgegangenen Arbeit Scaling TSN Scheduling for Factory Automation Networks [HGF+20] entwickelten Hellmanns et al. ein neues Scheduling Verfahren. Das Verfahren benutzt eine diskrete Ereignissimulation um Datenverkehr zu simulieren. Der Schedule wird von den Simulationsergebnissen abgeleitet. Diese Vorgehensweise beschleunigt die Berechnung, der berechnete Schedule ist jedoch nicht zwangsläufig optimal. Die Autoren nennen dieses Verfahren tracing-based scheduling. Wir erweitern das tracing-based scheduling zu einem vollständigen Scheduling Algorithmus. Dafür schlagen wir eine neue Formulierung des Scheduling Problems vor: Scheduling als Suchproblem. Mit unserer Formulierung entwickeln wir vier neue Scheduling Algorithmen: Tracing-based Scheduling (TBS) Naive; TBS Link Time Remaining Time; TBS Link Time Late Streams and TBS Link Time Monte Carlo Tree Search (MCTS). Der MCTS Ansatz zeigt die besten Scheduling Fähigkeiten und ist in der Lage, die meisten Problem Instanzen in unter 1200 s zu lösen.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
main-english.pdf3,13 MBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.