Just a second — Scheduling thousands of time-triggered streams in large-scale networks

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 high complexity of the problem. 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-Effective Lazy Forwarding Scheduling (CELF) to create time-triggered schedules for TTEthernet. H2S and CELF are highly efficient and scalable, computing schedules for more than 45,000 streams on random networks with 1000 bridges as well as a realistic energy grid network within seconds or even sub-seconds.