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 条

[21] Partitioned Multiprocessor Fixed-Priority Scheduling of Sporadic Real-Time Tasks
Chen, Jian-Jia
PROCEEDINGS OF THE 28TH EUROMICRO CONFERENCE ON REAL-TIME SYSTEMS ECRTS 2016, 2016, : 251 - 261
[22] Fixed-priority scheduling of real-time systems using utilization bounds
Park, DW
Natarajan, S
Kanevsky, A
JOURNAL OF SYSTEMS AND SOFTWARE, 1996, 33 (01) : 57 - 63
[23] Scheduling fixed-priority hard real-time tasks in the presence of faults
Lima, G
Burns, A
DEPENDABLE COMPUTING, PROCEEDINGS, 2005, 3747 : 154 - 173
[24] Preference-Oriented Fixed-Priority Scheduling for Real-Time Systems
Begam, Rehana
Zhu, Dakai
Aydin, Hakan
2014 IEEE 12TH INTERNATIONAL CONFERENCE ON DEPENDABLE, AUTONOMIC AND SECURE COMPUTING (DASC)/2014 IEEE 12TH INTERNATIONAL CONFERENCE ON EMBEDDED COMPUTING (EMBEDDEDCOM)/2014 IEEE 12TH INTERNATIONAL CONF ON PERVASIVE INTELLIGENCE AND COMPUTING (PICOM), 2014, : 159 - +
[25] Real-Time Traffic Guarantees in Heterogeneous Time-sensitive Networks
Barzegaran, Mohammadreza
Reusch, Niklas
Zhao, Luxi
Craciunas, Silviu S.
Pop, Paul
PROCEEDINGS OF THE 30TH INTERNATIONAL CONFERENCE ON REAL-TIME NETWORKS AND SYSTEMS, RTNS 2022, 2022, : 46 - 57
[26] Enhanced Real-time Scheduling of AVB Flows in Time-Sensitive Networking
Deng, Libing
Zeng, Gang
Kurachi, Ryo
Takada, Hiroaki
Xiao, Xiongren
Li, Renfa
Xie, Guoqi
ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS, 2024, 29 (02)
[27] Energy efficient DVS schedule for fixed-priority real-time systems
Quan, Gang
Hu, Xiaobo Sharon
ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS, 2007, 6 (04) : 29
[28] Feasibility intervals for fixed-priority real-time scheduling on uniform multiprocessors
Cucu, Liliana
Goossens, Joel
2006 IEEE CONFERENCE ON EMERGING TECHNOLOGIES & FACTORY AUTOMATION, VOLS 1 -3, 2006, : 336 - +
[29] Schedulability Analysis in Fixed-Priority Real-Time Multicore Systems with Contention
Ortiz, Luis
Guasque, Ana
Balbastre, Patricia
Simo, Jose
Crespo, Alfons
APPLIED SCIENCES-BASEL, 2024, 14 (10):
[30] A Novel Queue Priority Algorithm for Real-time Message in VANETs
Mi, Junwen
Liu, Fuqiang
Xu, Shangzhi
Li, Qi
INTERNATIONAL CONFERENCE ON INTELLIGENT COMPUTATION TECHNOLOGY AND AUTOMATION, VOL 2, PROCEEDINGS, 2008, : 919 - 923

← 1 2 3 4 5 →