Efficient Flow Scheduling for Industrial Time-Sensitive Networking: A Divisibility Theory-Based Method

As an emerging communication technology, time-sensitive networking (TSN) promises the real time and deterministic interaction of massive data in Industrial Internet of Things. However, it is challenging to schedule the time-sensitive flows timely and superiorly through the mechanism analysis for current TSN scheduling models, especially in complex industrial scenarios. In this article, we propose an analysis approach of flow sequences based on divisibility theory to characterize the flow conflicts and dependencies, which derives the scheduling flexibility based on flow position diversity (PD) and the equivalent flow judgment conditions for slot occupancy. Integrating the abovementioned derivation, a parallel computing framework with the generalized slot length is established to lower the scheduling complexity. Within each computing unit, an incremental scheduling algorithm with the flow judgment conditions and PD-based search boundary is proposed. It reduces the scheduling complexity further while maintaining load balance for the mixed transmission of periodic and aperiodic flows. To achieve the optimality of runtime and load balance, two PD-based flow sorting strategies are designed, respectively. The evaluation results show that compared with the existing works, the runtime efficiency of scheduling at scale is increased by at least 1500 times in complex traffic scenarios while the load balance on the network links is also improved.