Future-proof scheduling heuristics for TTEthernet

Abstract

Time-triggered networks run on a premade schedule to ensure that all messages arrive at their destination on time and without being dropped. They are deployed in safety-critical environments like airplanes, cars, but also factories. Online scheduling algorithms can create schedules for such networks in mere seconds while also being able to modify an existing schedule. With an algorithm of this kind, new devices can be plugged into its time-triggered network and start interacting with it in seconds, without manual setup. We propose modifications for improving two already existing online scheduling algorithms: Hierarchical Heuristic Scheduling (H2S) and Cost-Efficient Lazy Forwarding (CELF). We call these modifications "relaxed jitter", "backward rifts", and "gap closing". Our modifications achieved about 550 MBit/s more aggregated throughput while only increasing solving time by 2.5ms in a network with 25 switches. Zeitgesteuerte Netzwerke nutzen einen vorgefertigten Zeitplan um sicherzustellen, dass alle Nachrichten ihr Ziel rechtzeitig erreichen ohne verloren zu gehen. Sie werden in sicherheitskritischen Umgebungen wie Flugzeugen, Autos, aber auch Fabriken, eingesetzt. Online Planungsalgorithmen können Zeitpläne für solche Netzwerke in wenigen Sekunden generieren und auch bereits existierende Zeitpläne anpassen. Mit einem solchen Algorithmus können neue Geräte an ein zeitgesteuertes Netzwerk angeschlossen werden und sind dann innerhalb von Sekunden ohne manuellen Eingriff einsatzbereit. Wir schlagen Verbesserungen für zwei bereits existierende Online Planungsalgorithmen vor: Hierarchical Heuristic Scheduling (H2S) und Cost-Efficient Lazy Forwarding (CELF). Wir nennen diese Verbesserungen "Relaxed Jitter", "Backward Rifts" und "Gap Closing". Unsere Verbesserungen erreichten etwa 550 MBit/s zusätzlichen aggregierten Netzwerkdurchsatz, bei einer nur leicht erhöhten Berechnungszeit von 2,5ms in einem Netzwerk mit 25 Switches.