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.
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/inria-00346394
Contributor : Lionel Eyraud-Dubois <>
Submitted on : Thursday, December 11, 2008 - 3:19:12 PM
Last modification on : Tuesday, May 7, 2019 - 11:42:03 AM
Long-term archiving on : Thursday, October 11, 2012 - 1:21:13 PM

File

RR-6766.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00346394, version 1

Citation

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⟩

Share

Metrics

Record views

395

Files downloads

351