[BitTorrent] Have maps (was Merkle, URLs, etc)

Justin Cormack justin at street-vision.com
Fri Mar 4 07:34:22 EST 2005


> 
> Binary Merkle Trees: Are heavily flawed, and the only suggestion made to fix
> it was to send the grandchildren as well, which completely defeats the point
> of the child nodes, making the child nodes pure overhead, they serve no
> purpose except to enlarge the tranfer and raise the CPU time.

Apart from the performance issue (the nodes are very small and you almost
immediately need another one, what is the problem?
 
> MerklePool: It occured to me during the implementation that in many ways the
> most efficient way to implement the storage of the Merkle encoded files
> (including the partials) is to store them in one central pool structure,
> with search mechanisms used to find nodes by hash, this allows rare blocks
> to be distributed widely, and for blocks to be multicast among systems that
> should be interested at a later date.
> 
> Have maps: Actually with the MerkleTree since it is known that the root must
> be retrieved first (at least be designation), there can be a child Have Map
> associated with each request, that is specifically that when serving up an
> internal node a bitmap of the immediate children is supplied as well. This
> map will generally be only a few bytes and will be on the order of 0.2% of
> the overall transfers. Also moving the requests for these maps to immediate
> descendants of a node (or nodelist to reduce overhead) will have the same
> effect.
> 
> This works because sending the client a list of haves for nodes they know
> nothing about is pointless. The downside is that all requests are now based
> on node instead of file location, something that can be troublesome.

Thats why I suggested earlier using Bloom filters, as they transmit sets of
hashes. They need some thought to work out the best method, but you can
trade off size vs accuracy, and you can add hashes you dont know about to
them for later retrieval. You can also specify size to make tradeoffs with
overhead.  This could give you a purely hash based system with no numbering.

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