Afficher la notice abrégée

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

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorBEAUMONT, Olivier
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorBONICHON, Nicolas
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorEYRAUD-DUBOIS, Lionel
hal.structure.identifierLaboratoire d'informatique Fondamentale de Marseille [LIF]
dc.contributor.authorUZNANSKI, Przemyslaw
hal.structure.identifierCitibank, Singapore
dc.contributor.authorAGRAWAL, Shailesh Kumar
dc.date.accessioned2024-04-04T02:21:31Z
dc.date.available2024-04-04T02:21:31Z
dc.date.created2013
dc.date.issued2014-10
dc.identifier.issn1045-9219
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/189580
dc.description.abstractEnWe 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.
dc.description.sponsorshipSimulation de systèmes de prochaine génération - ANR-11-INFR-0013
dc.language.isoen
dc.publisherInstitute of Electrical and Electronics Engineers
dc.subject.endistributed processing
dc.subject.enoverlay networks
dc.subject.entransport protocols
dc.subject.enPeer-to-peer computing
dc.subject.enApproximation methods
dc.title.enBroadcasting on Large Scale Heterogeneous Platforms under the Bounded Multi-Port Model
dc.typeArticle de revue
dc.identifier.doi10.1109/TPDS.2013.245
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.journalIEEE Transactions on Parallel and Distributed Systems
bordeaux.page2520-2528
bordeaux.volume25
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue10
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00861830
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00861830v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=IEEE%20Transactions%20on%20Parallel%20and%20Distributed%20Systems&rft.date=2014-10&rft.volume=25&rft.issue=10&rft.spage=2520-2528&rft.epage=2520-2528&rft.eissn=1045-9219&rft.issn=1045-9219&rft.au=BEAUMONT,%20Olivier&BONICHON,%20Nicolas&EYRAUD-DUBOIS,%20Lionel&UZNANSKI,%20Przemyslaw&AGRAWAL,%20Shailesh%20Kumar&rft.genre=article


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée