Bachelor Thesis BCLR-2022-71

BibliographyRönsch, Lozenz: Weighted independent colorful sets in large vertex colored conflict graphs for timetriggered flow scheduling.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 71 (2022).
51 pages, english.

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.

Full text and
other links
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)Rothermel, Prof. Kurt; Geppert, Heiko
Entry dateNovember 29, 2022
   Publ. Computer Science