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

[Picconi Fabio <[e-mail]>]

I'm not sure I follow you.

First, I assumed three chunks per second because there is a paper that suggests that this is a good value [1]. But the actual chunk rate does not change the calculation (more chunks per seconds means both more bins and more ranges).

Second, if you use ranges, sending an update to inform the reception of an entire 32K block (i.e., 32 1K chunks) takes two integers with range lists, or one integer using bins. If you have three blocks per second, that means 6 integers per second per neighbor, instead of 3 integers per second per neighbor. In both cases the overhead is negligible.

In the absence of an average case analysis (i.e., where the buffer contains lots of holes) showing that bins are better than range lists, and given the negligible overhead of both solutions in the worst and best case, I would go for the simpler solution, i.e., range lists.

Fabio

[1] Size Does Matter (in P2P Live Streaming). N. Hegde, F. Mathieu and D. Perino. In Algotel'09 and also Inria Technical report #7032, 2009.




> -----Original Message-----
> From: Arno Bakker [mailto:[e-mail]]
> Sent: mardi 15 mai 2012 09:55
> To: Picconi Fabio
> Cc: zhangyunfei; ppsp
> Subject: Re: Proposal to resolve Issue 10 + 13
> 
> Hi Fabio and all
> 
> On 14/05/2012 17:52, Picconi Fabio wrote:
> >
> > 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.
> >
> 
> IMHO, the calculation should be somewhat different. It now assumes we
> send the complete 30 second map every second. I'd say it is more likely
> that we download at approx. the bitrate so we have only 1 seconds worth
> of updates to the map to send. I.e. 3 chunks in your example. This
> means less overhead.
> 
> With UDP as a transport, chunk size is preferably 1K to keep the impact
> of the loss of a single IP packet low (on Ethernet). Then 3 chunks per
> second should be 100 chunks per second for 1 Mbps, implying we send
> either 800 bytes (2 ints per range) or 400 bytes (1 bin) as overhead,
> worst case. For 10 neighbours this means 64 and 32 kbps, or 6% and 3%
> respectively.
> 
> 
> > 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.
> >
> 
> As argued before, I assume data will be requested in blocks of chunks,
> in particular on UDP with 1K chunks, which are a power of 2, e.g. 32K.
> We can align these requests on power-2 boundaries such that we need
> just
> 1 bin to address them. With ranges we always need 2 ints, as we're
> denoting a block of chunks.
> 
> With this block assumption, in the worst case, an update is (100K/block
> size) ranges. So e.g. 3 ranges for 32 K, taking either 2 or 1 int to
> encode, and thus implying 2 kbps and 1 kbps for 10 neighbours, or 0.2
> and 0.1% overhead. Less for larger block sizes.
> 
> In conclusion, if we send map updates instead of the full map, the
> absolute overhead of pushing chunk availability is low. Relative
> overhead can still be 100% and bins give a prettier one-unit design ;o)
> 
> CU,
>      Arno