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

Justin Cormack justin at street-vision.com
Wed Feb 9 21:28:35 EST 2005


> 
> 
> >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].
> 
> So, you're suggesting the use of extents, instead of a bitmap. There are
> two problems:
> 
> First, they're harder to deal with. The data structures to really take
> advantage of them are a lot more complex than a bitmap. At best, most
> clients will become more complex and deal with it. At worst, all clients
> will use a fixed size and use a bitmap behind the scenes and you've
> increased the bandwidth needed. I'm doubtful that a dynamic size will
> gain much.

I think its worth testing. I dont think the complexity is that bad, as
you can have a bitmap and not care or a better implementation.
 
> 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.
 
> 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. 
> 
> > End game is another time where making piece size really small might help,
> > we could get rid of the endgame protcol and cancel messages if we can shrink
> > piece size down.
> > 
> > In fact the beginning and end both symmetrically require small pieces,
> > which suggests that studying this further will give us a good insight into
> > how to select sizes
> 
> 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.

> > This is only a suggestion. We have isolated a problem, realised it is a
> > tradeoff (can reduce overhead but only by increasing latency) and have changed
> > the protcol so that clients can dynamically make this tradeoff rather than hard
> > coding it into the protocol. If we find optimum fixed values (or as function
> > of say filesize) we can recommend or mandate them in a standard. If it
> > turns out to depend on network conditions it can stay dynamic.
> 
> I suspect 256K was chosen in such a way...
> 
> 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.

j


 
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