Master Thesis MSTR-2022-36

BibliographyHoltwerth, Nico: Dynamic vertex colored conflict graphs for time-sensitive networks.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 36 (2022).
69 pages, english.
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.

Full text and
other links
Volltext
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)Rothermel, Prof. Kurt; Geppert, Heiko
Entry dateSeptember 16, 2022
   Publ. Computer Science