Abstract: With the development of the industrial Internet, the traditional best-effort forwarding mode can no longer meet the needs of deterministic delay communication, and the IEEE 802.1 working group proposes the cyclic queue forwarding mechanism to achieve deterministic transmission. However, due to fixed-granularity slot forwarding, there are problems such as excessive resource occupation and limited deterministic delay range. Therefore, for time-triggered traffic scheduling with strict latency requirements, a hierarchical cyclic queuing and forwarding mechanism is proposed to reduce the time-triggered traffic delay and reduce resource occupation through fast forwarding. An optimization model to maximize network throughput was constructed to determine the forwarding mode and the injection time slot of the flows. Due to the NP-hard nature, a heuristic priority iterative incremental scheduling algorithm is proposed, which adopts traffic clustering, priority order update and incremental scheduling to realize the calculation of large-scale deterministic traffic. Experimental results show that compared with the CQF mechanism, the scheduling ability of this proposed mechanism is enhanced, and the lower bound of deterministic delay is reduced by half compared with the original mechanism. Resource occupation decreased by 25.77% on average. In multiple sets of experiments involving various topologies, different traffic characteristics and scales, the proposed algorithm is better than the four comparison schemes in terms of network throughput, and the average increase is 3.52%、2.04% and 51.77% compared with the Tabu Search、IRFS and Naive.

摘要： 随着工业互联网的发展，传统尽力而为转发模式已经不能满足确定性时延通信的需求，IEEE 802.1工作组提出了循环排队和转发机制实现确定性传输。然而由于固定粒度的时隙转发存在过多资源占用、确定性时延范围受限的问题。因此，针对具有严格时延需求的时间触发流量调度，本文提出一种层次化循环排队和转发机制，设计快速转发模式，以降低时间触发流量时延并减少资源占用。同时，以确定转发模式和帧注入时隙的流量调度问题为研究对象，构建了最大化网络吞吐量的优化模型；由于求解该问题具有NP-hard性，设计了一种启发式的优先级迭代增量调度算法，采用流量聚类分组、优先级顺序更新和增量调度，实现大规模确定性流量的调度计算。实验结果表明，该机制相较于原始机制调度能力增强，可实现的确定性时延下限降低一半，资源占用平均降低了25.77%；在多种拓扑、不同流量特性和规模多组实验中，所提算法在调度成功流量的数目上均优于4种对比方案，相较于禁忌搜索、IRFS和Naive方案平均提升3.52%、2.04%和51.77%。