  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.
