8/2/2019 Chapitre5-Liaison de donnes
1/25
Introduction aux Rseaux
Protocoles et procdures de
transmission de donnes
Amine DHRAIEFEcole Nationale des Sciences de Linformatique
Universit de la Manouba
15/12/2011 Introduction aux Rseaux 1
Introduction
RseauRseau RseauRseauN-PDU
LiaisonLiaison LiaisonLiaison
Bits 010101
L-PDU
15/12/2011 Introduction aux Rseaux 2
Support Physique
Introduction
Liaison de donnes
Lors de lchange de donnes, le protocole detransfert doit assurer :
Support Physique
le contrle de lintgrit des donnes reues;
lorganisation et le contrle de lchange ;
ventuellement le contrle de la liaison.
15/12/2011 Introduction aux Rseaux 3
PROTOCOLE DE LIAISON DE
DONNES
15/12/2011 Introduction aux Rseaux 4
8/2/2019 Chapitre5-Liaison de donnes
2/25
Protocole de liaison de donnes
Rappel : Un protocole dfinit
e orma es messages c ang s La smantique/signification des messages
changs
Les rgles dchange
essages c ang s appe s rames. Trame = L-PDU
L-PDU = L-SDU + L-PCI
15/12/2011 Introduction aux Rseaux 5
Trames
Une trame est une suite de bits. Cest le L-PDU
Selon le protocole, elle peut tre de taille fixe ou variable (maisborne)
. , erne : a e var a e ATM : Taille fixe (53 octets)
Dlimitation explicite ou implicite. Utilisation de fanions de dbut (et de fin) de trame. Dtection de fin de trame par absence de signale
,
parties: en-tte, donnes et terminaison.
Len-tte et la terminaison forment le L-PCI
15/12/2011 Introduction aux Rseaux 6
Exercice
Le protocole ATM (Asynchronous Transfero e est un protoco e e transm ss on qu
fonctionne aux dbit suivants : 155Mbit/s,620 Mbit/s et 1.24 Gbit/s. Le format dunpaquet ATM, aussi appel cellule, est lesuivant :
Introduction aux Rseaux 715/12/2011
Exercice 6
1) Quel est le rendement du protocole?
2) Quelle est la dure dmission dunecellule aux dbits prcdemment indiqus?
Introduction aux Rseaux 815/12/2011
8/2/2019 Chapitre5-Liaison de donnes
3/25
Correction
1) rendement =48/53 = 0,9056 = 90%
2) 155 Mbit/s dure mission = 53* 8/155.10^6
= 2,74s
620 Mbit/s dure mission = 53*8/620.10^6 =, s
1,24 Gbit/s dure mission = 53*8/ 1 ,24.10^9= 0,34 s
Introduction aux Rseaux 915/12/2011
Exercice
Une lgende dans le monde des
dune cellule ATM est le rsultat dun compromisentre les Etats-Unis et lEurope, li auxcontraintes de la tlphonie.
-
une grande tendue (4 500 Km dun ocan lautre), compar aux pays europens (1000 Kmpour la France).
Introduction aux Rseaux 1015/12/2011
Exercice
3) Si lon prend 200 000 Km/s comme vitesse depropagation dun signal dans un fil de cuivre ou unefibre optique, combien de temps faut-il pour quun bit
soit transport dune cte lautre des tats-Unis ?
4) La voix, aux tats-Unis, est chantillonne 56Kbit/s, combien de temps faut-il pour remplir unchamp donne de 64 octets ?
5) En Europe, la voix est chantillonne 64 Kbit/s,combien de temps faut-il pour remplir un champdonne de 32 octets ?
Introduction aux Rseaux 1115/12/2011
Correction
3) t = 4500.10^3 / 200000.10^3 = 22,5ms
4) tech = 64 *8 / 56.10^3 = 9.14ms
5) tech = 32* 8 / 64.10^3 = 4ms
Introduction aux Rseaux 1215/12/2011
8/2/2019 Chapitre5-Liaison de donnes
4/25
Format gnrale dune trame
DlimiteurDlimiteurdu dbutdu dbut
DonnesDonnes DlimiteurDlimiteurde finde fin
15/12/2011 Introduction aux Rseaux 13
amps n ormat onEntte erm na son
Mthodes de dlimitation des trames
Chaque trame commence par un dlimiteur de dbut et peut se terminerpar un dlimiteur de fin.
Un dlimiteur peut tre : soit une squence particulire de caractres, soit une suite particulire de bits,
exemple : le fanion 01111110 du protocole HDLC.
soit un codage particulier Des squences, non-utilises pour coder les lments binaires, servent dlimiter les
trames.
: Len-tte de trame contient un champ indiquant la longueur de la trame. Problme: si la valeur du champ est modifie au cours de la transmission Mthode rarement utilise seule
15/12/2011 Introduction aux Rseaux 14
Exemple dutilisation dun compteur decaractres
06 S U P E R 03 L E 06 C O U R STrameEmise
ParasitesParasites
15/12/2011 Introduction aux Rseaux 15
TrameReue 06 S U P E R 04 L E 06 67 O U R S
Code ASCII de C
Notion de fanion
linstar des transmissions asynchrones o lests e start et e stop enca rent es ts
dinformation, en transmission synchrone uncaractre spcial ou une combinaison de bitsparticulire, le fanion, permet de reprer ledbut et la fin des donnes transmises
15/12/2011 Introduction aux Rseaux 16
8/2/2019 Chapitre5-Liaison de donnes
5/25
Notion de fanion
Le fanion assure trois fonctions essentielles :
i imite es onn es ; mis en labsence de donnes mettre, il permet de
maintenir la synchronisation de lhorloge rception ;
dans le flot de bits transmis, le rcepteur doitreconnatre les caractres. En identifiant le fanion, le
frontire doctets (synchronisation caractre) et, parconsquent, traduire le flux de bits reus en un fluxdoctets.
15/12/2011 Introduction aux Rseaux 17
Notion de transparence
Lutilisation dun caractre spcifique pour indiquer ledbut ou la fin dun bloc de donnes interdit lusage de ce
caract re ans e c amp onn es.
En consquence, il faut prvoir un mcanisme particuliersi on veut transmettre, en tant que donnes, le caractreou la combinaison binaire reprsentative du fanion.
caractre, si le fanion est un caractre, ou mcanisme detransparence binaire, si le fanion est une combinaison debits
15/12/2011 Introduction aux Rseaux 18
Notion de transparence
Le mcanisme de transparence consiste baliser lecaractre protger par un autre caractre ditcaractre dchappement.
Ce caractre insr lmission devant le caractre protger (le faux fanion) doit lui-mme tre protgsil apparat dans le champ donnes
15/12/2011 Introduction aux Rseaux 19
Notion de transparence
Lmetteur insre le caractre dchappementevan e carac re pro ger.
En rception, lautomate examine chaquecaractre pour dcouvrir le fanion de fin.
,llimine et ninterprte pas le caractre qui lesuit, il le dlivre au systme
15/12/2011 Introduction aux Rseaux 20
8/2/2019 Chapitre5-Liaison de donnes
6/25
Notion de transparence
Le fanion est reprsent par la combinaison binaire 01111110 soit 0x7E. La transparence binaire est assure par linsertion dun 0
tous les 5 bits 1 conscutifs. Seul, le fanion contiendra une combinaison binaire de plus
de 5 bits 1 conscutifs (01111110).
Cette technique dite du bit de bourrage (bit stuffing),,
resynchronisation des horloges en interdisant leslongues squences de bits 1 conscutifs. Les bits de bourrage insrs lmission sont limins par
lautomate de rception.
15/12/2011 Introduction aux Rseaux 21
Notion de transparence
15/12/2011 Introduction aux Rseaux 22
TECHNIQUES DE CONTR LE
15/12/2011 Introduction aux Rseaux 23
Techniques de contrle
Sassurer que le rcepteur a reu correctement, en unseul exemplaire, et dans lordre les trames mises.
Deux phnomnes viennent perturber la transmission la corruption de trames: transformation de la suite binaire
transmise
la perte de trames: due la non-transmission ou la non-reconnaissance de la trame (ex : corruption du dlimiteur)
une corruption se traduit par une perte lorsque lercepteur dtruit la trame corrompue
15/12/2011 Introduction aux Rseaux 24
8/2/2019 Chapitre5-Liaison de donnes
7/25
Techniques de contrle: les solutions
I. Mcanisme de dtection des erreurs
II. Mcanisme dacquittement positif ou ngatif
III. Techniques de mmorisation des trames et decorrection par retransmission
IV. Utilisation de temporisateurs
V. Identification des trames
15/12/2011 Introduction aux Rseaux 25
Identifications
Une numrotation permet didentifier les trames et leuracquittement
Lunit didentification varie en fonction des protocoles: latrame (par exemple HDLC), loctet (par exemple TCP)
Plus lunit est petite plus lidentification est prcise mais plus
ex : HDLC = 3 bits (ou 7 bits), TCP = 16 bits
La numrotation se fait modulo N(=2la_largeur_du_champ_de_numrotation)
15/12/2011 Introduction aux Rseaux 26
Identifications
Lidentification permet de dtecter
labsence de trames: perte
la duplication de trames: destruction du duplicata
lordonnancement des trames:rordonnancement si la mmorisation estautorise
sinon destruction des trames narrivant pas dans
le bonne ordre (+ facile).
15/12/2011 Introduction aux Rseaux 27
Perte de trames
I. Vrification de donnes Vrification du format des trames: longueur, valeurs prdfinies de
certains champs
II. Notification de lmtteur Soit implicitement: par temporisateur arm chaque envoi de
trame, dsarm lors de la rception dun acquittement Soit explicitement: par un Negative Acknowledgment (Nack)
Le rejet total: retransmission de toutes les trames partir de celle spcifie Le rejet slectif: retransmission de la trame spcifie
III. Retransmission de la trame (perdue ou dtruite) par lmetteur
15/12/2011 Introduction aux Rseaux 28
8/2/2019 Chapitre5-Liaison de donnes
8/25
Piggybacking
Au sein dun flot de donnes unidirectionnel, on peutdiscerner deux sous-flux: le sous-flux de donnes: de lmetteur de donnes au
rcepteur et le sous-flux de commande: du rcepteur vers lmetteur
de donnes (Ack par exemple).
Lorsque le flot de donnes est bidirectionnel, deux.
Les deux systmes dextrmit fonctionnent la foiscomme metteur de donnes et comme rcepteur dedonnes.
15/12/2011 Introduction aux Rseaux 29
Piggybacking
flot de donnes unidirectionnel flot de donnes bidirectionnel
DATA
CMD
DATA DATA
15/12/2011 Introduction aux Rseaux 30
Piggybacking
Piggybacking: -
donnes dun sens de transmission sontcombines avec les trames du sous-fluxde commande de lautre sens.
Par exemple : Une mme trame peut se
donnes (elle possde un champ
dinformation) et un acquittement (ellepossde un champ du mme nom).
15/12/2011 Introduction aux Rseaux 31
Piggybacking
Sans piggybacking Avec piggybacking
DATA DATA DATA + CMD DATA + CMD
15/12/2011 Introduction aux Rseaux 32
8/2/2019 Chapitre5-Liaison de donnes
9/25
Du mode Send and Wait aux protocoles anticipation
Le principe de base de toute transmission repose surlenvoi (Send) dun bloc dinformation. Lmetteur sarrte alors (Stop) dans lattente (Wait) dun
accus de rception. la rception de lacquittement, not ACK pour
Acknowledge, lmetteur envoie le bloc suivant
15/12/2011 Introduction aux Rseaux 33
Du mode Send and Wait aux protocoles anticipation
En cas derreur de transmission, le bloc reu est rejet. Le bloc estdit perdu, il nest pas acquitt.
Lmetteur reste alors en attente. Pour viter un blocage de latransmission, lmission de chaque bloc de donnes, lmetteurarme un temporisateur (Timer)
lchance du temps imparti (Time Out), si aucun accus derception (ACK) na t reu, lmetteur retransmet le bloc nonacquitt.
Cette technique porte le nom de reprise sur temporisation (RTO,Retransmission Time Out) ou correction derreur surtemporisation
15/12/2011 Introduction aux Rseaux 34
Du mode Send and Wait aux protocoles anticipation
15/12/2011 Introduction aux Rseaux 35
Du mode Send and Wait aux protocoles anticipation
Une difficult survient si la perte concerne .
En effet, bien que les donnes aient tcorrectement reues, lmetteur les retransmetsur temporisation.
Les informations sont ainsi reues 2 fois. Pourviter la duplication des donnes, il est ncessairedidentifier les blocs.
cet effet, lmetteur et le rcepteurentretiennent des compteurs
15/12/2011 Introduction aux Rseaux 36
8/2/2019 Chapitre5-Liaison de donnes
10/25
Du mode Send and Wait aux protocoles anticipation
Les compteurs Ns (Ns, Numro mis, s pour send) etNr Numro du bloc recevoir r our receive sontinitialiss zro.
Le contenu du compteur Ns est transmis avec le bloc,le rcepteur compare ce numro avec le contenu deson compteur Nr. es eux va eurs son en ques e oc es r pu va e
et accept. Si les valeurs diffrent, le bloc reu nest pas celui attendu.
Il est rejet et acquitt sil correspond un bloc dj reu.
15/12/2011 Introduction aux Rseaux 37
Du mode Send and Wait aux protocoles anticipation
15/12/2011 Introduction aux Rseaux 38
Du mode Send and Wait aux protocoles anticipation
Dans le cas contraire (Ns > Nr), il sagit duneerreur e ransm ss on
15/12/2011 Introduction aux Rseaux 39
Contrle de flux
Utilisation d'acquittements
Gestion de temporisateurs
Numrotation des trames
Limitation du nombre de trames pouvanttre envoyes par l'metteur
15/12/2011 Introduction aux Rseaux 40
8/2/2019 Chapitre5-Liaison de donnes
11/25
Protocole 1
Hypothses:
Mmoire tampon infinie Canal parfait (pas de pertes ni d'erreurs)
Protocole monodirectionnel:
un metteur un rcepteur
Protocole utopique
15/12/2011 Introduction aux Rseaux 41
Protocole 1
Emetteur Rcepteur
Tant que (vrai) rpterPcoucheReseau.donnerPaquet()
T construireTrame(p)
couchePhysique.prendreTrame(T)
Fin tant que
Tant que (vrai) rpterTcouchePhysique.donnerTrame()
P extrairePaquet(T)
coucheReseau.prendrePaquet(P)
Fin tant que
15/12/2011 Introduction aux Rseaux 42
Protocole 2
Protocole de type envoyer et attendre en a t
Hypothse leve : mmoire tampon infinie
Principe
Le rcepteur envoie une trame d'acquittement
Lmetteur attend de recevoir un acquittement
avant d'mettre la trame suivante
15/12/2011 Introduction aux Rseaux 43
Protocole 2
Emetteur Rcepteur
Tant que (vrai) rpterPcoucheReseau.donnerPaquet()
T construireTrame(p)
couchePhysique.prendreTrame(T)
attendreAck ()
Tant que (vrai) rpterTcouchePhysique.donnerTrame()
P extrairePaquet(T)
coucheReseau.prendrePaquet(P)
envoyer Ack()
Fin tant que Fin tant que
15/12/2011 Introduction aux Rseaux 44
8/2/2019 Chapitre5-Liaison de donnes
12/25
Protocole 3
Hypothse leve : canal parfait
es rames peuven re erron es Des trames peuvent tre corrompus
Principe Utiliser une mthode de dtection derreurs
Le rcepteur met une trame d'acquittement si latrame arriv e est correcte.
Lmetteur rmet une trame si aucun ack reu etsi un certain dlai de temporisation a expir
15/12/2011 Introduction aux Rseaux 45
Protocole 3Emetteur
Tant que (vrai) rpter
couc e eseau. onner aqueT construireTrame(p)
Boolen Ack FAUX
Tant que (Ack = FAUX) rptercouchePhysique.prendreTrame(T)
Fin Tant que
Fin tant que
15/12/2011 Introduction aux Rseaux 46
Protocole 3Rcepteur
Tant que (vrai) rpter
T couchePhysique.donnerTrame()
Si estCorrecte (T) alorsP extrairePaquet (T)
coucheReseau.prendrePaquet(P)
envoyerAck ()
Fin Si
Fin Tant que
15/12/2011 Introduction aux Rseaux 47
Mcanismes gnrauxContrle de flux: Protocole 3Problme
Problme:
Trame 1
Ack
Timeout Trame 1
r c p ur n
distinguepas une trametransmise pour lapremire fois dunetrame retransmise
15/12/2011 Introduction aux Rseaux 48
cSi A envoie B un
fichier, une partie defichier sera duplique
8/2/2019 Chapitre5-Liaison de donnes
13/25
Protocole 3Solution
il est ncessaire de numroter les trames
pour st nguer eux trame success ves.
il est prfrable que la trame d'acquittementcontienne le numro de la trame qui est
.
15/12/2011 Introduction aux Rseaux 49
Protocole 4
La liaison de donnes est alors inoccupe la plupart du temps.
Lmetteur passe son temps attendre lacquittement du rcepteur
Le rcepteur passe son temps attendre la trame de donnes de lmetteur
Protocole fentres danticipation (sliding windows)
Deux fentres sont gres par chaque entit de couche liaison. En effet:
Toute entit mettrice possde une fentre d'anticipation appel fentredmission.
Toute entit rceptrice possde une fentre d'anticipation appele fentre der cep on
15/12/2011 Introduction aux Rseaux 50
Protocole 4Sliding Windows
On autorise lmission (resp. la rception) deplusieurs trames dinformation conscutivessans attendre lacquittement de la premire(resp. avant denvoyer lacquittement).
mettent et reoivent simultanment que la
liaison est utilise de manirebidirectionnelle
15/12/2011 Introduction aux Rseaux 51
Protocole 4Sliding Windows
Fentre dmission: 012
3
La liste des numros de squence des trames autorises tremises Exemple: Taille fentre 2: lmetteur a reu Ack pour trame 0 et 1 ,
donc il peut envoyer les trames 2 et 30
12
3
La liste des numros de squence de trames dont on attendlacquittement (trames en mmoire tampon )
Exemple: Taille fentre 2: lmetteur a envoy trame 0 et 1 sansavoir reu dAck
15/12/2011 Introduction aux Rseaux 52
0
12
3
Mcanismes gnra
8/2/2019 Chapitre5-Liaison de donnes
14/25
Protocole 4Sliding Windows
Fentre de rcption : 012
3
La liste des numros de squence des trames autorises tre reues
Exemple: Taille fentre 2: le rcepteur a acquitt les trame 0 et1 , lmetteur peut envoyer les trames 2 et 3
15/12/2011 Introduction aux Rseaux 53
0
12
3
Mcanismes gnrauxContrle de flux: Protocole 4
Acquittement
Lorsque plusieurs trames doivent tre
acqu tt es, est poss e : denvoyer un acquittement individuel pour
chaque trame
denvoyer un acquittement collectif enindiquant le plus grand numro de trame parmicelles qui sont acquittes ou le numro de laprochaine trame attendue.
15/12/2011 Introduction aux Rseaux 54
Protocole 4Acquittement
Trame 0
Trame 1
Trame 2
15/12/2011 Introduction aux Rseaux 55
c
Protocole 4Acquittement
Sans Fentre coulissante Avec Fentre coulissante
DATA
ACK
15/12/2011 Introduction aux Rseaux 56
ACK
Protocole 4
Protocole 4
8/2/2019 Chapitre5-Liaison de donnes
15/25
Protocole 4Dimensionnement de la largeur de la fentre
Pour viter la congestion du rcepteur, cest--dire ledbordement de son espace de stockage quientranerait la destruction de trames La largeur de la fentre doit correspondre la capacit de
stockage du rcepteur
Dans le cas dune fentre de largeur fixe la fentre est ouverte ou ferme le contrle seffectue sur la totalit de la fentre
Dans le cas dune fentre de largeur variable La largeur est adapte la capacit de stockage du
rcepteur
15/12/2011 Introduction aux Rseaux 57
Protocole 4Dimensionnement de la largeur de la fentre
(W) la largeur de la fentre danticipation dmission(resp. de rception):
Pour que la capacit de la liaison de donnes soittotalement utilise il faut que : W* L >= RTT * D (L ) tant la longueur moyenne dune trame, (RTT) la dure daller/retour et (D) le dbit nominal de la liaison RTT*D: capacit de la liaison
La largeur de fentre peut tre : Fixe :par exemple : HDLC ou X25.3 Variable: par exemple : TCP
15/12/2011 Introduction aux Rseaux 58
Protocole 4Techniques de rejet
Si une trame situe au milieu d'une srie est
perdue ou errone ?
Deux techniques de rejet sont possibles:
Technique du rejet total
Technique du rejet slectif (Go Back N)
15/12/2011 Introduction aux Rseaux 59
Protocole 4Rejet Total vs. Rejet Slectif
Rejet Total Rejet Slectif
Le rcepteur rejette toutes
les trames qui suivent cellequi est errone.
Inconvnient : le canal estmal exploit
Le r cepteur accepte es
suivantes (en les stockant)jusqu' une certaine limitedonne
avantage : le canal estmieux ex loit
Avantage : pas besoin demmoires tampons
inconvnient : besoin demmoires tampons
15/12/2011 Introduction aux Rseaux 60
L t l HDLC (Hi h L l D t Li k C t l)
8/2/2019 Chapitre5-Liaison de donnes
16/25
HIGH LEVEL DATA LINK CONTROL
15/12/2011 Introduction aux Rseaux 61
Le protocole HDLC (High Level Data Link Control)
En 1976, lISO normalise une procdure de communicationentre deux ordinateurs sous le nom de HDLC (High-level DataLink Control .
Cest la naissance du premier protocole standardis deniveau liaison.
Dautres protocoles moins puissants taient jusqualorsut s s. I s ta ent u type Sen Wa t.
La gnration HDLC procde par anticipation.
15/12/2011 Introduction aux Rseaux 62
Le protocole HDLC
Pour les besoins de transmission sur les liaisons des rseauxdes oprateurs, lUIT-T a repris un sous-ensemble de lanorme HDLC, la partie concernant le mode quilibr (tous lesquipements agissent de la mme faon)
Cette procdure a pris au dpart le nom de LAP (LinkAccess Protocol) et comportait des optionsparticulires.
Aprs des mises jour en 1980 et en 1984, laprocdure a t appele LAP-B (Link Access Protocol-Balanced).
15/12/2011 Introduction aux Rseaux 63
Le protocole HDLC
HDLC: offre un service de transfert de donnes fiable et
efficace entre deux systmes adjacents protocole utilisant le mode connect
Utilis comme rotocole de la couche Liaisonde donnes dans les normes X.25 en usage
dans les rseaux publics de transmissionnumrique de donnes
15/12/2011 Introduction aux Rseaux 64
La pile X25 & le protocole LAP-B
ARM vs ABM
8/2/2019 Chapitre5-Liaison de donnes
17/25
La pile X25 & le protocole LAP-B
X25.2: Liaison de donnes LAP-B
X25.3: Rseau
Cette norme a t tablie en 1976 par le CCITT (puisreprise par l'UIT-T) pour les rseaux commutation depaquets
'
X25.1: Physique
publics de communication : Transpac pour la France, EPSS pour la Grande-Bretagne,
Datapac pour le Canada, DCS pour la Belgique et Telenet pourles tats-Unis.
15/12/2011 Introduction aux Rseaux 65
ARM vs. ABM
2 modes opratoires principaux : Asynchronous Response Mode (ARM)
Asynchronous Balanced Mode (ABM)
Asynchronous Response Mode: Primaire / secondaire Mode matre-esclave, ce qui veut dire quune extrmit de
la liaison dirige lautre ct.
le plus courant tous les quipements agissent de la mme faon
mode quilibr (balanced)
15/12/2011 Introduction aux Rseaux 66
Le protocole LAP-B
Link Access Procedure Balanced
implmente la couche liaison de donnes dfinie
pas le protocole X.25. LAP-B est un protocole driv du protocole HDLC
LAP-B est essentiellement utilis dans l'HDLC enmode ABM
LAP-B = HDLC en mode ABM
15/12/2011 Introduction aux Rseaux 67
Format gnral dune trame HDLC
01111110 adresses Commande Information x16+x15+x2+1 01111110
Fanion8bits
8 bits 8 ou 16 bits >= 0 FCS16 bits
Fanion8 bits
15/12/2011 Introduction aux Rseaux 68
8/2/2019 Chapitre5-Liaison de donnes
18/25
Trame HDLC - Fanion
Fanion
Est un imiteur e trame pour a sync ronisation. Sa valeur est pour HDLC : 01111110 (binaire) - 7E
(hexadcimal)
Un octet form de 6 bits conscutifs 1, prfixs etsuffixs par un bit 0.
mm n ur r un n ur n n r
du fanion lintrieur de la trame puisque le champde donnes de la trame peut comporter nimportequel octet ?
15/12/2011 Introduction aux Rseaux 69
Trame HDLC - Fanion
Transcodage :
de la transmission. toute suite de 5 bits conscutifs 1 est transcode en
une suite de cinq bits 1 et dun bit 0. dcodage : opration inverse au rcepteur.
0111110 devient 01111100
01111110 devient 011111010 01111111 devient 011111011 011111110 devient 0111110110
15/12/2011 Introduction aux Rseaux 70
Trame HDLC - FCS
le FCS (Frame Check Sequence)
errone
16 bits
constitu du reste de la division polynomiale des Nbits de la trame par un polynme gnrateur normalis de degr 16
e r cepteur ait e m me avec es N its e a tramereue
si le reste est gal celui de la zone FCS on admet quela transmission s'est passe correctement
15/12/2011 Introduction aux Rseaux 71
Trame HDLC - Adresse
Adresse
celle du destinataire qui est envoye la trame.
cette adresse est utilise lorsque lacommunication est de type matre-esclave,l'adresse tant celle de l'esclave
en communication point--point, elle n'est pasutilise
15/12/2011 Introduction aux Rseaux 72
Trame HDLC - Commande Trame HDLC - Commande
8/2/2019 Chapitre5-Liaison de donnes
19/25
Trame HDLC Commande
Trois types de trames :
les trames dinformation (I Information)
les trames de supervision (S Supervisory) les trames non numrotes (U Unnumbered)
Elles se distinguent par leur champcommande
15/12/2011 Introduction aux Rseaux 73
ypes e rame amp omman e
I O N(S) P/F N(R)
S 1 0 Type P/F N(R)
U 1 1 M M P/F M M M
Le bit P/F signifie Poll/Final (Invitation mettre/Fin). Il est dit positionn s'il a la valeur 1. le bit positionn vaut
P si la trame est une commande .
L'mission d'une commande avec P=1 exige une rponseimmdiate (avec F = 1).
la rception d'une trame avec le bit P/F positionn, le bit vaut F si on attend une rponse une commande dj envoye et il vaut P si aucune commande n'a t envoye.
Dans les trames d'information data N(S) est le numro de la trame courante. N(R) est le numro de la trame d'information attendue ; il
acquitte les trames de numro infrieur N(R).
15/12/2011 Introduction aux Rseaux 74
Trame dinformation (I) La trame I permet deffectuer le transfert de linformation.
Utilise le "piggybacking".
N(S) : '
N(R) : numro de la prochaine trame d'information attendue (modulo 8 ou
128) acquitte toutes les trames de numros strictement infrieurs N(R) la perte d'un acquittement peut ainsi tre compense par le prochain
acquittement
Bit P/F :
dans une commande : demande de rponse immdiate dans une rponse : rponse la demande de rponse immdiate
15/12/2011 Introduction aux Rseaux 75
Trame de supervision (S)
4 types de trames de supervision, codes dans le sous-champ Type du champ Commande commande ou rponse
RR ("Received & Ready") - 00 : acquittement confirme la rception des trames de donnes denumro < N(R) demande la transmission des trames suivantes
ece ve o ea y - : con r e e ux confirme la rception des trames de donnes de
numro
8/2/2019 Chapitre5-Liaison de donnes
20/25
Trame de supervision (S)
REJ ("Reject") - 01 : protection contre les erreurs confirme la rception des trames de donnes de
numro < N(R)
demande la retransmission des trames de numro N(R)
SREJ ("Selective Reject") - 11 : protection contreles erreurs confirme la rception des trames de donnes de
num ro < demande la retransmission de la trame de
numro=N(R) non-utilise par LAP-B
15/12/2011 Introduction aux Rseaux 77
Trames non numrotes
Toutes les autres trames ncessaires la gestion de laconnexion
-
Trame d'tablissement de la connexion (commande) : SABM ("Set asynchronous balanced mode") [11100] - en
format normal SABME ("Set asynchronous balanced mode extended") -
en format tendu
Trame de libration de la connexion (commande) : DISC ("Disconnection") [00010]
15/12/2011 Introduction aux Rseaux 78
Trames non-numrotes
Trame de confirmation (rponse) :
UA ("Unnumbered acknowledgment")[00110]
Trame de rcupration des erreurs (rponse):
FRMR ("Frame reject") [11000]
Trame d'indication de connexion libre
DM ("Disconnected mode") [10 001]
15/12/2011 Introduction aux Rseaux 79
Quelques variables des entits du protocole
Chaque entit tient jour les trois variables suivantes : V(S) = numro de la prochaine trame d'information mettre, V(R) = numro de la prochaine trame recevoir, DN(R) = numro du dernier acquittement reu.
Les constantes : T1 = dlai de garde au bout duquel une trame non acquitte est
rmise. T2 = temps maximal au bout duquel le rcepteur d'une trame
met une trame qui en accuse rception. N1 = taille maximum d'une trame.
N2 = nombre maximum de rmissions d'une mme trame.
W = largeur de la fentre.
15/12/2011 Introduction aux Rseaux 80
Procdure d mission d'une trame Procdure de rception d'une trame
8/2/2019 Chapitre5-Liaison de donnes
21/25
Procdure d mission d une trame
Emission d'une trame I : vrifier que V(S) < DN(R) + W N(S) V(S) et N(R) V(R) ; Mmoriser la trame; V S V S + 1 Armer le temporisateur (dlai de garde T1) associ la trame; Armer T2.
Emission d'une trame REJ : N(R) V(R) armer T2.
Emission d'une trame RR : N(R) V(R) armer T2.
15/12/2011 Introduction aux Rseaux 81
p
Sur rception d'une trame : Si la trame est invalide alors
la trame est ignore (si FCS incorrect) ou mission d'une trame FRMR(format incorrect).
sinon la trame est dcode
Sur rception d'une trame I : Si N(S) != V (R) alors
trame non-attendue (dsquence) mettre une trame REJ;
sinon /* N(S) = V(R) */ armement du temporisateur T2 (dlai d'acquittement) associ N(S);
V(R)V(R) + 1.
Si DN(R) =< N(R) < V(S) alors dsarmer les temporisateurs T1 des trames de n compris entre DN(R)
et N(R); DNR(R) N(R);
15/12/2011 Introduction aux Rseaux 82
Procdure de rception d'une trame
Sur rception d'une trame RR Si DN(R) =< N(R) < V(S) alors
dsarmer les temporisateurs T1 des trames de n comprisentre DN(R) et N(R);
DNR(R) N(R).
Sur rception d'une trame REJ Si DN(R) =< N(R) < V(S) alors
entre DN(R) et N(R);
DNR(R) N(R);
mettre les trames de numros compris entre N(R) et V(S) ( 5
RR(N(R),P/F)
RNR(N(R),P/F)
15/12/2011 Introduction aux Rseaux 88
I (4,0,)
I (5,0,)
Scnario de transfert de donnestransfert bidirectionnel des donnes
Scnario de transfert de donnestransfert avec perte
8/2/2019 Chapitre5-Liaison de donnes
23/25
transfert bidirectionnel des donnes
SABM,PW > 5
,
I (0,0,) I (0,0,)
I (1,1,)
I (2,1,)
I (3,1,P)I 1 3
15/12/2011 89
I (4,2,) I (2,4,F)
I (5,3,)
Introduction aux Rseaux
transfert avec perte
SABM,PW > 5
,
I (0,0,)I (1,0,)I (2,0,)I (3,0,)
REJ(1,)I (1,0,)
15/12/2011 90
, ,I (3,0,)
Introduction aux Rseaux
Scnario de transfert de donnestransfert avec contrle de flux
SABM,PW > 5
,
I (0,0,)I (1,0,)I (2,0,)I (3,0,)
RNR(3,)
Fentreouverte
Fentre
15/12/2011 91
I (3,0,)I (4,0,)
RR(3,)
ferme
Fentreouverte
Introduction aux Rseaux
EFFICACIT DES PROTOCOLES DE
LIAISONS DE DONNES
15/12/2011 Introduction aux Rseaux 92
Context Classification des protocoles de liaisons de donnes
8/2/2019 Chapitre5-Liaison de donnes
24/25
Protocole de liaison de donnes entre deux stations (liaison point point)
Chaque trame est numrote
Chaque acquittement porte le numro de la prochaine trame attendue
Lacquittement est une trame RR (Receiver Ready)
On ne considre que les transmissions de donnes dans un sens et lesacquittements dans le sens oppos
Second calcul o on tient compte des erreurs
15/12/2011 Introduction aux Rseaux 93
Trois stratgies possibles: Send and Wait / Go back N / SelectiveRepeat ou Selective Reject
en an a t appe auss top an a t La station envoie une trame puis attend un acquittement Pas danticipation
Go back N La station envoie plusieurs trames successives sans attendre
lacquittement de la premire trame (fentre danticipation) En cas derreur sur la N ime trame, toutes les trames de uis la Nime
sont retransmises
Selective Repeat ou Selective Reject Anticipation + seules les trames errones sont retransmises
15/12/2011 Introduction aux Rseaux 94
Principe du Send-and-Wait (dtaill)
ttrame : dure de transmission dune trame tpropag : dlai de propagation du signal ttrait : dlai de traitement ngligeable
15/12/2011 Introduction aux Rseaux 95
tacq : dure de transmission dun acquittement ngligeable Dure totale doccupation du support de transmission pour
transmettre la trame :Tt = ttrame + 2 tpropag + 2 ttrait + tacq
Efficacit du Send-and-Wait (simplifi)
Il est commode de raisonner en dure normalise : Dure de trame : 1 Dlai de propagation du signal a = tpropag / ttrame Dure totale doccupation : Tt ~ 1 + 2a
Efficacit U du protocole = Dure utile / Dure totale
USW = 1/ (1 + 2a)
15/12/2011 Introduction aux Rseaux 96
Efficacit de lanticipation en labsence derreursEfficacit des protocoles de liaison en prsence
derreurs
8/2/2019 Chapitre5-Liaison de donnes
25/25
Taille N de la fentre danticipation (=dure normalise) : nombre detrames quon peut mettre sans attente dacquittement
Si N > 1+2a (dans lexemple la trame 1 est envoy avant larrive de RR1) alors pas de perte de temps U = 1
Si N < 1+2a alors Uant = N / (1 + 2a)
Dure moyenne de transmission dune trame : (1+2a)/N
15/12/2011 Introduction aux Rseaux 97
d erreurs
Hypothses Les erreurs sont isoles (faibles probabilits davoir deux
erreurs successives)
Le canal de retour est parfait: pas derreur sur lesacquittements
Temporisation dattente maximale dun acquittementdimensionne au plus juste (pour le Send & Wait)
On note p la probabilit derreur sur une trame
On raisonne en dure normalise
15/12/2011 Introduction aux Rseaux 98
Efficacit du Stop-and-Wait avec erreurs
Probabilit de transmettre au bout de k essais (k-1 chec puis 1 succs):pk-1 (1-p)
En moyenne on a : k. pk-1(1-p) =1 /(1-p) essais
ur e u e :
Dure total : (1+2a)*(1/(1-p)) = (1-p)/(1+ 2a)
USW = (1-p) / (1 + 2a) USW = (1-p)USW
15/12/2011 Introduction aux Rseaux 99