Incentives - Peer-to-Peer Computing: Applications, Architecture, Protocols, and Challenges - page 100

natural selection. The key idea is depicted in Figure 5.14. The left part of
the figure illustrates a situation where multiple peers are sharing the capacity
of a single server. As a result, each peer can only enjoy a small downloading
data rate. However, when peers are organized as a multicast tree, based on
strategic natural selection (detailed below), each peer can enjoy a much larger
downloading rate.
The natural selection process can be illustrated in Figure 5.15. Here, ini-
tially the root is the only source in the system and thus, peer A selects the
root as the source, enjoying a downloading rate of 500 kbps. Now, when a new
peer B joins the system, peer A has basically two choices: (1) serve peer B;
or (2) do not serve peer B. To implement the second choice which seems to
be a more favorable one, peer A can declare to the BSE that its uploading
rate is 0 or a value smaller than 250Kbps (which is half of the capacity of the
root). However, in doing so, peer B has no choice but naturally selects the root
to be its streaming source. In that case, peers A and B will share the root's
uploading capacity and thus, each obtains only 250Kbps data rate. On the
other hand, in anticipation of such an actually unfavorable outcome, peer A
should instead strategically declare its uploading bandwidth to be 300Kbps,
which is slightly higher than the capacity declared by the root. Consequently,
peer A can continue to enjoy a high downloading rate from the root, at the
expense of its uploading of data to peer B at a rate of 300Kbps.
Ye and Makedon [Ye and Makedon, 2004] proposed a useful detection
and penalty scheme to tackle the existence of selfish peers in a multicast
streaming session. They observed that a selfish peer may lie to other peers in
that it claims its uploading bandwidth is large so that it can enjoy a higher
probability of being admitted into a streaming session or enjoy a higher quality
of media data. The key of the detection mechanism is that a downstream peer
in a multicast tree returns a “streaming certificate” back to its parent peer.
For example, as shown in Figure 5.16, peers P 4 , P 5 , and P 6 , send streaming
certificates SCert(P i ,P 3 ) to the parent peer P 3 (i = 4, 5, 6). The certificates
are sent periodically and are time-stamped with authentication. Thus, a higher
level peer, e.g., P 1 , can periodically check whether its children peers (i.e., P 2
and P 3 ) are selfish by asking for certificates they have received (if any) from
their own children peers. If a peer cannot produce such a certificate, the higher
level peer can then remove such a potentially selfish peer from the tree. The
removal process is manifested as a termination of media data transmission.
Jun et al. [Jun et al., 2005] also explored a similar idea in their proposed
Trust-Aware Multicast (TAM) protocol. Targeted for detecting and deterring
uncooperative peers which can modify, fabricate, replay, block, and delay data,
the TAM protocol is based on a message structure that contains four fields:
sequence number, timeout period, data payload, and cryptographic signature.
The sequence number is used for detecting duplicated or missing data. The
timeout period is used for detecting delayed data. Thus, a selfish (or even
malicious) peer can be identified by its children peers in the multicast tree.
Different from the approach suggested by Ye and Makedon [Ye and Makedon,