[bittorrent] 'Rarest first' question.

Bruno Hertz brrhtz at yahoo.de
Fri Jun 30 13:00:13 EDT 2006

Elliott Mitchell <ehem at m5p.com> writes:

>> 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.
> Quite true, but you sounded to me like you didn't regard disk seek
> performance as an issue in any way what so ever. Perhaps not a huge issue
> yet, but it is likely to become a bigger issue as wide-area networks
> become faster. Very much an issue for local transfers though.

No, I'd very much welcome a good caching algorithm. Not only because
of the throughput, I'd highly appreciate extending the life span of my
disks either.

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

>> Are you to say clients may download in any order they choose?
>> Interesting interpretation of BT ...
> Please find the words "must" anywhere in the mentions of rarest first.
> Random order is *any* order, at which point any selection is valid by
> the protocol. Notice too, that portion is untestable. You can look at the
> over the wire and .torrent files and deterministically state that
> something is valid or not. You cannot test for a random selection order
> and so any is valid.

I've been through that discussion a couple of times now. Just because
you can't prove a dice is perfect (i.e. produces each number with
exactly the same probability) doesn't mean any dice will do. With
which you'll readily agree in case you've already done your basic
stochastic course.

In other words, there's a distinct difference between 'selecting a
piece randomly' and 'selecting a piece picking scheme randomly' in the
sense of an arbitrary scheme. It's the difference between selecting
the uniform probability distribtion or any probability distribution.

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.

>> 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.
> Incorrect.
> The protocol specification does not require clients to send HAVE
> messages, nor provide a full bitfield. The specification tells you what
> those messages mean and provides suggestions for how to use them, but a
> client doesn't have to send them in order to conform to the BT protocol.
> Having said that, in general those give you a rough estimate of peer
> performance as most clients will send them, since they want to talk. Yet
> there are a number of interesting things that can be done which degrade
> the quality of that estimate. Suppression of HAVEs for pieces you're
> known to already have is one such (pretty much you have to divide by the
> fraction of pieces you have to correct for /this/, but other games can be
> played as well).

Your objection is valid. You might add that in large enough swarms,
even if 'have' messages and bitfileds were consistently sent, as not
all peers are interconnected there'd be still no global knowledge
which pieces are rarest. Which leaves you at exercising empirical
studies, in case you were to prove which algo performs better.

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.

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

And regarding those six neighbours, that'd be saying that in an
interconnected swarm with six seeds entropy does not matter any
more. Well, I'd argue that.

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

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.

>> 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.
> The odds are very much better than that. Crucially there is a lot of
> extra buffering involved. You end up with the torrent divided into three
> areas.
> The first segment is the portion already played for which you hopefully
> have all the pieces. You're not really interested in these pieces anymore
> as you won't replay them. OTOH you do keep them around as you can trade
> those pieces to peers behind you in playback.
> The second segment is a near-window of soon to be played pieces. Your
> portion of this area is densely populated by pieces you *have*. You're
> very interested in downloading any pieces in this area as you must soon
> play them, but you can also trade them too.
> The third segment is a portion well beyond the portion you're playing.
> You won't soon play them, so you're not too interested in them, but if
> you can't download anything else these will be valuable in time. These
> can also be traded to peers who are well ahead of you in playback, that
> have pieces you are really interested in.
> You can estimate the rate at which download will complete. The trick is
> to ensure the fully populated first area is sufficiently large that it
> will grow to encompass the whole torrent before playback reaches the end.
> The borderline between the first and second areas is where playback can
> occur (beyond that you're missing pieces and cannot play).

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.

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

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