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

Elliott Mitchell ehem at m5p.com
Tue Feb 8 19:10:39 EST 2005


>From: Olaf van der Spek <OvdSpek at LIACS.NL>
> > 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.

I've stated why I think THEX is bogus.


>From: Justin Cormack <justin at street-vision.com>
> 
> > 
> > Justin Cormack wrote:
> > > 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?

Nope, though the mainline BT1 client defaults to transfers of 16K though.
Most other clients used 32K. *shrug*, either would work. 64K might be
worthy of consideration.

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

Torrent file size is one consideration, but it shares equal ground with
HAVE messages.

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

There are two other things to consider here. Data transfer per peer, and
overall BT overhead. Figuring the canonical 50 peers equally handling the
load, each peer will send you roughly 85MB of payload. At this point that
512K is 0.5% overhead, not large but not something to casually enlarge.
Overall with BT1 HAVE messages come out pretty close to a full 50% of the
overhead.

Other factors here. Assuming the low-level encapsulation stays the same,
those messages have 4 bytes of length (silly seeing how no clients send
messages larger than 64K) and 1 command byte. You've made them have a
total size of 11 bytes per, at which point the overhead is 704K, 1%.
Against this, on average peers will have 50% of the pieces, bringing it
back to 352K, 0.5%. A smart peer could also supress HAVE messages for
pieces you're already known to have, bringing it all the way down to
0.25%.

This still represents nearly all of the BT overhead though.

(note to others, I conceed certain earlier arguments along similar lines
here; I now understand which way to go there)

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

Considering 1TB torrents, that bitmap hits 2MB, a very hefty connection
overhead indeed.

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

Does indeed amount to a compression algorithm of sorts. There is the one
other issue Olaf mentioned, by causing clustering of requests you greatly
reduce the load on your disks. Considering modern line speeds and this
does turn out to be a massive speed boost. In the light that HAVE
messages are the single largest portion of the BitTorrent protocol, it
does make sense.


-- 
(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \   (    |         EHeM at gremlin.m5p.com PGP 8881EF59         |    )   /
  \_  \   |  _____  -O #include <stddisclaimer.h> O-   _____  |   /  _/
    \___\_|_/82 04 A1 3C C7 B1 37 2A*E3 6E 84 DA 97 4C 40 E6\_|_/___/




 
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