Bachelorarbeit BCLR-2022-71

Bibliograph.
Daten
Rönsch, Lozenz: Weighted independent colorful sets in large vertex colored conflict graphs for timetriggered flow scheduling.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 71 (2022).
51 Seiten, englisch.
Kurzfassung

The need for time sensitive communication on networks is increasing more and more, especially due to Industrial internet of things and Industry 4.0. With the appearance of graphics-based network participants in time-critical networks, such as VR glasses, the absolute amount of traffic that needs to be scheduled over the network increases strongly. The most common method to realize real time communication is using the IEEE Time-Sensitive Network (TSN) and the Time-Aware Shaper (TAS). However, the TSN schedule calculation is not standardized. There are several approaches, such as SMT solver, integer linear programming and calculating a conflict graph to calculate time-triggered flow schedules. But none of them are tackling the problem of maximizing traffic. In our work, we extend the time-triggered flow scheduling problem to include the component of maximum traffic. For this purpose, we modify an existing heuristic, called Greedy Flow Heap Heuristic, so that we can adapt the scheduling to our problem. The results that our version provides compared to the original heuristic are very promising. On all our evaluation data, we achieved an average improvement of 81.91% in terms of maximum network traffic. We also developed an alternative non-deterministic approach based on a genetic algorithm. In our work we investigate different variants of the algorithm with the goal to provide better results with different adaptations of the algorithm. In our repair version, we manage to beat our benchmark algorithm the Greedy Flow Heap Heuristic on every circle based conflict graph.

Volltext und
andere Links
Volltext
Abteilung(en)Universität Stuttgart, Institut für Parallele und Verteilte Systeme, Verteilte Systeme
BetreuerRothermel, Prof. Kurt; Geppert, Heiko
Eingabedatum29. November 2022
   Publ. Abteilung   Publ. Institut   Publ. Informatik