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

[Arno Bakker <[e-mail]>]

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.


> 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

Note that a binmap is a novel data structure to efficiently store a
bitmap, which is not directly related to bin numbers.

Regards,
    Arno