grant : Grid with ants - répartition de charge

Grant propose la mise en oeuvre d'une grille de calcul à l'aide d'algorithmes biomimétiques. Cette grille de calcul étant conçue pour être mise en oeuvre sur de grands réseaux voir internet lui même doit avoir une forte robustesse et une bonne capacité d'adaptation. Les algorithmes biomimétiques sont de bons candidats pour répondre à ces besoins : ils sont conceptuellement adaptatifs et capables de fonctionner à partir d'informations incomplètes (erreurs de mesures, latances) ce qui est en pratique toujours le cas en situation réelle.

La grille est composée d'un ensemble de noeuds qui forment un réseau connexe. Chaque noeud ne permet d'atteindre qu'un nombre limité de noeuds voisins mais il doit exister au moins un chemin pour se rendre d'un noeud quelconque à un autre suivant cette relation de voisinage.

Chaque noeud peut soumettre des tâches à un autre qui lui pourra les relayer à un troisième, etc... Le problème fondamental de la répartition de charge devient assimilable à du routage. Une version biomimétique en est la collecte de nourriture par les fourmis : les noeuds sont des réservoirs plus ou moins importants de nourriture et les taches à faire éxecuter par les noeuds sont des fourmis.

L'ambition d'une grille déployable sur internet implique la capacité d'y accueillir des noeuds de toutes sortes : machines et systèmes d'exploitation variés. Ceci nous pousse à choisir des technologies portables pour le transport des requêtes et l'execution des tâches :

• Java : pour couvrir le besoin de protabilité binaire, chaque tâche doit être exécutable sur n'importe quel type de noeud.
• xmlrpc : protocole de communication "passe-partout", qui repose sur l'échange de messages XML via le protocole HTTP.

Le principal but de notre de grille et évidemment de réaliser les tâches confiées. Ces tâches sont des programmes tout à fait normaux dotés des points d'entrés necessaires à leur prise en charge par la grille. Par analogie avec les "servlet" et les "applets", nous avons baptisé de telles tâches "tasklets".

La première brique essentielle à la grille est le système de répartition de charge. Afin de proposer un service qui offre les même qualités de robustesse que l'internet lui-même il faut mettre en place un système capable de s'adapter aux aléas du réel et à l'incomplétude de sa connaissance. Le système de répartition de charge doit lui-même être réparti afin d'éviter les risque de saturation et de dysfonctionnement de l'ensemble de la grille qui serait du à ce seul point critique. La grille doit pouvoir résister autant que possible à la défaillance de quelques noeuds qui la constituent.

De plus la nature hétérogène de l'environnement ciblé ne permettra sans doute pas d'avoir une bonne connaissance à tout instant de l'état de chaque noeud :

• Les mesures de performance seront toujours plus ou moins dépendantes de la nature du noeud observé. Il est toujours difficile d'avoir de bon référents qui permettraient de comparer objectivement deux noeuds quelconques.
• L'information utilisé pour déterminer à quel noeud affecter une tâche est en pratique toujours incomplète. Elle est basée sur une ou plusieurs mesures instantanées que le temps de transport réseau rend obsolète dès leur transmission. En outre, la connaissance du passé n'est en soit pas utile directement, on souhaiterai idéalement connaitre l'état à venir qui n'est évidemment que partiellement prédictible.
• Une bonne répartition de charge devrait également prendre en compte la nature des tâches. Une tâche sera d'autant mieux affectée qu'on a une bonne connaissance des ressources nécessaires à sa réalisation. Une telle connaissance ne pourra être obtenue que pour des tâches totalement isolées, c'est à dire n'ayant aucune interaction avec des éléments exterieurs (intéraction avec un opérateur, lecture/écriture de flux réseaux, taille des données à traiter non connue à priori).

Devant l'impossibilité pratique de collecter l'information nécessaire à une affectation idéale, un système adaptatif capable de faire des choix judicieux à partir d'observation incomplètes et/ou dégradées doit être en mesure d'affecter les tâches en vue d'optimiser l'utilisation des ressources disponibles.

Les algorithmes biomimétiques visent à simuler certains comportements du vivant pour en extraire la capacité d'adaptation à des situations changeantes et cela avec une perception parfois très limitée. Chaque être vivant doit résoudre quotidiennement des situations difficilement prévisible uniquement à l'aide d'information partielles. Le problème de la répartition de charge dans un contexte hétérogène et généraliste (i.e. les tâches à soumettre ne sont pas connues à l'avance donc il n'est pas possible de planifier leur réalisation).

La grille ne devant pas être commandée par un point central critique, nous nous interesserons plus particulièrement aux systèmes d'intelligences collectives. De tels systèmes sont composés de nombreux éléments très simples dont le comportement individuel ne présente aucun trait d'intelligence voire même un certaine bêtise. Mais lorsqu'ils sont déployés en nombres il émerge de leurs intéractions un comportement général qui paraît intelligent, ou tout du moins suffisament évolué pour résoudre des problème complexes [R1]. L'exemple le plus célèbre est la fourmilière : chaque fourmis a un comportement suffisament simple pour être assez facilement modélisé mais la colonie est capable de s'organiser pour affronter les aléas du monde dans lequelle elle est plongée.

Tous les noeuds de la grille sont donc d'un point de vue fonctionnel strictement identiques. Chacun est capable de prendre en charge le traitement d'une tâche ou de relayer une requête vers un autre noeud. Chaque noeud connaît un nombre limité de noeud voisin et la répartition de charge agit localement pour déterminer à quel noeud confier une requête : soi-même ou l'un des noeuds voisins connus. Evidemment le noeud choisi, voyant arriver la requête fait de même et éventuellement dirige lui-même la demande vers un troisième noeud, et ainsi de suite. Affecter une tâche à un noeud dans un tel réseau s'apparente à du routage, on parcourt le réseau noeud par noeud jusqu'à la destination avec la particulirité suivante : dans notre cas la destination n'est pas connue à priori.

Le modèle des fourmis à la recherche de nourriture a déjà été appliqué avec succès au routage adaptatif de paquets dans un réseau [R2]. Il est transposable à la répartition de charge dès que celle ci peut également être traitée comme un problème de routage. La non connaissance de la destination pour chaque requête ne pose pas de problème puisque le modèle utilisé répond au même critère en réalité : les sources de nourriture ne sont connues pas connues des fourmis. Elles sont découvertes au fur et à mesures et apparaissent ou disparaissent selon des événements non maîtrisés.

Le réseau de noeuds constitue l'environnement dans lequels les fourmis sont plongées. Les fourmis à la recherche de nourritures sont les taches à la recherche d'un processeur pour être éxécutées. Les fourmis parcours d'abord au hasard le réseau jusqu'à aboutir à un noeud qui les accepte. Lorsque le travail est terminé, le chemin ayant permis d'atteindre le noeud est marqué. Ce marquage plus ou moins éphémère servira ensuite aux autres fourmis à trouver un chemin menant à un processeur dans le réseau. Afin de répartir efficacement la tache, le marquage doit être proportionnel à la quantitié de nourriture, c'est à dire à la puissance de calcul disponible sur un noeud. Si un noeud devient trop chargé, les taches-fourmis en reviennent moins rapidement, le marquage vers ce noeud s'attenue et il apparaît alors comme un moins bon candidat.

Tout le problème de la répartition de charge se réduit maintenant à une gestion appropriée du marquage des liens inter-noeuds. Ce marquage peut être élémentaire. Un incrément fixe pour chaque terminaison de tâche est suffisant pour un renforcement des routes menant à de bons noeuds. Il est toutefois possible d'accélérer l'apprentissage du réseau en utilisant un marquage lié à la puissance constaté. Ainsi les incidences de situations trompeuses alétoires (par exemple tâche très courte affecté à un mauvais noeud) seront limitées. Le problème n'est pourtant pas trivial : il n'y a pas d'indice de puissance absolue : il est déjà difficile de classer des processeurs selon un axe de puissance unique. La mesure de la puissance réelle disponible peut s'appuyer sur un ou plusieurs de ces critère :

• longueur de la route : cette mesure permet de privilégier le noeuds les plus proche de soi (selon la topologie de routage qui peut être différente de la topologie physique du réseau.)
• Taux d'occupation du processeur : cette information est accessible sur la plupart des plateforme mais son acquisition est spécifique à chacune.
• Temps d'éxécution : il s'agit de la mesure la plus impartiale et la plus significative pour l'utilisateur. Elle devrait toutefois être pondérée par la quantité de code sinon toute tache un temps soi peu importante signalerait avoir été éxécutée sur un mauvais noeud.
• Quantité de code éxécuté à l'issu de la tache : permet de reconsidérer avantageusement les critères précédent. Ainsi le calcul de consommation des ressources sera plus juste en tenant compte du travail réalisé. Toutefois se posent les problème de l'unité (le nombre de bytecode java est un bon candidat relativement neutre) et son acquisition requière que chacque tâche soit instrumentée à cet effet.

La fonction d'évaluation n'a toutefois pas besoin d'être totalement absolue sur tout le réseau, il suffit qu'il le soit pour tous les éléments pris en compte lors du routage d'une tâche. La fonction d'évaluation peut donc être locale à chaque noeud routeur si elle est appliquée de façon identique à tous les noeuds connus au niveau d'un noeud routeur.

De plus ces multiples critères d'évaluation permettent d'aller plus loin qu'une simple optimisation de l'affectation des noeuds. Il est aussi possible d'optimiser la topologie du réseau par la recherche des meilleurs chemins d'accès à la puissance de calcul.

Chaque noeud ne connais qu'un certain nombre d'autres noeuds auquel il est capable de relayer des requêtes. Cette relation de voisinage constitue une topologie qui selon ces caractéristiques aura une certaine influance sur les perforamances (robustesse, réactivité, ...) de la grille.

• arbres : Si l'arbre est bien balancé, cette topologie permet d'atteindre chaque noeud de façon unique avec un nombre d'intermédiaires maitrisé. Cependant la défaillance d'un seul intermédiaire coupe l'accès à toute une branche de l'arbre. De plus le noeud racine est un goulot d'étranglement potentiel puisque il doit relayer toutes les requêtes.
• réseau maillé : un réseau maillé, s'il peut augmenter considérablement la combinatoire d'accès au noeud apporte une certaine robustesse dès qu'il existe plusieurs noeuds d'accès ainsi que plusieurs chemins possibles pour atteindre chaque noeud. De cette façon les incidences de la défaillance d'un noeud sont limitées aux tâches en cours d'execution sur celui-ci.

Dans cette première phase d'évaluation de l'algorithme de routage des taches, l'implémentation se réduit à un environnement hétérogène simulé sur un unique poste : ceci essentiellement pour des raisons économiques et pratiques. Le travail sera transposable directement à un véritable environnement réparti par une simple révision de l'implémentation des interfaces de communication entre noeud.

Le noeud de simulation est un noeud fonctionnel qui ajoute un délai au temps de traitement de la tache. Ce délai est fixe pour un noeud donnée mais varie d'un noeud à l'autre. Il simule la force de calcul plus ou moins importante d'un noeud par un retard artificiel de la fin de traitement d'une tache. Il s'ajoute un délai supplémentaire proportionnel à la charge du noeud, i.e. le nombre de tache en cours d'execution sur le noeud. Ce dernier point simule une baisse de performance en fonction du nombre de taches simultanément en execution.

Les taches soumises sont également un délai attribué aléatoirement afin de tester la répartition de taches hétérogène dont le temps de traitement n'est pas connu à priori. La performance globale de la grille sera simplement mesuré par l'écart entre le temps d'exécution réel de toutes les taches et la somme des délais de chaque tache qui représente le temps d'exécution optimal.

Le réseau testé contient 30 noeuds repartis sur une topologie arborescente : toutes les taches sont soumises à un premier noeud racine qui réparti sur une couche de 5 noeuds routeurs qui eux même répartissent chacun sur 6 noeuds de calcul.

Il y a trois types de noeuds : fort, moyen et faible, soit trois valeur de temporisation fixe possibles. Chaque branche finale ne contient que deux types de noeuds : soit faible/moyen, soit moyen/fort.

Notre répartitions de charge sera confronté à trois autres système à titre de comparaison :

• Sélection purement aléatoire : il est bon de vérifier que le système proposer est capable de faire mieux que le hasard.
• "Round Robin" : chaque noeud est choisi successivement sans tenir compte de la charge ou des performances. Il s'agit du système de répartition le plus simple à mettre en oeuvre et qui l'est effectivement très souvent. Il est très efficace dans un environnement ou noeuds et taches sont homogènes.
• Sélection du meilleur noeud à l'instant de l'affectation : choisir le meilleur noeud le moins chargé. Cette méthode est très simple et permet des performances proche de l'idéal. Ce n'est pas la meilleur car il faudrait en réalité considérer le meilleur noeud pour toute la réalisation de la tache à affecter donc être capable d'anticiper les variations de charge de tout les noeuds. Cette méthode, si elle est un excellent élément de comparaison n'est pas utilisable dans un cas réel dès que la charge induite par l'éxecution d'une tache n'est pas connue. Ce n'est pas un bon système de répartition de charge dès que l'indice de charge pris en compte ne représente pas bien la charge réelle.