Projet d'architecture et de programmation réseau


Ce document est accessible à partir de l'url http://igm.univ-mlv.fr/~duris/RESEAU/archiProg.html. Il pourra être complété ou mis à jour à cet URL.


Cette année, deux projets au choix sont proposés en Master 1.

Conscient du peu de temps qui vous est imparti pour réaliser le projet, et de la difficulté d'appréhender les problématiques de Map/Reduce, le sujet NetSnake, plus "classique", vous est donc proposé. Néanmoins, certain d'entre vous ayant déjà commencé à réfléchir à Map Reduce, ce sujet est maintenu et le choix vous est laissé de réaliser l'un ou l'autre.

Quel que soit le projet choisi, vous devrez le rendre au plus tard le lundi 3 Avril 2006 avant midi, par mail à duris@univ-mlv.fr. Le projet est à réaliser par binômes (de deux personnes). Le format du rendu est toujours le même, quel que soit le projet : il doit s'agir d'une archive ZIP (nom de fichier constitué des noms des deux membres du binôme). Dans cette archive, on doit trouver, au minimum :



Map Reduce : Calculs répartis

Le but du projet

Le but de ce projet est de fournir une implantation en Java d'une architecture de répartition de calcul sur un ensemble de machines. Le point de départ de la réflexion est l'article publié par des chercheurs de Google : Map Reduce: Simplified Data Processing on Large Clusters. Il est bien évident qu'il ne s'agit pas d'implanter la totalité des mécanismes décrits par cet article, mais un sous-ensemble restreint de ces fonctionalités, où les machines d'un réseau local pourraient jouer le rôle de cluster.

Dans une très grossière approximation, l'idée véhiculée par cet article est qu'un certain nombre de calculs à réaliser sur une quantité de données importante peuvent être exprimés sous la forme de deux opérations fondamentales, Map et Reduce, et que cela peut permettre de répartir et de paralléliser ces calculs.

Toujours très grossièrement, l'idée est qu'étant donné un ensemble de machines (workers) disposées à exécuter des tâches qu'on leur soumet, et étant donnée la spécification sous la forme Map Reduce d'un calcul sur une très grande quantité de données, il est possible de procéder ainsi :

  1. l'utilisateur ou l'application choisit une machine maître (master) disponible, pour être responsable de la totalité de ce calcul
  2. le master "découpe" (split) l'ensemble des données d'entrée du calcul en plusieurs sous-ensembles sur lesquels l'opération de Map pourra être effectuée ; de même, le master utilise des critères d'organisation des données intermédiaires produites par les Map afin de spécifier comment elles devront être collectées, aglomérées par les opérations Reduce pour produire le résultat final.
  3. chacune des tâches Map (map-task) sur une partie des données d'entrée est confiée à une machine disponible.
  4. lorsqu'une machine exécute la map-task que lui a confiée le master, elle produit un ensemble de données intermédiaires, organisées ou regroupées selon des critères communs pour toutes les map-tasks. Ces résultats intermédiaires, organisés selon ces critères, sont stoqués à un emplacement qui est communiqué au master
  5. chacune des tâches Reduce (reduce-task) est confiée à une machine disponible, et le master lui signale chaque emplacement connu de stokage des données intermédiaires qui la concerne
  6. les différentes parties des données intermédiaires produites par les map-tasks correspondant à un même critère d'organisation peuvent alors être prises en compte par les reduce-tasks pour leur appliquer l'opération Reduce, après d'éventuelles opérations de tri de ces données intermédaires
  7. le master est informé de chaque résultat produit par les reduce-tasks et est en charge de les consolider pour produire le résultat global, qui est transmis à l'utilisateur ou à l'application.

L'objectif de ce projet est de modéliser ces opérations de sorte que chaque "machine", qu'elle héberge le master, une map-task ou une reduce-task soit représentée par une application Java qui est en mesure de communiquer avec les autres "machines", soit pour se faire connaître, soit pour se voir confier une tâche ou pour indiquer l'emplacement où elle a stoqué le résultat de l'exécution de sa tâche.

Il s'agit donc d'établir une architecture permettant de réaliser ces fonctionnalités, à l'intérieur de laquelle les différents éléments communiquent à travers le réseau.

Différentes formes de communications doivent être envisagées, et devront être modélisées selon des protocoles qui sont à définir (échanges permettant aux workers d'être répertoriés comme disponibles ou détectés comme ayant une panne, transferts d'informations, qu'elles soient d'entrées, intermédiaires ou correspondant au résultat, transmissions des spécifications de tâches, qu'elles soient de Map, de Reduce ou autre, transmissions de notifications d'état d'avancement de ces tâches, etc.). Sans pouvoir disposer des atouts du système de fichier de Google, GFS, ces communications pourront utiliser les protocoles classiques et devront reposer sur IP, UDP et TCP.

L'intérêt de ce projet réside davantage dans les choix d'architecture et de protocoles que dans l'utilité pratique des logiciels que vous allez développer pour résoudre des problèmes (en réalité, pour une réalisation pertinente de ce genre d'architecture, l'utilisation d'un système de fichier dédié tel que GFS est fondamental). Aussi, plus que dans l'efficacité du traitement des tâches planifiées, vous vous intéresserez à la modularité et la généricité dans la conception et la réalisation de votre projet, et vous pourrez vous contenter de calculs "jouets" tels que le comptage du nombre d'occurrence de chaque mots dans un ensemble de texte ou d'autres exemples simples cités dans l'article de recherche. En revanche, il est clair que votre architecture devra permettre à un utilisateur de spécifier son propre problème selon le schéma Map Reduce, et que vous devrez pour cela lui offir une librairie (API) compatible avec votre architecture.



NetSnake

L'idée

Ce projet a pour but de programmer un jeu de "nibbler" en réseau pour plusieurs utilisateurs, sur un modèle client-serveur. Chaque client peut entrer en communication avec le serveur pour établir une session par laquelle il va recevoir les informations nécessaires à la visualisation d'une zone de jeu (plateau). Cette zone (quadrillage, échiquier) est constituée de plusieurs éléments visualisés de manières distinctes:

Outre d'éventuelles informations initiales de configuration, des commandes de contrôle éventuelles au cours du jeu et des commandes liées à des variantes optionnelles de ce jeu, chaque client se contente de donner des ordres simples de déplacement pour que "son" serpent se déplace à gauche, à droite, en haut ou en bas. En fonction de ces commandes, et de celles de chacun des clients, le serveur doit centraliser les mouvements de chaque serpent et en informer chacun des clients pour rafraîchir leur zone de jeu.

L'objectif de ce jeu, pour chacun des clients, est de faire évoluer son serpent dans la zone de jeu de sorte qu'il consomme un maximum de "miams", pour devenir le plus long possible. Le serpent le plus long encore en vie sur la zone de jeu lorsqu'il n'y a plus de miams est le gagnant. En revanche, un serpent meurt immédiatement s'il se déplace sur une case contenant déjà un "bout" de serpent (que ce soit un bout du même serpent ou d'un autre). Pour les "sorties" de la zone de jeu par un bord, on pourra soit considérer qu'elle est fatale au serpent, soit qu'elle aboutit à une "entrée" à l'opposé de la zone de jeu (qu'on considère alors circulaire).

L'essentiel

La principale problématique de ce projet est le choix du ou des protocoles réseaux à utiliser, et éventuellement à définir. En effet, on devra se poser la question de l'utilisation de TCP ou d'UDP dans l'implantation de NetSnake, en prenant en compte la fiabilité par rapport à la charge réseau occasionnée. On pourra également réfléchir à l'utilisation de groupe de diffusion avec du multicast UDP. Néanmoins, la vitesse de traitement de chaque ordre de déplacement et le rafraîchissement, ainsi qu'une certaine équité d'accès au serveur entre les différents clients doivent être considérés. En particulier, on pourra réfléchir au problème de l'ordre dans lequel les commandes sont émises par rapport à l'ordre dans lequel elles sont traitées.

Pour ce qui est des informations qui transitent entre le serveur et chaque client, un format et un protocole devra être établi. Ces derniers pourront varier en fonction du type d'information: rafraîchissement d'écran, ordre de déplacement, configuration d'un client, mort d'un serpent, etc.

L'accessoire

La partie visuelle de l'application sur le client est accessoire. Même si elle peut avantageusement être réalisée en Java AWT/Swing, il ne faut pas perdre de vue que ce n'est pas le coeur de ce projet. Restez simples et n'y passez pas trop de temps.


© Université de Marne-la-Vallée - Mars 2006