Article in Proceedings INPROC-2021-01

BibliographyHellmanns, David; Haug, Lucas; Hildebrand, Moritz; Dürr, Frank; Kehrer, Stephan; Hummen, René: How to Optimize Joint Routing and Scheduling Models for TSN Using Integer Linear Programming.
In: ACM (ed.): Proceedings of the 29th International Conference on Real-Time Networks and Systems.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology.
pp. 1-12, english.
Nantes: ACM (Online), April 7, 2021.
ISBN: 10.1145/3453417.3453421.
Article in Proceedings (Conference Paper).
Corporation29th International Conference on Real-Time Networks and Systems
CR-SchemaD.4.7 (Operating Systems Organization and Design)
KeywordsTime-Sensitive Networking, TSN, Scheduling, Routing, Integer Linear Programming, Optimization, Model, ILP
Abstract

Reliable real-time communication is an essential technology for industrial manufacturing but also other branches to transport mission-critical messages. IEEE Time-Sensitive Networking (TSN) is a disruptive real-time communication standard extending IEEE Ethernet with real-time mechanisms. One of the core features of TSN is the Time-Aware Shaper (TAS) enabling TDMA-based scheduling of streams within the network. TDMA has many advantages from the real-time perspective. Foremost, stream isolation in the time dimension enables tight delay and jitter bounds. Moreover, conformance to these bounds is proven by the design of the TDMA schedule. However, calculating an optimal schedule is an NP-hard problem. Therefore, various approaches to optimize the schedule calculation are proposed, such as Integer Linear Programming (ILP). Nevertheless, a systematic comparsion of the different optimization approaches with respect to their performance is missing so far. To fill this gap, we first provide a systematic classification of optimizations of ILP-based TSN scheduling. To quantify the effects of such optimization approaches, we introduce a base ILP and propose optimizations for the different categories. Using the proposed optimization, we evaluate the performance with regard to execution time and schedulability (number of solved schedules). Our results show that the optimizations lead to strongly fluctuating results. Certain intuitive optimizations can even lead to massive performance degradations.

Full text and
other links
PDF (1919568 Bytes)
Contactdavid.hellmanns@ipvs.uni-stuttgart.de
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Entry dateMarch 9, 2021
   Publ. Computer Science