[bittorrent] 'Rarest first' question.

Bruno Hertz brrhtz at yahoo.de
Thu Jun 29 08:07:22 EDT 2006


Elliott Mitchell <ehem at m5p.com> writes:

>>From: Bruno Hertz <brrhtz at yahoo.de>
>> Well, I'd say too BT suggests rarest first, and I also see
>> why. Problem is there is no written spec apart from 1.0, which
>> suggests random selection. If you know of any other formal, written
>> specification, apart from the mainline source code, please let me
>> know.
>
> Suggests rarest first for pieces below a threshold of commonness, then
> random above that threshold.

Sure. I took knowledge of the algo's details, like the startup and
endgame phase, for granted.

>> His motivation btw is better caching, to reduce disk seeks. That's why
>> he basically wants to serialize the pieces to some extent, simply by
>> downloading them in that order :)
>
> Is the motivation wrong though? Certainly with high-bandwidth, locality
> of reference is a very serious issue. As you mention though, unless all
> your peers are synchronized (and rarest first will tend to break this)
> you'll have a problem with reads. This looks like an accidental feature
> of having 256KB pieces and 32KB request blocks, mainly in addition to
> keeping traffic from HAVEs down it also strongly encourages some locality
> of reference.

I'm not questioning the motivation but the solution. The attempt to
improve IO throughput in fact is very commendable. Question is how to
achieve this without hurting BT.

As it turns out, he has another solution in store which is writing
packets as they're downloaded to disk and reshuffle them later. While
not helping on the read side either, this approach does not bend the
piece selection, so it sure is preferable.

>> I've been looking into this for about two weeks now and already got
>> the impression developers implement anything but the mainline
>> algorithms (ok, that's an exaggeration, but the tendency is definitely
>> there).
>
> Make sure you realize that some sections of the specification are
> required, while some are merely suggested. The over the wire protocol and
> .torrent file arrangement are strictly defined. The choice of piece
> selection order though is merely suggested.

Are you to say clients may download in any order they choose?
Interesting interpretation of BT ...

>> You don't need to convince me. I have a math background, and to me it
>> is intuitively obvious that rarest first very likely performs better
>> than random selection and surely better than sequential. Finding the
>> proper arguments though in discussions is not that easy, since there's
>> all kinds of other random factors involved (initial peer set
>> etc.).
>
> Try this on for size. Random selection tends to effectively provide for
> maintaining diversity. In the general case I'd suggest use of weighted
> random piece selection will perform best.

Random selection sure is the best approach if you have no live
knowledge about how the other peers perform. Bitfields and 'have'
messages provide such knowledge though, so it makes sense to utilize
it.

> Rarest first though is crucial to ensure survival. So the common
> weight would be rare pieces to get a higher selection likelyhood
> (single-copies pretty well being guarenteed selection).

That's a common misconception about rarest first, i.e. that it is
primarily meant to increase piece availability and thus the chance of
torrent survival. Better entropy is at least as much of a goal though.

> For stream downloads, you merely add another weight; pieces nearer to the
> current playback index are prefered over more distant pieces. A
> psuedo-random number generator is a pretty good arbiter between these
> two motivations. Distant pieces are valuable because you will eventually
> play them, and peers ahead of you will be interested in downloading those
> and in turn uploading.

And what might be gained by that? Increased likelyhood of live
playback?  I'm not sure a streaming solution where, depending on
you're weight, e.g. one out of 100 peers might be able to actually
watch the stream live would be that much applauded.

Regards, Bruno.

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



More information about the BitTorrent mailing list