[bittorrent] 'Rarest first' question.

Bruno Hertz brrhtz at yahoo.de
Wed Jun 28 20:10:12 EDT 2006


Arnaud Legout <Arnaud.Legout at sophia.inria.fr> writes:

> Hi,

Hello Arnaud, thanks for your reply

> Bruno Hertz wrote:
>>
>> I browsed through your paper, thanks very much for the link. Two
>> questions though:
>>
>> (i)  since you measured torrents in the wild, how could you actually be
>>      sure the other clients employed rarest first? Not only did the
>>      original BT spec recommend random piece selection, but it may also
>>      be that developers twist the algorithms to serve other goals.
>>   
> no, the BT spec urges to use the rarest first piece selection. There is 
> a random piece selection for the first pieces only.
> I give some details on the piece selection in the paper.

Well, I'd say too BT suggests rarest first, and I also see
why. Problem is there is no written spec apart from 1.0, which
suggests random selection. If you know of any other formal, written
specification, apart from the mainline source code, please let me
know.

>>      E.g. the two first projects I contacted these recent days looking
>>      for a BT library I could use are considering implementing resp.
>>      have already implemented hybrid algorithms, with partial rarest
>>      first and partial sequential piece selection. One project to
>>      allow to watch movies while downloading, the other to provide for
>>      better disk caching.
>>   
> I am not sure what you mean by hybrid. It is known that random piece 
> selection performs poorly
> in most cases and do not outperform rarest first. You can have a random 
> choice when you have a set
> of pieces that are rarest. Also, if you have pieces ordering constraints 
> (live stream, content preview)
> you may implement something else than rarest first. But this is at the 
> cost of a decrease in system capacity/efficiency.

I'm aware of that. Currently I'm in a discussion with the libtorrent
developer to talk him out of making available a hybrid algorithm,
which applies rarest first selection for pieces with availability < 7
and strict sequential (!) download for pieces with higher
availability. That's what I call hybrid. Link here:
http://sourceforge.net/mailarchive/forum.php?thread_id=14663525&forum_id=33471

You may browse through the first three or four postings in that thread
to get a picture.

His motivation btw is better caching, to reduce disk seeks. That's why
he basically wants to serialize the pieces to some extent, simply by
downloading them in that order :)

Developers seem to find all kinds of motivations to deviate from the
'standard', I already mentioned another one: watching movies already
while downloading, again a motivation for sequential piece selection.

It's either users who come up with all kinds of weird feature
requests, and developers trying to please them, or the developers
themselves who think up ways to 'improve' bittorrent, make it faster
or whatever.

I've been looking into this for about two weeks now and already got
the impression developers implement anything but the mainline
algorithms (ok, that's an exaggeration, but the tendency is definitely
there).

I'd post a link to a discussion with another library developer, but I
rather prefer not because that one got emotional and out of hand, so
I'm not particular proud of that exchange. Let me know though if
you're interested.

>>      From this I got the impression clients might do what they want
>>      anyway, so did you actually limit your measurements to peers you
>>      know for sure use rarest first?
>>   
> I have the client ID for all the peers in the torrents I monitored. To 
> the best of my knowledge everybody implement rarest
> first. There are some specificities from protocols to protocols, but the 
> main piece selection strategy (i.e., the piece selection
> strategy used for most of the download) is always rarest first.
> We have checked the code of several clients in several versions (in 
> particular Azureus and mainline).
> You are right that clients can implement something else. But, there is 
> no known piece selection strategies that performs better
> than rarest first (except if you have coding techniques, which is not 
> the case for my experiments). So there is no incentive
> to use something else than rarest first.

You don't need to convince me. I have a math background, and to me it
is intuitively obvious that rarest first very likely performs better
than random selection and surely better than sequential. Finding the
proper arguments though in discussions is not that easy, since there's
all kinds of other random factors involved (initial peer set
etc.).

Also, not all people seem capable to follow the logic involved, and
they might not really understand how much peer and piece selection are
at the very heart of BT.

Regarding the incentives, well see above.

>> (ii) the graphic plots in the pdf are pretty hard to read. You haven't
>>      some larger copies lying around on some web server, haven't you? I'd
>>      really be interested in seeing some more detail.
>>   
>
> I can send you the original eps version of any plots if you give me the 
> fig number in the paper.
> I which details are you interested in.

Are they that large? I hoped you could just roll them all into a zip
or tgz and put them up on your web site. Others might be interested
too.

If that isn't feasible though, I'll give you specifics about which
results interest me.

>> Finally, while browsing through this list's archives, I saw you
>> mentioning you might make your instrumented client publicly
>> available. There isn't any news in that regard, is there?
>>   
> I have not yet put it in the public domain. However, if you have a 
> specific experiment in mind, we can discuss it.

Well, I'm not coming from the academic end but rather considering
client development. Right now I'm checking out projects I might
contribute to and make use of.

As mentioned, one issue the libtorrent developer is concerned with is
caching. Your client might for example help to gather some statistics
for this, better understand piece request and download behavior and
maybe discover patterns.

I myself would like to look into the behavior of different clients on
live torrents, including deviations from the standard. In particular,
that's something tracker hosts might be interested in, so again your
client could be the starting point for something practical.

Don't feel urged though. If it's a licensing (or competitional) issue
I might also pick an open source client for now and modify it myself
...

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