Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download
Contributor : Lionel Eyraud-Dubois <>
Submitted on : Friday, September 13, 2013 - 3:44:59 PM
Last modification on : Thursday, January 23, 2020 - 6:22:10 PM
Long-term archiving on: : Thursday, April 6, 2017 - 7:30:15 PM


Files produced by the author(s)



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⟩



Record views


Files downloads