OSSR: Online Scalable Scheduling and Routing for Industrial Time-Sensitive Networking

As the promising deterministic networking technology of Industrial Internet of Things (IIoT), Time-Sensitive Networking (TSN) has been widely investigated in recent years. Most existing research focuses on offline scheduling and routing for TSN, which is time-consuming and thus unsuitable for dynamic stream demands. To tackle this problem, an online scalable scheduling and routing (OSSR) scheme is proposed for TSN in this paper. A novel slot occupancy representation (SOR) model is established based on divisibility theory to transform the clique-based to a three-level tree-based mode in complex IIoT scenarios. This transformation reduces the computational complexity of maximum slot occupancy judgment from exponential to linear complexity. Based on the above SOR model, a load balance metric for stream scheduling is constructed to guide the optimal routing. Assessed by this metric, an online decoupled routing and scheduling algorithm is proposed to minimize the maximum slot occupancy of all links while guaranteeing high scalability. Evaluation results show that the proposed OSSR scheme outperforms the existing approaches with better adaption to dynamics and lower slot occupancy of links.