Weighted independent colorful sets in large vertex colored conflict graphs for timetriggered flow scheduling

Abstract

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.

Der Bedarf an zeitsensitiver Kommunikation in Netzwerken nimmt immer mehr zu, insbesondere aufgrund von dem industriellen internet der Dinge und Industrie 4.0. Mit dem Auftreten von grafikbasierten Netzwerkteilnehmern in zeitkritischen Netzwerken, wie z.B. VR-Brillen, steigt auch die absolute Menge des Netzwerkverkehr, der über das Netzwerk geplant werden muss, stark an. Die gängigste Methode zur Realisierung von Echtzeitkommunikation ist die Verwendung des IEEE Time-Sensitive Network (TSN) und des Time-Aware Shaper (TAS). Das Problem ist, dass es nicht standardisiert ist, wie die Zeitpläne für TSN zu berechnen sind. Es gibt verschiedene Ansätze wie SMT-Löser, ganzzahlige lineare Programmierung und die Berechnung eines Konfliktgraphen zur Berechnung von zeitgesteuerten Ablaufplänen. Aber keiner von ihnen befasst sich mit dem Problem der Maximierung des Netzwerkverkehr. In unserer Arbeit erweitern wir das Problem der zeitgesteuerten Verkehrsflussplanung um die Komponente des maximalen Netzwerkverkehr. Zu diesem Zweck modifizieren wir eine bestehende Heuristik, die so genannte Greedy Flow Heap Heuristic, zur Maximierung der Netzwerkteilnehmer bei der Verkehrsplanung, so dass wir die Planung an unser Problem anpassen können. Die Ergebnisse, die unsere Variante im Vergleich zur ursprünglichen Heuristik liefert, sind sehr vielversprechend. Bei all unseren Evaluierungsdaten erreichten wir eine durchschnittliche Verbesserung von 81.91% in Bezug auf den maximalen Netzwerkverkehr. Wir haben auch einen nicht-deterministischen Ansatz entwickelt, der auf einem genetischen Algorithmus basiert. In unserer Arbeit untersuchen wir verschiedene Varianten des Algorithmus mit dem Ziel, mit verschiedenen Anpassungen des Algorithmus bessere Ergebnisse zu erzielen. In einigen Varianten gelingt es uns auch, unseren Benchmark-Algorithmus, die Greedy Flow Heap Heuristik, zu schlagen.