Scalable traffic engineering heuristics for time-triggered communication in real-time networks
Date
2026
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Verteilte, sicherheitskritische cyber-physische Systeme erfordern Echtzeitverhalten. Das bedeutet, dass sie nicht nur schnell, sondern auch rechtzeitig, auf neue Situationen reagieren müssen - unter Berücksichtigung sowohl der Verarbeitungszeit von Aufgaben sowie der Netzwerklatenz. Aus Netzwerksicht ist eine sorgfältige, zeitgesteuerte Netzwerkverkehrsplanung auf Rahmenebene notwendig, um niedrige Ende-zu-Ende-Verzögerungen und geringe Latenzen zu gewährleisten. Dies beinhaltet eine präzise Planung der Übertragungsvorgänge entlang des Netzwerkpfads jedes zeitkritischen Rahmens, einschließlich exakter Zeitsteuerung. So lassen sich Störungen durch Querverkehr zu begrenzen oder sogar zu eliminieren und eine rechtzeitige Zustellung sicherstellen. Da moderne Echtzeitsysteme aus Hunderten oder Tausenden von Geräten bestehen können, etwa große Fertigungsanlagen oder kontinentalgroße Stromnetze, muss die Verkehrsplanung hochgradig skalierbar sein. In der Literatur gibt es zwar viele Ansätze zur Verkehrsplanung, es mangelt jedoch an sehr schnellen Heuristiken, die sehr große Netzwerke und viele Datenströme effizient verarbeiten können. In dieser Arbeit werden Heuristiken und Optimierungstechniken für die Verkehrsplanung untersucht. Der Schwerpunkt liegt dabei auf verschiedenen Aspekten des Bereichs der Netzwerkverkehrsplanung liegt. Die Verkehrsplanung umfasst neuartige Methoden für die konfliktgraphbasierte Planung sowie neue Heuristiken für sehr große Instanzen des Verkehrsplanungsproblems. Zu den Optimierungen gehören die Multicast-Partitionierung, die die Vorteile von Multicast- und Unicast-Verkehrsplänen kombiniert, sowie die lastbalancierte Platzierung von Datenströmen. Letzteres erzeugt Verkehrspläne, die die spätere Aufnahme zusätzlicher Ströme ermöglichen. Zur Bewertung unserer Ansätze entwickelten wir Prototypimplementierungen und analysierten ihre Leistungsfähigkeit im Hinblick auf das Verkehrsplanungsproblem. Unsere Verkehrspläne erzielten eine höhere kumulierte Netzauslastung oder ließen mehr Datenströme zu, während die Rechenzeiten selbst bei extrem großen Probleminstanzen von unter einer Sekunde bis hin zu wenigen Minuten reichten. Die in dieser Arbeit vorgestellten Methoden und Optimierungen lassen sich auf moderne Echtzeit-Netzwerktechnologien wie Time-Sensitive Networking oder TTEthernet anwenden.
Distributed safety-critical cyber-physical systems require real-time behavior. This means they must respond not just quickly, but in time, to new situations considering both, the task processing and network communication time. From a networking perspective, meticulous, time-driven traffic planning performed at the frame level is necessary to guarantee low end-to-end delay bounds and low latency. This involves carefully planning transmission operations along each time-critical frame's network path are carefully planned, including precise timing, to limit or even eliminate interference from cross-traffic and ensure timely delivery. Since modern real-time systems can consist of hundreds or thousands of devices - for example, large manufacturing plants or continental-sized power grids - the traffic planning must be highly scalable. Although there are many traffic planning approaches in the literature, there is a lack of very fast heuristics that can handle very large stream sets and networks quickly. This thesis investigates traffic planning heuristics and optimization techniques, focusing on different aspects of the traffic planning domain. The traffic planning consists of novel methods for conflict-graph-based scheduling and new heuristics for very large instances of traffic planning problem. The optimizations include multicast partitioning, which combines the benefits of multicast and unicast traffic plans, and load-balanced stream placement, which generates traffic plans that can accommodate additional streams joining the system later. We created prototype implementations and analyzed their performance in solving the traffic planning problem. Our traffic plans yielded a higher accumulated network throughput or admitted more streams while maintaining computation times ranging from sub-seconds to minutes, even for extremely large-scale problem instances. The traffic planning methods and optimization techniques presented in this thesis can be applied to modern real-time networking technologies, such as Time-Sensitive Networking and TTEthernet.
Distributed safety-critical cyber-physical systems require real-time behavior. This means they must respond not just quickly, but in time, to new situations considering both, the task processing and network communication time. From a networking perspective, meticulous, time-driven traffic planning performed at the frame level is necessary to guarantee low end-to-end delay bounds and low latency. This involves carefully planning transmission operations along each time-critical frame's network path are carefully planned, including precise timing, to limit or even eliminate interference from cross-traffic and ensure timely delivery. Since modern real-time systems can consist of hundreds or thousands of devices - for example, large manufacturing plants or continental-sized power grids - the traffic planning must be highly scalable. Although there are many traffic planning approaches in the literature, there is a lack of very fast heuristics that can handle very large stream sets and networks quickly. This thesis investigates traffic planning heuristics and optimization techniques, focusing on different aspects of the traffic planning domain. The traffic planning consists of novel methods for conflict-graph-based scheduling and new heuristics for very large instances of traffic planning problem. The optimizations include multicast partitioning, which combines the benefits of multicast and unicast traffic plans, and load-balanced stream placement, which generates traffic plans that can accommodate additional streams joining the system later. We created prototype implementations and analyzed their performance in solving the traffic planning problem. Our traffic plans yielded a higher accumulated network throughput or admitted more streams while maintaining computation times ranging from sub-seconds to minutes, even for extremely large-scale problem instances. The traffic planning methods and optimization techniques presented in this thesis can be applied to modern real-time networking technologies, such as Time-Sensitive Networking and TTEthernet.
Description
Keywords
Citation
Endorsement
Review
Supplemented By
Referenced By
Creative Commons license
Except where otherwised noted, this item's license is described as CC BY