Chapitre 3 :La Liaison de données :
4-1Définition ; La couche liaison de données fournit les moyens fonctionnels et procéduraux nécessaires &
Vétablissement, au maintien et a la libération des connexions de liaison de données entre
entités du réseau. Elle détecte et corrige, si possible, les erreurs dues au support physique et
signale & la couche réseau les erreurs irrécupérables. Elle supervise le fonctionnement de la
transmission et définit la structure syntaxique des trames, la maniére d'enchainer les échanges
selon un protocole normalisé ou non. Une liaison de données est réalisée & l'aide d'une ou
plusieurs liaisons physiques entre deux machines adjacentes dans le réseau done sans neeuds
intermédiaires entre elles.
4-2-Objectifs de la couche li: yn de donné:
* Que les blocs échangés soient structurés selon des formats standards et clairement délimités. ~afin de les
reconnaitre et les interpréter- exp : bit start et 2 bits stop.
‘« Implémentation d’un mécanisme de détection d’erreur , et éventuellement une stratégie de correction
@erreur . exp : bit de parité,
* Asservir l’émetteur a la capacité d’absorption du récepteur , le mécanisme de régulation de flux pour
assurer une exploitation optimale du canal et pour I’évitement erreur d’éerasement.
+ Prévoir une procédure de dialogue entre I’émetteur et le récepteur . exp : protocole de liaison -HDLC-.
ETD ETcD 7 EreD ETD
SD lrce Tigne de
XI]
Circuit de données itecaptdit
Liaison de données
Emetteur
SD : Source de données.
CC : Contrdleur de communication
Spécification
finition d’une trame
Tout bloc de données échangé au niveau d’une liaison de données. Le format d’une trame dépend du type
de protocole de liaison de données.
ly a deux type de protocoles de liaison synchrone comme (HDLC) , et asynchrone comme( ATM).
4-3-1 Protocoles Synchrones :
Ilya deux types de protocoles de liaison synchrone
a- Basé sur le caractére (COP : Character Oriented Protocol).
b- Basé sur le bit (BOP : Bit Oriented Protocol),
a- Format de trame pour protocole basé sur le caractore :
TIs'agit de trames formées d'un nombre entier d'octéts généralement variable.
Soit l’exemple d’une trame de protocole BSC d’IBM (Binary synchronous contrél)
SYN] SYN [ SOH [HEADER | STX DONNEES ETX| BCC
SYN , SOH ,STX ,ETX : sont des caractéres réservés choisis parmi
SYN : caractére de synchronisation , il précéde toute émission de nouvelle trame.
SOH : (start of header) début d’entéte.
Header : un entéte compose généralement dune adre
STX : (start of text) indique le début des données utiles.
ETX : (end of text) indique la fin de données utiles.
BCC : (Block check charcter) est un caractére utilisé pour le contrdle d’erreur
du récepteur et le N° d’ordre de séquence de trame
30 Si le champ données contient un caractére de contréle il ya un risque de fausse interprétation pour assurer la
transparence de la transmission il faut insérer un caractére « DLE : data link escape).
b- B-Format de trames basées sur le bit
Basée sur le bit, il n’est pas exigé que la trame soit constituée d’un nombre entier d’octets , par exemple
le protocole HDLC .(high level datal link control):
Est apparu en 1976 pour répondre aux besoins de communiquer un terminal avec une machine distante.
HDLC améliore les protocoles basés sur transmission synchrone c-ied envoi de message et attente
(BCC: block check character) est un bloc de parité longitudinale.
Liinconvénient de cette méthode de protection est quelle est inefficaces en cas d'occurrence d'erreurs groupées
1-3 les codes polynomiaux (CRC : le code redondant cyclique):
utilisation des codes polynomiaux permet de calculer pour chaque séquence de données utiles une
séquence de données redondantes garantissant une protection relativement efficace contre les erreurs groupées ,
utilisée généralement par les protocoles orientées bit. (BOP) par exemple I'HDLC
Soit : itizis....ip : une séquence de données utiles , et ritats........k sume séquence de données redondantes
On définit deux polyndmes
T¢)= ix Hig” Hix tim Hi
ROX) x Hox itt,
Soit un polynéme générateur : G(x) de degré k.
Tel que R(x)= le reste de la division de I(x)x* par G(x) , en d'autre terme
Iix)x* +R(X)=Q(x)*G(X) , tel que Q(x) est le quotient de la division
Si la transmission est passée sans erreurs la trame regu est supposée correspondre I(x)x* +R(x) qui
divisible par G(x) cest-a-dire que R'Qx)=0.
Le champ FCS du protocole HDLC= R(x).,
Gox)=x!x!7 P41
1 le protocole générateur utilisé par I'HDLC est
A la réception, on divise le polynéme I(x)x* +R(x) correspondant a la suite totale de bits regus
(information+CRC) par le polynéme générateur, Si le reste calculé est non nul, c'est qu'une erreur s'est produite
dans la transmission. Si le reste est nul, on est & peu prés sir (99,975% avec le polynéme générateur
Gox=x'? + x!? + x5 +1 de la norme V41 du ITU-T) que la transmission s'est faite sans erreur
32 Pourquoi cela fonctionne-t-il? Il est évident que x‘ *1(x) + R(x) est divisible par G(x), mais en
arithmétique modulo 2 addition et soustraction sont équivalentes (ce sont des OU exelusifs en fait) done on a
également E(x) = x'I(x)+R(x) = G(x)Q(x) montrant que E est un polynéme multiple de G.
il faut aussi remarquer un inconvénient de cette méthode qui signale des erreurs de transmission méme si
celles-ci ont eu lieu dans le CRC et non dans l'information & transmettre initialement, Dans ce cas il ne devrait
pas étre nécessaire de retransmettre l'information, or c'est ce qui est fait puisque globalement le transfert
(info+CRC) a subi des perturbations. si E(x) le polyndme formé par les erreurs est divisible par G(x) alors le
reste =0 et lerreur est indétectable.
Enfin , comme avantages:II permet la détection des erreurs groupées formées de k bits.
4-4-2-Méthodes de protection pour la correction :
Pour ce type de protection l'information redondante doit étre déterminge de maniére telle que le récepteur
puisse non seulement détecter les erreurs mais également procéder A leur correction a solution la plus simple
consiste a émettre chaque information en plusieurs exemplaires (trop cotiteuse).
Par exemple, le code de Hamming est un code correcteur d'erreurs basé sur la notion de distance de
Hamming.
Soit un alphabet composé de 4 caractéres (00,01,10,11). Si une erreur se produit alors le ca
transformé en un autre earactére et il n'y a pas moyen de retrouver le caractére original
Par contre, en ajoutant de l'information de telle sorte que les caractéres soient trés différents les uns des
autres cela devient possible, Par exemple, on peut coder les 4 caractéres de la maniére suivante
tere émis est
caractére initial 00 1 10 u
caractére émis 00000 ory 10110 11001
00001 01110 10111 11000
erronées 00010 o1011 10100 Holl
00100 oo1ll 10010 11101
10000 mu 1110 10001
Tab. 1.1 - Codage de Hamming.
illustrée dans la table 1.1. Ainsi si un bit (parmi les 5 émis) est erroné on sait quand méme déterminer quel
caractére a é16 émis, car comme on peut le voir dans la table 1.1 la modification d'un bit ne peut pas faire passer
d'un caractére initial 4 Vautre, On a des ensembles d'erreurs possibles totalement disjoints, Par contre la
modification de 2 bits dans cet exemple peut amener a des confusions et a I'impossibilité de corriger les erreurs.
Soit x et y deux caraetéres d'un alphabet A et soit N la longueur du codage des mots de cet alphabet, xi et yi
désignent respectivement le ie bit de x et y. On peut alors définir la distance d(x; y) “Ec.w(xi-¥i) mod 2 qui
permet de compter le nombre de bits qui différent entre x et y. On définit alors la distance de Hamming par dH
= inf d(x:y)
Ainsi, quand on regoit un caractére x (erroné ou non on ne peut pas le savoir & lavance) il suffit de chercher le
caractére c © A le plus proche de x selon la distance d pour obtenir le caractére émis.
Un exemple de code de Hamming est donné par la technique suivante oit 'on veut envoyer des caractéres codés
sur 4 bits de données ABCD. Pour cela on va émettre la suite ABCP3DP2P1
ajoutant une suite de trois bits de données redondantes P1P2P3 tel que les bits de contrle Pi sont placés sur les
bits de rang 2i et son définis par de maniére a satisfaire le systéme d'équation (ensemble d’équations) tel que
PI-A¥C4D
P2-A1BID
P3-A4B+C
Les Pi sont les bits de parité a I'aide des bits de parité de rang K tel que la décomposition de k en somme de
puissance de 2 contient 2i
A laréception , le récepteur calcule les équations suivantes :
P'l=P1+A+C+D
P'2=P2+A+B+D
=P" =0 alors c'est que la transmission s'est passée sans probléme , sinon la valeur binaire
P'3P'2P'1 donne la place de l'erreur dans les bits regus (on commengant par la droite)on corrige alors lerreur et
33 on recalcule les Pi siils sont devenus tous nuls lerreur a ét6 corrigée , sino il y avait eu au loin deux erreurs
alors I'émetteur doit retransmettre 4 nouveau cette trame,
34 44-3 Méthodes de correction par retransmission
‘Ces méthodes sont appelés méthodes de retransmission automatiques (ARQ automatique repeat request) on
distingue trois types
a/ retransmission avec arrét et attente (Idle RQ) :
4 la réception d'une trame d'information correcte par le recepteur,, il renvoie a I’émetteur une trame
d’acquittement (un accusé de réception) , une trame d’acquittement de taille relativement courte
Sert & acquitter une ou plusieurs trames.
fmetiour siconceut
Data
Un délai de garde est armé & I’émission si a ’éxpération du delai pas d’acquittement regu , alors l'emetteur
suppose que la trame perdue.
Méme en cas de perte d’aquittement , il y aura une retransmission de la trame plusieurs fois, au bout d’un
nombre limite de retransmission , la liaison est supposée défaillante , la couche supérieur est informée.
b/reteransmission continue (Continuous RQ)
l’émetteur transmet plusieurs trames d’informations successivement sans attendre d’acquitement pour chaque
trame :
émetteur trame °T récepteur
Liste des,
copies acquittement °I
de retransmission
on arme une horloge de délai de garde pour chaque trame émise.
On garde une copie des trames émises dans une liste de retransmission.
Les trames et les acquittements sont numérotés.
Si le délai de garde==0 et l’acquittement n'est pas regu N°(i),
Retransmission de la trame N°(i).
Sinon
Désarmer ’horloge N°(i)
Retirer la copie de la trame & partir de la liste de retransmission.
Finsi.
Ilya deux méthodes de retransmission continue :
bel retransmission systématique (Go-Back-N) :
le recepteur acquitte les trames correctes et qui sont regues dans l’ordre per exemple : le recepeteur & regu
correctement t21315t6 dans ce cas les trames t5 et 66 seront ignor
4 expiration du délai de garde de la tarme t4 , l'emetteur retransmettera les trames t4 , 15 et t6 .
Le recepteur n’envoie pas d’acquittement vers l’emetteur que pour les trames regues dans l'ordre supposons
que la trame
35 TO
Tl
12
13
T4
TS
16
12
T3
T4
On peut améliorer la retransmission systématique par l'utilisation des acquittements positives et négatives.
* Positive (I+1) signifie que I et bien regue méme en cas de perte de I’acquittement de (I).
+ Négative() signifie que la trame I n’est pas regu commencer a retransmettre & partir de I.
b-2 retransmisstion séléctive.
Le recepteur acquitte les trames correctement regues méme arrivées dans le désordre, il garde une liste de
reception oi! les trames seront réorganisées.
Si une trame ti n’est pas regue , mais on recoit une trame i+1 alors le recepteur acquitte la trame i+1 par un
acquittement +1
A Vexpiration du délai de garde et 4 la reception de l'acquittement de la trame suivante , la trame non acquittée
et retransmise elle seule.
Comparaison entre selective et systématique :
I-dans systématique : la liste de réception est réduite et ne contienne que la demiére trame recue.
2-V’encombrement du canal par des trames retransmises.
Pour les deux cas on peut si on a une configuration fullduplex , de mélanger une trame d’information du
recpeur avec l’acquittement attendu , ceci est appelé « Piggybacking ».
Lobjectif du contrdle de flux est d’adapter le débit de I’émetteur en fonction de la capacité d’absorption
du récepteur, tout en assurant une utilisation maximale de capacité du canal,
1-mécanisme X-on/X-off (protocole orienté caractére).
Pour les liaisons asynchrones simples
X-on, X-off : sont deux caractéres de code ascii
X-off : indique a l’émetteur de cesser toute émission.
X-on : indique 4 l’émetteur de reprendre son émission,
2-mécanisme de la fenétre (Protocole orienté bits)
L’idée de fixer le nombre de trames maximum qui peuvent étre émises par I’émetteur sans attente
Hacquittements, est égale A la taille de la liste de retransmission dés que le nombre est atteint I’émission est
stoppée
L’émission ne peut reprendre que lorsque une ou plusieurs on été acquitté
Remarque :
Lorsque le récepteur n’est plus en mesure d’absorber de nouvelles trames , il suffit done que le récepteur
retarde l’envoi d’acquittement I’émetteur et contraindre le dernier & cesser toute nouvelle émission de trames.
+ La fenétre l’émission : dépend de la taille maximum de trames, le nombre de tampon disponibles, le
débit de canal.
36 «La fenétre en réception : l'ensemble de trame que I’émetteur est disposé 4 accepter dépend du type de
retransmission implémentée.
* Lecas de la systématique =1
+ Leas de la retransmission sélective= au moins 4 la taille de la fenétre en émission.
Le modulo utilisé
1- en cas de retransmission systématique (k+1),
2. En cas de retransmission sélective (2k).
37
