Transcript Introduction to TTA

HRTC Meeting
12 September 2002, Vienna
Introduction to the TTA
Thomas Losert
Outlook
• Requirements
• Basic Principles




•
•
•
•
Composability
Dense Time versus Sparse Time
Communication System Paradigms
Temporal Firewall
Time Triggered Architecture (TTA)
TTP/C protocol
Bus Guardian
Conclusion
Thomas Losert
12 September 2002 / p.2
Outlook
• Requirements
• Basic Principles




•
•
•
•
Composability
Dense Time versus Sparse Time
Communication System Paradigms
Temporal Firewall
Time Triggered Architecture (TTA)
TTP/C protocol
Bus Guardian
Conclusion
Thomas Losert
12 September 2002 / p.3
Requirement: Small Jitter
Control Model
Sensor
Processing
Actuator
Control Object (Vehicle)
We must know the exact time difference between
observing and acting
Thomas Losert
12 September 2002 / p.4
Requirement:
Reduction of Complexity
If the mental effort
required to understand a
particular system function
grows with the system
size, there is an inherent
limitation to the size of
the systems we can build.
Mental Effort
(Perceived Complexity)
Human Mental
Capability
System
Size
Design faults have their root in unmanaged complexity.
Thomas Losert
12 September 2002 / p.5
Requirement: Composability
• Compose: “to make or form by combining things, parts, or
elements”
• Composition: “the act of combining parts or elements to form a
whole”
Webster Encyclopedic Dictionary, 1989, p. 302
• Composability: “The ease of forming a whole by combining
parts”
• Parts: The component systems
• Whole: A system of systems (SOS).
• A composition brings into existence new emerging services of
the SOS that are more than the sum of the prior services of the
components.
• These emerging services are the result of the integration of the
component systems.
Thomas Losert
12 September 2002 / p.6
Requirement: Safety
• Each device will fail sooner or later
• Thus an arbitrary single fault must be
tolerated without degradation of service
Thomas Losert
12 September 2002 / p.7
Outlook
• Requirements
• Basic Principles




•
•
•
•
Composability
Dense Time versus Sparse Time
Communication System Paradigms
Temporal Firewall
Time Triggered Architecture (TTA)
TTP/C protocol
Bus Guardian
Conclusion
Thomas Losert
12 September 2002 / p.8
Composability
• We call an architecture composable with respect to a
specified property, if the system integration will not
invalidate this property provided it has been
established at the subsystem level, e.g.:
 Timeliness
 Testability
• System properties should follow from subsystem
properties.
Otherwise the system integrator is left with the
challenging task to find out why the system does not
work, although all subsystems work according to
their specifications.
Thomas Losert
12 September 2002 / p.9
How is the “Integration” achieved?
 The component systems are integrated by the
exchange of messages across the real-time service
interfaces.
 Our focus is on what are the contents of a message
(data) and when a message is sent and received
(time).
 We abstract from the low-level (physical, coding)
aspects of communication.
 We assume that all property mismatches of the
interacting systems have been resolved by a
connection system.
Thomas Losert
12 September 2002 / p.10
The Four Principles of
Composability
 Independent Development of the Components (Architecture)
The message interfaces of the components must be precisely
specified in the value domain and in the temporal domain in
order that the component systems can be developed in isolation.
 Stability of Prior Services (Component Implementation)
The prior services of the components must be maintained after
the integration and should not fail if a partner fails.
 Performability of the Communication System (Comm.
System)
The communication system transporting the messages must meet
the given temporal requirements under all specified operating
conditions.
 Replica Determinism (Architecture)
Replica Determinism is required for the transparent
implementation of fault tolerance
Thomas Losert
12 September 2002 / p.11
Outlook
• Requirements
• Basic Principles




•
•
•
•
Composability
Dense Time versus Sparse Time
Communication System Paradigms
Temporal Firewall
Time Triggered Architecture (TTA)
TTP/C protocol
Bus Guardian
Conclusion
Thomas Losert
12 September 2002 / p.14
Dense Time versus Sparse Time (1)
It is impossible to perfectly synchronize the clocks of
nodes in a distributed computer system.
In a reasonable set of clocks each clock differs less
than 1 granule g from each other clock.
For reasonable clocks the timestamps of one single
event can differ at most by 1 clock tick.
g
A
0
1
2
3
4
5
REF CLK
0
1
2
3
4
5
CLK 1
0
1
2
3
4
5
CLK 2
Thomas Losert
12 September 2002 / p.15
Dense Time versus Sparse Time (2)
The temporal order cannot be established for events
with a difference of 1 granule g.
If the duration between two events is at least three
granules, the temporal order can be established always
because the timestamps differ at least by two ticks.
0
1
2
3
4
5
REF CLK
0
1
2
3
B
4
5
CLK 1
0
1
2
3
4
C
5
CLK 2
A
4-3=1
Thomas Losert
12 September 2002 / p.16
Dense Time versus Sparse Time (3)
In a sparse time base events occur only at predefined
intervals (events occuring in the silence interval are
delayed to the next activity interval).
a
s
a
s
a
Rea l Time
a dur ation of activity
s duration o f silence
Duration of activity determined by the granularity of
the global time
Thomas Losert
12 September 2002 / p.17
Outlook
• Requirements
• Basic Principles




•
•
•
•
Composability
Dense Time versus Sparse Time
Communication System Paradigms
Temporal Firewall
Time Triggered Architecture (TTA)
TTP/C protocol
Bus Guardian
Conclusion
Thomas Losert
12 September 2002 / p.18
Communication System Paradigms
Event-triggered (ET) communication systems
 Temporal control signals primarily derived
from non-time events
 Flexibility
 High average performance
Time-triggered (TT) communication systems
 Activities at predetermined points in time
 Predictability
 Dependability
Thomas Losert
12 September 2002 / p.19
Flow Control in Unidirectional Data
Transfer
• Information push
Sender
Control
Receiver
• Information pull Data
Sender
Receiver
• Time-triggered
Sender
Receiver
Thomas Losert
12 September 2002 / p.20
Control Flow and Data Flow in the TTA
Sender
CNI
Memory
CNI
Memory
Rcvr
Information Push
Time-Triggered Information Pull
Ideal for Sender
Communication Ideal for Receiver
System
Thomas Losert
12 September 2002 / p.21
Outlook
• Requirements
• Basic Principles




•
•
•
•
Composability
Dense Time versus Sparse Time
Communication System Paradigms
Temporal Firewall
Time Triggered Architecture (TTA)
TTP/C protocol
Bus Guardian
Conclusion
Thomas Losert
12 September 2002 / p.22
Concept of a Temporal Firewall
• A temporal firewall is a unidirectional data-sharing
interface with state-observations in the interface
memory where at least one of the interfacing
subsystems accesses the temporal firewall according
to an a priori known periodic schedule.
• The interface between the host computer and the
communication system can be seen as erecting two
unidirectional temporal firewalls:
an input firewall and an output firewall .
• A temporal firewalls eliminate control error
propagation by design.
Thomas Losert
12 September 2002 / p.23
A Temporal Firewall is a Natural
Concept
 A temporal firewall is a high-level abstract concept.
 It is a small and stable unidirectional interface that
provides understandable abstractions of the relevant
properties of the interfacing subsystems.
 Timeliness is an integral part of the temporal
firewall concept.
 Conceptually, the RT images in the temporal firewall
are closely related to the image presented by a
sensor of an analog RT entity in the environment.
 Temporal firewalls are thus based on an accustomed
view of the world.
Thomas Losert
12 September 2002 / p.24
Stable Properties of Temporal
Firewalls
The following stable properties of temporal firewalls
are known a priori to all interfacing partners:
 The addresses (names) and the syntactic structure of the data
items in the temporal firewall.
 A (abstract) model explaining the meaning of the data items
contained in the temporal firewall.
 The points on the global time base when the data items in
the temporal firewall are accessed by the TT communication
system. This information enables the avoidance of race
conditions between the producer and the consumer.
 The temporal accuracy of the data items in the temporal
firewall. This knowledge is important to guide the
information consumer about the minimum rate of sampling
of the temporal firewall.
Thomas Losert
12 September 2002 / p.25
TTA Interface: Temporal Firewall
A temporal firewall interface
 is a unidirectional elementary data flow interface for the exchange
of state information.
 is located in a dual ported RAM of a communication controller-update-in-place semantics
 the instants when data is fetched (delivered) from (to) the
communication system are a priori common knowledge to all
communicating partners (error detection!)
 eliminates control error propagation since no control signal cross
the temporal firewall interface
Input Firewall: Assumptions
Output Firewall: Guarantees
Thomas Losert
12 September 2002 / p.28
Temporal Firewalls and Validation
Assume a host that is encapsulated between two
temporal firewalls, and input firewall and an output
firewall. These two firewalls form the only interfaces of
this host to its environment.
 The stable properties of the input firewall form important
preconditions for the validation of the component under
consideration. Many assumptions about the environment are
contained in the specification of this input firewall.
 The stable properties of the output firewall form important
postconditions of the validation.
 In the validation process it must be demonstrated that the
postconditions, given in the output firewall specification, are
always TRUE, provided the preconditions associated with the
input firewall hold.
Thomas Losert
12 September 2002 / p.31
Temporal Firewalls and
Composability
A composable architecture must support the
 Independent development of components--relates to
the architecture
 Stability of prior services--relates to the components
 Constructive integration of components--relates to
the communication system.
 Replica determinism--to support transparent
implementation of fault tolerance.
The temporal firewall concept supports these
principles of composability.
Thomas Losert
12 September 2002 / p.32
Outlook
• Requirements
• Basic Principles




•
•
•
•
Composability
Dense Time versus Sparse Time
Communication System Paradigms
Temporal Firewall
Time Triggered Architecture (TTA)
TTP/C protocol
Bus Guardian
Conclusion
Thomas Losert
12 September 2002 / p.33
What is a “Single” Fault in the TTA?
 A Fault-containment region in the TTA is a single chip (SystemOn-a-Chip--SOC--software and hardware) which is at a
physical distance from the other fault containment regions.
 Byzantine failures of chips are masked by a proper physical
interconnection structure.
 It is claimed that in a properly configured TTA-star system,
every possible failure mode of any single chip (software or
hardware) and nearly any possible failure mode of any single
wire is tolerated, without a loss of the timely service.
 Failures outside the fault-hypothesis (e.g., concurrent multiple
chip failures) are detected with a high probability.
Thomas Losert
12 September 2002 / p.34
Priorities in the TTA
 Safety without compromises
• No single point of failure
• Formal analysis of critical functions
 Composability:
• Building systems out of prevalidated components-Component reuse
• Fully specified interfaces in the temporal domain and value
domain
• Two level design methodology
 Flexibility
• Flexible reuse of existing components
Thomas Losert
12 September 2002 / p.35
Design Principles of the TTA
 Provision of a consistent distributed computing base
(Membership service)
 Unification of Interfaces
• Real-Time Service Interface (TT)
• Diagnostic and Management Interface (ET)
• Configuration and Planning Interface (ET)
 Temporal Composability
 Transparent Fault-Tolerance
 Scalability and Openness
Thomas Losert
12 September 2002 / p.36
The TTA supports
 the provision of a global time base to all subsystems
 a predictable temporal behavior that can be analyzed
a priori.,
 the partitioning of a large system into nearly
autonomous composable subsystems by the
introduction of stable interfaces.
 the independent development and validation of these
subsystems, based on these precise interface
specification,.
 the application transparent implementation of faulttolerance by active redundancy.
Thomas Losert
12 September 2002 / p.37
TTA
• Services
 Message transport with
low latency, minimal jitter
 Fault-tolerant internal clock synchronization
 Membership service
• Tolerate arbitrary single faults
 Replicated medium
 Controller-state agreement
 Fail silence (bus guardian)
Thomas Losert
12 September 2002 / p.38
Outlook
• Requirements
• Basic Principles




•
•
•
•
Composability
Dense Time versus Sparse Time
Communication System Paradigms
Temporal Firewall
Time Triggered Architecture (TTA)
TTP/C protocol
Bus Guardian
Conclusion
Thomas Losert
12 September 2002 / p.39
TTP/C
• TT communication system
• Periodic transmission of state messages
• Two redundant channels with TDMA
 Sending slots
 TDMA rounds
Host
Host
Host
Host
CNI
CNI
CNI
CNI
TTP/C
TTP/C
TTP/C
TTP/C
Communication Network
Thomas Losert
12 September 2002 / p.40
TTP/C Cluster Operation
TDMA scheme
Time Message
0:00
1:00
TDMA scheme
global time
Node 1, Msg. 1
Node 2, Msg. 1
Time Message
0:00
1:00
TDMA scheme
Node 1, Msg. 1
Node 2, Msg. 1
TDMA scheme
Time Message
Time Message
0:00
1:00
0:00
1:00
Node 1, Msg. 1
Node 2, Msg. 1
Node 1, Msg. 1
Node 2, Msg. 1
Node (communications controller & host computer)
Interconnection network (replicated: 2 channels)
Thomas Losert
12 September 2002 / p.41
Time Division
Multiple Access
TDMA round n
TDMA round (n-1)
assigned to
node 3
assigned to
node 0
12:00
slot 3
slot 0
assigned to
node 1
3:00
slot 1
5:00
TDMA round (n+1)
assigned to
node 2
slot 2
assigned to
node 3
9:00
slot 3
assigned to
node 0
12:00
slot 0
Real Time
Thomas Losert
12 September 2002 / p.42
TTP/C Protocol Services
• Atomic broadcast and consistent membership
• Global time base of known precision
• Protection against faulty nodes (fault isolation)
Thomas Losert
12 September 2002 / p.43
Fault Hypothesis
•
•
•
•
•
•
Fault-Error-Failure
Component types
Correctness of a component
Type of component failures
Frequency of component failures
Number of faulty components & minimum
configuration
Thomas Losert
12 September 2002 / p.44
Component Types
in a TTA Network
• Node computer
 Host computer
 Communications controller
• Channel of the interconnection network
• Component instances fail statistically
independently and as units (component
instance n fault containment region)
Thomas Losert
12 September 2002 / p.46
Correctness of Nodes
• Correctness of host computer
• Correctness of communications controller
 Correctness as judged by omniscient observer
(and, maybe, as seen by the application)
 Correctness as judged by other nodes of the
cluster: Correctness at interconnection network
interface
Thomas Losert
12 September 2002 / p.47
Correctness of Nodes:
Correctness at Network Interface
• A correct frame is received on the respective channel
during the sending slot of the node
• A node has two network interfaces
• Correct frame




TX starts and ends within slot boundaries
Physical line signal obeys line encoding rules
CRC check is passed
Sender and receiver agree on the distributed state of the
TTP/C protocol (C-state)
• At the TTP/C level a node is considered correct if it is
correct on a least one of its network interfaces
Thomas Losert
12 September 2002 / p.48
Correctness of Channels
• Correct channel will deliver identical and
authentic copies of a frame received from
some node being correct at the network
interface to all correct receivers with known
delay provided there is only a single sender
• Channel may need a minimum time interval
between successive transmissions
Thomas Losert
12 September 2002 / p.49
Types of Node Faults
• A transmission fault is consistent (on a correct
channel)
• A node does not send data outside its assigned
sending slots on both channels of the network
• A node will never send a correct frame
outside its assigned sending slots
• A node will never hide its identity when
sending frames
Thomas Losert
12 September 2002 / p.50
Types of Channel Faults
• A channel does not spontaneously create
correct frames
• A channel will deliver a frame either within
some known maximum delay or never
Thomas Losert
12 September 2002 / p.51
Frequency of Faults
Nodes:
• Only one faulty node within the duration of a
TDMA round
• A node may become faulty only after any
previously faulty node either has shut down
or operates correctly again
Channel:
• Only one channel is faulty during a TDMA
slot
Thomas Losert
12 September 2002 / p.52
Number of Faulty Components &
Minimum Configuration
• Single faults: At most one component may be
faulty during a slot
• Min. three synchronized correct nodes
participating in clock synchronization
• I-frame frequency depending on requirements
• Correct I-frame sender (to allow for
integration)
Thomas Losert
12 September 2002 / p.53
Outlook
• Requirements
• Basic Principles




•
•
•
•
Composability
Dense Time versus Sparse Time
Communication System Paradigms
Temporal Firewall
Time Triggered Architecture (TTA)
TTP/C protocol
Bus Guardian
Conclusion
Thomas Losert
12 September 2002 / p.54
The Tasks of the Guardian
• Correct guardian transforms failure modes at
the interface of a fault containment region
(i.e., component)
• At the interface failure modes of the
supervised unit are replaced by failure modes
of the guardian
• The goal is to handle arbitrarily faulty nodes,
and, thus, to delete the assumptions on faulty
nodes
Thomas Losert
12 September 2002 / p.55
Fault Containment Region
The Tasks of the Guardian
output
to
system
Guardian
input
from
system
Thomas Losert
interface
12 September 2002 / p.56
The Tasks of a Guardian
for TTA Networks
• SOS faults w.r.t. the line encoding rules
• SOS faults w.r.t. the timing of frame
transmission
• Transmission outside the assigned sending slot
(both in startup and synchronized operation)
• Masquerading
• Transmission of invalid C-state data
Thomas Losert
12 September 2002 / p.57
The Central Guardian
Approach: Architecture
Fault
Containment
Region
Error Containment Region
Thomas Losert
12 September 2002 / p.58
The Central Guardian
Approach: Architecture
• Components of the central guardian
• Failure mode transformation units
 Reshape unit
 Transmission timing supervision units (for startup
& synchronous operation)
• TTP/C controller providing
 Access to the global time base
 Access to the distributed C-state of the cluster
Thomas Losert
12 September 2002 / p.59
Outlook
• Requirements
• Basic Principles




•
•
•
•
Composability
Dense Time versus Sparse Time
Communication System Paradigms
Temporal Firewall
Time Triggered Architecture (TTA)
TTP/C protocol
Bus Guardian
Conclusion
Thomas Losert
12 September 2002 / p.60
Conclusion
• The time-triggered architecture provides the
requirements regarding composability, security, and
scalability
• A central guardian is a both technically and
economically promising approach to achieve fault
isolation in time-triggered communication
• The concept is realized and available in hardware
• A C1-based hardware prototype is currently tested
re-doing fault injection experiments where bus-based
clusters suffered fault propagation (IST project FIT)
Thomas Losert
12 September 2002 / p.61
Ongoing Work
• Gigabit TTP/C: TTP/C based on Ethernet,
using standard COTS
• Event-Triggered – Time-Triggered:
 CAN over TTP/C
 TCP/IP over TTP/C
Thomas Losert
12 September 2002 / p.62
Thank you for your
attention!
Thomas Losert
12 September 2002 / p.63