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

Olivier Beaumont 1, 2, 3 Nicolas Bonichon 1, 3 Lionel Eyraud-Dubois 1, 2, 3 Przemyslaw Uznanski 4 Shailesh Kumar Agrawal 5
2 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
3 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 under the multi-port communication model. In this context, we are interested in both building an overlay network and providing an explicit algorithm for scheduling the communications. From an optimization point of view, we aim both at maximizing the throughput (ie the rate at which nodes receive the message) and minimizing the degree of the participating nodes, ie the number of TCP connections they must handle simultaneously. The main novelties of our approach are the introduction of this degree constraint and the classification of the set of participating nodes into two parts: open nodes that stay in the open-Internet and "guarded'' nodes that lie behind firewalls or NATs. Two guarded nodes cannot communicate directly, but rather need to use an open node as a gateway for transmitting a message. In the case without guarded nodes, we prove that it is possible to reach the optimal throughput, at the price of a quasi-optimal (up to a small additive increase) degree of the participating nodes. In presence of guarded nodes, 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 propose an algorithm that reaches 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, what makes acyclic solutions efficient both in terms of throughput maximization and degree minimization.
Type de document :
Article dans une revue
IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2014, 25 (10), pp.2520-2528. 〈10.1109/TPDS.2013.245〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00861830
Contributeur : Lionel Eyraud-Dubois <>
Soumis le : vendredi 13 septembre 2013 - 15:44:59
Dernière modification le : vendredi 9 mars 2018 - 11:25:33
Document(s) archivé(s) le : jeudi 6 avril 2017 - 19:30:15

Fichier

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

Identifiants

Citation

Olivier Beaumont, Nicolas Bonichon, Lionel Eyraud-Dubois, Przemyslaw Uznanski, Shailesh Kumar Agrawal. Broadcasting on Large Scale Heterogeneous Platforms under the Bounded Multi-Port Model. IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2014, 25 (10), pp.2520-2528. 〈10.1109/TPDS.2013.245〉. 〈hal-00861830〉

Partager

Métriques

Consultations de la notice

560

Téléchargements de fichiers

208