TD 5 Réseaux pair à pair (suite)

Cours "Protocoles de réseaux" de majeure d'informatique 2 par Walid Dabbous.

Ce TD explore plus avant les notions de routage dans les réseaux pair à pair. Il est nécessaire d'avoir au moins fait la question 1 du TD 4.

Exercice 1. Routage efficace

Pour router efficacement les messages PING, PUBLISH et GET, il faut rajouter des raccourcis à la structure d'anneau qui sert de base au routage. Pour cela chaque noeud va tenir à jour une table de voisins. Si x est son ID, le noeud va stocker les informations d'ID, d'adresse IP et de port des noeuds gérants les IDs x+1, x+2, x+4, x+2^3,..., x+2^(m-1). Les premiers IDs sont gérés par le noeud lui-même. On pourra utiliser l'indice indicePremVois du premier indice tel que x+2^indicePremVois n'est pas géré par le noeud lui-même. Les noeuds gérant les IDs x+2^k sont appelés voisins. Le noeud gérant x+2^k est celui dont l'intervalle contient cet ID. Les voisins sont découverts grâce à des messages PING. On pourra stocker ces voisins dans un tableau de Peer de longueur m. Seuls les indices supérieurs à indicePremVois correspondront à de réels voisins.

Pour router un message vers le noeud en charge de destID, un noeud doit maintenant le passer à son voisin de plus grand ID inférieur à destID. Le choix des voisins assure qu'un message transitera en moyenne par O(log N) noeuds (où N est le nombre de noeuds dans le réseau pair à pair). Cependant, si destID est inférieur à l'ID du premier voisin du noeud, on applique la règle du TD précédant (attention, le premier voisin du noeud n'est pas forcèment son successeur).

Une fois qu'un noeud s'est inséré dans l'anneau, il émet un PING pour chacun des IDs définissant ses voisins (sauf pour les IDs inférieurs à celui de son successeur). Si des PING_REP sont perdus, on n'essayera pas de réémettre les PINGs correspondants, mais il faudra garder la table des voisins cohérente de sorte que le routage fonctionne toujours. Remarquons que l'insertion de nouveaux noeuds par la suite peut rendre la table de voisinage d'un noeud obsolète mais ne remettra pas en cause la validité du routage. (L'efficacité peut toutefois en pâtir.)

Exercice 2. Gérer les départs de noeuds

Pour que le réseau pair à pair fonctionne toujours, il est primordial que l'anneau formé par les liens de noeud à successeur ne soit jamais brisé. Pour partir, un noeud d'ID x doit donc d'abord informer son prédécesseur (c'est à dire le noeud dont il est le successeur) de son départ iminent. Pour cela, créer un nouveau type de message : LEAVE (codé par la valeur 7). Le champ destID est mis à x-1 et le message est routé comme un PING. Le noeud est donc assuré que son message va arriver à son prédecesseur même s'il ne le connaît pas. Le prédecesseur, quand il reçoit le message, prend alors le successeur du noeud comme nouveau successeur.

Les informations qui était stockées par le noeud qui quitte le réseau sont perdues. Pour faire persister une donnée publiée dans le réseau, il faudrait la republier régulièrement. On ne traitera pas la gestion des données pour se concentrer sur les problématiques plus liéées au routage.

Pour signifier à un noeud qu'il doit quitter le réseau, on créera de plus un type de message KILL. Quand un noeud reçoit un message de type KILL avec son ID comme destID, il doit quitter le réseau. Pour éviter des attaques malveillantes, vous pouvez prendre un nombre secret plus grand que 256 pour coder ce type de message dans le champ type.

Exercice 3. Les départs de voisins

Pour gérer le départ de ses voisins, un noeud doit "pinguer" régulièrement les IDs définissant ses voisins. Un noeud doit envoyer un PING à chaque voisin toutes les PING_VOISIN_PERIOD=3 secondes. Si aucun PING_REP n'a été reçu d'un voisin dans PING_VOISIN_TIMEOUT=9 dernières secondes, le voisin est considéré comme parti. Pour le cas particulier du successeur, il faudra toujours stocker le successeur de celui-ci pour pouvoir réagir à la disparition du successeur.

Pour gérer ces actions régulières, il faut rendre le socket non bloquant en reception (méthode DatagramSocket.setSoTimeout()). Pour chaque voisin et pour le successeur, on stockera la date du dernier envoi d'un PING vers lui et la date de reception d'un PING_REP de sa part (utiliser java.util.Date.getTime()). A chaque itération de run, il faut comparer toutes ces dates à l'heure courante pour voir s'il ne faut pas envoyer un PING ou supprimer un voisin.

Pour aller plus loin, essayez de rendre votre protocole de réseau pair à pair robuste vis à vis de toutes les situations incongrues qui pourrait se produire. On peut par exemple imaginer qu'un nouveau noeud émet un PING pour s'insérer dans l'intervalle géré par un noeud n qui lui renvoie un PING_REP, et juste à ce moment là (avant le JOIN), le successeur de n décide de partir. Identifier et régler ce bug possible. Il est primordial qu'un noeud ait toujours un successeur valide. En dernier recours, si un noeud n'a plus de successeur, il peut essayer de prendre un voisin comme successeur, voire n'importe quel noeud dont il peut avoir connaissance et dont l'ID lui semble le plus proche possible du sien.

Une approche générale consiste à supposer que de toute manière il risque d'arriver des situations complexes qui risquent de déconstruire l'anneau. On peut donc essayer d'introduire des mécanismes pour réparer l'anneau si on détecte un problème. Par exemple, on peut faire en sorte qu'un noeud puisse détecter s'il y a deux noeuds qui le prennent pour successeur. Dans ce cas il pourra envoyer un message à l'un pour qu'il prenne l'autre comme successeur (par exemple un faux message JOIN de l'autre noeud).


Sujet proposé par Laurent Viennot Last modified: Sat Feb 8 22:14:47 CET 2003