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

From: Arno Bakker <[email-masked]>
Date: Wed, 9 May 2012 08:19:34 +0200

On 18/04/2012 12:34, zhangyunfei wrote:
> Hi Arno，
> Pls see inline.Thanks.

Hi all

this landed in my spam box, so sorry for the late reply. See inline.

> [Yunfei] This is what I worry about. We cannot assure that each time we 
> can request
> chunks in groups of powers of 2, as it's dependent on what the serving 
> peers have, which
> is hard to ensure that the number of available chunks being powers of 2. 

IMHO, chunks will be requested in powers of 2. First, one will likely
request more than 1 chunk at a time to be able to fill the pipeline from
sender to receiver (cf. delay-bandwidth product). Requesting 1K and then
waiting for it will not be efficient. Second, as we're computer
scientists we'll use base 2 (32K, 64K, etc) when using multiples ;o)

> 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.

CU,
    Arno

---

From: Arno Bakker <[email-masked]>
Date: Wed, 9 May 2012 09:02:24 +0200

> 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.

CU,
     Arno

---

From: zhangyunfei <[email-masked]>
Date: Thu, 10 May 2012 10:18:26 +0800

Hi Arno,
    I had an email on discussing the new issues derived from PPSP requirements you proposed in the mailing list several days ago. I am not sure if you received it correctly. If not, please check the spam box again.

BR
Yunfei

zhangyunfei

发件人： Arno Bakker
发送时间： 2012-05-09 14:19
收件人： zhangyunfei
抄送： ppsp
主题： Re: [Spam]回复: Re:[ppsp]回复: Re: Proposal to resolve Issue 10 + 13

Hi all

CU,
    Arno

---

From: Picconi Fabio <[email-masked]>
Date: Mon, 14 May 2012 17:52:27 +0200

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:[email-masked]]
> 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

---

From: zhangyunfei <[email-masked]>
Date: Tue, 15 May 2012 10:54:59 +0800

Hi Arno，
    Please see inline.

zhangyunfei

From: Arno Bakker
Date: 2012-05-09 15:02
To: [email-masked]
Subject: Re: [ppsp][Spam] 回复: Re:回复: Re: Proposal to resolve Issue 10 + 13

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
[email-masked]
https://www.ietf.org/mailman/listinfo/ppsp

---

From: zhangyunfei <[email-masked]>
Date: Tue, 15 May 2012 10:55:16 +0800

+1.

zhangyunfei

发件人： Picconi Fabio
发送时间： 2012-05-14 19:17
收件人： zhangyunfei; [email-masked]
抄送： ppsp
主题： RE: [ppsp] 回复: Re:回复: Re: Proposal to resolve Issue 10 + 13
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.
Fabio
 
From: [email-masked] [mailto:[email-masked]] On Behalf Of zhangyunfei
Sent: mercredi 18 avril 2012 12:35
To: [email-masked]
Cc: ppsp
Subject: [ppsp] 回复: Re:回复: Re: Proposal to resolve Issue 10 + 13
 
Hi Arno，
    Pls see inline.Thanks.
 
Yunfei

zhangyunfei
 
发件人： Arno Bakker
发送时间： 2012-04-18 15:31
收件人： zhangyunfei
抄送： ppsp
主题： Re:[ppsp]回复: Re: Proposal to resolve Issue 10 + 13
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.
 
[Yunfei] This is what I worry about. We cannot assure that each time we can request 
chunks in groups of powers of 2, as it's dependent on what the serving peers have, which 
is hard to ensure that the number of available chunks being powers of 2. 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.
 
> 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
[Yunfei] I need more time to reply on this:)
Note that a binmap is a novel data structure to efficiently store a
bitmap, which is not directly related to bin numbers.
 
Regards,
    Arno

---

From: zhangyunfei <[email-masked]>
Date: Tue, 15 May 2012 10:56:56 +0800

Same idea with Fabio.

zhangyunfei

发件人： Picconi Fabio
发送时间： 2012-05-14 23:52
收件人： [email-masked]
抄送： zhangyunfei; ppsp

[0-P]

[P+1,P+W] worst case
Bins: W/2 integers

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

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

Fabio

---

From: Arno Bakker <[email-masked]>
Date: Tue, 15 May 2012 09:55:01 +0200

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

---

From: Picconi Fabio <[email-masked]>
Date: Tue, 15 May 2012 15:04:36 +0200

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.

> 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
> 
> 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.
> >
> 
> of updates to the map to send. I.e. 3 chunks in your example. This
> means less overhead.
> 
> would
> > be interesting to do the average case analysis for the [P+1,P+W]
> > interval.
> >
>

---

From: zhangyunfei <[email-masked]>
Date: Wed, 16 May 2012 09:52:15 +0800

Hi Fabio, Arno and all,
     I have a thought on how to discuss the average case. Please discuss to see if it works.
     We may find in some measurement work to see the distribution of the chunks in the buffer (maybe in different phase, there are different distributions, e.g., the beginning, the normal play, after dragging, but I am not sure). In this case, the problem Fabio proposed is solved and we can get an analysis of the two schemes.

BR
Yunfei

zhangyunfei

From: Picconi Fabio
Date: 2012-05-15 21:04
To: [email-masked]
CC: zhangyunfei; ppsp
Subject: RE: Proposal to resolve Issue 10 + 13
I'm not sure I follow you.

Fabio

---

From: Picconi Fabio <[email-masked]>
Date: Wed, 16 May 2012 08:53:00 +0200

Yes, a quick simulation would shed some light on the average case. Now we need to find the time to do it. :-)
Fabio

From: zhangyunfei [mailto:[email-masked]]
Sent: mercredi 16 mai 2012 03:52
To: Picconi Fabio; [email-masked]
Cc: ppsp
Subject: Re: RE: Proposal to resolve Issue 10 + 13

Hi Fabio, Arno and all,

BR
Yunfei

________________________________
zhangyunfei

From: Picconi Fabio<mailto:[email-masked]>
Date: 2012-05-15 21:04
To: [email-masked]<mailto:[email-masked]>
CC: zhangyunfei<mailto:[email-masked]>; ppsp<mailto:[email-masked]>
Subject: RE: Proposal to resolve Issue 10 + 13
I'm not sure I follow you.

Fabio

---

From: Arno Bakker <[email-masked]>
Date: Wed, 16 May 2012 09:14:46 +0200

On 15/05/2012 15:04, Picconi Fabio wrote:
> 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).
>

Hi

I think we agree that the overhead of both solutions is small even worst 
case. I just added a level of detail to make sure we didn't miss 
anything given UDP induces a chunksize of 1K, to be transmitted in 
groups for bandwidth utilization and optimal sharing (your ref).

The only difference is that I prefer bins such that there is a single 
unit in the whole system that works conveniently with Merkle hash trees.

CU,
      Arno

---

From: zhangyunfei <[email-masked]>
Date: Thu, 17 May 2012 11:30:35 +0800

Yes. It would be great if we can have a conclusion before next next week, when is our proposed deadline for discussing the chunk addressing issue.  

BR
Yunfei

zhangyunfei

From: Picconi Fabio
Date: 2012-05-16 14:53
To: zhangyunfei; [email-masked]
CC: ppsp
Subject: RE: RE: Proposal to resolve Issue 10 + 13
Yes, a quick simulation would shed some light on the average case. Now we need to find the time to do it. :-)
Fabio

Hi Fabio, Arno and all,
 
BR
Yunfei

zhangyunfei
 
From: Picconi Fabio
Date: 2012-05-15 21:04
To: [email-masked]
CC: zhangyunfei; ppsp

 
 
Fabio