TD 4 Réseaux pair à pair

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

Le but de ce TD et du prochain est de mettre en place un réseau pair à pair. Ce TD est librement inspiré de Chord ("Chord: a scalable peer-to-peer lookup service for internet applications", 2001).

Introduction aux réseaux pair à pair

Après le précurseur Napster, plusieurs véritables réseaux pair à pair ont vu le jour (Gnutella, Kazaa, freenet, ...). Le but de ces réseaux est de partager des fichiers sans reposer sur l'existence d'un serveur central. Tout noeud qui joint le réseau met à la disposition des autres une partie de ses fichiers en espérant en retour pouvoir copier ceux des autres. La difficulté consiste à pouvoir trouver un noeud qui contient un fichier désiré et ce malgré le grand nombre potentiel de noeuds et la dynamique des arrivées et des départs de noeuds.

Un réseau pair à pair peut-être vu comme une table de hachage distribuée qui associe des noms de fichiers à leur contenu : étant un nom de fichier, on veut pouvoir en récupérer une copie. Une manière élégante de résoudre le problème consiste à se ramener à un problème de routage.

La difficulté dans cette stratégie consiste à sélectionner les voisins d'un nouveau noeud de sorte que le nombre de voisins d'un noeud donné reste petit, le diamètre du réseau (c'est à dire la longueur de la plus longue route) soit petit, et qu'il soit possible bien sûr de router, c'est à dire de contacter le noeud en charge d'un identificateur efficacement. Il faut de plus allouer dynamiquement et équitablement l'espace d'adressage des identificateurs : chaque noeud doit gérer à peu près autant d'identificateurs et doit s'adapter aux arrivées et aux départ.

Dans ce TD, nous allons mettre en place une infrastructure similaire à Chord. Pour simplifier, nous nous placeront dans le contexte de la table de hachage distribuée associant des noms à des contenus. Le contenu sera stocké directement sur le noeud en charge de l'identificateur associé au nom et on ne gérera pas les collisions. Les identificateurs seront maniés sous forme de long (8 octets).

Pour commencer, nous oublions la contrainte sur le diamètre du réseau et considérons une structure en anneau. Nous supposerons de plus que les noeuds ayant rejoint le réseau pair à pair ne le quittent plus par la suite, ne tombent pas en panne et qu'il n'y a pas de perte de paquets. Le prochain TD, sur la base de cette première ébauche, sera consacré à la prise en compte du départ possible des noeuds avec une topologie enrichie offrant un diamètre faible.

Voici maintenant quelques considérations techniques :

Exercice 1. Se joindre au réseau pair à pair

Un pair (ou peer en anglais) et donné par son ID, son addresse IP et un numéro de port ou le contacter. On utilisera pour cela la classe minimaliste PeerInfo.java. Chaque membre du réseau créera un socket Datagram sur ce port pour recevoir des messages et en envoyer. Cela vous permet de créer plusieurs membre d'un réseau sur la même machine en leur donnant des numéros de ports différents.

Pour opérer, les noeuds utiliseront 6 types de messages : PING, PING_REP, JOIN, PUBLISH, GET et GET_REP. PING, PING_REP et JOIN sont utilisés pour se joindre au réseau. PUBLISH, GET et GET_REP sont utilisés pour insérer et rechercher des données dans la table de hachage et sont décrits dans l'exercice suivant. Une classe Message.java vous est donnée pour manipuler les messages facilement et vous consacrer sur l'opération pair à pair. On se contentera de l'Annexe A pour comprendre son utilisation. Chaque message aura l'en-tête suivante (une ligne correspond a quatre octets) :

+----+----+----+----+
|  type   |   TTL   |
+----+----+----+----+
|      destID       |
|                   |
+----+----+----+----+
|      fromID       |
|                   |
+----+----+----+----+
|       fromIP      |
+----+----+----+----+
|fromPort |   ZERO  |
+----+----+----+----+
|      succID       |
|                   |
+----+----+----+----+
|      succIP       |
+----+----+----+----+
|succPort |  ZERO2  |
+----+----+----+----+
Décrivons les messages de types PING, PING_REP et JOIN :

Le but de cet exercice est de gérer l'insertion de nouveaux noeuds dans un réseau pair à pair. On pourra partir du squelette Peer.java. Le premier noeud du réseau est seul et son successeur est lui même. java Peer new 1024 permettra par exemple de créer le premier noeud d'un réseau sur le port 1024.

Un nouveau noeud tire un ID au hasard, émet un PING pour rechercher le noeud x en charge de cet ID. Quand il reçoit la réponse il prend pour successeur le successeur de x. Il envoie ensuite directement à x un message JOIN pour lui indiquer son arrivée. x prend alors ce noeud comme successeur. java Peer join 1025 truite 1024 permettra par exemple de créer un pair sur le port 1025 et de le joindre au réseau du pair tournant sur truite sur le port 1024.

Les fonctions suivantes vous sont fournies dans Peer.java :

Il est conseillé d'attraper un minimum d'exceptions et de laisser les autres s'échapper pour pouvoir débuguer plus facilement. Pour mettre au point votre programme, lancer pluiseures fois le programme dans plusieurs fenêtres xterm pour former un petit réseau pair à pair sur votre machine. (Tous les noeuds auront même adresse IP, mais des ports différents, par exemple 1024, 1025, 1026,...)

Pour tester l'anneau que vous formez ainsi, vous pouvez utiliser Visitor.java, en lançant java Visitor checkRing truite 1025 (où truite est une machine sur laquelle tourne un de vos pair et 1025 son port).

Exercice 2. Publier et retrouver une donnée

Rajouter une table de hachage (java.util.Hashtable) dans chaque membre du réseau. Un message PUBLISH est routé comme un PING et contient de plus des données (une chaîne de caractères ici) associées à la clé destID. Le noeud en charge de destID rajoute une entrée (destID, données) dans sa table de hachage. Un message GET est similaire à PUBLISH sauf qu'il ne contient aucune donnée ; le noeud en charge de l'identificateur répond directement à l'originateur par un GET_REP qui contient le même destID que le GET plus la donnée associée. (Une donnée vide indique que l'identificateur n'était pas associé à une donnée.) La donnée est directement codée à la suite de l'entête des messages. Le champs ZERO2 est utilisé pour coder la longueur (en octets) de la donnée. (Les méthodes void Message.setData (String s) et String Message.getData () permettent d'accéder à la donnée contenue dans un message.

Exercice 3. Test d'un réseau

Écrire une classe Visitor similaire à Peer pour envoyer des messages dans un réseau pair à pair dont on connaît un contact (c'est à dire son adresse IP et son port). java Visitor ping IP port destID permettra notamment de lancer un PING sur destID au contact d'adresse IP et de port spécifiés, puis d'afficher le PING_REP reçu en retour. Offrir de manière similaire la possibilité de publier ou de rechercher une donnée associée à une clé. Pour utiliser des clés sous forme de String, on pourra construire un ID à partir d'une clé sous forme de chaîne s avec long id = ((long)s.hashCode ()) << 32.

Proposer de plus un "traceroute". L'idée de traceroute est de découvrir le chemin suivi par un message PING en envoyant un message PING avec même destID et TTL 1, puis un autre avec même destID et TTL 2, et ainsi de suite jusqu'à atteindre le noeud en charge de destID. Pour en déduire le chemin suivi pour atteindre ce noeud final, il faut qu'un noeud intermédiaire (qui n'est pas en charge de destID) réponde au PING si toutefois le TTL vaut 0 (le fonctionnement prévu plus haut prévoyait qu'il jette le message sans le forwarder dans ce cas).

Une solution partielle.

Annexe A. Utilisation de Message.java

Un Message est simplement constitué d'un DatagramPacket (champ packet). La classe possède des fonctions pour modifier ou lire les champs dans la partie données du DatagramPacket (les autres champs de DatagramPacket ne sont pas considérés par cette classe).


Sujet proposé par Laurent Viennot Last modified: Sun Feb 8 22:10:42 CET 2004