Broadcasting on Large Scale Heterogeneous Platforms under the Bounded Multi-Port Model

Olivier Beaumont 1, 2 Lionel Eyraud-Dubois 1, 2 Shailesh Kumar 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 : We consider the problem of broadcasting a large message in a large scale distributed platform. The message must be sent from a source node, with the help of the receiving peers which may forward the message to other peers. In this context, we are interested in maximizing the throughput (i.e. the maximum streaming rate, once steady state has been reached). The platform model does not assume that the topology of the platform is known in advance: we consider an Internet-like network, with complete potential connectivity. Furthermore, the model associates to each node local properties (incoming and outgoing bandwidth), and the goal is to build an overlay which will be used to perform the broadcast operation. We model contentions using the bounded multi-port model: a processor can be involved simultaneously in several communications, provided that its incoming and outgoing bandwidths are not exceeded. For the sake of realism, it is also necessary to bound the number of simultaneous connections that can be opened at a given node (ie its outdegree). We prove that unfortunately, this additional constraint makes the problem of maximizing the overall throughput NP Complete. On the other hand, we also propose a polynomial time algorithm to solve this problem, based on a slight resource augmentation on the outdegree of the nodes.
Type de document :
Communication dans un congrès
24th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2010), Apr 2010, Atlanta, United States. 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00444586
Contributeur : Olivier Beaumont <>
Soumis le : samedi 27 novembre 2010 - 18:26:00
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : vendredi 26 octobre 2012 - 17:00:54

Fichier

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

Identifiants

  • HAL Id : inria-00444586, version 1

Collections

Citation

Olivier Beaumont, Lionel Eyraud-Dubois, Shailesh Kumar. Broadcasting on Large Scale Heterogeneous Platforms under the Bounded Multi-Port Model. 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2010), Apr 2010, Atlanta, United States. 2010. 〈inria-00444586〉

Partager

Métriques

Consultations de la notice

387

Téléchargements de fichiers

106