Conflict graph-based time-triggered stream scheduling with multicast

Abstract

For the industry it is important to have deterministic reaction times for time-critical applications. These applications run on distributed systems that are connected via a network. Real-time communication is therefore essential to ensure that the real-time behavior is maintained. Thereby, identical information needs to be distributed to multiple members of the network. Multicast is great for sending the same data to multiple destinations while keeping the network traffic minimal and saving resources. In this thesis we integrate multicasting in a conflict graph-based routing and scheduling approach for time-triggered streams. We especially look at the routing of the multicast streams. We present different methods to construct the route of multicasts on the data-link layer for joint routing and scheduling and empirically evaluate these methods. We discover that calculating up to four candidate path-trees already solves our joint routing and scheduling problem in most cases. Further, scheduling multicast streams becomes harder with an increasing number of destinations per stream. We confirm that multicast streams reduce the traffic compared to multiple unicast streams in the conflict graph-based routing and scheduling approach. We can route and schedule 842 multicast streams in 25 seconds for networks with 81 nodes. Traffic plan updates with 25 additional streams are generated in less than 3.3 seconds.

In der Industrie ist es sehr wichtig deterministische Reaktionszeiten für zeit-kritische Anwendungen zu haben. Diese Anwendungen laufen auf verteilten Systemen, die über ein Netzwerk verbunden sind. Echtzeitkommunikation ist daher essenziell, um sicherzustellen, dass das Echtzeitverhalten aufrechterhalten wird. Dabei müssen identische Informationen an mehrere Teilnehmer des Netzwerks verteilt werden. Multicast ist sehr gut, um dieselben Daten an mehrere Empfänger zu senden und gleichzeitig den Netzwerkdatenverkehr minimal zu halten sowie Resourcen zu sparen. In dieser Arbeit integrieren wir Multicasts in einen konfliktgraph-basierenden Routing und Scheduling Ansatz für zeitgesteuerte Streams. Besonders untersuchen wir das Routing der Multicaststreams. Wir präsentieren verschiedene Methoden um Multicastrouten im Data-Link Layer für das Routing und Scheduling zu bilden und evaluieren diese Methoden empirisch. Wir stellen fest, dass die Berechnung von vier Kandidat-Pfad-Bäumen unser kombiniertes Routing und Scheduling Problem bereits in den meisten Fällen löst. Des Weiteren wird das Scheduling von Multicaststreams mit ansteigender Zahl an Zielen pro Stream schwieriger. Wir bestätigen, dass Multicaststreams im Vergleich zu mehreren Unicaststreams den Datenverkehr im konfliktgraph-basierenden Routing und Scheduling Ansatz reduzieren. Für Netzwerke mit 81 Knoten verarbeiten wir 842 Multicaststreams in 25 Sekunden. Datenverkehrsplanänderungen mit 25 zusätzlichen Streams werden in weniger als 3,3 Sekunden generiert.