Couche Liaison de données

10/11/2020 Couche liaison Page 1

 Plan
• Introduction
• Délimitation de trames
• Détection d’erreurs
• Contrôle de flux
• Le protocole Ethernet

10/11/2020 Couche liaison Page 2

 Introduction

10/11/2020 Couche liaison Page 3

 Couche liaison
• Cette couche doit assurer une transmission
exempte d'erreurs sur un canal de
communication.

• Les données sont fractionnées en trames.

LLC
MAC

Couche Physique

10/11/2020 Couche liaison Page 4

 Description
• 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.

10/11/2020 Couche liaison Page 5

 Description

couche réseau couche réseau

paquet paquet

couche liaison couche liaison

trame trame

bits
couche physique couche physique

Emetteur Récepteur

10/11/2020 Couche liaison Page 6

 Services offerts
• Gestion (délimitation) de trames
• Contrôle d’erreurs
• Contrôle de flux
• Contrôle d'accès à un canal partagé (MAC)

10/11/2020 Couche liaison Page 7

 Délimitation de trames

10/11/2020 Couche liaison Page 8

 Dé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

10/11/2020 Couche liaison Page 9

 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

10/11/2020 Couche liaison Page 10

 Exemple
Trames émises

06 ‘S’ ‘U’ ‘P’ ‘E’ ‘R’ 03 ‘L’ ‘E’ 06 ‘C’ ‘O’ ‘U’ ‘R’ ‘S’

Trames reçues

06 ‘S’ ‘U’ ‘P’ ‘E’ ‘R’ 04 ‘L’ ‘E’ 06 43 ‘O’ ‘U’ ‘R’ ‘S’

code ASCII de ‘C’

10/11/2020 Couche liaison Page 11

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

10/11/2020 Couche liaison Page 12

 Exemple
• Fanion (ou Préambule) : 01111110

• Bit de transparence : 0 inséré après toute

séquence de cinq 1 successifs dans la trame.
• Technique utilisée dans :
– HDLC
– PPP

10/11/2020 Couche liaison Page 13

 Exemple

Données :
01011001111110

Trame :
01111110 010110011111010 01111110

10/11/2020 Couche liaison Page 14

 Utiliser des fanions
• Avantages
– permet toujours de retrouver la synchronisation
– permet l'envoi de trames de tailles quelconques
– technique la plus simple
• Cette technique est utilisée également en
considérant des caractères de délimitation et
des caractères de transparence.

10/11/2020 Couche liaison Page 15

 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
10/11/2020 Couche liaison Page 16
 Détection d’erreurs

10/11/2020 Couche liaison Page 17

 Transmission d’information

canal
bruit

émetteur récepteur

10/11/2020 Couche liaison Page 18

 Causes d’erreurs sur un canal
• rayonnement électromagnétique
– relais
– émetteurs
• câblage mal isolé
• effet de distorsion

10/11/2020 Couche liaison Page 19

 Taux d’erreur sur un canal
nombre de bits erronés
taux d' erreur 
nombre de bits émis

• 10-9 pour les réseaux locaux

• 10-5 pour le RTC
• taux élevé pour le téléphone sans fil

10/11/2020 Couche liaison Page 20

 Types d’erreurs de transmission
• Erreurs isolées • Erreurs en rafales
– simples à détecter – difficiles à détecter
– simples à corriger – difficiles à corriger
– proportion élevée de – proportion faible de
blocs affectés blocs affectés

10/11/2020 Couche liaison Page 21

 Mot de code
d bits de données
+
c bits de contrôle
=
n bits d’information (à transmettre)

Un tel mot de n bits est appelé un mot de code

10/11/2020 Couche liaison Page 22

 Distance de Hamming de 2 mots

Il s’agit du nombre de bits qui diffèrent entre

deux mots de code x et y.

1000 1001
1011 0001
= 0011 1000

Dist(x,y) = 3
10/11/2020 Couche liaison Page 23
 Distance de Hamming d’un code
Soit C un code (détecteur et/ou correcteur)

Dist(C) = min { Dist(x,y)  xC  y C }

Il s’agit de la distance minimale entre 2 mots

du code

10/11/2020 Couche liaison Page 24

 Capacité d’un code
• Pour qu’un code soit capable de détecter d
erreurs, sa distance de Hamming doit être
égal à d+1.

• Pour qu’un code soit capable de corriger d

erreurs, sa distance de Hamming doit être
égal à 2*d+1.

10/11/2020 Couche liaison Page 25

 Exercice
Soit le code C = { 0000 0000, 0000 1111,
1111 0000, 1111 1111 }
– quel est sa distance ?
– si un récepteur reçoit 0000 0111, que peut-il en
conclure ?
– est-il certain de pouvoir reconnaître le mot
original ?

10/11/2020 Couche liaison Page 26

 Différents codes
• Code de contrôle de parité

• Codes polynomiaux

• …

10/11/2020 Couche liaison Page 27

 Code de contrôle de parité
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.

10/11/2020 Couche liaison Page 28

 Exemple
• parité paire
100 0001 : bits de données
+0 : bit de contrôle
= 0100 0001 : mot de code

• parité impaire
101 1001 : bits de données
+1 : bit de contrôle
= 1101 1001 : mot de code

10/11/2020 Couche liaison Page 29

 Code de contrôle de parité
Distance de Hamming = 2

– peut détecter une erreur simple

– ne peut détecter un nombre pair d’erreurs
– peut détecter un nombre impair d’erreurs
– ne peut corriger une erreur simple

Code détecteur
10/11/2020 Couche liaison Page 30
 Code polynomial
• 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
degré de p = 5

10/11/2020 Couche liaison Page 31

 Arithmétique utilisée
Arithmétique modulo 2 (i.e. sans retenue)
• addition et soustraction = ou exclusif
• division
11 0101 1011 0000 / 1 0011
quotient = 11 0000 1010
reste = 1110

10/11/2020 Couche liaison Page 32

 Division
Deux méthodes pour l’effectuer à la main :

• division binaire

• division polynomiale

10/11/2020 Couche liaison Page 33

 Code polynomial
Principe : l’émetteur et le récepteur se mettent
d’accord sur le choix d’un polynôme dit
générateur G(x).

Le codage consiste à ajouter des bits de

contrôle appelés :
le total (ou somme) de contrôle (checksum)
CRC

10/11/2020 Couche liaison Page 34

 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)

10/11/2020 Couche liaison Page 35

 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

10/11/2020 Couche liaison Page 36

 Propriété
T(x) est toujours divisible par G(x)
Le dividende moins le reste est toujours
divisible par le diviseur.

Illustration en base 10 :
210 278 / 10 941 donne un reste égal à 2399
210 278 - 2399 est divisible par 10 941

10/11/2020 Couche liaison Page 37

 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

10/11/2020 Couche liaison Page 38

 Contrôle de flux

10/11/2020 Couche liaison Page 39

 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

10/11/2020 Couche liaison Page 40

 Protocole « send and wait »
• Principe
– Utiliser une méthode de détection d’erreurs
– Le récepteur émet une trame d'acquittement si la trame
arrivée est correcte.
– L'émetteur ré-émet une trame si aucun ack reçu et si un
certain délai de temporisation a expiré

10/11/2020 Couche liaison Page 41

 Problème
paquet 1
couche couche
réseau réseau

trame 1

 bruit
ack paquet 1

trame 1

ack paquet 1

10/11/2020
Émetteur Couche liaison
Récepteur Page 42
 Solution
• En considérant le problème précédent :
– il s’avère nécessaire de numéroter les trames
pour distinguer deux trame successives.

• De plus :
– il est préférable que la trame d'acquittement
contienne le numéro de la trame qui est
acquittée.

10/11/2020 Couche liaison Page 43

 Protocole à fenêtre d’anticipation
• Protocole à fenêtres d’anticipation (sliding
windows).
• Deux fenêtres sont gérées par chaque entité
de couche liaison. En effet :
– 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

10/11/2020 Couche liaison Page 44

 Fenêtre d’émission
• La fenêtre d’émission indique la liste des numéros
de trames dont on attend l’acquittement.
• Elle possède une taille maximale maxE indiquant
le nombre maximal de trames qui peuvent être
envoyées sans se préoccuper des acquittements.
• Elle possède une taille courante variable curE de
valeur inférieure ou égale à maxE. On a toujours :

0  curE  maxE

10/11/2020 Couche liaison Page 45

 Bornes
• La fenêtre est représentée par deux
frontières (bornes).
– la frontière droite (borne supérieure) est
incrémentée de 1 à chaque envoi
– la frontière gauche (borne inférieure) est
incrémentée de 1 à chaque acquittement reçu
correspondant à la trame associée à cette
frontière

10/11/2020 Couche liaison Page 46

 Mémoires tampons
• Coté émetteur, maxE mémoires tampons
sont nécessaires pour stocker les trames.
• En effet, il est possible qu’il faille envoyer à
nouveau une ou plusieurs trames.

10/11/2020 Couche liaison Page 47

 Exemple
• Considérons que :
– les trames soient numérotés de 0 à 7 (sur 3 bits)
– maxE = 3
– curE = 0 (initialement)

10/11/2020 Couche liaison Page 48

 Exemple

7 0 7 0 7 0
6 1 6 1 6 1
5 2 5 2 5 2
4 3 4 3 4 3
e1) e2) e3)

7 0 7 0 7 0
6 1 6 1 6 1
5 2 5 2 5 2
4 3 4 3 4 3
e4) e5) e6)

10/11/2020 Couche liaison Page 49

 Fenêtre de réception
• La fenêtre de réception indique la liste des
numéros de trame attendus.

• La fenêtre de réception possède une taille R

qui ne varie pas (sauf cas particuliers).

10/11/2020 Couche liaison Page 50

 Bornes
• La fenêtre est représentée par deux
frontières (bornes).
• les deux frontières sont toutes deux
incrémentées de 1 chaque fois qu’une trame
correcte correspondant à la frontière droite
(borne inférieure) est reçue.

10/11/2020 Couche liaison Page 51

 Exemple

7 0 7 0 7 0
6 1 6 1 6 1
5 2 5 2 5 2
4 3 4 3 4 3
r1) r2) r3)

7 0
6 1
5 2
4 3
r4)

10/11/2020 Couche liaison Page 52

 Pipelinage
• Utiliser des fenêtre d’anticipation permet
d’utiliser la technique de pipelinage.
• Cela consiste à envoyer plusieurs trames
successivement sans attendre de recevoir les
trames d'acquittement.
• Il est important de bien régler la largeur des
fenêtres pour améliorer l'efficacité du
pipelinage.

10/11/2020 Couche liaison Page 53

 Calcul de l’efficacité
• Temps d’émission Te(t) = temps nécessaire pour
que la trame t passe sur le canal.
Te(t) = length(t)/d où :
d = débit du canal (en bits/s)
length(t) = longueur de la trame t (en bits)
• Temps de propagation Tp = temps nécessaire pour
qu’un bit passe de l’émetteur au récepteur.
• Temps de traitement Tt = temps nécessaire au
récepteur pour traiter une trame.
10/11/2020 Couche liaison Page 54
 Calcul de l’efficacité
• Hypothèse : toutes les trames sont de longueur m.
• Temps d’attente Ta = temps nécessaire pour
recevoir l’acquittement d’une trame émise.
Ta = Te(t) + Tp + Tt + Te(ack) + Tp où :
– t désigne une trame quelconque
– ack désigne une trame quelconque d’acquittement.
• Temps d’émission maximale Tem = temps
maximal pendant lequel il est possible d’émettre
des trames. Tem = maxE*m/d
10/11/2020 Couche liaison Page 55
 Efficacité
• Efficacité :
100% si Tem >= Ta
Tem/Ta sinon
• NB : calcul théorique ne prenant en compte
– ni les erreurs de transmission
– ni les problèmes de surcharge du récepteur

10/11/2020 Couche liaison Page 56

 Exercice
• Soient d= 50kbits/s, m = 1000 bits, Tp =
250ms, Tt et ack considérés comme
négligeables (nuls)
• Calculer l’efficacité pour maxE = 1
• Calculer l’efficacité pour maxE = 25

10/11/2020 Couche liaison Page 57

 Le protocole Ethernet

10/11/2020 Couche liaison Page 58

 Ethernet : les raisons du succès
• Toutes les stations sont égales vis-à-vis du réseau : il n'y a
pas de notion de maître/esclave
•La méthode d'accès employée est distribuée entre tous les
équipements connectés
• On peut relier ou retirer une machine du réseau sans
perturber le fonctionnement de l'ensemble
• Une évolution constante
. Ethernet et IEEE 802.3 : la définition d'origine à
10Mbps
• Fast Ethernet l'extension à 100Mbps
• Gigabit Ethernet l'extension à 1000Mbps ou 1Gbps
• Et aujourd'hui le 10 GBE l'extension à 10Gbps
 Trame de données Ethernet

10/11/2020 Couche liaison Page 60

 Le préambule
• Il ne fait pas partie de la trame
• Permet à l'horloge du récepteur de se synchroniser sur
l'émetteur
• Possible de perdre une partie du préambule lors de la
transmission
• 2 derniers bits du préambule à 1 pour la trame ethernet (eq
au SOF)
• Préambule : 7 octets
– 10101010 = AAh
– Donnée régulière
 synchronisation des horloges
• Start Frame Delimitor : 1 octet
– 10101011 = ABh
– Fin du préambule, début des données
 Les adresses MAC
• Taille de 6 octets
• Les 3 premiers font référence au
constructeur et sont attribués par l'IEEE
• @source est unicast
• @destination est unicast, multicast,
broadcast([Link])
 Le champ longueur/type
• Taille de 2 octets
• Type de protocole de niveau 3 pour
Ethernet
Valeur du champ protocole Protocole
0x0800 IP
0x0806 ARP
0x86DD IPv6
0x8863 Découverte PPP
0x8864 Session PPP
 Les données
• Informations transmises strictement
• De 46 à 1500 octets
• Padding éventuel à 64 octets
• La norme IP impose :
– Maximum Transfer Unit octets par paquets.
– Le MTU dépend du réseau
• Internet ≥ 576 octets
• Ethernet = 1500 octets
 Le FCS
• Frame check sequence (4 octets)
• Valide l'intégrité de la trame à 1 bit près
• CRC qui englobe tous les champs de la
trame (du préambule exclu au FCS exclu)
• Si erreur simple, correction automatique
 Exercice
• Analyser la trame Ethernet suivant:
AA AA AA AA AA AA AA AB ff ff ff ff ff
ff 09 ab 14 d8 05 48 08 06 00 01 08 00 06
04 00 01 09 ab 14 d8 05 48 7d 05 30 0a 00
00 00 00 00 00 7d 12 6e 03 00 00 00 00 00
00 00 0000 00 00 00 00 00 00 00 00 00 XX
XX XX XX
Ou XXXXXX est le champ FCS

10/11/2020 Couche liaison Page 66

 Trames erronées
• Runt = trame trop courte (<64 octets)
• Jabber = trame trop longue (>1518 octets)
• Misaligned Frame= nb de bits non
divisibles par 8
• Bad FCS= mauvais CRC
• Les collisions (réseau sain<1%)
 Acquisition du canal
• Le problème :
– Chaque machine peut utiliser le canal
– Pas d’arbitre donnant la parole
– Comment ne pas parler simultanément ?
• La solution Ethernet/802.3
– CSMA : Carrier Sensing Multiple Access
– « Conversation civilisée »
– On n’interrompt pas une communication
– On écoute, on attend la fin, et on enchaîne
68
 Collision, vous avez dit collision ?
DTE1 DTE2

 Collision !
 DTE2 voit la collision
 DTE1 ne voit rien !

69
 Collision inaperçue
• Dans l’exemple:
– DTE2 voit la collision
– DTE1 ne voit rien
– DTE2 ré-émet sa trame, puisque collision
– DTE1 en reçoit une deuxième copie !!!
•  Eviter les collisions discrètes
– Eviter les trames trop courtes
– Limiter la longueur du réseau
70
 Collision
Les techniques d’accès au
medium ont pour but d’interdire
deux stations d’utiliser le
medium au même temps.
Collision

Le time-slot est le temps mis

pour qu’un message
envoyé d’une des extrémités de
la ligne face un aller et retour.

Le Ts doit être:

Avec Mmin est le nombre min

des bits par trame
 La solution Ethernet
• La norme impose :
– Round-Trip-Delay < 50 ms.
• A 10 Mbit/s, 50 ms  62,5 octets
• >64 octets  Détection de collision garantie

• 1 trame contient au moins 72 octets

• 26 octets de protocole
• 46 octets de données minimum
• Si moins de 46 octets à envoyer :
– Padding (ajout d’octets de bourrage)
– Ex : requête ARP = 28 octets + 18 padding

72
 La méthode d’accès CSMA/CD
• La méthode d'accès CSMA/CD :Carrier Sense Multiple Access
with Collision Detect;
• Chaque station est libre de communiquer à n'importe quel
moment.
• Chaque station envoyant un message vérifie qu'aucun autre
message n'a été envoyé en même temps par un autre maitre (pas
de collision).
• Si c'est le cas, les deux maitres patientent pendant un temps
aléatoire avant de recommencer à émettre.
• Principe:
– Emission
– Si collision
• Arrêt d’émission
• Attente aléatoire
• Ré-émission