On the capacity of tree-based P2P streaming systems

The success of P2P file sharing systems inspired the development of P2P streaming systems for delivering online multimedia service in the last few years. The capacity of P2P streaming systems, i.e., how many peers can be concurrently serviced by the system, depends on system configurations including network bandwidth, overlay network formation, QoS constraints, membership management, peer selection, subscribing/publishing scheduling, coding schemes, etc. Due to the complexity, there are not too many systematical studies on system capacity. This work is our first attempt to answer this question. Based on flow concepts, we compare the capacity of single-tree P2P streaming systems and multiple-tree P2P streaming systems. The delay issues are not considered here. We prove that finding the routing tree to maximize system capacity, no matter for either single-tree systems or multiple-tree systems, is NP-hard. Two generic network formation heuristics, one for single-tree topology and the other for multiple-tree topology, are proposed. Simulation results show that since multiple-tree topology can efficiently utilize upload bandwidth, the multiple-tree systems have potential to service more clients.