Perfect Pipelining for Streaming Large File in Peer-to-Peer Networks

Abstract : We study the efficiency of large file streaming in a peer-topeer network in which a large file is cut into many pieces of equal size, and initially all pieces are known only by one source node. We analyze the number of rounds required, called the finishing time, for all nodes in the network to collect all pieces in the default order.Based on the basic PUSH-PULL protocol, we design the Constant Out-degree Protocol (COP). At the beginning of the protocol, each node selects a constant number of neighbors, with only whom communication will be initiated. We focus our analysis on the performance of COP on preferential attachment graphs, which are believed to model peer-to-peer networks well. We show that a tight bound of Θ(B + log n) rounds can be achieved with high probability for streaming B pieces in preferential attachment graphs with n nodes. Moreover, we show that there is a dichotomy in the results depending on how neighbors are contacted in each round; specifically, when each node avoids repeating initiation with neighbors in the previous M ≥ 2 rounds, then the finishing time is improved to $\Theta (B+\frac{\log n}{\log\log n})$ with high probability. For lower bounds, we show that there is a class of regular graphs in which perfect pipelining is impossible for any PUSH-PULL protocols using random neighbor selection.
Type de document :
Communication dans un congrès
Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.27-38, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_3〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01402025
Contributeur : Hal Ifip <>
Soumis le : jeudi 24 novembre 2016 - 10:47:39
Dernière modification le : jeudi 24 novembre 2016 - 11:14:12
Document(s) archivé(s) le : mardi 21 mars 2017 - 01:58:21

Fichier

978-3-662-44602-7_3_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Fei Chen, Xiaowei Wu. Perfect Pipelining for Streaming Large File in Peer-to-Peer Networks. Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.27-38, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_3〉. 〈hal-01402025〉

Partager

Métriques

Consultations de la notice

36

Téléchargements de fichiers

10