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

doi:10.11959/j.issn.2096-3750.2023.00318

Abstract

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

CLC Number:

TP393

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.

Figures/Tables 9

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

An algorithm for joint optimization of dynamic routing and scheduling in time-sensitive networking

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 32

Related Articles 4

Metrics

Recommended 0

[1]	Nongyu WEI, Zilong JIANG, Fangjiong CHEN. AODV protocol for acoustic-radio integrated network based on location information and energy balance [J]. Chinese Journal on Internet of Things, 2023, 7(1): 27-36.
[2]	Jinfeng YANG,Ji WANG. Research of precision agriculture WSN protocols [J]. Chinese Journal on Internet of Things, 2020, 4(4): 62-69.
[3]	Jie HU,Jie ZHAN,Baoquan REN. K connectivity algorithm based on flow network in wireless sensor networks [J]. Chinese Journal on Internet of Things, 2019, 3(3): 11-17.
[4]	Ruijin DING,Feifei GAO,Ling XING. Intelligent routing strategy in the Internet of things based on deep reinforcement learning [J]. Chinese Journal on Internet of Things, 2019, 3(2): 56-63.