Status: operational code
Give-To-Get is the core algorithm for Video-on-Demand and streaming.
Measured to work efficiently in a trial with 6000+ participants. (experimental results)
Centralised solutions for Video-on-Demand (VoD) services, which stream pre-recorded
video content to multiple clients who start watching at the moments of their own choosing,
are not scalable because of the high bandwidth requirements of the central video servers.
Peer-to-peer (P2P) techniques which let the clients distribute the video content
among themselves, can be used to alleviate this problem.
However, such techniques may introduce the
problem of free-riding, with some peers in the P2P network not forwarding the video
content to others if there is no incentive to do so.
When the P2P network contains too many free-riders, an increasing number of the
well-behaving peers may not achieve high enough download speeds to maintain an
In this paper we propose Give-to-Get, a P2P VoD algorithm which discourages free-riding
by letting peers favour uploading to other
peers who have proven to be good uploaders.
As a consequence, free-riders are only tolerated as long as there is spare capacity
in the system.
Our simulations show that even if 20% of the peers are free-riders, Give-to-Get continues to provide good performance to the well-behaving peers. In particular, they show that Give-to-Get performs very well for short videos, which dominate the current VoD traffic on the Internet.
While this paper describes the algorithm in detail, I'll give a sketch of the basic idea.
Starting with Bittorrent
We started with the Bittorrent protocol and modified it to suit our needs and create Give-to-Get. This method makes implementing Give-to-Get easy as one can start with a Bittorrent client. Letting Give-to-Get and BitTorrent peers interact is quite easy as they share a common base.
As in Bittorrent, Give-to-Get divides the video stream into fixed-sized pieces. A peer keeps its neighbours (the other peers it is connected to) informed about which pieces it has, and which neighbours are allowed to request pieces.
Piece Picking policy
The order in which the pieces are requested is important. In Bittorrent, pieces are requested rarest-first, which allows each downloaded piece to be uploaded to many other neighbours. Such a scheme is ideal in a download setting in which a peer only cares about completing the whole download, not in which order. In a streaming setting, a peer actually needs its pieces from start to end, in order. If pieces are requested in order by every peer, many peers will request the same pieces at the same time and will not be able to forward them to each other.
So, we use a hybrid between rarest-first and in order. A peer divides the pieces after its current playback position into three sets: high-priority (10 seconds), middle priority (40 seconds), and low priority (the rest). Pieces are requested based on their priority. Within the high-priority set, pieces are requested in-order. In the middle and low priority sets, rarest-first is used. As a result, if a peer has enough bandwidth, it will spend most of its time downloading rarest-first in the middle and low priority sets, but a peer will switch to in-order downloading if it is running out of bandwidth.
In Bittorrent,a system not unlike tit-for-tat is used to promote the uploading of pieces: a peer will allow requests from those neighbours that send data in return. This works in a download setting, since all peers are interested in receiving all pieces at any time. However, in a streaming setting, data will mostly flow in one direction between two peers, One peer is always ahead of the other and is thus interested in different parts of the stream. So, a different incentive is needed for uploading.
In Give-to-Get, we promote uploading by having peers provide data to those neighbours that upload the most data to others. This information is gathered by querying the peers that receive data from the neighbours. As the best uploaders will receive the most data from others, peers have an incentive to upload.
To avoid peers colluding by claiming that their friends are good uploaders, it is recommendable to assign random neighbours to peers.
I measured the performance of Give-to-Get using a Discrete Event Simulator, written in C. The simulator and Give-to-Get implementation can be downloaded [source:abc/branches/jandavid/g2gsim here]. Also, Give-to-Get is in the process of being implemented in Tribler, most of which will end up [source:abc/branches/mainbranch/Tribler/Core/Video/ here].
2nd generation Give-to-Get
Merge the positive effects of public trackers
and private trackers with sharing ratio enforcements;
without the drawbacks.
Link the BarterCast rating of a peer in the
algorithm to divide the upload capacity. Design principles:
Give priority to balanced peers, but do not punish
freeriders with bandwidth starvation; let
them download four times slower.
Take into account a mix of previous upload behavior,
current swarm uploading to others (hearsay feedback), and
direct upload to yourself.
A significant drawback of BarterCast is that is only provides a rough
estimate of a sharing ratio.
Each peer is assigned a ratio class, according to the
table below. Peers that are poor sharers or freeride are
slowed down. Note that new peers have to earn trust and
are also slowed down. Attacks such as: Bitthief, Bittyrant, or
ratio faking are thus resolved.
|Ratio Class||Ratio||Age of Peer||Allocated Upload
|Nice ||>0.8, 5MB+ ||1+ days||maximum 100%
|Poor ||unknown, 5KB+ ||new ||maximum 100%, pre-empted by Nice peers to min. 10%
|Freerider||unknown ||new ||maximum 50%, pre-empted by Nice and Poor peers to min. 5%
Note that if there are no Nice or Poor peers in a swarm
only 50% of the upload capacity of a peer is used. The above
ratio classes ensure that in the steady state there is an
incentive to have a good ratio and that your identity is known
to others (Age>1 day). Most peers are thus in the Nice class
and are allocated bandwidth according to their behavior in the
current swarm. The hearsay algorithm is used to allocate
bandwidth between peers of the same class.
Standard Bittorrent Tit-for-Tat clients have an unknown long-term sharing ratio
and include no measures to prevent identity spoofing attacks.
Sharing ratio is even easily faked
due to limitations of the original protocol.
The Give-To-Get algorithm states therefore that Tit-for-Tat peers cannot enter the Nice class.
They are positioned in the Poor class when they have
uploaded at least 5KByte or more to you and marked as a potential
Freerider in all other cases.
The requirements of playing fair to existing Tit-for-Tat peers
is implicitly build in into the Give-to-Get algorithm.
Within a mixed swarm of mostly Tit-for-Tat peers each uptimistic
unchoke triggers an upgrade of the traffic class and allocation
of bandwidth. Within a mixed swarm of just a few Tit-for-Tat peers
the Give-to-Get peers still give back any consumed bandwidth.