Efficient Conflict Graph Creation for Time-Sensitive Networks With Dynamically Changing Communication Demands
Open Access
- 6 June 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network and Service Management
- Vol. 22 (5) , 4525-4537
Abstract
Many applications of cyber-physical systems require real-time communication: manufacturing, automotive, etc. Recent Ethernet standards for Time Sensitive Networking (TSN) offer time-triggered scheduling in order to guarantee low latency and jitter bounds. This requires precise frame transmission planning, which becomes especially hard when dealing with many streams, large networks, and dynamically changing communications. A very promising approach uses conflict graphs, modeling conflicting transmission configurations. Since the creation of conflict graphs is the bottleneck in these approaches, we provide an improvement to the conflict graph creation. We present a randomized selection process that reduces the overall size of the graph in half and three heuristics to improve the scheduling success. In our evaluations we show substantial improvements in the graph creation speed and the scheduling success compared to existing work, updating existing schedules in fractions of a second. Additionally, offline planning of 9000 streams was performed successfully within minutes.Keywords
All Related Versions
Funding Information
- Deutsche Forschungsgemeinschaft (EXC 2075 - 390740016)
This publication has 26 references indexed in Scilit:
- Large-scale periodic scheduling in time-sensitive networksComputers & Operations Research, 2022
- Constraint programming approaches to joint routing and scheduling in time-sensitive networksComputers & Industrial Engineering, 2021
- IEEE Standard for Local and Metropolitan Area Networks--Timing and Synchronization for Time-Sensitive Applications2020
- Networks2018
- Optimal harmonic period assignment: complexity results and approximation algorithmsReal-Time Systems, 2018
- Runtime reconfiguration of time-sensitive networking (TSN) schedules for Fog Computing2017
- Paving the road toward Smart Grids through large-scale advanced metering infrastructuresElectric Power Systems Research, 2015
- IEEE Standard for Local and metropolitan area networks--Media Access Control (MAC) Bridges and Virtual Bridged Local Area Networks--Amendment 20: Shortest Path Bridging2012
- IEEE Standard for Local and Metropolitan Area Networks---Virtual Bridged Local Area Networks---Amendment 4: Provider Bridges2011
- Routing of multipoint connectionsIEEE Journal on Selected Areas in Communications, 1988