Techniques and tools for communications and dynamic load balancing in networks of workstations

Description

In this thesis, we focus on technics and tools that help in building and optimizing parallel and distributed applications for networks and clusters of workstations. The first problem we study is dynamic load balancing in a strongly heterogeneous environment: an efficient dynamic load balancing strategy requires first to evaluate and compare the availability of each of the workstations and second to find a good matching between this availability and the resources requirements of the applications. For this purpose, we propose an empirical method whose goal is to model the behavior of the compo- nents of a network of workstations according to the workload levels being observed. This method allows the construction of multi-dimensional and multi-criteria workload indices. To put this method in practice, we have developed LoadBuilder, a distributed environment especially intended to drive distributed experiments. The second problem we study is accessing reliable ordered multi-point communication mechanisms and protocols in UNIX operating systems. In order to deal with the communications requirements of distributed applications, we propose an original solution, the MPCFS virtual file system. This file system provides its users a way of (i) creating and managing process groups and (ii) exchanging multi-points messages in these groups. These operations can be achieved easily, through the usual UNIX file and directory operations. We have developed a dynamically loadable module for the Linux 2.0 operating system, that implements a prototype of this file system.

Abstract (French)

Dans cette thèse, nous nous intéressons aux techniques et outils qui permettent de concevoir et d'opti- miser les applications parallèles et réparties sur les réseaux et grappes de stations de travail. Le premier problème abordé est celui de la répartition dynamique de charge en environnement fortement hétérogène : pour répartir dynamiquement et efficacement la charge d'une application répartie, il faut (i) être en mesure d'évaluer et de comparer la disponibilité des différentes machines du réseau et (ii) savoir mettre ces informations en correspondance avec les besoins en ressources des tâches de l'application. Pour cela, nous proposons une méthodologie de modélisation empirique du comportement des éléments d'un réseau de stations de travail face à la charge. Cette méthodologie nous permet de construire des indica- teurs de charge multi-dimensions et multi-critères. Pour mettre cette méthodologie en pratique, nous avons conçu LoadBuilder, une plate-forme répartie d'expérimentation. Le deuxième problème abordé est celui de l'accès à des mécanismes et protocoles de communication multipoints fiables et ordonnés, à partir d'un système d'exploitation UNIX. Pour répondre à ce besoin des applications réparties, nous proposons une solution originale, le sys- tème de fichiers virtuel MPCFS. Ce système de fichiers permet la création de groupes de communication dynamiques et la réalisation de communications multipoints dans ces groupes, au travers de simples manipulations de fichiers et répertoires. Nous avons développé un prototype de ce système, qui peut être chargé dynamiquement dans le noyau du système Linux 2.0.

Additional details