TD : utilisation des automates pour les protocoles réseaux
Résumé
Séance présentant l’intérêt des automates pour la modélisation de protocoles réseaux. Cette
séance utilise du matériel pédagogique mis en place par Olivier Paul et ses collègues de l’Institut
Mines-Télécom 1 .
1 Prérequis
Cette séance de TD présuppose que vous avez vu la vidéo d’Olivier Paul (Telecom Sud Paris) accessible
à l’adresse https://vimeo.com/88630275. Quelques questions de compréhension pour commencer :
Dans l’exemple des transactions bancaires, un premier protocole de communication utilise uniquement
un minuteur du côté de l’émetteur pour détecter les messages non parvenus au récepteur. Contrairement
au protocole du bit alterné, ce premier protocole simple n’associe pas de numéro à ses messages.
Exercice 1
Indiquez un problème qui peut survenir quand un tel protocole est utilisé. Représentez la situation à
l’aide d’un diagramme temporel.
2 Modélisation du protocole du bit alterné par un automate
Les automates sont une façon de modéliser les protocoles, ils permettent de vérifier manuellement des
cas d’utilisation, de vérifier que certains scénarios sont prévus. Une fois établis, ces automates peuvent
être utilisés de façon automatique par des programmes : pour déterminer si un protocole se termine
(quand c’est un but souhaité), ou pour implémenter automatiquement une partie du code réalisant le
protocole.
2.1 Le cas de l’émetteur
Plaçons-nous dans un premier temps du point de vue de l’émetteur. Chaque état représentera une
situation dans laquelle l’émetteur peut se trouver et toute transition entre deux états contient deux
informations :
– l’événement qui déclenche ce changement d’état
– l’action de l’émetteur en réponse à cet événement
Dans le protocole du bit alterné, nous avons plusieurs états, ne serait-ce qu’en raison du fait que la
valeur du compteur doit être envoyée et qu’elle peut être 0 ou 1 (auquel cas on n’envoie pas la même
information).
Exercice 2
Pour concevoir l’automate de l’émetteur, les questions suivantes sont importantes :
– quels sont les types de messages qui peuvent circuler entre l’émetteur et le récepteur (indice : il y a
2 × 2 types de messages).
– quels sont les événements qui peuvent survenir ?
– est-ce que l’action déclenchée par l’émetteur est toujours la même quand il reçoit un certain événe-
ment ?
1. nous remercions O. Paul pour l’autorisation de réutiliser ce matériel sous la forme d’un TD.
1
Polytech IG3 – Langages, automates, expressions régulières TD-protocoles 14 avril 2014 p. 2/ 6
Exercice 3
Etablissez maintenant une table indiquant pour chaque événement (colonne 1), l’action qui doit lui
être associée (colonne 2).
Exercice 4
Dessinez maintenant l’automate de l’émetteur avec 4 états.
Exercice 5
Dans un tel automate, un état peut être final quand les informations à communiquer ont bien été
transmises. Dans votre automate, quel état est final ? Combien sont-ils dans ce cas ?
Exercice 6
Dans le diagramme temporel ci-joint, indiquez dans les petits nuages le numéro de l’état dans lequel
l’émetteur se situe à ces moments là.
Exercice 7
En supposant que l’émetteur est dans l’état 4, et qu’on lui demande de transmettre une nouvelle donnée
D, dans quel état l’automate va-t-il se retrouver ?
2.2 Le cas du récepteur
Plaçons-nous maintenant du point de vue du récepteur. On rappelle que le récepteur gère lui aussi son
propre compteur.
Exercice 8
Dans la vidéo vue en préambule à cette séance, rappelez quel est le sens de la valeur du compteur de
l’émetteur, c-à-d que signifie que ce compteur est à 0 (idem quand il est à 1).
Exercice 9
Montrez que deux états seulement sont nécessaires pour concevoir l’automate du récepteur.
Exercice 10
Dessinez l’automate du récepteur.
Polytech IG3 – Langages, automates, expressions régulières TD-protocoles 14 avril 2014 p. 3/ 6
3 Algorithmique
Exercice 11
Quel paradigme de programmation est particulièrement adapté pour traduire un automate sous la
forme d’un algorithme (en particulier pour la gestion des transitions) ?
Exercice 12
Dans une méthode gérant la réception d’un événement, quelle structure conditionnelle est particuliè-
rement utile ?
Exercice 13
Traduisez l’automate du récepteur sous la forme d’un algorithme.
Exercice 14
Même question pour l’émetteur. On supposera que les messages à transmettre s’accumulent dans une
file F (que l’on manipulera par l’API de ce Type de Données Abstrait).
4 Solidité du protocole du bit alterné
Supposons que l’on utilise ce protocole pour faire dialoguer deux sites distants (un Emetteur et un
Récepteur) connectés sur internet par un nombre quelconque de noeuds intermédiaires.
Exercice 15
Est-il possible que l’automate de l’émetteur reçoive un message ACK0 quand il est dans l’état 4 ? (si
non pourquoi, si oui dessinez un diagramme temporel correspondant à cette situation).
Exercice 16
Si jamais cette situation était possible, quelle action faudrait-il faire à la réception d’un tel message
(comment complèterait-on l’automate) ?
Exercice 17
Le protocole du bit alterné semble donc pouvoir être pris en défaut Dessinez le schéma temporel d’un
enchaînement malencontreux amenant à la non transmission d’une donnée sans que l’émetteur et le
récepteur ne s’en aperçoive
5 Pour aller plus loin
Si l’on se place dans le cadre d’une communication directe entre Emetteur et Récepteur où les messages
circulent en FIFO sur le canal, le protocole du bit alterné ne peut pas être pris en défaut (il ne souffre
pas des soucis évoqués ci-dessus). Par contre, même dans ce cadre très strict, il a pour inconvénient
important que la liaison de données est inoccupée la plupart du temps (on n’autorise la transmission
que d’une seule trame à la fois (D0 ou D1) : l’émetteur (resp. le récepteur) passe son temps à attendre
l’acquittement du récepteur (resp. la trame D suivante de l’émetteur).
Exercice 18
Supposons que l’on numérote les trames non plus 0 et 1 mais 0, 1, 2, · · · , n. De la même façon, les
acquittements sont numérotés ACK0, · · · , ACKn.
Expliquez comment modifier le comportement de l’émetteur et du récepteur pour permettre que plu-
sieurs messages soient émis les uns après les autres sans avoir encore reçu les ACK des premiers messages
envoyés (on supposera n = 3 par exemple).
Exercice 19
Combien de messages peut envoyer l’émetteur sans avoir encore reçu d’acquittement ?
