Flow Ordering Problem for Time-Triggered Traffic in the Scheduling of Time-Sensitive Networking

Time-Sensitive Networking (TSN) can ensure deterministic communications for time-critical traffic, which plays a crucial role in various real-time scenarios. In this letter, we propose and study a neglected problem in TSN, named flow ordering problem, which provides a new perspective on improving the scheduling of large-scale TSN. Specifically, we formulate the flow ordering problem, look into its theoretical basis, and prove this problem is NP-hard. Furthermore, we propose a hybrid search algorithm to provide an optimized scheduling order. Simulation results verify the significant impact of the flow ordering problem on TSN scheduling and the effectiveness of our algorithm.

Automated summary

Time-Sensitive Networking (TSN) is crucial for deterministic communications in time-critical traffic in real-time scenarios. This letter proposes and studies the neglected flow ordering problem in TSN, which offers a new perspective to improve the scheduling of large-scale TSN. The problem is formulated, its theoretical basis is investigated, and its NP-hardness is proved. Additionally, a hybrid search algorithm is proposed to provide an optimized scheduling order. Simulation results demonstrate the significant impact of the flow ordering problem on TSN scheduling and the effectiveness of the algorithm.