Abstract-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 NPComplete 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. I. Introduction P2P systems have enabled scalable file sharing and video streaming for almost a decade, yet the following fundamental questions on its performance limits have only recently been answered partially: what is the streaming capacity, the maximum streaming rate that can be achieved by all receivers of a streaming session, under various overlay topology constraints? What kind of peering algorithms achieve near-capacity rates? As explained in Section II, P2P streaming can be modeled as multiple multicast trees superimposed on top of the overlay graph. The streaming capacity problem depends on the constraints on the graph and tree properties. The simplest case is the unconstrained tree construction on top of a full mesh (complete) graph, where the streaming capacity is derived in several papers [1], [8]- [12] . Various practical constraints on peering and overlay graph have since been considered. For example, [3], [4] solved the streaming capacity problem under the node per-tree degree bound on top of a complete graph. In contrast to node degree constraints in this paper, node per-tree degree constraints individually upper bound the number of peers a node can have in each of the multiple trees,
Chen et al. REF explore the streaming capacity of a streaming system with node degree bound.
P2P Streaming Capacity under Node Degree Bound
2010 IEEE 30th International Conference on Distributed Computing Systems
2010 IEEE 30th International Conference on Distributed Computing Systems
Computer Science