A novel iterated integer linear programming approach for IEEE 802.1time sensitive network scheduling

Deterministic communication plays an increasingly important role for Cyber Physical Systems such as industrial automation and in-vehicle communication networks. IEEE 802.1 Time Sensitive Networking (TSN) task group leads an initiative to define common standards for Ethernet- based deterministic communications due to its low-cost and high band- width. Iterated ILP-based TSN scheduling (IIS) is an approach to enhance the scalability of an ILP computation to solve the NP-hard 802.1Qbv-compliant TSN scheduling problem where the set of streams are divided into disjoint partitions which are iteratively solved. In this work, defining the communication constraints for no-wait TSN scheduling, we propose a novel IIS procedure (O-IIS) which intelligently determines the processing order of the disjoint parti- tions in order to enhance TSN schedulability, and evaluate the performance of O-IIS using various partitioning schemes. Experimental results show that O- IIS achieves up to a six times better performance almost in all traffic scenarios compared to conventional IIS within nearly the same amount of execution time.