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.

关键词