时间敏感网络中的新型异步流量调度算法

IEEE802.1时间敏感网络（Time Sensitive Network，TSN）任务组致力于保障数据通信中的确定性低时延。为了在TSN中合理地调度流量，异步流量整型（Asynchronous Traffic Shaper，ATS）机制被引入以保证端到端最大时延边界，同时不需要复杂的时间同步，其中基于紧迫性的调度器（Urgency-Based Scheduler，UBS）成为ATS的默认实现算法。然而，在真实部署中，由于实际网络环境存在不稳定的突发流量，如果一些参数没有得到适当的实时配置，UBS并不能实现最佳的低时延调度表现。更重要的是，UBS需要消耗过多的缓冲区资源，这限制了TSN在现实世界中部署可行性。为了解决上述问题，我们提出了一种新型ATS调度方法，即时间敏感排队（Time Sensitive Queuing，TSQ）。TSQ通过去除需要实时配置的参数，大大降低了TSN部署的难度。此外，为了减少缓冲区的消耗，TSQ将基于时隙的数据报文分配机制作为入队策略，将基于时隙的数据报文轮询机制作为出队策略。我们基于网络演算（Network Calculus）的性能分析表明，与UBS相比，TSQ可以提供有边界的低时延和节约高达40%的缓冲区资源。在NS3中进行的大量实验表明，与UBS相比，TSQ消耗的缓冲区资源减少了33%。

The IEEE 802.1 Time Sensitive Networking (TSN) task group is devoted to improving deterministic delay during data communication. To schedule traffic in TSN, Asynchronous Traffic Shaping (ATS) has been introduced to guarantee bounded maximum delays without complicated time synchronization, and Urgency Based Scheduler (UBS) becomes the default implementation for ATS. However, due to the traffic fluctuation, UBS cannot achieve best delay bounds if some parameters are not configured appropriately in real time. What is more, UBS needs to consumes excessive buffer resources, which prevents TSN from being deployed in real world. To solve these problems, we propose Time Sensitive Queuing (TSQ), a novel ATS mechanism. TSQ lowers the difficulty of TSN deployment by removing the parameter that need to be configured in real time. In addition, to reduce the buffer consumption, TSQ applies time-slot-based packet allocation mechanism as the enqueue strategy, and time-slot-based packet polling mechanism as the dequeue strategy, respectively. Our analysis based on Network Calculus indicates that TSQ is capable of providing bounded delays while reducing the buffer resource usage by up to 40% compared to UBS. The extensive experiments implemented in NS3 show that TSQ consumes 33% less buffer resource compared to UBS.

[1] GALLOWAY B, HANCKE G P. Introduction to Industrial Control Networks[J]. IEEE Communications Surveys & Tutorials, 2013, 15(2): 860-880.
[2] TINDELL K, HANSSMON H, WELLINGS A J. Analysing Real-Time Communications: Controller Area Network (CAN)[C]//Proceedings of the 1994 IEEE Real-Time Systems Symposium. Piscataway, NJ: IEEE, 1994: 259-263.
[3] MAKOWITZ R, TEMPLE C. Flexray - A Communication Network for Automotive Control Systems[C]//Proceedings of the 2006 IEEE International Workshop on Factory Communication Systems. Piscataway, NJ: IEEE, 2006: 207-212.
[4] FELD J. PROFINET - Scalable Factory Communication for all Applications[C]//Proceedings of the 2004 IEEE International Workshop on Factory Communication Systems. Piscataway, NJ: IEEE, 2004: 33-38.
[5] LANGLOIS K, VAN DER HOEVEN T, RODRIGUEZ CIANCA D, et al. EtherCAT Tutorial: An Introduction for Real-Time Hardware Communication on Windows[J]. IEEE Robotics & Automation Magazine, 2018, 25(1): 22-122.
[6] CENA G, SENO L, VALENZANO A, et al. Performance Analysis of Ethernet Powerlink Networks for Distributed Control and Automation Systems[J]. Computer Standards & Interfaces, 2009, 31(3): 566-572.
[7] IEEE. IEEE Standard for Local and metropolitan area networks – Bridges and Bridged Networks - Amendment 25: Enhancements for Scheduled Traffic[S]. Piscataway,NJ: IEEE, 2016.
[8] IEEE. IEEE Standard for Local and metropolitan area networks – Bridges and Bridged Networks – Amendment 29: Cyclic Queuing and Forwarding[S]. Piscataway,NJ: IEEE, 2017.
[9] IEEE. IEEE Standard for Local and Metropolitan Area Networks – Bridges and Bridged Networks – Amendment 34:Asynchronous Traffic Shaping[S]. Piscataway,NJ: IEEE, 2020.
[10] NASRALLAH A, THYAGATURU A S, ALHARBI Z, et al. Ultra-Low Latency (ULL) Net works: The IEEE TSN and IETF DetNet Standards and Related 5G ULL Research[J]. IEEE Communications Surveys & Tutorials, 2019, 21(1): 88-145.
[11] IEEE. IEEE Standard for Local and Metropolitan Area Networks – Virtual Bridged Local Area Networks Amendment 12: Forwarding and Queuing Enhancements for Time-Sensitive Streams[S]. Piscataway,NJ: IEEE, 2010.
[12] IEEE. IEEE Standard for Local and Metropolitan Area Networks – Timing and Synchronization for Time-Sensitive Applications[S]. Piscataway,NJ: IEEE, 2020.
[13] SHI H, AIJAZ A, JIANG N. Evaluating the Performance of Over-the-Air Time Synchronization for 5G and TSN Integration[C]//Proceedings of the 2021 IEEE International Black Sea Conference on Communications and Networking. 2021: 1-6.
[14] HU H, LI Q, XIONG H, et al. The Delay Bound Analysis Based on Network Calculus for Asynchronous Traffic Shaping under Parameter Inconsistency[C]//Proceedings of the 2020 IEEE International Conference on Communication Technology. Piscataway, NJ: IEEE, 2020: 908-915.
[15] NAYAK N G, DURR F, ROTHERMEL K. Time-Sensitive Software-Defined Network (TSSDN) for Real-Time Applications[C]//Proceedings of the 24th IEEE International Conference on Real-Time Networks and Systems. 2016: 193–202.
[16] SPECHT J, SAMII S. Urgency-Based Scheduler for Time-Sensitive Switched Ethernet Networks[C]//Proceedings of the 2016 IEEE Euromicro Conference on Real-Time Systems. Piscataway, NJ: IEEE, 2016: 75-85.
[17] ZHOU Z, YAN Y, BERGER M, et al. Analysis and Modeling of Asynchronous Traffic Shaping in time sensitive networks[C]//Proceedings of the 2018 IEEE International Workshop on Factory Communication Systems. Piscataway, NJ: IEEE, 2018: 1-4.
[18] SPECHT J, SAMII S. Synthesis of Queue and Priority Assignment for Asynchronous Traffic Shaping in Switched Ethernet[C]//Proceedings of the 2017 IEEE Real-Time Systems Symposium. Piscataway, NJ: IEEE, 2017: 178-187.
[19] THOMAS L, BOUDEC J Y L, MIFDAOUI A. On Cyclic Dependencies and Regulators in Time-Sensitive Networks[C]//Proceedings of the 2019 IEEE Real-Time Systems Symposium. Piscataway, NJ: IEEE, 2019: 299-311.
[20] ZHAO L, POP P, STEINHORST S. Quantitative Performance Comparison of Various Traffic Shapers in Time-Sensitive Networking[J]. IEEE Transactions on Network and Service Management, 2022, 19(3): 2899-2928.
[21] NASRALLAH A, THYAGATURU A S, ALHARBI Z, et al. Performance Comparison of IEEE 802.1 TSN Time Aware Shaper (TAS) and Asynchronous Traffic Shaper (ATS)[J]. IEEE Access, 2019, 7(1): 44165-44181.
[22] GRIGORJEW A, METZGER F, HOßFELD T, et al. Constant Delay Switching: Asynchronous Traffic Shaping with Jitter Control[C]//Proceedings of the 2022 IFIP International Federation for Information Processing Networking Conference. Piscataway, NJ: IEEE, 2022: 1-9.
[23] ECKERT T, CLEMM A, BRYANT S. gLBF: Per-Flow Stateless Packet Forwarding with Guaranteed Latency and Near-Synchronous Jitter[C]//Proceedings of the 2021 IEEE International Conference on Network and Service Management. Piscataway, NJ: IEEE, 2021: 578-584.
[24] GRIGORJEW A, METZGER F, HOßFELD T, et al. Constant Delay Switching: Asynchronous Traffic Shaping with Jitter Control[C]//Proceedings of the 2022 IFIP Networking Conference. 2022: 1-9.
[25] BOUDEC J Y L. A Theory of Traffic Regulators for Deterministic Networks with Application to Interleaved Regulators[J]. IEEE/ACM Transactions on Networking (TON), 2018, 26(6): 2721-2733.
[26] MOHAMMADPOUR E, STAI E, MOHIUDDIN M, et al. Latency and Backlog Bounds in Time-Sensitive Networking with Credit Based Shapers and Asynchronous Traffic Shaping[C]//Proceedings of the 2018 IEEE International Teletraffic Congress. Piscataway, NJ: IEEE, 2018: 1-6.
[27] IEEE. IEEE Standard for Local and metropolitan area networks – Bridges and Bridged Networks – Amendment 26: Frame Preemption[S]. Piscataway,NJ: IEEE, 2016.
[28] SIMON C, MALIOSZ M, MATE M. Design Aspects of Low-Latency Services with Time Sensitive Networking[J]. IEEE Communications Standards Magazine, 2018, 2(2): 48-54.
[29] PEDREIRAS P, GAI P, ALMEIDA L, et al. FTT-Ethernet: A Flexible Real-Time Communication Protocol That Supports Dynamic QoS Management on Ethernet-Based Systems[J]. IEEE Transactions on Industrial Informatics, 2005, 1(3): 162-172.
[30] 孙广东. 时间敏感网络中时钟同步与调度算法的研究与仿真[D]. 北京: 北京邮电大学, 2018.
[31] STEINER W. An Evaluation of SMT-based Schedule Synthesis for Time-Triggered Multi-hop Networks[C]//Proceedings of the 2010 IEEE Real-Time Systems Symposium. Piscataway, NJ: IEEE, 2010: 375-384.
[32] CRACIUNAS S S, OLIVER R S, CHMELK M, et al. Scheduling Real-Time Communica tion in IEEE 802.1Qbv Time Sensitive Networks[C]//Proceedings of the 2016 IEEE Real-Time Systems Symposium. Piscataway, NJ: IEEE, 2016: 183-192.
[33] CRACIUNAS S S, OLIVER R S. Combined Task- and Network-level Scheduling for Distributed Time-Triggered Systems[J]. Real-Time Systems, 2016, 52(2): 161-200.
[34] HANZáLEK Z, BURGET P, ŠůCHA P. Profinet IO IRT Message Scheduling with Temporal Constraints[J]. IEEE Transactions on Industrial Informatics, 2010, 6(3): 369-380.
[35] DURR F, NAYAK N G. No-wait Packet Scheduling for IEEE Time-Sensitive Networks (TSN)[C]//Proceedings of the 24th ACM International Conference on Real-Time Networks and Systems. New York, NY, USA: ACM, 2016: 203-212.
[36] 王朴野. 时间敏感网络中调度算法的研究与仿真[D]. 北京: 北京邮电大学, 2018.
[37] YAN J, QUAN W, JIANG X, et al. Injection Time Planning: Making CQF Practical in Time Sensitive Networking[C]//Proceedings of the 2020 IEEE INFOCOM. 2020: 616-625.
[38] QUAN W, YAN J, JIANG X, et al. On-line Traffic Scheduling optimization in IEEE 802.1Qch based Time-Sensitive Networks[C]//Proceedings of the 2020 IEEE International Conference on High Performance Computing and Communications. 2020: 369-376.
[39] ZHOU Z, BERGER M S, RUEPP S, et al. Insight into the IEEE 802.1 Qcr Asynchronous Traffic Shaping in Time Sensitive Network[J]. Advances in Science, Technology and Engineering Systems, 2019, 4(1): 292-301.
[40] BOUDEC J Y L, THIRAN P. Network Calculus : A Theory of Deterministic Queuing Systems for the Internet[M]. Springer, 2001.
[41] ZHAO L, POP P, ZHENG Z, et al. Timing Analysis of AVB Traffic in TSN Networks Using Network Calculus[C]//Proceedings of the 2018 IEEE Real-Time and Embedded Technology and Applications Symposium. Piscataway, NJ: IEEE, 2018: 25-36.
[42] IEEE. IEEE Standard for Local and Metropolitan Area Network – Bridges and Bridged Networks[S]. Piscataway,NJ: IEEE, 2018.
[43] 杜静. 时间敏感网络关键技术仿真研究[D]. 西安电子科技大学, 2019.
[44] IMPUTATO P, AVALLONE S. Design and Implementation of the Traffic Control Module in ns-3[C]//Proceedings of the 2016 ACM Workshop on Ns-3. New York, NY, USA: ACM, 2016:1-8.