Computer Science ›› 2025, Vol. 52 ›› Issue (11A): 250300028-6.doi: 10.11896/jsjkx.250300028

• Network & Communication • Previous Articles     Next Articles

Traffic Scheduling Mechanism for Time-sensitive Networks Based on Satisfiability Modulo Theories

XU Jing, LIU Chunlong, HUO Jiahao, HUANGFU Wei   

  1. School of Computer and Communication Engineering,University of Science and Technology Beijing,Beijing 100083,China
  • Online:2025-11-15 Published:2025-11-10
  • Supported by:
    Key Program of the Joint Funds of the National Natural Science Foundation of China(U22A2005) and Sub-project of the National Key Research and Development Program of the Ministry of Science and Technology of China(2022QY1403).

Abstract: Globally,the fusion of industrialization,informatization,and intelligence is significantly impacting various industries,especially in fields requiring stringent latency,such as in-vehicle systems and avionics.TSN has emerged as a key technology for achieving deterministic low-latency communications.However,TSN’s current network-level traffic scheduling mechanisms struggle to fully meet the complex priority demands of upper-layer services.To address this issue,this paper proposes an SMT-based TSN scheduling mechanism called SMT-TAS.By incorporating an SMT solver into the existing TAS model,and designing a traffic scheduling algorithm based on priority satisfaction rate,SMT-TAS enables real-time generation of optimal scheduling schemes based on dynamic business scenarios.Experimental results demonstrate that compared to traditional TAS methods,SMT-TAS improves the average priority satisfaction rate by approximately 20%,significantly enhances system schedulability,and reduces end-to-end latency by around 10%,demonstrates outstanding performance in terms of solving efficiency.Furthermore,it exhibits higher stability and reliability in large-scale tasks,effectively meeting various TSN scheduling constraints,providing strong support for the further development and application of TSN.

Key words: Time sensitive networking, Satisfiability modulo theories, Traffic scheduling, Priority assurance

CLC Number: 

  • TP393
[1]LIANG X H,HUANG H,ZHANG J,et al.Research and Trend on New Technology of Industrial Network[J].Communication &Information Technology,2022(S2):43-47.
[2]WG802.1.IEEE Standard for Local and Metropolitan Area Net-works-Timing and Synchronization for Time-Sensitive Applications:IEEE Std 802.1 AS-2020(Revision of IEEE Std 802.1 AS-2011)[S].IEEE,2020:1-421.
[3]WG802.1.IEEE Standard for Local and metropolitan area networks -- Bridges and Bridged Networks Amendment 25:Enhancements for Scheduled Traffic:IEEE Std 802.1Qbv-2015[S].IEEE,2016:1-57.
[4]WG802.1.IEEE Standard for Local and metropolitan area net-works-Frame Replication and Elimination for Reliability:IEEE Std 802.1 CB-2017[S].IEEE,2017:1-102.
[5]SCHWEISSGUTH E,DANIELIS P,TIMM-ERMANN D,et al.ILP-based joint routing and scheduling for time-triggered networks[C]//Proceedings of the 25th International Conference on Real-Time Networks and Systems.2017:8-17.
[6]POP P,RAAGAARD M L,CRACIUNAS S S,et al.Design optimisation of cyber-physical distributed systems using IEEE time-sensitive networks[J].IET Cyber-Physical Systems:Theory & Applications,2016,1(1):86-94.
[7]OLIVER R S,CRACIUNAS S S,STEINER W,et al.IEEE 802.1 Qbv gate control list synthesis using array theory encoding[C]//2018 IEEE Real-Time and Embedded Technology and Applications Symposium,2018:13-24.
[8]ZHANG Y,XU Q,XU L,et al.Efficient Flow Scheduling forIndustrial Time-Sensitive Networ-king:A Divisibility Theory Based Method[J].IEE-E Transactions on Industrial Informatics,2022,18(12):9312-9323.
[9]NAYAK N G,DURR F,ROTHERMEL K.Inc-remental FlowScheduling and Routing in Time-Sensitive Software-Defined Networks[J].IEEE Transactions on Industrial Informatics,2018,14(5):2066-2075.
[10]PANG Z,HUANG X,LI Z,et al.Flow Scheduling for Conflict-Free Network Updates in Time-Sensitive Software-Defined Networks[J].IEEE Transactions on Industrial Informatics,2021,17(3):1668-1678.
[11]HELLMANNS D,GLAVACKIJ A,FALK J,et al.Scaling TSNScheduling for Factory Automation Networks[C]//2020 16th IEEE International Conference on Factory Communication Systems.2020:23-30.
[12]KIM H J,LEE K C,KIM M H,et al.Optimal Scheduling of Time-Sensitive Networks for Automotive Ethernet Based on Genetic Algorithm[J].Electronics,2022,11(6):926.
[13]ZHOU Y,SAMII S,ELES P,et al.Reliability-aware scheduling and routing for messages in time-sensitive networking[J].ACM Transactions on Embedded Computing Systems,2021,20(5):1-24.
[14]PATTI G,BELLO L,LEONARDI L.Deadline-Aware OnlineScheduling of TSN Flows for Automotive Applications[J].IEEE Transactions on Industrial Informatics,2023,19(4):5774-5784.
[15]KIM H J,CHOI M H,KIM M H,et al.Development of an Ethernet-Based Heuristic Time-Sensitive Networking Scheduling Algorithm for Real-Time In-Vehicle Data Transmission[J].Electronics,2021,10(2):157.
[16]YAO X,GAN Z,CHEN Y,et al.Hybrid Flow Scheduling with Additional Simple Compensation Mechanisms in Time-Sensitive Networks[C]//2022 IEEE 6th Advanced Information Technology,Electronic and Automation Control Conference.2022:1315-1320.
[17]WANG S,XU Q,ZHANG Y,et al.Hybrid Traffic Scheduling Based on Adaptive Time Slot Slicing in Time-Sensitive Networking[C]//2022 IEEE International Conference on Industrial Technology.2022:1-7.
[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]TANG A,WANG X F,HE F.A survey of satisfiability modulo theories[J].Computer Engineering & Science,2024,46(3):400-415.
[1] WANG Jiaxing, YANG Sijin, ZHUANG Lei, SONG Yu, YANG Xinyu. Multi-objective Online Hybrid Traffic Scheduling Algorithm in Time-sensitive Networks [J]. Computer Science, 2023, 50(7): 286-292.
[2] DOU Hao-ming, JIANG Hui, CHEN Si-guang. SDN-based Network Controller Algorithm for Load Balancing [J]. Computer Science, 2019, 46(6A): 312-316.
[3] JIN Yong, LIU Yi-xing, WANG Xin-xin. SDN-based Multipath Traffic Scheduling Algorithm for Data Center Network [J]. Computer Science, 2019, 46(6): 90-94.
[4] ZHOU Kuan-jiu,CHANG Jun-wang,HOU Gang,REN Long-tao and WANG Xiao-long. Interrupt Modeling and Verification for Embedded Systems Based on Time Petri Nets [J]. Computer Science, 2014, 41(9): 205-209.
[5] . Detecting Behavioral Mismatch of Web Services Based on Bounded Model Checking [J]. Computer Science, 2012, 39(6): 129-132.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!