Skip to Main content Skip to Navigation
New interface
Conference papers

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
Abstract : In this paper we are interested in large scale distributed platforms like BOINC, consisting of heterogeneous resources and using Internet as underlying communication network. In this context, we study a resource clustering problem, where the goal is to build clusters having at least a given capacity and such that any two participants to the same cluster are not too far from each other. In this context, the distance between two participants corresponds to the latency of a communication between them. Our goal is to provide algorithms with provable approximation ratios. In such large scale networks, it is not realistic to assume that the whole latency matrix (that gives the latency between any two participants) is known, and we need to rely on embedding tools such as Vivaldi or Sequoia. These tools enable to work on compact descriptions and well described metric spaces in which the distance between two points can be obtained directly from a small amount of information available at each node.We present the Bin Covering under Distance Constraint problem (BCDC for short), and propose dedicated algorithms for this problem for each metric space induced by each of the embedding tools. Then, we propose a comparison of these algorithms based on actual latency measures, that enables to decide which algorithm/embedding tool pair offers in practice for realistic datasets the best balancing between distance prediction and approximation ratios for the resource clustering problem.
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Olivier Beaumont Connect in order to contact the contributor
Submitted on : Monday, April 25, 2011 - 10:03:39 PM
Last modification on : Saturday, June 25, 2022 - 8:29:53 PM
Long-term archiving on: : Tuesday, July 26, 2011 - 2:32:09 AM


Files produced by the author(s)


  • HAL Id : inria-00588650, version 1



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



Record views


Files downloads