Gestion de collisions

4 Gestion de collisions

Pour bien comprendre la notion de gestion de collision, il vous est demandé de réaliser une couche de niveau liaison. Vous devrez gérer les collisions pouvant se produire lors de la communication de plusieurs PC sur un bus série. Si vous désirez aller jusqu'au bout de l'exercice, vous pourrez faire en sorte que le port série du PC se comporte comme une interface réseau Ethernet. Ainsi, il sera possible de tester l'efficacité de votre application en utilisant les utilitaires TCP/IP classiques (en particulier ping et ssh).

4.1 Dispositif matériel

Ce projet est basé sur un dispositif matériel qui implante un bus série. Ce dispositif ne comporte, comme composant électronique, que des diodes. Voici le schéma d'un dispositif à 4 ports :

Une réalisation de ce dispositif par Thierry Flamen de la plateforme électronique est visible sur ces deux photos. Vous y trouvez aussi le câble utilisé pour connecter le port série du PC au dispositif (câble avec un connecteur DB9 femelle et un connecteur RJ45 mâle).

4.2 Code fourni

Pour cette partie vous pouvez vous appuyer sur le code fourni dans l'archive http://www.plil.net/~rex/Enseignement/Reseau/Tutorat.Reseau.GIS3/linkCollisionsStudents.tgz. Il ne vous reste plus qu'a compléter les fichiers du sous-répertoire Programs. La génération des exécutables se fait par un simple make.

4.2.1 Bibliothèque série

Vous avez à votre disposition une bibliothèque permettant de gérer le port série. Cette bibliothéque ne comporte les fonctions décrites ci-après.

int serialOpen(char *device,int speed,int mode);
void serialClose(int fd);

La première fonction permet d'ouvrir le port série correspondant au périphérique device. Le port est configuré pour une vitesse de speed bauds. Il existe 3 modes d'ouverture :

SERIAL_READ: : possibilité de lire des octets sur le port série,
SERIAL_WRITE: : possibilité d'écrire des octets sur le port série,
SERIAL_BOTH: : possibilité de lire et d'écrire des octets sur le port série.

La seconde fonction ferme le port série. Dans le cadre du TP, le port série est représenté par le fichier spécial /dev/ttyS0 et il est conseillé de commencer par utiliser une vitesse faible (9600 bauds par exemple). Attention, par défaut vous n'avez pas accès au port série de votre PC de TP (affichez les permissions du fichier spécial). Pour obtenir l'accès au port série, utilisez la commande super serial.

4.2.2 Utilitaire de gestion d'interface Ethernet virtuelle

Pour ceux qui souhaitent aller plus loin il est possible de créer une interface Ethernet virtuelle. La création s'effectue avec la commande super addtap <@IP> <mask>, la destruction avec la commande super deltap. Une fois l'interface tap0 créée, il est possible de lancer l'utilitaire ethercat disponible dans le répertoire Utilities. Cet utilitaire utilise la bibliothèque du répertoire Ethernet pour se connecter sur l'interface Ethernet virtuelle. L'utilitaire ethercat affiche sur sa sortie standard les paquets reçus sur l'interface tap0 et envoi sur l'interface tap0 les paquets lus sur l'entrée standard. Les paquets lus sur l'entrée et affichés sur la sortie sont au même format : des octets en hexadécimal sur deux chiffres sans séparateur. Un paquet est terminé par un saut de ligne. L'utilitaire ethercat peut être utilisé, en conjonction avec les programmes d'envoi et de réception sur le port série, pour simuler une connexion Ethernet entre plusieurs machines.

4.3 Communication simple

Nous allons commencer par établir une communication entre deux PC via leurs ports série. Les deux ports série sont connectés par un bus série comme décrit en 4.1.

4.3.1 Procédure d'envoi sur le bus

Dans le fichier source serialWrite.c, écrivez un programme capable de lire des chaînes de caractères sur son entrée standard et de les envoyer sur le port série caractère par caractère. Attention le port série est ouvert en mode non bloquant. Ceci signifie qu'un appel à la primitive write peut échouer avec l'erreur EAGAIN pour cause de port série non immédiatemment prêt à envoyer un caractère. Dans ce cas, il convient d'attendre un cours instant avec la fonction usleep et de retenter l'envoi. N'oubliez pas de prévoir un mécanisme pour séparer les tableaux d'octets (chaînes de caractères). Vous pouvez par exemple transmettre les sauts de lignes. Si vous le souhaitez, vous pouvez aussi envoyer un caractère de début d'envoi.

4.3.2 Procédure de réception sur le bus

Dans le fichier source serialRead.c, écrivez un programme récupérant les octets sur le port série et affichant les tableaux d'octets sur la sortie standard. Attention, l'ouverture du port série en mode non bloquant influe aussi sur la lecture. Vous devez vérifier le retour de la primitive read, l'erreur de type EAGAIN ne doit conduire qu'à une attente courte suivie par une nouvelle tentative de lecture. Les octets ne doivent pas être affichés un par un mais stockés en mémoire et affichés uniquement sur réception de la marque de fin. Le programme doit aussi accepter des paramètres. Chaque paramètre est un préfixe permettant de filtrer les tableaux d'octets. Ne sont affichés que les tableaux commencant par l'un des préfixes. Ce filtrage permet, à terme, de ne laisser passer que les paquets dont l'adresse de destination concerne notre interface Ethernet virtuelle.

4.3.3 Premiers tests

Pour faire le premier test, connectez deux PC via un bus série. Lancez votre exécutable serialWrite sur un PC et votre exécutable serialRead sur l'autre PC. Tapez une chaîne de caractères sur l'entrée standard de serialWrite, elle devrait s'afficher sur la sortie standard de serialRead. Vous pouvez tester la gestion des préfixes en lançant serialRead avec des préfixes en paramètres et en vérifiant que les chaînes affichées sont bien celles commençant par ces préfixes.

Le second test vérifie le bon fonctionnement du bus série. Lancez aussi l'exécutable serialRead sur le premier PC. Vous devriez constater que les caractères envoyés par serialWrite arrivent sur tous les PC connectés au bus série. Essayez aussi avec un troisième PC.

Le troisième test consiste à lancer un serialRead sur un PC et deux serialWrite sur deux autres PC. Le but est d'effectuer un envoi simultané sur le bus série. Si vous avez du mal à synchroniser vos envois vous pouvez écrire une boucle d'affichage en shell et rediriger la sortie de cette boucle sur l'entrée de votre exécutable serialWrite. Que constatez-vous sur la sortie standard de votre exécutable serialRead ?

4.4 Somme de contrôle

Pour éviter d'afficher des tableaux d'octets corrompus, vous allez ajouter une somme de contrôle aux tableaux d'octets transmis sur le bus série.

4.4.1 Calcul de la somme de contrôle

Modifiez votre programme d'émission pour calculer une somme de contrôle et l'insérer en fin de tableau d'octets. Il vous est suggéré d'utiliser l'addition classique sur les octets et de tronquer la somme aux 16 bits de poids faibles. Pour insérer la somme de contrôle, vous pouvez, par exemple, utiliser la fonction sprintf avec un format du type "%04x".

4.4.2 Vérification de la somme de contrôle

Modifiez votre programme de réception pour vérifier la somme de contrôle une fois le paquet reçu. Pour lire la somme de contrôle vous pouvez utiliser la fonction sscanf avec le format "%x". Le paquet ne doit pas être affiché sur la sortie standard si la somme de contrôle n'est pas correcte.

4.4.3 Test de la somme de contrôle

Générez à nouveau des collisions avec des émissions simultanées. Vérifiez qu'aucun tableau d'octets n'est affiché. Arrêtez l'un des processus d'émission vérifiez que les tableaux d'octets sont affichés à nouveau.

4.5 Détection de collisions

Pour éviter les pertes de tableaux d'octets, vous allez mettre en place divers mécanismes déjà utilisé par le protocole Ethernet.

4.5.1 Ecoute de porteuse

Dans votre programme d'émission, ajoutez une fonction permettant d'attendre le silence sur le bus série avant d'envoyer un tableau d'octets. Il va donc falloir ouvrir le port série en lecture et écriture. Il faut aussi trouver un dispositif pour arrêter le programme de lecture sur le port série s'il est lancé sur la même machine. En effet si deux programmes lisent le port série en même temps, le résultat est indéterminé. Il vous est proposé de passer un paramètre optionnel à serialWrite pour lui communiquer le PID du serialRead. Avant l'envoi d'un tableau d'octets le processus serialWrite doit envoyer, en utilisant la primitive kill, un signal SIGSTOP au processus de PID passé en paramètre. Aprés l'envoi, qu'il y ait eu collision ou non, un signal SIGCONT doit être envoyé au même processus.

4.5.2 Détection de collision

Lors de l'envoi d'un tableau d'octets, vérifiez que les octets sont correctement envoyés. Pour cela, il faut faire autant de lectures que d'écritures en comparant les octets pour s'assurer qu'ils sont passés intacts. Si vous souhaitez avoir des performances correctes il ne faut pas essayer de vérifier chaque octet après l'avoir envoyé à cause de la latence entre émission et réception. Cela dit il ne faut non plus faire trop d'écritures avant les premières vérifications car cela conduit à une perte de bande passante en cas de collision. En cas de collision il faut arrêter l'émission immédiatement.

4.5.3 Retransmissions après collision

Lorsqu'une collision est détectée, une retransmission du tableau d'octets doit être retentée après une attente. Utilisez le même algorithme que pour Ethernet, à savoir 16 retransmissions avec des temps d'attentes tirés au hasard entre 0 et (2ⁿ)-1 unités où n est le numéro de la tentative. Réduisez l'intervalle à [0,1024] s'il est plus large. A vous de spécifier l'unité d'attente en fonction du temps nécessaire pour envoyer un petit tableau d'octets. N'oubliez pas de relancer l'éventuel processus serialRead avant l'attente. Utilisez la fonction usleep pour réaliser l'attente.

4.5.4 Test de détection de collisions

Générez à nouveau des collisions avec des émissions simultanées. Vérifiez que les tableaux s'affichent à nouveau, bien qu'éventuellement dans le désordre. Attention a ne pas saturer la bande passante avec des envois trop rapides.

4.6 Interface Ethernet virtuelle

Si vous souhaitez aller plus loin vous pouvez utiliser des interfaces Ethernet virtuelles pour tester votre couche liaison avec les utilitaires habituels comme ping et ssh. Regardez le script shell launch.sh qui vous montre comment combiner vos exécutables et l'utilitaire ethercat. Créez une interface Ethernet virtuelle par PC connecté au bus série en lui donnant une adresse IP d'un réseau IP commun (par exemple 192.168.0.0/24). Lancez ensuite le script launch.sh sur chaque PC. Enfin utilisez ping pour vérifier que votre couche liaison est capable de transporter des paquets IP. Vous pouvez aussi lancer des ping simultanés voire des ssh pour des tests exhaustifs.