[ppsp] 回复: Re:回复: Re: Proposal to resolve Issue 10 + 13

[zhangyunfei <[e-mail]>]

Hi Arno，
    Pls see inline.Thanks.

Yunfei




zhangyunfei

发件人： Arno Bakker
发送时间： 2012-04-18 15:31
收件人： zhangyunfei
抄送： ppsp
主题： Re:[ppsp]回复: Re: Proposal to resolve Issue 10 + 13
On 18/04/2012 09:00, zhangyunfei wrote:
> Hi Arno,
> I think I understand your example. So is there some figures to show that 
> the case I raised is a small-probability case? That would be convincing 
> to show the efficiency of MHT method.

Hi Yunfei and all

bin numbers can be more bandwidth efficient and lead to a more elegant
design when used in combination with content integrity protection using
Merkle hash trees, as there is one unit in the system then. The
efficiency gains depend on usage. If you request chunks in groups of
powers of 2 (e.g. 128 KiB, 256 KiB) as is common in computer networks,
you only need single bin numbers. On the other hand, if you want to
express a sliding window over the chunk space, especially when that is
not a power of 2 wide, you need more than 1 bin number.

[Yunfei] This is what I worry about. We cannot assure that each time we can request 
chunks in groups of powers of 2, as it's dependent on what the serving peers have, which 
is hard to ensure that the number of available chunks being powers of 2. In such cases, requsting 
a range of chunks needs no more bits than bin number. What's worse, if the chunks peer A has is 
sparsely distributed, i.e., the chunkmap is likely to be 10001011110, bin numbering needs more bits.

> BTW, I remember that in last interim meeting, you replied that the 
> mapping between binmap and range expression is quite easy. Could you 
> elaborate this mapping? Thanks.

Assuming ranges are intervals of a list of chunks numbered 0...N: for a
given bin number "bin":

startrange = (bin & (bin + 1))/2
endrange = ((bin | (bin + 1)) - 1)/2
[Yunfei] I need more time to reply on this:)
Note that a binmap is a novel data structure to efficiently store a
bitmap, which is not directly related to bin numbers.

Regards,
    Arno