Masterarbeit MSTR-2018-12

Bansal, Bharat: Divide-and-conquer scheduling for time-sensitive networks.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Masterarbeit Nr. 12 (2018).
83 Seiten, englisch.

The advent of the Internet of Things(IoT) and Industry 4.0 coupled with the increase in the deployment of Cyber-physical systems(CPS), which includes industrial automation systems, has increased the urgency to deploy networking technologies with real-time guarantees. The IEEE 802.1Obv standard has recently emerged as a viable alternative for the future of real-time communication over Ethernet that has stringent end-to-end latency and jitter requirements after it has been recently standardized by the Time Sensitive Network Task Group. Scheduling in Time-Sensitive Network(TSN) has not been standardized by the Task Group to carry the scheduled traffic till now. In this paper, we address the scheduling problem for a Time-Sensitive Network(TSN) for large and complex networks. State-of-the-art scheduling algorithms take a centralized approach to compute transmission schedules for time-triggered traffic. Centralized approaches generally compute fairly optimum transmission schedules but the runtimes for the centralized approaches are high (order of days) for large and complex networks. The aim is to generate a scheduling algorithm having lower runtimes as compared to centralized approaches for large networks and having large time-triggered flows even if the computed scheduling has a worse optimum solution than the centralized algorithm. We present a divide-and-conquer approach that might be apter in these scenarios, as it may generate a schedule with lower runtimes as compared to the centralized approaches. In particular, we present an Integer Linear Program(ILP) based formulation and a simple heuristics for the divide-and-conquer approach. Moreover, we parallelize the problem in order to further reduce the runtimes. We evaluate the optimality, utilization, scalability of the different approaches. Furthermore, we evaluate the runtimes for different network configurations and discuss the trade-off between heuristics and ILP based formulation.

Volltext und
andere Links
Abteilung(en)Universität Stuttgart, Institut für Parallele und Verteilte Systeme, Verteilte Systeme
BetreuerRothermel, Prof. Kurt; Nayak, Naresh
Eingabedatum24. Mai 2019
   Publ. Informatik