Just a Second -- Scheduling Thousands of Time-Triggered Streams in Large-Scale Networks
Preprint
Abstract
Deterministic real-time communication with bounded delay is an essential requirement for many safety-critical cyber-physical systems, and has received much attention from major standardization bodies such as IEEE and IETF. In particular, Ethernet technology has been extended by time-triggered scheduling mechanisms in standards like TTEthernet and Time-Sensitive Networking. Although the scheduling mechanisms have become part of standards, the traffic planning algorithms to create time-triggered schedules are still an open and challenging research question due to the problem's high complexity. In particular, so-called plug-and-produce scenarios require the ability to extend schedules on the fly within seconds. The need for scalable scheduling and routing algorithms is further supported by large-scale distributed real-time systems like smart energy grids with tight communication requirements. In this paper, we tackle this challenge by proposing two novel algorithms called Hierarchical Heuristic Scheduling (H2S) and Cost-Efficient Lazy Forwarding Scheduling (CELF) to calculate time-triggered schedules for TTEthernet. H2S and CELF are highly efficient and scalable, calculating schedules for more than 45,000 streams on random networks with 1,000 bridges as well as a realistic energy grid network within sub-seconds to seconds.Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- Large-scale periodic scheduling in time-sensitive networksComputers & Operations Research, 2022
- A fault-tolerant time-triggered scheduling algorithm of mixed-criticality systemsComputing, 2021
- Constraint programming approaches to joint routing and scheduling in time-sensitive networksComputers & Industrial Engineering, 2021
- Joint routing and scheduling for large-scale deterministic IP networksComputer Communications, 2021
- Packet-size aware scheduling algorithms in guard band for time sensitive networkingCCF Transactions on Networking, 2020
- Control Performance Optimization for Application Integration on Automotive ArchitecturesIEEE Transactions on Computers, 2020
- Runtime reconfiguration of time-sensitive networking (TSN) schedules for Fog Computing2017
- Design optimisation of cyber‐physical distributed systems using IEEE time‐sensitive networksIET Cyber-Physical Systems: Theory & Applications, 2016
- Energy Efficient Ethernet for Real-Time Industrial NetworksIEEE Transactions on Automation Science and Engineering, 2014
- A Survey on Smart Grid Communication Infrastructures: Motivations, Requirements and ChallengesIEEE Communications Surveys & Tutorials, 2012