[bittorrent] 'Rarest first' question.

Bruno Hertz brrhtz at yahoo.de
Tue Jun 27 20:04:53 EDT 2006

Arnaud Legout <Arnaud.Legout at sophia.inria.fr> writes:

> Hi,
> Bruno Hertz wrote:
>> Consider a small swarm of let's say 10 peers with one seed, where the
>> seed is part of all the peers' (initial) peer set. I'm one of the
>> leechers in this swarm.
>> Furthermore, let the swarm be in a state where the torrent isn't yet
>> fully replicated into the swarm.
>> Now, apparently the single seed owns all the rarest piecest,
>> i.e. those not yet replicated, and all the other peers, including me,
>> are aware of that thanks to bitfields and have messages.
>> What follows is that, if I were to strictly observe 'rarest first',
>> the only peer I'd ever be interested in at this stage is the single
>> seed, and I'd just be waiting to be unchoked by it.
>> Especially, no replication at all would happen amongst the leechers at
>> this stage
> I am not sure what you are talking about.
> There are two issues:
> -first, the piece selection strategy is preempted by the peer selection 
> strategy. You first consider the
> peers that unchoke you and you are interested in, then you select the 
> rarest piece (according to your peer set view)
> that is available on those peers. Thus you do not have to download the 
> real rarest piece from the seed, which is as you noted a blocking
> situation. As, the seed can only unchoke four peers at the same time (I 
> skip here details, it is
> a bit more complicated in reality), only four peers will get pieces from 
> the seed at the same time.

Thanks a bunch, that was it. Since there's no formal description of
rarest first available, I wasn't sure about the priorities
resp. preemption, as you call it.

> -second, as the replication of the pieces is exponential (this is the 
> property of a P2P architecture),
> but as the seed can only serve new pieces at its upload rate,
> you have what we call a transient state (see 
> http://hal.inria.fr/inria-00001111/en). During this state, there are 
> rare pieces, but
> there is no piece selection strategy or piece coding strategy that can 
> do significantly better than rarest first.

I browsed through your paper, thanks very much for the link. Two
questions though:

(i)  since you measured torrents in the wild, how could you actually be
     sure the other clients employed rarest first? Not only did the
     original BT spec recommend random piece selection, but it may also
     be that developers twist the algorithms to serve other goals.

     E.g. the two first projects I contacted these recent days looking
     for a BT library I could use are considering implementing resp.
     have already implemented hybrid algorithms, with partial rarest
     first and partial sequential piece selection. One project to
     allow to watch movies while downloading, the other to provide for
     better disk caching.

     From this I got the impression clients might do what they want
     anyway, so did you actually limit your measurements to peers you
     know for sure use rarest first?

(ii) the graphic plots in the pdf are pretty hard to read. You haven't
     some larger copies lying around on some web server, haven't you? I'd
     really be interested in seeing some more detail.

Finally, while browsing through this list's archives, I saw you
mentioning you might make your instrumented client publicly
available. There isn't any news in that regard, is there?

Kind regards, Bruno.

Telefonate ohne weitere Kosten vom PC zum PC: http://messenger.yahoo.de

More information about the BitTorrent mailing list