Upload
arion
View
33
Download
0
Embed Size (px)
DESCRIPTION
Chapitre 4. L’acquittement (acknowledgment). Auteur des transparents: L. Logrippo w3.uqo.ca/luigi. Protocoles. Procédures concernant la communication Afin que deux ou plusieurs parties puissent communiquer, ils doivent utiliser un protocole commun - PowerPoint PPT Presentation
Citation preview
1
Chapitre 4
L’acquittement(acknowledgment)
Auteur des transparents: L. Logrippow3.uqo.ca/luigi
INF6001 Chap 3 2
Protocoles
Procédures concernant la communicationAfin que deux ou plusieurs parties puissent
communiquer, ils doivent utiliser un protocole communP.ex. pour communiquer par la poste, il faut informer
les autres de votre adresse, il faut regarder dans la boîte aux lettres périodiquement, poster aux boîtes rouges, utiliser des enveloppes, des timbres, etc.
INF6001 Chap 3 3
Deux généraux qui doivent prendre une ville…
Seulement en agissant ensemble peuvent-ils gagner… Un général n’attaquera que s’il est certain que l’autre attaquera aussi
Le seul moyen de communication est un pigeon…
http://www.clipart-darktreasures.com
INF6001 Chap 3 4
Un dialogue sans espoir…
Général A envoie un message: attaquons à 6h demain Attaqueront-ils? Non, A attendra confirmation
Général B envoie une réponse: d’accord à 6h demain Attaqueront-ils? Non, B attendra confirmation
Général A répond encore: d’accord à 6 h demain Attaqueront-ils? Non, A attendra confirmation
Etc…
http://www.clipart-darktreasures.com
INF6001 Chap 3 5
Il n’y a pas de protocole pour résoudre ce problème!
Preuve (informelle): (v. notes de cours du Prof. Pelc pour une preuve plus générale)
Supposez qu’un protocole existe Il doit impliquer au moins un message Il doit être tel que si le dernier message est perdu, les
généraux attaquent Donc le dernier message ne serait pas nécessaire Enlevons le dernier message pour un protocole plus efficace Le même raisonnement s’applique inductivement à tout
message, y inclus le premier! Aucun message ne serait nécessaire
contradiction
INF6001 Chap 3 6
Erreurs résiduels Après analyse, on découvre que ce résultat s’applique à n’importe quel
protocole! Il n’est pas possible d’établir l’accord certain dans le cas de canaux avec perte
Un aspect fondamental de la preuve est que nous ne savons pas combien de fois le milieu va échouer Si nous savons que sûrement il y aura succès au moins 1 fois sur 10, alors l’envoi de
10 pigeons suffira Étant donné que normalement il est impossible d’établir ce type de borne, il
n’est pas possible d’établir la certitude globale dans les systèmes répartis N’importe la complexité du protocole et la fiabilité du milieu, il y a toujours la
possibilité d’erreurs résiduels On parle donc de taux d’erreur résiduel (residual error rate)
Il est vrai cependant que dans les supports de communication modernes (fibres optiques, etc.) la fiabilité est extrêmement élevée
Et nous avons aussi des applications pour lesquelles la fiabilité absolue n’est pas nécessaire Si un paquet est perdu dans la transmission de la parole, de la musique, d’une
image de télévision, l’usager pourrait ne pas s’en rendre compte
INF6001 Chap 3 7
Problèmes de sécurité
Considérez aussi la possibilité que le pigeon puisse être intercepté et remplacé par un autre pigeon avec un message différent…
INF6001 Chap 3 8
Fonctionnalité des acquittements
Dans les systèmes télématiques, les acquittements peuvent avoir deux fonctions différentes Simplement faire savoir que le message a été reçu
Surtout dans la couche liaison de données Répondre à la requête
Surtout dans la couche application
C’est la première fonction qui nous préoccupe en ce chapitre
INF6001 Chap 3 9
La détection d’erreurs dans les modèles à couche
Quelle couche est la plus appropriée pour la détection d’erreurs?
Dans l’ OSI, la détection d’erreurs se fait un peu partout dans les premières 4 couches surtout dans la couche 2: Liaison de données pas du tout après la couche Transport
Dans le TCP/IP, elle se fait à la couche TCP (Transport)Cependant en principe il n’y a pas de couche préférableChaque couche doit en quelque sorte se préoccuper d’erreurs à
son niveau Détectable p.ex. comme ‘réception non spécifiée’
Même dans les applications nous devons nous préoccuper de la possibilité d’erreurs P.ex. une application de base de données qui reçoit une requête dans
un format non valable
INF6001 Chap 3 10
Protocoles à trois étapes – Three-way handshake
Utilisé dans TCP, connexion et déconnexionEt dans un grand nombre d’autres protocoles
Invitation
Accept (ou non)
Confirm.
INF6001 Chap 3 11
Avec ré-essai
Chaque côté renvoie après un certain temps
Ici aussi, il n’y a pas certitude après l’envoi de conf.
Afin de chercher à la créer, on pourrait avoir une temporisation et boucle pour conf, ce qui demanderait une 2ème conf, etc.
! invit
? accept
tempor.
! conf
? invit
! accept
tempor.
? conf
Peut commencer à envoyer sans être certain….
INF6001 Chap 3 12
Le protocole du bit alterné (BA)
Le protocole BA fut le 1er protocole qui fut spécifié en utilisant la notion de modèle de transitions d’état Article de Bartlett et Scantlebury dans Comm. ACM May 1969, disponible à
partir de l’UQO sur http://portal.acm.org/portal.cfm Excellent et fameux article, 2 pages seulement! Parfois cité comme 1er article dans l’ingénierie des protocoles
BA est un des plus simples protocoles de liaison données possible, mais il Démontre les principes fondamentaux de tous les protocoles de liaison de
données Réussit à récupérer des erreurs de transmission
Dans certaines limites, nous verrons… Il a été utilisé dans un grand nombre d’études sur la validation des
protocoles
INF6001 Chap 3 13
Découvrons le protocole du bit alterné
Exigence: un protocole qui accepte une séquence de paquets de données et les remet à l’autre côté dans le même ordre
0
1
2
3
Message 0
1
2
3
Effet désiré: comment l’obtenir?
INF6001 Chap 3 14
Contrôle d’erreurs
Problème, le canal peut perdre des données
0
1
2
0
1
2
3
Le récepteur a perdu l’ordre des messages
INF6001 Chap 3 15
Compter les messages
Chaque message contient son numéro, afin que le récepteur sache quel message il vient de recevoir
Besoin de connexion: les deux côtés doivent initialiser une connexion, ce qui permet d’initialiser le comptage
Étant donné qu’il faut pas gaspiller les bits pour le comptage, essayons avec le plus petit compteur possible: 1 bit
INF6001 Chap 3 16
Utilisation du bit alterné
Le protocole commence le comptage à 0
Pour pouvoir reprendre, il faut donner au récepteur la possibilité de demander le renvoi du message perdu
0 Message 0
Message 1
2
3
bit=0
1
0
Attend 0, OK
Attend 1, reçoit 0Erreur
INF6001 Chap 3 17
Deux méthodes
Le récepteur peut envoyer un message NACK 0, signalant le fait que le message 0 n’a pas été reçu Cependant ce message pourra lui-même être perdu
Une solution équivalente est d’exiger un ACK pour chaque message reçu Qui peut lui aussi être perdu
ARRÊT ET ATTENTE: Stop and Wait Protocol L’émetteur envoie, attend acquittement Si l’acquittement arrive, continue avec proch. message Sinon (le message ou l’acquittement pourraient être perdus!) renvoie
message précédentProblème: combien de temps attendre
Solution: établir un temps sur la base du temps d’allée/retour du message et son acquittement (le double?)
Minuterie: positionner , annuler
INF6001 Chap 3 18
Arrêt et attente (stop-and-wait)
Cas normal
Message n Attend bit 0: accepté
OK
minuterie t annulée
D0
Ack
positionne minuterie t
t
t
n-1 messages déjà transmis, n pair
Message n+1
D1
positionne minuterie t
t
Etc.
INF6001 Chap 3 19
Perte de message dans arrêt-attente(si l’attente n’est pas assez longue)
Message n Attend bit 0: accepté
D0
D1
n-1 messages déjà transmis, n pair
Ack
Retransmet DO et pense que l’acquittement est pour le 2ème
D0
Ceci est l’acquittement du 2ème DO mais il paraît être pour D1
Ack
D0Ne sait pas si ce D0 est une retransmission du 1er ou s’il s’agit d’un nouveau message…
Etc.
INF6001 Chap 3 20
Protocole du bit alterné:Bit dans l’acquittement
Il faut donc que l’acquittement contienne l’identification du message reçu
Message n Attend bit 0: accepté
D0
D1
n-1 messages déjà transmis, n pair
A0
D0 acquitté
D0
Écarte ceci et il saura qu’il doit retransmettre D1
A0
D1OK
A1
INF6001 Chap 3 21
Protocole bit alterné: Arrêt et attente
Cas de perte de message (OK)
Message n
TemporisationDoit renvoyer n
B0
B0
Positionne Minuterie
n
n-1 messages déjà transmis, n impair
A0
INF6001 Chap 3 22
Protocole bit alterné: Arrêt et attente
Cas de perte d’acquittement (OK)
n
TemporisationDoit renvoyer n
D0
D0
Positionne Minuterie A0
Attend 1: écarté
n-1 messages déjà transmis, n pair
A0
D1
Continue d’envoyer l’acquittement du dernier msg bien reçu
INF6001 Chap 3 23
Protocole bit alterné: Arrêt et attente
Chevauchement de message! (OK)
n
TemporisationDoit renvoyer
D0
D0
Positionne Minuterie
n
Attend 1, reçoit 0ÉcarterA0
n-1 messages déjà transmis, n pair
INF6001 Chap 3 24
Protocole bit alterné: Arrêt et attente
Chevauchement d’ack! (OK)
TemporisationDoit renvoyer
D0
D0
Positionne Minuterie
Attend 1, écarter
A0
Attend ack de 0, OK
n+1D1
n+1
A1
n-1 messages déjà transmis, n pair
n
INF6001 Chap 3 25
Collision
Nous venons de voir un cas de collision, cad une situation où deux entités envoient des messages ‘en même temps’ (D0-A0)
Les collisions ne sont pas nécessairement des erreurs, cependant elles doivent être prises en considération dans la conception P.ex. deux entités qui demandent connexion ou déconnexion
indépendamment Deux données qui voyagent en direction opposée dans les
protocoles bi-directionnels
INF6001 Chap 3 26
Bit alterné unidirectionnel, diagramme de transition
Données de l’usager
!D0
To, ?A1
To: temporisation
A: Ack
?A0
Données de l’ usager
!D1
!D0
To, ?A0
!D1
?A1
?D1
!A1!A1
Données à usager
?D0
Données à usager
!A0
?D1
?D0
!A0
émetteur récepteur
1
2
3 4
5
6
7
8
1
2
3
4
5
6
7
8
INF6001 Chap 3 27
Usagers émetteur et recepteur
Donner message à l’émetteur
Prendre message du récepteur
INF6001 Chap 3 28
Architecture globale: 4 machines à états
Usager émetteur
Émetteur Récepteur
Usager récepteur
INF6001 Chap 3 29
Messages altérés - Erreurs
Nous n’avons pas considéré le cas de réception de messages altérés (messages avec erreur détectée)
L’hypothèse étant qu’un message altéré est comme un message non-reçu
Dans le diagramme de transition nous pourrions ajouter ce cas d’erreur aux transitions 3 7 et 6 8 dans l’émetteur 67 et 18 dans le récepteur
INF6001 Chap 3 30
Problèmes (montrant que ce protocole n’est pas parfait, comme attendu)
Double chevauchement de message! Un vieux message échu avec un bit égal à ce qui est attendu sera
considéré bon…
nD0
D0
nA0
D1
A1
OK! (croit avoir reçu n+2)
n+1 n+1
n
A0Acquitte vieille donnée
13
37
73 13
3634
46 64
416113
36
Pense que ceci est un msg répété par erreur!
67
INF6001 Chap 3 31
Réceptions non spécifiées dans BA
Que va faire l’envoyeur avec un A0 après avoir reçu un A1 lorsqu’il n’a rien envoyé? Il pourrait l’écarter
le récepteur recevra un deuxième D0 qu’il acquittera et ignorera
Ou il pourrait lire dans le canal seulement après avoir envoyé D0 Il considérera son dernier D0 acquitté Et il répondra avec !D1 à l’A0 que le récepteur lui enverra
Dans les deux cas, le protocole retournera enfin à la normalité Mais la mauvaise donnée a été livrée à l’usager
INF6001 Chap 3 32
Et aussi…
Double chevauchement d’ACK
nD0
D0
A0
n+1
A0
D1
A1
D0
A0
D1D0 n’a pas été reçu, D1 sera écarté
13
37
73
34
46
61
13
34
46
n
13
36
67
76
64
n
n+1
41
18
INF6001 Chap 3 33
Problèmes de sécurité
Nous aurons évidemment des problèmes semblables si nous admettons que le milieu puisse générer par lui-même des mauvais messages,
ou si ceci serait possible par intervention d’un tiers
INF6001 Chap 3 34
Transmission bidirectionnelle
Le protocole que nous venons de donner est pour transmission dans 1 direction seulement (simplex)
Le protocole BA original pouvait fonctionner dans les 2 directions (alternat ou half-duplex)
Piggybacking: un seul paquet sert pour transférer les nouvelles données en même temps que l’ack du message précédent dans la direction opposée
INF6001 Chap 3 35
Protocole BA alternat bidirectionnel, compacté…Deux stations A et B, chacune
garde son propre bit local Bit local=1 au début pour les deux A commence en état 1 B commence en état 3
N=Données de l’usager, bit local est renversé
!D envoi données avec bit local?Db réception de données avec
Pour A, bit = local de A Pour B, bit ≠ local de B
?Dm réception opposée (erreur)U=données à l’usager
1
2
3
4!D ?Dm, To
?Db
N
U
A
B
INF6001 Chap 3 36
Architecture globale: 4 machines à états
Usager émetteur
Émetteur Récepteur
Usager récepteurN U
INF6001 Chap 3 37
Mais...
La vitesse des deux usagers doit être la même: Quoi faire si A envoie un message, B doit acquitter mais son
usager n’a pas de données prêtes à envoyer? A devra donc attendre, ou sinon des messages vides
pourraient être livrés avec certains acquittements...
INF6001 Chap 3 38
Terminologie
Simplex = UnidirectionnelHalf-Duplex ou alternat = bidirectionnel alternative
Canal qui peut fonctionner dans une direction ou l’autre, mais pas simultanément
Full duplex = bidirectionnel simultané
INF6001 Chap 3 39
Propriété qui peut être prouvée pour le BA
Dans le cas d’un milieu avec possibilité d’erreur mais sans double chevauchement, il est possible de prouver que le BA préserve l’ordre des données, c.-à-d. La chaîne des messages reçus est dans le même ordre de
la chaîne des messages envoyés Moins évidemment les messages envoyés et pas encore
arrivés
INF6001 Chap 3 40
Auto-stabilisation (Self-synchronisation)
Le protocole du BA a aussi la propriété d’être capable de retourner au fonctionnement normal après n’importe quelle situation d’erreur
Il pourra cependant avoir envoyé à l’usager les mauvaises données (ce que nous avons vu)
INF6001 Chap 3 41
Protocoles à fenêtre d’anticipation (sliding window)
Le protocole du BA peut être généralisé en utilisant un compteur de plusieurs bits n bits
Dans le cas de n=1, l’émetteur devait garder le dernier message jusqu’à l’acquittement, donc 2n -1 messages
En général, pour un compteur de n bits, l’émetteur doit garder au plus les derniers 2n -1 messages jusqu’à leur acquittement
Dans ce cas, il y a plus de liberté concernant la vitesse relative de l’émetteur et du récepteur L’émetteur peut continuer d’envoyer des paquets même si un certain
nombre de paquets déjà transmis n’a pas été acquittéLes protocoles à fenêtre ont été utilisés dans la couche 2 de
X.25, couche 2 de l’OSI et dans TCP HDLC: High-level Data Link Control
INF6001 Chap 3 42
Fenêtre d’anticipationAu moment de l’envoi d’un message, l’émetteur positionne une
minuterie spécifique à ce messageSi l’ack n’est pas reçu dans le délai, le message doit être
retransmis, avec tous les messages qui l’ont suivi jusqu’à la détection de l’erreur
L’émetteur doit être prêt à renvoyer tous les messages non acquittés dans une ‘fenêtre’ ou tampon dont la dimension est reliée à l’intervalle de la minuterie
Peut réutiliser l’espace des messages acquittés La dimension de la fenêtre doit être telle que le transmetteur
puisse être sûr de pouvoir retransmettre toutes les trames non acquittées
L’intervalle de temporisation et la dimension du tampon doivent être soigneusement choisis
INF6001 Chap 3 43
Fenêtre d’anticipation
01
2 0
1Erreur
3
écarté
écarté
écarté
écarté2
émetteur récepteur
3
4
23
5
6L’émetteur s’est enfin aperçu que 2 n’a pas été acquitté (temporisation)
4
4Émetteur doit garder en mémoire un certain nombre de messages pour pouvoir éventuellement les retransmettre (dans ce cas, de 2 à 6)
Exercice: combien de messages faut-il garder?
INF6001 Chap 3 44
Comment choisir le temps d’attente pour un acquittement?
Ce temps est déterminé par la vitesse du réseauDoit être choisi judicieusement:
Si trop petit, beaucoup de messages pourraient être renvoyés inutilement
Si trop grand, trop de message devront être renvoyés quand on s’apercevra qu’un message a été perdu
Aussi le protocole pourrait retourner à numéroter un message n avant qu’on se soit aperçu que le message n précédent a été perdu…
INF6001 Chap 3 45
Quelques calculs, par exemple…
Avec un numéro de séquence de 16 bits, nous pouvons numéroter 65 536 messages
Si un message est de 27 = 128 bits, ceci demande une zone tampon de 216x27 = 223 = 8 388 608 bits
À la très modeste vitesse de 9 600 bps, tous les numéros seront utilisés dans 15 minutes Plus exactement 14.56 mins
Donc si un message retarde plus de ça, il pourrait être mal placé dans la séquence suivante Il doit cependant arriver au moment où un message avec le
même no de séquence est attendu
INF6001 Chap 3 46
Taille du tampon
Des exemples qu’on trouve dans les livres et dans les sites web montrent des tampons de taille 2N pour numéros de séquences de N bits
En réalité, l’émetteur ne peut transmettre plus de 2N-1 message à l’avance Considérez le cas où l’émetteur envoie 2N messages et tous les
acquittements sont perdus! L’émetteur essaiera de renvoyer la même séquence Le receveur, ne sachant pas que tous ses acquittements sont perdus,
pensera qu’il s’agit de la séquence suivante! Donc il est nécessaire que l’émetteur s’arrête après avoir envoyé 2N-1
messages, s’il ne reçoit aucun acquittement à ce moment là, il doit reprendre la séquence courante à partir du début
Et le récepteur saura qu’il s’agit encore de la séquence courante
INF6001 Chap 3 47
Technique alternative
Seulement les messages erronés sont retransmisLe récepteur doit donc stocker tous les messages
suivant une erreur et être prêt à insérer les retransmissions dans le bon ordre
Meilleure utilisation de bande passante s’il y a beaucoup d’erreurs (rare aujourd'hui)
Mais moins utilisé car il demande un stockage tant pour l’émetteur que pour le récepteur Donc stockage double pour une station relais
INF6001 Chap 3 48
Et encore une autre technique
Dans chaque acquittement, le récepteur déclare être prêt à recevoir k paquets à partir d’un certain numéro
L’émetteur doit garder dans un tampon tous les paquets non acquittés Pourraient devoir être retransmis
Il peut réutiliser l’espace libéré par les paquets déjà acquittés Réduit le nombre d’acquittements
3 4 5 66 7 0 1 2 3 4 5 6 7 0 1 2
Paquets déjà transmis
Paquets qui pourraient être transmis
INF6001 Chap 3 49
Contrôle de flux
Ces mécanismes sont étroitement reliés au problème de contrôle de flux
Le contrôle de flux est un mécanisme pour empêcher l’émetteur d’envoyer plus que le récepteur ne peut recevoir (à cause de l’espace de tamponnage disponible)
Il y a deux formes fondamentales de contrôle de flux: Explicite: le récepteur dit à l’émetteur qu’il est prêt à recevoir x paquets
(exemple précédent) Ou il envoie un message demandant à l’émetteur de suspendre
Implicite: le récepteur n’accepte pas (p.ex. n’envoie plus d’acquittements) Ceci peut forcer l’émetteur à retransmettre
INF6001 Chap 3 50
Les deux fonctions des acquittements
Le message d’acquittement (ack) a donc deux fonctions reliées: Faire savoir que le message a été reçu correctement
(contrôle d’erreur) Faire savoir que le récepteur est prêt à recevoir un ou
plusieurs nouveaux messages (contrôle de flux)
INF6001 Chap 3 51
La couche liaison aujourd’hui
La couche liaison était très importante à l’époque où les réseaux étaient lents et peu fiables (contrôle d’erreurs) et les ressources de mémoire des noeuds étaient limitées (contrôle de flux)
Aujourd’hui les réseaux sont très rapides, très fiables, et les ressources de mémoire sont importantes
À fins d’efficacité et simplicité, beaucoup d’applications sont bâties sur des protocoles comme UDP, un protocole de «transport » qui ne garantit pas de préserver l’ordre des messages
Chose qui n’avait pas été prévue par les concepteurs de l’architecture OSI! Quel est le résultat dans le cas d’erreur?
Certaines applications ne sont pas sensible aux erreurs occasionnels p.ex. voix sur IP, multimédia
L’application peut être bâtie pour détecter et récupérer des erreurs à son niveau p.ex. un programme qui consulte une base de données peut reconnaître l’erreur
car les données ne sont pas reçues dans le format approprié et peut donc répéter la requête
INF6001 Chap 3 52
Pour en savoir davantage
Un vieux livre de Gerhard Holzmann contient beaucoup d’informations que j’ai utilisé pour ce chapitre
http://spinroot.com/spin/Doc/Book91_PDF/Design_and_Validation_1991.pdf
V. Surtout Chapitre 4.