Acta Metallurgica Sinica(English letters) ›› 2010, Vol. 17 ›› Issue (2): 76-84.doi: 10.1016/S1005-8885(09)60451-9

• Networks • Previous Articles     Next Articles

Scheduling Piece Requests Blindly and Randomly for Peer-to-Peer Live Streaming


  • Received:2009-07-06 Revised:2010-01-21 Online:2010-04-30 Published:2010-06-01


The design of piece scheduling algorithm is fundamental in mesh-based Peer-to-Peer (P2P) live streaming systems. This paper regards the piece propagation process in P2P live streaming system as a conflict process, where peers compete to get the piece as soon as possible to meet the tight timing requirement of the live system. In this vision, we reduce the piece scheduling problem as a conflict resolution problem, and propose a blind random scheduling method to resolve it. The algorithm is: 1) pieces are scheduled independently; 2) conflicts are resolved by the random back off algorithm. The theoretical analysis and simulation results prove that the algorithm scales well with the network size, and can obtain near-optimal in-time delivery of pieces. The algorithm is also easy to implement in the real-world system.

Key words:

Peer-to-peer, Live streaming, Conflict Resolution, Exponential Back Off, Piece Scheduling