Heterogeneous Resource Allocation under Degree Constraints

Olivier Beaumont 1, 2 Lionel Eyraud-Dubois 1, 2 Hejer Rejeb 1, 2 Christopher Thraves 3
1 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 assigning a set of clients with demands to a set of servers with capacities and degree constraints. The goal is to find an allocation such that the number of clients assigned to a server is smaller than the server's degree and their overall demand is smaller than the server's capacity, while maximizing the overall throughput. This problem has several natural applications in the context of independent tasks scheduling or virtual machines allocation. We consider both the offline (when clients are known beforehand) and the online (when clients can join and leave the system at any time) versions of the problem. We first show that the degree constraint on the maximal number of clients that a server can handle is realistic in many contexts. Then, our main contribution is to prove that even if it makes the allocation problem more difficult (NP-Complete), a very small additive resource augmentation on the servers degree is enough to find in polynomial time a solution that achieves at least the optimal throughput. After a set of theoretical results on the complexity of the offline and online versions of the problem, 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 disconnections and reconnections) of proposed algorithms through a set of extensive simulation results.
Type de document :
Pré-publication, Document de travail
2011
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00624640
Contributeur : Lionel Eyraud-Dubois <>
Soumis le : lundi 19 septembre 2011 - 12:54:08
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : jeudi 30 mars 2017 - 15:05:45

Fichier

MTBD.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00624640, version 1

Collections

Citation

Olivier Beaumont, Lionel Eyraud-Dubois, Hejer Rejeb, Christopher Thraves. Heterogeneous Resource Allocation under Degree Constraints. 2011. 〈inria-00624640〉

Partager

Métriques

Consultations de la notice

518

Téléchargements de fichiers

185