Schedule Synthesis for Next Generation Time-Triggered Networks

For handling frame transmissions in highly deterministic real-time networks, i.e. networks requiring low communication latency and minimal jitter, an offline time-triggered schedule indicating the dispatch times of all frames can be used. Generation of such an offline schedule is known to be a NPcomplete problem, with complexity driven by the size of the network, the number and complexity of the traffic temporal constraints, and link diversity (for instance, coexistence of wired and wireless links). As embedded applications become more complex and extend over larger geographical areas, there is a need to deploy larger real-time networks, but existing schedule synthesis mechanisms do not scale satisfactorily to the sizes of these networks, constituting a potential bottleneck for system designers. In this paper, we present an offline synthesis tool that overcomes this limitation and is capable of generating time-triggered schedules for networks with hundreds of nodes and thousands of temporal constraints, also for systems where wired and wireless links are combined. This tool models the problem with linear arithmetic constraints and solves them using a Satisfiability Modulo Theory (SMT) solver, a powerful general purpose tool successfully used in the past for synthesizing time-triggered schedules. To cope with complexity, our algorithm implements a segmented approach that divides the total problem into easily solvable smaller-size scheduling problems, whose solutions can be combined for achieving the final schedule. The paper also discusses a number of optimizations that increase the size and compactness of the solvable schedules. We evaluate our approach on a set of realistic large-size multi-hop networks, significantly bigger than those in the existing literature. The results show that our segmentation reduces the synthesis time dramatically, allowing generation of extremely large compact schedules.