Fault-Tolerant Topology Selection for TTEthernet Networks

Many safety-critical real-time applications are implemented using distributed architectures, composed of heterogeneous processing elements (PEs) interconnected in a network. In this paper, we are interested in the TTEthernet protocol, which is a deterministic, synchronized and congestion-free network protocol based on the IEEE 802.3 Ethernet standard and compliant with ARINC 664p7. TTEthernet supports three types of traffic: static time-triggered (TT) traffic and dynamic traffic, which is further subdivided into Rate Constrained (RC) traffic that has bounded end-to-end latencies, and Best-Effort (BE) traffic, for which no timing guarantees are provided. TTEthernet offers spatial separation through the concept of virtual links (VLs), and temporal separation, through schedule tables for TT messages and bandwidth allocation for RC messages. Given a set of PEs, we are interested to determine a fault-tolerant network topology, consisting of redundant physical links and network switches, such that the architecture cost is minimized, the applications are fault-tolerant to a given number of permanent faults occurring in the communication network, and the timing constraints of the TT and RC messages are satisfied. Deciding on a fault-tolerant topology means (i) deciding on the number of network switches, (ii) the physical links and the network topology, (iii) the routing of VLs on top of the physical network, (iv) the assignment of frames to VLs and (v) the schedule tables for the TT frames. We propose a Simulated Annealing meta-heuristic to solve this optimization problem. The proposed approach has been evaluated using a synthetic benchmark and a space case study, based on the Orion Crew Exploration Vehicle.