Temporal Boundary Analysis on Startup Algorithm for Time-Triggered Architecture with Bus Topology

Baoyue Yan, Long Xiang, Mu Li2018 · DOI

Abstract

The Time-triggered Architecture (TTA) is a widely-recognized design framework for large distributed embedded real-time systems. This paper derives an elaborated startup scheme and discusses its temporal boundary for TTA-based systems, which require predictable communication in TDMA environments. The scheme introduces an arrival time window (ATW) with a dedicated lower time boundary for contention resolution during the startup phase without direct collision detection. While previous model checking approaches have analyzed startup temporal attributes, they struggle with arbitrary node counts and propagation delays. This paper provides the upper boundary of startup time for TTA systems with an arbitrary number of nodes through formal deduction.

Introduction

In safety-critical domains like aerospace and autonomous vehicles, timing is a fundamental safety requirement. Time-Triggered Architecture (TTA) ensures predictability by following a strict, pre-planned schedule. However, a critical challenge arises at system power-on: nodes start with independent internal clocks and must synchronize to a common "Time Zero" to establish the Time Division Multiple Access (TDMA) schedule without signal interference.

The Challenge of Startup in TTA

In a TTA system utilizing a bus topology, nodes are assigned specific time slots for communication. At startup, the system is asynchronous, necessitating a robust algorithm to transition nodes from individual clocks to a synchronized cluster.

TTA System Architecture with Bus Topology

The primary obstacle is contention. Physical contention occurs when signals overlap on the bus, while logical contention arises when propagation delays cause nodes to misinterpret the bus state. Traditional collision detection (like CSMA/CD) is often insufficient for TTA due to these propagation effects. Previous research relied heavily on model checking, which is limited by specific scenarios and cannot easily generalize to systems with an arbitrary number of nodes ($n$) or varying propagation delays ($\Delta_{prop}$).

Proposed Startup Scheme and Arrival Time Window

The authors propose an elaborated startup scheme based on a Finite State Machine (FSM) and a novel Arrival Time Window (ATW). Nodes transition through states—INIT, LISTEN, COLDSTART, and SYNC—based on bus activity.

TDMA Cluster Cycle and Detailed Slot Structure

The ATW (labeled as AT in the diagram) is central to resolving logical contention. When a node detects a signal, it opens an ATW to judge if the frame is valid for synchronization or a result of a collision. The authors determine that for effective contention resolution, the ATW's lower boundary must be at least $2\Delta_{prop} + \Delta_{frame}$. This mechanism allows nodes to accept valid frames earlier than standard schemes, potentially reducing overall startup time.

Formal Analysis and Results

Using formal deduction rather than simulation, the paper establishes a universal upper boundary for the startup process. The analysis divides startup into two phases:

  1. Contention Eliminating Phase: Ensuring overlapping startup attempts are resolved. Max duration: $2\Delta_{TDMA} - \Delta_{PSP} + \Delta_{prop}$.
  2. Clique Detecting Phase: Ensuring all nodes agree on the same schedule. Max duration: $(n - 1)\Delta_{slot} + \Delta_{PSP}$.

By combining these phases, the authors prove that the total Upper Boundary of Startup Time ($\Delta_{UBS}$) for a fault-free system is: $$\Delta_{UBS} = 3n\Delta_{slot}$$

This result provides a concrete worst-case bound that is independent of specific node configurations, offering a reliable metric for system designers to set timeouts and diagnostic parameters.

Conclusion and Future Work

This work fills a gap in TTA research by providing a mathematically rigorous upper bound for startup synchronization in bus topologies. While the current analysis assumes a fault-free environment, it establishes a foundation for future studies to incorporate fault models, such as "babbling idiot" nodes or transient signal failures. Additionally, extending this formal boundary analysis to star or mesh topologies remains an area for further exploration.

Summary updated

Abstract

The Time-triggered Architecture (TTA) is seen as a widely-recognized design framework for the domain of large distributed embedded real-time systems. This paper derives an elaborated startup scheme and discusses the temporal boundary of it for real-time systems based on TTA, which normally require predictable communication in TDMA environments. The scheme presents an arrival time window (ATW) with a dedicated lower time boundary for contention resolution during startup phase without detecting collisions directly. Although many previous model checking approaches have been taken for analyzing the temporal attributes of the startup algorithm, it is hard to model the startup scenario at arbitrary number of nodes and arbitrary propagation between them. This paper gives the upper boundary of startup time for systems based on TTA with arbitrary number of nodes towards the dedicated startup scheme by formal deduction.
BibTeX
@misc{yan2018temporal,
  author = {Baoyue Yan and Long Xiang and Mu Li},
  title = {{Temporal Boundary Analysis on Startup Algorithm for Time-Triggered Architecture with Bus Topology}},
  year = {2018},
  doi = {10.2991/aeecs-18.2018.48},
}

Loading related content...

Figure