Le Coin Wiki
d'Olivier Dalle
$WikiTagline
 

Seance de TD sur CPNTools

Pour finir ce cours d’initiation l’Ingnierie des Protocoles nous allons exprimenter l’outil CPNTools dvelopp par le Prof. K. Jensen et le CPN Group de l’Universit d’Aarhus au Danemark.

CPN signifie Colored Petri Nets. C’est une extension des Rseaux de Petri dans laquelle les jetons peuvent avoir diffrentes couleurs. Et pour cela on autorise des tests (en particulier sur la couleur des jetons) au niveau des arcs (pre- et post-conditions). Cette extension est intuitivement facile comprendre, nous allons la dcouvrir et l’exprimenter sur le tas.

Installation

CPNTools est un outil trs puissant, dont l’ergonomie est assez originale et ludique, mais trs exigeant en terme de configuration car utilisant le standard OpenGL. En pratique, le programme n’est disponible que sous forme binaire, et seulement pour Linux et Windows. Mais sur MacOs, on peut eventuellement le faire tourner dans une machine virtuelle Windows (ca marche trs bien sur mon <nop>MacBook Pro Intel).

Le programme n’est pas librement tlchargeable, mais l’Universit d’Aarhus nous a accord un droit d’utilisation. Vous trouverez l’archive .tar.gz sur le compte de Olivier Dalle. Sur les machines Linux de la fac, vous NE pouvez PAS utiliser directement la version installee sur le compte de Olivier Dalle en /u/profs/dalle/CPNTools, decomprimez l’archive cpntools_2.3.5.tar.gz sur votre compte, ou en /tmp si vous manquez de place. La commande lancer est cpntools.

Premiers pas (Seance 1)

Lisez la documentation sur le site cpntools, elle est trs bien faite: http://cpntools.org/documentation/start

On vous y explique en particulier ce qui fait l’originalit de l’interface, ce menu qu’on obtient en cliquant avec le bouton droit.

Lors du demarrage de l’application ou du chargement d’un RdP, il est courant que les traits (pre- et post-conditions) n’apparaissent pas. C’est un petit bug de l’outil, vous pouvez corriger en deplacant les elements graphiques ou en redimmensionnant la fenetre pour forcer le rafraichissement de l’affichage.

Ouvrez un exemple de Rseau de Petri, par exemple les philosophes, et essayez de comprendre son fonctionnement. Remarquez que grace a l’utilisation des couleurs, il n’y a besoin de dcrire qu’un seul philosophe.

Remarquez ce qui se passe lorsque vous “tirez” les lments du menu Toolbox dans la partie gauche avec la souris vers la zone de droite. Entrainez-vous un peu…

Essayez de faire tourner l’exemple pas pas a l’aide du menu de simulation. Vous pouvez choisir prcisment quel jeton utiliser, ou lancer la simulation pour un certain nombre d’etapes. Expriementez ces diffrentes options.

Exprimentez le menu State Space. Lancez l’action de proudction de rapport, et analysez le resultat.

Un protocole simple

Ouvrez l’exemple SimpleProtocol. Faites le tourner et cherchez une explication prcise du role de chaque lement du rseau: les places, les arcs, les couleurs, etc.

Ce rseau est-il k-born ? Pourquoi ?

Y a-t-il un moyen de le rendre k-born sans changer la partie centrale du rseau (les transitions <nop>TransmitPacket et <nop>TransmitAck ? (Pensez aux gnraux …)

Rflchissons un peu… ( a terminer avant la seance 2)

Avez-vous remarque que la liste initiale des messages ne s’puise jamais ? En fait, ce rseau ne fait pas la diffrence entre les messages que l’on envoie pour la premire fois et ceux que l’on r-envoie.

Modifiez ce rseau de facon a corriger cela, cad faire en sorte que la liste des messages a envoyer pour la premire fois s’puise. Vous pouvez par exemple ajouter de nouvelle places pour reprsenter la liste des messages dj envoys en attente de confirmation.

Modifiez maintenant le protocole prcdent de telle facon que le message d’acquittement contienne systmatiquement le numro du paquet recu par le destinataire. Il faudra donc faire en sorte que l’emeteur ignore les acquitements pour des messages deja envoys et acquits. Il faudra aussi faire attention ce que le destinataire continue de recevoir et d’accepter les paquets dans le bon ordre (en particulier il ne faut pas permettre que la place Received recoive plusieurs fois le meme message).

On souhaite maintenant modliser le fait que perdre plus de 3 fois le meme message est tellement improbable que ca ne peut pas se produire. (Au fait, pourquoi peut-on vouloir modliser une telle chose au lieu de la ralit ?). Pour cela on va modifier le rseau de telle facon qu’il se souvienne de ce qu’il a transmis, et fasse en sorte que si le message est deja pass trois fois, alors il est remis de facon certaine la destination (ou la source dans le sens des acquittements). Une fois que cette dernire modification est effectue, utilisez l’analyse statique pour vrifier les bonnes proprits de votre rseau de Petri.

Pour aller plus loin (Seance 2, a rendre a la fin de la seance).

Le protocole CSMA-CA est le protocole utilis par les rseaux radio WiFi. Pour eviter les collisions, il utilise une technique consistant signaler d’abord son intention d’envoyer avant d’envoyer vraiment. Pour cela le temps est decoup alternativement en priodes de contention et priode de transmission. Durant la priode de contention, les stations candidates envoient un message RTS (Request To Send). Si ce message n’est pas collisionn alors le destinataire envoie un message CTS (Clear To Send). Puis aprs un certain dlai, les stations commencent changer. Pendant cet change, les autres stations qui ont vu passer l’change RTS/CTS sont supposes rester silencieuses jusqu’ la fin de l’change.

Il faudra donc modliser les diffrentes priodes (contention, change) et tat du canal durant la priode de contention (si 1 message Ok, si plus que 1 contention).

INDICATIONS

  • L’objectif du TP est simuler 3 stations qui communiquent en utilisant le protocole CSMA-CA.
  • Pour montrer (de facon informelle) que le protocole fonctionne, votre simulation devra montrer que chaque station parvient a envoyer un message a chaque autre station.
  • Au depart vous chaque station devra donc etre dans etat initial comportant un message a envoyer vers chacune des deux autres stations.
  • Pensez a utiliser les “couleurs” (jetons typs) de CPN: chacune des 3 station execute exactement le meme protocole, mais en utilisant des jetons de couleur differente. Comme dans l’exemple des philosophes, vous n’avez donc besoin de reprsenter l’automate que d’une seule station.* Comme dans l’exemple du protocole simple, vous devrez reprsenter l’tat du rseau (libre, occup sans collision, occup avec collision).
  • Gestion du non determinisme:
    • initialement, chaque station a deux messages a envoyer, soit 6 messages en tout. On ne sait pas a l’avance quel message sera choisi pour etre envoye le premier, ni quelle station commence: vous devez laisser CPN faire ce choix. Attention: votre solution doit pouvoir fonctionner aussi avec plus que 3 stations et/ou plus que 2 messages initiaux. Cela signifie que votre solution ne doit pas dependre du nombre de messages restant a envoyer.
    • deux stations peuvent choisir de commencer en meme temps, ou presque, ce qui doit normalement conduire a une collision.
    • Attention: une station ne peut pas envoyer son deuxieme message avant d’avoir fini d’envoyer le premier. Initialement, sur chaque station il y a donc un choix du message a envoye qui rend l’envoi du message suivant impossible tant que le premier n’est pas fini d’envoyer.
  • Types des messages: les messages pourront etre representes a l’aide de jetons. Chaque message comporte un type (RTS, CTS, DATA, …) un expediteur et un destinataire, donc les jetons auront 3 dimensions.

Ne vous jetez pas sur l’outil CPNTools des la premiere minute. Commencez reflechir avec un papier et un crayon. Une fois que vous avez une solution sur le papier, la ralisation ira trs vite!

Vous DEVEZ rendre une premiere version de votre projet sur jalon a la fin de la seance, ou au plus tard dans l’heure suivante. Ensuite, vous pourrez encore amliorer votre solution (ventuellement) pendant quelques jours. Vous deposerez votre projet CPNTools dfinitif sur Jalon au plus tard le 13 novembre minuit. Vous pouvez travailler en binme, mais pas plus que 2 etudiants par projet. Il est interdit de copier sur le voisin ou de laisser le voisin copier sur votre projet. Votre archive doit etre un fichier zip faisant apparaitre votre nom ou les noms des deux binomes. L’archive contenant le version definitive doit avoir le suffixe additionnel “final”. L’archive doit produire un repertoire unique contenant tous vos fichiers, Ce repertoire doit aussi faire apparaitre votre(vos) nom(s). Exemple: OlivierDalle-final.zip, contenant OlivierDalle-final/CSMA-CA.cpn …

retour a la page du cours…