A Backtracking Ensemble Pruning Based Reconfiguration Method for Time-Triggered Flows in TTEthernet

Abstract

In time-triggered ethernet (TTEthernet), when an end system node (ES) permanently fails, the affected TT flows should be reconfigured (known as reconfigured TT flows) with ESs, routings and an updated scheduling table while maintaining the scheduling scheme of unaffected TT flows (referred as original TT flows) during runtime. This paper presents a reconfiguration method with backtracking ensemble pruning as the core solution algorithm for solving tree search models which are built with network topology and idle link slots. The model comprises a two-step strategy to reduce solution space scale of the search tree. The first step involved use of a backtracking ensemble pruning algorithm for each reconfigured TT flow (BEPA-S) where only the constraints of the original TT flows for each reconfigured TT flow are considered. The second step involved elimination of possible conflicts between reconfigured TT flows in which a modified BEPA algorithm (ModBEPA) was used to preferentially search scheduling schemes with smaller end-to-end delay. Dynamic pruning was performed based on the conflict information obtained during the depth-first search. Simulation results indicated that the time consumed in generation of scheduling scheme was further reduced without reducing its success rate because ESs, routings and TT scheduling tables were considered simultaneously (instead of calculating alternative ESs, routings and TT scheduling table separately through black box combinational optimization solver performed in traditional methods). Verification of the three different network scales showed that the efficiency acceleration ratio of BEPA based reconfiguration method was significantly better compared with that of the traditional method.

Keywords

• Time-triggered Ethernet
• reconfiguration
• routing
• backtracking ensemble pruning algorithm
• scheduling table