Embed Size (px)
Citation preview
Chapitre 3: Fiabilisation de transmission
(Couche liaison)
ABBACI KAHYA N
Université Badji Mokhtar Annaba
Département d'informatique
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.
