Architecture et protocole des réseaux

Couche liaison de données

Inès MOUAKHER-ABDELMOULA

2ème LFIG

PLAN

 Introduction  Délimitation de trames  Détection/Correction d’erreurs  Contrôle de flux

Introduction

 La couche liaison de données établie,

maintient, et relâche la liaison physique entre deux nœuds adjacents dans un réseau.

 La couche liaison est en charge des

communications entre des machines situées dans le même sous-réseau. Elle transporte donc les messages sur un lien entre 2 nœuds.

 La couche liaison elle se charge du transport sur le support physique, mais pas de l'envoi des bits, qui se fait à la couche physique.

Introduction

 La trame est l’unité de base que gère le protocole de

liaison de données.

 La couche liaison récupère des paquets de la couche réseau. Pour chaque paquet, elle construit une (ou plusieurs) trame(s). La couche liaison envoie chaque trame à la couche physique.

 Généralement au sein de chaque système (ETTD), les

fonctions de la couche Liaison de données sont réalisées par une carte spécifique appelée contrôleur de communication.  Par exemple : carte HDLC, carte Ethernet, etc.

Introduction

Protocole de liaison de données

 Définir un protocole de liaison de données consiste donc à préciser principalement:  le format des trames,

 le critère de début et de fin de trames,

 la place et la signification des différents champs

dans une trame,

 la technique de détection d’erreur utilisée,

 les règles de dialogue : les procédures après

détection d’erreur ou de panne et la supervision de la liaison.

Quelques protocoles de couche 2

Trame

 C'est l'unité de données du protocole de niveau

Liaison de données (L-PDU)

 Suivant le type de protocoles, elle peut être:

 de taille fixe, ex: trame d'HDLC

 de taille variable (jusqu'à une certaine taille maximum), ex : cellule d'ATM (53 octets)

Trame

 Composée d'un certain nombre de champs

ayant chacun une signification précise

 On distingue souvent 3 ensembles de champs : l'entête ("header"), le champ de données, la terminaison ("trailer")

Adressage physique

 Les réseaux Ethernet, Token Ring et FDDI

utilisent le même type d’adressage : l’adressage MAC.

 Chaque machine d'un réseau dispose d'un numéro unique, généralement une adresse MAC (sur 48 bits) qui la désigne sans ambigüité.

 Ce sont des adresses physiquement

enregistrées dans une mémoire de la carte réseau lors de sa construction

Adressage physique

 Les trames émises sur un réseau contiennent à la fois l'adresse du destinataire et celle de la machine ayant émis la trame.

 Pour connaitre l'adresse MAC d’un PC sous

Windows, taper « ipconfig /all » ou «getmac » dans l’invité de commande MS- DOS

Temps d'acheminement

 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

 Temps d'acheminement : Ta = Tp + Tt

DÉLIMITATION LIMITATION DES TRAMES

Délimitation limitation des trames

 Il existe trois méthodes :  Compter les caractères

 Utiliser des champs délimiteurs de trame  Ils se situent en début et en fin de trame

 Des bits (ou caractères) de transparence sont

nécessaires

 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

Exemple

Utiliser 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 pas accidentellement au fanion.

Utiliser des délimiteurs - 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 Hiigh-Levell Data Liink Controll

 PPP Poiint to Poiint Protocoll

Utiliser des délimiteurs

 Avantage

 permet toujours de retrouver la synchronisation

 permet l'envoi de trames de tailles quelconques

 technique la plus simple

Violer le codage

 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

Taux d’erreur sur un canal

 10-9 pour les réseaux locaux  10-5 pour le Réseau Téléphonique Commuté  taux élevé pour le téléphone sans fil

émis bits de nombreerronés bits de nombreerreurd'taux 

Détection d’erreur

 Le mécanisme mis en œuvre par le système

destinataire pour vérifier la validité des données reçu:  La détection par écho

 La détection par répétition

 La détection d’erreur par clé calculé : une

information supplémentaire (clé) déduite des informations transmises est ajoutée à celles-ci

 La détection et correction d’erreur par code

Détection d’erreur par clé calculée

 Exploiter la redondance d’informations ⇒ ajouter des bits de contrôle aux bits de

données

 Code de contrôle de parité

 VRC (Vertical Redundancy Check)

 LRC (Longitudinal Redundancy Check)

 Code cyclique

 CRC (Cyclic Redundancy Check)

Méthode VRC (Vertical Redundancy Check)

 C'est la méthode de la parité verticale.  Principe : un seul bit (dit de parité) est ajouté

aux bits de données

 parité paire : le nombre de bits à 1 du mot

formé doit être pair

 parité impaire : le nombre de bits à 1 du mot

formé doit être impair

Méthode VRC (Vertical Redundancy Check)

 La détection d'erreur avec le VRC consiste à : recalculer le bit de parité à la réception et vérifier que le nombre total de 1 correspond à la parité choisie.

 parité paire lorsque le nombre de 1 est paire  parité impaire lorsque le nombre de 1 est

impaire.

 La méthode VRC n'est pas très fiable (si deux

bits sont erronés, la détection échoue).  Son taux d’efficacité est estime a 50 %

Méthode VRC (Vertical Redundancy Check)

Exemple :  Transmission de caractères utilisant un code de représentation (le code ASCII sur 7 bits).

Parité longitudinale LRC (Longitudinal Redundancy Check)

 Elle permet de tester l'ensemble d'un bloc de

données.

 Le résultat obtenu est appelé BCC (Block

Check Character) ou clé de fin de message, il est transmis comme dernier caractère du message à émettre.

Parité longitudinale LRC (Longitudinal Redundancy Check)

 Exemple : LRC avec parité paire (sur 7 bits)  Caractère A (code 41 en ASCII) 1 0 0 0 0 0 1

 Caractère C (code 43 en ASCII) 1 0 0 0 0 1 1

 LRC 0 0 0 0 0 1 0

Parité longitudinale et transversale

 Le bloc de données est disposé sous une forme matricielle (k=a.b). On applique la parité (uniquement paire) sur chaque ligne et chaque colonne.

 On obtient une matrice (a+1, b+1).  Le récepteur fait la même opération et

compare les deux clés.

 Cette méthode atteint un taux d'efficacité de

98%.

Code polynomial CRC (Cyclic Redundancy Check)

 On considère que les bits d’une séquence binaire sont les coefficients

d ’un polynôme



Exemple : p = 110001  p(x) = x5 + x4 + x0 et degré de p = 5

 Principe : l’émetteur et le récepteur se mettent d’accord sur le choix

d’un polynôme dit générateur G(x) (ex: x4+x+1)

 Soit P(x) les données à envoyer et k le degré de G(x). L’émetteur



calculer (P(x)*xk) / G(x) le reste de cette division R(x) est le CRC

 Le message à Transmettre est P(x)+R(x)

 Le récepteur calcule P(x)+R(x) / G(x) si le reste de la division est égal

à zéro il estime que le message est correct

 Les calculs nécessaires semblent complexes mais en pratique on utilise

des circuits électroniques

Exemple CRC

 Exemple : CRC sur 4 bits

 P(x) = 1101011011

 P(x)* x4 = 11010110110000

 G(x) = x4 + x + 1

 CRC = 1110

 Message transmis :  1101011011 1110

Les codes autocorrecteur

 Dans les systèmes autocorrecteurs, on

substitue au mot à transmettre (mot naturel) un nouveau mot tel que deux mots successif diffèrent de  bits où  est appelé distance de Hamming  Détecter les erreurs pourtant ( -1) bit

 Corriger toute erreur portant sur ( -1)/2 bit

Les codes autocorrecteur

Nous considérons la table de codage de Hamming suivante

Mots naturels

Mots codes

00 01 10 11

10011 10100 01001 01110

Dans ce code il y a au moins 3 bit qui diffèrent d’un mot code à un autre donc ce code permet de :

•détecter des erreurs portant sur 2 ( -1) bits •corriger les erreurs sur 1 (( -1)/2) bits

Les codes autocorrecteur

Emetteur :Soit le mot 00, on transmet 10011 Récepteur : reçoit 11011 ne correspond à aucun des mots du code On retient le mot dont la distance de hamming est de 1 avec le mot reçu

10011

 =1

 =2

01001

11011

10100

 =4

 =3

01110

CONTRÔLE DE FLUX

Contrôle de flux

 Utilisation d'acquittements  Gestion de temporisateurs  Numérotation des trames  Limitation du nombre de trames pouvant

être envoyées par l'émetteur

Le mode Send and Wait

 Chaque trame envoyée doit être acquittée par

le récepteur.

 L’acquittement peut être positif (ACK) ou

négatif (NACK)

ACK

NACK

Reprise sur temporisation

 Problème A



ACK



 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 -), l’émetteur renvoi la même trame d’information

Reprise sur temporisation(Solution)



ACK



Numérotation des blocs de données

 Problème : En cas de perte de l’ACK, l’émetteur retransmet le même bloc alors que le récepteur l’a déjà reçu : il y a duplication d’un bloc.

ACK



solution

ACK



 Solution : Numérotation de trames

(identification)

Numérotation des ACK

 Problème : le second ACK du premier bloc est

interprété comme celui du second bloc de données

ACK



solution

ACK1



 Solution : Pour éviter cette confusion d’interprétation 42

il est aussi nécessaire de numéroter les ACK.

Problème 3

 Les protocoles qui mettent en œuvre les principes

précédents sont appelés protocoles en mode de base  Les faibles performances du mode « Stop and Wait » sont essentiellement dues au temps d’attente entre les ACK.

 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

Solution

 Piggypacking : dans des échanges

bidirectionnels, le récepteur peut acquitter une trame d’information reçue par l ’envoi d’une autre trame d’information.

 Protocole à fenêtres d’anticipation :

l’émetteur peut envoyer W trames sans avoir un acquittement.

Protocole à fenêtres d’anticipation (sliding windows )

 Une amélioration substantielle est obtenue en émettant les blocs suivants, sans attendre la réception des ACK

 Cette possibilité d’émettre sans acquittement

s’appelle l’anticipation.

 On appelle fenêtre d’anticipation le nombre maximum de blocs (trames) qui peuvent être envoyés sans acquittement (en attente de ACK)

 Plus la fenêtre est importante, plus le nombre de

tampons nécessaires à la conservation des blocs en attente d’acquittement est important

Protocole à fenêtres d’anticipation (sliding windows ).

 Deux fenêtres sont gérées par chaque entité

de couche liaison.  Toute entité émettrice possède une fenêtre d'anticipation appelée fenêtre d’émission

 Toute entité réceptrice possède une fenêtre d'anticipation appelée fenêtre de réception

Modes de gestion de la fenêtre

 Deux modes de fonctionnement :

 chaque bloc est acquitté. lors de la réception d’un

ACK, l’émetteur libère un buffer et émet le suivant: la fenêtre est dite glissante

 le bloc n’est pas nécessairement besoin d’être

acquitté individuellement. L’acquittement peut être différé et concerne plusieurs blocs: la fenêtre est dite sautante

La fenêtre d’anticipation : fenêtre glissante(sliding window)

 Fenêtre dynamique: elle évolue au fur et à mesure des émissions et des acquittements de blocs :

 L’émission de blocs sans ACK fait progresser la borne inférieure jusqu’au blocage éventuel de l’émission (fenêtre fermée).

 L’acquittement de blocs par le récepteur fait

progresser la borne supérieure: fenêtre glissante

La fenêtre d’anticipation : fenêtre glissante

La fenêtre d’anticipation : fenêtre glissante (w=3)

(a,0)

(b,1)

(a) (b) (c)

I0 I1 I2

ACK0

ACK1

ACK2

(a)

(b)

ACK0

ACK1

ACK2

(a,0) (b,1) (c,2)

Protocole à fenêtre sautante

 L’acquittement concerne plusieurs blocs (acquittement collectif ou global): un seul ACK acquitte N blocs (ainsi ACK2 signifie « j’ai bien reçu 3 blocs de données (0, 1, et 2».  N est la fenêtre d’anticipation  Fenêtre d’émission : nombre de blocs

en attente d'acquittement

I0 I1 I2

ACK2

(w=3)

Problème

 Transmettre un message de A à B, en tenant

compte  Des erreurs

 Des pertes

 Du temps de traitement (couches supérieures. . . )

 La réception d’un NACK (acquittement

négatif) ou l’échéance d’un temporisateur

La politique de reprise sur erreur

 Deux modes de fonctionnement, selon la

technique de reprise sur erreur :

 reprise depuis le bloc erroné (rejet simple)

« GO-BACK-N »

 reprise du bloc erroné seulement (rejet sélectif)

« Selective Repeat »

Le rejet simple

 La réception d’un NACK (acquittement négatif) ou

l’échéance d’un temporisateur provoque :  l’arrêt des émissions en cours,

 la reprise depuis le bloc erroné ou perdu

 l’élimination par le récepteur des blocs reçus

postérieurement.

 le séquencement est conservé, et le récepteur n’aura pas à trier les blocs pour les remettre en séquence.  L’émetteur doit posséder N tampons (pour conserver

les N blocs émis jusqu’à ce qu’ils aient été tous confirmés) et le récepteur 1 seul tampon.

Exemple de la retransmission simple avec fenêtre glissante (w=3)

I0 I1 I2

ACK0

ACK1

NACK2

Rejet(erroné)

Rejet

I2 I3

ACK2

ACK3

ACK4

Le rejet sélectif

 Seul le bloc erroné est retransmis. Cela implique la mémorisation des blocs hors séquence (non rejetés s’ils ont été confirmés).

 L’anticipation est cependant limitée par les possibilités de comptage des blocs émis.

 le récepteur devra exécuter un programme de tri

pour rétablir le séquencement initial.

Exemple de la retransmission sélective avec fenêtre glissante (w=3)

I0 I1 I2

ACK0

ACK1

NACK2

Rejet(erroné)

ACK0

ACK1

NACK2

Rejet(erroné)

ACK4

Mettre dans Buffer

Réordonnacement 2,3,4

ACK3

ACK4

ACK2

Mettre dans Buffer

Réordonnacement 2,3,4