[bittorrent] 'Rarest first' question.

Elliott Mitchell ehem at m5p.com
Thu Jun 29 01:17:38 EDT 2006

>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.

> 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'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.

> 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.

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).

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.

(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \BS (    |         EHeM at gremlin.m5p.com PGP 8881EF59         |    )   /
  \_CS\   |  _____  -O #include <stddisclaimer.h> O-   _____  |   /  _/
    \___\_|_/82 04 A1 3C C7 B1 37 2A*E3 6E 84 DA 97 4C 40 E6\_|_/___/

More information about the BitTorrent mailing list