Queue assignment for fixed-priority real-time flows in time-sensitive networks: Hardness and algorithm
文献类型:期刊论文
作者 | Lin YH(林宇晗)2; Jin X(金曦)4![]() ![]() |
刊名 | Journal of Systems Architecture
![]() |
出版日期 | 2021 |
卷号 | 116页码:1-11 |
关键词 | Resource management Industrial internet of things Real-time scheduling Time-sensitive networks |
ISSN号 | 1383-7621 |
产权排序 | 2 |
英文摘要 | 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. |
语种 | 英语 |
WOS记录号 | WOS:000651143900006 |
资助机构 | National Key Research and Development Program of China under Grant 2018YFB1702003 ; National Natural Science Foundation of China under Grant 62072085 ; LinoNing Revitalization Talents Program under Grant XLYC1902017 |
源URL | [http://ir.sia.cn/handle/173321/28793] ![]() |
专题 | 沈阳自动化研究所_工业控制网络与系统研究室 |
通讯作者 | Deng QX(邓庆绪) |
作者单位 | 1.The Hong Kong Polytechnic University, Hong Kong 2.Northeastern University, China; 3.Nanjing University of Posts and Telecommunications, China; 4.Shenyang Institute of Automation, Chinese Academy of Sciences, China; |
推荐引用方式 GB/T 7714 | Lin YH,Jin X,Zhang TY,et al. Queue assignment for fixed-priority real-time flows in time-sensitive networks: Hardness and algorithm[J]. Journal of Systems Architecture,2021,116:1-11. |
APA | Lin YH,Jin X,Zhang TY,Han ML,Guan N,&Deng QX.(2021).Queue assignment for fixed-priority real-time flows in time-sensitive networks: Hardness and algorithm.Journal of Systems Architecture,116,1-11. |
MLA | Lin YH,et al."Queue assignment for fixed-priority real-time flows in time-sensitive networks: Hardness and algorithm".Journal of Systems Architecture 116(2021):1-11. |
入库方式: OAI收割
来源:沈阳自动化研究所
其他版本
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。