Perfect Pipelining for Streaming Large File in Peer-to-Peer Networks - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

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

Résumé

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

Dates et versions

hal-01402025 , version 1 (24-11-2016)

Licence

Paternité

Identifiants

Citer

Fei Chen, Xiaowei Wu. Perfect Pipelining for Streaming Large File in Peer-to-Peer Networks. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. pp.27-38, ⟨10.1007/978-3-662-44602-7_3⟩. ⟨hal-01402025⟩
95 Consultations
72 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More