Modeling and Practical Evaluation of a Service Location Problem in Large Scale Networks

Olivier Beaumont 1, 2 Nicolas Bonichon 1, 2 Hubert Larchevêque 1, 2
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
Résumé : Nous considérons une généralisation d'un problème d'optimisation classique lié au placement de serveurs et de réplicats dans les réseaux. Plus précisément, nous supposons qu'un ensemble d'utilisateurs au sein d'un réseau souhaite accéder à un service particulier proposé par un ensemble de fournisseurs de ce service. L'objectif est alors d'identifier un ensemble de fournisseurs de service capable d'offrir suffisamment de ressources pour répondre aux requêtes des clients. Par ailleurs, une certaine qualité de service relativement aux temps de communications est désirable. Une répartition judicieuse des serveurs dans le réseau offrirait également de bonnes propriétés de tolérance aux pannes. Nous modélisons ce problème comme une variante de Bin Packing, le Bin Packing avec Contrainte de Distance (BPDC en anglais) où le but est de construire un minimum de groupes (i.e. de choisir un nombre minimal de serveurs) de telle sorte que (i) chaque client est associé à exactement un serveur, (ii) la capacité dudit serveur est suffisante pour répondre aux requêtes des clients qui lui sont associés et (iii) la distance entre deux clients associés au même serveur est minimisée. Nous prouvons que ce problème est inapproximable même en utilisant des techniques d'augmentation de ressources : le nombre de groupes obtenus en utilisant des algorithmes s'exécutant en temps polynomial et autorisés à construire des groupes de diamètre au plus b*dmax, avec b>1, est comparé au nombre de groupes d'une solution optimale construisant des groupes de diamètre au plus dmax. D'un côté, nous prouvons que (i) si b=(2-e), BPDC est inapproximable à facteur constant, pour tout e>0; et que (ii) BPDC est inapproximableà un facteur inférieur à 3/2 même en utilisant de l'augmentation de ressources. D'un autre côté, si b=2, nous proposons un algorithme s'exécutant en temps polynomial pour BPDC assurant un facteur d'approximation de 7/3 dans le cas général. Nous montrons également comment transformer un algorithme d'approximation pour BPDC en un algorithme d'approximation pour le K-centre non uniforme avec capacités, et vice-versa. Enfin, nous présentons une comparaison qualitative de nos résultats pour BPDC en utilisant plusieurs outils de plongement de l'espace des latences d'Internet, comme Sequoia et Vivaldi.
Type de document :
Communication dans un congrès
Internation Conference on Parallel Computing 2011, Sep 2011, Taipei, Taiwan. pp.10, 2011
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00580969
Contributeur : Hubert Larchevêque <>
Soumis le : mardi 29 mars 2011 - 18:06:53
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : jeudi 8 novembre 2012 - 12:56:13

Fichier

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

Identifiants

  • HAL Id : inria-00580969, version 1

Collections

Citation

Olivier Beaumont, Nicolas Bonichon, Hubert Larchevêque. Modeling and Practical Evaluation of a Service Location Problem in Large Scale Networks. Internation Conference on Parallel Computing 2011, Sep 2011, Taipei, Taiwan. pp.10, 2011. 〈inria-00580969〉

Partager

Métriques

Consultations de la notice

242

Téléchargements de fichiers

119