[bittorrent] 'Rarest first' question.

Bruno Hertz brrhtz at yahoo.de
Sat Jul 1 11:04:19 EDT 2006

Elliott Mitchell <ehem at m5p.com> writes:

>> Look at the wording of http://www.bittorrent.org/protocol.html:
>> "Downloaders generally download pieces in random order, which does a
>> reasonably good job of keeping them from having a strict subset or
>> superset of the pieces of any of their peers."
>> This wording is not only unambigous, it also gives a clear idea where
>> things are targeted at, for obvious reasons.
>> Regarding the 'must' (or 'shall', the word which I'd expect in such
>> situations), I guess we all know by now that we have no formal and
>> complete BT specification and are required to use our own brains.
> Yes it states the goal (which placing more emphasis on rarest first
> accomplishes better), but I think that word "generally" was a good choice
> here. Other strategies can be used and still conform to the protocol as
> written. Given that the over-the-wire protocol and torrent files are the
> only way clients interact, those are really the only thing that matter
> for protocol conformance. Other choice algorithms are valid.

By that reasoning the choke algorithm might also be chosen ad
libitum. Is that what you are saying? And what do you mean by 'choice'

>> Regarding the original goal, one might find that quite some scientific
>> discoveries in history were made by accident or while looking for
>> something else. Although our subject may not have that significance, I
>> do still appreciate the benefit.
> Yes, another example: I think the piece size was chosen to reduce torrent
> size, but it accidentally reduces peer to peer traffic quite
> significantly and increase locality of reference (because you typically
> as for all of the piece from the peer). I'd say the second two are
> actually much more important.

Torrent size, and I believe protocol overhead either. Just imagine the
reception of every byte being broadcasted throughout the peer set with
big hooray, i.e. 'have' messages. On the other hand is piece size
(inversely) correlated to diversity, so it's a typical tradeoff

Regarding locality, I seem to understand that clients these days
request subpieces resp. blocks from different peers anyway.

>> Consider the slightly degenerate case where an initial six seeds are
>> joined by 34 peers which strictly download sequentially. The share
>> factor amongst those peers would be minimal (cf. sub/supersets above)
>> and performance as well as cost distribution clearly and significantly
>> hurt.
> Which strictly download sequentially /from the start of the torrent/.
> If sequential peers download starting at random locations, availability
> is quite good.

You know lotto? Here, it means betting on 7 numbers which are randomly
picked out of 49. Now compare this to a scheme where only one is
picked at random and the rest of them sequentially, and then please
explain what 'quite good' means. I also recommend revisiting the
definition of statistical entropy.

>> Since this effect would carry through to all scenarios, albeit maybe
>> not that noticable, I'd still insist that you can't just proceed at
>> will given a specific piece availability, at least not in the
>> wild. Special purpose environments are a different thing.
> True, but certainly the choice method in the spec isn't set in stone.

Maybe. But I leave it to the inventor of BT what is to be called
BT. Up to now, I'm just aware of two piece picking schemes which
qualify, random and rarest first. Please correct me in case I might
be missing something.

>> That is, you basically download sequentially with some randomized read
>> ahead. Sure that's a feasible approach. It's one step more than the
>> classic client/server model, i.e. strict sequential downloading
>> resp. streaming, plus the added capability of clients sharing amongst
>> each other.
> Perhaps. If that randomized read-head is far enough ahead though the
> probability becomes identical to pure random/rarest first; so the
> degradation mode is good. The trick is to keep the read ahead far enough
> ahead such that you don't overrun the border, and you've still got pieces
> to trade.

I guess a typical approach might be to ensure a constant or variable
size streaming buffer is filled at any time for playback, and pick
other pieces at random, or whatever distribution function might

>> Anybody is of course free to develop solutions better suited for
>> whatever purpose, and try for an own success story. The issue though
>> is that calling them BT might be considerd an attempt on what BT
>> itself tries to prevent in a slightly different context, i.e. free
>> riding. See also http://groups.yahoo.com/group/BitTorrent/message/6726
> I'll still emphasize that such a peer conforms to the invarient sections
> of the BT specification. The over the wire code and handling of torrent
> files. Therefore merely choosing an alternate choice method is valid.

I propose recognizing that we have different opinions and settling
with that.

Kind regards, Bruno.


Gesendet von Yahoo! Mail - Jetzt mit 1GB Speicher kostenlos - Hier anmelden: http://mail.yahoo.de

More information about the BitTorrent mailing list