时间敏感网络中的动态路由与调度联合优化算法

doi:10.11959/j.issn.2096-3750.2023.00318

摘要/Abstract

摘要：

时间敏感网络（TSN, time-sensitive networking）是由IEEE TSN工作组制定的以太网通信标准，致力于在以太网底层实现统一的确定性网络通信。由于 TSN 没有定义流量调度的具体实现方法，路由与调度算法研究仍然是TSN研究领域的一个开放问题。面向工业应用中的TSN建立路由与调度联合优化问题模型，并提出一个在线启发式算法求解动态流量的路由与调度方案。算法同时考虑传输时延和网络负载因素确定路由路径，并利用两次剪裁操作快速确定调度时间。最后基于OMNeT的NeSTiNg框架实现TSN仿真环境。仿真结果表明，所提算法与参考算法相比，随着网络规模和网络流量增加始终可以在较短时间内完成增量流量的调度，保证了动态变化网络环境下实时流量的传输性能。

关键词: 时间敏感网络, 802.1Qbv, 路由, 在线调度

Abstract:

Time-sensitive networking (TSN) is a set of protocols developed by the IEEE TSN task group, aiming at achieving deterministic communications over Ethernet.As the implementation method of TSN traffic scheduling is not specified in the protocols, the routing and scheduling algorithm for TSN remains an open issue.The joint optimization problem of routing and scheduling in TSN for industrial applications was modeled, and then an online heuristic algorithm was proposed to deliver the routing and scheduling solution for dynamic traffics.The routing path was determined by optimizing both the transmission delay and network load factors, and the scheduling time was quickly conducted by twice clipping operations.Finally, a simulated TSN testbed was developed with NeSTiNg framework based on OMNeT.The simulation results show that the execution time of the proposed algorithm outperforms the baseline algorithms even with large scale of network size and network traffics.It shows that the proposed algorithm guarantees the real-time performance even in dynamically changing networks.

Key words: time-sensitive networking, 802.1Qbv, routing, online scheduling

中图分类号:

TP393

周阳, 陈鸿龙, 张雷. 时间敏感网络中的动态路由与调度联合优化算法[J]. 物联网学报, 2023, 7(4): 52-62.

Yang ZHOU, Honglong CHEN, Lei ZHANG. An algorithm for joint optimization of dynamic routing and scheduling in time-sensitive networking[J]. Chinese Journal on Internet of Things, 2023, 7(4): 52-62.

图/表 9

图1

图2

图3

图4

图5

图6

图7

图8

图9

参考文献 32

[1]	蔡岳平, 姚宗辰, 李天驰 . 时间敏感网络标准与研究综述[J]. 计算机学报, 2021,44(7): 1378-1397.
	CAI Y P , YAO Z C , LI T C . A survey on time-sensitive networking:standards and state-of-the-art[J]. Chinese Journal of Computers, 2021,44(7): 1378-1397.
[2]	FINN N . Introduction to time-sensitive networking[J]. IEEE Communications Standards Magazine, 2018,2(2): 22-28.
[3]	LOBELLO L , STEINER W . A perspective on IEEE time-sensitive networking for industrial communication and automation systems[J]. Proceedings of the IEEE, 2019,107(6): 1094-1120.
[4]	ZHAO L , HE F , LI E S ,et al. Comparison of time sensitive networking (TSN) and TTEthernet[C]// Proceedings of 2018 IEEE/AIAA 37th Digital Avionics Systems Conference (DASC). Piscataway:IEEE Press, 2018: 1-7.
[5]	STEINER W . Synthesis of static communication schedules for mixed-criticality systems[C]// Proceedings of 2011 14th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing Workshops. Piscataway:IEEE Press, 2011: 11-18.
[6]	DüRR F , NAYAK N G . No-wait packet scheduling for IEEE time-sensitive networks (TSN)[C]// Proceedings of RTNS '16:Proceedings of the 24th International Conference on Real-Time Networks and Systems.[S.l.:s.n.], 2016: 203-212.
[7]	LI Q , LI D , JIN X ,et al. A simple and efficient time-sensitive networking traffic scheduling method for industrial scenarios[J]. Electronics, 2020,9(12): 2131.
[8]	张彤, 冯佳琦, 马延滢 ,等. 时间敏感网络流量调度综述[J]. 计算机研究与发展, 2022,59(4): 747-764.
	ZHANG T , FENG J Q , MA Y Y ,et al. Survey on traffic scheduling in time-sensitive networking[J]. Journal of Computer Research and Development, 2022,59(4): 747-764.
[9]	SCHWEISSGUTH E , DANIELIS P , TIMMERMANN D ,et al. ILP-based joint routing and scheduling for time-triggered networks[C]// Proceedings of RTNS '17:Proceedings of the 25th International Conference on Real-Time Networks and Systems.[S.l.:s.n.], 2017: 8-17.
[10]	FALK J , DüRR F , ROTHERMEL K . Exploring practical limitations of joint routing and scheduling for TSN with ILP[C]// Proceedings of 2018 IEEE 24th International Conference on Embedded and Real-Time Computing Systems and Applications. Piscataway:IEEE Press, 2018: 136-146.
[11]	SCHWEISSGUTH E , TIMMERMANN D , PARZYJEGLA H ,et al. ILP-based routing and scheduling of multicast realtime traffic in time-sensitive networks[C]// Proceedings of 2020 IEEE 26th International Conference on Embedded and Real-Time Computing Systems and Applications. Piscataway:IEEE Press, 2020: 1-11.
[12]	HELLMANNS D , HAUG L , HILDEBRAND M ,et al. How to optimize joint routing and scheduling models for TSN using integer linear programming[C]// Proceedings of RTNS'2021:29th International Conference on Real-Time Networks and Systems.[S.l.:s.n.], 2021: 100-111.
[13]	PAHLEVAN M , OBERMAISSER R . Genetic algorithm for scheduling time-triggered traffic in time-sensitive networks[C]// Proceedings of 2018 IEEE 23rd International Conference on Emerging Technologies and Factory Automation. Piscataway:IEEE Press, 2018: 337-344.
[14]	ALNAJIM A , SALEHI S , SHEN C C . Incremental path-selection and scheduling for time-sensitive networks[C]// Proceedings of 2019 IEEE Global Communications Conference. Piscataway:IEEE Press, 2019: 1-6.
[15]	SONG Y , GUO C Y , XU P F ,et al. Research on routing and scheduling algorithms for the simultaneous transmission of diverse data streaming services on the industrial Internet[J]. Scientific Reports, 2021(11): 18351.
[16]	ATALLAH A A , HAMAD G B , MOHAMED O A . Routing and scheduling of time-triggered traffic in time-sensitive networks[J]. IEEE Transactions on Industrial Informatics, 2020,16(7): 4525-4534.
[17]	LI H T , CHENG H , YANG L . Reliable routing and scheduling in time-sensitive networks[C]// Proceedings of 2021 17th International Conference on Mobility,Sensing and Networking (MSN). Piscataway:IEEE Press, 2021: 806-811.
[18]	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): 44165-44181.
[19]	REUSCH N , ZHAO L X , CRACIUNAS S S ,et al. Window-based schedule synthesis for industrial IEEE 802.1Qbv TSN networks[C]// Proceedings of 2020 16th IEEE International Conference on Factory Communication Systems. Piscataway:IEEE Press, 2020: 1-4.
[20]	周小明, 仇梓鑫, 朱瑾瑜 ,等. 一种时间敏感网络GCL自适应调整算法[J]. 北京邮电大学学报, 2022,45(1): 26-32.
	ZHOU X M , QIU Z X , ZHU J Y ,et al. GCL adaptive adjustment algorithm in time sensitive networks[J]. Journal of Beijing University of Posts and Telecommunications, 2022,45(1): 26-32.
[21]	冯泽坤, 龚龙庆, 徐丹妮 ,等. 时间敏感网络中基于 ILP 的动态流量均衡调度算法[J]. 微电子学与计算机, 2021,38(6): 33-37.
	FENG Z K , GONG L Q , XU D N ,et al. ILP-based dynamic flow balancing scheduling algorithm in time sensitive network[J]. Microelectronics ＆ Computer, 2021,38(6): 33-37.
[22]	HUANG Y D , WANG S , HUANG T ,et al. Online routing and scheduling for time-sensitive networks[C]// Proceedings of 2021 IEEE 41st International Conference on Distributed Computing Systems. Piscataway:IEEE Press, 2021: 272-281.
[23]	HUANG K , WU J K , JIANG X W ,et al. A period-aware routing method for IEEE 802.1Qbv TSN networks[J]. Electronics, 2020,10(1): 58.
[24]	LI Y T , JIANG J H , HONG S H . Joint traffic routing and scheduling algorithm eliminating the nondeterministic interruption for TSN networks used in IIoT[J]. IEEE Internet of Things Journal, 2022,9(19): 18663-18680.
[25]	SYED A A , AYAZ S , LEINMüLLER T ,et al. Fault-tolerant dynamic scheduling and routing for TSN based in-vehicle networks[C]// Proceedings of 2021 IEEE Vehicular Networking Conference. Piscataway:IEEE Press, 2021: 72-75.
[26]	YU Q H , WAN H , ZHAO X B ,et al. Online scheduling for dynamic VM migration in multicast time-sensitive networks[J]. IEEE Transactions on Industrial Informatics, 2020,16(6): 3778-3788.
[27]	LI C , ZHANG C Y , ZHENG W ,et al. Joint routing and scheduling for dynamic applications in multicast time-sensitive networks[C]// Proceedings of 2021 IEEE International Conference on Communications Workshops. Piscataway:IEEE Press, 2021: 1-6.
[28]	IEEE standard for local and metropolitan area networks -timing and synchronization for time-sensitive applications in bridged local area networks[J]. IEEE Std 802 1AS-2011, 2011: 1-292.
[29]	IEEE standard for local and metropolitan area networks – bridges and bridged networks - amendment 25:enhancements for scheduled traffic[J]. IEEE Std.802.1Qbv-2015, 2015.
[30]	HELLMANNS D , GLAVACKIJ A , FALK J ,et al. Scaling TSN scheduling for factory automation networks[C]// Proceedings of 2020 16th IEEE International Conference on Factory Communication Systems. Piscataway:IEEE Press, 2020: 1-8.
[31]	FALK J , HELLMANNS D , CARABELLI B ,et al. NeSTiNg:simulating IEEE time-sensitive networking (TSN) in OMNeT++[C]// Proceedings of 2019 International Conference on Networked Systems (NetSys). Piscataway:IEEE Press, 2019: 1-8.
[32]	NAYAK N G , DüRR F , ROTHERMEL K . Incremental flow scheduling and routing in time-sensitive software-defined networks[J]. IEEE Transactions on Industrial Informatics, 2018,14(5): 2066-2075.