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.
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.)
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.
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).