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

[Picconi Fabio <[e-mail]>]

Here's a brief comparison:

[0-P]
Bins: 1 integer if power of 2, multiple integers otherwise
Range list: always 2 integers

[P+1,P+W] worst case
Bins: W/2 integers
Range list: W/2 ranges, i.e., W integers

[P+1,P+W] average case
Bins: ?
Range list: ?

[P+W+1,N] empty range
Bins: no integers
Range list: no integers

Taking W=30 seconds and 3 chunks per second, 4 bytes per integer, and 1 buffer map per second to 10 neighbors, range list requires ~ 30 kbps in the worst case vs. ~ 15 kbps for bins. For a 1 Mbps stream, that's a 3% overhead instead of 1.5%, which I don't think is that big a deal.

Now, two things: 1) an optimized implementation of range lists would encode single-element ranges with a single integer, so the overhead would be identical to that of bins (i.e., 1.5%); 2) we're talking about the worst case which is extremely unlikely to happen... it would be interesting to do the average case analysis for the [P+1,P+W] interval.

Fabio


> -----Original Message-----
> From: Arno Bakker [mailto:[e-mail]]
> Sent: lundi 14 mai 2012 14:31
> To: Picconi Fabio
> Cc: zhangyunfei; ppsp
> Subject: Re: [ppsp] 回复: Re:回复: Re: Proposal to resolve Issue 10 + 13
> 
> On 14/05/2012 13:17, Picconi Fabio wrote:
> > Sorry about the late reply. I agree with Yunfei. As I mentioned
> during
> > the Paris meeting, I think that most exchanged buffer map are likely
> > to look like this: 1) a contiguous range [0-P] (the peer has all
> > chunks from 0 to P, where P is the playback position), a sparsely
> > populated range [P+1,P+W] which corresponds to the download window,
> > and an empty range [P+W+1,N]. So I’m not sure that bin numbers would
> > constitute a big improvement over using a list of ranges.
> >
> 
> Hi Fabio and all
> 
> can you clarify how you would express the above example in your
> proposed numbering scheme, which is [start byte range,end byte range],
> right?
> 
> In bin notation, there would be 1 or more bins to express [0-P] (more
> than 1 is needed if P is not a power of 2). For [P+1,P+W] there would
> be, at worst case (=0101010101...) 1 bin per 2 chunks, so W/2 bins. The
> empty range would require no bins. As each bin requires 1 int, the on-
> the-wire costs of transmitting this chunk availability map are ~ W/2
> integers.
> 
> To summerized my position: bins are more efficient in common
> situations, and lead to a clean protocol design when Merkle Hash trees
> are used for content integrity protection, at the cost of a small
> increase in complexity.
> 
> Regards,
>     Arno