[bittorrent] 'Rarest first' question.

Bruno Hertz brrhtz at yahoo.de
Thu Jul 6 08:37:12 EDT 2006


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.

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

If a client chooses to unchoke more peers though it's certainly a
tradeoff situation. 

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

Sure it's not too hard to implement logic taking care of this problem
even in situations where I download blocks from several peers.  And in
the 'sometimes' case you're unlikely to disconnect a peer anyway.

> More significantly, if 16 peers have that piece, it isn't too rare
> and you won't be able to upload it much.

That's why we have rarest first, which still should govern piece
selection. For details on a sample implementation see e.g. here
http://azureus.sourceforge.net/details.php

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

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.

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

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