Optimizing ILP-based joint scheduling and routing for time-aware shaping in factory automation networks

Abstract

With the rise of Industry 4.0 and Internet of Things (IoT), the need for deterministic real-time communication is higher than ever before. In the past, fieldbus systems have dominated the field of time-critical applications. However, they are incompatible among each other and are not able to transmit time-sensitive and non-time-sensitive traffic over the same medium. The widespread usage of IEEE Ethernet Networks and the growing need for real-time communication lead to the IEEE Time-sensitive Networking (TSN) Standards. These TSN Standards extend IEEE Ethernet networks with real-time capabilities. They provide multiple priority levels and a Time Division Multiple Access (TDMA)-based gating mechanism for each switch. However, they do not define how to calculate the TDMA schedules. There are already different approaches, which solve the Scheduling- or the Joint Routing and Scheduling (JRaS) problem for TSN. These approaches are either complete and suffer from a high runtime or they are heuristic and do not guarantee to find a feasible solution. In this work, we improve upon an already existing Integer Linear Programming (ILP)-based JRaS approach. For this, we develop different optimizations of different categories, which reduce the complexity of the problem or make use of an ILP-solver's specific capabilities. We evaluate our different optimizations individually and in combination in order to find the best combination for two different switching types. These switching types are known as Store-and-Forward switching, which is the default switching type provided in the IEEE Ethernet standards and Cut-Through switching, which is an optimization commonly used in industrial networks. Additionally, we benchmark our optimized ILP-based approach against other schedulers. With our best optimization combination, we are able to reduce the runtime by about 80% compared to the base ILP-model.

Mit dem Aufschwung von Industrie 4.0 und Internet of Things (IoT) ist der Bedarf an deterministischer Echtzeitkommunikation höher als je zuvor. In der Vergangenheit haben Feldbussysteme den Bereich der zeitkritischen Anwendungen weitgehend geprägt. Sie sind jedoch untereinander inkompatibel und nicht in der Lage, zeitkritischen und nicht zeitkritischen Verkehr über dasselbe Medium zu übertragen. Die weit verbreitete Verwendung von IEEE-Ethernet-Netzwerken und der wachsende Bedarf an Echtzeit-Kommunikation führten zu den IEEE Time-sentivie Networking (TSN) Standards. Diese TSN Standards erweitern IEEE-Ethernet-Netzwerke um Echtzeitfähigkeiten. Sie bieten mehrere Prioritätsstufen und einen auf Zeitmultiplexing (engl. Time Division Multiple Access, TDMA) basierenden Gating-Mechanismus für jeden Switch. Sie definieren jedoch nicht, wie die TDMA-Schedules zu berechnen sind. Es gibt bereits verschiedene Ansätze, die das Scheduling- oder das Joint Routing and Scheduling (JRaS) Problem für TSN lösen. Diese Ansätze sind entweder vollständig und leiden unter einer hohen Laufzeit oder sie sind heuristisch und garantieren nicht, eine gültige Lösung zu finden. In dieser Arbeit verbessern wir einen bereits bestehenden Integer Linear Programming (ILP)-basierten JRaS-Ansatz. Dazu entwickeln wir verschiedene Arten von Optimierungen, die die Komplexität des Problems reduzieren oder die spezifischen Fähigkeiten eines ILP-Lösers nutzen. Wir evaluieren unsere verschiedenen Optimierungen einzeln und in Kombination, um die beste Kombination für zwei verschiedene Switching-Typen zu finden. Diese Switching-Typen sind bekannt als Store-and-Forward, der Standard-Switching-Typ, der in den IEEE-Ethernet-Standards vorgesehen ist, und als Cut-Through-Switching, eine Optimierung, die häufig in industriellen Netzwerken verwendet wird. Zusätzlich vergleichen wir unseren optimierten ILP-basierten Ansatz mit anderen Schedulern. Mit unserer besten Optimierungskombination sind wir in der Lage, die Laufzeit um etwa 80% im Vergleich zum ILP-Basismodell zu reduzieren.