Dynamic vertex colored conflict graphs for time-sensitive networks

Abstract

Industrial IoT has a growing demand for dynamically changing real-time communication networks, e.g., dynamic production systems. Thereby, a trend to the Plug-and-Produce paradigm is evident. Using IEEE Time-sensitive network standards is a common way to uphold real-time requirements. Usually, global traffic schedules for networks are computed statically, e.g., using Linear Programs. A conflict graph based scheduler is introduced to fulfill the requirements of a dynamic real-time communication network. The conflict graph stores flow configurations as vertices and conflicts (an incompatibility of two configurations) as edges. The scheduler solves an independent set problem to compute a global traffic plan for a network. However, constructing the conflict graph constitutes a significant bottleneck. Therefore, we present approaches to optimize the conflict graph construction phase. We discuss different graph data structures storing the conflict graph efficiently. Due to the efficient insert operations, we argue that implementing the conflict graph as an adjacency list is the most efficient conflict graph data structure for this use case. Further, we present approaches to reduce the conflict computations for new flow configurations by storing meta information. Roughly, a naive insertion is an O(|V|) operation checking if the new configuration conflicts with all other configurations. To reduce the complexity, we apply the Potential Conflicts approach by omitting conflict computations for flow configurations, which use disjoint paths. The approach shows to be effective for network topologies with many disjoint paths, e.g., Erdős-Rényi, but less efficient on topologies like trees. The runtime performance improvement achieved by the Potential Conflicts approach is up to a factor of 1.2-2 depending on the network topology. Another approaches we present are the Recurrence Conflicts and Recurrence Non-Conflicts checks. These checks recognize conflict reappearances that are shifted over time. The Recurrence Conflicts check decreases the runtime performance, however, checking for Recurrence Non-Conflicts improves the runtime performance immensely in cost of an exponential memory overhead. Combining the Potential Conflicts and Recurrence Non-Conflicts approaches provides the most efficient improvement. The runtime performance of the conflict graph construction phase increases up to a factor of 4-8, depending on the network topology.

Im Industrie 4.0 Kontext besteht ein wachsender Bedarf an sich dynamisch verändernden Echtzeit-Kommunikationsnetzen, z.B. bei dynamischen Produktionssystemen. Dabei zeichnet sich ein Trend zum Plug-and-Produce Paradigma ab. Die Verwendung von IEEE-Standards für zeitsensitive Netzwerke ist eine gängige Methode zur Einhaltung von Echtzeitanforderungen. Normalerweise werden globale Verkehrspläne für Netzwerke statisch berechnet, z.B. mit Hilfe linearer Programme. Um die Anforderungen eines dynamischen Echtzeit-Kommunikationsnetzes zu erfüllen, wurde ein Ansatz für einen Planer eingeführt, der auf Konfliktgraphen basiert. Der Konfliktgraph speichert Flusskonfigurationen als Eckpunkte und Konflikte (zwei inkompatible Konfigurationen) als Kanten. Um einen globalen Netzwerkplan zu berechnen, löst der Planer ein Independent Set Problem. Die Konstruktion des Konfliktgraphen erweist sich dabei jedoch als sehr aufwendig. Daher stellen wir Ansätze zur Optimierung der Konstruktionsphase vor. Wir diskutieren verschiedene Graph Datenstrukturen, die den Konfliktgraphen effizient speichern. Außerdem zeigen wir, dass die am besten geeignete Datenstruktur für den Konfliktgraphen in unserem Anwendungsfall die Adjazenz Liste ist. Dies kommt vor allem durch die effizienten Einfüge Operationen. Zusätzlich stellen wir Ansätze vor, die unterschiedliche Metainformationen speichern, um die Anzahl der Konfliktberechnungen zu reduzieren. Grob gesagt ist das Einfügen eine O(|V|) Operation, die prüft, ob die neue Konfiguration mit allen anderen Konfigurationen in Konflikt steht. Dabei wenden wir den Ansatz von Potential Conflicts an, indem wir die Konfliktberechnungen für Flusskonfigurationen auslassen, die disjunkte Pfade verwenden. Der Ansatz erweist sich als effektiv für Netzwerktopologien mit vielen disjunkten Pfaden, z.B. die Erdős-Rényi Topologie. Topologien wie Bäume zeigen sich eher als ineffizient. Die Laufzeitverbesserung, die mit dem Potential Conflicts Ansatz erreicht wird, beträgt je nach Netzwerktopologie bis zu einem Faktor von 1,2-2. Ein weiterer Ansatz, den wir vorstellen, sind die Recurrence Conflicts und Recurrence Non-Conflicts Prüfungen. Diese Prüfungen erkennen wiederkehrende Konflikte, die zeitlich versetzt sind. Dabei verschlechtert die Prüfung auf Recurrence Conflicts die Laufzeit. Die Prüfung auf Recurrence Non-Conflicts hingegen verbessert die Laufzeit, jedoch auf Kosten einer exponentiellen Speichernutzung. Die Kombination der beiden Ansätze Potential Conflicts und Recurrence Non-Conflicts ist am effizientesten und verbessert die Laufzeit der Konstruktionsphase des Konfliktgraphens je nach Netzwerktopologie um einen Faktor von 4-8.