Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-11699
Authors: Schneefuss, Patrick
Title: Desychronization algorithms for fast ILP solutions of TDMA schedules in IEEE Time-Sensitive Networks
Issue Date: 2021
metadata.ubs.publikation.typ: Abschlussarbeit (Master)
metadata.ubs.publikation.seiten: 95
URI: http://elib.uni-stuttgart.de/handle/11682/11716
http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-117165
http://dx.doi.org/10.18419/opus-11699
Abstract: Time-Sensitive Networking (TSN) is extending standard IEEE 802.3 Ethernet with deterministic real-time capabilities, which are essential for many networked real-time systems. It does so by implementing a time-division multiple access (TDMA) scheme. To operate correctly, this requires the presence of a global schedule to manage access times. However, the methods and algorithms to compute such schedules are not part of the TSN standard. The calculation of a schedule for the TDMA scheme of Time-Sensitive Networks is generally NP-hard. A popular method to solve such optimization problems is to formulate them as an integer linear program (ILP). State-of-the-art ILP solvers can solve the problem to proven optimality at the expense of very high runtimes. To combat the latter, some ILP solvers provide the user with the possibility to specify an initial set of hints for the variables of the ILP. Existing ILP-based approaches for TSN did not exploit this method so far. Therefore, it is an open research question whether and how much TSN scheduling could be improved by providing hints to the ILP solver. In this work, we thus propose to split up the solution process. First, we generate a set of hints. Afterwards, we supply the hints to the ILP solver, which is then executed on the original scheduling problem. The essential question in this process is now, how a good heuristic to calculate hints that support the ILP solution looks like. The generated hints should approximate a feasible solution of the scheduling problem; however, their calculation must be fast to speed up the overall process. To this end, we transfer the primitive of desynchronization, which originally had been proposed for wireless ad-hoc networks, to the TSN domain. Intuitively, to avoid collisions of transmitted packets as required by a valid TDMA schedule, we space out the transmission times of network traffic by adapting the sending times. In this thesis, we present a total of five different desynchronization algorithms for Time-Sensitive Networks. Our results show that by supplying initial desynchronization hints to the ILP solver, the runtime to compute a first feasible solution to the scheduling problem is sped up by at least a factor of six compared to an execution without any provided hints.
Time-Sensitive Networking (TSN) erweitert standardisiertes IEEE 802.3 Ethernet um deterministische Echtzeit-Fähigkeiten, die essentiell für viele Echtzeitsysteme sind. Dies wird durch die Implementierung eines Zeitmultiplexverfahrens (TDMA) erreicht. Für eine korrekte Funktionalität wird hierfür ein globaler Zeitplan (engl. schedule) benötigt, der die Zugriffszeiten koordiniert. Konkrete Algorithmen und Mechanismen, um einen solchen Zeitplan zu berechnen, sind allerdings nicht Teil des TSN Standards. Die Berechnung eines Zeitplans für TSN Netzwerke ist allgemein NP-schwer. Ein beliebter Weg zur Lösung solcher Optimierungsprobleme ist die Formulierung des Solchen als ganzzahlig lineares Programm (ILP). ILP-Lösungsprogramme sind in der Lage, diese Probleme beweisbar optimal zu lösen, allerdings auf Kosten sehr hoher Laufzeiten. Um die Lösung zu beschleunigen, bieten einige ILP-Lösungsprogramme dem Nutzer die Option, eine Reihe an initialen Hinweisen für die Variablen des ILPs anzugeben. Bereits existierende, auf ILP basierende TSN-Ansätze haben dieses Verfahren allerdings bisher nicht ausgenutzt. Deshalb ist es eine offene Forschungsfrage, ob und um wieviel sich TSN-Scheduling durch bereitgestellte Hinweise verbessern lässt. Hierzu wird in dieser Arbeit eine Zweiteilung des Lösungsprozesses vorgeschlagen. Zuerst wird eine Reihe an Hinweisen generiert. Daraufhin werden diese Hinweise an ein ILP-Lösungsprogramm weitergebenen und dieses auf die ursprüngliche Problemstellung angesetzt. Die grundlegende Frage in diesem Prozess ist nun, wie eine geeignete Heuristik zur Berechnung initialer Hinweise zur Unterstützung des ILP-Lösungsprogrammes aussieht. Einerseits sollen die generierten Hinweise eine bestmögliche Annährung an eine geeignete Lösung des Scheduling-Problems sein. Andererseits muss die Berechnung dieser Hinweise schnell erfolgen, sodass der gesamte Lösungsprozess beschleunigt wird. Zu diesem Zweck wird in dieser Arbeit das Prinzip der Desynchronisation, welches ursprünglich für kabellose Ad-hoc-Netzwerke vorgeschlagen wurde, auf das TSN-Scheduling Problem übertragen. Intuitiv gesehen können hiermit die Übertragungszeiten des Netzwerkverkehrs gleichmäßig verteilt werden, sodass Kollisionen von übertragenen Paketen vermieden werden. In dieser Arbeit werden fünf Desynchronisationsalgorithmen für TSN Netzwerke vorgestellt. Die Evaluierung dieser Algorithmen zeigt, dass die Lösungszeit zur Berechnung einer ersten geeigneten Lösung durch Angeben von initialen Desynchronisations-Hinweisen um mindestens einen Faktor von sechs verkürzt wird.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
Masterarbeit_Schneefuss_signed.pdf2,02 MBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.