Broadcasting on Large Scale Heterogeneous Platforms under the Bounded Multi-Port Model
BEAUMONT, Olivier
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
BONICHON, Nicolas
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
EYRAUD-DUBOIS, Lionel
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
See more >
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
BEAUMONT, Olivier
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
BONICHON, Nicolas
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
EYRAUD-DUBOIS, Lionel
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
< Reduce
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Language
en
Article de revue
This item was published in
IEEE Transactions on Parallel and Distributed Systems. 2014-10, vol. 25, n° 10, p. 2520-2528
Institute of Electrical and Electronics Engineers
English 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 ...Read more >
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.Read less <
English Keywords
distributed processing
overlay networks
transport protocols
Peer-to-peer computing
Approximation methods
ANR Project
Simulation de systèmes de prochaine génération - ANR-11-INFR-0013
Origin
Hal imported