Peer-to-Peer Streaming Capacity

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

40 Scopus Citations
View graph of relations

Author(s)

  • Sudipta Sengupta
  • Shao Liu
  • Mung Chiang
  • Jin Li
  • Philip A. Chou

Detail(s)

Original languageEnglish
Article number5961847
Pages (from-to)5072-5087
Journal / PublicationIEEE Transactions on Information Theory
Volume57
Issue number8
Online published29 Jul 2011
Publication statusPublished - Aug 2011
Externally publishedYes

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. © 2011 IEEE.

Research Area(s)

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

Citation Format(s)

Peer-to-Peer Streaming Capacity. / Sengupta, Sudipta; Liu, Shao; Chen, Minghua et al.

In: IEEE Transactions on Information Theory, Vol. 57, No. 8, 5961847, 08.2011, p. 5072-5087.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review