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 metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/inria-00588650
Contributor : Olivier Beaumont <>
Submitted on : Monday, April 25, 2011 - 10:03:39 PM
Last modification on : Thursday, January 11, 2018 - 6:22:11 AM
Long-term archiving on : Tuesday, July 26, 2011 - 2:32:09 AM

File

HCW2011.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00588650, version 1

Citation

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⟩

Share

Metrics

Record views

295

Files downloads

151