TY - GEN

T1 - P2P streaming capacity under node degree bound

AU - Liu, Shao

AU - Chen, Minghua

AU - Sengupta, Sudipta

AU - Chiang, Mung

AU - Li, Jin

AU - Chou, Phil A.

N1 - Copyright:
Copyright 2010 Elsevier B.V., All rights reserved.

PY - 2010

Y1 - 2010

N2 - Two of the fundamental problems in peer-to-peer (P2P) streaming are as follows: what is the maximum streaming rate that can be sustained for all receivers, and what peering algorithms can achieve close to this maximum? These problems of computing and approaching the P2P streaming capacity are often challenging because of the constraints imposed on overlay topology. In this paper, we focus on the limit of P2P streaming rate under node degree bound, i.e., the number of connections a node can maintain is upper bounded. We first show that the streaming capacity problem under node degree bound is NP-Complete in general. Then, for the case of node out-degree bound, through the construction of a "Bubble algorithm", we show that the streaming capacity is at least half of that of a much less restrictive and previously studied case, where we bound the node degree in each streaming tree but not the degree across all trees. Then, for the case of node total-degree bound, we develop a "Cluster-Tree algorithm" that provides a probabilistic guarantee of achieving a rate close to the maximum rate achieved under no degree bound constraint, when the node degree bound is logarithmic in network size. The effectiveness of these algorithms in approaching the capacity limit is demonstrated in simulations using uplink bandwidth statistics of Internet hosts. Both analysis and numerical experiments show that peering in a locally dense and globally sparse manner achieves near-optimal streaming rate if the degree bound is at least logarithmic in network size.

AB - Two of the fundamental problems in peer-to-peer (P2P) streaming are as follows: what is the maximum streaming rate that can be sustained for all receivers, and what peering algorithms can achieve close to this maximum? These problems of computing and approaching the P2P streaming capacity are often challenging because of the constraints imposed on overlay topology. In this paper, we focus on the limit of P2P streaming rate under node degree bound, i.e., the number of connections a node can maintain is upper bounded. We first show that the streaming capacity problem under node degree bound is NP-Complete in general. Then, for the case of node out-degree bound, through the construction of a "Bubble algorithm", we show that the streaming capacity is at least half of that of a much less restrictive and previously studied case, where we bound the node degree in each streaming tree but not the degree across all trees. Then, for the case of node total-degree bound, we develop a "Cluster-Tree algorithm" that provides a probabilistic guarantee of achieving a rate close to the maximum rate achieved under no degree bound constraint, when the node degree bound is logarithmic in network size. The effectiveness of these algorithms in approaching the capacity limit is demonstrated in simulations using uplink bandwidth statistics of Internet hosts. Both analysis and numerical experiments show that peering in a locally dense and globally sparse manner achieves near-optimal streaming rate if the degree bound is at least logarithmic in network size.

UR - http://www.scopus.com/inward/record.url?scp=77955681823&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955681823&partnerID=8YFLogxK

U2 - 10.1109/ICDCS.2010.39

DO - 10.1109/ICDCS.2010.39

M3 - Conference contribution

AN - SCOPUS:77955681823

SN - 9780769540597

T3 - Proceedings - International Conference on Distributed Computing Systems

SP - 587

EP - 598

BT - ICDCS 2010 - 2010 International Conference on Distributed Computing Systems

T2 - 30th IEEE International Conference on Distributed Computing Systems, ICDCS 2010

Y2 - 21 June 2010 through 25 June 2010

ER -