ILP-based schedule planning for dynamic IEEE time-sensitive networks

Abstract

Time-Sensitive Networking (TSN) denotes a set of IEEE standards that amend Ethernet by realtime capabilities. Specifically, the Time-Aware Shaper (TAS) implements a time division multiple access (TDMA) scheme allowing to temporally isolate time-sensitive traffic. In order to deploy a TSN network configuration providing hard bounds on delay and jitter, synchronized clocks and a global transmission schedule are required. However, the calculation of such a global schedule is not part of the TSN standard. Most scheduling approaches proposed in the literature target static scenarios where the network topology and the flow set are known a priori. Novel use cases encountered in Industry 4.0 have more dynamic requirements, such as connecting further machines or enabling new features that result in additional flows that need to be admitted into the schedule. Dynamic TSN scheduling poses challenges not only in adding new flows to an existing schedule, but also for initial offline scheduling, as each placement of flows in the original schedule may decrease future schedulability. In our work, we define an Integer Linear Programming (ILP) model that supports incrementally adding new flows to an existing schedule, taking original flow placements into account. It supports both defensive scheduling, where existing flows are not temporally moved, as well as offensive scheduling, in which existing flows may be rescheduled by a limited amount configurable per flow. We propose two optimization objectives aiming to improve schedulability of future flows. The first objective max-freeblock schedules flows in a way that increases the unoccupied time at the end of each schedule cycle time, leaving space to place future flows in defensive scheduling scenarios. The second objective link-desync maximizes the unoccupied gap between every two consecutive flows of a link, creating flexibility for future offensive scheduling. Further, we propose a heuristic-based algorithm that strategically selects a reduced set of initial flows for rescheduling based on link occupancy, reducing the model size and decreasing the execution time necessary to place additional flows. Our evaluations show that our max-freeblock strategy outperforms the baseline min-flowspan objective in defensive scheduling. Utilizing our rescheduling selection algorithm, 97 % of additional flows were admitted in offensive scheduling scenarios, compared to only 72 % achieved without restricting the rescheduling flow set.

Time-Sensitive Networking (TSN) umfasst mehrere IEEE Standards, die den Ethernet-Standard um Echtzeitfähigkeiten erweitern. Der darin beschriebene Time-Aware Shaper (TAS) implementiert ein Time Division Multiple Access (TDMA) Verfahren um zeitkritischen Datenverkehr zeitlich zu isolieren. TSN-basierte Netzwerke können nur dann Echtzeiteigenschaften wie Delay und Jitter garantieren, wenn alle beteiligten Geräte zeitsynchronisiert sind und einem globalen Schedule (Zeitplan) folgen. Die Berechnung eines solchen Schedule bleibt im Standard explizit offen. Die meisten in der Forschung diskutierten Berechnungsverfahren beziehen sich auf statische Szenarien, in denen die Netzwerktopologie und alle Flowspezifikationen im Voraus bekannt sind. Moderne Anwendungsfälle z.B. in der Industrie 4.0 haben wechselnde Anforderungen an zeitkritische Netzwerke, beispielsweise das Hinzufügen weiterer Geräte oder aktivieren zusätzlicher zeitkritischer Funktionen im laufenden Betrieb. Dynamisches TSN Scheduling stellt nicht nur in Bezug auf das Hinzufügen von Flows im laufenden Betrieb eine Herausforderung dar, sondern betrifft auch das initiale Scheduling, da die Platzierung von Flows die Platzierbarkeit von künftigen Flows beeinträchtigt. In dieser Arbeit wird ein Integer-Linear-Programming-Modell (ILP) formuliert, mit dem neue Flows in einen bestehenden TSN-Schedule unter Beachtung der existierenden Restriktionen eingefügt werden können. Das Modell unterstützt sowohl defensives Scheduling, bei dem bestehende Flows nicht verschoben werden dürfen, als auch offensives Scheduling, welches das Verschieben bestehender Flows bis zu einem pro Flow definierten Limit ermöglicht. Weiter enthält das Modell zwei Strategien in Form von Optimierungszielen, um die Platzierbarkeit von künftigen Flows zu verbessern. Das erste Optimierungsziel, max-freeblock, platziert Flows so innerhalb des Schedules, dass bei jedem Link ein großer freier Bereich zeitlich am Ende des Schedules entsteht, um Platz für die freie Platzierung weiterer Flows freizuhalten. Das zweite Optimierungsziel, link-desync, maximiert paarweise den Abstand zwischen allen Flows, die über einen Link geroutet werden und schafft somit Lücken zwischen aufeinanderfolgenden Flows. Die Lücken bieten Flexibilität um sowohl neue Flows direkt darin zu platzieren, als auch um durch geringe Verschiebungen an geschickten Stellen Platz für neue Flows zu schaffen. Weiterhin wurde ein heuristikbasierter Algorithmus implementiert, der basierend auf den Linkbelegungen strategisch eine reduzierte Menge bestehender Flows auswählt, bei denen eine zeitliche Verschiebung erlaubt wird. Die Einschränkung der Verschiebbarkeit auf diese Teilmenge reduziert die Größe der Probleminstanz und damit die benötigte Laufzeit um zusätzliche Flows im Schedule zu platzieren. Evaluationen der Ansätze zeigen, dass die max-freeblock-Strategie bessere Ergebnisse im defensiven Scheduling erzielt als die Vergleichsstrategie min-flowspan aus der Literatur. Durch den Verschiebbarkeitsalgorithmus können bei offensivem Scheduling durchschnittlich 97 % der zusätzlichen Flows platziert werden, während ohne Einschränkung der Verschiebbarkeit nur 72 % der Flows aufgenommen werden können.