Skip to Main content Skip to Navigation

Extended Version: Online Allocation of Splitable 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 the online allocation of a very large number of identical tasks on a master-slave platform. Initially, several masters hold or generate tasks that are transfered and processed by slave nodes. The goal is to maximize the overall throughput achieved using this platform, i.e., the (fractional) number of tasks that can be processed within one time unit. We model the communications using the so-called bounded degree multi-port model, in which several communications can be handled by a master node simultaneously, provided that bandwidths limitation are not exceeded and that a given server is not involved in more simultaneous communications than its maximal degree. Under this model, it has been proved that maximizing the throughput (MTBD problem) is NP-Complete in the strong sense but that a small additive resource augmentation (of 1) on the servers degrees is enough to find in polynomial time a solution that achieves at least the optimal throughput. In this paper, we consider the reasonable setting where the set of slave processors is not known in advance but rather join and leave the system at any time, i.e., the online version of MTBD. We prove that no fully online algorithm (where nodes cannot be disconnected even if they do not leave the system) can achieve a constant approximation ratio, whatever the resource augmentation on servers degrees. Then, we prove that it is possible to maintain the optimal solution at the cost of at most one change per server each time a new node joins and leave the system. At last, we propose several other greedy heuristics to solve the online problem and we compare the performance (in terms of throughput) and the cost (in terms of disconnexions and reconnections) of proposed algorithms through a set of extensive simulation results.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Chrsitopher Thraves Caro Connect in order to contact the contributor
Submitted on : Friday, May 15, 2009 - 12:52:30 PM
Last modification on : Friday, December 3, 2021 - 3:38:04 PM
Long-term archiving on: : Monday, October 15, 2012 - 10:30:44 AM


Files produced by the author(s)


  • HAL Id : inria-00384475, version 1



Olivier Beaumont, Lionel Eyraud-Dubois, Hejer Rejeb, Christopher Thraves. Extended Version: Online Allocation of Splitable Clients to Multiple Servers on Large Scale Heterogeneous Platforms. [Research Report] 2009. ⟨inria-00384475⟩



Record views


Files downloads