ILP-based joint routing and scheduling for time-triggered networks

Abstract

Networks in the automotive and aerospace area as well as in production facilities have to support time-critical (i.e., hard real-time) communication. For such applications, time-triggered Ethernet-based networking solutions provide the required timeliness, i.e., reliable packet delivery with deterministic latencies and low jitter. However, the routing and scheduling of the time-triggered traffic is an NP-hard problem. Hence, existing solutions to this problem make certain abstractions to reduce complexity if necessary. Nonetheless, such abstractions exclude feasible routing and scheduling options from the design space. Specifically, it is a typical approach to model routing and scheduling as separate problems, which are solved successively or with heuristic coupling. Therefore, we present a novel ILP formulation that can be used to jointly solve the routing and scheduling problem for time-triggered Ethernet networks. Using this formulation, it is possible to solve various scheduling problems that are infeasible when using a fixed shortest path routing with separate scheduling. Compared to a fixed load balanced routing with separate scheduling, schedules computed with our formulation offer lower communication latencies.