Bibliography | Schneefuss, Patrick: Desychronization algorithms for fast ILP solutions of TDMA schedules in IEEE Time-Sensitive Networks. University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 39 (2021). 95 pages, english.
|
Abstract | Time-Sensitive Networking (TSN) is extending standard IEEE 802.3 Ethernet with deterministic real-time capabilities, which are essential for many networked real-time systems. It does so by implementing a time-division multiple access (TDMA) scheme. To operate correctly, this requires the presence of a global schedule to manage access times. However, the methods and algorithms to compute such schedules are not part of the TSN standard. The calculation of a schedule for the TDMA scheme of Time-Sensitive Networks is generally NP-hard. A popular method to solve such optimization problems is to formulate them as an integer linear program (ILP). State-of-the-art ILP solvers can solve the problem to proven optimality at the expense of very high runtimes. To combat the latter, some ILP solvers provide the user with the possibility to specify an initial set of hints for the variables of the ILP. Existing ILP-based approaches for TSN did not exploit this method so far. Therefore, it is an open research question whether and how much TSN scheduling could be improved by providing hints to the ILP solver. In this work, we thus propose to split up the solution process. First, we generate a set of hints. Afterwards, we supply the hints to the ILP solver, which is then executed on the original scheduling problem. The essential question in this process is now, how a good heuristic to calculate hints that support the ILP solution looks like. The generated hints should approximate a feasible solution of the scheduling problem; however, their calculation must be fast to speed up the overall process. To this end, we transfer the primitive of desynchronization, which originally had been proposed for wireless ad-hoc networks, to the TSN domain. Intuitively, to avoid collisions of transmitted packets as required by a valid TDMA schedule, we space out the transmission times of network traffic by adapting the sending times. In this thesis, we present a total of five different desynchronization algorithms for Time-Sensitive Networks. Our results show that by supplying initial desynchronization hints to the ILP solver, the runtime to compute a first feasible solution to the scheduling problem is sped up by at least a factor of six compared to an execution without any provided hints.
|