Peer-to-peer (P2P) systems provide a scalable way

to stream content to multiple receivers over the Internet and has

become a major type of application traffic. The maximum rate

achievable by all receivers is the capacity of a P2P streaming

session. We provide a taxonomy of the problem formulations. In

each formulation, computing P2P streaming capacity requires the

computation of an optimal set of multicast trees, generally with

an exponential complexity. We survey the family of constructive,

polynomial-time algorithms that can compute P2P streaming

capacity and the associated multicast trees, arbitrarily accurately

for some of the formulations, and to some approximation factors

in other formulations. Performance evaluation using large-scale

Internet trace is provided before open problems in this research

area are discussed.

Details