On tree construction of super peers for hybrid P2P live media streaming

This paper considers a hybrid hierarchical P2P overlay network structure that consists of both super and normal peers. The media streaming architecture is built upon a tree-structured network of super peers and the tree construction process has a significant impact on the overall system performance. We build network cost models and formulate a specific type of problem to maximize the minimum node throughput in Tree Construction (max-minTC), which aims at optimizing the system's stream rate by constructing an efficient spanning tree among super peers. We consider two scenarios: (i) When the overlay network has an arbitrary topology, we prove max-minTC to be NP-complete by reducing from the Degree Constrained Spanning Tree problem and propose an efficient heuristic algorithm. The performance superiority of the proposed algorithm is justified by experimental results collected by a live media streaming system deployed in real networks and is also illustrated by extensive simulations performed on a large set of simulated networks of various sizes from small to large scales in comparison with other methods. (ii) When the topology of the overlay network is complete, we rigorously prove that the same heuristic algorithm yields an optimal solution.