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

[Arno Bakker <[e-mail]>]

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