Algorithmique de la mobilité

↑ Accueil du cours


Routage au plus court dans les réseaux périodiques

Dans cette leçon, on suppose que les noeuds se déplacent périodiquement en tournant le long d'une trajectoire cyclique. Ces mouvements induisent l'apparition et la disparition de liens (eux-même périodiques) entre les noeuds. L'objectif principal du TP est que les noeuds apprennent l'empreinte du réseau, c'est à dire l'union de tous les liens (à travers le temps). Cela se fera en s'échangeant des messages de proche en proche pour partager les informations sur notre voisinage. Une fois l'empreinte connue, on sélectionne un noeud source et un noeud destination, et le noeud source doit envoyer un message au noeud destination en utilisant un chemin temporel (c'est à dire un chemin à travers l'espace et le temps).

Mouvement

On partira d'un type de noeud très simple pour générer les mouvements :

public class CircleNode extends Node{
    double angle;
    public void onStart() {
        angle = (Math.random() > 0.5) ? 0.1 : -0.1;
    }
    public void onClock() {
        setDirection((getDirection()-angle)%(2.0*Math.PI));
        move(2);
    }
}

Q1. Testez cette classe depuis votre méthode main.

Apprentissage distribué de l'empreinte

Dans les questions ci-dessous, il est interdit d'utiliser onLinkAdded et onLinkRemoved. On détectera les voisins uniquement par l'envoi de messages réguliers (appelés beacons ci-dessous).

Q1. À chaque top d'horloge, chaque noeud envoie un beacon en mode sendAll.

Q2. Grâce aux beacons, chaque noeud doit apprendre la liste de ses voisins "temporels" (noeuds qu'il croise au cours du temps, autrement dit ses voisins dans l'empreinte).

Q3. Sachant qu'un noeud modifie son angle de 0.1 radian à chaque étape, combien d'étapes faut-il pour que son angle reviennent (à peu près) au point de départ ? Note : Cela coincide aussi avec le fait de faire un tour complet !

Q4. Afin de piloter plus finement votre exécution, vous pouvez faire en sorte que la topologie se mette en pause immédiatement (tp.pause() juste en dessous de tp.start() dans votre main). Ainsi, lorsque vous lancez votre programme, vous pouvez placer vos noeuds sans qu'ils démarrent, puis démarrer l'exécution globalement via le menu contextuel (Pause or resume execution).

Q5 Après combien d'étapes (tops d'horloge) un noeud est-il sûr de connaître tous ses voisins temporels ? Le fait que tous les noeuds aient la même période ici est déterminant !

Q6 On souhaite maintenant partager les informations de voisinage de sorte que chaque noeud apprenne la carte complète du réseau (de manière complètement distribuée). Ainsi, une fois qu'un noeud connait la liste de ses voisins, il partage cette information avec ses voisins. Plus généralement, chaque noeud partage toute l'information qu'il connait en permanence, de sorte que les noeuds finissent par connaitre toute l'empreinte. Quelle structure de donnée serait appropriée pour stocker ce type d'information ? Vous pouvez m'appeler pour valider votre proposition avant de la coder.

Q7 Un noeud peut-il détecter lorsqu'il connait l'ensemble de l'empreinte ? Si oui, comment ?

Q8 Détectez-le et vérifiez cela en affichant le résultat dans la sortie standard pour l'un des noeuds (par exemple, lorsqu'on le sélectionne).

Q9 (bonus). Créez une autre Topology et un autre JViewer permettant d'afficher dans une autre fenêtre l'empreinte calculée par un des noeuds. Attention, un objet Node ne peut appartenir qu'à une topologie, il faudra donc créer des copies de vos noeuds pour cette nouvelle topologie.

Routage temporel au plus court

Q10. En pausant l'exécution, l'utilisateur doit pouvoir sélectionner un noeud source (src) et un noeud destination (dest). Utilisez onSelection() deux fois et des couleurs appropriées pour indiquer le rôle.

Q11. Lorsque l'exécution redémarre, faites en sorte d'acheminer (router) un message depuis le noeud src jusqu'au noeud dest en utilisant le moins de sauts possibles (grâce à votre connaissance de l'empreinte. Vous pouvez utiliser la primitive sendRetry(), qui s'avère très pratique ici. Vous avez le choix, entre (1) pré-calculer l'ensemble du chemin dès le début, ou (2) calculer uniquement le saut suivant, et recommencer.

Q12 (bonus). Revisiter les questions du TP, cette fois avec des périodes différentes sur les noeuds, par exemple en remplaçant le paramètre de setDirection() par un angle aléatoire (choisi une fois au début de l'exécution).