Re: hash-based requests

>From: Justin Cormack <[email protected]>
> > 
> > >From: Justin Cormack <[email protected]>
> > >  
> > > > If HAVE messages are somehow indexed to tree location, then it works
> > > > pretty well.
> > > 
> > > You can encode the path down a binary tree (left = 0, 1 = right) as the
> > > HAVE message payload. Thats fairly independent of how (if at all) you
> > > actually index your nodes. You can with non binary trees too if you insist...
> > 
> > Problem is this turns back into a variable length string.
> 
> But log N bounded, which isnt very much. But it doesnt buy you anything.

I already suggested a numbering structure which would work. Keeps the
HAVE messages smaller.

> > > > > The other alternative is a two-phase protocol where you first obtain the Merkle
> > > > > tree before you can do anything else.
> > > > 
> > > > I'm working on a sample implementation which computes the hashes, and
> > > > uses a midsize branching factor. Turns out working with n-ary trees isn't
> > > > always easy.  %-)
> > > 
> > > Its almost never worth it. Possbly never... Whats your reason for not using
> > > binary?
> > 
> > I'm working with block size divided by hash size as the branching factor.
> > This results in a node fitting into a single message. At the same time
> > a block of hashes can be accounted for like a payload block. Should also
> > mollify the folks looking for a flatish tree (2TB with only 3 levels).
> > 
> > Problem is computing the indicies correctly.  %-)

> Well you can get that right (and padding the tree with empty leaves (length 0,
> hash to match) might help.
> 
> However why not have a binary tree and send more children and granchildren
> with a request if you want to get the message size up? It pretty much amounts
> to the same thing and is simpler. With a 32k message, and 20 byte hashes, 
> each request will get 10 levels of a binary tree in one message (slightly
> smaller, so only 1TB fits in 3 levels...)

You wouldn't bother sending the direct children, only the grandchildren.
At this point it effectively reverts to an n-ary tree. Notably converting
to bitfield indicies once again becomes annoying. This does limit things
to power of 2 branching, but the computations are still annoying.

With things turning into an n-ary tree no matter what, I once again have
to question the wisdom to sticking to "THEX". Just seems completely
inappropriate here.


-- 
(\___(\___(\______          --=> 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/