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

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

Abstract

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

CLC Number:

TP393

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.

Figures/Tables 14

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

Metrics

Recommended 0

No Suggested Reading articles found!

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

流数量	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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 35

Related Articles 15

Metrics

Recommended 0

[1]	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.
[2]	Zongxuan SHA, Ru HUO, Chuang SUN, Shuo WANG, Tao HUANG. Forwarding efficiency aware traffic scheduling algorithm based on deep reinforcement learning [J]. Journal on Communications, 2022, 43(8): 30-40.
[3]	Changchuan YIN, Yanjue LI, Hailong ZHU, Xinxin HE, Wenxuan HAN. HSTC: hybrid traffic scheduling mechanism in time-sensitive networking [J]. Journal on Communications, 2022, 43(6): 119-132.
[4]	Sijin YANG, Lei ZHUANG, Yu SONG, Jiaxing WANG, Xinyu YANG. Intelligent scheduling mechanism of time-sensitive network modal in polymorphic network [J]. Journal on Communications, 2022, 43(5): 82-91.
[5]	Lei SUN, Jianquan WANG, Shangjing LIN, Zhangchao MA, Wei LI, Liang Qilian, Rong HUANG. Research on 5G-TSN joint scheduling mechanism based on radio channel information [J]. Journal on Communications, 2021, 42(12): 65-75.
[6]	Shuo WANG, Yudong HUANG, Tao HUANG, Ru HUO, Yunjie LIU. Software-defined cross-domain scheduling mechanism for time-sensitive networking [J]. Journal on Communications, 2021, 42(10): 1-9.
[7]	Ruozhou LIANG, Xibin ZHAO, Hai WAN. Deterministic local multi-point fault detection method for industrial control topology [J]. Journal on Communications, 2021, 42(10): 10-22.
[8]	Yueping CAI, Dong LI, Chi XU, Zhen WANG, Xiaowen ZHANG. Integrating 5G-U with time-sensitive networking for industrial Internet: architectures and technologies [J]. Journal on Communications, 2021, 42(10): 43-54.
[9]	Yaomin WANG,Xia WANG,Yi DONG,Songhai ZHANG,Xinling SHI. Data center traffic scheduling strategy based on Fibonacci tree optimization algorithm [J]. Journal on Communications, 2020, 41(6): 112-127.
[10]	Xuesong QIU,Xuchuan HUANG,Wencui LI,Wenjing LI,Shaoyong GUO. Group-scheduling mechanism for large-scale time-sensitive network [J]. Journal on Communications, 2020, 41(11): 124-131.
[11]	Qian DONG,Jun LI,Yuxiang MA. Traffic scheduling method based on centralized control in named data networking [J]. Journal on Communications, 2018, 39(7): 68-80.
[12]	Qian DONG,Jun LI,Yuxiang MA,Shujun HAN. Traffic scheduling method based on segment routing in software-defined networking [J]. Journal on Communications, 2018, 39(11): 23-35.
[13]	Cheng-long SU,Guang JIN,Xian-liang JIANG,Jun NIU. Active queue management algorithm focusing on fairness and low delay [J]. Journal on Communications, 2017, 38(5): 199-206.
[14]	gang CHENZhi,jian SHENXiao,Li LIU. Minimal coding cost and low delay multicast routing of wireless mesh networks [J]. Journal on Communications, 2016, 37(1): 10-16.
[15]	Rui-fang LI,Quan LIU,Ren-fa LI. Spectrum access scheme of MAC layer for real-time traffic in cognitive radio network [J]. Journal on Communications, 2014, 35(4): 35-43.