Optimal serial broadcast of successive chunks ?
This paper considers the problem of broadcasting successive chunks to all nodes in a communication network under the assumption that every node can upload a chunk to exactly one adjacent node at a time. This problem models the delivery of video streams in Peer-to-Peer (P2P) networks in which a stream of chunks  is continuously given from an external media server. We propose two schemes for solving the problem. The first scheme attains an optimum broadcast time of ?lg?n? ? lg ? n ? steps using an overlay network in which each node has O(lg2?n) O ( lg 2 ? n ) children, where n  is the number of nodes in the network. The second scheme reduces the number of children by slightly increasing the broadcast time. More concretely, it completes each broadcast in lg?n+o(lg?n) lg ? n + o ( lg ? n ) steps when the number of children is bounded by O((f(n))2) O ( ( f ( n ) ) 2 ) for any function f  satisfying f(x)=?(1) f ( x ) = ? ( 1 ) and f(x)=o(lg?x) f ( x ) = o ( lg ? x ) .
optimum broadcast time peer-to-peer video streaming scheduling