[bittorrent] what is bitTorrent piece download mechanism?

Arnaud Legout arnaud.legout at sophia.inria.fr
Fri Mar 7 09:12:36 EST 2008


Alan McGovern wrote:
>     2. Peer selects "which piece to download?" based on rarest first
>     policy.
> Yes.

and random first for the first few pieces (usually around 4)

>     (except for first 4 packets.)
> That isn't in the specification, but some clients could download the 
> first 4 pieces first to allow for previewing video/mp3

Alan, I don't to which spec you are referring to (probably the 
wiki.theory.org spec),
as there is no up to date official BT spec.

The wiki.theory.org spec is good for the protocol description, but weak 
when it comes to the algorithms description
(peer and piece selection algorithms). If you refer to the Bram Cohen's 
paper [1] you can find the notion
of random first.
Also you can refer to [3]  for a more detailed description of the peer 
and piece selection algorithms.

The initial goal of random first was not to do previewing, but to 
increase the speed at which a peer
will get its first piece so that it can start reciprocating to others.
We can surely do much better to speed up a peer on its first piece, but 
random first is a good
tradeoff between simplicity and efficiency.
You can refer to the bram cohen's paper [1].

> files.
>     I have following questions:
>     1. *(A)* Whether this entire piece is requested for download only
>     from one remote peer  ;
>     or *(B)* does it send multiple requests to different  remote peers
>     (in case if that piece is available with more than one)?
>     --> (I think it should request multiple remote peers to have
>     better performance but not sure about what actually happens?)
> That's implementation dependent. You can even get a mix of both of 
> these behaviours. Some clients might do (B) but switch to (A) if the 
> piece ends up being corrupt. This way they can find which peer is 
> sending the bad data.

The regular behavior is to first try to download blocks of a same piece 
from a same peer.
The rational is to have an efficient block pipelining in order to increase
the speed at which you download blocks. This strategy is called strict 
Requesting blocks for a same piece on different peers may have many 
negative side effects.
For instance, when a peer choke you, you increase the probability that 
you will not be able
to find the remaining blocks of the partially downloaded pieces on the 
peers that currently unchoke you.
So you will end up with partially downloaded pieces that you cannot 
reciprocate (so a poor usage
of your upload capacity for the system without any clear benefit for you).

your comment on B ("have better performance") should be managed at the 
piece level.
You perform parallel download at the piece level and strict priority at 
the block level.
If you want more information on dynamic parallel download (that is used 
in BT)
you can refer to the paper that introduced it [4] in a somewhat 
different context.

>     3. Suppose  peer requests remote peer for a particular block; and
>     then remote peer chokes that request.
>     Then does this peer request this block to some other peer? Is
>     there any time-out limit for that?
> Implementation dependent again. Some clients may drop all partial data 
> when a  peer chokes. Some may retain that data and continue 
> downloading off another peer. Clients who do (A) may drop the data, 
> whereas clients who do (B) would continue downloading as normal.

by "data" do you mean all the blocks already downloaded, which IMHO does 
not make sense (unless you
are suspicious this particular peer sends corrupted data), or the data 
of the currently partially downloaded block.

We recently got a paper at IPTPS that discuss the impact of piece size on
BT efficiency. This is still a work under progress, but the results we 
already have may be relevant to you.


[1]  "Incentives Build Robustness in BitTorrent". Bram Cohen

[2] P. Marciniak, N. Liogkas, A. Legout, E. Kohler. Small Is Not Always 
In Proceedings of IPTPS'2008, February 25--26, 2008, Tampa Bay, FL, USA.

[3] A. Legout, G. Urvoy-Keller, and P. Michiardi.  Rarest First and 
Choke Algorithms Are Enough. 
In Proceedings of ACM SIGCOMM/USENIX IMC'2006, October 25--27, 2006, Rio 
de Janeiro, Brazil.

[4] P. Rodriguez, W. Ernst Biersack., "Dynamic Parallel-Access to 
Replicated Content in the Internet". In IEEE/Transactions on Networking, 
August 2002 (Also in IEEE/Infocom 2000) 

More information about the BitTorrent mailing list