chapitre 3.pdf

Chapitre 3: Fiabilisation de transmission

(Couche liaison)

ABBACI KAHYA N

Université Badji Mokhtar Annaba

Département d'informatique

Kahya.noudjoud@gmail.com

Plan

Introduction

Délimitation de trames

Détection/Correction d’erreurs

Contrôle de flux

Introduction

Couche liaison

Nous avons étudié tous les mécanismes à mettre en œuvre pour

transmettre un flot de bits entre deux systèmes distants.

La couche physique nous permet une transmission brute de bits

par un medium reliant une machine A à une machine B.

Comment assurer une transmission exempte d'erreurs sur un

canal de communication ? couche liaison.

La couche liaison est responsable du transfert des

datagrammes d’un nœud à un nœud adjacent à travers une liaison.

DEFINITION : Ensemble des matériels et des logiciels

fournissant les moyens fonctionnels nécessaires pour

acheminer des données avec un taux d'erreur garanti.

OBJECTIF : fiabiliser la transmission physique et offrir un

service a la couche RESEAU pour acheminer les bits remis

par le processus réseau vers leur destination.

Services offerts

La délimitation des blocs de données

Contrôle de l’intégrité des données reçues.

L’organisation et le Contrôle de l’échange.

Contrôle de la liaison et l'accès à un canal partagé (MAC)

Trames

Les données sont fractionnées en trames.

Une donnée échangée au niveau liaison s’appelle une trame.

Données + Commandes

Problème : comment délimiter les trames ?

Délimitation de trames

Délimitation des trames

Il existe trois méthodes :

Indiquer la taille de chaque trame (Compter les caractères)

Utiliser des champs délimiteurs de trame

Violer le codage normalement utilisé dans la couche physique

Compter les caractères

On utilise un champ dans l'en-tête de la trame pour indiquer le

nombre de caractères de la trame.

Problème : si la valeur du champ est modifiée au cours de la

transmission.

Méthode rarement utilisée seule.

Compter les caractères

Utilisation des délimiteurs

Un fanion (délimiteur) est placé :

au début de chaque trame

à la fin de chaque trame (en fait, au début de la suivante)

Un fanion (flag) = séquence particulière de bits.

Des bits de transparence sont alors nécessaires pour

qu’une séquence binaire dans la trame ne corresponde

accidentellement au fanion.

Exemple

Fanion : 01111110

Bit de transparence : 0 inséré après toute séquence de cinq 1

successifs dans la trame.

Technique utilisée dans :

HDLC High-Level Data Link Control

PPP Point to Point Protocol

Exemple

01111110 01111110

01011001111110

Données :

Trame :

010110011111010

Utiliser des fanions

Avantages

permet toujours de retrouver la synchronisation

permet l'envoi de trames de tailles quelconques

technique la plus simple

.

Violer le codage

Utilisable lorsque le codage sur le support physique contient

des redondances

Par exemple :

0 = impulsion positive puis négative

1 = impulsion négative puis positive

On peut donc utiliser les combinaisons positive-positive et

négative-négative pour délimiter les trames

Utilisée dans la norme 802

Détection/Correction d’erreurs

Problématique

Le support matériel utilisé par la couche physique n'est pas fiable à 100%

Il est par conséquent nécessaire de pouvoir détecter des erreurs parmi la suite

de bits reçue, et éventuellement les corriger. Pour cela, la couche liaison de

données de l'émetteur ajoute des bits au message à transmettre, qui permettent

à la couche liaison de données de l'entité réceptrice du message de vérifier la

cohérence de ce qu'elle a reçu.

La problématique des erreurs comporte 3 aspects :

la détection d'une erreur ;

la localisation de l'erreur détectée ;

la correction de l'erreur trouvée.

Pour répondre a ces problèmes, on utilise des codes qui sont

appliqués au message à transmettre.

Ils permettent de détecter certaines erreurs, mais pas

nécessairement toutes, et peu permettent la correction.

Code simple

Un code simple : la répétition

Une approche naïve consiste à dupliquer ( c'est-à-dire répéter) le message à

transmettre.

Supposons que le message effectivement transmis soit le double du message réel.

Par exemple, pour envoyer 11100010, on transmet 1110001011100010

La détection et la localisation des erreurs sont alors simples : on cherche les

différences entre la première et la seconde moitiés du message.

Par contre, il est impossible de corriger une erreur détectée : le bit erroné est

différent dans les deux copies, et rien ne permet de dire lequel est le bon.

Pour remédier à ce problème, on peut envoyer les message en 3 exemplaires au

lieu de 2

Dans ce cas, un bit a soit la même valeur dans toutes les copies, ou la même

valeur dans deux d'entre elles et l'autre valeur dans la troisième copie. Le bit

correct est celui qui apparaît en deux exemplaires.

Un code simple : la répétition

Le code de répétition est simple, mais présente de nombreux

inconvénients:

o La détection et la correction d'erreurs nécessitent l'introduction

de redondance dans les messages transmis. La taille du message à

transmettre peut alors augmenter de manière significative.

o Certaines erreurs peuvent ne pas être détectées. C'est le cas

lorsque l'on utilise la redondance, si le même bit est erroné dans

toutes les copies du message.

Détection d’erreurs

Codes à contrôle de parité

Les codes à contrôle de parité sont de parité soit paire, soit impaire.

Dans le premier cas, on va protéger une séquence de bits en ajoutant

un nouveau bit de telle sorte que le nombre de bits ayant la valeur 1

(dans la séquence protégée plus le bit introduit) soit pair. Dans le

second cas, ce nombre doit être impair.

VRC (Vertical Redundancy Check)

C'est la technique la plus simple. Un code ASCII étant défini sur 7 bits,

on utilise le 8ème bit de l'octet pour introduire le code vérificateur.

Codes à contrôle de parité

Exemple : Pour transmettre la chaîne de caractères IUT, on code

chaque lettre en ASCII, puis on a joute le code de parité.

Pour envoyer le message avec un code de parité pair, on transmet

(avec l'ordre d'envoi des bits de gauche à droite) :

Ce code permet de détecter les erreurs en nombre impair sans

pouvoir corriger. Il est peu efficace.

Codes à contrôle de parité

LRC (Longitudinal Redundancy Check)

Le principe est similaire à celui du VRC, mais au lieu de protéger les caractères un par un, on protège l'ensemble des bits de même rang de tous les caractères. On obtient alors un code de protection sur 7 bits.

Pour envoyer le message avec un code de parité pair, on transmet:

Codes à contrôle de parité LRC+VRC

On peut également combiner les deux techniques précédentes. On

protège alors chaque caractère par un code VRC et l'ensemble des bits

par un code LRC. On obtient donc un LRC sur 8 bits. La parité des LRC

et VRC utilisés est la même (tous les deux pairs ou tous les deux

impairs).

Exemple : Pour transmettre la chaîne de caractères IUT, on code chaque

lettre en VRC puis en LRC :

Pour envoyer le message avec un code de parité pair, on transmet:

Codes polynomiaux

Les codes polynomiaux, encore appelés CRC (Cycling Redundancy

Code), sont utilisés par la plupart des protocoles actuels.

Un code polynomial est basé sur l'utilisation d'un polynôme générateur

G(x) connu à l'avance par à la fois l'émetteur et le récepteur du message.

Les polynômes manipulés sont binaires : tous les coefficients sont 0 ou 1

Par conséquent, un polynôme générateur de degré k s'écrit sous la forme :

Codes polynomiaux

Le polynôme G(x) est associé à une valeur binaire.

Exemple : La valeur binaire associée au polynôme G(x) = x 3 +

x+ 1 est 1011

Soit M le message (séquence de bits) à protéger. Un polynôme

M(x) lui est associé :

Exemple : Au message M = 1101 est associé le polynôme M(x) =

x 3 + x 2 + 1

Emetteur Soit D(x) les données à envoyer et k le degré de G(x)

1) calculer D(x)*xk

revient à ajouter k zéros (poids faibles) à D(x)

2) calculer D(x)*xk / G(x)

on obtient le quotient Q(x) et le reste R(x)

3) calculer T(x) = D(x)*xk - R(x)

revient à remplacer les k zéros par R(x)

Récepteur

T(x) est le mot transmis par l’émetteur

T’(x) est le mot reçu par le récepteur

Le récepteur effectue le test suivant :

Si T’(x) / G(x) donne un reste égal à 0 alors

pas d’erreur

sinon

une erreur

fin si

Normalisation

Plusieurs polynômes ont fait l’objet d’une norme car possédant

de bonnes propriétés

CRC 12 = x12 + x11 + x3 + x2 + x +1

CRC 16 = x16 + x15 + x2 + 1

CRC CCITT = x16 + x12 + x5 + 1

Exemple

D(x) = 0101 1100

G(x) = 1 1000 0101

D(x)*xk = 0101 1100 0000 0000

R(x) = 0100 1101

T(x) = 0101 1100 0100 1101

Exemple Exercice1 : Soient le polynôme générateur G(x) = x 3 + x + 1 et le

message à envoyer M = 1101. Le polynôme correspondant au

message est M(x) = x 3 + x 2 + 1. Le degré de G(x) est 3. Donc,

P (x) = M(x).x 3 = x 6 + x 5 + x 3

1. Effectuons la division de P (x) par G(x).

2. Trouvez R(x) et le message à envoyé.

Détection et Correction d’erreurs

Correction d'erreurs

Deux approches permettent de corriger les erreurs :

les codes auto-correcteurs, tels que le code de Hamming

la correction par retransmission qui demande à l'émetteur de

retransmettre le message lorsqu'une erreur est détectée.

Le code de Hamming

Le code de Hamming est utilisé dans les transmissions de

données car il permet de détecter et de corriger une erreur

survenue dans un bloc transmis.

Principe du codage.

On fixe un entier k et on code chaque bloc de m = 2k- k-1

bits de données par un bloc de n = 2k- 1 bits en ajoutant

donc k bits, dits de correction, a certaines positions au bloc

de m bits.

Le tableau suivant indique les nombres de bits de correction,

de données pour différentes valeurs de k.

Le code de Hamming

Position des k bits de correction :

Les k bits de correction sont placés dans le bloc envoyé aux

positions d’indice une puissance de 2. Ainsi, en notant k1 k2 k3

les bits de correction et m1 m2 m3 m4 les bits de données, le

bloc envoyé est :

m4 m3 m2 k3 m1 k2 k1.

Le code de Hamming Calcul des k bits de correction :

Les k bits de correction sont calcules en utilisant une matrice de parité H, représentée ci-dessous pour k=3.

Les k bits de correction sont tels qu’en

considérant le vecteur

Le code de Hamming

On obtient ainsi 3 équations scalaires que doivent vérifier les k

bits de correction :

Le code de Hamming

Réception des données et vérification :

On reçoit le bloc C = c1 c2 c3 c4 c5 c6 c7 qui peut être

différent du bloc A si il y a eut des perturbations sur la ligne.

Si on considère qu’il n’y a eut qu’une seule erreur de

transmission, alors on peut écrire :

C = A + E ou E est un bloc contenant 6 bits a 0 et 1 bit a 1.

Les positions des 0 et du 1 sont inconnues dans le bloc.

Le code de Hamming

On calcule le vecteur S tel que :

Finalement, S est une des colonnes de la matrice de parité dont

l’indice nous donne la position de l’erreur dans le bloc C. L’erreur est

corrigée en changeant le bit considère d’état.

s3 s2 s1 est le code binaire de position de l’erreur dans le bloc C que

nous obtenons a partir des équations suivantes :

Le code de Hamming

Exercice 1: On souhaite envoyer le message 1010, compléter

le mot de Hamming correspondant.

Exercice 2 : On veut envoyer le mot 1011, quels bits, je doit

lui adjoindre et quelle séquence je transmettrai alors ?

Exercice 3 : y a-t-il une erreur dans le mot suivant ? 1101101

Demande de retransmission

Lorsque l'on effectue de la correction par demande de

retransmission, l'émetteur conserve une copie des données

envoyées. Le récepteur applique une méthode de détection

des erreurs. Quand il reçoit un message, le récepteur renvoie

un paquet à l'émetteur, contenant un acquittement positif si

aucune erreur n'a été détectée, et un acquittement négatif si

une erreur a été trouvée. Lors de la réception d'un

acquittement négatif, l'émetteur retransmet le message

erroné.

Contrôle de flux

contrôle de flux

Réguler le flux de données entre un émetteur et un récepteur Capacité de stockage

Capacité de traitement

Plusieurs variantes de contrôle de flux :

Protocole de type « envoyer et attendre » (Send and Wait)

Les données ne circulent que dans un sens

Une seule trame est envoyée a la fois

Le récepteur Informe I 'émetteur de son état par un acquittement

Protocoles avec fenêtre d'anticipation (Sliding Window)

Les données circulent dans les deux sens

Plusieurs trames sont envoyées a la fois

Liste des numéros de séquence de trames = fenêtre d'anticipation

Contrôle de flux : principes

Chaque trame envoyée doit être acquittée par le récepteur.

L’acquittement peut être positif (ACK) ou négatif (NACK)

Contrôle de flux : principes Problème 1:

Solution : Armer un temporisateur T1 après l’envoi d’une trame d’information.

Si T1 expire avant la réception d’un acquittement (+ ou -), Alors l’émetteur renvoi la même trame d’information.

Contrôle de flux : principes

Problème 2 :

Solution : Numérotation de trames (identification).

Contrôle de flux : principes

Problème 3 :

Si chaque trame doit être acquittée par une trame spécifique

et d’une manière individuelle l’efficacité de la liaison sera

très faible.

La plupart de temps les extrémités de la liaison seront en état

d’attente d’acquittement.

Contrôle de flux : principes

Solutions :

Piggypacking : le récepteur peut acquitter une trame

d’information reçue par l ’envoi d’une autre trame

d’information.

Anticipation : l’émetteur peut envoyer w trames sans avoir

un acquittement.

Acquittement groupé : Le récepteur peut acquitter par une

seule trame un groupe de trames reçues.

• Numérotation de trames d’information

• Acquitter la trame N c’est acquitter toutes les trames précédentes 1..N

Contrôle de flux : principes

L’acquittement peut être explicite ou implicite

Chaque trame d’informations est identifiée par un numéro.

La numérotation de trames est faite modulo 2n où n est le

nombre de bits utilisés pour représenter les numéros de

trames.

Selon le protocole HDLC, n = 3

Protocoles de liaison de données

1960 : BSC (Binary synchronous communication) - IBM

Protocole orienté caractère

Synchronisation en continue

1970 : SDLC (Synchronous Data Link Control) - IBM/ANSI

Orienté trame

1976-80 : HDLC (High Data Link Control) - ISO

Protocole orienté bit

ISO 3309 (format), ISO 4335 (HDLC), ISO 7776 (LAP-B), ISO 7448 (MLP) ISO 8471 (HDLC équilibré)

1985 : Liaison de réseaux locaux

HDLC

HIGH-LEVEL DATA LINK CONTROL Protocole de référence normalisé par I'lSO.

Version très générale (LAP-B, LAP-D, LLC, PPP, LAP-X, ...),

Utilise dans LAN, Internet, GSM.

Caractéristiques:

Transmission synchrone

Oriente bit

Liaisons point-a-points ou multi-points

Full Duplex

Mécanisme d'anticipation

fenêtre de 7 trames : HDLC et LAP-B

fenêtre de 127 trames : LAP-B étendu, PPP

Transmission fiable ?

Problème : Garantir la réception correcte, sans duplication

et dans l’ordre des informations transmises.

Solution:

Utilisation d’un code polynomial. G( x) = x16 + x15 + x2 + 1.

Utilisation de technique d’acquittement positif et négatif.

Numérotation de trames.

Format des trames (HDLC)

Format des trames (HDLC)

Taille minimale d’une trame : 6 octets

Types de trames

HDLC est un protocole de transmission fiable qui opère en mode connecté :

Trames de gestion de la liaison (U)

Demande de connexion, acceptation, refus, libération de la connexion

Trames d’informations (I)

Trames de transmission effective des données.

Trames de supervision de la transmission (S)

Acquittements : positifs et négatifs

Trois types : 2 bits suffisent pour les distinguer

Types de trames : définitions

Le champs contrôle définit le type de la trame.

Le bit P/F

On dit que le bit P/F est positionné s’il a la valeur 1.

Par pure convention de notation on dit :

Un bit P/F positionné a la valeur P si la trame est une trame de commande.

Un bit P/F positionné a la valeur F si la trame est une trame de réponse.

L’émetteur d ’une commande exige une réponse immédiate.

En recevant une trame avec le bit P/F positionné, la signification de ce bit dépend du contexte local.

F si le récepteur a déjà envoyé une commande

P si aucune commande n ’est envoyée.

Trames d’informations (I)

Ns : Numérotation des trames émises: 3 bits donc numéro

module 8

Nr : Numéro de la prochaine trame d’information

attendue: Numérotation modulo 8.

Une trame acquitte toutes les trames de numéros strictement

inférieur à Nr

Trames de supervision (S)

RR (Recieved Ready) [00]: Acquittement

Prêt à recevoir, accusé de réception utilisé lorsque le récepteur n’a pas de trame d’infot à envoyé.

RNR (Recieved & Not Ready) [10] : contrôle de flux

Non prêt à recevoir, le récepteur demande à l’émetteur d’arrêter ses émissions et d’acquitté les trames acceptées N( r ) -1

REJ (Reject) [01]

Demander la retransmission a partir de la trame Nr.

Trames de gestion (U)

SABM [11100]: commande de passage en mode équilibré,

chaque station peut émettre sans autorisation.

SABME [11110]: passage en mode étendu.

UA [00110]: Trame de confirmation de connexion

DISC [11010]: Libération de la connexion

FRMR[11000]: Rejet de trames

HDLC : ÉTABLISSEMENT ET RUPTURE DE

CONNEXION (TRAME U)

Connexion

La source demande l’établissement d’une liaison par l’envoi de trames non numérotées (U) de type SABM (Set Asynchronous Balanced Mode) , P =1

La destination, si elle accepte la connexion, répond par la trame non numérotée UA (Unnumbered Acknowledgement), F = 1 identique à celui du bit P.

La liaison est établie, l’échange d’informations peut donc commencer.

Déconnexion

La source émet une demande de déconnexion DISC (DISConnect), P est positionné indifféremment à 1 ou à 0.

La destination accuse la réception avec UA, F prend la même valeur du bit P de la trame DISC

La liaison est rompue.

HDLC : ÉTABLISSEMENT ET RUPTURE DE

CONNEXION (TRAME U)

HDLC : ÉCHANGE DE DONNÉES (TRAME I)

Chaque extrémité met à jour les variables suivantes :

V(s) : indique le numéro de la trame à émettre,

V(r) : indique le numéro de la trame attendue

Après la phase de connexion les compteurs sont initialisés à zéro de chaque côté

N(S) : numéro de la trame reçus

N(R) : acquittement des trames reçues de numéro strictement inférieur à N(S)

HDLC : GESTION DES ERREURS (TRAME S)

Exemple de la reprise sur erreur

Supposons la trame 2 erronée, elle est ignorée par le récepteur.

La trame 3 est alors reçue hors séquence, elle est rejetée.

La machine B émet alors une trame de supervision de rejet (REJ : Reject) en indiquent à A à partir de quelle trame il doit reprendre la transmission [N(r) = 2].

Toutes les trames dont la valeur de Ns est supérieure à 2 sont alors rejetées (rejet simple).

La machine A reprend la transmission à partir de la trame 2 (N(s) = 2).

Si, suite à la trame erronée, A n’avait plus de données à émettre, alors B n’aurait pas détecté le déséquencement.

Dans ce cas, c’est A qui à l’échéance du temporisateur T1, aurait pris l’initiative de retransmettre la trame 2.

HDLC : GESTION DES ERREURS (TRAME S)

HDLC : GESTION DE FLUX (TRAME S)

HDLC utilise le contrôle de flux implicite.

La fenêtre est paramétrée à l’installation du logiciel ou

négociée lors de la connexion par le protocole de niveau

supérieur.

En cas de saturation des tampons de réception, le récepteur,

(la machine B) rejette la trame en excès et informe A de son

incapacité temporaire à accepter de nouvelles données.

Il émet la trame S indique RNR (Receive Not Ready) avec le

compteur Nr positionné au numéro de la trame reçue et

rejetée.

HDLC : GESTION DE FLUX (TRAME S)

Calcul du temps de transmission

Temps de propagation Tp: Temps nécessaire à un signal pour parcourir un support d'un point à un autre

Temps de transmission Tt: Délai qui s'écoule entre le début et la fin de la transmission d'un message sur une ligne

performances

Soit:

C: Débit de la transmission D: distance de propagation

L: Longueur de la trame a émettre L' : Longueur de I 'acquittement

V : Vitesse du support

Te: temps d‘émission de la trame = L/C

Tp: temps de propagation aller de la trame = D/V

T'e : temps d‘émission de I 'acquittement = L' /C

T'p: Temps de propagation retour de I'ACK = Tp = D / V

Texec : Temps de traitement des données = négligeable

T: temps de transmission total = Te + 2Tp + T'e = ((L+L')/C) + 2D/V

Exercices

Exercice 1 : Calcul du VRC et du LRC

1. Calculez le VRC et le LRC du message HELLO en utilisant la

parité paire, sachant que H est codé par 0001001, E par 1010001,

L par 0011001 et O par 1111001.

2. Déterminer le message construit à transmettre.

Exercice 2 : Protocole HDLC

1. On considère un échange de données bidirectionnel simultané entre deux stations A et B, géré par le protocole LAP-B (sous-ensemble de HDLC utilisant le rejet simple des erreurs). La liaison est déjà initialisée et aucun temporisateur n’est armé. La station A a 5 trames d’information à transmettre à la station B. Celle-ci en a 10 à émettre vers A. On suppose que toutes les trames sont de même longueur. Les deux stations commencent leur transmission à des instants très voisins l’un de l’autre. Donnez le schéma des échanges en indiquant le numéro des trames émises et reçues avec la nomenclature classique : I, N(S), N(R) pour une trame I portant le numéro N(S) et acquittant les trames jusqu’au numéro N(R)– 1. On suppose de même :

• Qu’il n’y a aucune erreur de transmission sur les trames de A.

• Qu’il y a une erreur de transmission sur les sixième et septième trames de B.

• Que les trames sont correctement retransmises.