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

Olivier Beaumont 1, 2 Nicolas Bonichon 1, 2 Lionel Eyraud-Dubois 1, 2 P. Uznanski 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 classical problem of broadcasting a large message at an optimal rate in a large scale distributed network. The main novelty of our approach is that we consider that the set of participating nodes can be split into two parts: "green" nodes that stay in the open-Internet and "red" nodes that lie behind firewalls or NATs. Two red nodes cannot communicate directly, but rather need to use a green node as a gateway for transmitting a message. In this context, we are interested in both maximizing the throughput (\ie the rate at which nodes receive the message) and minimizing the degree at the participating nodes, \ie the number of TCP connections they must handle simultaneously. We both consider cyclic and acyclic solutions for the flow graph. In the cyclic case, our main contributions are a closed form formula for the optimal cyclic throughput and the proof that the optimal solution may require arbitrarily large degrees. In the acyclic case, we prove that it is possible to achieve the optimal throughput with low degree. Then, we prove a worst case ratio between the optimal acyclic and cyclic throughput and show through simulations that this ratio is on average very close to 1, which makes acyclic solutions efficient both in terms of the throughput and the number of connections.
Type de document :
Communication dans un congrès
IEEE. ICPADS 2011 - 17th Internation Conference on Parallel and Distributed Systems, Dec 2011, Taïnan, Taiwan. Proceeding of ICPADS 2011, pp.173-180, 2011
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00618784
Contributeur : Olivier Beaumont <>
Soumis le : lundi 5 septembre 2011 - 10:52:15
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : mardi 13 novembre 2012 - 09:51:10

Fichier

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

Identifiants

  • HAL Id : inria-00618784, version 1

Collections

Citation

Olivier Beaumont, Nicolas Bonichon, Lionel Eyraud-Dubois, P. Uznanski. Broadcasting on Large Scale Heterogeneous Platforms with connectivity artifacts under the Bounded Multi-Port Model. IEEE. ICPADS 2011 - 17th Internation Conference on Parallel and Distributed Systems, Dec 2011, Taïnan, Taiwan. Proceeding of ICPADS 2011, pp.173-180, 2011. 〈inria-00618784〉

Partager

Métriques

Consultations de la notice

346

Téléchargements de fichiers

178