Algorithms for calculating robust schedules for time sensitive networking (TSN)

Abstract

With the 802.1Qbv standard, the time-sensitive networking (TSN) task group has specified a TDMA-based scheduling method based on Ethernet, that allows to ensure real-time guarantees for time-critical data streams. A major challenge here is the computation of the cyclic schedules required for the switch configurations in the network. There exist already a number of different approaches to calculate these schedules. However, most of them focus on supporting a high number of streams and optimize target functions such as the Makespan. This leads to schedules that are particularly fragile against errors in the system model. To close this gap, we have developed a scheduler based on simple temporal networks (STNs) that maximizes the intervals allocated for the transmission of data packets in order to ensure a very high degree of robustness against unforeseen delay or cross-traffic. In a simulation it could be shown that the calculated schedules could still guarantee a loss-free data transmission under compliance with all deadlines if the actual per-hop network delay deviated from the assumed delay by a factor of up to 7. Furthermore, an even larger error did not immediately lead to a breakdown, but to a gradual degradation. This makes the scheduling method presented here as well as the underlying algorithms particularly interesting for applications that come with a high degree of uncertainty in the system model, such as wireless communications or heterogeneous networks.

Die time-sensitive Networking (TSN) task group hat mit dem 802.1Qbv Standard einen TDMA basierten Schedulingverfahren auf der Basis von Ethernet spezifziert, mit welchem Echtzeitgarantieren für zeitkritische Datenströme garantiert werden können. Eine große Herausforderung ist hierbei die Berechnung der zyklischen Schedules welche für die Switch Konfigurationen im Netzwerk benötigt werden. Es gibt bereits eine Reihe verschiedener Ansätze um diese Schedules zu berechnen. Die meisten fokusieren sich aber darauf Schedules für eine möglichst hohe Anzahl an Streams zu berechnen und optimieren hierzu Zielfunktionen wie z.B. den Makespan. Das führt dazu, das die Schedules besonders fragil gegenüber Fehler im Systemmodell sind. Um diese Lücke zu schließen haben wir auf Basis von Simple Temporal Networks (STNs) einen Scheduler entwickelt welcher die allokierten Zeitbänder für Datenpakete auf sinnvolle Weise maximiert um eine möglichst hohe Robustheit gegenüber unvorhergesehenem Delay oder Cross-Traffic zu gewährleisten. In einer Simulation konnten gezeigt werden, das die berechneten Schedules auch weiterhin eine verlustfreie Datenübertragung unter Einhaltung aller Deadline gewährleisten konnten wenn der tatsächliche per-Hop Netzwerkdelay um bis zum Faktor 7 vom angenommenen Delay abwich. Darüber hinaus führte ein noch größerer Fehler nicht sofort zu einem Zusammenbruch, sondern einer allmählich kontinuierlichen Verschlechtung. Das macht das hier vorgestellte Schedulingverfahren und die darunterliegenden Algorithmen besonders interessant für Anwendungen in welchen eine hohe Unsicherheit im Systemmodell herscht wie z.B. bei drahtloser Kommunikation oder innerhalb heterogener Netzwerke.