Layer Allocation Algorithms in Layered Peer-to-Peer Streaming with Source Server's Participation

Peer-to-peer streaming is cost-effective for it can capitalize the resources of peer nodes to provide service to other receivers. But in peer-to-peer streaming, as the outbound bandwidths of supplying peers or the bandwidths they willing to contribute are normally constrained and limited, the source media server can still become overloaded when the system's scale is very large. Considering layered peer-to-peer media streaming, it is needed to optimally allocate layers among peers to maximally save the source server's bandwidth consumption, and the optimal allocation problem is NP-hard. Two algorithms are analyzed for this optimization problem: the first one is an approximation algorithm which is based on the principle of multiple objective optimization, and the algorithm's approximation ratio is also analyzed; The second one is a branch and bound accurate algorithm, and by calculating a constructed bigraph's maximum flow it can identify the corresponding branch's upper bound and can thus decide whether to prune this branch or not. Performance study based on simulation is carried out. The results show that the two proposed algorithms have better performance than the related algorithm, and the accurate algorithm's branch and cut principle is high-efficient.