Peer-to-peer streaming capacity

Sudipta Sengupta, Shao Liu, Minghua Chen, Mung Chiang, Jin Li, Philip A. Chou

Research output: Contribution to journalReview article

38 Scopus citations

Abstract

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 nonreceiver 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 using topologies derived from statistics of uplink capacities of Internet hosts.

Original languageEnglish (US)
Article number5961847
Pages (from-to)5072-5087
Number of pages16
JournalIEEE Transactions on Information Theory
Volume57
Issue number8
DOIs
StatePublished - Aug 2011

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Internet content distribution
  • linear program
  • multicast tree
  • network degree bound
  • peer-to-peer network
  • primal-dual
  • streaming capacity

Fingerprint Dive into the research topics of 'Peer-to-peer streaming capacity'. Together they form a unique fingerprint.

  • Cite this

    Sengupta, S., Liu, S., Chen, M., Chiang, M., Li, J., & Chou, P. A. (2011). Peer-to-peer streaming capacity. IEEE Transactions on Information Theory, 57(8), 5072-5087. [5961847]. https://doi.org/10.1109/TIT.2011.2145630