Re: Have maps (was Merkle, URLs, etc)

----- Original Message ----- 
From: "Justin Cormack" <[email protected]>
Subject: [BitTorrent] Have maps (was Merkle, URLs, etc)


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

In my view there is no need for another problem. The binary trees create 
pure bloat that serves no purpose except to provide for more bloat.

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

Actually I hadn't thought of using Bloom filters, they do seem a reasonable 
approach. The only problem I see is generating the necessary number of hash 
functions, the easiest way to solve this problem is to prepend 0, 1, 2, 
...., k to the crypto hash already being used, and mod out by the bitfield 
size. Now the question is, how to determine the parameters. In my view there 
are a number of variables; the number of nodes, the false positive rate, the 
size of the Bloom bitfield, the number of hash functions, and the critical 
point for measurement of false positives. Locating some old texts I've got:
N =  # nodes * measurement Point in %.
M = bitfield size
K = # hash funcs
P = probability of false positive

P = (1-(1-(1/M))^KN)^K

This is easy enough to algebraicly manipulate to find near optimum numbers 
given all but one input, I just don't feel like solving it.

The various inputs would also have to be included in the torrent file (or 
URL) mostly the number of hash functions, and the bitfield size. The 
question in my mind, and one that needs some implementation and testing to 
solve is what is the real protocol advantage of Bloom over the prepended 
children list, and the flat list. My worry is that under the birthday 
paradox it would require nlogn space to store a Bloom field that would have 
a 50% probability of collision for n insertions. This worries me some as the 
peers approach a complete download since the number of collisions will rise 
exponentially, leading to a potentially large number of false positive 
queries for these near seeds, possibly slowing their connection. To take a 
braindead case, consider a file with 10,000 nodes, but only a single bit 
bitfield. The result is that the peer is queried for many nodes it does not 
have yet once the first node is downloaded. Obviously this case is unlikely 
to happen, but the same happens when you have 9,999 bits in the bitfield, if 
only for the last piece. This complicates the endgame and as result concerns 
me since the endgame is already the most difficult phase. The BitTorrent 
simulator that someone mentioned a bit ago would be extremely helpful in 
answering these questions.
                    Joe 



 
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/