Use of Internet Embedding Tools for Heterogeneous Resources Aggregation

Olivier Beaumont 1, 2 Nicolas Bonichon 1, 2 Philippe Duchon 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é : Dans cet article nous nous intéressons aux plateformes de grande échelle comme BOINC, qui consistent en un ensemble de ressources hétérogènes qui utilisent Internet comme réseau de communications. Dans ce contexte, nous étudions un problème d'agrégation de ressources dans lequel l'objectif est de construire des groupes de noeuds de telle sorte que chaque groupe ait une capacité totale supérieure à une certaine valeur, et tels qu'au sein d'un même groupe, deux noeuds ne soient pas trop éloignés l'un de l'autre. Dans ce contexte, la distance entre deux participants correspond à la latence d'une communication entre eux. Notre objectif est de fournir des algorithmes assurant des facteurs d'approximations prouvés. Dans de telles plateformes, il n'est pas réaliste de supposer connaître l'intégralité de la matrice des latences (qui donne, pour chaque paire de noeud, la latence les séparant). Il est nécessaire d'avoir recours à des outils de plongements comme Vivaldi ou Sequoia. Ces outils permettent de travailler sur des espaces métriques spécifiques bien décrits, dans lesquels la distance entre deux points peut être obtenue directement à partir d'une petite quantité d'informations disponible à chaque noeud. Nous présentons le problème de Bin Covering avec Contrainte de Distance (BCCD), et proposons pour ce problème des algorithmes dédiés à chacun des espaces métriques induits par chacun des outils de plongement que nous étudions. Ensuite nous proposons une comparaison de ces algorithmes en nous appuyant sur des mesures de latences réelles, qui nous permet de décider quel couple algorithme/outil de plongement offre en pratique, sur des jeux de données réalistes, le meilleur équilibre entre prédictions de distance et facteur d'approximation pour ce problème d'agrégation de ressources.
Type de document :
Communication dans un congrès
IEEE. Heterogeneity in Computing Workshop (HCW) - in IPDPS 2011, May 2011, Anchorage, United States. pp.114-124, 2011
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00588650
Contributeur : Olivier Beaumont <>
Soumis le : lundi 25 avril 2011 - 22:03:39
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : mardi 26 juillet 2011 - 02:32:09

Fichier

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

Identifiants

  • HAL Id : inria-00588650, version 1

Collections

Citation

Olivier Beaumont, Nicolas Bonichon, Philippe Duchon, Hubert Larchevêque. Use of Internet Embedding Tools for Heterogeneous Resources Aggregation. IEEE. Heterogeneity in Computing Workshop (HCW) - in IPDPS 2011, May 2011, Anchorage, United States. pp.114-124, 2011. 〈inria-00588650〉

Partager

Métriques

Consultations de la notice

233

Téléchargements de fichiers

74