# Improving Streaming Capacity in Multi-Channel

Authors: Yifeng He; Ling Guan
Journal: International Journal of Digital Multimedia Broadcasting
 (2012)

---

## Abstract

Multi-channel Peer-to-Peer (P2P) Video-on-Demand
(VoD) systems can be categorized intoindependent-channel P2P
VoD systems and correlated-channel P2P VoD systems. Streaming
capacity for a channel is defined as the maximal streaming
rate that can be received by every user of the channel. In this
paper, we study the streaming capacity problem in multi-channel
P2P VoD systems. In an independent-channel P2P VoD system,
there is no resource correlation among channels. Therefore, we
can find the average streaming capacity for the independent-channel
P2P VoD system by finding the streaming capacity for
each individual channel, respectively. We propose a distributed
algorithm to solve the streaming capacity problem for a single
channel in an independent-channel P2P VoD system. The average
streaming capacity for a correlated-channel P2P VoD system
depends on both the intra-channel and cross-channel resource
allocation. To better utilize the cross-channel resources, we
first optimize the server upload allocation among channels to
maximize the average streaming capacity and then propose
cross-channel helpers to enable cross-channel sharing of peer
upload bandwidths. We demonstrate in the simulations that the
correlated-channel P2P VoD systems with both intra-channel and
cross-channel resource allocation can obtain a higher average
streaming capacity compared to the independent-channel P2P
VoD systems with only intra-channel resource allocation.


---

## Body

## 1. Introduction

Video-on-demand (VoD) services have been attracting a lot of users because it allows users to watch any video at any time. Traditional client/server architectures for VoD services cannot provide video streams to a large number of concurrent users. To offload the server upload burden, Peer-to-Peer (P2P) technology has been integrated into VoD applications by utilizing the uplink bandwidths of the peers [1–5].Most of the P2P VoD systems offer many video channels. Users can choose any of the channels that they are interested in at any time. The P2P VoD systems with multiple channels are calledmulti-channel P2P VoD systems. Depending on the resource correlation, multi-channel P2P VoD systems can be categorized into independent-channel P2P VoD systems and correlated-channel P2P VoD systems. In an independent-channel P2P VoD system, the peers watch the same channel form an independent overlay and share the resources with each other exclusively within the overlay. In a correlated-channel P2P VoD system, overlay m formed by the peers watching channel m can be correlated with overlay k formed by the peers watching channel k, such that the peers in overlay m can share the resources not only with other peers in overlay m but also with the peers in overlay k. The resources in a correlated-channel P2P VoD system can be utilized in a better way compared to an independent-channel P2P VoD system.In P2P VoD systems, users would like to watch the video at a high quality. The streaming rate can be used to indicate the video quality. LetM denote the set of the channels in a P2P VoD system. If channel m(m∈M) is associated with overlay m, streaming capacity for channel m, denoted by cm, is defined as the maximum streaming rate that can be received by every user in overlay m [6, 7]. The average streaming capacitycavg for a multi-channel P2P VoD system is defined as cavg=Σm∈Mpmcm where pm is the priority of channel m, and Σm∈Mpm=1. The priority of a channel can be set by the service provider. For example, the more expensive channel can be assigned a higher priority.Streaming capacity problem in multi-channel P2P VoD systems is a challenging problem. The average streaming capacity in a multi-channel P2P VoD system is dependent on the number of the peers, the playback time, and the bandwidth of each peer, the server capacity, the overlay construction, and the resource allocation. Optimal resource allocation in a multi-channel P2P VoD system is expected to improve the streaming capacity. However, resource allocation in multi-channel P2P VoD systems is quite challenging due to the following reasons. (1) Peers have heterogeneous upload and download bandwidths and different playback progress. (2) Each channel is heterogeneous in terms of available resources, since the number of the peers in each channel is different. (3) Peers may leave or join a channel dynamically.In this paper, we improve the average streaming capacity for multi-channel P2P VoD systems by better utilizing both the intra-channel resources and the cross-channel resources. We first investigate the streaming capacity for an independent-channel P2P VoD system, in which we find the streaming capacity for a single channel by optimizing the intra-channel resource allocation in a distributed manner. We then investigate the streaming capacity for a correlated-channel P2P VoD system, in which we find the average streaming capacity for multiple channels by optimizing both intra-channel and cross-channel resource allocation. The proposed cross-channel resource allocation consists of two steps as follows. (1) We optimize the server upload allocation among channels to maximize the average streaming capacity. (2) We introducecross-channel helpers to establish cross-channel links and then utilize cross-channel peer upload bandwidths to improve the average streaming capacity.The remainder of this paper is organized as follows. Section2 discusses the related work. Section 3 formulates and solves the streaming capacity problem for an independent-channel P2P VoD System. Section 4 finds the average streaming capacity for a correlated-channel P2P VoD System. The simulation results are provided in Section 5, and the conclusions are drawn in Section 6.


## 2. Related Work

Streaming capacity in P2P live systems has been examined in the recent literature [6–9]. In [6], the streaming capacity problem is formulated into an optimization problem, which maximizes the streaming rate that can be supported by multitree-based overlay. Sengupta et al. provide a taxonomy of sixteen problem formulations on streaming capacity, 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 [7]. Liu et al. analyze the performance bounds for minimum server load, maximum streaming rate, and minimum tree depth in tree-based P2P live systems, respectively [8]. The streaming capacity under node degree bound is investigated in [9].Streaming capacity for a single channel in P2P VoD systems has been studied in [10–12]. In [10, 12], the streaming capacity for a single channel is formulated into an optimization problem which maximizes the streaming rate under the peer bandwidth constraints. The throughput maximization problem in a scalable P2P VoD system is studied in [13]. Helpers have been proposed in P2P systems to improve the system performance [11, 14, 15]. In P2P VoD systems, each additional helper increases the system upload capacity, thus offloading the server burden [15]. In [11], the algorithms on helper assignment and rate allocation are proposed to improve the streaming capacity for P2P VoD systems.Cross-channel resource sharing has been recently studied in multi-channel P2P streaming systems [16–20]. In [16], Wu et al. propose an online server capacity provisioning algorithm to adjust the server capacities available to each of the concurrent channels, taking into account the number of peers, the streaming quality, and the priorities of channels. In [17], a View-Upload Decoupling (VUD) scheme is proposed to decouple what a peer uploads from what it views, bringing stability to multi-channel P2P streaming systems and enabling cross-channel resource sharing. In [18], Wu et al. develop infinite-server queueing network models to analytically study the performance of multi-channel P2P live streaming systems. In [19], the bandwidth satisfaction ratio is used to compare three bandwidth allocation schemes, namely, Naive Bandwidth allocation Approach (NBA), Passive Channel-aware bandwidth allocation Approach (PCA), and Active Channel-aware bandwidth allocation Approach (ACA), in multi-channel P2P streaming systems. In [20], Zhao et al. investigate the streaming capacity in multi-channel P2P live streaming systems when each peer can only connect to a small number of neighbors.


## 3. Streaming Capacity for an Independent-Channel P2P VoD System

In an independent-channel P2P VoD system, the peers watching the same channel form an overlay. We assume that the server upload bandwidth allocated to channelm, denoted by sm, is predetermined. An independent-channel P2P VoD system is illustrated in Figure 1. The peers within the same overlay redistribute the video content to each other. A peer belonging to overlay m only caches the video content of channel m, and it does not serve any video content to any peer outside overlay m. In other words, each overlay in an independent-channel P2P VoD System is an isolated subsystem. Therefore, the streaming capacity of a channel is independent of that of another channel. The streaming capacity problem in an independent-channel P2P VoD system is to find the streaming capacity of each individual channel, respectively. We will next focus on the streaming capacity for a single channel.Figure 1
Illustration of an independent-channel P2P VoD system.


### 3.1. Complete Overlay

The streaming capacity for a single channel depends on the constructed overlay. In a P2P VoD system, each peer maintains a buffer to cache the recently received packets in order to smoothen the playback and serve other peers. There is aparent-child relationship between two peers (e.g., peer k and peer j) if the two peers satisfy the following two conditions: (1) peer k (the parent) has an earlier playback progress than peer j (the child), and (2) peer k is buffering the segment(s) which are being requested by peer j. The parent-child relationship is illustrated in Figure 2(a). At the current moment, peer k is playing segment 11, and peer j is playing segment 7. Each peer can hold 5 segments in its buffer. Segment 8, held by peer k, is being requested by peer j. Therefore, peers k and j can establish a parent-child relationship, in which peer k is the parent, and peer j is the child. The server is regarded as a special peer because it contains all the segments of the video. The server has a parent-child relationship with any other peer.Overlay construction for a single channel in an independent-channel P2P VoD system: (a) the parent-child relationship between peerk and peer j, and (b) the complete overlay.
(a)(b)A parent-child relationship isimplemented, if an overlay link has been established from the parent to the child. A complete overlay for a channel is defined as the overlay in which all of the available parent-child relationships have been implemented, and an incomplete overlay for a channel is defined as the overlay in which only a part of the available parent-child relationships have been implemented [12]. An example of complete overlay is illustrated in Figure 2(b). Compared to the incomplete overlay, the complete overlay contains more overlay links, thus supporting a higher streaming capacity. Therefore, we will formulate the streaming capacity problem based on the complete overlay. The method for overlay construction is not a study focus of this paper. A complete overlay can be constructed using the existing approaches [2].


### 3.2. Streaming Capacity Problem for a Single Channel

The set of the overlays (channels) in the independent-channel P2P VoD system is denoted byM. Since each channel is independent in terms of resources, we can just study the streaming capacity of channel m(∀m∈M).Overlaym in a P2P VoD system can be modeled as a directed graph G(m)=(N(m),L(m)), where N(m) is the set of nodes and L(m) is the set of directed overlay links. Peer 1 is defined as the server. The relationship between a node and its outgoing links is represented with a matrix A(m)+, whose elements are given by(1)ail(m)+={1,iflinklisanoutgoinglinkfromnodei,0,otherwise.The relationship between a node and its incoming links is represented with a matrixA(m)-, whose elements are given by(2)ail(m)-={1,iflinklisanincominglinkintonodei,0,otherwise.The upload capacity of peeri is denoted by Oi(m). The server is denoted as Peer 1. The server upload bandwidth sm for channel m is actually the upload capacity of Peer 1, which is given by O1(m)=sm. Upload capacity is typically the bottleneck in P2P systems. We consider upload constraint at peer i(∀i∈N(m)), which is given by ∑l∈L(m)ail(m)+xl(m)≤Oi(m) where xl(m) is the link rate at link l of overlay m. The upload constraint represents that the total outgoing rate from peer i is no larger than its upload capacity Oi(m). The streaming rate for channel m is denoted by r(m). Each peer except the server (e.g., Peer 1) receives the streaming rate r(m), which can be expressed by ∑l∈Lail(m)-xl(m)=fi(m)r(m), for all i∈N(m), where fi(m)=0 if i=1, or fi(m)=1 otherwise. The download constraint is given by r(m)≤mini∈N(m)Ii(m) where Ii(m) is the download capacity of peer i. From the download constraint, we can see that the maximal streaming rate is limited by the minimal download capacity among the peers. Therefore, the users with a very low download bandwidth should not be admitted into the P2P VoD system in order for maintaining a high streaming capacity.The streaming capacity for channelm is stated as to maximize the streaming rate r(m) that can be received by every user in channel m by optimizing the streaming rate r(m) and the link rate xl(m)(∀l∈L(m)) under the upload constraint at each peer. Mathematically, the problem can be formulated as follows:(3)maximizer(m)subjectto∑l∈L(m)ail(m)-xl(m)=fi(m)r(m),∀i∈N(m),∑l∈L(m)ail(m)+xl(m)≤Oi(m),∀i∈N(m),xl(m)≥0,∀l∈L(m),0≤r(m)≤min⁡i∈N(m)Ii(m).The optimization problem in (3) is a Linear Programming (LP). It can be solved in a centralized way using the interior point method [21]. However, the centralized solution is not scalable. Therefore, we will develop a distributed algorithm using the primal-dual method to solve the streaming capacity problem.


### 3.3. Distributed Algorithm

We will use primal-dual method [22] to develop a distributed algorithm for the optimization problem (3). However, the objective function in problem (3) is not strictly convex with respect to the optimization variables r(m) and xl(m)(∀l∈L(m)). Therefore, the corresponding dual function is nondifferentiable, and the optimal values of r(m) and xl(m)(∀l∈L(m)) are not immediately available. We first convert the the original optimization problem (3) to an equivalent minimization problem by changing the objective from maximizing r(m) to minimizing -r(m). We then add a quadratic regularization term for the streaming rate r(m) and each link rate xl(m)(∀l∈L(m)) to make the objective function strictly convex. Finally, the optimization problem (3) is approximated to the following:(4)minimize-r(m)+ε(r(m))2+ε∑l∈L(m)(xl(m))2subjectto∑l∈L(m)ail(m)-xl(m)=fi(m)r(m),∀i∈N(m),∑l∈L(m)ail(m)+xl(m)≤Oi(m),∀i∈N(m),xl(m)≥0,∀l∈L(m),0≤r(m)≤min⁡i∈N(m)Ii(m),
where (ε(r(m))2+ε∑l∈L(m)(xl(m))2) is the sum of the regularization terms, and ε(ε>0) is called the regularization factor. When ε is small enough, the solution for the problem in (4) is arbitrarily close to the solution for the original streaming capacity problem (3).Let us denote by(r(m)*,xl(m)*(∀l∈L(m))) the optimal solution to the original optimization problem (3), and (r(m)$,xl(m)$(∀l∈L(m))) the optimal solution to the approximated optimization problem (4). Based on the original optimization problem (3), we have r(m)*≥r(m)$. Based on the approximated optimization problem (4), we have -r(m)$+ε(r(m)$)2+ε∑l∈L(m)(xl(m)$)2≤-r(m)*+ε(r(m)*)2+ε∑l∈L(m)(xl(m)*)2. Therefore, we can get 0≤r(m)*-r(m)$≤ε((r(m)*)2-(r(m)$)2+∑l∈L(m)(xl(m)*)2-∑l∈L(m)(xl(m)$)2), from which we show that the streaming capacity obtained from the approximated optimization problem (4) with a small regularization factor can approach closely to the truly maximal streaming rate obtained from the original optimization problem (3).The optimization problem (4) is a convex optimization problem with a strictly convex objective function and the linear constraints [23]. We introduce dual variables (ui,vi,∀i∈N(m)) to formulate the Lagrangian corresponding to the primal problem (4) as below:(5)L(x(m),r(m),u,v)=-r(m)+ε(r(m))2+ε∑l∈L(m)(xl(m))2+∑i∈N(m)ui(∑l∈L(m)ail(m)-xl(m)-fi(m)r(m))+∑i∈N(m)vi(∑l∈L(m)ail(m)+xl(m)-Oi(m))=ε(r(m))2-r(m)-r(m)∑i∈N(m)uifi(m)+∑l∈L(m)(∑i∈N(m)ε(xl(m))2+xl(m)∑i∈N(m)(uiail(m)-+viail(m)+))-∑i∈N(m)viOi(m).LetImin(m)=mini∈N(m)Ii(m). The Lagrange dual function G(u,v) is the minimum value of the Lagrangian over the vector of link rates x(m) and the streaming rate r(m):(6)G(u,v)=min⁡(x(m)≥0,0≤r(m)≤Imin⁡(m)){L(x(m),r(m),u,v)}.The Lagrange dual problem is to maximize the Lagrange dual function. That is,(7)maximizeG(u,v)subjecttovi≥0,∀i∈N(m).We use subgradient method [24] to solve the Lagrange dual problem (7). The dual variables ui(k+1) and vi(k+1) at the (k+1)th iteration are updated, respectively, by(8)ui(k+1)=ui(k)-θ(k)(fi(m)(r(m))(k)-∑l∈L(m)ail(m)-(xl(m))(k)),vi(k+1)=max⁡{0,vi(k)-θ(k)(O(m)-∑l∈L(m)ail(m)+(xl(m))(k))},
where θ(k)>0 is the step size at the kth iteration. The algorithm is guaranteed to converge to the optimal value for a step-size sequence satisfying the nonsummable diminishing rule [24]:(9)lim⁡k→∞θ(k)=0,∑k=1∞θ(k)=∞.The update of the streaming rate(r(m))(k) at the kth iteration is given by(10)(r(m))(k)=min⁡{max⁡{0,1+∑i∈N(m)ui(k)fi(m)2ε},Imin⁡(m)}.
At the kth iteration, the link rate (xl(m))(k) at link l can be calculated from the dual variables:(11)(xl(m))(k)=max⁡{0,-∑i∈N(m)(ui(k)ail(m)-+vi(k)ail(m)+)2ε}.As shown in (10) and (11), the optimization variables are decomposed. The optimization of the streaming rate is executed at the server as follows. At the kth iteration, the server collects the dual variable ui(k) from peer i(∀i∈N(m)), respectively, and then computes the streaming rate (r(m))(k). The optimization of each link rate is executed at each peer as follows. At the kth iteration, each peer only collects the dual variable uj(k) from each of its children, and then computes the link rate for each of the outgoing links.A P2P system is inherently dynamic. Peers may join or leave the system at any time. Therefore, the streaming capacity for a single channel varies with time. To handle the time-varying streaming capacity, the server can encode the video using a scalable coding scheme and then adjust the output video rate adaptive to the current streaming capacity.


## 3.1. Complete Overlay

The streaming capacity for a single channel depends on the constructed overlay. In a P2P VoD system, each peer maintains a buffer to cache the recently received packets in order to smoothen the playback and serve other peers. There is aparent-child relationship between two peers (e.g., peer k and peer j) if the two peers satisfy the following two conditions: (1) peer k (the parent) has an earlier playback progress than peer j (the child), and (2) peer k is buffering the segment(s) which are being requested by peer j. The parent-child relationship is illustrated in Figure 2(a). At the current moment, peer k is playing segment 11, and peer j is playing segment 7. Each peer can hold 5 segments in its buffer. Segment 8, held by peer k, is being requested by peer j. Therefore, peers k and j can establish a parent-child relationship, in which peer k is the parent, and peer j is the child. The server is regarded as a special peer because it contains all the segments of the video. The server has a parent-child relationship with any other peer.Overlay construction for a single channel in an independent-channel P2P VoD system: (a) the parent-child relationship between peerk and peer j, and (b) the complete overlay.
(a)(b)A parent-child relationship isimplemented, if an overlay link has been established from the parent to the child. A complete overlay for a channel is defined as the overlay in which all of the available parent-child relationships have been implemented, and an incomplete overlay for a channel is defined as the overlay in which only a part of the available parent-child relationships have been implemented [12]. An example of complete overlay is illustrated in Figure 2(b). Compared to the incomplete overlay, the complete overlay contains more overlay links, thus supporting a higher streaming capacity. Therefore, we will formulate the streaming capacity problem based on the complete overlay. The method for overlay construction is not a study focus of this paper. A complete overlay can be constructed using the existing approaches [2].


## 3.2. Streaming Capacity Problem for a Single Channel

The set of the overlays (channels) in the independent-channel P2P VoD system is denoted byM. Since each channel is independent in terms of resources, we can just study the streaming capacity of channel m(∀m∈M).Overlaym in a P2P VoD system can be modeled as a directed graph G(m)=(N(m),L(m)), where N(m) is the set of nodes and L(m) is the set of directed overlay links. Peer 1 is defined as the server. The relationship between a node and its outgoing links is represented with a matrix A(m)+, whose elements are given by(1)ail(m)+={1,iflinklisanoutgoinglinkfromnodei,0,otherwise.The relationship between a node and its incoming links is represented with a matrixA(m)-, whose elements are given by(2)ail(m)-={1,iflinklisanincominglinkintonodei,0,otherwise.The upload capacity of peeri is denoted by Oi(m). The server is denoted as Peer 1. The server upload bandwidth sm for channel m is actually the upload capacity of Peer 1, which is given by O1(m)=sm. Upload capacity is typically the bottleneck in P2P systems. We consider upload constraint at peer i(∀i∈N(m)), which is given by ∑l∈L(m)ail(m)+xl(m)≤Oi(m) where xl(m) is the link rate at link l of overlay m. The upload constraint represents that the total outgoing rate from peer i is no larger than its upload capacity Oi(m). The streaming rate for channel m is denoted by r(m). Each peer except the server (e.g., Peer 1) receives the streaming rate r(m), which can be expressed by ∑l∈Lail(m)-xl(m)=fi(m)r(m), for all i∈N(m), where fi(m)=0 if i=1, or fi(m)=1 otherwise. The download constraint is given by r(m)≤mini∈N(m)Ii(m) where Ii(m) is the download capacity of peer i. From the download constraint, we can see that the maximal streaming rate is limited by the minimal download capacity among the peers. Therefore, the users with a very low download bandwidth should not be admitted into the P2P VoD system in order for maintaining a high streaming capacity.The streaming capacity for channelm is stated as to maximize the streaming rate r(m) that can be received by every user in channel m by optimizing the streaming rate r(m) and the link rate xl(m)(∀l∈L(m)) under the upload constraint at each peer. Mathematically, the problem can be formulated as follows:(3)maximizer(m)subjectto∑l∈L(m)ail(m)-xl(m)=fi(m)r(m),∀i∈N(m),∑l∈L(m)ail(m)+xl(m)≤Oi(m),∀i∈N(m),xl(m)≥0,∀l∈L(m),0≤r(m)≤min⁡i∈N(m)Ii(m).The optimization problem in (3) is a Linear Programming (LP). It can be solved in a centralized way using the interior point method [21]. However, the centralized solution is not scalable. Therefore, we will develop a distributed algorithm using the primal-dual method to solve the streaming capacity problem.


## 3.3. Distributed Algorithm

We will use primal-dual method [22] to develop a distributed algorithm for the optimization problem (3). However, the objective function in problem (3) is not strictly convex with respect to the optimization variables r(m) and xl(m)(∀l∈L(m)). Therefore, the corresponding dual function is nondifferentiable, and the optimal values of r(m) and xl(m)(∀l∈L(m)) are not immediately available. We first convert the the original optimization problem (3) to an equivalent minimization problem by changing the objective from maximizing r(m) to minimizing -r(m). We then add a quadratic regularization term for the streaming rate r(m) and each link rate xl(m)(∀l∈L(m)) to make the objective function strictly convex. Finally, the optimization problem (3) is approximated to the following:(4)minimize-r(m)+ε(r(m))2+ε∑l∈L(m)(xl(m))2subjectto∑l∈L(m)ail(m)-xl(m)=fi(m)r(m),∀i∈N(m),∑l∈L(m)ail(m)+xl(m)≤Oi(m),∀i∈N(m),xl(m)≥0,∀l∈L(m),0≤r(m)≤min⁡i∈N(m)Ii(m),
where (ε(r(m))2+ε∑l∈L(m)(xl(m))2) is the sum of the regularization terms, and ε(ε>0) is called the regularization factor. When ε is small enough, the solution for the problem in (4) is arbitrarily close to the solution for the original streaming capacity problem (3).Let us denote by(r(m)*,xl(m)*(∀l∈L(m))) the optimal solution to the original optimization problem (3), and (r(m)$,xl(m)$(∀l∈L(m))) the optimal solution to the approximated optimization problem (4). Based on the original optimization problem (3), we have r(m)*≥r(m)$. Based on the approximated optimization problem (4), we have -r(m)$+ε(r(m)$)2+ε∑l∈L(m)(xl(m)$)2≤-r(m)*+ε(r(m)*)2+ε∑l∈L(m)(xl(m)*)2. Therefore, we can get 0≤r(m)*-r(m)$≤ε((r(m)*)2-(r(m)$)2+∑l∈L(m)(xl(m)*)2-∑l∈L(m)(xl(m)$)2), from which we show that the streaming capacity obtained from the approximated optimization problem (4) with a small regularization factor can approach closely to the truly maximal streaming rate obtained from the original optimization problem (3).The optimization problem (4) is a convex optimization problem with a strictly convex objective function and the linear constraints [23]. We introduce dual variables (ui,vi,∀i∈N(m)) to formulate the Lagrangian corresponding to the primal problem (4) as below:(5)L(x(m),r(m),u,v)=-r(m)+ε(r(m))2+ε∑l∈L(m)(xl(m))2+∑i∈N(m)ui(∑l∈L(m)ail(m)-xl(m)-fi(m)r(m))+∑i∈N(m)vi(∑l∈L(m)ail(m)+xl(m)-Oi(m))=ε(r(m))2-r(m)-r(m)∑i∈N(m)uifi(m)+∑l∈L(m)(∑i∈N(m)ε(xl(m))2+xl(m)∑i∈N(m)(uiail(m)-+viail(m)+))-∑i∈N(m)viOi(m).LetImin(m)=mini∈N(m)Ii(m). The Lagrange dual function G(u,v) is the minimum value of the Lagrangian over the vector of link rates x(m) and the streaming rate r(m):(6)G(u,v)=min⁡(x(m)≥0,0≤r(m)≤Imin⁡(m)){L(x(m),r(m),u,v)}.The Lagrange dual problem is to maximize the Lagrange dual function. That is,(7)maximizeG(u,v)subjecttovi≥0,∀i∈N(m).We use subgradient method [24] to solve the Lagrange dual problem (7). The dual variables ui(k+1) and vi(k+1) at the (k+1)th iteration are updated, respectively, by(8)ui(k+1)=ui(k)-θ(k)(fi(m)(r(m))(k)-∑l∈L(m)ail(m)-(xl(m))(k)),vi(k+1)=max⁡{0,vi(k)-θ(k)(O(m)-∑l∈L(m)ail(m)+(xl(m))(k))},
where θ(k)>0 is the step size at the kth iteration. The algorithm is guaranteed to converge to the optimal value for a step-size sequence satisfying the nonsummable diminishing rule [24]:(9)lim⁡k→∞θ(k)=0,∑k=1∞θ(k)=∞.The update of the streaming rate(r(m))(k) at the kth iteration is given by(10)(r(m))(k)=min⁡{max⁡{0,1+∑i∈N(m)ui(k)fi(m)2ε},Imin⁡(m)}.
At the kth iteration, the link rate (xl(m))(k) at link l can be calculated from the dual variables:(11)(xl(m))(k)=max⁡{0,-∑i∈N(m)(ui(k)ail(m)-+vi(k)ail(m)+)2ε}.As shown in (10) and (11), the optimization variables are decomposed. The optimization of the streaming rate is executed at the server as follows. At the kth iteration, the server collects the dual variable ui(k) from peer i(∀i∈N(m)), respectively, and then computes the streaming rate (r(m))(k). The optimization of each link rate is executed at each peer as follows. At the kth iteration, each peer only collects the dual variable uj(k) from each of its children, and then computes the link rate for each of the outgoing links.A P2P system is inherently dynamic. Peers may join or leave the system at any time. Therefore, the streaming capacity for a single channel varies with time. To handle the time-varying streaming capacity, the server can encode the video using a scalable coding scheme and then adjust the output video rate adaptive to the current streaming capacity.


## 4. Streaming Capacity for a Correlated-Channel P2P VoD System

In a correlated-channel P2P VoD system, the resources among different channels can be shared with each other. The average streaming capacity in a correlated-channel P2P VoD system can be obtained by optimizing both the intra-channel resource allocation and the cross-channel resource allocation. The optimization of intra-channel resource allocation for a single channel has been presented in Section3. In this section, we will focus on the cross-channel resource allocation. We will first optimize the server upload allocation among channels to maximize the average streaming capacity in Section 4.1, and then further utilize cross-channel peer upload bandwidth to improve the average streaming capacity in Section 4.2.


### 4.1. Optimization of Server Upload Allocation among Channels

The server upload allocated for channelm is denoted by sm. In an independent-channel P2P VoD system, the server upload allocation for each channel is predetermined. Therefore, the server upload bandwidth is not utilized in an optimal way. In this subsection, we treat {sm,∀m∈M} as variables and optimize them to maximize the average streaming capacity for a correlated-channel P2P VoD system.The optimization of server upload allocation for a correlated-channel P2P VoD system is stated as to maximize the average streaming rate by optimizing the server upload allocation, the link rates, and the streaming rate, for each channel, subject to the upload constraint at each peer. Since maximizing the average streaming rate is equivalent to minimizing the negative average streaming rate, we formulate the problem into a minimization problem as follows:(12)minimize-∑m∈Mpmr(m)subjectto∑l∈L(m)ail(m)-xl(m)=fi(m)r(m),∀i∈N(m),∀m∈M,∑l∈L(m)ail(m)+xl(m)≤Oi(m),∀i∈N(m),∀m∈M,xl(m)≥0,∀l∈L(m),∑m∈Msm≤sT,sm≥0,∀m∈M,0≤r(m)≤min⁡i∈N(m)Ii(m),∀m∈M,
where pm is the priority for channel m, and sT is the server upload capacity. The optimization problem in (12) is an LP. The optimization variables in the optimization problem (12) are the server upload allocation sm, the link rate vector x(m), and the streaming rate r(m), for channel m, for all m∈M. The number of the optimization variables is increased with the number of the channels and the number of the links in each overlay. In order to solve the optimization efficiently, we use dual decomposition [22] to decompose the optimization problem (12) into multiple subproblems, each of which is associated with a channel.We introduce a dual variableλ for the inequality constraint ∑m∈Msm≤sT. The Lagrangian corresponding to the primal problem (12) is given by L(s,x,r,λ)=-Σm∈Mpmr(m)+λ(∑m∈Msm-sT). Then, the Lagrange dual function [23] is given by G(λ)=minL(s,x,r,λ)=∑m∈Mmin(-pmr(m)+λsm)-λsT.The Lagrange dual problem is to maximize the Lagrange dual function [23]. That is,(13)maximizeG(λ)subjecttoλ≥0.Subgradient method [24] is used to solve the Lagrange dual problem (13). The dual variable λ is updated at the (k+1)th iteration by λ(k+1)=max{0,λ(k)-θ(k)(sT-∑m∈Msm(k)) where θ(k) is the step size at the kth iteration. In order to guarantee the convergence, the sequence of the step sizes is required to satisfy the nonsummable diminishing rule in (9).At thekth iteration, the primal variables (sm,x(m),r(m)) for channel m are obtained by solving the following optimization problem:(14)minimize-pmr(m)+λsmsubjectto∑l∈L(m)ail(m)-xl(m)=fi(m)r(m),∀i∈N(m),∑l∈L(m)ail(m)+xl(m)≤Oi(m),∀i∈N(m),xl(m)≥0,∀l∈L(m),0≤r(m)≤min⁡i∈N(m)Ii(m),sm≥0.The optimization problem (12) is decomposed into |M| subproblems where |M| is the number of the channels. Subproblem m, represented in (14), is associated with channel m. Subproblem m, for all m∈M, can be solved with a distributed algorithm.


### 4.2. Cross-Channel Sharing of Peer Upload Bandwidth

Though the server upload allocation among channels is optimized, the cross-channel resources have not yet been fully utilized. In each channel, there are a number of under-utilized peers, which can be utilized by the other channels. For example, the leaf nodes of overlaym contribute zero upload bandwidth to the channel because they have no outgoing links. We can utilize the upload bandwidth of the leaf nodes in overlay m to serve the peers in another channel (e.g., channel k), thus improving the streaming capacity of channel k. However, it is challenging to establish the cross-channel links to enable the cross-channel sharing of peer upload bandwidth.In this paper, we propose a scheme for cross-channel peer upload sharing. We introduce the concept ofcross-channel helpers. A cross-channel helper is the peer who uses its remaining upload bandwidth to help other peers in another channel. Cross-channel helpers are chosen from the peers who have a remaining upload bandwidth greater than a threshold.Suppose that peeri in channel m is a cross-channel helper serving segment j of channel k, and it has a remaining upload bandwidth bi. We denote the set of peers watching segment j in channel k by Hj(k). Peer i can download segment j of channel k from the server or the peers who are buffering segment j, at a rate RiIN, and then output it to peer h, for all h∈Hj(k), at a rate Rih, respectively. The bandwidth gain for peer i is defined as gi=(∑h∈Hj(k)Rih)/RiIN. In order to maximize the bandwidth gain gi under the flow constraint Rih≤RiIN, for all h∈Hj(k), and the bandwidth constraint ∑h∈Hj(k)Rih≤bi, the optimal download rate at peer i is RiIN*=bi/|Hj(k)| where|Hj(k)| is the number of the peers watching segment j of channel k, and the optimal outgoing rate to peer h, for all h∈Hj(k), is Rih*=RiIN*. The bandwidth gain should be larger than 1, otherwise, the cross-channel helper consumes a larger bandwidth than it contributes. Figure 3 illustrates a correlated-channel P2P VoD system. As shown in Figure 3, peer 8 in overlay 1 is a cross-channel helper, who downloads a segment from the server and then forwards it to peers 12–14 in overlay 2; peer 12 in overlay 2 is also a cross-channel helper, who downloads a segment from peer 4 in overlay 1 and then forwards it to peers 5–7 in overlay 1.Figure 3
Illustration of a correlated-channel P2P VoD system.The proposed scheme for cross-channel peer upload sharing is described as follows.(1)
Channelm(∀m∈M) finds a partner, channel k(k≠m,k∈M), to help each other, by using a resource-balancing scheme, which is described as follows. (i) Calculate Bmre, the amount of the total remaining bandwidth, for channel m(∀m∈M), the average amount of the total remaining bandwidth is given by Bavgre=(∑m∈MBmre)/|M| where |M| represents the number of channels. (ii) Given the set of unchosen channels Mun, the partner of channel m is determined by k=argj∈Munmin((1/2)(Bjre+Bmre)-Bavgre)2.(2)
Determine the set of cross-channel helpers in channelm, denoted by Y(m), by choosing the peers who have a remaining upload bandwidth greater than a thresholdbth. Sort Y(m) in a descending order based on the remaining upload bandwidth.(3)
Determine thedemanding segment set in channel k, denoted by W(k), by choosing |Y(m)| segments which are watched by the largest number of peers. Sort W(k) in a descending order based on the number of watching peers.(4)
Assign theith cross-channel helper in Y(m) to serve the peers watching the ith segment in W(k). Determine the incoming rate and outgoing rates at the ith cross-channel helper to maximize the bandwidth gain.(5)
After allocating the rate for each of the cross-channel links as in Step (4), revise the optimization problem (12) by integrating the cross-channel link rates and then solve it to obtain the optimal server upload allocation for each channel and the optimal link rates within each overlay.Peer dynamics have an impact on the streaming capacity in correlated-channel P2P VoD systems. First, the peers may leave or join a channel dynamically. Second, the cross-channel helpers may leave the channel, which causes the disconnection of the cross-channel links. To handle the dynamic conditions, the optimizations of intra-channel resource allocation and cross-channel resource allocation need to be performed in a discrete-time manner, in which the peers and the overlay are assumed to remain unchanged during a time slot, and the algorithms for resource allocation are performed at the beginning of each time slot.


## 4.1. Optimization of Server Upload Allocation among Channels

The server upload allocated for channelm is denoted by sm. In an independent-channel P2P VoD system, the server upload allocation for each channel is predetermined. Therefore, the server upload bandwidth is not utilized in an optimal way. In this subsection, we treat {sm,∀m∈M} as variables and optimize them to maximize the average streaming capacity for a correlated-channel P2P VoD system.The optimization of server upload allocation for a correlated-channel P2P VoD system is stated as to maximize the average streaming rate by optimizing the server upload allocation, the link rates, and the streaming rate, for each channel, subject to the upload constraint at each peer. Since maximizing the average streaming rate is equivalent to minimizing the negative average streaming rate, we formulate the problem into a minimization problem as follows:(12)minimize-∑m∈Mpmr(m)subjectto∑l∈L(m)ail(m)-xl(m)=fi(m)r(m),∀i∈N(m),∀m∈M,∑l∈L(m)ail(m)+xl(m)≤Oi(m),∀i∈N(m),∀m∈M,xl(m)≥0,∀l∈L(m),∑m∈Msm≤sT,sm≥0,∀m∈M,0≤r(m)≤min⁡i∈N(m)Ii(m),∀m∈M,
where pm is the priority for channel m, and sT is the server upload capacity. The optimization problem in (12) is an LP. The optimization variables in the optimization problem (12) are the server upload allocation sm, the link rate vector x(m), and the streaming rate r(m), for channel m, for all m∈M. The number of the optimization variables is increased with the number of the channels and the number of the links in each overlay. In order to solve the optimization efficiently, we use dual decomposition [22] to decompose the optimization problem (12) into multiple subproblems, each of which is associated with a channel.We introduce a dual variableλ for the inequality constraint ∑m∈Msm≤sT. The Lagrangian corresponding to the primal problem (12) is given by L(s,x,r,λ)=-Σm∈Mpmr(m)+λ(∑m∈Msm-sT). Then, the Lagrange dual function [23] is given by G(λ)=minL(s,x,r,λ)=∑m∈Mmin(-pmr(m)+λsm)-λsT.The Lagrange dual problem is to maximize the Lagrange dual function [23]. That is,(13)maximizeG(λ)subjecttoλ≥0.Subgradient method [24] is used to solve the Lagrange dual problem (13). The dual variable λ is updated at the (k+1)th iteration by λ(k+1)=max{0,λ(k)-θ(k)(sT-∑m∈Msm(k)) where θ(k) is the step size at the kth iteration. In order to guarantee the convergence, the sequence of the step sizes is required to satisfy the nonsummable diminishing rule in (9).At thekth iteration, the primal variables (sm,x(m),r(m)) for channel m are obtained by solving the following optimization problem:(14)minimize-pmr(m)+λsmsubjectto∑l∈L(m)ail(m)-xl(m)=fi(m)r(m),∀i∈N(m),∑l∈L(m)ail(m)+xl(m)≤Oi(m),∀i∈N(m),xl(m)≥0,∀l∈L(m),0≤r(m)≤min⁡i∈N(m)Ii(m),sm≥0.The optimization problem (12) is decomposed into |M| subproblems where |M| is the number of the channels. Subproblem m, represented in (14), is associated with channel m. Subproblem m, for all m∈M, can be solved with a distributed algorithm.


## 4.2. Cross-Channel Sharing of Peer Upload Bandwidth

Though the server upload allocation among channels is optimized, the cross-channel resources have not yet been fully utilized. In each channel, there are a number of under-utilized peers, which can be utilized by the other channels. For example, the leaf nodes of overlaym contribute zero upload bandwidth to the channel because they have no outgoing links. We can utilize the upload bandwidth of the leaf nodes in overlay m to serve the peers in another channel (e.g., channel k), thus improving the streaming capacity of channel k. However, it is challenging to establish the cross-channel links to enable the cross-channel sharing of peer upload bandwidth.In this paper, we propose a scheme for cross-channel peer upload sharing. We introduce the concept ofcross-channel helpers. A cross-channel helper is the peer who uses its remaining upload bandwidth to help other peers in another channel. Cross-channel helpers are chosen from the peers who have a remaining upload bandwidth greater than a threshold.Suppose that peeri in channel m is a cross-channel helper serving segment j of channel k, and it has a remaining upload bandwidth bi. We denote the set of peers watching segment j in channel k by Hj(k). Peer i can download segment j of channel k from the server or the peers who are buffering segment j, at a rate RiIN, and then output it to peer h, for all h∈Hj(k), at a rate Rih, respectively. The bandwidth gain for peer i is defined as gi=(∑h∈Hj(k)Rih)/RiIN. In order to maximize the bandwidth gain gi under the flow constraint Rih≤RiIN, for all h∈Hj(k), and the bandwidth constraint ∑h∈Hj(k)Rih≤bi, the optimal download rate at peer i is RiIN*=bi/|Hj(k)| where|Hj(k)| is the number of the peers watching segment j of channel k, and the optimal outgoing rate to peer h, for all h∈Hj(k), is Rih*=RiIN*. The bandwidth gain should be larger than 1, otherwise, the cross-channel helper consumes a larger bandwidth than it contributes. Figure 3 illustrates a correlated-channel P2P VoD system. As shown in Figure 3, peer 8 in overlay 1 is a cross-channel helper, who downloads a segment from the server and then forwards it to peers 12–14 in overlay 2; peer 12 in overlay 2 is also a cross-channel helper, who downloads a segment from peer 4 in overlay 1 and then forwards it to peers 5–7 in overlay 1.Figure 3
Illustration of a correlated-channel P2P VoD system.The proposed scheme for cross-channel peer upload sharing is described as follows.(1)
Channelm(∀m∈M) finds a partner, channel k(k≠m,k∈M), to help each other, by using a resource-balancing scheme, which is described as follows. (i) Calculate Bmre, the amount of the total remaining bandwidth, for channel m(∀m∈M), the average amount of the total remaining bandwidth is given by Bavgre=(∑m∈MBmre)/|M| where |M| represents the number of channels. (ii) Given the set of unchosen channels Mun, the partner of channel m is determined by k=argj∈Munmin((1/2)(Bjre+Bmre)-Bavgre)2.(2)
Determine the set of cross-channel helpers in channelm, denoted by Y(m), by choosing the peers who have a remaining upload bandwidth greater than a thresholdbth. Sort Y(m) in a descending order based on the remaining upload bandwidth.(3)
Determine thedemanding segment set in channel k, denoted by W(k), by choosing |Y(m)| segments which are watched by the largest number of peers. Sort W(k) in a descending order based on the number of watching peers.(4)
Assign theith cross-channel helper in Y(m) to serve the peers watching the ith segment in W(k). Determine the incoming rate and outgoing rates at the ith cross-channel helper to maximize the bandwidth gain.(5)
After allocating the rate for each of the cross-channel links as in Step (4), revise the optimization problem (12) by integrating the cross-channel link rates and then solve it to obtain the optimal server upload allocation for each channel and the optimal link rates within each overlay.Peer dynamics have an impact on the streaming capacity in correlated-channel P2P VoD systems. First, the peers may leave or join a channel dynamically. Second, the cross-channel helpers may leave the channel, which causes the disconnection of the cross-channel links. To handle the dynamic conditions, the optimizations of intra-channel resource allocation and cross-channel resource allocation need to be performed in a discrete-time manner, in which the peers and the overlay are assumed to remain unchanged during a time slot, and the algorithms for resource allocation are performed at the beginning of each time slot.


## 5. Simulations

In the simulations, we use two classes of peers: cable/DSL peers and Ethernet peers. Cable/DSL peers take 85% of the total peer population with download capacity uniformly distributed between 0.9 Mbps and 1.5 Mbps and upload capacity uniformly distributed between 0.3 Mbps and 0.6 Mbps. Ethernet peers take the remaining 15% of the total peer population with both upload and download capacities uniformly distributed between 1.5 Mbps and 3.0 Mbps. The length of the video is 60 minutes, which is evenly divided into 60 segments. Each peer maintains a buffer with a capacity of 5 segments. The playback time of each peer is randomly distributed between 0 and 60 minutes. The priorities for all channels are equal.Figure4 compares the average streaming capacity between the equal server upload scheme and the optimized server upload scheme. In the equal server upload scheme, each channel is allocated an equal server upload, the link rates within each channel are optimized by solving the optimization problem (3). In the optimized server upload scheme, the server upload for each channel and the link rates within each channel are jointly optimized by solving the optimization problem (12). The equal server upload scheme considers only intra-channel resource allocation [10], while the optimized server upload scheme considers both intra-channel and cross-channel resource allocation. The number of the peers in a channel is uniformly distributed between 10 and 150. The server upload capacity is 45.0 Mbps. The optimized server upload scheme improves the average streaming capacity by 14.1% in average compared to the equal server upload scheme.Figure 4
Comparison of average streaming capacity with different number of channels.We show in Figure5 the impact of server upload capacity to the average streaming capacity for a P2P VoD system with 2 channels. The first channel has 40 peers, and the second one has 120 peers. As shown in Figure 5, the average streaming capacity is increased with the server upload capacity. The improvement brought by the optimized server upload scheme is larger when the server upload capacity is larger.Figure 5
Impact of server upload capacity to the average streaming capacity.Joint consideration of server upload optimization and cross-channel peer upload sharing can improve the performance in a correlated P2P VoD system, as shown in Figure6. There are two channels with total 200 peers in the P2P VoD system. The server upload capacity is 20.0 Mbps. We vary the number of the peers in channel 1 from 20 to 140 and evaluate two metrics: peer upload utilization ratio and average streaming capacity. Peer upload utilization ratio is defined by β=Σi∈N,i≠1vi/Σi∈N,i≠1Oi where Σi∈N,i≠1vi represents the sum of the outgoing rates from all peers except the server, and Σi∈N,i≠1Oi represents the sum of the upload capacities of all peers except the server. Due to a better utilization of cross-channel resources, joint consideration of server upload optimization and cross-channel peer upload sharing improves the peer upload utilization ratio by 7.7% in average, as shown in Figure 6(a), and improves the average streaming capacity by 0.04 Mbps in average, as shown in Figure 6(b), compared to optimized server upload scheme.Performance improvement brought by cross-channel peer upload sharing: (a) peer upload utilization ratio, and (b) average streaming capacity.
(a)(b)


## 6. Conclusion

In this paper, we studied the streaming capacity problem for multi-channel P2P VoD systems. Depending on the resource correlation, multi-channel P2P VoD systems can be categorized into independent-channel P2P VoD systems and correlated-channel P2P VoD systems. Since there is no resource correlation among channels in an independent-channel P2P VoD system, we just need to find the streaming capacity for each individual channel, respectively. We formulated the streaming capacity problem for a single channel into an LP problem and solved it with a distributed algorithm. In a correlated-channel P2P VoD system, we optimized both the intra-channel resource allocation and cross-channel resource allocation to improve the streaming capacity. In order to better utilize the cross-channel resource, we first optimized the server upload allocation among channels to maximize the average streaming capacity and then introduced cross-channel helpers to enable cross-channel sharing of peer upload bandwidth. We demonstrated in the simulations that the correlated-channel P2P VoD systems with both intra-channel and cross-channel resource allocation can achieve a higher average streaming capacity compared to the independent-channel P2P VoD systems with only intra-channel resource allocation.



---

*Source: 807520-2012-02-29.xml*