Allocation of Clients to Multiple Servers on Large Scale Heterogeneous Platforms

Olivier Beaumont 1, 2 Lionel Eyraud-Dubois 1, 2 Hejer Rejeb 1, 2 Christopher Thraves 1, 2
2 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
Abstract : In this paper, we consider the problem of allocating a large number of independent, equal-sized tasks to a heterogeneous large scale computing platforms, such as BOINC~\cite{boinc} or Folding@home~\cite{folding}. We model the platform using a set of servers (masters) that initially hold (or generate) the tasks to be processed by a set of clients (slaves). All resources have different speeds of communication and computation and we model contentions using the bounded multi-port model. Under this model, a processor can be involved simultaneously in several communications, provided that its incoming and outgoing bandwidths are not exceeded. This model corresponds well to modern networking technologies, but for the sake of realism, another parameter needs to be introduced in order to bound the number of simultaneous connexions that can be opened at a server node. We prove that unfortunately, this additional parameter makes the problem of maximizing the overall throughput (\ie the fractional number of tasks that can be processed within one time-unit) NP-Complete. This result is closely related to results on bin packing with splittable items and cardinality constraints. On the other hand, we also propose a polynomial time algorithm, based on a slight resource augmentation, to solve this problem. More specifically, we prove that, if $\sdeg_j$ denotes the maximal number of connexions that can be opened at node $\server_j$, then the throughput achieved using this algorithm and $\sdeg_j+1$ is at least the same as the optimal one with $\sdeg_j$. We also provide a dual algorithm for minimizing the maximal number of connexions that need to be opened in order to achieve a given throughput. Finally, we also propose extensive simulations to assess the performance of the proposed algorithm.
Type de document :
[Research Report] RR-6767, INRIA. 2008, pp.17
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger
Contributeur : Lionel Eyraud-Dubois <>
Soumis le : jeudi 11 décembre 2008 - 15:19:12
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : jeudi 11 octobre 2012 - 13:21:13


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00346394, version 1



Olivier Beaumont, Lionel Eyraud-Dubois, Hejer Rejeb, Christopher Thraves. Allocation of Clients to Multiple Servers on Large Scale Heterogeneous Platforms. [Research Report] RR-6767, INRIA. 2008, pp.17. 〈inria-00346394〉



Consultations de la notice


Téléchargements de fichiers