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

Yuhan Lin; Xi Jin; Tianyu Zhang; Meiling Han; Nan Guan; Qingxu Deng

doi:10.1016/j.sysarc.2021.102141

Back

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

Journal article

Peer reviewed

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

Yuhan Lin, Xi Jin, Tianyu Zhang, Meiling Han, Nan Guan and Qingxu Deng

Journal of systems architecture, Vol.116, p.102141

06/01/2021

DOI: 10.1016/j.sysarc.2021.102141

View Online

Abstract

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.

Computer Science

Computer Science, Hardware & Architecture

Computer Science, Software Engineering

Science & Technology

Technology

Details

Title: Subtitle: Queue assignment for fixed-priority real-time flows in time-sensitive networks: Hardness and algorithm
Creators: Yuhan Lin - Northeastern University
Xi Jin - Shenyang Institute of Automation
Tianyu Zhang - Northeastern University
Meiling Han - Nanjing University of Posts and Telecommunications
Nan Guan - Hong Kong Polytechnic University
Qingxu Deng - Northeastern University
Resource Type: Journal article
Publication Details: Journal of systems architecture, Vol.116, p.102141
Publisher: Elsevier
DOI: 10.1016/j.sysarc.2021.102141
ISSN: 1383-7621
eISSN: 1873-6165
Number of pages: 11
Grant note: 62072085 / National Natural Science Foundation of China; National Natural Science Foundation of China (NSFC) XLYC1902017 / LinoNing Revitalization Talents Program 2018YFB1702003 / National Key Research and Development Program of China; National Key Research & Development Program of China
Language: English
Date published: 06/01/2021
Academic Unit: Computer Science
Record Identifier: 9984696725402771

Metrics

1 Record Views