Chapitre 5 Réseaux embarqués de type « TDMA » Time Division Multiple Access 2006 – 2007 Françoise Simonot-Lion ([email protected]) Certains transparents

Chapitre 5

Réseaux embarqués de type « TDMA »

Time Division Multiple Access

2006 – 2007

Françoise Simonot-Lion ([email protected])

Certains transparents de ce cours proviennent du cours de Nicolas Navet (ENSEM – EMN / 2003-2004) du cours de Philip Koopman (Carnegie Mellon / 2004) des transparents disponibles sur le site de TTTech du document TTP/C, High Level SpecificationDocument Protocol v1.1

•TTP/CTTP/C• FlexrayFlexray

Ingénieur Civil des Mines

2ème année

Conception Sûre des Systèmes Embarqués et Ambiants – Module SI342b

Ecole des Mines de Nancy CSSEA SI342b2

Pourquoi des réseaux guidés par le temps - 1

Futures applications embarquées « X-by-Wire » Domaine « chassis » et « contrôle moteur » Connexion mécanique entre les constituants du système

remplacée par une connexion numérique

Avantages

bruit, vibrations, poids, encombrement, …

coût de maintenance, …

évolutivité du système

confort de conduite, assistance à la conduite, …

…

Problèmes Vérifier, prouver la sûreté de fonctionnement du système



Plusieurs cas de figures Cas 1 : seule la consigne conducteur est transmise via un

réseau

processus à contrôlerprocessus à contrôlerconducteurconducteur

Système de contrôleCapteurs de

consigne conducteur

réseau

c a



Plusieurs cas de figures Cas 2 : capteurs de consigne / capteurs processus /

actionneurs / calculateurs partagent le même réseau

conducteur + processus à contrôlerconducteur + processus à contrôler

Capteurs de consigne

conducteur

c a

Système de contrôle

capteurs actionneurs

calculateurs

réseau



Exemple : « steer-by-Wire »

Assistance à la conduite

Capteur Capteur angle volantangle volant

Retour de Retour de forceforce

Capteur Capteur angle roueangle roue

ActionneursActionneurs

de directionde direction

Capteurs Capteurs environnement environnement (caméra)(caméra)

Réseau

VolantVolant


Systèmes X-by-Wire et architecture de communication

Besoins en termes de systèmes de communication Déterminisme, robustesse, tolérance aux fautes (détection, surveillance,

tolérance) Composabilité (intégration de fonctions au sein d’un ECU, au sein d’un

ensemble d’ECU)

Des réseaux TDMA (« Time Division Multiple Access ») – Pourquoi ? Déterminisme assuré par une pré-affectation des intervalles de temps

(« slots ») aux messages et aux stations Preuve « facile » à obtenir (temps de réponse borné, …) Composabilité assurée par un placement dans les « slots » des divers

acteurs communicants

Conception d’architectures d’applications « guidées par le temps »


Réseaux de communication embarqués de type TDMA

TTP/C Première publication en 1994 Hermann Kopetz – Université de Vienne, Autriche (brevet en 1997) Abondamment étudié, prouvé, testé Systèmes embarqués dans l’automobile autres applications (aviation,

transport ferroviaire, …) Des produits : TTTech (www.tttech.com/ )

FlexRay Une initiative de l’industrie automobile (1999) – intégration de Byteflight

(BMW) Plus de flexibilité (ne remet pas en cause les applications déployées au-

dessus de CAN) Pour l’instant, le protocole reste à valider Produits à venir

8 CSSEA SI342b Ecole des Mines de Nancy

TTP/C - « Time Triggered Protocol »

pour les applications de

classe C (temps réel « dur »)

Quelques sites http://www.vmars.tuwien.ac.at/frame-home.html http://tttech.com/technology/articles.htm

Projets connexes https://www.decos.at/index.php http://www.vmars.tuwien.ac.at/projects/xbywire/index.html

http://www.vmars.tuwien.ac.at/frame-home.html

http://tttech.com/technology/articles.htm

http://tttech.com/technology/articles.htm

https://www.decos.at/index.php

http://www.vmars.tuwien.ac.at/projects/xbywire/index.html


Caractéristiques générales

Ordonnancement cyclique des messages Accès au médium sur une base de temps stable

(pas de collision) Tolérance aux fautes intégrée dans le protocole

(support physique redondant) Débits

500kbits/s – 1Mbits/s – 2Mbits/s – 5 Mbits/s – 25 Mbits/s

Topologie : bus ou étoile

conforme aux applications relevant de la classe C (D)


Structure d’un réseau TTP/C

Application Locale

1 micro-contrôleur

Communication NetworkInterface

Contrôleur de

Communication

Bus physique redondé

Application Locale

1 micro-contrôleur


Contrôleur de

Communication

Application Locale

1 micro-contrôleur


Contrôleur de

Communication

CNICNI

CCCC

…

SRU (Smallest

Replaceable Unit)

Pa

rtie co

mm

un

icatio

nP

artie a

pp

licativ

e

Capteurs / actionneurs

CNI(échange

de données)


Principe de fonctionnement - TTP/C

NœudProducteur 1

NœudConsommateur 1

NœudConsommateur 2

Réseau

NœudProducteur 2

Exemple d’application

a b

ba,b



NœudConsommateur 1

NœudConsommateur 2

Réseau

b2b1 b5 b6

t

NœudProducteur 1

NœudProducteur 2

a1a1 a2a2 a3a3 a4a4 a6a6

b2b1

a7a7a5a5

b3 b4

a1a1 a2a2 a3a3 a4a4 a6a6a5a5CNI

CNI

??

??

a1a1 a4a4b2 b2

b2b1 b3 b4



NœudConsommateur 1

NœudConsommateur 2

CNI

CNI

t

NœudProducteur 1

Réseau

NœudProducteur 2


b2b1

a7a7a5a5

b3 b4

a1a1 a2a2 a3a3 a4a4 a6a6a5a5

b2b1 b3 b4

CNI

CNI

??

??

a1a1 a4a4b2 b2

????

??

a1a1 a4a4b2 b2

b2 b2


Principe de fonctionnement - TTP/Ct

NœudProducteur 1

NœudConsommateur 1

NœudConsommateur 2

Réseau

NœudProducteur 2


b2b1

a7a7a5a5

b3 b4

a1a1 a2a2 a3a3 a4a4 a6a6a5a5

b2b1 b3 b4

CNI

CNI

CNI

CNI

??

??

a1a1 a4a4b2 b2

????

??

a1a1 a4a4b2 b2

b2 b2


Un nœud TTP

CNI DPRAM (Dual Ported RAM)

ContrôleurGestion du protocole

TTP/C

Interface d’entrées/sorties avec l’environnement

Micro-contrôleur (CPU, RAM, ROM)supportant les tâches applicatives locales

Gardien de bus

Gardien de bus

•Chien de garde matériel pour garantir un comportement « fail silent »•Garde contre le « babbling idiot »

MEDLDonnées de

contrôle TTP/C (ROM)

« Message Descriptor List »


Topologies TTP/C

Noeud Noeud Noeud Noeud

Bus Noeud

Noeud

Noeud

NoeudSC

SC

Etoile

Noeud

Noeud

Noeud

NoeudSC

SC

Noeud Noeud

Combinaison Bus/Etoile

Noeud

Noeud

Noeud

NoeudSC

SC

Multi-Etoiles

SC

SC


Cluster et « Fault Tolerant Unit » (FTU)

NoeudNoeud

Noeud

NoeudNoeud

Noeud

FTUFTU

• FTU : ensemble des nœuds réalisant les mêmes calculs (redondance de nœuds)• Réplication des informations transmises : chaque nœud émet la même information (3 réplicas / 1 information dans l’exemple)• Cluster : tous les nœuds connectés sur un réseau particulier

Bus


Fault Tolerance - Shadow SRU

NoeudNoeud

• Le nœud fantôme :•émet uniquement si le nœud principal est défaillant,•et, dans ce cas, émet dans le « slot » du nœud principal

Bus

Nœud fantôme


Protocoles de type TDMA – Principes

Un « slot »slot » est un intervalle de temps durant

lequel une station émet un message

Un « round » TDMA est une séquence de slots

telle que chaque station parle exactement 1 fois

NœudMaître

NœudA

NœudB

NœudC

1122 33 44

round

11 22 33 4422 33 44

t

Bus 11

slot

Sync


TTP/C – TDMA

Un nœud (une FTU) peut vouloir transmettre plusieurs

messages Mais 1 slot / nœud dans chaque « round »

dans un round TDMA, chaque nœud (de chaque FTU) transmet un message (un « réplica » du

message) dans son slot (sur chaque bus)

le round se termine quand tous les nœuds (de tous les FTU) ont envoyé un

message

Plusieurs « round » TDMA différents par les messages peuvent

être définis (ordre et taille des slots identiques pour tous les

rounds)

Le « Cluster Cycle » est la suite de tous les « rounds TDMA »

Un « Cluster Cycle » est exécuté en boucle

Une spécification de « Cluster Cycle » est définie pour chaque

mode de marche


TTP/C – ordonnancement des messages

t

Noeud

Message

A B C D A B C D

1 TDMA round 1 TDMA round

MA1

A B C D

MB1

MC1

MD1

MA2

MB2

MC2

MD2

MA1

MB1

MC1

MD1

1 Cluster Cycle

Canal 1

Canal 2


TTP/C – ordonnancement des messages et Tolérance aux fautes

FTU Un slot par nœud de la FTU dans chaque « TDMA round »

La redondance n’est pas traitée au niveau du protocole mais au niveau supérieur (par exemple, dans OSEK-FTCom)

2 nœuds par FTU ? Assure la transmission en cas de défaillance unique de l’un des nœuds – « protection dans le domaine temporel » – pas de conclusion possible en cas de valeurs transmises divergentes

3 nœuds par FTU ? Conclusion possible en cas de valeurs divergentes (moyenne, par exemple) – « protection dans le domaine des valeurs »

« Shadow Node » Un seul slot pour le nœud et son nœud fantôme dans chaque

« TDMA round »


TTP/C – Message Descriptor List (MEDL)

Chaque nœud connaît l’ordonnancement statique

de tous les messages du « Cluster Cycle » pour

chaque mode de marche

Dans un mode de marche donné, à un instant t

donné, dans un « Cluster Cycle » correspond : un et un seul nœud

un et un seul message

Pas d’arbitrage pour l’accès au bus

Synchronisation des horloges

Arbitrage pour le démarrage et l’intégration de

nœuds en ligne


TTP/C – Gardien de bus (« Bus Guardian ») -1

Garantit que le processeur de protocole n’émet des

données sur le bus que dans le slot prévu Protection contre les stations qui sont désynchronisées

Protection contre les stations bavardes (« babbling idiot »)

Le gardien de bus devrait : avoir sa propre horloge

ne pas être trop proche physiquement du processeur de

protocole (éviter les modes de défaillance communs)

avoir sa propre alimentation électrique


TTP/C – Gardien de bus (« Bus Guardian ») -2

Sur un nœud N, ouverture de la ligne uniquement

aux instants spécifiés dans la MEDL exemple, sur le nœud B

t

Noeud A B C D A B C D

MA1

A B C D

MB1

MC1

MD1

MA2

MB2

MC2

MD2

MA1

MB1

MC1

MD1

Canal 1

Canal 2

Round-Slot B

Slot B

Slot B

Slot B


Trames TTP/C

Trame de démarrage (« cold start frame »)

Trame avec « C-State » explicite

Trame avec « C-State » implicite

TypeChangement

de modeC-State

émetteur« Application

Data »CRC

TypeChangement

de mode« Application

Data »CRC

Type Date globale Slot de l’émetteur CRC

16 octets maximum

4 bits 16 bits


Trames TTP/C - vocabulaire

Exemple sur une trame avec « C-State » explicite

Message 1

Message 2

Message 3

Application Application

Message 1

Message 2

Message 3

« Application Data »CNICNI

HorsProtocole

TypeChangement

de modeC-State

émetteurCRCProtocoleProtocole

Protocole

Message 1

Message 2

Message 3

Trame


Trames TTP/C – Calcul du CRC

Trame avec « C-State » explicite

Trame avec « C-State » implicite

TypeChangement

de modeC-State

émetteur« Application

Data »CRC

TypeChangement

de mode« Application

Data »CRC

Calcul du CRC

Calcul du CRC

C-Stateémetteur


Trames TTP/C – validité d’une trame pour un nœud récepteur

Pour qu’une trame soit acceptée par le nœud qui la

reçoit, il faut : qu’elle soit « valide » (conforme à la spécification indiquée

dans la MEDL du nœud récepteur)

et « correcte » : pour une trame à « C-State » explicite,

• CRC reçu = CRC calculé

• et C-State dans la trame = C-State de la station réceptrice

pour une trame à « C-State » implicite,

• CRC reçu = CRC calculé


Trames TTP/C – phases de transmission

slot i dans le « TDMA round »

Durée du slot pour le nœud i

Durée du slot pour le nœud i+1

PRP idle PSP PRP idle PSP TP PRP idle PSP

slot i+1 dans le « TDMA round »

IFGInter Frame Gap

ATAction Time

PSP (Pre Send Phase) – TP (Transmission Phase) – PRP (Post Receive Phase)

TP


TTP/C – Synchronisation des horloges

Pas de trafic supplémentaire pour synchroniser les horloges

4 nœuds au minimum doivent être « Master Clocks » Dérive maximale de leurs horloges de 10

-4 s/s

Chaque nœud récepteur compare son horloge à l’horloge de l’émetteur (si celui-ci est « Master Clock ») Si la différence absolue est supérieure à /2 ( est la précision

demandée), le nœud récepteur se considère incorrect (déconnexion)

Sinon, le nœud remet à jour son horloge (et les données impliquées)


TTP/C – C-State

Chaque nœud N émetteur construit et éventuellement transmet dans son « slot » une structure de donnée C-State, qui comprend : horloge de transmission du nœud N (Master Clock) numéro du slot attribué au nœud N dans ce « TDMA round » … demande de changement de mode au prochain « Cluster

Cycle » vecteur local de « Membership »

vecteur de la vision qu’a le nœud N de tous

les nœuds du « Cluster » (vivant / non reconnu vivant)


TTP/C – Mécanisme d’acquittement - 1

Acquittement non explicite

L’acquittement est déterminé par le nœud N, émetteur dans le slot i, après un traitement des trames en provenance de ses deux successeurs (au plus) dans le TDMA round relation « successeur » de nœud (relation dynamique)

Le processus d’acquittement repose sur la comparaison du vecteur de Membership local au nœud N avec les vecteurs de Membership transmis dans les trames Seules les trames valides (émises dans leur slot, longueur

correcte) sont analysées Trames à C-State explicite / Trames à C-State implicite


TTP/C – Mécanisme d’acquittement - 2

Membership envoyé par un nœud A A est vivant

Membership Point d’un nœud Dans la PRP du noeud

Membership Recognition Point d’un nœud Instant où la décision est définitive pour ce nœud (trame acquittée / non

acquittée)

A l’émission, A a une vision des stations vivantes conforme à celle des stations vivantes

TP A IFG A TP B IFG B TP C IFG C…… ……

Membership Point de A

Membership Point de B

Membership Point de C

MembershipRecognition

Point de A


TTP/C – Mécanisme d’acquittement – 3Processus d’acquittement d’un nœud A Processus d’acquittement d’un nœud A

Hypothèse Ia : A suppose que B voit A et B vivants

Hypothèse Ib : A suppose que B voit A non vivant et B vivant

Erreur de transmission de B ou B a une vision des autres stations différente de celle de AB défaillant – prendre un nouveau premier successeur – recommencer avec hypothèse Ia

Acquittement de A

A ou B est défaillant – continuer avec le deuxième successeur

CRC reçu=

CRC calculé false

true

CRC reçu=

CRC calculéfalse

true

A transmet (C-State : VM(A) vivant) IFG AIFG A

A reçoit une trame de B Transmission du nœud BTransmission du nœud B

IFG BIFG B


TTP/C – Mécanisme d’acquittement – 4Processus d’acquittement d’un nœud A Processus d’acquittement d’un nœud A

Hypothèse IIa : A suppose que C voit A vivant, B non vivant et C vivant

Hypothèse IIb : A suppose que C voit A non vivant, B vivant et C vivant

Erreur de transmission de C ou C a une vision des autres stations différente de celle de AC défaillant – prendre un nouveau deuxième successeur – recommencer avec hypothèse IIa

Acquittement de A

CRC reçu=

CRC calculé false

true

CRC reçu=

CRC calculéfalse

true

A reçoit une trame de C Transmission du nœud CTransmission du nœud C

IFG CIFG C

B et C n’ont pas bien reçu la trameNon Acquittement de A


TTP/C – Service de Membership

Assure que tout nœud vivant sur le réseau a la même vue de l’état des autres nœuds

Service réalisé par le mécanisme d’acquittement


TTP/C – Membership - 1

IFG BIFG B

A transmet (C-State : VM(A) vivant)

A reçoit une trame de B

CRC reçu=

CRC calculé

Hypothèse Ia : A et B vivants

CRC reçu=

CRC calculé

Hypothèse Ib : A mort et B vivant

false

false

B défaillant – prendre un nouveau premier successeur – recommencer avec hypothèse Ia

Acquittement de A

A ou B est défaillant – continuer avec le deuxième successeur

true

true

IFG AIFG A

Transmission du nœud BTransmission du nœud B

A, B restent dans le Membership

•Agreed counter++•Acknowledgement failure counter = 0

•Failed slots counter++ si transmission sur les 2 canaux

B quitte le Membership



IFG CIFG C

A reçoit une trame de C

CRC reçu=

CRC calculé

Hypothèse IIa : A vivant, B mort et C vivant

CRC reçu=

CRC calculé

Hypothèse IIb : A mort, B vivant et C vivant

false

false

C défaillant – prendre un nouveau deuxième successeur – recommencer avec hypothèse IIa

Acquittement de A

true

true

Transmission du nœud CTransmission du nœud C

Non Acquittement de A

A, C restent dans le MembershipB quitte le Membership

•Agreed slots counter++•Failed slots counter++•Acknowledgement failure counter = 0


C quitte le Membership



IFG CIFG C

A reçoit une trame de C

CRC reçu=

CRC calculé

Hypothèse IIa : A vivant, B mort et C vivant

CRC reçu=

CRC calculé

Hypothèse IIb : A mort, B vivant et C vivant

false

false

C défaillant – prendre un nouveau deuxième successeur – recommencer avec hypothèse IIa

Acquittement de A

true

true

Transmission du nœud CTransmission du nœud C

Non Acquittement de AA n’est pas dans le Membership

B, C restent dans le Membership

•Agreed slots counter++•Failed slots counter++•Acknowledgement failure counter ++


C quitte le Membership

Si >= une valeur max, le noeud se déconnecte



Conditions initiales : à l’intégration du nœud Agreed slots counter = 2 Failed slots counter = 0

Lors de la réception d’une trame, un nœud : Calcule la valeur du Slot Status selon les trames reçues sur les 2 canaux (max de

{correct > tentative > other error > incorrect > null frame > invalide}) Slot status = correct agreed slots counter ++ Slot status = incorrect ou invalide failed slots counter ++

Après émission réussie, avant le processus d’acquittement Agreed slots counter = 1

Détection de « clique » Une fois / round, dans le PSP précédant le slot du nœud A :

agreed slots counter < failed slots counter le nœud se déconnecte

agreed slots counter - failed slots counter < 2

erreur globale du système de communication

42 CSSEA SI342b Ecole des Mines de Nancy

FlexRay

Un site http://www.flexray-group.com/

http://www.flexray-group.com/


Origine de FlexRay

1999 – consortium BMW, Daimler Chrysler,

Bosch, Delphi, Motorola, Philips, …

Objectif : déterminisme + flexibilité

Réutilisation des principes de ByteFlight (BMW)


FlexRay – Topologie, couche physique

Bus simple ou redondant

Couche physique optique ou électrique

Débit : 500 kBits/s 10 Mbits/s

Nœud connecté sur un ou les 2 bus (si redondance)

Bus ou étoile

Réutilisation des principes de ByteFlight (BMW)


FlexRay – Format de la trame

RES1

RES2

Frame ID

Length

SYNC

HeaderCRC

DUB

Message IDou données

Données CRC

Data Update Bit (rafraîchissement de la donnée depuis la dernière transmission)

1 1 12 7 91 1 16 0..244 octets 24

5 + (0..246) + 3 octets


FlexRay – Codage des trames

Code NRZ 8N1 : 1 bit start, 1 bit stop, pour chaque octet de données

FSS (Frame Start Sequence) : 8 bits 0 SOC (Start Of Cycle) : 10 bits 1 – 30 bits 0


FlexRay – Medium Access Control

MAC F-TDMA MAC de type TDMA

Accès au médium : statique / dynamique 3 modes : statique pur – dynamique pur – mixed Cycle de fonctionnement périodique < 64 ms

silence Trame physique silence


FlexRay – partie statique

Les slots ont tous la même taille (taille max d’une trame)

Au plus 4095 slots Un nœud peut avoir plusieurs slots / cycle (<=16) Dans le cas d’un bus redondant, un nœud peut

émettre des données différentes dans les slots homologues des deux bus, ou n’émettre rien sur l’un ou les deux bus

Gardien de bus Slots libres pour extensions futures Les nœuds sont informés du «MEDL» au startup


FlexRay – partie dynamique - 1

Chaque nœud possède un ou des identificateurs uniques sur l’ensemble du système (=CAN)

A chaque identificateur est assigné un intervalle de temps (mini-slot) dans lequel la transmission de la trame correspondante peut commencer

Les intervalles sont alloués dans l’ordre des identificateurs

Pas de retransmission en cas d’erreur


FlexRay – partie dynamique - 2

Si redondance des canaux, les choix de transmettre ou non peuvent être différents sur chacun des canaux

Des transmissions successives d’une trame de même identificateur peuvent être de tailles différentes

Le segment dynamique se termine après une durée prédéterminée même si toutes les trames ne sont pas transmises

Pas de gardien de bus dans le segment dynamique

Sous certaines hypothèses sur le trafic, il est possible de calculer des pires temps de réponse (= CAN)


FlexRay – synchronisation d’horloge

Maître unique : un slot dans le cycle statique

Multi-maîtres (2 .. 16)


FlexRay – conclusions

Meilleure utilisation de la bande passante que TTP/C d’où des débits moins élevés et des CPUs moins coûteux

Réutilisation aisée d’applications Event-Triggered développées sur CAN

Services spécifiques à l’automobile comme l’endormissement et le réveil des stations

Grande flexibilité !


FlexRay – conclusions TTP/C

+ Nombreux services pour la SdF (mode de marche, redondance, membership, clique avoidance,…)

+ Visiblement conçu pour la certification - Comportement en dehors des hypothèses de fautes !? Les hypothèses faites

(au plus une faute tous les 2 rounds) sont-elles les bonnes pour l’automobile ??

- Flexibilité / incrémentalité faible FlexRay

+ Conçu spécifiquement pour l’automobile (nécessité de CPU moins puissants que TTP/C, réutilisation des logiciels développés pour CAN, mode veille,…)

+ Flexibilité - Délibérément peu de fonctionnalités liées à la SdF (redondance,

membership) – pb: implémentation moins efficace au dessus de la couche LdD

- Validation du protocole !

Documents

Chapitre 5 Réseaux embarqués de type « TDMA » Time Division Multiple Access 2006 – 2007 Françoise Simonot-Lion ([email protected]) Certains transparents