Synchronous Time-Sensitive Networking Scheduling Algorithm Based on Dynamic Time Margin

Time-Sensitive Networking (TSN), as a set of the protocols of data link layer, is proposed by the IEEE 802.1 task group to ensure the real-time and deterministic network communication. However, the computation and configuration of the synchronous TSN scheduling problem is a non-deterministic polynomial hard (NP-hard) problem. To deal with such a problem, a fast solution algorithm is proposed in this paper based on the flow-by-flow method and dynamic programming method. Firstly, the difficulty aroused from the synchronization error is analyzed and the corresponding queue and gating resources for frames are reserved to guarantee the feasibility of the solution. Secondly, the upper and lower bounds of each frame are defined such that dynamic time margin is calculated. In addition, with the above bounds, two necessary feasibility conditions for the synchronous TSN scheduling problem are given, which can judge whether the problem is feasible before the scheduling. Finally, the queue arrangement problem with complex coupling constraints is solved by dynamic programming method with the aim of minimizing end-to-end delay. The proposed algorithm is verified, and the results show the efficacy of the proposed algorithm in obtaining the feasible and satisfactory scheduling scheme within a short time.