|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.
|Abteilung(en)||Universität Stuttgart, Institut für Parallele und Verteilte Systeme, Verteilte Systeme|
|Betreuer||Rothermel, Prof. Kurt; Hellmanns, David|
|Eingabedatum||1. März 2021|