当前位置:首页 >> 工学 >>

Coalition-Based


IEEE TRANSACTIONS ON BROADCASTING, VOL. 54, NO. 3, SEPTEMBER 2008

557

Coalition-Based Resource Reciprocation Strategies for P2P Multimedia Broadcasting
Hyunggon Park, Student Member, IEEE, and Mihaela van der Schaar, Senior Member, IEEE
Abstract—In this paper, we consider a peer-to-peer (P2P) network, where multimedia streams are broadcast by matched peers based on their resource reciprocation pro?les. We propose a new framework where each peer creates a coalition of matched peers with which it can exchange resources in order to improve its utility. The utility is determined based on explicit consideration of the peer’s multimedia attributes and the quality derived by the peers’ reciprocation behavior. We adopt the proportional bargaining solution to negotiate the upload bandwidth among the matched peers. Proportional bargaining allows to determine each peer’s optimal (in a Pareto optimal sense) upload rates in a coalition in terms of its utility impact. The impact of an incoming peer on the coalition value, which represents the collective utility achieved by the peers in a coalition, is assessed by explicitly investigating the coalition value improvement. Finally, our results show that the proposed coalition-based resource reciprocation can improve the resource allocation/scheduling algorithms deployed in existing P2P systems such as BitTorrent and CoolStreaming. We also discuss how the proposed resource reciprocation approach can be implemented in other multimedia broadcasting applications. Index Terms—Coalitions, multimedia peer-to-peer (P2P) broadcast, peer matching, proportional bargaining solution, P2P network, service level.

P

I. INTRODUCTION 2P applications (e.g., [1], [2]) have become increasingly popular and represent a large majority of the traf?c currently transmitted over the Internet. One of the unique aspects of P2P networks stems from its ?exible and distributed nature, where each peer can act as both server and client [3]. Due to these characteristics, it has been recently proposed to use P2P networks for multimedia streaming and broadcasting [4]–[7]. Moreover, several media streaming and broadcasting systems have been developed for P2P networks using different approaches such as tree-based or data-driven approaches (e.g. [8]–[10]). While the above mentioned multimedia streaming and broadcasting systems over P2P networks have been successfully developed, the focus of P2P for multimedia is on developing ef?cient streaming solutions given a certain P2P network. In this paper, we consider a chunk-based and data-driven multimedia P2P broadcasting system such as CoolStreaming [4] and Chainsaw [5], which adopt pull-based techniques [5],
Manuscript received November 20, 2007; revised March 27, 2008. Published August 20, 2008 (projected). This work was supported by UC Micro and NSF CCF-0541867. The authors are with the Electrical Engineering Department, University of California, Los Angeles, (UCLA), Los Angeles, CA 90095 USA. (e-mail: hgpark@ee.ucla.edu; mihaela@ee.ucla.edu). Color versions of one or more of the ?gures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identi?er 10.1109/TBC.2008.2001148

[6]. In this system, a multimedia stream is divided into chunks, which are broadcast over the P2P network. The peers possess several chunks and these chunks are shared by the interested1 peers. While this approach has been successfully deployed in real-time multimedia broadcasting over P2P networks, key challenges such as incentives for cooperation and designing ef?cient resource-reciprocation solutions among the autonomous peers still remain open. Speci?cally, pull-based techniques assume that the peers in the P2P network are altruistic and they provide their available chunks whenever requested. Several works such as [11], [12] propose how to design the incentives for cooperation in general P2P networks. For example, a general ?le download solution such as BitTorrent adopts a tit-for-tat (TFT) algorithm (or choking algorithm) [11]. This algorithm favors peers that have higher upload rates and penalizes free-riders, thereby encouraging the peers to allocate more upload bandwidth [13]. While this algorithm can provide incentives for cooperation, it does not consider the exact resource reciprocation. Rather, a peer equally allocates its available bandwidth to a ?xed number of peers (i.e., leechers) having the highest upload rates [11]. This approach has been shown to be inef?cient for multimedia applications [14]. Hence, this solution cannot be directly deployed for multimedia broadcasting as it does not ef?ciently consider important issues related to the quality of service (QoS) requirements such as the derived quality and delay sensitivity. In order to address these issues for multimedia broadcasting, several works such as [15], [16] have been proposed. While they successfully provide incentives for cooperation in multimedia broadcasting, the resource reciprocation among peers is not explicitly considered. In this paper, to explicitly consider the resource reciprocation among the interested multimedia peers, we discriminate the peers based on their multimedia attributes such as the derived quality, which is neglected by existing solutions. For instance, the TFT strategy in BitTorrent allows a peer to choke2 the already associated peers at any rechoke period if they ?nd new peers that can provide higher upload rates. Thus, TFT can only considers provisional connections among the associated peers. Hence, this strategy for multimedia content sharing cannot guarantee an acceptable quality for broadcast at all times. To overcome this issue, we introduce the service level, which represents the level of guaranteed bandwidth that the peer promises to sustain to the matched peers in its coalition. We show that a higher service level can reduce the quality ?uctuations in P2P based multimedia broadcasting.
1In [11], it is said that peer A is interested in peer B when B has chunks of the content that A would like to possess. 2It is said that peer A is choked by peer B when B decides not to send any data to A.

0018-9316/$25.00 ? 2008 IEEE

558

IEEE TRANSACTIONS ON BROADCASTING, VOL. 54, NO. 3, SEPTEMBER 2008

A peer can create a coalition with its matched peers, which agree to share their chunks. In the created coalitions, peers negotiate their upload bandwidth based on their contributions to the coalitions, while explicitly considering their quality impact. We de?ne appropriate utility functions to consider the derived multimedia qualities and the negotiated download/upload rates. Hence, utility-based resource negotiation enables peers to determine how much upload bandwidth they should provide, while considering the resulting quality impact. In order to achieve this, we propose to deploy the proportional bargaining solution (PBS) [17]. This paper is organized as follows. In Section II, we propose a framework for multimedia broadcasting over the P2P network and abstract the attributes of peers based on their multimedia characteristics. In Section III, we discuss the cooperative behavior and the corresponding achievable utilities. In Section IV, we discuss the upload bandwidth reciprocation among the peers and its resulting utilities determined by PBS. In Section V, we study how much the peers bene?t by making coalitions and analyze the impact of their interactions in terms of the coalition value. Simulation results are provided in Section VI and conclusions are drawn in Section VII. II. COALITION FORMATION BASED ON MULTIMEDIA PEERS’ ATTRIBUTES A. Coalition Formation When a peer joins the P2P network, the ?rst step for the incoming peer is to identify the peers that are interested in the same content. As discussed in [4], the incoming peer can contact a source node, which generates/broadcasts the new multimedia content, and the peer can be redirected to the other peers that are already associated with the source node in the overlay. Hence, the peers that are interested in the same content will interact with each other by sharing (i.e., downloading and uploading) chunks of the interested content. The detailed process to create and maintain the connections among the peers can be found in e.g., [4], [5]. In this paper, we consider the case where a source node distributes multimedia content and the peers that are interested in it interact with each other by sharing their content and negotiating their resources. This can be easily extended to the case when multiple multimedia contents from multiple source nodes are simultaneously broadcast. Our focus is on the resource reciprocation among the peers that are interested in each other.3 When two peers are interested in each other, they are referred to as matched peers. More specifand are matched if peer is interically, any two peers ested in the chunks that peer possesses and peer is also interested in the chunks that peer possesses. Peer includes in its matched peers with which it will exchange its coalition chunks. In the process of chunk exchanges, resource reciprocation is necessary for the peers to improve their utilities based on their limited upload bandwidths (i.e., resources). An illustrative example of coalitions in a P2P network is shown in Fig. 1(a).
3If a peer m is interested in n, while n is not interested m, then we assume that peer n provides the minimum upload bandwidth, which is similar to the optimistic unchoke in BitTorrent [11]. This operation can help to maintain the coalitions and to increase the P2P network capacity as peer n can contribute its chunks in the future interactions.

Fig. 1. Illustrative examples of coalitions and chunks. (a) An illustration of coalitions (C and C ); (b) peers matched to peer m in C and their chunks.

In this example, two coalitions and , formed by peer and peer with their matched peers, are depicted. Moreover, the are chunks possessed and required by the peers in coalition illustrated in Fig. 1(b). A peer maintains a window of interest (or an active buffer) as in [4], [5], which represents the range of chunks that the peer is interested in obtaining at the current are time. As Fig. 1(b) shows, the chunks required for peer . available in its coalition B. Models for Multimedia Peer’s Attributes The multimedia peers in the P2P network can be characterized by their possessed and demanded chunks, their preferences for the content, available bandwidth, as well as the cost for upload [18]–[21]. Moreover, a quality function is required to assess the achievable multimedia quality based on the download rates, and a minimum download rate for a demanded multimedia content is required to successfully decode the content [22]. We de?ne a peer’s service level as its commitment to sustaining an upload bandwidth for its matched peers. In the considered P2P-based multimedia broadcasting, we can abstract the attributes of peer as (1) denotes a multimedia content in which peer is interwhere is the minimum required ested with its preference and rate to successfully decode . If this condition is not satis?ed, a peer cannot decode the downloaded multimedia chunks, and

PARK AND VAN DER SCHAAR: COALITION-BASED RESOURCE RECIPROCATION STRATEGIES

559

hence, it achieves no utility. denotes the available chunks for peer , which will be continuously exchanged among the associated peers. This is similar to the Buffer Map deployed in [4]. denotes the available upload bandwidth4 of peer . Note that the available upload bandwidth of a peer will decrease as it associates with more peers. The achieved quality is denoted by , which can given the download rate be represented by the Peak Signal to Noise Ratio (PSNR). is the service level, which will be discussed later, and denotes the per unit cost of uploading rate that can be determined as in [21]. We de?ne a utility function that captures this behavior of multimedia peers. The utility function of peer , which is downat rate and providing upload rate loading content to other peers, is de?ned as:

Note that other characteristics of P2P networks such as reliability, contract, and reputation can also be included as attributes of peers. However, we do not consider them in this paper, as they are already discussed in the prior literature [23], [25], and they can be incorporated in our framework. III. CHARACTERIZATION OF PEERS’ INTERACTIONS In this section, we consider the utility-based interactions between autonomous and self-interested peers in a P2P network. A. Motivating Example: Incentives for Peers’ Collaboration As motivating examples, we discuss simple cases where two peers do not cooperate or overly cooperate. Note that this derivation can be easily extended to the general -peer case. In this analysis, we consider two matched peers and . 1) Non-Cooperative Interactions: Based on the de?nition of and can be utility function as in (2), the utilities of peer expressed as

if otherwise

,

(2) represents the speci?c minwhere a non-negative constant imum required rates to decode the video sequence. Peer ’s utility increases as it derives a higher quality by downloading at higher rates. The utility also increases as peer reduces its upis a function of , i.e., load bandwidth. Download rate , since they are determined based on the resource reciprocation among the associated peers.5 The resource reciprocation is investigated in Section III. Note that different utilities can be de?ned and employed in our framework depending on the P2P applications. represents peer ’s level of The service level6 commitment to maintain the upload bandwidth promised to the associated peers. For instance, the available upload bandwidth of peer matched to the other peers is determined by

(3) denotes peer ’s where is the service level of peer , and current upload bandwidth for peer . This expression shows that a higher value of service level of a peer will result in a lower available upload bandwidth for the future resource negotiation with incoming peers, as it sustains an upload bandwidth for the already established connections. For instance, peer with uses its maximum available upload bandwidth whenever new incoming peers join , while it only uses the re. The effect of the service maining upload bandwidth if level on making coalitions and negotiating upload bandwidths will be discussed in Section V. Importantly, it will be shown that a higher service level provides more stable multimedia quality.
4In this paper, we focus on the upload bandwidth allocation since the maximum upload bandwidth L of peer i is typically smaller than the maximum download bandwidth, e.g., ADSL, cable network, etc. 5In this paper, we use notation R instead of R (R ) for simplicity. 6The service level can be determined based on peers’ reputation [23], experience, or characteristics such as risk-averse or risk-lover [24]. While we do not explicitly examine algorithms to determine this parameter dynamically, the impact on coalition formation and upload bandwidth negotiation can be investigated by considering two extreme cases.

If both peers are non-cooperative, each peer only tries to improve its utility without considering the impact on the other can improve its utility by repeers’ utilities. Hence, peer ducing its upload rate by , and peer can also reduce as a response of peer ’s upload rate its upload rate by change. The resulting utilities of two peers become and . To minimize the penalties due to the cost for upload, two peers will continuously reduce their upload rate, which leads to the and , bandwidth reciprocation , ). Thus, the non-coand thus, zero utilities (i.e., operative behavior of peers in a P2P network eventually results in zero utilities for every peer. It can be interpreted that if there is no cooperation among peers, then the collapse of a P2P network is possible [26], i.e., no utility can be provided to peers through a P2P network. A well-known example for this non-cooperative behavior of peers is the free-riding [26] in P2P networks. 2) Overly Cooperative Interactions: Alternatively, we consider the case where peers are completely cooperative, by providing their entire upload bandwidth to other peer’s and be the maximum available download. Let and , respectively. Since they upload bandwidth for peers completely collaborate by providing their maximum available upload bandwidth, their achievable utilities are expressed as and , respectively. Since these utilities can be negative depending on their costs, quality functions, and the provided maximum upload bandwidth, the complete cooperation among peers does not always bene?t them. Rather, it may penalize the participating peers in terms of the derived utility. Moreover, this type of over altruistic cooperation can also prevent incoming peers which join the P2P network at a later time from associating with these peers, as the available upload bandwidth of the peers in the network is already exhausted. This may lead to inef?cient bandwidth

560

IEEE TRANSACTIONS ON BROADCASTING, VOL. 54, NO. 3, SEPTEMBER 2008

utilization for peers as well as the P2P system in terms of the derived utilities. Therefore, the cooperative negotiation for determining the upload bandwidth among peers is essential for improving both each peer’s utility and the total utility in P2P network. B. Example of Collaboration Between Two Peers In this section, we analyze the collaborative two-peer’s interaction and its achievable utility. Unlike the non-cooperative types of peers, the matched peers exchange information that is required to establish their cooperation. In this simple cooperative two-peer scenario, we assume that two peers and agree before making their coalition to provide their upload bandwidth as long as the allocated bandwidth enables them to achieve positive utilities. Note that each peer achieves no utility (i.e., zero utility) if they are not associated with each other. Based on can ?rst provide its upload bandwidth this agreement, peer to peer [27], which results in

Fig. 2. Achievable utilities U and U for two peers with respect to peer m’s .  = 0 induces the highest utility for peer m while peer n upload rate R achieves the lowest utility, and vice versa. The shapes of achievable utilities are determined by their utility functions and peer-dependent cost.

After receiving from peer , peer can now provide its if it does not make its achievable utility upload bandwidth negative (if it is not possible, they cannot interact cooperatively). needs to satisfy Hence,

utility of peer . Note that

, which are a function of the upload rate of peer in (6) can be parameterized by the variable :

and it leads to the maximum upload rate that peer which is

can provide,

(7) . As Fig. 2 illustrates, it is easily observed where that there is a con?ict of interest between two peers’ utilities , where according to their upload rates. For instance, if peer supports the minimum upload rate to peer , peer can achieve the minimum utility 0 while peer can achieve the highest achievable utility, and vice versa. Hence, variable can be viewed as an altruism parameter [28] of peer , represents that peer is the least altruistic where represents for providing its upload bandwidth, while that peer is ideally altruistic. However, we note that in this paper, this variable is not a pre-determined peer-speci?c constant. Rather, it will be determined by the upload bandwidth negotiation, which will be discussed in Section IV. Hence, each peer’s utility can be expressed as a function of using (7): and . Based on the above analysis, we can summarize that, through cooperation, the peers can derive positive utilities. However, the utilities that each peer can derive are jointly connected as a function of each peer’s upload rates and . Hence, it is imperative to determine the optimal upload rates of each peer in the coalition and in this example), while (e.g., determine explicitly considering the derived utility and each peer’s contribution to the coalition. This will be discussed in Section IV.

(4) Moreover, the upload rate from peer should also guarantee that peer can derive a positive utility. Hence,

which leads to the minimum upload rate,

(5) From (4), (5), and the required minimum rates, peer in the range of vide its upload rate can pro-

(6) Summarizing, (6) implies that the upload rate of peer is upperbounded by the rate that achieves the minimum utility of peer and lower-bounded by the rate that achieves the minimum

PARK AND VAN DER SCHAAR: COALITION-BASED RESOURCE RECIPROCATION STRATEGIES

561

C. Cooperative Peers’ Interactions In this section, we generalize the interactions of peers sharing multimedia content in a P2P network. Since a peer interacts with several matched peers in its coalition, we focus on a one-tomany peers’ interaction. be the coalition of peer 1, where peer Let matched peers while negotiating 1 interacts with its resource reciprocation. The utilities of the peers in the coalition are expressed as

Eq. (10) can be expressed using

in (11) as

(12) Therefore, the upload rate can be expressed as

(13) (8) with variable . Note that is a function of from peer 1 to peer and parameters of peer upload rates in (i.e., upload/download rates in and ). is also , from peer 1 to its a function of upload rates . peers in , and coalition parameters of peer l, Therefore, by substituting (13) into (8) and (9), the achievable can be expressed as a function of peer 1’s upload utilities in rates to its coalition peers given the other coalition parameters. Hence, it can be concluded that if the feasible upload rate pairs satisfying (11) and (12) can be found, the peers’ cooperative behavior ?nally bene?ts the participating peers in this cooperative interaction. Therefore, it is essential for peers to form coalitions that enable peers to interact with each other cooperatively. The remaining question is hence how to negotiate an agreement for determining the upload rates of all peers after in a coalimaking a coalition (i.e., determining for all tion ). In the following sections, we resolve this problem by relying on axiomatic bargaining theory among the peers. Note that the proposed bargaining solution provides axioms that can be dictated by the adopted P2P protocol for the resource reciprocation in the coalitions. Hence, there is no need for an iterative bargaining process among peers. IV. COALITION BASED UPLOAD BANDWIDTH NEGOTIATION In this section, we discuss the upload bandwidth negotiation and determine the optimal upload rates of the peers in a coalition based on the derived utility and each peer’s contribution to the coalition. A. Resource Reciprocation and Resulting Utilities In order to determine the optimal upload rates of peers based on the derived utility and each peer’s contribution to the coalition, it is required to identify the feasible utility set. For this analysis, we again assume that peer 1 interacts with the other peers in . The feasible utility set can be obtained given the utility functions of peers and their interactions for the upload rates, which is expressed as

(9) denotes the upload rate of peer to peer . where Note that peer in assumes that the resource reciprocations of the associated peers in its coalition are stationary as shown for two sets represents the relative in (9). The expression of complement of in . Since peer is associated with peer 1 as well as other peers in , the achieved utility of peer depends provided by peer 1 and provided on the upload rates . It also depends on the provided by the other peers upload rates from peer to the associated peers. Note that the upload rates that peer can provide to peer 1 depends on , which implies that peers the service level of peer . If do not promise to sustain the already established connections in , then peer can provide its maximum upload bandwidth to peer 1, i.e., . However, if , peer can provide only the remaining upload bandwidth to peer 1, , while sustaining the already established i.e., connection in its coalition . Since every peer needs to achieve at least a minimum utility (i.e., zero utility), (8) and (9) can be rewritten as

(10)

(11)

(14)

562

IEEE TRANSACTIONS ON BROADCASTING, VOL. 54, NO. 3, SEPTEMBER 2008

peers in a coalition can also be considered as contributions, which can determine . By deploying proportional bargaining solution (PBS) [17] to with the vector , a unique utility the bargaining problem can be thereby determined as point

(16) where denotes the PBS and based on the PBS determined utility point . Note that the satis?es

(17) Hence, vector can be interpreted as the weight of the peers based on their contributions to the coalition. Several properties of PBS can be found in [17]. Among them, monotonicity9 will be used to analyze the coalition value dynamics as peers join the coalitions (see Section V). Note that given vector , the unique utility pair selected by PBS is optimal (in the sense of Pareto optimality). by PBS can be ef?ciently Determining a unique solution performed using numerical tools such as the bisection method without identifying the entire feasible utility set [14]. Although computing PBS may incur higher initial delay for resource reciprocation process than heuristic approaches deployed in [4], random packet selection approach [5], or the TFT strategy, the proposed approach can ef?ciently utilize multiple peers’ resources. Hence, the proposed approach can improve the video quality and provide a steady video quality, which is desired for multimedia broadcasting. Hence, overall delay for multimedia broadcasting can be reduced. These tradeoffs are illustrated in Section VI. Algorithm 1 summarizes the negotiation of the upload bandwidth based on PBS in a coalition. Algorithm 1 Upload Bandwidth Negotiation in

Fig. 3. Illustrative examples for utility pairs derived by cooperative interactions of peers.

where

, for all , where

, and

for . The feasible utility set includes all the possible interactions of peers, i.e., cooperative interactions as well as non-cooperative interactions. Moreover, each peer’s can also be identi?ed and minimum required utility7 considered in the upload bandwidth negotiation. The outcome of the upload bandwidth negotiation needs to be Pareto optimal and yield higher utilities than the minimum required quality. Thus, peers’ agreement on their derived utilities is located in , expressed as set8

(15) where denotes the boundary [17] of feasible utility set . An illustrative example of utility pairs derived by the results of two-peer’s cooperative interactions is shown in Fig. 3. Different upload rates result in different utility pairs and their maximal values are elements of the bargaining set. B. Resource Reciprocation Based on Contributions We now discuss how the peers can agree on a unique utility point. Given feasible utility set in (14) and the minimum required utility , peers can agree on a unique utility point based , referred to as inter-peer utility on a vector comparison ratio vector. The vector represents each peer’s contribution to their coalition and can be adjusted based on the goal of the peers in the coalition. For example, if the available upload bandwidth of peers are considered as their contributions, , . Alternavector can be determined as tively, the number of chunks that are requested by the matched
7This 8This

1: Form Feasible Utility Set : From peers’ attributes , , peers form and the disagreement point . 2: Determine inter-peer utility comparison ratio vector : Based on the peers’ contribution to the coalition, vector for PBS is determined. : A unique utility 3: Determine Operating Utility Point is determined based on the PBS with ; point . , peers determine 4: Determine Upload Bandwidth: Given for all . their upload bandwidth; V. COALITION VALUE AND ITS DYNAMICS In this section, we study how much the peers bene?t by making coalitions and analyze the impact of their interactions in terms of the coalition value.
[F (S; d)]
9Monotonicity:

is called disagreement point in axiomatic bargaining theory [24]. set is called bargaining set [24].

[

F(

For any two feasible utility sets S ; d)] for all i.

S

and

S, if S

 S then

PARK AND VAN DER SCHAAR: COALITION-BASED RESOURCE RECIPROCATION STRATEGIES

563

A. Service Level and Coalition Value Dynamics Coalition value is the total utility derived by the peers in a coalition and represents the bene?t of cooperation among the be the coalition of peer at peers in the coalition. Let round10 . Initially, peer exists as a self-coalition at round 0, with . Incoming peers matched to peer i.e., can join . In , the coalition value for determined by PBS is given by

networks. Hence, the service level needs to be determined considering these tradeoffs. In the rest of the analysis, we assume . that the service level of each peer is B. Peers’ Joining and Coalition Value Dynamics on In order to quantify the impact of peer ’s joining the coalition value, the coalition value improvement needs to be for all , we have investigated. Since

where is the feasible utility set formed by the interaction and is their disagreement point. among the peers in Suppose that an incoming peer matched to peer joins at round , i.e., . For the PBS with peer at round , the disagreement point of all peers is updated by , expressed as

Similarly,

(18) for , and Hence, the improvement of coalition value tional matched peer can be expressed as by an addi-

(20) (19) where is the service level of peer in . Moreover, , since peer is an incoming peer. As shown in (3), (18), and (19), the service levels signi?cantly impact the resource reciprocation among the peers in their coali, they try to tions. For example, if peers in a coalition have ?nd better matched peers that can provide higher upload rates at every round as they are not obligated to sustain any upload bandwidth for currently associated peers. While this can lead to a higher achievable utility for peers depending on the associated peers, they can suffer from frequent connection loss, which can lead to signi?cant ?uctuations of the derived utility. Moreover, the complexity required for PBS computation can increase exponentially since the number of peers that can be associated with a peer can increase signi?cantly. Hence, the interaction of do not guarantee a steady level of quality peers with , for multimedia applications. However, if peers have they sustain the established connections unless the associated peers leave the P2P network. Peers in a coalition can derive less achievable utility, but they are able to attain a stable achievable utility, leading to quality guarantee for multimedia. This is an important feature for multimedia content distribution over P2P
10The term round is adopted from [11] to represent the time when PBS is executed. In this paper, rounds are equivalent to the instances of peers’ joining or leaving coalitions.

Since , the joining of a matched peer does not decrease the coalition value. We also show that the coalition value improvement is a non-increasing function as the number of peers with similar , attributes increases. Let peer be in a coalition at round and peer join the coalition at round and and peer , respectively. Since peer uses the residual bandwidth as upload that is left after bargaining at round with peer at round , and the disagreement point of rate for peer ), we have peer increases (i.e.,

(21) where round PBS, and and are the feasible utility sets formed at , respectively. By the monotonicity of the

(22) and therefore,

(23)

564

IEEE TRANSACTIONS ON BROADCASTING, VOL. 54, NO. 3, SEPTEMBER 2008

Thus, the coalition value improvement is a non-increasing function. Since the maximum upload bandwidth is gener, which ally ?nite, we have implies that the coalition value improvement by incoming consequently converges to zero as , i.e., peer . This upload bandwidth negotiation can be easily applied iteratively at each round, as multiple peers join the coalition. VI. SIMULATION RESULTS In this section, we provide simulation results of the proposed framework for matching peers for multimedia broadcasting over P2P networks. In order to illustrate the potential impact of the proposed coalition-based resource reciprocation on multimedia P2P broadcasting networks, several simulations are performed based on the PlanetLab experimental platform as in [11]. We assume that the broadcast video ?les are at CIF (352 288) resolution, 30 frames/sec, as well as encoded in a prioritized manner using the H.264/AVC encoder [22]. The encoded video ?les are partitioned into chunks that have uniform size of 50 Kbits. Peers download ?rst the chunks that have the highest impact on the video quality. In these experiments, a single video ?le has 100 seconds duration, which was obtained by concatenating 10 identical MPEG test sequences. We assume that peers can change their available upload bandwidth, or disconnect at each round. In our simulations, 1000 peers are registered in the P2P network with various multimedia attributes. Relevant peers’ attributes are presented in each simulation. A. Effect of Service Level We investigate two cases of service levels, and for all in a coalition. Recall that if for all peers in a coalition, they maintain their established connections and negotiate their remaining bandwidth with incoming peers. If for all peers in a coalition, peers do not promise to sustain their established connection and renegotiate their available upload bandwidth at all times. In order to investigate the impact of the for all in vector . service level, we assume that We focus on coalition 1 which is created by peer 1 and its matched incoming peers that join the coalition sequentially. Two separate simulations are performed with two different video sequences: Foreman and Coastguard. The maximum upload bandwidth of each peer is given by . Simulation results are shown in Fig. 4 and Table I. Fig. 4 shows the achieved quality of peer 1 when it downloads the Foreman sequence or Coastguard video sequences. As disprovides an stable cussed above, the achieved quality with quality over time because the associated peers sustain their upload bandwidth. However, while the achieved quality with can be higher than that with (e.g., ?rst 12 seconds), signi?cant ?uctuation in the achieved quality can occur, which is not desirable for multimedia broadcasting (e.g., approximately a 10 dB and 6 dB difference in terms of PSNR, respectively). Note that a larger ?uctuation in PSNR generally results in a higher ?uctuation in perceptual quality [29], thereby leading to signifis preicant perceptual quality degradation [30]. Hence, ferred for the considered multimedia P2P broadcasting system. B. Comparison With Other Resource Reciprocation Strategies In this section, we illustrate the achievable utilities of peers in a coalition based on different resource reciprocation strategies. We consider several different P2P network scenarios: (i) a simple P2P system that cannot detect and cannot prevent freeriders (e.g., Gnutella [26]), (ii) a more sophisticated and adaptive P2P system that can detect and prevent free-riders effectively but does not consider the multimedia utility impact (e.g., a BitTorrent-like system [11]), and (iii) the proposed P2P system that explicitly considers each peer’s multimedia attributes as well as free-rider prevention when performing resource reciprocation. Note that we present the result for a representative coalition that was formed in a network with 1000 peers. We assume that the peers are interested in the Stefan video sequence. The maximum upload bandwidth of each peer is given and the unit by costs of uploading rate are peer-dependent and pre-determined. In scenarios (i) and (ii), we assume that each peer shares part of its upload bandwidth with the matched peers due to the incurred cost. However, in scenario (iii), the upload bandwidth allocation is negotiated by PBS considering the utility impact. To study the impact of the resource reciprocation strategies on the utilities, we consider two simple bandwidth allocation strategies. The available bandwidth can be equally divided (Equal Bandwidth Division) for scenarios (i) and (ii) as in a BitTorrent-like for scenario system, and equivalently (iii). Alternatively, the available bandwidth can be proportionally divided (Proportional Bandwidth Division) based on each

Fig. 4. Achieved quality with different service levels in a coalition.

TABLE I ACHIEVED QUALITIES WITH DIFFERENT SERVICE LEVELS IN COALITION

PARK AND VAN DER SCHAAR: COALITION-BASED RESOURCE RECIPROCATION STRATEGIES

565

TABLE II ACHIEVABLE INDIVIDUAL QUALITIES IN DIFFERENT SCENARIOS

peer’s maximum upload bandwidth for scenarios (i) and (ii), and for scenario (iii). We assume that a thus, free-rider is connected to peer 1. Simulation results are shown in Table II. The results of scenario (i) and scenario (ii) using the two bandwidth division strategies (equal bandwidth division and proportional bandwidth division) show that the quality derived in scenario (ii) is always higher than that derived in scenario (i). This occurs because in scenario (i) the free-rider obtains a part of the available bandwidth without contribution to the coalition. The results of scenario (ii) and scenario (iii) in the bandwidth division strategies show that scenario (iii) provides improved qualities since the PBS explicitly considers the impact of peers’ attributes as well as the incurred cost. Moreover, scenario (iii) always provides improved individual qualities except for peer 2 and peer 3 in the proportional bandwidth division. The results show that the proportional bandwidth division strategy in scenario (i) and (ii) does not result in proportional utilities for the peers in the coalition. However, PBS does provide rewards, in terms of the utility, proportional to their contributions. These proportional rewards act as an incentive for the peers. C. Comparison With TFT Strategy In this section, we investigate the coalition formation and the resulting performance in terms of utilities based on the proposed and resource reciprocation strategies (i.e., PBS with ) and a TFT strategy deployed in P2P systems such as BitTorrent [11]. To compare both strategies, we assume that there is no cost for providing upload bandwidth in coalition based bandwidth sharing strategy, as the TFT strategy does not consider it. Moreover, since the TFT strategy focuses only on the downloading rates from other peers, the utility in the proposed solution is de?ned to represent the downloading rate. The inter-peer utility comparison ratio vector is determined based on the download rates. We also assume that the maximum number of parallel uploads for a peer deploying the TFT strategy is two, as peers have the maximum number of parallel uploads in the leecher state [11]. In the following simulations, a peer creates its coalition by sequentially joining 11 matched peers, and bandwidth negotiation is performed in each round (i.e., when peers join or leave the coalition). The peer is downloading the Foreman or Mobile video sequences and its maximum upload bandwidth is
Fig. 5. Peers in each coalition for different strategies over time (rounds): (a) number of peers in each coalition; (b) peer index in coalition 1.

850 Kbps, which is the highest upload bandwidth among coalition peers. Note that all peers in the coalition provide their maximum upload bandwidth, which is assumed to be constant in this experiment, as no cost is incurred for providing their upload bandwidth. The simulation results are shown in Fig. 5, Fig. 6, and Table III. Fig. 5 shows the number and index of associated peers in selected coalitions (coalition 1, 2, and 3) over time (rounds). The corresponding achieved quality of peer 1 are shown in Fig. 6. During the ?rst 6 seconds (the ?rst round), the achieved quality of peer 1 are the same for all the strategies , and PBS with ). This occurs (i.e., TFT, PBS with due to the small number of coalition peers (in this example, two peers—peer 2 and peer 3—are associated) and that they provide their maximum upload bandwidth to peer 1. However, as more peers join this P2P network, and they create their own

566

IEEE TRANSACTIONS ON BROADCASTING, VOL. 54, NO. 3, SEPTEMBER 2008

). Moreover, due to the ?xed number of parallel uploads in the TFT strategy, other peers can choke this peer, leading to signi?cant loss of download rate and quality (e.g., the peer is choked by peer 2 and 3 at 20 second and at 50 second (round 3 and 5). However, PBS does not abruptly deny to provide upload rates. Rather, it enables peers to scale the upload rates smoothly, leading to smooth changes of quality even in the case . of the PBS with We can also observe a period of time where peer 1’s derived qualities decrease for both the TFT strategy and PBS with even though the same peers are associated (e.g., from 35 second to 53 second (at round 5, 6, and 7)). In this period, the associated peers for peer 1 create their own coalitions and negotiate their upload rates with their coalition peers. Hence, they decrease the upload rates for peer 1, resulting in decrease of , as we shown download rates of peer 1. In the case of in the previous section, the quality can be derived at a similar ensures a minlevel over the time. Note that PBS with imum multimedia quality (in these simulations, 32 dB PSNR for Foreman and 28dB PSNR for Mobile are assumed.), while the other strategies do not. Note that in Fig. 6, the upload bandwidth from each peer is ?xed, but different PSNRs are achieved due to different sequence characteristics (e.g., Foreman and Mobile). However, if larger upload bandwidth is available for each peer, a higher PSNR can be derived. These simulation results also show the resulting delay. If the minimum required quality is not satis?ed, the peers may pause their displays until they ?nd additional peers that have the necessary chunks. This can incur undesirable delay during the broadcasting besides the initial delay for the resource reciprocation process. In the simulation results, the TFT strategy can incur signi?cant delays during the broadcasting. Therefore, although the PBS incurs some initial delays for the resource reciprocation process, the overall delay can be reduced. This forms an interesting area for future research. D. Application to Other Usage Scenarios
Fig. 6. The achieved qualities for different strategies: (a) Foreman sequence; (b) Mobile sequence.

TABLE III THE ACHIEVED QUALITIES WITH DIFFERENT STRATEGIES

coalitions, the download rates of peer 1 vary. Since the TFT strategy allows peers to maintain a ?xed maximum number of parallel uploads with peers providing the highest upload rates, its download rates can be smaller than the proposed coalition based resource reciprocation strategy (i.e., PBS with

Simulations results presented in this section show that the proposed resource reciprocation based on the PBS with is preferred for a multimedia broadcasting system, which requires a stable multimedia quality. Hence, for example, the proposed approach can be adopted into proxy-based solutions (e.g., [31]) for several streaming video applications such as distance learning, Internet TV broadcasting, and video-on-demand (VoD) streaming services. Unlike P2P systems, where the service level can be determined by individual peers, if the proposed approach is implemented in the proxy servers, for PBS can be ensured, as they are dedicated to video distribution to clients. Thus, the proposed approach enables the proxy servers to support a stable quality multimedia services, while considering several constraints such as the different available bandwidths of heterogeneous clients. The proposed approach can also be deployed in chaining schemes (e.g., [32]), as each client can forward its cached video streams to its associated clients. Hence, each client can divide its available bandwidth, while considering the quality impact as well as the associated clients’ video characteristics.

PARK AND VAN DER SCHAAR: COALITION-BASED RESOURCE RECIPROCATION STRATEGIES

567

VII. CONCLUSIONS In this paper, we propose quality driven bandwidth reciprocation strategies for multimedia broadcasting over P2P networks. The proposed framework enables peers to create/join coalitions with which they can cooperatively share their available chunks. Moreover, the proposed approach based on PBS enables the peers to reciprocate their resources such that the resulting utilities are proportional to their contributions to the coalition value. In order to investigate the impact of the peers’ attitude toward the other peers on the derived multimedia quality, the service level is introduced. We show that peers with a higher service level can guarantee more stable multimedia quality in the coalition. This feature is important for multimedia broadcasting applications. Simulation results show that the proposed coalitionbased resource reciprocation strategy is more ef?cient for P2P multimedia broadcast than the TFT strategy currently deployed in BitTorrent-like networks. We also discuss how the proposed approach can be implemented in other video streaming applications.

REFERENCES
[1] “Napster,” [Online]. Available: http://www.napster.com [2] “Gnutella,” [Online]. Available: http://www.gnutella.com [3] S. Androutsellis-Theotokis and D. Spinellis, “A survey of peer-to-peer content distribution technologies,” ACM Comp. Surveys, vol. 36, no. 4, pp. 335–371, Dec. 2004. [4] X. Zhang, J. Liu, B. Li, and T. S. P. Yum, “Coolstreaming/donet: A data-driven overlay network for ef?cient live media streaming,” in Proc. INFOCOM ’05, 2005. [5] V. Pai, K. Kumar, K. Tamilmani, V. Sambamurthy, and A. E. Mohr, “Chainsaw: Eliminating trees from overlay multicast,” in Proc. 4th Int. Workshop on Peer-to-Peer Systems (IPTPS), Feb. 2005. [6] J. Liu, S. G. Rao, B. Li, and H. Zhang, “Opportunities and challenges of peer-to-peer internet video broadcast,” in Proceedings of the IEEE, Special Issue on Recent Advances in Distributed Multimedia Commun., 2007. [7] M.-F. Leung and S.-H. G. Chan, “Broadcast-based peer-to-peer collaborative video streaming among mobiles,” IEEE Trans. Broadcast., vol. 53, no. 1, pp. 350–361, 2007. [8] X. Jiang, Y. Dong, D. Xu, and B. Bhargava, “GnuStream: A P2P media streaming system prototype,” in Proc. 4th Int. Conf. on Multimedia and Expo, Jul. 2003. [9] Y. Cui, B. Li, and K. Nahrstedt, “oStream: asynchronous streaming multicast in application-layer overlay networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 1, pp. 91–106, Jan. 2004. [10] V. N. Padmanabhan, H. J. Wang, and P. A. Chou, Microsoft Tech. Rep. MSR-TR-2003-11, Mar. 2003. [11] A. Legout, N. Liogkas, E. Kohler, and L. Zhang, Clustering and sharing incentives in BitTorrent systems INRIA-00112066, Tech. Rep. 1-21, Nov. 2006. [12] K. Lai, M. Feldman, I. Stoica, and J. Chuang, “Incentives for cooperation in peer-to-peer networks,” in Proc. Workshop on Economics of Peer-to-Peer Systems, 2003. [13] T. Locher, P. Moor, S. Schmid, and R. Wattenhofer, “Free riding in BitTorrent is cheap,” in Proc. HotNets-V, Irivine, CA, Nov. 2006. [14] H. Park and M. van der Schaar, “Bargaining strategies for networked multimedia resource management,” IEEE Trans. Signal Process., vol. 55, no. 7, pp. 3496–3511, Jul. 2007. [15] A. Habib and J. Chuang, “Service differentiated peer selection: an incentive mechanism for peer-to-peer media streaming,” IEEE Trans. Multimedia, vol. 8, no. 3, pp. 610–621, June 2006.

[16] Y.-H. Chu, J. Chuang, and H. Zhang, “A case for taxation in peer-topeer streaming broadcast,” in Proc. ACM SIGCOMM ’04 Workshop on Practice and Theory of Incentives in Networked Systems (PINS ’04), Aug. 2004. [17] E. Kalai, “Proportional solutions to bargaining situations: Interpersonal utility comparisons,” Econometrica, vol. 45, no. 7, pp. 1623–1630, Oct. 1977. [18] D. Qiu and R. Srikant, “Modeling and performance analysis of BitTorrent-like peer-to-peer networks,” in ACM SIGCOMM ’04, Aug. 2004, pp. 367–378. [19] J. Li, P. A. Chou, and C. Zhang, Mutualcast: An ef?cient mechanism for content distribution in a peer-to-peer (P2P) network Microsoft, Tech. Rep. MSR-TR-2004-100, Sep. 2004. [20] Z. Xu and L. Bhuyan, “Effective load balancing in P2P systems,” in Proc. 6th IEEE Int. Symp. on Cluster Computing and the Grid (CCGRID ’06), 2006, pp. 81–88. [21] M. van der Schaar, D. S. Turaga, and R. Sood, “Stochastic optimization for content sharing in P2P systems,” IEEE Trans. Multimedia, vol. 10, no. 1, pp. 132–144, Jan. 2008. [22] , M. van der Schaar and P. A. Chou, Eds., Multimedia over IP and Wireless Networks. : Academic Press, 2007. [23] M. Gupta, P. Judge, and M. Ammar, “A reputation system for peer-topeer networks,” in Proc. the 13th Int. Workshop on Netw. and Operating Systems Support for Digital Audio andVvideo (NOSSDAV ’03), 2003, pp. 144–152. [24] M. J. Osborne and A. Rubinstein, A Course in Game Theory. Cambridge, MA : The MIT Press, 1994. [25] R. Mahajan, M. Castro, and A. Rowstron, “Controlling the cost of reliability in peer-to-peer overlays,” in Proc. 2nd Int. Workshop on Peer-to-Peer Systems (IPTPS ’03), 2003. [26] E. Adar and B. A. Huberman, Free riding on Gnutella Xerox PARC, Aug. 2000, Tech. Rep.. [27] R. Axelrod, The Evolution of Cooperation. New York: Harper Collins, 1984. [28] P. Golle, K. Leyton-Brown, I. Mironov, and M. Lillibridge, “Incentives for sharing in peer-to-peer networks,” in Proc. Second Int. Workshop on Electronic Commerce, Lecture Notes in Computer Science, 2001. [29] G. Hauske, T. Stockhammer, and R. Hofmaier, “Subjective image quality of low-rate and low-resolution video sequences,” in Proc. Int. Workshop on Mobile Multimedia Commun., Oct. 2003. [30] X. X. Lu, R. O. Morando, and M. E. Zarki, “Understanding video quality and its use in encoding control,” in Proc. 12th Int. Packet Video Workshop 2002, Apr. 2002. [31] Z. L. Zhang, Y. W. Wang, D. H. C. Du, and D. L. Su, “Video staging: a proxy-server-based approach to end-to-end video delivery over widearea networks,” IEEE/ACM Trans. Netw., vol. 8, pp. 429–442, 2000. [32] J. K. Chen and J. L. C. Wu, “Adaptive chaining scheme for distributed VOD applications,” IEEE Trans. Broadcast., vol. 45, no. 2, pp. 215–224, June 1999. Hyunggon Park received the B.S. degree (magna cum laude) in electronics and electrical engineering from the Pohang University of Science and Technology (POSTECH), Korea, in 2004, and the M.S. degree in electrical engineering from the University of California, Los Angeles (UCLA), in 2006. Currently, he is pursuing the Ph.D. degree in the Multimedia Communications and Systems Laboratory at UCLA. His research interests are ef?cient and adaptive multimedia transmission and resource management over wired/wireless/P2P networks using game theoretic approaches. Mr. Park was a recipient of the Graduate Study Abroad Scholarship from the Korea Science and Engineering Foundation during 2004–2006.

Mihaela van der Schaar is currently an Associate Professor in the Electrical Engineering Department at UCLA. She received in 2004 the NSF Career Award, in 2005 the Best Paper Award from IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, in 2006 the Okawa Foundation Award, in 2005 and 2007 the IBM Faculty Award, and in 2006 the Most Cited Paper Award from EURASIP: Image Communications journal. She holds 30 granted US patents and three ISO awards. Her research interests are in multimedia communications, networking, architectures, systems, compression and processing.


赞助商链接
相关文章:
2016四六级模拟试卷十套(含答案)
The National Coalition for the Homeless estimates that there are _____ ...40. According to Fries and Crapo sound health choices should be based on...
王长喜老师 专八听力周计划 第四周(预测试题)星期三
[D] It may become the first party to govern without a coalition since 1990. 9. Which of the following party mentioned get the least vote based on ...
3 - Leading & Leadership
Leadership Power Positional powers (all leaders have these – based on the ... frequent reminders to influence follower Coalition: leader seeks the help of...
美国空军无人机指导概述 2013-2038
decision makers but also directly to joint and coalition forces in the ...… 4.4.4.1 Ground-Based Sense and Avoid Mid-term NAS access can include...
2014年12月大学英语六级考试真题试题三 - 备考族
I base this conclusion not on any individual study, but on large-scale ...Commissioned by the National Coalition of Girls’ Schools, the raw findings ...
冲击波系列英语专业四级听力2(新闻)
新闻听力模拟练习 100 题 News Item 1 Questions 1 to 2 are based on the...A. Some gunmen tried to flee from the coalition position. B. Some gunmen...
Part II Reading Comprehension
Passage One Questions 21 to 25 are based on the following passage. ...The National Coalition for the Homeless estimates that there are _____ ...
六级听力
Student Action Coalition这个组织的 情况,故答案为[D]。 20. What is the ...England was the first country to Questions 30 to 32 are based on the ...
Features of Academic Writing
3.ThefirstNationalGovernmentwasn'tintendedtobeacoalitiongovernmentinthenormalsenseoftheter m. 4.Thesearen'tatalloriginalorexoticbutarebasedontheordinarythingsthat...
HND商务行为技巧 xn
developing the relationship between parties Coalition: involving others in ...the original based on performance index is designed to generate participation....
更多相关标签: