Hybrid Heuristic Optimization for Joint Routing and Scheduling in Time-Sensitive Networking
Huajian Zhou, Miao Guo, Xiuzhen Guo, Shibo He, Chaojie Gu, Jiming Chen · 2024
Time-Sensitive Networking (TSN) offers deterministic communication for time-sensitive applications, using Cyclic Queuing and Forwarding (CQF) to manage time-triggered flows (TT flows). Scheduling TT flows is essential for optimizing network resource utilization and scheduling success rates. Existing works prefer heuristic algorithms due to their favorable trade off between computational overhead and performance. However, they overlook two critical factors during design: search space approximation efficiency and the impact of routing policy. In this study, we present H-GATS (Hybrid Genetic Algorithm and Tabu Search) for CQF-based TSN flow routing and scheduling. H-GATS combines the global search of Genetic Algorithms with the local search of Tabu Search, achieving fine-grained search efficiency and reduced execution time in complex networks. Moreover, H-GATS considers the offset and routing of flows, further improving scheduling performance. Compared to GA, Tabu, and JRS-LB, H-GATS is 5.8×, 3.05×, and 1.6× faster, respectively, in achieving the same success rates. Additionally, H-GATS improves the success rate by 5.5%, 9.6%, and 3.9% and enhances the resource utilization rate by 18%, 13.3%, and 3.3% over these baselines.