[bittorrent] 'Rarest first' question.

Elliott Mitchell ehem at m5p.com
Fri Jul 7 00:55:07 EDT 2006


>From: Arnaud Legout <Arnaud.Legout at sophia.inria.fr>
> As pointed out by Bruno, there is no specification of the protocol, but 
> http://groups.yahoo.com/group/BitTorrent/message/1260
> clearly states that rarest first is intended to by used as the piece 
> selection strategy for BT.

But does that say all other selection algorithms are invalid?

> Moreover, we have shown that on real torrents rarest first is close to 
> an optimal piece selection strategy,
> and Ashwin Bharambe et al. [1] have shown that the random piece 
> selection strategy may perform poorly.

I'll accept both statements, but they are orthogonal to my position. I am
saying other selection algorithms are valid, and in fact useful in some
situations. Certainly rarest first is very good in the general case, but
this doesn't mean it cannot be combined with other approaches, nor that
other approaches are invalid.

> Additionally, as the mainline client is developed under the supervision 
> of the inventor of BT,
> it is de facto the most up to date specification of BitTorrent. And the 
> mainline client uses rarest first as the piece
> selection strategy.

Has he stated or implied that other algorithms are not merely inferior,
but invalid? I don't read that in the protocol specification and I don't
recall him saying so. The mainline client is ment for common situations
and so likes rarest first, this doesn't mean other selection schemes are
invalid.



>From: Bruno Hertz <brrhtz at yahoo.de>
> Elliott Mitchell <ehem at m5p.com> writes:
> >> > 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"?
> 
> Thanks. So it's not choice like in 'choice whisky'. My main question
> remains unanswered though.

Sure. I'm doubtful of that providing gains very often, but why not?

> >> 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).
> 
> Well, mainline unchokes 4 peers max simultaneously, the set of which
> changes each 10 to 30 secs. With those peers, you still can cache
> whole pieces even if not every block is requested. The worst cache hit
> ratio you'd get in this scenario is .25. Or in other words, the worst
> case is you cache to serve 4 times the bandwidth than you actually
> do. The average hit rate though is likely to be much higher, so I'd
> say there's no reason to panic at least as long as you're not
> uploading hundreds of Mbit/s.

Hit ratio of .125 with 32KB blocks, .0625 with 16KB blocks.

Given disk seek times of roughly 10ms, you can handle roughly 100
blocks/second if someone goes truely random in choice (and note that
actual time spent reading the data is trivial compared to seek time).
With 16KB blocks that translates into roughly 16mbps, more than commonly
made available to end-users currently, but not really much. 

> > 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.
> 
> I didn't misunderstand you. I just wanted to give a hint on how to
> compare probabilities. In the scenario with seven pieces, what may the
> probability be that I download the same seven pieces as another peer
> so we can't trade them in the future amongst us, once with your
> selection scheme and once with rarest first? I thought my example
> gives a straightforward idea of the orders of magnitude we are talking
> about.

Okay, might need a non-standard unchoke scheme as well. Note the emphasis
wasn't supposed to be that this was a good idea. Merely that it is
*valid* within the constrains of the BitTorrent protocol.

> >> 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).
> 
> 'Degrades' in terms of playback or shareability? As you have to keep
> your playback buffer filled at any time, those pieces have to be
> selected with probability one in the time frame it needs to play back
> that buffer, no matter what. That certainly decreases, i.e. degrades,
> shareability.

Meaning that if you're not trying to play back the stream while it is
still incomplete, that weighting will be flat and so rarest first will
dominate the choice.

You're correct that it degrades sharability, but does it degrade it to
the point where it is unusable?


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