TEAEin fehlertolerantes

dynamisches zeitgesteuertes Protokoll

Jens Chr. Lisner

1

/ 43

Inhalt

• Grundlagen

• Das TEA Protokoll

• Idee

• Architektur

• Aufbau und Arbeitsweise des Protokolls

• Sonstiges

• Modellbasierte Analyse

• Zusammenfassung und Ausblick

2

2

/ 43

Feldbusprotokolle

• in Automation, Automotive, Avionics und Raumfahrt

• Beispiele: CAN, SAFEbus, FlexRay, byteflight, TT-CAN, ARINC 429, TTP/C

• Einsatz in kritischen Anwendungen⇒ Fehlertoleranzanforderung

• Zeitgesteuerte Protokolle besonders geeignet

3Grundlagen

3

/ 43

Fehlertoleranz

• Fehlertolerantes System

• fehlertolerante HW-Architektur

• fehlertolerantes Protokoll(hier: ISO/OSI Layer 2 und 3)

• Zeitgesteuerte Arbitrierung (z.B. statisches TDMA, Minislotting)

• Encoding (z.B. Prüfsummen, CRC)

• Ziel: Fehlerfreie Komponenten sind immer in der Lage zu kommunizieren.

4Grundlagen

4

/ 43

Arbitrierung (statisches TDMA)

Jeder Sender muß senden!

Zeit

X sendet Y sendet Z sendet

t1 t2 t3Δt ΔtΔt

Zyklus

5Grundlagen

5

/ 43

Arbitrierung (statisches TDMA)

• Vorteile:

• Deterministisch

• Senden in eigenem Slot immer möglich

• Nachteile:

• Sendereihenfolge statisch

• Nachrichtenlänge statisch

• Nachrichten müssen gesendet werden, auch wenn keine Daten zu übertragen sind

• Beispiele: TTP/C, FlexRay (statisches Segment)

6Grundlagen

6

/ 43

Arbitrierung (Minislotting)

Zeit

X sendetY sendet nicht

Z sendet

ΔtminΔtX ΔtZ

7Grundlagen

7

/ 43

Arbitrierung (Minislotting)

Zeit

ΔtQ

Q X YV W

ΔtminΔtmin Δtmin Δtmin ΔtZ

Z

„Verlorene“ Bandbreite: 4 Δtmin

8Grundlagen

8

/ 43

Arbitrierung (Minislotting)• Vorteile:

• Reihenfolge der Zugriffsrechte bekannt

• Nachrichtenlänge dynamisch

• Nachteile:

• Sendezeitpunkt und -länge unbekannt

• ggf. hoher Bandbreitenverlust

• Beispiele: byteflight, ARINC 459

9Grundlagen

9

/ 43

Architektur: Kanal

• Topologie: Bus, Stern, gemischt

• Kanalfehler:

• Nachrichtenverlust

• Nachrichtenverfälschung/-zerstörung (erkennbar mit hinreichend guten Prüfsummenverfahren)

• byzantinischer Kanalfehler:Wenn K die Menge der Knoten ist, dann empfangenE ⊂ K die Nachricht fehlerfrei, undK - E die Nachricht fehlerhaft

10Grundlagen

10

/ 43

Architektur: Kanal

Knoten Knoten Knoten

Kanal

Kanal B

A

Text

Nachrichten werden auf zwei Kanälen übertragenMaßnahme gegen Kanalfehler:

11Grundlagen

11

/ 43

Architektur: Knotenzum Host

CommunicationController (CC)

BD BD

zum/vom Kanal

Uhr

12Grundlagen

12

/ 43

Architektur: Controller

• Aufgaben (z.B.):

• Senden/Empfangen von Nachrichten

• Kodieren/Dekodieren von Nachrichten

• Scheduling

• Uhrensynchronisation

• Interface zum Host

13Grundlagen

13

/ 43

Architektur: Controller

• Mögliche Fehler:

• Senden falsch codierter Nachrichten

• Senden von Nachrichten mit „falschem“ Inhalt (i.A. nicht erkennbar)

• Nachrichtenausfall

• Nachricht zum falschen Zeitpunkt gesendet⇒ Kollisionen möglich

14Grundlagen

14

/ 43

Architektur: Knoten

Freigabe Ydurch BG

X sendet Y sendetfehlerfrei Z sendet

freigegeben

gesperrt

X sendet Y sendetzu spät Z sendet

Nachricht wird abgeschnitten ⇒ keine Kollisionen

15Grundlagen

15

/ 43

Architektur: Guardian

• Dezentrale Bus Guardians

• unabhängig von Controller (eigene Uhr, eigene Synchronisation) ⇒ teuer

• abhängig vom Controller ⇒ billig, aber nicht fehlertolerant

• Zentraler Bus Guardian

• An jedem Eingang eines Sternkopplers ein Bus Guardian

• Eigener Controller zur Steuerung

• ⇒ nur Stern-Topologie

16Grundlagen

16

/ 43

Das TEA-Protokoll

• Neues Zeitgesteuertes Protokoll mit statischen und dynamischen Anteilen

• Fehlertolerant (Doppelfehler)

• Bandbreitenverlust minimal

• Nachrichten dynamischer Länge

• Verschiedene Schedulingalgorithmen

• Formale Beschreibung

• Fehlerfortpflanzung

• Struktur/Timing

• Korrektheit Beweisbar

17TEA - Idee

17

/ 43

Das TEA-Protokoll

Fehlerannahme

• Knotenfehler(Ausfallfehler, fehlerhaftes Encoding, fehlerhafter Nachrichteninhalt, Timingfehler, nicht byzantinisch)

• Kanalfehler(Ausfallfehler, „Message corruption,“ byzantinisch)

• Knoten & Kanalfehler (Doppelfehler)(alle Kombinationen)

18TEA - Idee

18

/ 43

Das TEA-ProtokollIdee

• (Zeitgesteuerter) Zyklus wird geteilt

• Regular Part (statisch)

• Extension Part (dynamisch)

• Jeder Sender kann Slot für Extension Part anfordern

• Schedule wird unmittelbar vor Extension Part festgelegt (Agreement Algorithm)

• Zwei Controller überwachen sich gegenseitig

Time-triggered Efficiency by Agreement

19TEA - Idee

19

/ 43

Das TEA-Protokoll

2m2 +1

B

Aphase phase

confirmationrequest

regular part extension

1 m m+1 m+em

20TEA - Idee

20

/ 43

TEA Architektur: Knoten

21

Drivers

from/to Host 2

Controller 1 Controller 2

B

A

Gates and

Node

from/to Host 1

TEA - Architektur

21

/ 43

TEA Architektur: Knoten

B,1

from C2

from C2D

A

B

C1to GA,2

to GB,2

DA,1

A,1

GB,1

G

22TEA - Architektur

22

/ 43

TEA Architektur: Knoten

• Dezentral

• Jede Topologie möglich

• Vollzieht Schedule für Extension Part nach

• Unabhängig

• Nachteil:Fehlerhafter Controller kann Nachbarn am senden hindern.

23TEA - Architektur

23

/ 43

Gate

c,j,i

Tx c,i

c,i

Guard!

!

!

!

"

Gate

Driver

!

Switch

Pwrc,i

TxCh

24TEA - Architektur

24

/ 43

TEA: Regular Part

• Statisches TDMA

• Aufgeteilt in

• Request Phase

• Confirmation Phase

• Beide Phasen haben gleiche Länge

• Ergebnis: Schedule für Extension Part

• Jeder Sender muß mind. einmal in jeder Phase senden

25TEA - Arbeitsweise

25

/ 43

TEA: Regular Part (Scheduling)RequestPhase

Slot 1 Slot 2 Slot 3 Slot 4

Kanal A

Kanal B

S1 S3 S5 S7

S2 S4 S6 S8

Confirm.Phase

Slot 5 Slot 6 Slot 7 Slot 8

Kanal A

Kanal B

S2 S4 S6 S8

S1 S3 S5 S7

26TEA - Arbeitsweise

26

/ 43

TEA: Request Phase

• Request Phase

• Jede Nachricht enthält ein „request bit.“

• Requests werden gesammelt

• Confirmation Phase

• Jede Nachricht enthält einen „confirmation vector“

• 3 mögliche Werte: request, no request,unknown (im Fehlerfall)

• „request matrix“ wird aufgebaut

27TEA - Arbeitsweise

27

/ 43

TEA: Request Phase (Slot 1)Confirmance Vectors

ss2

s3

s4

s5

s6

s7

s8

1s s2 s3 s4 s5 s6 s7 s8

A

A

A

A

B

B

B

B

B B B BA A A A

f n

fn

Req

ues

ts1

28TEA - Arbeitsweise

28

/ 43

TEA: Request Phase (Slot 2)Confirmance Vectors

ss2

s3

s4

s5

s6

s7

s8

1s s2 s3 s4 s5 s6 s7 s8

A

A

A

A

B

B

B

B

B B B BA A A A

f n

fn

Req

ues

ts1

29TEA - Arbeitsweise

29

/ 43

TEA: Request Phase (Slot 3)Confirmance Vectors

ss2

s3

s4

s5

s6

s7

s8

1s s2 s3 s4 s5 s6 s7 s8

A

A

A

A

B

B

B

B

B B B BA A A A

f n

fn

Req

ues

ts1

30TEA - Arbeitsweise

30

/ 43

TEA: Request Phase (Slot 4)Confirmance Vectors

ss2

s3

s4

s5

s6

s7

s8

1s s2 s3 s4 s5 s6 s7 s8

A

A

A

A

B

B

B

B

B B B BA A A A

f n

fn

Req

ues

ts1

31TEA - Arbeitsweise

31

/ 43

TEA: Confirmation Phase (Slot 5)Confirmance Vectors

ss2

s3

s4

s5

s6

s7

s8

1s s2 s3 s4 s5 s6 s7 s8

A

A

A

A

B

B

B

B

B B B BA A A A

f n

fn

Req

ues

ts1

32TEA - Arbeitsweise

32

/ 43

TEA: Confirmation Phase (Slot 6)Confirmance Vectors

ss2

s3

s4

s5

s6

s7

s8

1s s2 s3 s4 s5 s6 s7 s8

A A

f n

fn

Req

ues

ts1A

A

A

A

B

B

B

B

B B B BA A

33TEA - Arbeitsweise

33

/ 43

TEA: Confirmation Phase (Slot 7)Confirmance Vectors

ss2

s3

s4

s5

s6

s7

s8

1s s2 s3 s4 s5 s6 s7 s8

B

B

B B B BA A A A

f n

fn

Req

ues

ts1A

A

A

A

B

B

34TEA - Arbeitsweise

34

/ 43

TEA: Confirmation Phase (Slot 8)

ss2

s3

s4

s5

s6

s7

s8

1s s2 s3 s4 s5 s6 s7 s8

1A

A

A

A

B

B

B

B

B B B BA A A A

f n

fn

Req

ues

ts

Confirmance Vectors

35TEA - Arbeitsweise

35

/ 43

TEA: Agreement Algorithm

• Ergebnisvektor wird gebildet

• Default-Wert falls Wert nicht eindeutig

• Korrektheit formal bewiesen

• Effizient: Übereinstimmung wird innerhalb eines Zyklus erreicht

• Toleriert Doppelfehler

36TEA - Arbeitsweise

36

/ 43

Sonstiges

• Scheduling im Extension Part

• FIFO

• Priority

• FIFO-first

• Priority first

• Slots dynamischer Länge

• Fehlertolerant!

37TEA - Sonstiges

37

/ 43

Network Behavior Functions

• Methode zur formalen Beschreibung der Fehler-fortpflanzung in einem System

• System dargestellt als gerichteter Graph

• Berücksichtigt:

• Verhalten einer Komponente

• Verhalten an den Eingängen in die Komponente

• Verhalten ist Zeitabhängig

• Automatisierbar

38TEA - Modellbasierte Verfahren

38

/ 43

Timed Grammars

• Protokollablauf ist aus Aktionen aufgebaut

• Verschiedene Aktionen können verknüpft werden (Sequenz, Parallel, ...)

• Struktur des Systems: Darstellung als Grammatik

• Zu einer Aktion gehören Offset und Dauer

• Die Länge von Offset und Dauer sind „ungenau“(z.B. Gangunterschied von Uhren!)

• Zu jedem Operator gibt es eine Rechenvorschrift

• Timings von Aktionen lassen sich automatisiert berechnen

39TEA - Modellbasierte Verfahren

39

/ 43

Timed Grammars

40

msg

sender

neighbor

msgOfstmsgOfst

TEA - Modellbasierte Verfahren

40

/ 43

Zusammenfassung

✓Zeitgesteuertes Protokoll mit statischen und dynamischen Anteilen

✓Fehlertolerant (Doppelfehler)

✓Bandbreitenverlust minimal

✓Nachrichten dynamischer Länge

✓Verschiedene Schedulingalgorithmen

✓Formale Beschreibung

• Network Behavior Functions

• Timed Grammars

✓Korrektheit bewiesen

41

41

/ 43

Zusammenfassung

42

TEA:Erstes zeitgesteuertes, voll

fehlertolerantes Protokoll mit dynamischen Anteilen!

42

/ 43

Ausblick

• Weitere Operationsmodi (z.B. Startup)

• Aufbau in Hardware

• Weiterentwicklung formaler Methoden

• Erweiterung der Fehlerannahme(z.B. byzantinische Controllerfehler)

• Anfragen mehrerer Slots

Fragen ?

43

43

/ 43

Echtzeitprotokolle

• in Automation, Automotive, Avionics und Raumfahrt

• Echtzeiteigenschaft:Jede Aktion muß bis zu einem bestimmten Zeitpunkt abgeschlossen sein.

• Einsatz in kritischen Anwendungen⇒ Fehlertoleranzanforderung

44

44

/ 43

Echtzeitprotokolle

• nicht fehlertolerant:

• CAN (Automatisierung, Automotive)

• byteflight (Automotive)

• FlexRay (Automotive - mit dyn. Segment)

• fehlertolerant:

• TTP/C (Automotive, Avionics)

• FlexRay (Automotive - ohne dyn. Segment)

45

45

/ 43

Arbitrierung (Ereignisgesteuert)

Zeit

Ereignis

X sendet

Ereignis 2 Ereignis 2

Y sendet

Beispiel: CAN

46

46

/ 43

Arbitrierung (Ereignisgesteuert)

• Vorteile:

• Zeitunabhängig

• Kanalzugriff falls notwendig

• Nachrichtenlänge dynamisch

• Nachteile:

• Sendezeitpunkt unbekannt

• Kanalzugriff nicht immer sofort möglich

• Beispiel: CAN

47

47

/ 43

Fehlertoleranz

• Komponenten:

• Kanal

• Knoten (Controller, Uhren, ...)

• Typische Fehler:

• Nachrichtenkollision

• Nachrichtenverlust

• Verfälschung der Nachricht

• Senden der Nachricht zum falschen Zeitpunkt

48

48

/ 43

TEA: Request Phase

• Jeder Slot wird durch zwei Sender belegt (Kanal A und B)

• Nachbarn senden auf verschieden Kanälen

• Jede Nachricht enthält ein „request bit.“

• Jeder Empfänger sammelt die Requests der anderen Controller

49

49

/ 43

TEA: Confirmation Phase

• Zuordnung zu Kanälen wird vertauscht.

• Jede Nachricht enthält einen „confirmation vector“

• 3 mögliche Werte pro Sender

• request

• no request

• unknown (im Fehlerfall)

50

50

/ 43

TEA Architektur: Gate

• Zerfällt in ...

• Output Driver

• Switch

• Switch kann die Spannungsversorgung von Output Driver unterbrechen

• Switch wird vom Nachbarcontroller gesteuert

• Beide Teile gehören in verschiedene Fehlerbereiche

51

51

/ 43

Architektur: Controller

• Maßnahmen gegen Fehler:

• Nachrichtenverfälschung: Prüfsummen/Encoding

• Kollisionsvermeidung:

• dezentrale Bus Guardians

• zentrale Bus Guardians

• Doppelcontrollerarchitektur (später)

52

52

/ 43

TEA Architektur

• Doppelkanal

• Stern, Bus oder gemischte Topologie

• Doppelcontroller

• Jeweils zwei unabhängige Controller pro Knoten

• Ein Knoten für mehrere Hosts

• Gate für Zugriffskontrolle

53

53

/ 43

TEA: Agreement Algorithm

Voraussetzungen:

• Mind. 8 Controller

Ziel:

• Bitvector (request, kein request)

• Bitvector gleich für jeden Controller

54

54

/ 43

Timed Grammars

• Protokollablauf ist aus Aktionen aufgebaut

• Aktionen werden aus anderen Aktionen produziert

• Zyklus besteht aus Regular und Extension Part

• Regular Part besteht aus Phasen

• Phase besteht aus Slots

• etc.

• Verschiedene Aktionen können verknüpft werden (Sequenz, Parallel, ...)

55

55

/ 43

Timed Grammars

• Struktur des Systems: Darstellung als Grammatik

• Hierarchisch

• Mehrere Produktionen pro Aktion möglich

• Zu einer Aktion gehören Offset und Dauer

• Die Länge von Offset und Dauer sind „ungenau“(z.B. Gangunterschied von Uhren!)

• Zu jedem Operator gibt es eine Rechenvorschrift

• Timings von Aktionen lassen sich automatisiert berechnen

56

56

/ 43

Sonstiges: Slots dynamischer Länge

• Slots dynamischer Länge im Extension Part möglich

• Länge wird aus Längenfeld im Header abgeleitet

• Fehlertolerant

• Verifiziert durch Zustandsraumexploration

57

57

/ 43

Arbitrierung (Minislotting)

Zeit

X Y

ΔtQ

Q V W

tlastΔtminΔtmin Δtmin

Z kann nicht mehr senden!

58

58

/ 43

Architektur: Kanal

Knoten Knoten Knoten

Kanal

Text

Topologie: Bus, Stern, gemischt

59

59

/ 43

Architektur: Uhr

• Taktgenerator (Quarz)

• Spezifizierte max. erlaubte Abweichung von Nominalfrequenz⇒ Uhrensynchronisation erforderlich

• Uhrensynchronisation im Controller

• Uhren als Teil des Controllers

60

60

/ 43

Architektur: Knotenzum Host

CommunicationController (CC)

BD BD

zum/vom Kanal

Uhr

BG

Uhr

ARM

61

61

/ 43

Architektur: Driver

• Verbindung zwischen Kanal und Controller

• Zweimal pro Kanal (Hin- und Rückrichtung)

• Mögliche Fehler:

• Nachrichtenverlust

• Nachrichtenverfälschung

62Grundlagen

62