TY - JOUR
T1 - Queue assignment for fixed-priority real-time flows in time-sensitive networks: Hardness and algorithm
AU - Lin, Yuhan
AU - Jin, Xi
AU - Zhang, Tianyu
AU - Han, Meilin
AU - Guan, Nan
AU - Deng, Qingxu
N1 - Funding Information:
This work is supported in part by the National Key Research and Development Program of China under Grant 2018YFB1702003 . This work is also supported by the National Natural Science Foundation of China under Grant 62072085 and the LinoNing Revitalization Talents Program under Grant XLYC1902017 .
Publisher Copyright:
© 2021
PY - 2021/6
Y1 - 2021/6
N2 - 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 real-time 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.
AB - 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 real-time 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.
KW - Industrial internet of things
KW - Real-time scheduling
KW - Resource management
KW - Time-sensitive networks
UR - http://www.scopus.com/inward/record.url?scp=85105334483&partnerID=8YFLogxK
U2 - 10.1016/j.sysarc.2021.102141
DO - 10.1016/j.sysarc.2021.102141
M3 - Journal article
AN - SCOPUS:85105334483
SN - 1383-7621
VL - 116
SP - 1
EP - 11
JO - Euromicro Newsletter
JF - Euromicro Newsletter
M1 - 102141
ER -