Scheduling with uncertainty for Time-Sensitive Networking using robust optimization techniques and integer linear programming

Abstract

Application services depend on the network to guarantee reliability, which is critical for safety and correct operation. Time-Sensitive Networking is a technology for reliable real-time communication of time-sensitive applications. While many schedulers exist that provide reliability for wired Time-Sensitive Networks (TSN) with the assumption of deterministic packet delays, scheduling for wireless TSN with uncertain packet delays has received significantly less attention. This work leverages the methodology of Robust Optimization (RO) to propose a robust scheduling approach that ensures provable reliability for both wired and wireless TSN. An uncertainty set defines the range of possible values, ensuring that the schedule remains feasible under all possible realizations within this set. As uncertainty sets are a key component in RO, we introduce methods to compute boxed and polytope uncertainty sets containing possible packet delays based on a set of given reliability requirements. A scheduler is deemed robust if it satisfies the given reliability constraints for all possible packet delays within the computed uncertainty set. Although robustness can be achieved through strict isolation and conservative filtering of packets, we demonstrate that several limitations prevent known robust schedulers from fully exploiting arbitrary uncertainty set shapes. As certain problem instances are unsolvable using simple boxed uncertainty sets, we indicate the need for schedulers that can utilize complex shapes of uncertainty sets rather than boxes. In response to this challenge, we introduce Uncertain No-Wait Packet Scheduling (UNWPS), a scheduler capable of computing robust schedules, and prove that UNWPS is robust against arbitrary upper-bounded boxed and polytope uncertainty sets. We assess the influence of uncertainty sets on the quality of the resulting UNWPS schedules, compare their performances to the performance of other robust scheduling approaches across various exemplary TSN networks and message stream configurations and carry out simulations conducted using the DetCom simulation framework to validate the robustness of UNWPS empirically. Anwendungsdienste können Sicherheit und den ordnungsgemäßen Betrieb nur dann garantieren, wenn das Netzwerk eine gewisse Zuverlässigkeit gewährleisten kann. TSN ist eine Technologie, die zuverlässige Echtzeitkommunikation in zeitkritischen Anwendungen ermöglicht. Während viele Ansätze zur Planung (Scheduler) existieren, die Zuverlässigkeit für kabelgebundene TSN-Netzwerke mit der Annahme von deterministischen Übertragungsdauern garantieren, hat die Planung für drahtlose TSN-Netzwerke, bei denen die Übertragungsdauern ungewiss sind, deutlich weniger Aufmerksamkeit erhalten. Diese Arbeit nutzt die Methodik der Robusten Optimierung (RO), um einen robusten Planungsansatz vorzuschlagen, der nachweisbare Zuverlässigkeit für sowohl kabelgebundene als auch drahtlose TSN-Netzwerke gewährleistet. Eine Unsicherheitsmenge definiert einen Bereich möglicher Werte und stellt sicher, dass ein Zeitplan unter allen möglichen Realisierungen innerhalb dieser Menge realisierbar bleibt. Da Unsicherheitsmengen ein zentrales Element in der robusten Optimierung sind, stellen wir Methoden zur Berechnung von würfelförmigen und polytopförmigen Unsicherheitsmengen vor, die mögliche Übertragungsdauern auf der Grundlage einer Menge gegebener Zuverlässigkeitsanforderungen enthalten. Ein Scheduler gilt als robust, wenn er die angegebenen Zuverlässigkeitsanforderungen für alle möglichen Übertragungsdauern innerhalb der berechneten Unsicherheitsmenge erfüllt. Obwohl Robustheit durch strikte Isolation und konservatives Filtern von Paketen erreicht werden kann, zeigen wir Limitierungen auf, welche verhindern, dass bekannte robuste Scheduler willkürliche Formen von Unsicherheitsmengen vollständig ausnutzen können. Da bestimmte Problemstellungen mit einfachen würfelförmigen Unsicherheitsmengen nicht lösbar sind, weisen wir ebenfalls auf die Notwendigkeit von Scheduler hin, die komplexe Formen von Unsicherheitsmengen nutzen können. Als mögliche Lösung auf diese Problemstellung stellen wir UNWPS als Scheduler vor und beweisen, dass UNWPS robust gegenüber würfelförmigen und polytopförmigen Unsicherheitsmengen mit beliebigen Obergrenzen ist. Wir evaluieren den Einfluss von Unsicherheitsmengen auf die Qualität der resultierenden UNWPS-Zeitpläne, vergleichen die Performanz von UNWPS-Zeitplänen mit der Performanz von Zeitplänen von anderen robusten Scheduler mithilfe verschiedener beispielhafter TSN-Netzwerke und Nachrichtenstromkonfigurationen und validieren die Robustheit von UNWPS empirisch durch Simulationen auf Basis des DetCom-Simulationsrahmens.