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

被引：0

作者：

Lin, Yuhan ^{[1
]}

Jin, Xi ^{[2
]}

Zhang, Tianyu ^{[1
]}

Han, Meilin ^{[3
]}

Guan, Nan ^{[4
]}

Deng, Qingxu ^{[1
]}

机构：

[1] Northeastern University, China

[2] Shenyang Institute of Automation, Chinese Academy of Sciences, China

[3] Nanjing University of Posts and Telecommunications, China

[4] The Hong Kong Polytechnic University, Hong Kong

来源：

Journal of Systems Architecture | 2021年 / 116卷

基金：

中国国家自然科学基金;

关键词：

Queueing theory - Time switches - Internet of things - Real time systems - Heuristic algorithms - Combinatorial optimization;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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. © 2021

引用

共 50 条

[1] Queue assignment for fixed-priority real-time flows in time-sensitive networks: Hardness and algorithm
Lin, Yuhan
Jin, Xi
Zhang, Tianyu
Han, Meiling
Guan, Nan
Deng, Qingxu
JOURNAL OF SYSTEMS ARCHITECTURE, 2021, 116
[2] Fixed-Priority Scheduling and Controller Co-Design for Time-Sensitive Networks
Dai, Xiaotian
Zhao, Shuai
Jiang, Yu
Jiao, Xun
Hu, Xiaobo Sharon
Chang, Wanli
2020 IEEE/ACM INTERNATIONAL CONFERENCE ON COMPUTER AIDED-DESIGN (ICCAD), 2020,
[3] Priority Assignment for Real-Time Flows in WirelessHART Networks
Saifullah, Abusayeed
Xu, You
Lu, Chenyang
Chen, Yixin
PROCEEDINGS OF THE 23RD EUROMICRO CONFERENCE ON REAL-TIME SYSTEMS (ECRTS 2011), 2011, : 35 - 44
[4] Energy Efficient Scheduling for Hard Real-Time Systems with Fixed-Priority Assignment
Niu, Linwei
2010 IEEE 29TH INTERNATIONAL PERFORMANCE COMPUTING AND COMMUNICATIONS CONFERENCE (IPCCC), 2010, : 153 - 160
[5] An optimal fixed-priority assignment algorithm for supporting fault-tolerant hard real-time systems
Lima, GMD
Burns, A
IEEE TRANSACTIONS ON COMPUTERS, 2003, 52 (10) : 1332 - 1346
[6] Analyzing stochastic fixed-priority real-time systems
Gardner, MK
Liu, JWS
TOOLS AND ALGORITHMS FOR THE CONSTRUCTION AND ANALYSIS OF SYSTEMS, 1999, 1579 : 44 - 58
[7] Sensitivity analysis for fixed-priority real-time systems
Enrico Bini
Marco Di Natale
Giorgio Buttazzo
Real-Time Systems, 2008, 39 : 5 - 30
[8] Sensitivity analysis for fixed-priority real-time systems
Bini, Enrico
Di Natale, Marco
Buttazzo, Giorgio
18TH EUROMICRO CONFERENCE ON REAL-TIME SYSTEMS, PROCEEDINGS, 2006, : 13 - +
[9] Sensitivity analysis for fixed-priority real-time systems
Bini, Enrico
Di Natale, Marco
Buttazzo, Giorgio
REAL-TIME SYSTEMS, 2008, 39 (1-3) : 5 - 30
[10] PASS: Priority Assignment of Real-Time Tasks with Dynamic Suspending Behavior under Fixed-Priority Scheduling
Huang, Wen-Hung
Chen, Jian-Jia
Zhou, Husheng
Liu, Cong
2015 52ND ACM/EDAC/IEEE DESIGN AUTOMATION CONFERENCE (DAC), 2015,

← 1 2 3 4 5 →