Peer-to-peer (P2P) systems provide a scalable way to stream content to multiple receivers over the Internet. The maximum rate achievable by all receivers is the capacity of a P2P streaming session. We provide a taxonomy of sixteen problem formulations, depending on whether there is a single P2P session or there are multiple concurrent sessions, whether the given topology is a full mesh graph or an arbitrary graph, whether the number of peers a node can have is bounded or not, and whether there are non-receiver relay nodes or not. In each formulation, computing P2P streaming capacity requires the computation of an optimal set of multicast trees, with an exponential complexity, except in three simplest formulations that have been recently solved with polynomial time algorithms. These solutions, however, do not extend to the other more general formulations.

In this paper, we develop a family of constructive, polynomial-time algorithms
that can compute P2P streaming capacity and the associated multicast trees,
arbitrarily accurately for seven formulations, to a factor of
*4*-approximation for two formulations, and to a factor of log of the number
of receivers for two formulations. The optimization problem is reformulated in
each case so as to convert the combinatorial problem into a linear program with
an exponential number of variables. The linear program is then solved using a
primal-dual approach. The algorithms combine an outer loop of primal-dual update
with an inner loop of smallest price tree construction, driven by the update of
dual variables in the outer loop. We show that when the construction of smallest
price tree can be carried out arbitrarily accurately in polynomial time, so can
the computation of P2P streaming capacity. We also develop several efficient
algorithms for smallest price tree construction. Using the developed algorithms,
we investigate the impact of several factors on P2P streaming capacity on
topologies derived from statistics of uplink capacities of Internet hosts.