Online Allocation of Splitable Clients to Multiple Servers on Large Scale Heterogeneous Platforms

Abstract

Dans cet article, nous considérons l'allocation dynamique (online) d'un très grand nombre de tâches identiques et indépendantes sur une plate-forme maîtres-esclaves. Initialement, plusieurs nœuds maîtres possèdent ou génèrent les tâches qui sont ensuite transférées et traitées par des nœuds esclaves. L'objectif est de maximiser le débit (i.e., le nombre fractionnaire de tâches qui peut être traité en une unité de temps, en régime permanent, par la plate-forme). Nous considérons que les communications se déroulent suivant le modèle multi-port à degré borné, dans lequel plusieurs communications peuvent avoir lieu simultanément sous réserve qu'aucune bande passante ne soit dépassée et qu'aucun serveur n'ouvre simultanément un nombre de connections supérieur à son degré maximal. Sous ce modèle, la maximisation du débit correspond au problème Maximum-Througput- Bounded-Degree (MTBD) qui a été analysé dans~\cite{beaumont08}. Il a été montré que le problème est NP-Complet au sens fort mais qu'une augmentation de ressources minimale (de 1) sur le degré maximal des serveurs permet de le résoudre en temps polynomial. Dans cet article, nous considérons une extension de MTBD à la situation plus réaliste, dans le contexte des plates-formes de calcul à grande échelle, dans laquelle les nœuds esclaves rejoignent et quittent dynamiquement la plate-forme à des instants arbitraires (problème online MTBD). Nous montrons tout d'abord qu'aucun algorithme complètement à la volée (c.-à.-d. qui n'autorise pas les déconnections) ne peut conduire à un facteur d'approximation constant, quelle que soit l'augmentation de ressources utilisée. Ensuite, nous montrons qu'il est en fait possible de maintenir à tout instant la solution optimale (avec une augmentation de ressource additive de 1) en ne réalisant à chaque modification de la plate-forme qu'une déconnection et qu'une nouvelle connection par maître.