Standards (was [BitTorrent] Back to Merkle Hash Trees...)

Justin Cormack justin at street-vision.com
Tue Feb 8 11:45:03 EST 2005


> 
> 
> Justin Cormack wrote:
> >>
> >>>>>It messes up the code, because you cant allocate buffers until you receive
> >>>>>it.
> >>>>
> >>>>What's the disadvantage of the delayed buffer allocation?
> >>>
> >>>
> >>>You start to get have messages for example before you know what they mean
> >>>because you dont know the piece size. Even if you just connect to a peer
> >>>to get the info blob it has to send you have messages. And a bitmap that
> >>>you dont know whether it is the right length. You are going to have to
> >>>cache all this stuff and process it later.
> >>
> >>That'd be one option. You could also introduce a have_info message and 
> >>not send other stuff before you receive that.
> > 
> > 
> > The other major problem is when conencting to a torrent, if most peers use
> > the URL encoding it will be very hard to find a peer (ie the seed) that has
> > the info data. If there are a lot of clients all at once there will be a large
> > delay before anyone can do useful work.
> 
> The first thing any peer does, is get the info. The info is probably 
> very small (size depends on the file count), so would that really be an 
> issue?

I think it can be. If a lot of peers connect to a torrent at once, most wont
have it. If you request it what should they do? You dont mention this case.
Presumably you should only ask one peer at a time for it (or you run the risk
of eating bandwidth by getting multiple copies) so if a small proportion of
the peers have it it can take a long time to find them.
 
> >>>>>>>eg see the THEX paper.
> >>>>>>
> >>>>>>No it doesn't. That paper says nothing about minimal transfer size.
> >>>>>>It does mention 1 kbyte as base segment size, but my 'spec' uses 1 kbyte 
> >>>>>>as base segment size too but it doesn't use it as minimal transfer size.
> >>>>>>
> >>>>>
> >>>>>
> >>>>>But if you cant transfer less than 32k, there is no point having the
> >>>>>segment size less than 32k. As far as I can see.
> >>>>
> >>>>The (only) point is to make the root hash (and top of the tree) 
> >>>>independent of the chunk/piece size and to maintain compatibility with 
> >>>>other uses of merkle hashes/THEX.
> >>>
> >>>
> >>>But your implementation has a fixed 32k chunk so that dopesnt matter.
> >>
> >>It does. I could change my implementation without invalidating old 
> >>.torrents.
> >>
> >>
> >>>Being compatible with other uses, hmm, well I am not sure. Who else is
> >>>using THEX?
> >>
> >>I don't know. I considered the cost of being compatible lower than using 
> >>another base segment size.
> > 
> > 
> > Personally I think 4k as a chunk size and hashable size makes sense as this
> > is the most common page size and file system block size so it is the amount
> > that will be written to disk anyway, and its not too small.
> 
> But what is the advantage over 32k? Do you consider 32k too large?

Well 32k might be reasonable if piece = chunk = 32k if there is not too much
overhead in sending out have messages. Not having piece and chunk simplifies
things. Actually I would pick 65536, and then use 48 bit chunk numbers,
bacause I am tidy minded that way... Its an improvement over the current
(typical) piece size of 256k or 1M. The main reason this was so high was
because of size of torrent file.

Doing the maths, a 4G file with 64k pieces/chunks will have 64k of them,
which means a bitmap is 8k, which is smaller than a request (64k) so
thats not a huge transfer. you will get 64k have messages (worst case)
which is 512k. These figures are per peer.

Actually the file size for which the request size = bitmap size is:
64k chunk: 32G
32k chunk: 8G
4k: 128M

With 4k pieces/chunks the bitmaps get too big (128k) especially compared
to the transfer size which has gone down to 4k. You clearly need to change
how these are encoded.

In fact if we dont want to change the encoding you could specify the
piece and chunk size by this rule...

Your scheme where you can transfer and verify 32k chunks but cant tell
anyone you have them until you get enough to make an arbitrary larger
piece doesnt make much sense to me. It is a kind of lossy compression
of have and bitmap messages in effect.



 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/BitTorrent/

<*> To unsubscribe from this group, send an email to:
    BitTorrent-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/
 





More information about the BitTorrent mailing list