• 10 hours
  • Easy

Free online content available in this course.

course.header.alt.is_video

course.header.alt.is_certifying

Got it!

Last updated on 12/13/19

Animez un atelier : le routage élastique !

Log in or subscribe for free to enjoy all this course has to offer!

Le "routage élastique" permet de comprendre la notion de routage et la façon dont les routeurs construisent leurs tables. Vous pouvez en trouver une version étendue sur la page des activités débranchées de Marie Duflot-Kremer. Vous pouvez la pratiquer avec le matériel recommandé sur la page en question. Ce matériel n’est pas très difficile à trouver, l'activité est super ludique, et permet de tester plusieurs configurations de réseaux grâce aux élastiques.

Voilà le matériel dont vous aurez besoin : des ceintures de judo (par exemple), des sangles ou cordes avec des mousquetons et un “message” représenté par cette pince en fer :

On peut aussi simplement utiliser un marquage au sol pour représenter le réseau. Notre réseau doit ressembler à cela :

Ce réseau est tout petit, mais c’est pour éviter une activité trop longue. Vous pouvez en imaginer de plus grands si vous le souhaitez, ou bien en faire plusieurs en même temps (par exemple 3 groupes de 4 sur le même modèle).

Pardonnez notre manque d’imagination sur les noms des participant·e·s… ils se prénomment donc A, B, C et D. Et chacun représente un routeur (une machine sur le réseau). Les connexions dans le réseau (qui est voisin de qui ?) sont représentées par les traits entre les participant·e·s.

L’activité se déroule en plusieurs temps (et, comme dit en introduction, vous pouvez vous arrêter sur le temps qui vous convient).

  • Dans un premier temps on va simplement voir comment fonctionnent les échanges en faisant circuler quelques messages.

  • Dans un deuxième temps, le réseau va évoluer, et on va devoir s’adapter.

  • Et, dans un troisième temps, on va voir que l’adaptation n’est pas toujours si facile que ça…

Temps 1 : routons routons petits patapons !

Chaque participant·e joue le rôle d’un routeur et possède une table de routage. C’est cette table qui permet au routeur d’orienter un message en fonction de son destinataire.

On y voit, par exemple, que le routeur A peut rediriger des messages à destination de B, C ou D. Si le message est pour B, alors A va l’envoyer directement… à B. Si le message est pour C, c’est aussi facile, il l’envoie directement à C. Par contre, si le message est pour D, alors il doit le rediriger vers C, et ensuite… eh bien ensuite C saura bien se débrouiller ! Le routeur A n’a pas besoin d’en savoir plus.

Vous pouvez déjà faire distribuer quelques messages avec ce réseau et ces tables de routage et voir comment la communication se passe. Placer 2 ou 3 messages par routeur au départ avec des destinations plus ou moins éloignées et laissez les enfants acheminer tout ça. Normalement, on ne perd aucun message et tout se passe bien.

Regardez cette vidéo pour bien comprendre le fonctionnement de l’activité :

Temps 2 : Attention, réseau mouvant !

Dans la vraie vie, la forme du réseau change : un câble peut être coupé, un routeur peut tomber en panne, on peut rajouter un nouveau routeur, de nouvelles connexions, etc. Que se passe-t-il dans ce cas-là ? Les tables de routage fonctionnent-elles toujours ? Evidemment non. Modifiez le réseau pour le schéma suivant :

Et maintenant, demandez aux participant·e·s de s’adapter. Eh oui… il faut refaire les tables de routage !

Mise en œuvre : les participant·e·s peuvent se concerter à l’avance pour définir l’algorithme à exécuter (par exemple “on n’a qu’à se montrer nos tables entre nous” ou bien “on peut recopier la table de l’autre dans un coin”, etc.) Ensuite, fin de la communication générale ! On applique l’algorithme ainsi établi pour voir si ça marche.

Règles de communication : quel que soit l’algorithme choisi, tout doit passer par des échanges 2 à 2, en respectant les règles suivantes.

  • On ne peut communiquer qu’avec ses voisins directs (pas au-delà).

  • Pas de personne extérieure pour aller voir tout ce qui se passe partout, on n’envoie pas d’explorateur/rapporteur.

  • On a le droit de montrer sa table de routage, mais uniquement à ses voisins directs.

On peut laisser faire les participant·e·s jusqu’à ce qu’ils trouvent une solution, ou bien apporter la solution si c’est nécessaire.

Une “solution”. Les tables de routage seront mises à jour plusieurs fois, jusqu’à ce qu’elles se stabilisent. Pour cela, les routeurs s’échangent leurs tables régulièrement entre voisins directs. Montrer sa table à son voisin sera suffisant pour cette activité (et cela évitera la lenteur de la recopie et les erreurs qui vont avec). Ces échanges successifs entre les routeurs voisins font propager dans le réseau des petits bouts d’information, jusqu’à ce que tout le monde y trouve son compte. Pour cela, il y a une règle simple à respecter : à chaque modification de ma table, je l’envoie à mes voisins.

Ensuite, pour chaque routeur, il y a quatre questions à se poser en permanence, et une condition à vérifier pour savoir si sa table de routage est stabilisée. On peut noter ces quatre questions, visibles de tout le monde, pour que chacun·e puisse les appliquer sans se tromper. Elles sont, finalement, plutôt basiques.

  1. Que faire si j’ai perdu la connexion avec un de mes voisins ? Je le supprime de ma table ainsi que toutes les redirections qui passaient par lui.

  2. Que faire si j’ai un nouveau voisin, par exemple D ? Je note que le chemin vers D est direct : si le message est pour D, alors je l’envoie à D.

  3. Que faire si je passais par C pour aller à D, mais que C me dit ne plus savoir accéder à D ? Je supprime le chemin vers D qui passait par C.

  4. Que faire si mon voisin peut accéder à C, alors que moi je n’avais pas de chemin pour accéder à C ? J’ajoute dans ma table que pour atteindre F, je peux passer par le voisin en question.

Et alors quand est-ce qu’on s'arrête ? Quand plus personne ne peut envoyer de message c’est fini ! Pour ne pas que ce soit le bazar, on peut faire envoyer les messages chaque routeur à son tour : A fait tous ses envois, puis B, etc. Et quand tout le monde y est passé, on recommence un tour et on demande à chaque routeur s'il a des envois à faire. Quand, lors d'un tour, personne ne veut plus rien envoyer... c'est qu'on a fini.

Ah mais c’est cool ! Et si on faisait un essai pour voir si ça marche ?

Dans notre cas, il suffira de 2 tours. Après la modification des connexions, A perd un voisin (C) et en gagne un (D) ; B gagne un voisin (D) ; C perd deux voisins (A et D) ; et D perd un voisin (C) et en gagne 2 (A et B). Voici donc les tables de chacun, juste en regardant qui sont ses voisins :

Ensuite on démarre les échanges de tables entre routeurs. Regardons ce qui se passe au tour 1. A envoie sa table à B (qui n'en fait rien, il a déjà une connexion directe vers tous les routeurs) et à D (qui n'en fait rien non plus car A ne peut pas lui permettre d'accéder à C, la seule connexion qui lui manque). Par contre quand B envoie sa table à ses voisins A, C et D alors là… tout le monde va se mettre à jour. Le résultat sera :

Comme les routeurs ont modifié leurs tables, ils vont vouloir les communiquer à nouveau à leurs voisins. Ce sera le tour 2. Personne ne mettra sa table à jour. Et donc les échanges sont terminés.

Temps 3 : C’était trop beau !

L'algorithme vu au dessus est relativement simple, seulement il a un bug : il peut lui arriver de créer des cycles. Pour s’en rendre compte, vous pouvez disposer les participant·e·s selon le schéma de réseau suivant :

 

Sans surprise, les tables de routage sont comme cela : 

Simplement, dans ces tables, chacun pousse les messages vers son ou ses voisins, façon “chenille”. Mais voilà que le réseau évolue, et prend maintenant cette forme :

Nous allons voir que, dans ce cas, C a perdu sa connexion à D mais… les routeurs A et B, ne vont pas s’en rendre compte ! Finalement, tout le monde va croire que D est toujours connecté dans le réseau.

Alors D serait le routeur fantôme de ce réseau ?

C’est un peu ça… Voyons le déroulement.

Après le changement de connexions, tout le monde met à jour sa table en fonction des voisins qui sont toujours accessibles, qui sont nouveaux ou qui ont disparu, comme suit :

En fait A a une nouvelle connexion et va envoyer sa table à tous :

B s'en moque, il a déjà des connexions vers tout le monde et ses voisins sont là, il ne change rien. C a perdu sa connexion vers D, il supprime donc D de sa table, et il reçoit la table de A, du coup il note dans sa table qu'il a un moyen de joindre D en passant par A. La table de C devient :

Comme C vient de modifier sa table, il la renvoie à tous. Mais plus personne n’a de modification à faire. D, lui, n’a personne à qui envoyer quoi que ce soit. L’algorithme s’arrête. On obtient donc un cycle A-B-C pour envoyer les messages à D et les routeurs ne se rendent pas compte que la connexion est perdue :

 Qu’est-ce qu’on peut faire ?

Une première solution, simple à mettre en pratique, consiste à compter le nombre de routeurs par lesquels un message est passé. S’il passe par trop de routeurs, alors il est détruit.

Ok… c’est un peu brutal comme solution (et pourtant, elle est bien utilisée en pratique). Il existe une technique complémentaire qui permet d’éviter ces cycles : ajouter le nombre d’étapes nécessaires pour aller à destination.

Example of certificate of achievement
Example of certificate of achievement