Have compression (was Re: Standards (was [BitTorrent] Back to Merkle

Elliott Mitchell ehem at m5p.com
Wed Feb 9 23:27:04 EST 2005

>From: Justin Cormack <justin at street-vision.com>
> > 
> > >From: Justin Cormack <justin at street-vision.com>
> > > Here is one suggestion
> > > 
> > > Lets change the have (and request etc) messages to look like
> > > uint32_t clen
> > > uint8_t message_type
> > > uint8_t log
> > > uint32_t piece
> > > 
> > > ie 10 bytes. piece size no longer fixed, but specified by 1 << log (may be
> > > minimum eg 1k/4k). Have messages should be as compact as possible, so if you
> > > have the whole file (the initial message from a seed) you send (for 4G file)
> > > log=33, piece=0. We can abolish the bitmap message and just send initial
> > > have messages, as mostly clients will have significant locality [They could
> > > be longer, but we want to encourage some locality for performance reasons].
> > 

> > Second, the protocol design encourages locality at the small scale and
> > discourages it at the large scale. By making pieces 256K, clients tend to
> > maintain that size locality because spreading requests out further harms
> > them by taking longer to obtain an advertisable chunk. Throughout the
> > protocol documentation, note that it is *deliberatly* encouraged to
> > choose pieces to download at random as this gives you a distinct set of
> > pieces and increases the likelyhood of others both being interested in
> > you and having pieces of interest. As a result of this it will be rare
> > that you get sufficient contiguous pieces for extents to be worthwhile.
> Pure randomness at small scale is clearly bad, for performance reasons,
> but randomness at large scale is beneficial. Its a tradeoff, and the way
> to deal with tradeoffs is to either give the clients the flexibility to
> choose (they after all want to optimise their download rates), or to find
> a global optimum (if its not dependent on circumstances). Justify 256k as
> being optimal if you think it is. It was a tradeoff based on torrent
> size in BT1, not based on peer protocol.

And the problem is that extents are slightly worse at handling medium
scale (piece) blocks, and at the large scale the randomness will destroy
the usefulness of extents. This does profit at the very begining and
very end, but those are brief (we hope) time periods.

The 256K comes from BT's default, beyond that I can't say much. It has
been discussed before that much smaller and HAVEs bloat. Much larger and
startup takes too long. I can see a per-torrent setting remaining, but I
don't see a varying size one to gain much.

> > Overall I think at the start you'll end up advertising pieces so small
> > that peers don't want to bother with you. Towards the end you'll have
> > large extents, but you'll be filling small holes. You're not the only
> > person to think of extents, but I for one just don't see how they could
> > end up being worthwhile.
> I think the suggestions I gave of 1. dont send haves to choked peers until
> you unchoke, 2. dont send haves to interested peers as they already have
> something until they say not interested, and 3. make the unchoke give
> explicit transfer sizes might help this. It might not be siginificant though. 

#1 and #2 are trying to batch things so that you'll have something large
enough to justify an extent. Due to the randomness, I doubt you'll even
come close to break-even. For #3, simply declaring a block size during
the initial handshake seems a better choice...

Thinking about this, I /do/ see why you brought up latency though. You
can work around that by sending extent-haves in anticipation of
not-interested messages.

> > I worry I'll be flamed for this, but I suspect the deal is that the
> > official client's handling of begining and ending is pretty well bogus. A
> > 30% overhead has been cited for end-game mode and dups. A better approach
> > might be to assign the blocks to different peers. This degrades the
> > peer's performance (anyone want to make a client that tit-for-tats for
> > this?), but gets you whole pieces much faster. Outside those two domains,
> > raw bandwidth is more essential than rarity of whole pieces so reversion
> > to the conventional strategy is best.
> I am not sure there is a good justification for endgame mode, but will
> listen to good arguments.

The justification is given in Bram's specification. Avoiding a long wait
for a request message sent to a client on a slow connection. I think the
above seems a more likely approach (despite causing seeks on the peer).

> > Why bring up latency? There aren't any parts of the BT protocol that are
> > affected by latency. Tune your queue depth appropriately and your network
> > connection will never be idle (unless everyone else is too slow). The
> > above suggestion would be more latency sensitive, but nothing in the
> > protocol requires round trips (except initial handshake).
> I was specifically referring to latency as the time between you downloading a
> chunk and reannouncing it with a have message, not round trip latency.
> This is a measure of the propogation of data that is independent of
> bandwidth.

When you get a swarm where the breadth of the swarm is 37 (10 minutes for
a 16 second link latency), then I might start worrying about every person
on Earth, the other planets orbiting sol and all the asteroids between
Mars and Jupiter trying to download something at the exact same (might
be having to look at 256bit IP addresses too).

So, back to the issue, why bring up latency? The BT1 protocol isn't
effected by it, and if properly designed neither will BT2.

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

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

<*> Your use of Yahoo! Groups is subject to:

More information about the BitTorrent mailing list