计算机科学

计算机科学 ›› 2026, Vol. 53 ›› Issue (7): 324-335.doi: 10.11896/jsjkx.250400034

• 计算机网络 • 上一篇    下一篇

时间敏感网络中基于链路负载峰值的流量调度算法

徐佳, 唐群, 王乃民, 徐力杰   

  1. 南京邮电大学计算机学院 南京 210003
  • 收稿日期:2025-04-08 修回日期:2025-07-16 出版日期:2026-07-15 发布日期:2026-07-10
  • 通讯作者: 徐佳(xujia@njupt.edu.cn)
  • 基金资助:
    国家自然科学基金(62372249)

Traffic Scheduling Algorithm Based on Peak Link Load in Time-sensitive Networks

XU Jia, TANG Qun, WANG Naimin, XU Lijie   

  1. School of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210003,China
  • Received:2025-04-08 Revised:2025-07-16 Published:2026-07-15 Online:2026-07-10
  • About author:XU Jia,born in 1980,Ph.D,professor,Ph.D supervisor,is a senior member of CCF(No.18435S).His main research interests include edge computing,wireless rechargeable sensor networks and time-sensitive networks.
  • Supported by:
    National Natural Science Foundation of China(62372249).

PDF (PC)

13

摘要： 时间敏感网络(Time-Sensitive Network,TSN)标准中定义的时间感知整形器机制通过门控列表保证时间触发(Time-triggered,TT)流量的有界延迟和抖动。门控列表控制TSN交换机出口队列的打开和关闭时间,由调度算法生成。现有的调度方法采用最短路径传输TT流,或将链路状态和路由隔离,没有考虑链路状态对路由的动态影响,导致网络中部分链路负载过高。对此,提出一种基于链路负载峰值的路由与流量联合调度算法(Joint Routing and Traffic Scheduling Algorithm Based on Peak Link Load,JRTSPLL)。该方法结合负载均衡的思想,在计算最优路径的过程中实现了网络中链路负载峰值的最小化。实验结果表明,与最短路径调度算法相比,JRTSPLL的链路负载峰值降低了29.96%,调度成功率提高了23.02%,总传输时长减少了15.14%;与等代价多路径调度算法相比,JRTSPLL的链路负载峰值降低了9.52%,调度成功率提高了38.46%,总传输时长减少了14.01%。

关键词: 时间敏感网络, 时间感知整形器, 联合路由与调度, 时间触发流

Abstract: The time-aware shaper(TAS) mechanism defined in the time-sensitive network(TSN) standard ensures bounded delay and jitter of time triggered(TT) traffic through gate control list(GCL).The GCL is generated by the scheduling algorithm and controls the opening and closing time of the TSN switch out queues.The existing scheduling methods use the shortest path to transmit TT flows,or isolate link state and routing,without considering the dynamic impact of link state on routing,resulting in excessive load on some links in the network.This paper proposes a joint routing and traffic scheduling algorithm based on peak link load(JRTSPLL).The proposed method integrates the idea of load balancing to minimize the peak load of links in the network during the calculation of the optimal path.Simulation results show that,compared with the shortest path scheduling algorithm,JRTSPLL reduces the peak link load by 29.96%,increases the scheduling success rate by 23.02%,and reduces the total transmission time by 15.14%.Compared with the equal cost multi-path scheduling algorithm,JRTSPLL reduces the peak link load by 9.52%,increases the scheduling success rate by 38.46%,and reduces the total transmission time by 14.01%.

Key words: Time-sensitive network, Time-aware shaper, Joint routing and scheduling, Time-triggered traffic

中图分类号: 

  • TP393
[1]IEEE.IEEE Standard for Local and Metropolitan Area Net-works-Timing and Synchronization for Time-Sensitive Applications in Bridged Local Area Networks:802.1AS-2011[S].New York,IEEE,2011.
[2]IEEE.IEEE Approved Draft Standard for Local and Metropolitan Area Networks－Bridges and Bridged Networks－Amendment:Path Control and Reservation:802.1Qca-2015[S].New York, IEEE,2015.
[3]IEEE.IEEE Standard for Local and Metropolitan Area Net-works－Bridges and Bridged Networks－Amendment 25:Enhancements for Scheduled Traffic:802.1Qbv-2015[S].New York,IEEE,2016.
[4]DÜRR F,NAYAK N G.No-wait Packet Scheduling for IEEE Time-sensitive Networks(TSN)[C]//Proceedings of the 24th International Conference on Real-Time Networks and Systems.New York:Association for Computing Machinery,2016:203-212.
[5]CRACIUNAS S S,OLIVER R S,CHMELIK M,et al.Scheduling Real-Time Communication in IEEE 802.1Qbv Time Sensitive Networks[C]//Proceedings of the 24th International Conference on Real-Time Networks and Systems.New York:Association for Computing Machinery,2016:183-192.
[6]LI B Q,WANG Y.Hybrid-GA based static schedule generation for time-triggered ethernet[C]//2016 8th IEEE International Conference on Communication Software and Networks(ICCSN).IEEE,2016:423-427.
[7]BUJOSA D,ASHJAEIM,PAPADOPOULOS A V,et al.HERMES:Heuristic Multi-queue Scheduler for TSN Time-Triggered Traffic with Zero Reception Jitter Capabilities[C]//Proceedings of the 30th International Conference on Real-Time Networks and Systems.New York:Association for Computing Machinery,2022:70-80.
[8]VLK M,HANZÁLEK Z,TANG S.Constraint programming approaches to joint routing and scheduling in time-sensitive networks[J].Computers & Industrial Engineering,2021,157:107317.
[9]VLK M,BREJCHOVÁ K,HANZÁLEK Z,et al.Large-scaleperiodic scheduling in time-sensitive networks[J].Computers & Operations Research,2022,137:105512.
[10]SCHWEISSGUTH E,DANIELIS P,TIMMERMANN 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.
[11]SCHWEISSGUTH E,TIMMERMANN D,PARZYJEGLA H,et al.ILP-based routing and scheduling of multicast realtime traffic in time-sensitive networks[C]//2020 IEEE 26th International Conference on Embedded and Real-Time Computing Systems and Applications(RTCSA).IEEE,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 the 29th International Conference on Real-Time Networks and Systems.2021:100-111.
[13]FALK J,DÜRR F,ROTHERMEL K.Exploring practical limitations of joint routing and scheduling for TSN with ILP[C]//2018 IEEE 24th International Conference on Embedded and Real-Time Computing Systems and Applications(RTCSA).IEEE,2018:136-146.
[14]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(TECS),2021,20(5):1-24.
[15]PAHLEVAN M,OBERMAISSER R.Genetic algorithm forscheduling time-triggered traffic in time-sensitive networks[C]//2018 IEEE 23rd International Conference on Emerging Technologies and Factory Automation(ETFA).IEEE,2018:337-344.
[16]KIM H J,LEE K C,KIM M H,et al.Optimal scheduling oftime-sensitive networksfor automotive Ethernet based on gene-tic algorithm[J].Electronics,2022,11(6):926.
[17]PAHLEVAN M,TABASSAM N,OBERMAISSER R.Heuristic list scheduler for time triggered traffic in time sensitive networks[J].ACM Sigbed Review,2019,16(1):15-20.
[18]CHANG S H,CHEN H,CHENG B C.Time-predictable routing algorithm for Time-Sensitive Networking:Schedulable guarantee of Time-Triggered streams[J].Computer Communications,2021,172:183-195.
[19]HUANG K,WU J,JIANG X,et al.A period-aware routingmethod for ieee 802.1qbv tsn networks[J].Electronics,2020,10(1):58.
[20]ZHENG Y,WANG S,YIN S,et al.Mix-Flow Scheduling for Concurrent Multipath Transmission in Time-Sensitive Networking[C]//2021 IEEE International Conference on Communications Workshops(ICC Workshops).2021:1-6.
[21]MACCHIAROLI R,MOLE S,RIEMMA S.Modelling and optimization of industrial manufacturing processes subject to no-wait constraints[J].International Journal of Production Research,1999,37(11):2585-2607.
[22]XUE C,ZHANG T,ZHOU Y,et al.Real-Time Scheduling for 802.1 Qbv Time-Sensitive Networking(TSN):A Systematic Review and Experimental Study[C]//2024 IEEE 30th Real-Time and Embedded Technology and Applications Symposium(RTAS).IEEE,2024:108-121.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市两江新区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发