Re: Have compression (was Re: Standards (was Back to Merkle Hash Trees...))

>From: Justin Cormack <[email protected]>
> 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.

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.

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.


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

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


-- 
(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \   (    |         [email protected] 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:
    [email protected]

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