Enhanced conflict-aware iterated integer linear programming for IEEE 802.1Qbv Time-Sensitive Network scheduling


Ozkan A. K., CEVHER S.

INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, 2024 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Publication Date: 2024
  • Doi Number: 10.1002/dac.5920
  • Journal Name: INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Aerospace Database, Communication & Mass Media Index, Communication Abstracts, Compendex, INSPEC, Metadex, zbMATH, Civil Engineering Abstracts
  • Karadeniz Technical University Affiliated: Yes

Abstract

Deterministic communication plays a crucial role for real-time distributed embedded systems by guaranteeing a low end-to-end delay and minimal jitter. Conflict-aware iterated ILP-based scheduling (IIS) is an incremental approach to enhance the scalability of single-shot ILP computation to solve the computationally hard Qbv-compliant offline scheduling problem for IEEE 802.1 Time-Sensitive Networking (TSN). Taking into account the conflicting demands of the streams, IIS computes no-wait schedules by dividing the set of streams into disjoint partitions, each of which is incrementally scheduled by an ILP solver. In this work, defining the no-wait communication constraints for TSN scheduling, we propose a novel iterated scheduling approach, namely, O-IIS, with a backtracking mechanism and partial solution support extending the conventional IIS procedure. O-IIS relies on an ordering strategy to determine the order in which the constructed partitions will be processed by an ILP solver. We evaluate the performance of our approach in terms of schedulability success rate and schedule synthesis time using various network topologies and different partitioning schemes to construct the partitions. The evaluation results show that our approach provides significantly better scheduling performance compared to the existing work in the literature. Conflict-aware iterated ILP-based scheduling is an incremental approach to enhance the scalability of single-shot ILP computation to solve the computationally hard Qbv-compliant offline scheduling problem for IEEE 802.1 Time-Sensitive Networking (TSN). In this work, we propose a novel iterated scheduling approach with a backtracking mechanism and partial solution support extending the conventional procedure. Evaluation results show that our approach provides a significantly better scheduling performance compared to the existing work in the literature. image