3.

4 – Principes de transfert de données fiable

 Il est de la responsabilité d'un protocole de transfert de données fiable de mettre en œuvre

l'abstraction de service consistant à fournir un transfert de données fiable.
o Ce qui peut être difficile car les couches situées en dessous peuvent ne pas être fiables.
 Nous utiliserons le terme « paquet » plutôt que « segment » de couche transport.
 Nous ne discuterons que du transfert de données unidirectionnel, c'est-à-dire du transfert de
données du côté émetteur vers le côté récepteur. Pas de transfert de données bidirectionnel
(full duplex)

3.4.1 – Construire un protocole de transfert de données fiable

 Rdt1.0
o Le cas le plus simple : le canal sous-jacent est totalement fiable.
o Machines à états finis (FSM) séparées pour l'expéditeur et le destinataire
 Définit le fonctionnement de l'expéditeur
 Définit le fonctionnement du récepteur

o Les flèches dans la description du FSM indiquent la transition du protocole d'un état à
un autre.
o L'événement provoquant la transition est affiché au-dessus de la ligne horizontale
indiquant la transition, et les actions entreprises lorsque l'événement se produit sont
affichées sous la ligne horizontale.
o Lorsqu'aucune action n'est entreprise sur un événement, ou qu'aucun événement ne se
produit et qu'une action est entreprise, utilisez le symbole au-dessous ou au-dessus de
l'horizontale, respectivement, pour désigner explicitement l'absence d'action ou même.
L'état initial du FSM est indiqué par la flèche en pointillés.
o Du côté de l'expéditeur :
 Accepte les données de la couche supérieure via la fonction rdt_send(data)
 Via make_pkt(data) qui crée un paquet contenant les données via la
fonction
o Le côté réception :
 Reçoit un paquet du canal sous-jacent via la fonction rdt_rcv(packet)
 Supprime les données vi Extraire (paquet, données)
 Transmet les données jusqu'à la couche supérieure via la fonction
Deliver_data(data)
o Étant donné que le canal est parfaitement fiable, le côté récepteur n’a pas besoin de
fournir de retour à l’expéditeur puisque rien ne peut se passer mal.
 Rdt2.0

o Un cas plus réaliste : les paquets peuvent être corrompus (erreurs de bits) (normalement
dans la couche physique lors de leur transmission, de leur propagation ou de leur mise
en mémoire tampon)
o Les protocoles de transfert de données fiables basés sur la retransmission où des
accusés de réception positifs et négatifs sont utilisés sont connus sous le nom de
protocoles ARQ (Automatic Repeat reQuest).
 Détection d’erreur :
 Un mécanisme nécessaire pour permettre au récepteur de détecter quand
des erreurs de bits se sont produites.
 Commentaires du récepteur :
 Le récepteur envoie des réponses d'accusé de réception positives ACK et
négatives NAK (un bit de longueur, 1 ou 0) pour fournir un retour
d'information à l'expéditeur.
 Retransmission :
 Un paquet reçu par erreur chez le destinataire sera transmis par
l'expéditeur.
o Le côté envoi a deux états :
 État le plus à gauche : attente que les données soient transmises depuis la
couche supérieure. Lorsque l'événement rdt_send(data) se produit, l'expéditeur
crée un paquet (sndpkt) contenant les données et une somme de contrôle. Avant
de l'envoyer avec udt_send(sndpkt)
 État le plus à droite : en attente d’ACK ou de NAK du récepteur.
 S'il reçoit un ACK, il sait que le paquet le plus récemment transmis a été
reçu correctement. Le protocole attend donc un nouveau paquet de la
couche supérieure.
 S'il reçoit un NAK, il sait qu'il doit retransmettre et attendre un nouveau
ACK ou NAK.
 Il ne peut pas obtenir un nouveau paquet de la couche supérieure en attendant un
ACK ou un NACK. Il ne peut donc pas envoyer de nouvelles données avant
d'obtenir un ACK
 Cela fait de Rdt2.0 un protocole d'arrêt et d'attente
o Le côté récepteur a un seul état :
 Il répond par un ACK ou un NAK lorsque le paquet arrive selon qu'il est
corrompu ou non.
 o Ce protocole a aussi ses défauts car les ACK ou NAK peuvent également être
corrompus.
 Ce problème peut être résolu en retransmettant le paquet si l'ACK ou le NAK est
tronqué. Ce qui introduit des paquets en double que nous résolvons en
introduisant un champ de numéro de séquence dans le paquet.

 Rdt2.1


o La version corrigée de Rdt2.0
o Deux fois plus d'états que cet état de protocole doivent refléter si le paquet en cours
d'envoi ou attendu doit avoir un numéro de séquence de 0 ou 1.
o Utilise à la fois des accusés de réception positifs et négatifs du destinataire à
l'expéditeur. Lorsqu'un paquet dans le désordre est reçu, le récepteur envoie un accusé
de réception positif pour le paquet qu'il a reçu. Lorsqu'un paquet corrompu est reçu, le
destinataire envoie un accusé de réception négatif.
 Rdt2.2

o Nous pouvons accomplir le même effet que NAK si, au lieu d'envoyer NAK, nous
envoyons un ACK pour le dernier paquet correctement reçu.
 Un expéditeur qui reçoit deux ACK pour le même paquet sait que le destinataire
n'a pas reçu correctement le paquet qui suit le paquet qui est accusé de réception
deux fois.
 Ainsi, le récepteur doit maintenant inclure le numéro de séquence du paquet en
cours d'accusé de réception par un message ACK, et l'expéditeur doit vérifier le
numéro de séquence du paquet en cours d'accusé de réception.
 Rdt3.0
o Supposons maintenant que le canal puisse également perdre des paquets. Cela nous
pose deux nouveaux problèmes.
 Comment détecter la perte de paquets et que faire en cas de perte de paquets
o Il existe de nombreuses façons de résoudre le problème de perte de paquets, mais nous
laisserons la charge de la détection et de la récupération sur l'expéditeur.
o Supposons que l'expéditeur transmette un paquet de données et que ce paquet, ou
l'ACK du destinataire de ce paquet, soit perdu. Dans les deux cas, aucune réponse n’est
reçue de la part du destinataire par l’expéditeur. Si l'expéditeur est prêt à attendre
suffisamment longtemps pour être certain qu'un paquet a été perdu, il peut simplement
le retransmettre.
 Le temps d'attente est très difficile à estimer. Il doit s'agir au minimum du temps
aller-retour et du temps nécessaire au traitement du paquet, mais cela varie.
 Le protocole doit essayer de récupérer le plus rapidement possible et attendre le
délai maximum dans le pire des cas le ralentit
o Ainsi, l'approche adoptée consiste à utiliser un délai qui rend probable la perte du
paquet, mais qui n'est pas garanti.
 Cela permet d'envoyer des paquets dupliqués, mais Rdt2.2 gère déjà cela.
o La retransmission basée sur le temps nécessite un compte à rebours qui interrompt
l'expéditeur après l'expiration d'un délai donné. L'expéditeur doit être capable de :
 Démarrez le minuteur à chaque fois qu'un paquet est envoyé
 Répondre à une interruption de minuterie
 Arrêtez le chronomètre
o Étant donné que les numéros de séquence des paquets alternent entre 0 et 1, ce
protocole est parfois appelé protocole à bits alternés.
3.4.2 – Protocoles de transfert de données fiables par pipeline

 Rdt3.0 a de mauvaises performances, et c'est parce qu'il s'agit d'un protocole stop-and-wait.
 Prenons un exemple pour voir à quel point cela peut être grave :
o Supposons qu'il y ait un hôte sur la côte est et un autre sur la côte ouest et qu'il existe
une liaison R de 1 Gbit/s entre eux. Le RTT est de 30 ms et la taille du paquet L est de
1 000 octets par paquet.
o Le temps de transmission du paquet dans la liaison 1 Gbps est :
 $$d_{trans} = \frac{L}{R} = \frac{8000 \frac{Bits}{packet}}{10^9 bits/sec}$$
= 8 microsecondes
o Supposons que l'ACK soit si petit que nous ignorons leur temps de transmission et que
le récepteur peut envoyer l'ACK au moment où le dernier bit des paquets est présent. Le
paquet utilise $$t=\frac{RTT}{2}+\frac {L}{R} = 15,008 ms$$ pour voyager dans un
sens. Cela signifie que l'ACK revient à l'expéditeur à $$t = \frac{RTT}{2}+\frac{L}
{R} = 30,008 msec$$ Ce qui signifie que l'expéditeur n'était occupé que 0,008 s.
o Si nous définissons l'utilisation de l'expéditeur comme la fraction de temps pendant
laquelle l'expéditeur est réellement occupé à envoyer des bits dans le canal. Le stop-
and-wait a une utilisation plutôt lamentable des expéditeurs :
 $$U_{expéditeur} = \frac{\frac{L}{R}}{RTT + \frac{L}{R}} = \frac{0,008}
{30,008} = 0,00027$$
o Cela signifie que l'expéditeur a envoyé 1 000 octets en 30,0008 ms, soit seulement 267
Kbps sur une liaison à 1 Gbps.
 Nous voulons que l'expéditeur soit autorisé à envoyer plusieurs paquets sans attendre d'accusé
de réception. C'est ce qu'on appelle le pipeline :
o La plage de numéros de séquence doit être augmentée, car chaque paquet en transit doit
avoir un numéro de séquence unique et il peut y avoir plusieurs paquets en transit non
accusés de réception.
o Les côtés expéditeur et récepteur des protocoles peuvent avoir un tampon pour
plusieurs paquets. Au minimum, l'expéditeur devra mettre en mémoire tampon les
paquets qui ont été transmis mais qui n'ont pas encore été reconnus. La mise en
mémoire tampon des paquets correctement reçus peut également être nécessaire au
niveau du récepteur, comme indiqué ci-dessous.
o La plage de numéros de séquence nécessaire et les exigences de mise en mémoire
tampon dépendront de la manière dont un protocole de transfert de données répond aux
paquets perdus, corrompus et trop retardés. Deux approches de base en matière de
récupération d'erreur en pipeline peuvent être identifiées : Go-Back-N et répétition
sélective.

3.4.3 – Go-Back-N (GBN)

 L'expéditeur est autorisé à transmettre plusieurs paquets sans attendre un accusé de réception,
mais il est contraint de ne pas avoir plus d'un certain nombre maximum autorisé, N, de paquets
non accusés de réception dans le pipeline.
 Nous définissons base comme le numéro de séquence du paquet non reconnu le plus ancien
et nextseqnum comme le plus petit numéro de séquence inutilisé, puis quatre intervalles dans la
plage des numéros de séquence peuvent être identifiés.
o Les numéros de séquence dans l'intervalle [0,base-1] correspondent aux paquets déjà
transmis et accusés de réception.
o L'intervalle [base,nextseqnum-1] correspond aux paquets envoyés mais non encore
reconnus.
 o Les numéros de séquence dans l'intervalle [nextseqnum, base+N-1] peuvent être utilisés
pour les paquets qui peuvent être envoyés immédiatement, si les données arrivent de la
couche supérieure.
o Les numéros de séquence supérieurs ou égaux à Base+N ne peuvent pas être utilisés
tant qu'un paquet non reconnu actuellement dans le pipeline n'a pas été reconnu.
 Cette plage de numéros de séquence autorisés pour les paquets transmis mais non encore
reconnus peut être considérée comme une fenêtre de taille N (taille de la fenêtre/taille de la
fenêtre coulissante)
o Pendant que le protocole fonctionne, cette fenêtre glisse vers l'avant sur l'espace du
numéro de séquence.
o La raison pour laquelle nous avons une limite est due au contrôle de flux (contrôle de
congestion TCP)
 Le numéro de séquence d'un paquet est transporté dans un champ de longueur fixe dans l'en-
tête du paquet.
o Si K est le nombre de bits dans le champ du numéro de séquence du paquet, la plage du
numéro de séquence est donc $$[0.2^k-1]$$
o Avec une plage finie de numéros de séquence, toutes les arithmétiques impliquant des
numéros de séquence doivent alors être effectuées en utilisant l'arithmétique modulo $
$2^k$$.
 Nous faisons référence à un FSM où les côtés expéditeur et récepteur sont basés sur un
protocole GBN basé sur ACK, sans NAK, comme un FSM étendu car nous avons ajouté des
variables pour base et nextseqnum et ajouté des opérations de ces variables et des actions
conditionnelles impliquant ces variables.
 L'émetteur du GBN doit répondre à trois types d'événements :
o Invocation d'en haut
 Lorsque rdt_send() est appelé depuis le haut, l'expéditeur vérifie d'abord si la
fenêtre est pleine.
 S'il n'est pas plein, un paquet est créé et envoyé, et les variables sont mises à
jour de manière appropriée.
 Si la fenêtre est pleine, l'expéditeur renvoie simplement les données à la couche
supérieure, une indication implicite que la fenêtre est pleine.
 Dans un environnement réel, l'expéditeur aurait soit un tampon, soit une
synchronisation. Mécanisme qui permettrait à la couche supérieure de
l'appeler lorsque la fenêtre n'est pas pleine.
o Réception d'un ACK
 Un accusé de réception pour un paquet avec un numéro de séquence n sera
considéré comme un accusé de réception cumulatif, indiquant que tous les
paquets avec un numéro de séquence supérieur et incluant n ont été
correctement reçus au niveau du récepteur.
o Un événement de délai d'attente
 Comme dans un protocole d'arrêt et d'attente, une minuterie sera à nouveau
utilisée pour récupérer des données perdues ou des paquets d'accusé de
réception. En cas d'expiration du délai, l'expéditeur renvoie tous les paquets
précédemment envoyés mais qui n'ont pas encore été reconnus.
 Si un ACK est reçu mais qu'il y a encore des paquets supplémentaires transmis
mais pas encore reconnus, le temporisateur est redémarré. S'il n'y a aucun
paquet en attente non reconnu, le temporisateur est arrêté.
 Si un paquet avec le numéro de séquence n est reçu correctement et est en ordre, le récepteur
envoie un ACK pour le paquet n et transmet la partie données du paquet à la couche
supérieure. Dans tous les autres cas, le récepteur rejette le paquet et renvoie un ACK pour le
paquet dans l'ordre reçu le plus récemment.
 o Supprimer un paquet en panne peut sembler inutile, mais s'il devait le conserver, il
devrait le mettre en mémoire tampon, puis le livrer après les paquets avant qu'il ne soit
reçu. Si le paquet devait être perdu, l'expéditeur retransmettrait à la fois le paquet perdu
et celui mis en mémoire tampon. Éliminant ainsi le besoin d’un tampon.
o Ainsi, le récepteur doit uniquement garder une trace de la variable attendueqnum.
Tandis que l'expéditeur doit maintenir les limites supérieures et inférieures de ses
fenêtres et la position du nextseqnum.
 La mise en œuvre de ce protocole prendrait probablement la forme de diverses procédures
mettant en œuvre les actions à prendre en réponse aux différents événements pouvant survenir.
o Dans une telle programmation basée sur les événements, les différentes procédures
sont invoquées soit par d'autres procédures dans la pile de protocoles, soit à la suite
d'une interruption.

3.4.4 – Répétition sélective (SR)

 GBN souffre de problèmes de performances lorsque la taille de la fenêtre et le produit de

retard de bande passante sont tous deux importants, de nombreux paquets peuvent être dans le
pipeline. Une seule erreur de paquet peut ainsi amener GBN à retransmettre un grand nombre
de paquets, dont beaucoup inutilement.
o À mesure que la probabilité d’erreurs de canal augmente, le pipeline peut se remplir de
ces retransmissions inutiles.
 Les protocoles de répétition sélective évitent les retransmissions inutiles en demandant à
l'expéditeur de retransmettre uniquement les paquets suspectés d'avoir été reçus par erreur par
le destinataire.
o La retransmission individuelle selon les besoins nécessite que le récepteur accuse
individuellement un accusé de réception des paquets correctement reçus.
 Une fenêtre de taille N sera utilisée pour limiter les paquets non acquittés en attente, mais elle
contiendra désormais également certains paquets pour lesquels nous avons déjà reçu des ACK.
 Les paquets seront reconnus même s'ils sont en panne. Il doit donc mettre en mémoire tampon
les paquets dans le désordre jusqu'à ce qu'il reçoive les paquets manquants.
 Événements et actions de l'expéditeur SR :
o Données reçues d'en haut :
 Lorsque les données sont reçues d'en haut, il vérifie le prochain numéro de
séquence disponible pour le paquet. Si le numéro de séquence se trouve dans la
fenêtre de l'expéditeur, les données sont mises en paquets et envoyées ; sinon, il
est soit mis en mémoire tampon, soit renvoyé à la couche supérieure pour une
transmission ultérieure
o Temps mort:
 Les minuteries sont à nouveau utilisées pour se protéger contre la perte de
paquets. Cependant, chaque paquet doit désormais avoir son propre
temporisateur logique, puisqu'un seul paquet sera transmis à l'expiration du
délai.
o ACK reçu :
 Si un ACK est reçu, le SR le marquera comme reçu (s'il est dans la fenêtre). Si
le numéro de séquence est égal à send_base alors la base de fenêtre passera au
prochain paquet non accusé de réception. S'il se déplace dans une plage
contenant un paquet non transmis, il l'enverra.
 Événements et actions du récepteur SR :
o Le paquet avec le numéro de séquence dans [rcv_base, rcv_base+N-1] est correctement
reçu :
  Il tombe sous la fenêtre et un ACK est renvoyé. Si le paquet n'a pas été reçu
précédemment, il sera mis en mémoire tampon. Si le numéro de séquence était
égal à la base de la fenêtre de réception, alors ce paquet et tous les paquets
précédemment mis en mémoire tampon et numérotés consécutivement sont
transmis au système supérieur. La fenêtre est alors avancée du nombre de
paquets envoyés au système supérieur.
o Le paquet avec le numéro de séquence dans [rcv_base-N, rcv_base-1] ] est
correctement reçu :
 Un ACK doit être généré même s'il s'agit d'un paquet que le récepteur a
précédemment accusé de réception.
o Sinon:
 Ignorer le paquet
 Il est important que l'expéditeur envoie des ACK pour dupliquer les paquets car s'il n'y a pas
d'ACK pour la propagation du paquet send_base du récepteur à l'expéditeur, l'expéditeur finira
par retransmettre le paquet send_base, même s'il est clair que le récepteur l'a déjà reçu. Si le
destinataire n'accusait pas réception de ce paquet, les fenêtres de l'expéditeur n'avanceraient
jamais.
o Ceci est important car les fenêtres de l’expéditeur et du destinataire ne coïncideront pas
toujours.
 Le manque de synchronisation entre les fenêtres émetteur et récepteur a des conséquences
importantes :
o Supposons que la taille de la fenêtre soit 3.
o Disons que les paquets 0-2 sont reçus par le récepteur, la fenêtre est maintenant sur le
4ème, 5ème et 6ème paquet avec les numéros de séquence 3, 0, 1
o Scénario 1:
 Les ACK des trois premiers paquets sont perdus et l'expéditeur retransmet ces
paquets. Le récepteur reçoit ainsi ensuite un paquet de numéro de séquence 0,
copie du premier paquet envoyé.
o Scénario 2 :
 Les ACK des trois premiers paquets sont tous livrés correctement. L'émetteur
avance ainsi sa fenêtre et envoie les quatrième, cinquième et sixième paquets,
portant respectivement les numéros de séquence 3, 0, 1. Le paquet de numéro de
séquence 3 est perdu, mais le paquet de numéro de séquence 0 arrive, un paquet
contenant de nouvelles données.
o Ces deux scénarios sont identiques pour le récepteur. Il n'existe aucun moyen de
distinguer la transmission du premier paquet de la transmission originale du cinquième
paquet.
 C'est pourquoi la taille de la fenêtre doit être inférieure ou égale à la moitié
de la taille de l'espace des numéros de séquence pour les protocoles SR.
 Nous avons supposé que les paquets ne peuvent pas être réorganisés dans le canal entre
l'expéditeur et le destinataire. Cependant, cela peut arriver lorsque le canal est un réseau et non
des câbles physiques.
o Une manifestation de la réorganisation des paquets est que d'anciennes copies d'un
paquet avec un numéro de séquence ou d'accusé de réception de x peuvent apparaître,
même si ni la fenêtre de l'expéditeur ni celle du destinataire ne contiennent x.
o Un canal peut être considéré comme mettant essentiellement en mémoire tampon des
paquets et émettant spontanément ces paquets à tout moment. Ce qui pose problème car
les numéros de séquence peuvent être réutilisés.
o L'approche pour résoudre ce problème consiste à ne pas réutiliser un numéro de
séquence avant que l'expéditeur ne soit « sûr » que le paquet n'est plus dans le réseau.
o La durée de vie maximale actuelle est estimée à environ 3 minutes dans le protocole
TCP des réseaux à haut débit.