联合路由规划的时间敏感网络流量调度方法

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

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

联合路由规划的时间敏感网络流量调度方法

裴金川, 胡宇翔, 田乐, 胡涛, 李子勇

信息工程大学信息技术研究所，河南郑州 450002

修回日期:2022-10-13 出版日期:2022-12-25 发布日期:2022-12-01
作者简介:裴金川（1998- ），男，河北唐山人，信息工程大学博士生，主要研究方向为时间敏感网络
胡宇翔（1982- ），男，河南周口人，博士，信息工程大学教授、博士生导师，主要研究方向为新型网络体系结构、路由与交换技术
田乐（1987- ），男，陕西咸阳人，博士，信息工程大学副研究员，主要研究方向为新型网络体系结构、时间敏感网络、路由与交换技术
胡涛（1993- ），男，陕西武功人，博士，信息工程大学助理研究员，主要研究方向为软件定义网络、人工智能
李子勇（1995- ），男，安徽蚌埠人，信息工程大学博士生，主要研究方向为软件定义网络、网络安全
基金资助:
国家重点研发计划基金资助项目(2019YFB1802505);国家重点研发计划基金资助项目(2020YFB1806402);河南省中原学者基金资助项目(224000510002)

Time-sensitive network traffic scheduling method with joint routing planning

Jinchuan PEI, Yuxiang HU, Le TIAN, Tao HU, Ziyong LI

Institute of Information Technology, Information Engineering University, Zhengzhou 450002, China

Revised:2022-10-13 Online:2022-12-25 Published:2022-12-01
Supported by:
The National Key Research and Development Program of China(2019YFB1802505);The National Key Research and Development Program of China(2020YFB1806402);Central Plains Scholars Program in Henan Province(224000510002)

摘要/Abstract

摘要：

为解决时间敏感网络中时间敏感流量调度与路由分离导致的端到端传输时延不确定的问题，提出了一种联合路由规划的多约束流量调度方法。所提方法结合时间敏感流量的流间冲突度，灵活分配流量路由，在此基础上建立时间感知整形和联合无冲突路由的调度约束模型，在时间和空间2个维度严格保障时间敏感流量调度的有界低时延需求。实验结果表明，所提方法在不同类型拓扑场景下均表现出良好的时延性能，在保证链路均衡负载的同时，有效降低了不同时间敏感流量规模下由于拥塞冲突而产生的时延。

关键词: 时间敏感网络, 时间敏感流量, 流量调度, 无冲突路由, 低时延

Abstract:

To solve the problem of uncertain end-to-end transmission delay caused by the separation of time-sensitive traffic scheduling and routing in time-sensitive network, a multi-constrained traffic scheduling method with joint routing planning was proposed.The inter-flow conflict degree of time-sensitive traffic was introduced to flexibly allocated traffic routing.On that basis, a scheduling constraint model of time-aware shaping and joint conflict-free routing was established to strictly guarantee the time-sensitive traffic scheduling with bounded low latency in both spatial and temporal dimensions.Experimental results show that the proposed method has good delay performance in different topological scenarios, and effectively reduces the delay caused by congestion conflicts under different time-sensitive traffic scales while ensuring link load balancing.

Key words: time-sensitive network, time-sensitive traffic, traffic scheduling, conflict-free routing, low delay

中图分类号:

TP393

裴金川, 胡宇翔, 田乐, 胡涛, 李子勇. 联合路由规划的时间敏感网络流量调度方法[J]. 通信学报, 2022, 43(12): 54-65.

Jinchuan PEI, Yuxiang HU, Le TIAN, Tao HU, Ziyong LI. Time-sensitive network traffic scheduling method with joint routing planning[J]. Journal on Communications, 2022, 43(12): 54-65.

图/表 14

图1

图2

图3

图4

图5

图6

表1

图7

图8

表2

表3

图9

图10

图11

参考文献 35

[1]	黄韬, 刘江, 汪硕 ,等. 未来网络技术与发展趋势综述[J]. 通信学报, 2021,42(1): 130-150.
	HUANG T , LIU J , WANG S ,et al. Survey of the future network technology and trend[J]. Journal on Communications, 2021,42(1): 130-150.
[2]	黄韬, 汪硕, 黄玉栋 ,等. 确定性网络研究综述[J]. 通信学报, 2019,40(6): 160-176.
	HUANG T , WANG S , HUANG Y D ,et al. Survey of the deterministic network[J]. Journal on Communications, 2019,40(6): 160-176.
[3]	胡宇翔, 伊鹏, 孙鹏浩 ,等. 全维可定义的多模态智慧网络体系研究[J]. 通信学报, 2019,40(8): 1-12.
	HU Y X , YI P , SUN P H ,et al. Research on the full-dimensional defined polymorphic smart network[J]. Journal on Communications, 2019,40(8): 1-12.
[4]	MESSENGER J L . Time-sensitive networking:an introduction[J]. IEEE Communications Standards Magazine, 2018,2(2): 29-33.
[5]	LIU Y , ZHOU Y Q , YUAN J H ,et al. Delay aware flow scheduling for time sensitive fronthaul networks in centralized radio access network[J]. IEEE Transactions on Communications, 2020,68(5): 2992-3009.
[6]	WG802.1.IEEE standard for local and metropolitan area networks-timing and synchronization for time-sensitive applications:IEEE Std 802.1 AS-2020 (Revision of IEEE Std 802.1 AS-2011)[S]. 2020.
[7]	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]. 2016.
[8]	WG802.1.IEEE standard for local and metropolitan area networks–frame replication and elimination for reliability:IEEE Std 802.1 CB-2017[S]. 2017.
[9]	WG802.1.IEEE standard for local and metropolitan area networks--bridges and bridged networks - - amendment 31:stream reservation protocol (SRP) enhancements and performance improvements:IEEE Std 802.1Qcc-2018[S]. 2018.
[10]	张彤, 冯佳琦, 马延滢 ,等. 时间敏感网络流量调度综述[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.
[11]	邱雪松, 黄徐川, 李文萃 ,等. 面向大规模时间敏感网络的分组调度机制[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.
[12]	ARESTOVA A , HIELSCHER K S J , GERMAN R . Design of a hybrid genetic algorithm for time-sensitive networking[C]// International Conference on Measurement,Modelling and Evaluation of Computing Systems. Berlin:Springer, 2020: 99-117.
[13]	PANG Z Y , HUANG X , LI Z H ,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.
[14]	VLK M . Constraint programming approaches to joint routing and scheduling in time-sensitive networks[J]. Computers ＆ Industrial Engineering, 2021,157:107317.
[15]	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.
[16]	GAVRILUT V , ZARRIN B , POP P ,et al. Fault-tolerant topology and routing synthesis for IEEE time-sensitive networking[C]// Proceedings of the 25th International Conference on Real-Time Networks and Systems. New York:ACM Press, 2017: 267-276.
[17]	HUANG J Y , HSU M H , SHEN C A . A novel routing algorithm for the acceleration of flow scheduling in time-sensitive networks[J]. Sensors (Basel,Switzerland), 2020,20(21): E6400.
[18]	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.
[19]	NAYAK N G , DüRR F , ROTHERMEL K . Routing algorithms for IEEE802.1Qbv networks[J]. ACM SIGBED Review, 2018,15(3): 13-18.
[20]	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.
[21]	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.
[22]	OJEWALE M A , YOMSI P M . Routing heuristics for load-balanced transmission in TSN-based networks[J]. ACM SIGBED Review, 2020,16(4): 20-25.
[23]	韩文璇, 朱海龙, 何欣欣 ,等. 一种结合入队整形的 TSN 流量调度算法[J]. 物联网学报, 2022:doi.org/10.11959/j.issn.2096-3750.2022.00296.
	HAN W X , ZHU H L , HE X X ,et al. A TSN traffic scheduling algorithm combined with enqueue shaping[J]. Chinese Journal on Internet of Things, 2022:doi.org/10.11959/j.issn.2096-3750.2022.00296.
[24]	XU L , XU Q M , ZHANG Y Z ,et al. Co-design approach of scheduling and routing in time sensitive networking[C]// Proceedings of IEEE Conference on Industrial Cyberphysical Systems. Piscataway:IEEE Press, 2020: 111-116.
[25]	VLK M , BREJCHOVá K , HANZáLEK Z ,et al. Large-scale periodic scheduling in time-sensitive networks[J]. Computers ＆ Operations Research, 2022,137:105512.
[26]	伍仲丽, 曹园园, 黄文睿 ,等. 面向确定性网络的按需智能路由技术[J]. 电信科学, 2021,37(11): 11-16.
	WU Z L , CAO Y Y , HUANG W R ,et al. On-demand intelligent routing technology for deterministic network[J]. Telecommunications Science, 2021,37(11): 11-16.
[27]	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.
[28]	GROSSMAN E . Deterministic networking use cases[R]. RFC Editor, 2019.
[29]	ZHANG Y Z , XU Q M , XU L ,et al. Efficient flow scheduling for industrial time-sensitive networking:a divisibility theory-based method[J]. IEEE Transactions on Industrial Informatics, 2022,18(12): 9312-9323.
[30]	ZHOU Y B , 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.
[31]	HAUR N K , CHIN T S . Time-sensitive-aware scheduling traffic (TSA-ST) algorithm in software-defined networking[C]// Proceedings of International Conference on Internet and Distributed Computing Systems. Berlin:Springer, 2019: 248-259.
[32]	BARABASI A L , ALBERT R . Emergence of scaling in random networks[J]. Science, 1999,286(5439): 509-512.
[33]	ERDOS P , RéNYI A , . On the evolution of random graphs[J]. Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 1960,5(1): 17-60.
[34]	GAVRILU? V , POP P . Traffic-type assignment for TSN-based mixed-criticality cyber-physical systems[J]. ACM Transactions on Cyber-Physical Systems, 2020,4(2): 1-27.
[35]	苏建忠, 张华宇, 朱海龙 . 结合SDN控制器的TSN周期性带宽预留值计算方法[J]. 通信学报, 2021,42(10): 23-31.
	SU J Z , ZHANG H Y , ZHU H L . Computing method for periodic stream reservation in TSN combined with SDN controller[J]. Journal on Communications, 2021,42(10): 23-31.

流数量	CF	RTRS	D/MM	D/SAP
5	16.27%	16.27%	16.27%	32.27%
10	23.10%	24.15%	20.62%	32.27%
15	25.18%	27.56%	25.67%	32.27%
20	28.27%	32.54%	28.27%	50.67%
25	29.26%	32.54%	28.27%	50.67%
30	30.22%	35.67%	30.64%	54.28%
35	31.67%	38.58%	35.60%	60.42%
40	31.80%	40.28%	36.16%	60.42%

流数量	CF	RTRS	D/MM	D/SAP
5	8.25%	8.42%	7.80%	11.69%
10	8.36%	8.95%	8.62%	11.39%
15	9.45%	10.07%	8.62%	13.72%
20	9.75%	10.94%	9.83%	13.47%
25	10.95%	12.13%	11.06%	14.95%
30	10.96%	12.46%	11.36%	14.51%
35	10.96%	13.97%	12.05%	15.44%
40	12.54%	15.21%	13.02%	17.66%

联合路由规划的时间敏感网络流量调度方法

Time-sensitive network traffic scheduling method with joint routing planning

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 35

相关文章 15

Metrics

推荐阅读 0

拓扑场景	交换节点数量/个	终端节点数量/个	链路数量/条
ER₁	5	5	13
ER₂	12	8	25
BA₁	6	4	16
BA₂	12	8	36

[1]	秦武韬, 王鹏, 李玉峰. 基于周期耦合处理的CAN总线数据组合加密方法[J]. 通信学报, 2023, 44(1): 29-38.
[2]	聂宏蕊, 李绍胜, 刘勇. 时间敏感网络中基于IEEE 802.1Qch标准的优化调度机制[J]. 通信学报, 2022, 43(9): 12-26.
[3]	沙宗轩, 霍如, 孙闯, 汪硕, 黄韬. 基于深度强化学习的转发效能感知流量调度算法[J]. 通信学报, 2022, 43(8): 30-40.
[4]	尹长川, 李妍珏, 朱海龙, 何欣欣, 韩文璇. HSTC：TSN中的混合流量调度机制[J]. 通信学报, 2022, 43(6): 119-132.
[5]	杨思锦, 庄雷, 宋玉, 王家兴, 阳鑫宇. 多模态网络中时间敏感网络模态的智能调度机制[J]. 通信学报, 2022, 43(5): 82-91.
[6]	孙雷, 王健全, 林尚静, 马彰超, 李卫, Qilian Liang, 黄蓉. 基于无线信道信息的5G与TSN联合调度机制研究[J]. 通信学报, 2021, 42(12): 65-75.
[7]	汪硕, 黄玉栋, 黄韬, 霍如, 刘韵洁. 基于软件定义的时间敏感网络跨域调度机制[J]. 通信学报, 2021, 42(10): 1-9.
[8]	梁若舟, 赵曦滨, 万海. 针对工业控制拓扑的确定性局部多点故障检测方法[J]. 通信学报, 2021, 42(10): 10-22.
[9]	苏建忠, 张华宇, 朱海龙. 结合SDN控制器的TSN周期性带宽预留值计算方法[J]. 通信学报, 2021, 42(10): 23-31.
[10]	蔡岳平, 李栋, 许驰, 王振, 张潇文. 面向工业互联网的5G-U与时间敏感网络融合架构与技术[J]. 通信学报, 2021, 42(10): 43-54.
[11]	孙国林,欧睿杰,刘贵松. 基于深度强化学习的应急物联网切片资源预留算法[J]. 通信学报, 2020, 41(9): 8-20.
[12]	伏玉笋,杨根科. 无线超可靠低时延通信：关键设计分析与挑战[J]. 通信学报, 2020, 41(8): 187-203.
[13]	王耀民,王霞,董易,张松海,施心陵. 基于斐波那契树优化算法的数据中心流量调度策略[J]. 通信学报, 2020, 41(6): 112-127.
[14]	邱雪松,黄徐川,李文萃,李温静,郭少勇. 面向大规模时间敏感网络的分组调度机制[J]. 通信学报, 2020, 41(11): 124-131.
[15]	左旭彤,王莫为,崔勇. 低时延网络：架构，关键场景与研究展望[J]. 通信学报, 2019, 40(8): 22-35.