[bittorrent] 'Rarest first' question.

Elliott Mitchell ehem at m5p.com
Thu Jul 6 01:43:52 EDT 2006

>From: Bruno Hertz <brrhtz at yahoo.de>

> 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'
> algorithms?

"Choice" is a bad synonym for "piece selection"?

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

Yup. Though with the file sizes BT was designed to handle, even 1MB
chunks cause much of a diversity problem.

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

Ouch! Perhaps not a problem with the commonly used file sizes, but the
moment you work with files larger than the amount of memory you have,
this is a problem if done throughout the download. Also a problem for
bad apples.

Disk seek time is very much a problem. It is far more efficient to grab
256KB chunks from disk than 16KB chunks. With the latter you quickly run
into performance problems, unless you can hold the entire payload in
memory (okay, not a big deal with many torrents).

The bad apple problem is much more severe. If you've grabbed 16 chunks of
a piece from 16 different peers and the checksum is wrong, which peer
caused it. Very bad if a peer merely /sometimes/ gives bad chunks. More
significantly, if 16 peers have that piece, it isn't too rare and you
won't be able to upload it much.

There are two times when it makes a great deal of sense though. At
startup you need a whole piece quickly that someone is interested in
downloading. Grabbing a somewhat more common piece from a couple of peers
to complete that one piece quickly then makes a lot of sense, because
though less valuable due to commonality. it is more valuable since you
can then trade it earlier. Towards the end you get the benefit of
completing that one last piece even if held by slower peers.

I'd tend towards not metering tit for tat strictly on bytes downloaded.
In particular, if a peer asks for 1 byte at a time, something is up. I'd
tend to count each REQUEST message as a few bytes (processing time) and
each non-sequential REQUEST as a few more bytes (due to seek time cost).

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

You misunderstood what I ment. I was suggesting that a peer could do a
sequential download where the sequence started at a random block, looping
around to the first block when the end was hit. ie in a 7 block torrent
one might download in the order 1-2-3-4-5-6-7, another might do
4-5-6-7-1-2-3 and another might do 6-7-1-2-3-4-5. This should perform
fairly well, once those groups overlap. Not something I would do, I'm
just saying it /could/ work.

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

The approach that strikes me as best is a biased random number generator.
Make it more likely to pick pieces that need to be played back soon and
make it more likely to choose pieces that are rare (the metric that rare
pieces are more likely to be traded still holds). The trick is to get the
biasing right to keep playback rate constant. I'd guess something along
the lines of a hyperbolic function for both (a piece only available from
one peer is a heck of a lot more valuable than a piece available for two
peers, a piece available from all but one peer isn't much more valuable
from all peers; if a piece is about to be played back, it is important to
get it *now*, if it is far in the future it isn't too important for now).

Note that in the case of fully downloading prior to playback, this
degrades to the strategy of rarest first (because your playback metric is
giving flat values for all pieces, but the rarest first metric is giving
differing values).

>From: Arnaud Legout <Arnaud.Legout at sophia.inria.fr>
> Elliott Mitchell wrote:
> > 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 am not sure I am interpreting correctly what you are saying. If you 
> intended to point out
> that as you cannot test from a client the piece selection strategy of 
> other clients, you cannot
> specify with a MUST (note that I am not shouting, I am just using the 
> notations used in RFCs)
> the piece selection strategy, you are wrong. Specifying a protocol does 
> not mean that you can enforce the
> specification. Take for instance TCP, you can enforce the packet header 
> format, you cannot enforce the
> congestion control algorithm.
> (The reality a bit more complex, but the details are not relevant for 
> this discussion)

Okay, perhaps. Again the specification says "generally", that doesn't
sound anything like "must".

> One criteria to deem if a protocol is good is when a selfish user must 
> follow the protocol specification in order to improve
> its the satisfaction.
> This is clearly the case of rarest first when your satisfaction comes 
> from the speed of download.

Ah, but as mentioned, a peer doesn't have to follow pure random selection
nor rarest first to get good performance. Those are just the simplest two
algorithms to get good performance. I would agree that a selfish peer
can't get better performance by using other algorithms, just that other
algorithms can get comparable performance.

The prefer earlier chunks algorithm is one such. It doesn't result in
significantly improved download speeds, it just results in getting
earlier pieces sooner and results in something that can come close to
the performance needed for streaming.

> There are two important properties of BT:
> -efficient content replication
> -scalability/resilience to flash crowd
> For both properties rarest first is required.

When have I suggested tossing rarest first? Or that rarest first is bad?
I've been trying to merely suggest that alternatives can be used and
still conform. At no time have I had thoughts of completely tossing
rarest first, merely treating it as a metric amoung several metrics.

> I agree that there are tons of scenarios for which rarest first may not 
> be appropriate, but in this
> case does it still makes sense to consider BT. We can surely reuse part 
> of it, but if you don't use rarest first
> or the choke algorithm, then it is not BT anymore.

Where does the protocol use a synonym of "must" in conjunction with the
piece selection algorithm? I don't see it anywhere.

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