Chapitre 3 Couche Liaison

8/3/2019 Chapitre 3 Couche Liaison

http://slidepdf.com/reader/full/chapitre-3-couche-liaison 1/78

Cours Introduction aux réseaux

Ecole Nationale des Sciences de l’informatique (ENSI)

Université de la Manouba

La couche liaison de données

Salma BOURBIA II1 – 2010 / 2011

1



Introduction

Réseau Réseau

Liaison de Liaison deTrames

Paquets

données

physiquephysique

données

bits

Signaux

2



Introduction fonctions de la couche liaison

Fournir des services à la couche 3 Regroupement des bits venant de la couche physique en des

trames

ssurer e contr e erreurs Assurer le contrôle de flux pour régulariser le volume des

données échangées entre source et destination

Assure des fonctions de gestion de la liaison

3



1. Les services fournis à la couche réseau Transmettre des données de la couche réseau d’une machine

source vers la couche réseau d’une machine destinatrice

765

765

765

765

Deux processus de la couche liaison communiquent parl’intermédiaire d’un protocole de liaison

321

321

Chemin virtuel 321

321

Chemin réel

4



1. Les services fournis à la couche réseau Les services offerts par la couche liaison

Service sans connexion et sans acquittement Service sans connexion et avec acquittement

Service orienté connexion

5



1.1 Le service sans connexion et sans

acquittement La machine source envoie des trames à la machine

destination sans recevoir de cette dernière des

acquittements Pas de connexion établie au préalable

Aucun moyen de traiter le problème de perte de trames

Service convenable si: Le taux d’erreurs est faible

La correction des erreurs est prévue dans les couches

supérieures Le trafic est en temps réel (exemple la parole)

6



1.1 Le service sans connexion et sans

acquittement

émetteur Récepteur

Trame 1

t t

rame

7



1.2 Le service sans connexion et avec

acquittement Service plus fiable

Pas d’établissement de connexion

L’émetteur sait pour chaque trame si elle a été correctement

reçue

Si trame n’a pas été acquittée pendant un intervalle de temps,

l’émetteur peut la ré-envoyer de nouveau

8



1.2 Le service sans connexion et avec

acquittement

émetteur Récepteur

Trame 1

t t

Acquittement de la trame 1

9



1.3. Le service avec connexion Établissement d’une connexion entre les machines source

et destination avant tout envoie de données

Chaque trame envoyée sur la connexion est numérotéeet la couche liaison garantit que chaque trame envoyéeest reçue une fois et que toutes les trames sont reçues

ans or re mission Trois phases dans un service à connexion

Etablissement de la connexion

Transmission des données Libération de la connexion

10



1.3. Le service avec connexion Etablissement de la connexion

Initialiser des deux côtés un certain nombre de paramètres

Les compteurs qui servent à déterminer les trames qui ont été reçuescorrectement et celles qu’il faut retransmettre

ransm ss on es onn es

Fin de la connexion

Libérer les variables et les ressources utilisées au cours de latransmission

11



1.4 Les primitives de services La communication entre les couches réseau et liaison de

données se fait par les primitives de services Primitive Demande

Utilisée par la couche réseau pour demander à la couche liaison deréaliser une tâche Établir une connexion Envoyer une trame

Permet d’informer la couche réseau qu’un évènement est survenu Une demande de connexion provenant d’une machine Une demande de libération de la connexion Arrivée d’une trame

Primitive Réponse Utilisée par la couche réseau de la machine de destination pour répondre

à une primitive d’indication Primitive Confirmation

Permet de savoir si une demande a été exécutée avec succès

12







2.1 Format général d’une trame

15



2.2 délimiteurs de trames

Méthodes Comptage de caractères Utilisation des caractères spéciaux

Utilisation des fanions

Violation du codage utilisé dans la couche physique

16



2.2 délimiteurs de trames Méthode du comptage des caractères

Utiliser un champ dans l’entête de la trame qui indique le

nombre de caractères qu’elle contient Lorsque la couche liaison à la réception lit ce champ elle

connait le nombre de caractères de la trame

Problème de synchronisation après une erreur de transmissionaffectant le compteur de caractère

5 1 2 3 4 5 6 7 8 9 8 0 1 2 3 4 5 6

Trame 1 Trame 2 Trame 3

Compteur de caractère

17



2.2 délimiteurs de trames Méthode des caractères spéciaux

Délimiter chaque trame par les séquences de caractères DLE

STX et DLE ETX. DLE STX (Data Link Escape Start of TeXt)

Placé au début de la trame

Placé en fin de trame

Si la station de destination perd la synchronisation, il lui suffitde chercher les séquences DLE STX et DLE ETX pour

retrouver la délimitation des trames Les caractères DLE dans les données sont dédoublés

Caractères de transparence

18



2.2 délimiteurs de trames Méthode des fanions

Le fanion est le délimiteur (une séquence de bits)

01111110 Pour éviter l’ambigüité, un 0 est ajouté par l’émetteur après 5bits consécutifs à 1 dans les données, ce bit est appelé bit detransparence

19



2.2 délimiteurs de trames Méthode de violation du codage en couche physique

Utiliser des séquences invalides dans le codage du support

physique pour délimiter les trames

Exemple dans le codage de Manchester’

impulsion positive suivie d’une impulsion positive)

20



3. Détection et correction des erreurs Problème d’erreurs

La porteuse est souvent affectée par du bruit Modification ou perte des données pendant le transport

Sources d’erreurs Bruit sur la ligne

interférence électromagnétique Dia honie

Bruit thermique,…

Les stratégies de protection contre les erreurs se divisent en deuxcatégories Les techniques de détection des erreurs

Se rendre compte de la modification ou de données à l’arrivée des trames Les techniques de correction des erreurs

Corriger à l’arrivée des trames Correction Ré-envoyer les trames erronées ou perdus retransmission

21



3. Détection et correction des erreurs Mot de code et distance de Hamming

Deux stratégies possibles dans la gestion des erreurs

Ajouter dans les blocs de données suffisamment de redondances pourque le récepteur soit capable de restituer les données d’origines àartir des données re ues Utilisation des codes correcteurs

d’erreurs

Ajouter de la redondance dans les données à transmettre afin que lerécepteur puisse détecter les erreurs (non de les corriger) et de

demander la retransmission des données erronées utilisationdes codes détecteurs d’erreurs

22



3. Détection et correction des erreurs Mot de code et distance de Hamming

Une trame est formée de m bits de données r bits de contrôle n=m+r : longueur de la trame L’ensemble des n bits s’appelle mot de code

Etant donné deux mots de code, le nombre de bits dedifférence entre eux s’appelle distance de Hamming

À partir de l’ensemble de tous les mots de code, la distanceminimale entre deux mots de code s’appelle distance deHamming du code complet

23



3.1 Codes de détection d’erreursCode de contrôle de parité

Ajouter aux bits de données un bit de parité

Le choix du bit se fait de façon que le nombre de bits1dans le mot de code soit pair (ou impair)

Utilisé seulement our détecter les erreurs sim les

(affectant une seule position) Exemple

Données 1010001

Mot codé : (pair) 10100011(impair) 10100010

24



3.1 Codes de détection d’erreursCode de redondance cyclique (CRC: Cyclic

Redundancy Code)

Appelé aussi code polynomial On considère que les bits sont les coefficients d’un

polynôme qui prennent deux valeurs 0 ou 1

25

Un bloc de k bits est vu comme la série des coefficientsd’un polynôme (de degré k) comprenant des termesallant de à

Exemple La séquence 110001 représente le polynôme

1k x

+ 0 x

5 41 x x+ +



3.1 Codes de détection d’erreurs

Chaque mot de code est un multiple d’un polynôme

générateur Un polynôme générateur G est fourni, de degré n qui

détermine le nombre de bits de contrôle

26

L’émetteur et le récepteur doivent se mettre d’accordauparavant sur le choix du polynôme G(x)

Le bit de poids le plus fort et le bit de poids le plus faible dupolynôme générateur sont égaux à 1



3.1 Codes de détection d’erreurs Principe de détection

La trame envoyée = (données, bits de contrôle) À la réception, le récepteur divise la trame par le polynôme G(x), si

le reste obtenu est non nul, on détecte une erreur de transmission

Algorithme de calcul des bits de contrôle

27

oc envoyer e m ts Soit n le degré du générateur G(x) Ajouter n bits à 0 après le bit de poids le plus faible du bloc, le bloc

devient de taille n+m Diviser le polynôme (correspondant au bloc de données) par le

générateur Soustraire le reste de cette division du bloc initial (XOR) le résultat

obtenu correspond à ce qui est transmis



3.1 Codes de détection d’erreurs Exemple

Bloc : 110101

Ajout de bits 0 : 11010100

28

Trame émise : 11010111



4. Les protocoles élémentaires

Réseau Réseau

Liaison de Liaison de

29

données

physiquephysique

données

Emetteur Récepteur



4.1 Protocole 1 : protocole utopique

(irréaliste) Suppositions

Les données ne sont transmises que dans un seul sens Les couches réseau côté émetteur et récepteur sont toujours

prêtes à émettre et à recevoir des paquets

30

e temps e ca cu est gnor

Une infinité de mémoire tampon pour stocker les trames

Le canal de communication est parfait : aucune trame n’esterronée ni perdue




(irréaliste) Procédure de l’émetteur

L’émetteur réalise une boucle infinie qui consiste à émettre des

données aussi vite que possible sur la ligne

Répéter

31

eman er un paque e a couc e r seau

Construire la trame Envoyer la trame vers la couche physique




(irréaliste) Procédure à la réception

Répéter Initialement le récepteur attend que quelque chose arrive

Il enlève une trame venant d’arriver

32

a partie e a trame correspon ant au c amp in o est passée à a

couche réseau Attendre le prochain évènement



4.2 Protocole 2 : « Envoyer et attendre » Suppositions

Le canal est parfait

Les données circulent dans un seul sens Pas d’infinité de mémoire tampon pour stocker les trames

dans la couche liaison de la machine réceptrice

33

rouver une man re emp c er metteur envoyer esdonnées plus rapidement que le récepteur ne peut les traiter

Il ne faut pas que l’émetteur envoie une trame avant que lerécepteur ne réalise une acquisition, sinon celle-ci sera écrasée





4.2 Protocole 2 : « Envoyer et attendre » Procédure à l’émission

Répéter Prendre un paquet de la couche réseau

Construire la trame

35

nvoyer a trame à a couc e p ysique

Attendre un acquittement du récepteur



4.2 Protocole 2 : « Envoyer et attendre »

Procédure à la réception

Répéter Attendre l’arrivée d’une trame

Prendre la trame de la couche physique

36

Envoyer un acquittement à l’émetteur



4.3 Protocole 3 : pour un canal bruité

Suppositions Le canal de communication n’est pas parfait

Des trames envoyées peuvent être erronées ou perdues Il est possible de détecter les trames endommagées

Situation à résoudre

37

La perte de trame peut aussi toucher les trames d’acquittement ,l’acquittement n’arrive jamais à l’émetteur

L’émetteur croyant que sa trame envoyée n’est jamais parvenue à laréception, il la retransmet encore une fois

Cette trame dupliquée arrive également à la couche liaison dedestination et est encore une fois transmis à la couche réseau

problème de duplication






Procédure de l’émetteur Initialisation

Initialiser le numéro de la trame à envoyer

Charger le premier paquet de la couche réseau Répéter

Construire la trame

39

ns rer e num ro e s quence ans a rame

Envoyer la trame vers la couche physique Attendre un évènement Arrivée d’un acquittement Expiration du temporisateur

Si l’évènement est l’arrivée d’un acquittement Charger un nouveau paquet de la couche réseau Incrémenter le numéro de la prochaine trame à envoyer

Si l’évènement est (temporisateur expire ou erreur de trame) Retransmettre la trame de nouveau et ne pas changer le numéro de séquence




Procédure du récepteur Initialisation

Initialiser le numéro de trame attendue à 0 Répéter

Attendre un évènement’

40

Erreur Si une trame arrive (trame correcte) Prendre la trame de la couche physique

Si le numéro de séquence de cette trame est le numéro de trame attendue

Envoyer la partie info de trame à la couche réseau Incrémenter le numéro de la trame attendue

Envoyer un acquittement à l’émetteur



5. Les protocoles avec fenêtre d’anticipation

Dans les protocoles précédents, les données ne circulentque dans un seul sens

Nécessité d’adopter des liaisons en duplex Solution

Utiliser le même circuit pour transmettre les trames dans les

41

deux directions Le champ « genre » de l’entête de la trame permet d’indiquer

s’il s’agit d’une trame de données ou d’une tramed’acquittement




Technique de piggybacking

Lorsqu’une trame de données arrive, le récepteur ne va plus envoyerdirectement une trame d’acquittement séparée mais il attend que lacouche réseau lui fournit le paquet suivant

L’acquittement est joint à la trame de donnée émise

42

En utilisant le champ ack de l’entête de la trame

Retarder légèrement l’envoie d’un acquittement afin d’attendre la trame dedonnées suivante

Intérêts Meilleure utilisation de la bande passante L’utilisation du champ ack ne coûte que quelques bits alors que l’envoie d’une

trame séparée nécessite un entête, un acquittement et une somme de contrôle




Spécificités d’un protocole à fenêtre d’anticipation

Dans un tel protocole, les trames émises possèdent un numérode séquence variant de 0 à une valeur maximale

Cette valeur maximale est de la forme (le numéro est2 1n

−

43

co sur n ts

À chaque instant l’émetteur détient la liste des numéros deséquence des trames qu’il peut envoyer

Fenêtre d’émission

Fenêtre définie par la liste des numéros de séquence des tramesautorisées à être émises






Les trames doivent être stockées pour une éventuelle retransmission L’émetteur doit disposer assez de mémoires tampon pour stocker les

trames non encore acquittées

Si la taille de la fenêtre atteint son maximum, alors la couche liaison’

45

des mémoires tampon se libèrent




Fonctionnement à la réception

La couche liaison accepte les trames dont le numéro de séquence se

trouve à l’intérieur de la fenêtre de réception

Toute trame à l’extérieure de la fenêtre est rejetée

46

Lorsque la couche liaison du récepteur reçoit une trame dont lenuméro de séquence est égale à la borne inférieure de la fenêtred’anticipation, elle la transmet à la couche réseau, envoie unacquittement à l’émetteur et augmente sa fenêtre de 1

5 1 Protocole à fenêtre d’anticipation de



5.1 Protocole à fenêtre d anticipation de

largeur 1

Séq ACK Data

Trame à envoyer

47

Numéro deséquence de latrame envoyée

La trameacquittée

Donnéesenvoyées

Les numéros peuvent être 0 ou 1

5.1 Protocole à fenêtre d’anticipation de




largeur 1

48





largeur n

Manque d’efficacité dans le cas d’une fenêtre de taille 1

Exemple On suppose que le débit d’un canal est 50bps

Délai de propagation d’aller retour 500 ms

49

ai e e a trame its

À t=0, l’émetteur commence à envoyer une première trame À t=20 ms, la trame est complètement émise (temps de transmission)

À t=270 ms, la trame arrive à destination (20 + 250)

La trame d’acquittement parvient à l’émetteur à t=520 ms (270+250),en supposant que la trame d’acquittement est très courte

L’émetteur se trouve bloqué (500/520 = 96 % du temps)




2 p

largeur n

manque d’efficacité ceci est dû au fait que l’émetteur attend un acquittement avant d’émettre

pour améliorer l’efficacité, l’émetteur pourra envoyer plusieurstrames d’une façon continue pendant un temps égal au délai de

50

propaga on a er re our

Autoriser l’émetteur à envoyer w trames (w taille de la fenêtred’anticipation)




p

largeur n

Principe : Dans l’exemple précédant

La taille de la fenêtre est 26

L’émetteur émet la trame 0 et continue sans s’arrêter, dès qu’il finit’

51

acquittement (Ack) de la trame 0, ensuite les acquittementscontinuent à arriver autorisant ainsi l’émetteur à envoyer

technique du pipelining

Enchaîner les trames envoyées pour occuper la ligne pendant le délai depropagation d’aller retour




p

largeur n

Situation de trame erronée

Si une trame située au milieu de la série de trames envoyéesest perdue ou erronée

52

Un certain nombre de trames correctes vont parvenir aurécepteur avant que celui-ci ne se rend compte qu’une erreurde transmission s’est produite

Deux stratégies possibles, sachant que la couche liaison dedonnées doit passer les paquets à la couche réseau dansl’ordre de leur envoie :




p

largeur n

Stratégie 1 : Rejeter toutes les trames qui suivent la trame erronée en n’envoyant pas

d’acquittements

Stratégie 2 Effectuer un rejet sélectif : la couche liaison de destination stocke toutes

les trames correctes arrivées après la trame erronée.’ ’ ’

53

,

retransmet la trame erronée et une partie des trames suivantes Si cette seconde transmission réussit, la couche liaison du récepteurdispose de trames correctes stockées, elle les réordonne et les remet à lacouche réseau

La couche liaison de destination envoie ensuite un acquittement portant le

numéro le plus élevé stratégie qui nécessite plusieurs mémoires tampon si la largeur de lafenêtre est grande




largeur n

exemple de la stratégie 1 (taille de la fenêtre w=26)

54




largeur n

Exemple de la stratégie 2

55



6. Protocole à rejet sélectif

Principe Les trames qui suivent une trame perdue ne sont jamais

rejetées

L’émetteur et le récepteur disposent chacun d’une fenêtre qui

56

Fenêtre de l’émetteur de taille variant entre 0 et valeur maximale denuméro de séquence

Fenêtre du récepteur de taille fixe égale à la valeur maximale denuméro de séquence




Lorsqu’une trame arrive, le récepteur vérifie si le numérode cette trame se trouve dans sa fenêtre et la stocke La couche liaison de données doit livrer cette trame à la

couche réseau dès qu’il reçoit et livre toutes les trames dont lenuméro de séquence est inférieur

57

Le récepteur est autorisé à recevoir des trames dans ledésordre mais les paquets seront réordonnés avant d’êtrelivré à la couche réseau

6 P l à j él if




À chaque trame émise est associé un temporisateur,lorsque ce dernier expire on ne retransmet que la tramequi lui est associé.

Le récepteur doit avoir un nombre de mémoires tamponsnécessaire égale à la taille de la fenêtre

58

Le nombre de temporisateurs utilisés est égale à la taillede la fenêtre À chaque case mémoire est associé un temporisateur, s’il

s’expire, le contenu de cette case est directement retransmis

6 P t l à j t él tif




Lorsqu’une trame arrive à destination, le récepteurn’envoie pas directement l’acquittement mais il le joint àla prochaine trame émise

Le récepteur met en place un temporisateur auxiliaire, si ce’

59

empor sa eur exp re e que e r cep eur n a aucune rame e

donnée à envoyer, il envoie un acquittement séparé Éviter les situations de blocage dues à des trafics unidirectionnels

6 P t l à j t él tif




Traitement des erreurs

Le récepteur peut envoyer un acquittement négatif (NAK) àl’émetteur : S’il suspecte l’existence d’une erreur dans la trame reçue

’

60

perdue)

7. Le protocole HDLC (High level Data Link

C t l)



Control)

Historique 60 : BSC (“Binary synchronous communication”) – IBM

Unité de transmission est le caractère

70 : SDLC (Synchronous Data Link Control) – IBM Unité de transmission est la trame

’

61

-

Control Procedure) 76 : HDLC (High-level Data Link Control) de

Normalisation de SDLC par l’ISO

80 : adapté pour l’accès au réseau numérique de données LAP-B (“Link access procedure-balanced”)

Normalisé : CCITT X25.2 et ISO 7776


C t l)



Control)

Format général d’une trame HDLC

8 bits 8 bits 8 bits 16 bits 8 bits

62

données ContrôleCommandeAdresse01111110 01111110


C t l)



Control)

Format général d’une trame HDLC Champ adresse

Sert à identifier un terminal particulier sur des lignes multipoints

Sert à distinguer les commandes des contrôles sur des lignes point àpoint

Champ commande

63

Utilisé pour les numéros de séquence, les acquittements

Champ données Peut contenir n’importe quelle information Longueur du champ est arbitraire

Champ contrôle Obtenue par code correcteur d’erreur CRC

Fanions Délimiteurs de trame


Control)



Control)

Les types de trames Trames d’information (I Information)

Trames de supervision (S Supervisory)

Trames non numérotées (U Unnumbered)

8 bits 8 bits 8 bits 16 bits 8 bits

64

données ContrôleCommandeAdresseFanion Fanion

N(S)0 P/F N(R) Trame d’information (données)

type1 P/F N(R)0 Trame de supervision

type1 P/F N(R)1 Trame non numérotée

1 3 1 3


Control)



Control)

Les trames d’information

Trames qui acheminent des données

N(S) : numéro de séquence de la trame d’information

N(R) : numéro de la prochaine trame d’information attendue acquitte toutes les trames de numéros strictement inférieurs à N(R)

65

Mode normal (non équilibré / maître esclave / primaire secondaire) Quand un ordinateur interroge plusieurs terminaux

P indique que l’ordinateur invite un terminal à envoyer ses données

La dernière trame envoyée met ce bit à F

Mode équilibré Bit utilisé pour obliger le correspondant à envoyer immédiatement une trame

de supervision sans attente de trame d’information en retour


Control)



Control)

Les trames de supervision 4 types de trames de supervision, codées dans le sous-champ Type du champ

Commande.

RR (“Received & Ready”) trame d’acquittement Prêt à recevoir

Indique la prochaine trame attendue

66

ece ve ot ea y

Non prêt à recevoir Réaliser l’acquittement de toutes les trames jusqu’à N(R)-1, (comme RR) et

demande à l’émetteur de suspendre l’émission de trames pour un problèmepassager

Lorsque le problème est résolu, le récepteur envoie une trame RR ou de rejet ouautre trame de controle


Control)



Control)

Les trames de supervision

REJ (“Reject”) - acquittement négatif Indique une erreur de transmission détectée

Le champ N(R) contient le numéro de la première trame reçue erronée

’ -

67

ci

SREJ (“Selective Reject”) rejet sélectif

Sert à demander la retransmission de la trame spécifiée


Control)



Control)

Les trames non numérotées (Unnumbered)

Trames utilisées pour le contrôle et la gestion d’une connexion

Codées sur 5 bits mais les 32 types possibles ne sont pas tousutilisés

68

omman e sconnect

Déconnexion Permet à une machine d’annoncer qu’elle va être arrêtée

Commande SNRM (Set Normal Response mode) Permet à une machine d’annoncer sa remise en route

Commande SABM (Set Asynchronous Balanced mode) Permet d’initialiser la liaison et de placer les deux correspondants sur un pied

d’égalité


Control)



Control)


Trames d’établissement de la connexion : SNRM/SNRME (Set Normal Response Mode/extended)

SABM/ SABME (Set Asynchronous Balanced Mode/extended)

69

SARM/ SARME (Set Asynchronous Response mode/extended)

NRM est utilisé pour les liaisons de données multipoint ABM utilisé pour X25.2 efficace pour les liaisons point à point

full duplex

ARM est très rarement utilisé (situations où le secondaire peutavoir besoin d’initialiser certaines transmissions : le secondairea un peu plus de liberté)


Control)



Control)


Trame de libération de la connexion (Commande) : DISC(DISConnect : déconnexion) Trame de confirmation (Réponse) : UA (“Unnumbered

”

70

Trame de récupération des erreurs (R) : FRMR (“FRaMe Reject”):FCS correcte mais format incorrecte.

Trame d’indication de connexion libérée (R) : DM (“DisconnectedMode”) : connexion non établie

Trame d’information non numérotée : UI (“UnnumberedInformation”) données pour LD uniquement.

Exemples de scénarios




Etablissement d’uneconnexion en mode

71

qu r





72




p

73




p

Transfert de données unidirectionnel

74

argeur e en re




p

Transfert dedonnées

75

rec onne

Largeur defenêtre >5






p

Transfert de donnéesunidirectionnel

77

ransm ss on avecerreurs et rejetsélectif

Largeur de fenêtre >5




Contrôle de flux

78

Documents

Chapitre 3 Couche Liaison