Queue assignment for fixed-priority real-time flows in time-sensitive networks: Hardness and algorithm

被引:11
作者
Lin, Yuhan [1 ]
Jin, Xi [2 ]
Zhang, Tianyu [1 ]
Han, Meiling [3 ]
Guan, Nan [4 ]
Deng, Qingxu [1 ]
机构
[1] Northeastern Univ, Shenyang, Peoples R China
[2] Chinese Acad Sci, Shenyang Inst Automat, Guangzhou, Peoples R China
[3] Nanjing Univ Posts & Telecommun, Nanjing, Peoples R China
[4] Hong Kong Polytech Univ, Hong Kong, Peoples R China
基金
中国国家自然科学基金;
关键词
Resource management; Industrial internet of things; Real-time scheduling; Time-sensitive networks; CONTROLLER-AREA-NETWORK; SCHEDULABILITY ANALYSIS;
D O I
10.1016/j.sysarc.2021.102141
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Time sensitive networks (TSNs) enable deterministic real-time communication over Ethernet networks. According to IEEE 802.1Qbv standards, TSN switches use gates between queues and their corresponding egress ports to facilitate timing-deterministic communications. Management of switch resources, such as queues, has a significant impact on the schedulability of real-time flows. In this paper, we look into the theoretical foundation of queue management in TSN switches. We prove that the queue assignment problem for realtime flows on time sensitive networks under static priority scheduling is NP-hard in the strong sense, even if the number of queues per port is 3. Then we formulate the problem as a satisfiability modulo theories (SMT) specification. Besides, we propose a worst case response time analysis and a fast heuristic algorithms by eliminating scheduling conflicts. Experiments with randomly generated workload demonstrate the effectiveness of our algorithms for queue assignment of real-time flows.
引用
收藏
页数:11
相关论文
共 32 条
[21]   Incremental Flow Scheduling and Routing in Time-Sensitive Software-Defined Networks [J].
Nayak, Naresh Ganesh ;
Duerr, Frank ;
Rothermel, Kurt .
IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS, 2018, 14 (05) :2066-2075
[22]   Worst-case traversal time analysis of TSN with multi-level preemption [J].
Ojewale, Mubarak Adetunji ;
Yomsi, Patrick Meumeu ;
Nikolic, Borislav .
JOURNAL OF SYSTEMS ARCHITECTURE, 2021, 116
[23]   IEEE 802.1Qbv Gate Control List Synthesis using Array Theory Encoding [J].
Oliver, Ramon Serna ;
Craciunas, Silviu S. ;
Steiner, Wilfried .
24TH IEEE REAL-TIME AND EMBEDDED TECHNOLOGY AND APPLICATIONS SYMPOSIUM (RTAS 2018), 2018, :13-24
[24]  
Pahlevan M, 2018, IEEE INT C EMERG, P337, DOI 10.1109/ETFA.2018.8502515
[25]  
Raagaard ML, 2017, 2017 IEEE FOG WORLD CONGRESS (FWC), P73
[26]   Real-Time Scheduling for WirelessHART Networks [J].
Saifullah, Abusayeed ;
Xu, You ;
Lu, Chenyang ;
Chen, Yixin .
31ST IEEE REAL-TIME SYSTEMS SYMPOSIUM (RTSS 2010), 2010, :150-159
[27]   A survey and taxonomy on energy management schemes in wireless sensor networks [J].
Singh, Jaspreet ;
Kaur, Ranjit ;
Singh, Damanpreet .
JOURNAL OF SYSTEMS ARCHITECTURE, 2020, 111
[28]   Synthesis of Queue and Priority Assignment for Asynchronous Traffic Shaping in Switched Ethernet [J].
Specht, Johannes ;
Samii, Soheil .
2017 IEEE REAL-TIME SYSTEMS SYMPOSIUM (RTSS), 2017, :178-187
[29]   Urgency-Based Scheduler for Time-Sensitive Switched Ethernet Networks [J].
Specht, Johannes ;
Samii, Soheil .
PROCEEDINGS OF THE 28TH EUROMICRO CONFERENCE ON REAL-TIME SYSTEMS ECRTS 2016, 2016, :75-85
[30]   An Evaluation of SMT-based Schedule Synthesis For Time-Triggered Multi-Hop Networks [J].
Steiner, Wilfried .
31ST IEEE REAL-TIME SYSTEMS SYMPOSIUM (RTSS 2010), 2010, :375-384