Mécanismes de recherche de services extensibles pour les environnements de grilles de calcul
Institution:
BesançonDisciplines:
Directors:
Abstract EN:
The aim of Grid computing is to share computing resources. Users should find efficiently the resources that they need. To do it, we propose to connect the resources with an overlay network and to use a flooding search algorithm. Overlay networks are usually formed with a graph or a tree. Trees use an optimal number of messages but suffer of bottlenecks which reduce the number of simultaneous search that can be done. Graphs use more messages but support an higher number of simultaneous searches. We propose a new topology which uses an optimal number of messages like trees and does not have any bottleneck like graphs. If every node of a tree is a computer, some computers are leaves which receive messages and the others are intermediate nodes which forward messages. We distribute the intermediate nodes role between every server in a way where every server have the same roles. This new tree structure is build recursively: every server is a leaf and intermediate nodes are complete graphs of their children. We show that such kind of tree can be build and that it is possible to run tree traversal on it. We also show that the load is fairly shared between the servers. As a result, this structure has better performances than the tree and the graph in search speed term and in load term.
Abstract FR:
Deux topologies sont couramment utilisées pour former ces graphes de communication : les arbres et les graphes pseudo-aléatoires. Si les arbres permettent de réaliser des parcours avec un nombre de messages optimal, ils souffrent de la présence de noeuds de contention qui limitent le nombre de recherches pouvant être effectuées de manière simultanée. Quant aux graphes pseudo-aléatoires, bien qu'ils utilisent plus de messages, ils supportent une charge plus importante tout en fournissant des recherches plus rapides. La solution proposée est une alternative entre les arbres et les graphes. Elle emprunte aux arbres leur structure hiérarchique pour minimiser le nombre de messages et aux graphes l'égalité de leurs noeuds. Si chaque noeud de l'arbre est un serveur, certains serveurs sont des feuilles se contentant de recevoir des messages. Les autres serveurs sont des noeuds intermédiaires acheminant les messages de recherche. Afin de mettre tous les serveurs sur un pied d'égalité, nous distribuons le rôle des noeuds intermédiaires entre plusieurs serveurs. Nous avons montré qu'il est possible de construire un tel arbre qui réalise effectivement les recherches par voisinage à l'aide d'algorithmes de parcours d'arbre tout en répartissant la charge d'une manière similaire aux parcours de graphe. Il en résulte de meilleures performances concernant la vitesse de recherche et la charge supportée quel que soit le nombre de serveurs et la probabilité de trouver une offre.