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

Olivier Beaumont 1, 2, 3, 4 Lionel Eyraud-Dubois 1, 4 Hejer Rejeb 1, 4 Christopher Thraves 1, 4
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
INRIA Futurs, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
4 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Résumé : 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.
Complete list of metadatas

Cited literature [3 references]  Display  Hide  Download

https://hal.inria.fr/inria-00384569
Contributor : Chrsitopher Thraves Caro <>
Submitted on : Friday, May 15, 2009 - 2:41:24 PM
Last modification on : Tuesday, May 7, 2019 - 11:42:03 AM
Long-term archiving on : Monday, October 15, 2012 - 10:31:05 AM

File

OCRalgotel.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00384569, version 1

Citation

Olivier Beaumont, Lionel Eyraud-Dubois, Hejer Rejeb, Christopher Thraves. Online Allocation of Splitable Clients to Multiple Servers on Large Scale Heterogeneous Platforms. AlgoTel, 2009, Carry-Le-Rouet, France. ⟨inria-00384569⟩

Share

Metrics

Record views

356

Files downloads

326