|
#REDIRECT [[Peer-to-peer]]
(editing)
[[Peer_to_peer|Peer-to-Peer]] (P2P) computer network has been an active research area in the past decade. Different forms of file distribution systems have been developed based on P2P. A pure P2P [[File_sharing|file-sharing]] network does not have a centralized server; instead peers are responsible for uploading and downloading the data among themselves. This is the major difference compared with the traditional file-sharing system, where communication is usually directed to and from a server. As a result, given a stable P2P network, files can be shared effectively and network scalability can increase with lower cost.
With the power of P2P network, users become interested in sharing large volume of data (especially multimedia contents) across the Internet. Therefore, [[Video_on_demand|video on demand]] and live [[Streaming_media|media streaming]] systems are created. In order to achieve the highest quality of service, the most important principle is [[cooperation]] among different peers. This article will focus on P2P streaming systems and discuss several incentive mechanisms that reward peers for cooperation and punish [[Free_rider_problem|free riders]].
==P2P Streaming Systems==
In P2P multimedia streaming, the video/audio stream is split into several smaller streams. Each stream is stamped with a numerical sequence number so that it can be placed in the correct sequence for playback. In order to guarantee each stream is delivered, a [[Forward_error_correction|forward error correction]] code will be used. Different peers join the streaming session and exchange availability information. A peer retrieves data by requesting data from other peers, while supplying available data to other peers. These operations are monitored by an application-level streaming system.
===Tree-based Multicast System===
[[Image:Tree-based.jpg|thumb|Figure 1a: A tree-based multicast system. The interior nodes carry all the forwarding loads. On the other hand, no forwarding is required by leaf nodes]]
A traditional design of P2P streaming system is the tree-based [[multicast]] system that is based on a single tree (Figure 1a). In this system, a peer is either an interior node or a leaf node. If a peer is an interior node, it will carry all the loads to forward the data to other nodes. On the other hand, if a peer is a leaf node, no forwarding is required. There are two problems with this design. First, the system is not fair. When the number of fanouts of the tree increases, the number of leaf nodes increases much faster than the number of interior nodes. Since all the loads are within the interior nodes, the system becomes very unbalanced. Second, peers who act as interior nodes may not be able to handle high-bandwidth application (e.g. high quality video) due to network capacity limitation.
===Split Stream Multicast System===
[[Image:Split_stream.jpg|thumb|Figure 1b: A split stream multicast system. In this example, the source is split into two stripes. Each peer is the interior node in one tree and a leaf node in the other (diagram reproduced from [1])]]
In order to overcome the unbalanced loads on peers, an improved system was proposed in [1], using a split stream approach (Figure 1b). Split stream system works by splitting the stream into multiple stripes which uses separate multicast trees to distribute each stripe to the peers. The goal is to ensure that vast majority of peers are interior nodes in only one tree, and they will be leaf nodes in all other trees. As a result, the system distributes forwarding workloads among all peers and solves the first problem in the traditional streaming system. This method becomes useful when a large number of cooperative peers are interested in a streaming session to share the content [2].
With this approach, peers choose to join a subset of the stripes to control their inbound bandwidths. On the other hand, peers opt to limit the number of children nodes they adopt to control their outbound bandwidths. Thus, the split stream system accommodates peers with different bandwidths and solves the second problem in the traditional streaming system. Other advantages of striping across multiple trees include improved robustness to node failure since a node failure only causes the loss of a single stripe on average, and the system also guarantees quick recovery from node failure.
The major drawback of this design is no guarantee of finding an optimal forest, even if the network has sufficient capacity.
==Incentive Mechanisms==
===Social Optimum vs. Nash Equilibrium===
So far I have assumed peers to be honest that they will cooperate with others. However, this is not always true and peers misbehave in streaming systems. According to [[game theory]], strategic behavior leads to sub-optimal outcome and designers of P2P systems should take this into account when designing the architecture. The [[Prisoner%27s_Dilemma|prisoner’s dilemma]] model can be used to explain the above situation. In Table 1 below, the numbers represent the resources each peer can get. A higher value means more resources and vice versa. As we assumed that peers are selfish, they both choose not to cooperate under this model, and this leads to a sub-optimal [[Nash equilibrium]].
{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; width: 500px"
|+Table 1: Payoff matrix in the prisoner’s dilemma model
| rowspan=2 colspan=2 |
| colspan=2 align="center" | Peer 1
|-
| align="center" | Cooperate
| align="center" | Not Cooperate
|-
| rowspan=2 align="center" | Peer 2
| align="center" | Cooperate
| align="center" | 5,5
| align="center" | 1,8
|-
| align="center" | Not Cooperate
| align="center" | 8,1
| align="center" | 3,3
|}
Although the above model is simplified to represent only two peers in the network, this can extend to an N x N [[Matrix_%28mathematics%29|matrix]], where N is sufficiently large to represent all peers. Notice that social optimum occurs when peer 1 and peer 2 both choose to cooperate. Therefore, it is of social benefits to design incentive mechanisms that encourage cooperation in the streaming system.
===Reputation-based Mechanism===
Two [[reputation]]-based mechanisms are proposed in [3]. The first one is Debit-Credit Reputation Mechanism and the second one is Credit Only Reputation Mechanism. In the first mechanism, a peer’s reputation increases by sharing contents with others, while its reputation decreases upon downloading contents. In the latter mechanism, peer is not punished for downloading.
Imagine that a peer joins a split stream multicast system as a child of a tree, and acts cooperatively. However, its parent node refuses to share resources, and acts as a free rider. The free rider claims that it is already serving the maximum number of peers that it can handle. The validity of this claim can be confirmed after several multicast tree reconstructions, when the free rider has demonstrated a history of service refusal strategy against its child peer [4]. The system can then send a reputation report to the child peer based on one of the above mechanisms. Later on if a child peer becomes a parent node, it can refer to the reputation report and refuse to share resources to the free rider, which was the parent before but now the child node. Notice that the parent node in this case will not be assigned a bad reputation by not serving the child node, because the system recognizes the child node as a free rider.
'''Long-term and Short-term History''': In the reputation-based mechanism, it is also useful to consider the reputation report in terms of long-term history and short-term history [5]. If the reputation report is based on long-term history, peers with high reputations will have incentives to turn into defectors before leaving the system, because the long-term history does not discriminate between old and recent actions. In order to workaround this problem, a short-term reputation report should be used. In this scheme, the system examines recent instead of past actions. Therefore, peers who defect are quickly detected by the system. I think that the problem in short-term history is the unfairness imposed to peers who always cooperate. This is because their long-term reputations will be ignored after a certain period of time, and they have to build up their reputations again from zero.
===Payment-based Mechanism===
First I should point out that a flat rate fee does not work in P2P system. This is because in this payment mechanism, everyone is charged the same amount of utility (money or virtual currency), and free riders continue to exist and do not have incentives to share resources.
In [6], the authors suggest a [[Micropayment|micro-payment]] mechanism, such that a user needs to pay for each block that is downloaded. For example, each block may contain 10 different streams. At the end of a payment period, the number of streams the user downloaded is rounded up to the next block of usage. So in this case, if the user downloads 33 streams, he will pay for the price of four blocks. For uploads, the user gets rewards for the exact number of streams uploaded for sharing. At the end of each period, user is charged an amount of ''C = k(d – u)'' by the system, where ''C'' is the overall charge, ''k'' is a scaling coefficient, ''d'' is the number of blocks downloaded and ''u'' is the number of streams uploaded. The authors also prove that this mechanism leads to unique and strict equilibrium, and the goal of the system is to achieve maximum cooperation among peers.
There are couple interesting facts with this payment mechanism. First, it is clear to see that a user can get credited by sharing more resources than downloading. This reward can be used for future downloads. Second, with unconsumed streams in a block, users may take advantage of zero [[marginal cost]] to download from their friends (even if they have no interest in the resources), so that their friends receive the credits for uploading the resources. The authors suggest two methods to solve this potential problem. The first solution is to hide the identities of all users, so that they cannot collude. In the second method, instead of hiding user identities, the system randomly assigns users into different groups, to reduce the chance of [[collusion]].
===Score-based Mechanism===
Another incentive mechanism is the score-based mechanism suggested by [3]. The scoring function can consider only the contribution by a peer or it can consider both the consumption and contribution by a peer. A peer is awarded scores for uploading and penalized for downloading. When a peer with a score of ''S'' issues a request for a stream, it can only obtain the stream from peers with scores lower than ''S''. It is also a good practice to map the score into a percentile ranking, based on scores from all peers. This helps in predicting the expected quality to be received by the peer.
The score-based mechanism provides service differentiation. For the peers who always cooperate, they are awarded higher scores and get the chance to choose large number of peers to download from and obtain high quality of streaming. However, for the free riders, they are given limited options to select peers and thus receive low quality of content sharing. [3] also points out that when the streaming network is congested, even when all peers cooperate, the quality of streaming still degrades.
===Other Issues Relating to Incentive Mechanisms===
Besides the above incentive mechanisms, there are other related issues in P2P file-sharing and streaming systems that are worth discussing in order to build a better cooperative network.
'''False Report''': According to [5], there are four types of false reports: providing service, not providing service, receiving service, and not receiving service. The second and third reports do no good to the free riders. On the other hand, if the free rider lied about service provision when it did not, its reputation and score may be boosted. The consequence is the free rider receives better quality of service, but the overall system performance is degraded. And if a peer lies about not received service which it did receive, it may hurt the reputation and score of the peers who have provided the service. The incentive mechanisms previously described are some effective ways of discouraging and identifying false reports.
'''Zero-cost Identity''': Most P2P systems allow peers to continuously switch identities (whitewash). It encourages free riders to obtain new identities and avoid punishment for not cooperating with others. In order to prevent whitewashing behaviors, most P2P systems treat newcomers and free riders identically (with zero credit/reputation). This may seem unfair for the newcomers at the beginning, but eventually the system will be able to distinguish between newcomers (who cooperate) and free riders by using the incentive mechanisms described above.
==Conclusion==
In this article, I have examined the importance of peer selection algorithms and how they can improve overall network throughput in a P2P network environment. I have also described the split stream multicast streaming system and discussed its advantages over the traditional tree-based system. Next, a game theoretic approach is used to address the problem of cooperation in P2P network. I have shown different incentive mechanisms based on reputation, payment, and score that can reduce the number of free riders in a P2P network. Other important issues such as false report and zero-cost identity are also discussed.
With the active researches and developments in P2P environments, the next generation P2P systems will likely be more efficient by overcoming the problems of free riding and whitewashing behavior.
| 