Architecture et protocole des r seaux
Couche liaison de donn es
In s MOUAKHER-ABDELMOULA
2 me LFIG
PLAN
w Introduction
w D limitation de trames
w D tection/Correction derreurs
w Contr le de flux
2
Introduction
w La couche liaison de donn es tablie,
maintient, et rel che la liaison physique entre
deux nSuds adjacents dans un r seau.
w 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 nSuds.
w 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.
3
Introduction
w La trame est lunit de base que g re le protocole de
liaison de donn es.
w 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.
w 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.
n Par exemple : carte HDLC, carte Ethernet, etc.
4
Introduction
5
Protocole de liaison de donn es
w D finir un protocole de liaison de donn es
consiste donc pr ciser principalement:
n le format des trames,
n le crit re de d but et de fin de trames,
n la place et la signification des diff rents champs
dans une trame,
n la technique de d tection derreur utilis e,
n les r gles de dialogue : les proc dures apr s
d tection derreur ou de panne et la supervision
de la liaison.
6
Quelques protocoles de couche 2
7
Trame
w C'est l'unit de donn es du protocole de niveau
Liaison de donn es (L-PDU)
w Suivant le type de protocoles, elle peut tre:
n de taille fixe, ex: trame d'HDLC
n de taille variable (jusqu' une certaine taille
maximum), ex : cellule d'ATM (53 octets)
8
Trame
w Compos e d'un certain nombre de champs
ayant chacun une signification pr cise
w On distingue souvent 3 ensembles de champs :
l'ent te ("header"), le champ de donn es, la
terminaison ("trailer")
9
Adressage physique
w Les r seaux Ethernet, Token Ring et FDDI
utilisent le m me type dadressage :
ladressage MAC.
w 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 .
w Ce sont des adresses physiquement
enregistr es dans une m moire de la carte
r seau lors de sa construction
10
Adressage physique
w Les trames mises sur un r seau contiennent
la fois l'adresse du destinataire et celle de
la machine ayant mis la trame.
w Pour connaitre l'adresse MAC dun PC sous
Windows, taper ipconfig /all ou
getmac dans linvit de commande MS-
DOS
11
Temps d'acheminement
w Temps de propagation Tp : Temps n cessaire un
signal pour parcourir un support d'un point un autre
w 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
w Temps d'acheminement : Ta = Tp + Tt
12
D LIMITATION LIMITATION
DES TRAMES
13
D limitation limitation des trames
w Il existe trois m thodes :
n Compter les caract res
n Utiliser des champs d limiteurs de trame
w Ils se situent en d but et en fin de trame
w Des bits (ou caract res) de transparence sont
n cessaires
n Violer le codage normalement utilis dans la
couche physique
14
Compter les caract res
w On utilise un champ dans l'en-t te de la
trame pour indiquer le nombre de caract res
de la trame
w Probl me : si la valeur du champ est
modifi e au cours de la transmission
w M thode rarement utilis e seule
15
Exemple
16
Utiliser des d limiteurs
w Un fanion (d limiteur) est plac :
n au d but de chaque trame
n la fin de chaque trame (en fait, au d but de la
suivante)
w Un fanion (flag) = s quence particuli re de
bits
w Des bits de transparence sont alors
n cessaires pour quune s quence binaire
Advertisement
dans la trame ne corresponde pas
accidentellement au fanion.
17
Utiliser des d limiteurs - Exemple
w Fanion : 01111110
w Bit de transparence : 0 ins r apr s toute
s quence de cinq 1 successifs dans la trame.
w Technique utilis e dans :
n HDLC Hiigh-Levell Data Liink Controll
n PPP Poiint to Poiint Protocoll
18
Utiliser des d limiteurs
w Avantage
n permet toujours de retrouver la synchronisation
n permet l'envoi de trames de tailles quelconques
n technique la plus simple
19
Violer le codage
w Par exemple :
n 0 = impulsion positive puis n gative
n 1 = impulsion n gative puis positive
n On peut donc utiliser les combinaisons positive-
positive et n gative-n gative pour d limiter les
trames
w Utilis e dans la norme 802
20
D TECTION/CORRECTION
DERREURS
21
Taux derreur sur un canal
w 10-9 pour les r seaux locaux
w 10-5 pour le R seau T l phonique Commut
w taux lev pour le t l phone sans fil
22
mis bits de nombreerron s bits de nombreerreurd'taux =
D tection derreur
w Le m canisme mis en Suvre par le syst me
destinataire pour v rifier la validit des
donn es re u:
n La d tection par cho
n La d tection par r p tition
n La d tection derreur par cl calcul : une
information suppl mentaire (cl ) d duite des
informations transmises est ajout e celles-ci
n La d tection et correction derreur par code
23
D tection derreur par cl calcul e
w Exploiter la redondance dinformations
ajouter des bits de contr le aux bits de
donn es
w Code de contr le de parit
n VRC (Vertical Redundancy Check)
n LRC (Longitudinal Redundancy Check)
w Code cyclique
n CRC (Cyclic Redundancy Check)
24
M thode VRC (Vertical Redundancy
Check)
w C'est la m thode de la parit verticale.
w Principe : un seul bit (dit de parit ) est ajout
aux bits de donn es
w parit paire : le nombre de bits 1 du mot
form doit tre pair
w parit impaire : le nombre de bits 1 du mot
form doit tre impair
25
M thode VRC (Vertical Redundancy
Check)
w 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.
w parit paire lorsque le nombre de 1 est paire
w parit impaire lorsque le nombre de 1 est
impaire.
w La m thode VRC n'est pas tr s fiable (si deux
bits sont erron s, la d tection choue).
w Son taux defficacit est estime a 50 %
26
M thode VRC (Vertical Redundancy
Check)
Exemple :
w Transmission de caract res utilisant un code
de repr sentation (le code ASCII sur 7 bits).
27
Parit longitudinale LRC (Longitudinal
Redundancy Check)
w Elle permet de tester l'ensemble d'un bloc de
donn es.
w 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.
28
Parit longitudinale LRC (Longitudinal
Redundancy Check)
w Exemple : LRC avec parit paire (sur 7 bits)
n Caract re A (code 41 en ASCII) 1 0 0 0 0 0 1
n Caract re C (code 43 en ASCII) 1 0 0 0 0 1 1
n LRC 0 0 0 0 0 1 0
29
Parit longitudinale et transversale
w 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.
w On obtient une matrice (a+1, b+1).
w Le r cepteur fait la m me op ration et
compare les deux cl s.
w Cette m thode atteint un taux d'efficacit de
98%.
30
Code polynomial
CRC (Cyclic Redundancy Check)
w On consid re que les bits dune s quence binaire sont les coefficients
d un polyn me
n
Exemple : p = 110001 p(x) = x5 + x4 + x0 et degr de p = 5
w Principe : l metteur et le r cepteur se mettent daccord sur le choix
dun polyn me dit g n rateur G(x) (ex: x4+x+1)
w Soit P(x) les donn es envoyer et k le degr de G(x). L metteur
n
calculer (P(x)*xk) / G(x) le reste de cette division R(x) est le CRC
n Le message Transmettre est P(x)+R(x)
w 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
w Les calculs n cessaires semblent complexes mais en pratique on utilise
Advertisement
des circuits lectroniques
31
Exemple CRC
w Exemple : CRC sur 4 bits
n P(x) = 1101011011
n P(x)* x4 = 11010110110000
n G(x) = x4 + x + 1
n CRC = 1110
w Message transmis :
n 1101011011 1110
32
Les codes autocorrecteur
w Dans les syst mes autocorrecteurs, on
substitue au mot transmettre (mot naturel)
un nouveau mot tel que deux mots successif
diff rent de a bits o a est appel distance
de Hamming
n D tecter les erreurs pourtant (a -1) bit
n Corriger toute erreur portant sur (a -1)/2 bit
33
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 dun mot code
un autre donc ce code permet de :
"d tecter des erreurs portant sur 2 (a -1) bits
"corriger les erreurs sur 1 ((a -1)/2) bits
34
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
a =1
a =2
01001
11011
10100
a =4
a =3
01110
35
CONTR LE DE FLUX
36
Contr le de flux
w Utilisation d'acquittements
w Gestion de temporisateurs
w Num rotation des trames
w Limitation du nombre de trames pouvant
tre envoy es par l' metteur
37
Le mode Send and Wait
w Chaque trame envoy e doit tre acquitt e par
le r cepteur.
w Lacquittement peut tre positif (ACK) ou
n gatif (NACK)
A
B
A
B
I1
ACK
I2
I1
NACK
I1
38
Reprise sur temporisation
w Probl me
A
I
?
B
A
B
I
ACK
?
w Solution: Armer un temporisateur T1 apr s
lenvoi dune trame dinformation.
w Si T1 expire avant la r ception dun
acquittement (+ ou -), l metteur renvoi la
m me trame dinformation
39
Reprise sur temporisation(Solution)
A
I
T1
I
B
A
B
T1
I
ACK
I
40
Num rotation des blocs de donn es
w Probl me : En cas de perte de lACK,
l metteur retransmet le m me bloc alors que
le r cepteur la d j re u : il y a duplication
dun bloc.
A
B
A
B
T1
I
ACK
I
solution
T1
Advertisement
I1
ACK
I1
w Solution : Num rotation de trames
(identification)
41
Num rotation des ACK
w Probl me : le second ACK du premier bloc est
interpr t comme celui du second bloc de donn es
A
B
A
B
T1
I1
I1
ACK
I2
ACK
I3
T1
solution
I1
I1
ACK1
T1
ACK1
I2
I2
w Solution : Pour viter cette confusion dinterpr tation
42
il est aussi n cessaire de num roter les ACK.
Probl me 3
w Les protocoles qui mettent en Suvre les principes
pr c dents sont appel s protocoles en mode de base
w Les faibles performances du mode Stop and Wait
sont essentiellement dues au temps dattente entre
les ACK.
w Si chaque trame doit tre acquitt e par une trame
sp cifique et dune mani re individuelle lefficacit de
la liaison sera tr s faible.
w La plupart de temps les extr mit s de la liaison
seront en tat dattente dacquittement
43
Solution
w Piggypacking : dans des changes
bidirectionnels, le r cepteur peut acquitter
une trame dinformation re ue par l envoi
dune autre trame dinformation.
w Protocole fen tres danticipation :
l metteur peut envoyer W trames sans avoir
un acquittement.
44
Protocole fen tres danticipation
(sliding windows )
w Une am lioration substantielle est obtenue en
mettant les blocs suivants, sans attendre la
r ception des ACK
w Cette possibilit d mettre sans acquittement
sappelle lanticipation.
w On appelle fen tre danticipation le nombre maximum
de blocs (trames) qui peuvent tre envoy s sans
acquittement (en attente de ACK)
w Plus la fen tre est importante, plus le nombre de
tampons n cessaires la conservation des blocs en
attente dacquittement est important
45
Protocole fen tres danticipation
(sliding windows ).
w Deux fen tres sont g r es par chaque entit
de couche liaison.
n Toute entit mettrice poss de une fen tre
d'anticipation appel e fen tre d mission
n Toute entit r ceptrice poss de une fen tre
d'anticipation appel e fen tre de r ception
46
Modes de gestion de la fen tre
w Deux modes de fonctionnement :
n chaque bloc est acquitt . lors de la r ception dun
ACK, l metteur lib re un buffer et met le
suivant: la fen tre est dite glissante
n le bloc nest pas n cessairement besoin d tre
acquitt individuellement. Lacquittement peut tre
diff r et concerne plusieurs blocs: la fen tre est
dite sautante
47
La fen tre danticipation : fen tre
glissante(sliding window)
w Fen tre dynamique: elle volue au fur et mesure
des missions et des acquittements de blocs :
w L mission de blocs sans ACK fait progresser la borne
inf rieure jusquau blocage ventuel de l mission
(fen tre ferm e).
w Lacquittement de blocs par le r cepteur fait
progresser la borne sup rieure: fen tre glissante
48
La fen tre danticipation : fen tre
glissante
49
La fen tre danticipation : fen tre
glissante (w=3)
A
B
A
B
(a,0)
(b,1)
(a)
(b)
(c)
I0
I1
I2
ACK0
ACK1
ACK2
(a)
(b)
I0
ACK0
I1
ACK1
I2
ACK2
Advertisement
(a,0)
(b,1)
(c,2)
50
Protocole fen tre sautante
w Lacquittement concerne plusieurs
blocs (acquittement collectif ou
global): un seul ACK acquitte N blocs
(ainsi ACK2 signifie jai bien re u 3
blocs de donn es (0, 1, et 2 .
w N est la fen tre danticipation
w Fen tre d mission : nombre de blocs
en attente d'acquittement
A
B
I0
I1
I2
ACK2
I3
(w=3)
51
Probl me
w Transmettre un message de A B, en tenant
compte
n Des erreurs
n Des pertes
n Du temps de traitement (couches sup rieures. . . )
w La r ception dun NACK (acquittement
n gatif) ou l ch ance dun temporisateur
52
La politique de reprise sur erreur
w Deux modes de fonctionnement, selon la
technique de reprise sur erreur :
n reprise depuis le bloc erron (rejet simple)
GO-BACK-N
n reprise du bloc erron seulement (rejet s lectif)
Selective Repeat
53
Le rejet simple
w La r ception dun NACK (acquittement n gatif) ou
l ch ance dun temporisateur provoque :
n larr t des missions en cours,
n la reprise depuis le bloc erron ou perdu
n l limination par le r cepteur des blocs re us
post rieurement.
w le s quencement est conserv , et le r cepteur naura
pas trier les blocs pour les remettre en s quence.
w L metteur doit poss der N tampons (pour conserver
les N blocs mis jusqu ce quils aient t tous
confirm s) et le r cepteur 1 seul tampon.
54
Exemple de la retransmission simple
avec fen tre glissante (w=3)
A
B
I0
I1
I2
ACK0
ACK1
NACK2
Rejet(erron )
I3
I4
Rejet
Rejet
I2
I3
I4
ACK2
ACK3
ACK4
55
Le rejet s lectif
w Seul le bloc erron est retransmis. Cela implique la
m morisation des blocs hors s quence (non rejet s
sils ont t confirm s).
w Lanticipation est cependant limit e par les
possibilit s de comptage des blocs mis.
w le r cepteur devra ex cuter un programme de tri
pour r tablir le s quencement initial.
56
Exemple de la retransmission s lective
avec fen tre glissante (w=3)
A
B
A
B
I0
I1
I2
I0
I1
I2
ACK0
ACK1
NACK2
Rejet(erron )
ACK0
ACK1
NACK2
Rejet(erron )
I3
I4
I2
ACK4
Mettre dans Buffer
Mettre dans Buffer
R ordonnacement
2,3,4
I2
ACK3
ACK4
ACK2
I3
I4
Mettre dans Buffer
Mettre dans Buffer
R ordonnacement
2,3,4
57