A Novel Traffic Scheduling Algorithm for Multi-CQF Using Mixed Integer Programming and Variable Neighborhood Search Genetic Algorithm in Time-Sensitive Networking

Time-Sensitive Networking (TSN) is an advance Ethernet paradigm designed to provide low delay, low jitter, and deterministic transmission time. The Cycling Queuing and Forwarding (CQF) mechanism is introduced in TSN as a scheduler to achieve precise communication. Multi-CQF, as an extension of CQF, supports the transmission of various traffic types by assigning different cycle lengths to each queue group. In its original form, Multi-CQF-based scheduling algorithms do not account for flow sorting, leading to increased transmission delays and reduced network efficiency as a network dynamically changes. To enhance the performance of Multi-CQF, this paper initially utilizes queuing theory to analyze and manage traffic, providing foundation solutions. Subsequently, Mixed Integer Programming (MIP) and the Variable Neighborhood Search Genetic Algorithm (VNS-GA) are employed to optimize transmission delay in small- and large-traffic TSN networks, respectively. MIP quickly seeks out the optimal scheduling solution for small-traffic TSN networks using branch-and-bound and linear programming techniques, while the VNS-GA improves efficiency and performance for large-traffic ones by continuously adjusting the search neighborhood strategy. Comparing with other existing schemes, computer simulation reveals that MIP reduces delay by approximately 13% on average in small-traffic TSN networks, while the VNS-GA achieves an average delay reduction of 7% in large-traffic ones.