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

Hi Arno，
    Please see inline.

zhangyunfei

From: Arno Bakker
Date: 2012-05-09 15:02
To: ppsp@ietf.org
Subject: Re: [ppsp][Spam] 回复: Re:回复: Re: Proposal to resolve Issue 10 + 13
On 09/05/2012 08:19, Arno Bakker wrote:
> 
>> 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.
> 
> Bins are actually more efficient than (start,end) in this example. With
> bin numbers, you'll in the worst case need an integer for every 1 in the
> bitmap, so 6 in this case. In a better case we might be able to address
> the 4 ones at the end as a single bin. However, if you use (start,end)
> addressing, you'll actually need 2 integers per 1 bit, or 12 integers.
> 

Correction: bins are equally or more efficient. It will take 3
(start,end) byte range pairs to represent 10001011110, so 6 ints. It
will take 3 to 6 bins to represent that, so 3-6 ints.

Yunfei: For representating a single 1 followed by 0, the range pair can be shortened 
from (start,end) to just (start). So 3 ints are eliminated in this case.
So my point is that:
1) in a worst case for bin, 101010..., the scheme of bin and range are equal considering in such case range scheme . only 1 ints is needed for a single 1;
2) in a common case where there are the consecutive 1 with the amount not the order of power of 2,
the scheme of bin is not more efficicent than range.
3) Only in the case where the consecutive 1 are of the amount the order of power of 2, one int is saved in bin scheme.
However the complexity is also increased in all 3 cases. So range scheme is a simple way to address this. 

CU,
     Arno

_______________________________________________
ppsp mailing list
ppsp@ietf.org
https://www.ietf.org/mailman/listinfo/ppsp