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.
Document type :
Conference papers
Domain :

Cited literature [16 references]

https://hal.inria.fr/hal-01402025
Contributor : Hal Ifip <>
Submitted on : Thursday, November 24, 2016 - 10:47:39 AM
Last modification on : Thursday, November 24, 2016 - 11:14:12 AM
Long-term archiving on: : Tuesday, March 21, 2017 - 1:58:21 AM

File

978-3-662-44602-7_3_Chapter.pd...
Files produced by the author(s)

Citation

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⟩

Record views