时间敏感网络中基于IEEE 802.1Qch标准的优化调度机制

doi:10.11959/j.issn.1000-436x.2022183

通信学报 ›› 2022, Vol. 43 ›› Issue (9): 12-26.doi: 10.11959/j.issn.1000-436x.2022183

时间敏感网络中基于IEEE 802.1Qch标准的优化调度机制

聂宏蕊¹, 李绍胜², 刘勇¹

¹ 北京邮电大学信息与通信工程学院，北京 100876
² 北京邮电大学人工智能学院，北京 100876

修回日期:2022-09-08 出版日期:2022-09-25 发布日期:2022-09-01
作者简介:聂宏蕊（1995- ），女，河北唐山人，北京邮电大学博士生，主要研究方向为时间敏感网络、确定性网络、调度优化、自组织网络、异构网络等
李绍胜（1966- ），男，河北唐山人，博士，北京邮电大学研究员、博士生导师，主要研究方向为全移动、自组织、抗干扰通信技术、软件无线电、多媒体处理的应用技术、时间敏感网络等
刘勇（1962- ），男，湖北宜昌人，博士，北京邮电大学教授、博士生导师，主要研究方向为移动通信和多媒体通信技术，多媒体通信协议，图像压缩、识别和检索技术，时间敏感网络等
基金资助:
国家重点研发计划基金资助项目(2020YFC1511801)

Optimized scheduling mechanism based on IEEE 802.1Qch standard in time-sensitive networking

Hongrui NIE¹, Shaosheng LI², Yong LIU¹

¹ School of Information and Communication Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China
² School of Artificial Intelligence, Beijing University of Posts and Telecommunications, Beijing 100876, China

Revised:2022-09-08 Online:2022-09-25 Published:2022-09-01
Supported by:
The National Key Research and Development Program of China(2020YFC1511801)

摘要/Abstract

摘要：

针对通用的TAS复杂的门控规划的问题，借助IEEE 802.1Qch标准提出了缓存队列与硬件调度时隙自适配的高调度能力的流量调度机制。综合考虑流量与网络特征，实现调度粒度、求解时间与成本之间的平衡，基于自适应的队列与硬件调度时隙建立混合整数线性规划的路由与调度模型，旨在最大化映射到目标网络的时间敏感流数量，并通过均衡每个调度时隙所承载的流量进一步提高网络调度能力。通过不同场景得到流量与网络属性对于队列与硬件时隙长度的影响。仿真结果表明，所提算法在解决局域网的调度问题上能成功部署上千条时间敏感流量，与其他算法相比调度成功率最高可提高28%，具有可行的执行时间。

关键词: 时间敏感网络, 时间触发流量, 循环排队与转发, 调度优化, 混合整数线性规划

Abstract:

To address the problem of complex gating planning for generic time-aware shaper (TAS), a traffic scheduling mechanism of adaptive queue buffer size and hardware time slot length was proposed with the help of IEEE 802.1Qch standard.Taking traffic and network characteristics into account, a mixed integer linear programming routing and scheduling model was formulated to maximize the number of time-sensitive flows mapped to the target network and then further improve the network scheduling capability by balancing the traffic carried by each scheduling time slot.Moreover, the impact of traffic and network features on queue buffer and hardware scheduling time slot was obtained through different scenarios.Simulation results show that the proposed method could successfully deploy thousands of time-sensitive flows for solving the scheduling problem in local area networks, and can improve the scheduling success rate by up to 28% compared with other algorithms with feasible execution time.

Key words: time-sensitive networking, time-triggered traffic, cyclic queuing and forwarding, scheduling optimization, mixed integer linear programming

中图分类号:

TP393

聂宏蕊, 李绍胜, 刘勇. 时间敏感网络中基于IEEE 802.1Qch标准的优化调度机制[J]. 通信学报, 2022, 43(9): 12-26.

Hongrui NIE, Shaosheng LI, Yong LIU. Optimized scheduling mechanism based on IEEE 802.1Qch standard in time-sensitive networking[J]. Journal on Communications, 2022, 43(9): 12-26.

图/表 12

图1

图2

图3

表1

系统参数"

符号	含义
G= (V,E)	网络拓扑
$F = {f_{1}, \dots, f_{K}}$	流量集合
fk.src	流 fk 的源端系统
fk.dest	流 fk 的目标端系统
fk.size	流 fk 的帧长度
fk.prd	流 fk 的周期
fk.ddl	流 fk 的允许的最大端到端时延
f_k.route	流 fk 的传输路径
f_k.φ	流 fk 的注入网络时隙
$r_{e_{i j}}^{f_{k}}$	流 fk 在链路(vi,v j)上的占用情况
Tschedule	交换机出端口的调度周期
Lslot	硬件调度时隙
Lqueue	交换机中CQF队列长度
period_set	流量周期所组成的向量

表1

图4

表2

图5

图6

图7

图8

图9

图10

参考文献 26

[1]	YANG X R , SUN Z G , LI J N ,et al． FAST:enabling fast software/hardware prototype for network experimentation［C］// Proceedings of the International Symposium on Quality of Service． Piscataway:IEEE Press, 2019: 1-10．
[2]	NASRALLAH A , THYAGATURU A S , ALHARBI Z ,et al． Ultra-low latency (ULL) networks:the IEEE TSN and IETF detnet standards and related 5g ull research［J］． IEEE Communications Surveys ＆ Tutorials, 2019,21(1): 88-145．
[3]	IEEE． IEEE standard for local and metropolitan area networks—bridges and bridged networks—amendment:IEEE 802．1 Qbv［S］． 2015．
[4]	IEEE． IEEE Standard for local and metropolitan area networks—bridges and bridged networks—amendment 29:cyclic queuing and forwarding:IEEE 802．1Qch［S］． 2017．
[5]	NASRALLAH A , BALASUBRAMANIAN V , THYAGATURU A ,et al． TSN algorithms for large scale networks:a survey and conceptual comparison［J］． arXiv Preprint,arXiv:1905．08478, 2019．
[6]	YAN J L , QUAN W , JIANG X Y ,et al． Injection time planning:making CQF practical in time-sensitive networking［C］// Proceedings of IEEE Conference on Computer Communications． Piscataway:IEEE Press, 2020: 616-625．
[7]	QUAN W , YAN J L , JIANG X Y ,et al． On-line traffic scheduling optimization in IEEE 802.1Qch based time-sensitive networks［C］// 2020 IEEE 22nd International Conference on High Performance Computing and Communications; IEEE 18th International Conference on Smart City; IEEE 6th International Conference on Data Science and Systems． Piscataway:IEEE Press, 2020: 369-376．
[8]	LAURSEN S M , POP P , STEINER W ． Routing optimization of AVB streams in TSN networks［J］． SIGBED Rev, 2016,13: 43-48．
[9]	PAHLEVAN M , OBERMAISSER R ． Genetic algorithm for scheduling time-triggered traffic in time-sensitive networks［C］// Proceedings of IEEE 23rd International Conference on Emerging Technologies and Factory Automation． Piscataway:IEEE Press, 2018: 337-344．
[10]	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．
[11]	ARESTOVA A , HIELSCHER K S J , GERMAN R ． Design of a hybrid genetic algorithm for time-sensitive networking［C］// Measurement,Modelling and Evaluation of Computing Systems． Berlin:Springer, 2020: 99-117．
[12]	GAVRILU? V , ZHAO L X , RAAGAARD M L ,et al． AVB-aware routing and scheduling of time-triggered traffic for TSN［J］． IEEE Access, 2018,6: 75229-75243．
[13]	POZO F , STEINER W , RODRIGUEZ-NAVAS G ,et al． A decomposition approach for SMT-based schedule synthesis for time-triggered networks［C］// Proceedings of IEEE 20th Conference on Emerging Technologies ＆ Factory Automation． Piscataway:IEEE Press, 2015: 1-8．
[14]	CRACIUNAS S S , OLIVER R S ． SMT-based task- and network-level static schedule generation for time-triggered networked systems［C］// Proceedings of the 22nd International Conference on Real-Time Networks and Systems． New York:ACM Press, 2014: 45-54．
[15]	CRACIUNAS S S , OLIVER R S , CHMELíK 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:ACM Press, 2016: 183-192．
[16]	NAYAK N G , DüRR F ,, ROTHERMEL K ． Time-sensitive software-defined network (TSSDN) for real-time applications［C］// Proceedings of the 24th International Conference on Real-Time Networks and Systems． New York:ACM Press, 2016: 193-202．
[17]	WANG N C , YU Q H , WAN H ,et al． Adaptive scheduling for multicluster time-triggered train communication networks［J］． IEEE Transactions on Industrial Informatics, 2019,15(2): 1120-1130．
[18]	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．
[19]	DüRR F , NAYAK N G ． No-wait packet scheduling for IEEE time-sensitive networks (TSN)［C］// 2016 24th International Conference on Real-Time Networks and Systems． New York:ACM Press, 2016: 203-212．
[20]	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．
[21]	邱雪松, 黄徐川, 李文萃 ,等．面向大规模时间敏感网络的分组调度机制［J］．通信学报, 2020,41(11): 124-131．
	QIU X S , HUANG X C , LI W C ,et al． Group-scheduling mechanism for large-scale time-sensitive network［J］． Journal on Communications, 2020,41(11): 124-131．
[22]	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．
[23]	STEINER W , ． An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks［C］// Proceedings of 31st IEEE Real-Time Systems Symposium． Piscataway:IEEE Press, 2010: 375-384．
[24]	IEEE． IEEE standard for local and metropolitan area networks-bridges and bridged networks - amendment 31:stream reservation protocol (SRP) enhancements and performance improvement:IEEE 802．1Qcc［S］． 2018．
[25]	IEEE． IEEE standard for local and metropolitan area network--bridges and bridged networks:IEEE Std 802．1Q-2018 (Revision of IEEE Std 802．1Q-2014［S］． 2018．
[26]	HUANG Y D , WANG S , FENG T ,et al． Towards network-wide scheduling for cyclic traffic in IP-based deterministic networks［C］// Proceedings of 4th International Conference on Hot Information-Centric Networking (HotICN)． Piscataway:IEEE Press, 2021: 117-122．

参数	值
T_schedule	LCM(period_set)
L_slot/μs	200
L_queue/B	12 000
period_set/μs	{1 000,2 000,4 000,8 000}
f.size/B	125～1 500（均为125的倍数）
仿真拓扑结构	线性拓扑，环形拓扑，雪花形拓扑

时间敏感网络中基于IEEE 802.1Qch标准的优化调度机制

Optimized scheduling mechanism based on IEEE 802.1Qch standard in time-sensitive networking

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 26

相关文章 13

Metrics

推荐阅读 0

[1]	刘帅, 关杰, 胡斌, 马宿东. 基于MILP的轻量级密码算法ACE的差分分析[J]. 通信学报, 2023, 44(1): 39-48.
[2]	尹长川, 李妍珏, 朱海龙, 何欣欣, 韩文璇. HSTC：TSN中的混合流量调度机制[J]. 通信学报, 2022, 43(6): 119-132.
[3]	杨思锦, 庄雷, 宋玉, 王家兴, 阳鑫宇. 多模态网络中时间敏感网络模态的智能调度机制[J]. 通信学报, 2022, 43(5): 82-91.
[4]	裴金川, 胡宇翔, 田乐, 胡涛, 李子勇. 联合路由规划的时间敏感网络流量调度方法[J]. 通信学报, 2022, 43(12): 54-65.
[5]	孙雷, 王健全, 林尚静, 马彰超, 李卫, Qilian Liang, 黄蓉. 基于无线信道信息的5G与TSN联合调度机制研究[J]. 通信学报, 2021, 42(12): 65-75.
[6]	汪硕, 黄玉栋, 黄韬, 霍如, 刘韵洁. 基于软件定义的时间敏感网络跨域调度机制[J]. 通信学报, 2021, 42(10): 1-9.
[7]	梁若舟, 赵曦滨, 万海. 针对工业控制拓扑的确定性局部多点故障检测方法[J]. 通信学报, 2021, 42(10): 10-22.
[8]	苏建忠, 张华宇, 朱海龙. 结合SDN控制器的TSN周期性带宽预留值计算方法[J]. 通信学报, 2021, 42(10): 23-31.
[9]	蔡岳平, 李栋, 许驰, 王振, 张潇文. 面向工业互联网的5G-U与时间敏感网络融合架构与技术[J]. 通信学报, 2021, 42(10): 43-54.
[10]	伏玉笋,杨根科. 无线超可靠低时延通信：关键设计分析与挑战[J]. 通信学报, 2020, 41(8): 187-203.
[11]	邱雪松,黄徐川,李文萃,李温静,郭少勇. 面向大规模时间敏感网络的分组调度机制[J]. 通信学报, 2020, 41(11): 124-131.
[12]	黄韬,汪硕,黄玉栋,郑尧,刘江,刘韵洁. 确定性网络研究综述[J]. 通信学报, 2019, 40(6): 160-176.
[13]	张晶,陆音,高西奇,郑福春. 主用户干扰约束下的机会频谱接入感知-传输时隙优化调度[J]. 通信学报, 2013, 34(12): 42-48.