Master Thesis MSTR-2022-51

BibliographyWeitbrecht, Michel: ILP-based schedule planning for dynamic IEEE time-sensitive networks.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 51 (2022).
74 pages, english.
Abstract

Time-Sensitive Networking (TSN) denotes a set of IEEE standards that amend Ethernet by realtime capabilities. Specifically, the Time-Aware Shaper (TAS) implements a time division multiple access (TDMA) scheme allowing to temporally isolate time-sensitive traffic. In order to deploy a TSN network configuration providing hard bounds on delay and jitter, synchronized clocks and a global transmission schedule are required. However, the calculation of such a global schedule is not part of the TSN standard. Most scheduling approaches proposed in the literature target static scenarios where the network topology and the flow set are known a priori. Novel use cases encountered in Industry 4.0 have more dynamic requirements, such as connecting further machines or enabling new features that result in additional flows that need to be admitted into the schedule. Dynamic TSN scheduling poses challenges not only in adding new flows to an existing schedule, but also for initial offline scheduling, as each placement of flows in the original schedule may decrease future schedulability. In our work, we define an Integer Linear Programming (ILP) model that supports incrementally adding new flows to an existing schedule, taking original flow placements into account. It supports both defensive scheduling, where existing flows are not temporally moved, as well as offensive scheduling, in which existing flows may be rescheduled by a limited amount configurable per flow. We propose two optimization objectives aiming to improve schedulability of future flows. The first objective max-freeblock schedules flows in a way that increases the unoccupied time at the end of each schedule cycle time, leaving space to place future flows in defensive scheduling scenarios. The second objective link-desync maximizes the unoccupied gap between every two consecutive flows of a link, creating flexibility for future offensive scheduling. Further, we propose a heuristic-based algorithm that strategically selects a reduced set of initial flows for rescheduling based on link occupancy, reducing the model size and decreasing the execution time necessary to place additional flows. Our evaluations show that our max-freeblock strategy outperforms the baseline min-flowspan objective in defensive scheduling. Utilizing our rescheduling selection algorithm, 97 % of additional flows were admitted in offensive scheduling scenarios, compared to only 72 % achieved without restricting the rescheduling flow set.

Full text and
other links
Volltext
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)Rothermel, Prof. Kurt; Dürr, Dr. Frank
Entry dateOctober 28, 2022
   Publ. Computer Science