Master Thesis MSTR-2018-12

BibliographyBansal, Bharat: Divide-and-conquer scheduling for time-sensitive networks.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 12 (2018).
83 pages, english.

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.

Full text and
other links
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)Rothermel, Prof. Kurt; Nayak, Naresh
Entry dateMay 24, 2019
   Publ. Computer Science