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
基金
中国国家自然科学基金;
关键词
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 条
  • [41] Periodic Charging Scheme for Fixed-Priority Real-Time Systems with Renewable Energy
    Bambagini, Mario
    Aydin, Hakan
    2014 9TH IEEE INTERNATIONAL SYMPOSIUM ON INDUSTRIAL EMBEDDED SYSTEMS (SIES), 2014,
  • [42] Response Time Analysis for Thermal-Aware Real-Time Systems Under Fixed-Priority Scheduling
    Chandarli, Younes
    Fisher, Nathan
    Masson, Damien
    2015 IEEE 18th International Symposium on Real-Time Distributed Computing (ISORC), 2015, : 84 - 93
  • [43] SysWCET: Whole-System Response-Time Analysis for Fixed-Priority Real-Time Systems
    Dietrich, Christian
    Wagemann, Peter
    Ulbrich, Peter
    Lohmann, Daniel
    PROCEEDINGS OF THE 23RD IEEE REAL-TIME AND EMBEDDED TECHNOLOGY AND APPLICATIONS SYMPOSIUM (RTAS 2017), 2017, : 37 - 48
  • [44] Priority assignment in hierarchically scheduled time-partitioned distributed real-time with flows
    Amurrio, Andoni
    Gutierrez, J. Javier
    Aldea, Mario
    Azketa, Ekain
    JOURNAL OF SYSTEMS ARCHITECTURE, 2022, 122
  • [45] An efficient response-time analysis for real-time transactions with fixed priority assignment
    Rahni, Ahmed
    Grolleau, Emmanuel
    Richard, Michael
    INNOVATIONS IN SYSTEMS AND SOFTWARE ENGINEERING, 2009, 5 (03) : 197 - 209
  • [46] Research on Real-Time Communication Algorithm of Substation Based on Time-Sensitive Network
    Wang, Beilei
    Liu, Yang
    Guo, Chenyang
    Song, Yan
    Wang, Jidong
    Xiao, Jinchao
    Chen, Xiaoguang
    SYMMETRY-BASEL, 2022, 14 (06):
  • [47] Semi-partitioned scheduling for fixed-priority real-time tasks based on intelligent rate monotonic algorithm
    Senobary, Saeed
    Naghibzadeh, Mahmoud
    INTERNATIONAL JOURNAL OF GRID AND UTILITY COMPUTING, 2015, 6 (3-4) : 184 - 191
  • [48] A Period Assignment Method for Fixed Priority Preemptive Real-time Systems
    Liu, Jiankang
    Fu, Yunzhong
    Chen, Chuanwei
    Fu, Hongya
    PROCEEDINGS OF THE 2016 8TH INTERNATIONAL CONFERENCE ON INFORMATION MANAGEMENT AND ENGINEERING (ICIME 2016), 2016, : 89 - 92
  • [49] Dynamic voltage scaling algorithm for fixed-priority real-time systems using work-demand analysis
    Kim, W
    Kim, J
    Min, SL
    ISLPED'03: PROCEEDINGS OF THE 2003 INTERNATIONAL SYMPOSIUM ON LOW POWER ELECTRONICS AND DESIGN, 2003, : 396 - 401
  • [50] Energy efficient fixed-priority scheduling for real-time systems on variable voltage processors
    Quan, G
    Hu, XB
    38TH DESIGN AUTOMATION CONFERENCE PROCEEDINGS 2001, 2001, : 828 - 833