[BitTorrent] Have maps (was Merkle, URLs, etc)
Konstantin 'Kosta' Welke
kosta at fillibach.de
Wed Mar 9 21:49:30 EST 2005
On Mon, 7 Mar 2005 17:21:38 -0800, Joseph Ashwood <ashwood at msn.com> wrote:
> From: "Konstantin 'Kosta' Welke" <kosta at fillibach.de>
>> On Sun, 6 Mar 2005 17:36:43 -0800, Joseph Ashwood <ashwood at msn.com> wrote:
> [Optimal case for binary trees?]
>> In the case of "I need to verify this one piece to be able to share it".
> Actually the optimum case for that is having the verification in the node,
> regardless of branching. this then leads to the overhead to verification =
> depth, binary trees will be deepest, they are not optimal.
IBTD. Branching is as important as tree depth. In order to verify a
piece, one needs its hash. To verify the hash, you need all the siblings
and its parent. So the total number of nodes needed to verify a hash
is about braching*depth. Of course, this number decreases with every
piece we download, as we already have internal nodes.
> Searching is important when a piece is requested, there is a search overhead
> to determine whether or not that piece is available. Using a perfectly flat
> tree this is a search of the minimum possible area, using a binary tree it
> is a search of the maximum possible area. These represent the extremes
> available, the binary tree is the most costly.
I thought of an implentation where this search is not necessary. If a piece is
avaiable (i.e. downloaded and checked), some bit will be switched to 1 in a
bitfield of size p. Checking that is O(1) as we know which piece is requested.
I also thought that the tree nodes are numbered consequtively. (This is very easy
for a binary tree) This makes it possible to just use simple arrays to store
the tree, too. I think someone posted some basic math to do that on this list
about a month ago. In other words: All node-retrieving and storing operations
are done in O(1) time. This also means that calculating which nodes are necessary
for a piece are done in O(h*N) time.
>> Just so I get it right: Are you talking about "What partial trees do I
>> need next?" or "What partial trees does my peer need?". In the first case, I
>> cant follow you (should be logarithmic, just like for all trees). In the
>> second case, I can neither see a computational difference.
> It is the second case (peer need). The overhead of this becomes critical as
> the trees and number of connections grows, it is linear in both but
> exponential in the combined. By adding overhead to the search for the next
> piece you slow down the tit-for-tat, on a single peer with a single file and
> a single connection, this is not ciritical, but as these numbers grow it
> becomes increasingly necessary to predict what your peers will want in order
> to reduce the computation overhead (i.e. don't flush it out of the memory
I'll think about it, but cant we just evade the problem by letting the peer
that needs the nodes just request them?
> I didn't post about it. The search overhead problem is succinctly "find me
> piece with hash X" finding it in a Merkle tree is costly, binary is the most
> costly, flat the least, but finding it in a 256-ary tree in a shared
> MerklePool eliminates the advantage/disadvantage in this case.
Why dont just number the pieces. No search required.
And finding a node in an unordered tree in linear to the number of nodes, so there
should not be a very big difference between binary tree flat tree, as the
binary tree only has about twice the nodes of the flat one.
> The better way is to compute all the nodes at a single level (this is where
> I began the use of the MerklePool), but the cost is primarily in the depth
> of the tree. as the depth increase it becomes necessary to maintain indexing
> across multiple levels, by flattening the tree this again exponential
> overhead is reduced.
Sorry, I dont understand :)
> Modern hashes have substantial overhead in the finalization operations, by
> having the smallest nodes possible the finalization code is executed the
> maximum number of times. As the size of the nodes shrinks linearly, the
> number of internal nodes increases super-linearly.
> As the number of nodes
> increases the number of times it is necessary to run the finalization code
As the number of siblings on one level increases, this increases.
> I did have a misstep there, I believe it is only a polynomial
> increase, not exponential.
I think that is it polynomial in O(height^2) or something like that. I was
unaware of that problem, good that you mentioned it.
>> Note that I do neither think that binary trees are the best choice. They
>> are worst case for tree size but optimal case for quick verification of a
>> single piece.
> Here is where we substantially differ. In verifying a single piece in a
> properly formatted n-ary tree (like my proposal) the cost is the tree depth.
I think that the cost is depth*N. How do you check a node without knowing
> This is the same optimal cost for binary trees. The n-ary tree will be
> flatter and so offers faster verification of the piece than the binary
> version. For reference, my implemenation can verify a single piece of a
> 478MB file in 4 hashes, assuming 4KB blocks, the same performance for a
> binary tree would only be a 65KB file, again assuming 4KB blocks. Verifying
> the same 478MB file would take a binary tree 29 hashes (assuming I counted
> correctly) approximately 7 times as long. 7 times the time is not a small
> performance penalty.
Could you write out what exactly is calculated here? Are you assuming
that you only need all ancestors of a leaf to verify it and its contents?
>> To know if this is really relevant, this bittorrent simulator might
>> be helpfull (I think I'll start coding next week). If it is irrelevant, we
>> should use flat trees. I not, a tradeoff using n-ary trees seems good.
> I agree a simulator would be of great help.
Lets start with a tree calculator! ;)
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