Extended Version: Online Allocation of Splitable Clients to Multiple Servers on Large Scale Heterogeneous Platforms - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2009

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

Résumé

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.
Fichier principal
Vignette du fichier
Onlinealgo.pdf (205.19 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00384475 , version 1 (15-05-2009)

Identifiants

  • HAL Id : inria-00384475 , version 1

Citer

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⟩
209 Consultations
72 Téléchargements

Partager

Gmail Facebook X LinkedIn More