[bittorrent] 'Rarest first' question.

Elliott Mitchell ehem at m5p.com
Sat Jul 1 01:23:42 EDT 2006


>From: Bruno Hertz <brrhtz at yahoo.de>
> Elliott Mitchell <ehem at m5p.com> writes:
> >> 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.
> >
> > If you have the space, merge-sorting is quite efficient. By avoiding
> > seeking the disk during writes, this likely does provide speed gains.
> > Given how many files are useless until totally reassembled, seems a very
> > worthwhile approach.
> 
> Thanks for the pointer. I have a vague recollection of nifty
> approaches to sort data under both constraints, minimum core memory
> usage and disk access. Couldn't name one offhand, though.

I'd always filed it under "obvious ideas" and figured I'd do it at some
point. Didn't seem worth mentioning otherwise, but certainly worth
defending.

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


> Well, I myself don't really care that much. But I may emphasize that
> there's still a huge difference between sequential and random
> selection, the actual point of the main discussion I've involved
> myself in. It's not about random vs. rarest first, it's rather
> sequential vs. random/rarest first.

Agreed.

> >> 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.
> >
> > That may be the effect, but I highly doubt it was the original goal. As
> > already pointed out, beyond a certain level of entropy, additional
> > entropy isn't useful. Once every piece is helf by at least six of your
> > neighbors, performance of those neighbors is more crucial than entropy.
> 
> 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.

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

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


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

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


-- 
(\___(\___(\______          --=> 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