Bachelorarbeit BCLR-2020-66

Haug, Lucas: Optimizing ILP-based joint scheduling and routing for time-aware shaping in factory automation networks.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 66 (2020).
83 Seiten, englisch.

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.

Volltext und
andere Links
Abteilung(en)Universität Stuttgart, Institut für Parallele und Verteilte Systeme, Verteilte Systeme
BetreuerRothermel, Prof. Kurt; Hellmanns, David
Eingabedatum1. März 2021
   Publ. Informatik