Broadcasting on Large Scale Heterogeneous Platforms under the Bounded Multi-Port Model - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue IEEE Transactions on Parallel and Distributed Systems Année : 2014

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

Résumé

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.
Fichier principal
Vignette du fichier
broadcast.pdf (642.02 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00861830 , version 1 (13-09-2013)

Identifiants

Citer

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, 2014, 25 (10), pp.2520-2528. ⟨10.1109/TPDS.2013.245⟩. ⟨hal-00861830⟩
272 Consultations
215 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More