An Evaluation of SMT-Based Schedule Synthesis for Time-Triggered Multi-hop Networks

Networks for real-time systems have stringent end-to-end latency and jitter requirements. One cost-efficient way to meet these requirements is the time-triggered communication paradigm which plans the transmission points in time of the frames off-line. This plan prevents contentions of frames on the network and is called a time-triggered schedule (tt-schedule). In general the tt-scheduling is a bin-packing problem, known to be NP-complete, where the complexity is mostly driven by the freedom in topology of the network, its associated hardware restrictions, and application-imposed constraints. Multi-hop networks, in particular, require the synthesis of path-dependent tt-schedules to maintain full determinism of time-triggered communication from sender to receiver. Our experiments using the YICES SMT solver show that the scheduling problem can be solved by YICES out-of-the-box for a few hundred random frame instances on the network. A customized tt-scheduler using YICES as a back-end solver allows to increase this number of frame instances up to tens of thousands. In terms of scheduling quality, the synthesis produces up to ninety percent maximum utilization on a communication link with schedule synthesis times of about half an hour for the biggest examples we have studied. As a nice side-effect the YICES out-of-the-box approach is immediately applicable for the verification of existing (even large-scale) tt-schedules and for debugging more sophisticated tt-schedulers.

I. Introduction

The types and variants of existing and emerging embedded real-time systems are as numerous as the physical processes that they command and control. For example, the surround sound system of a home theater has a different set of requirements than the flight-management system in an airplane. Naturally, several trade-offs have to be taken into account when developing the embedded real-time system. For realtime scheduling one fundamental trade-off is in the amount of off-line versus the amount of on-line computation.