Master Thesis MSTR-2023-64

BibliographyKollmeier, Magnus: Advanced Scheduling Heuristics for Time-triggered Realtime Networks.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 64 (2023).
51 pages, english.

In recent years, deterministic real-time communication with bounded delay has been a focus of development, with particular emphasis on Ethernet technologies. The TTEthernet and Time- Sensitive-Networking standards are being extended and worked on, to boost and broaden their use. Both standards include scheduling mechanism, but they do not represent all possible needs for scheduling of time-triggered communication. One of these areas is the need for solutions that work with an already existing system and modify the previous schedule to add additional streams. Another topic is the optimization outside of scheduling. For these two problems this thesis presents two new approaches. Both are based on the idea of ease of schedulability, not only to find a viable position to schedule a stream, but also to make it easier to schedule additional streams later. This is particularly important in the complex scheduling situation presented by time-triggered communication in a deterministic real-time Ethernet network. The first heuristic presented, Back-to-Back (Back2Back) scheduling, is a stream placement strategy that attempts to schedule clusters of streams to avoid small, hard-to-use free spaces in the schedule. It shows promising results, outperforming the comparison strategy when used in networks with changing stream utilization. It is capable of scheduling 4000 streams in a random network topology with 250 switches in less than half a second, while maintaining ease of schedulability. This means that in 40 time steps and large changes in utilization, scheduling is still able to fit more streams into the network, while the comparison strategy performs worse and is merely able to schedule the most basic new streams. The other approach is a heuristic called ’Defragment Scheduling’. It is designed to optimize schedules after streams are added respectively removed. Small unused intervals (’holes’) are identified and merged by moving streams. Due to implementation issues just preliminary results are presented, further investigations have to be done.

Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)Becker, Prof. Christian; Geppert, Heiko
Entry dateFebruary 20, 2024
   Publ. Computer Science