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

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

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

Original languageEnglish
Article number102141
Pages (from-to)1-11
Number of pages11
JournalJournal of Systems Architecture
Volume116
DOIs
Publication statusPublished - Jun 2021

Keywords

  • Industrial internet of things
  • Real-time scheduling
  • Resource management
  • Time-sensitive networks

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture

Cite this