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

From: Arno Bakker <[email-masked]>
Date: Mon, 2 Apr 2012 14:47:29 +0200

On 29/03/2012 14:56, Picconi Fabio wrote:
> Hi,
>
> So, a follow-up of what I said during the Paris meeting:
>
> 1) Regarding the content addressing mechanism, I think the mandatory
> solution should be one which is as simple as possible without
> compromising efficiency.

Hi all

the merits of bins are some efficiency gain (bins save 1 integer over 
(start,end) to address a range) and an overall more elegant design.

With bins there is one unit of addressing in the whole system that
is used for chunk availability maps, requesting data and for addressing 
the hashes inside the Merkle hash tree (MHT) needed for integrity 
protection. The Merkle hash tree is the best known solution for low 
latency integrity checking for video-on-demand and hence is proposed to 
be mandatory (see below).

With (start,end) and MHTs mandatory we need a new scheme to address the 
nodes in the tree, resulting two units in the system.

IMHO, Binary trees is 1st year computer science stuff ;o)

> 2) Regarding integrity checking,
>
> Since sign-all is *significantly simpler to implement* that
> Merkle-trees, and the group seemed headed towards making merkle-trees
> mandatory anyway, I would suggest making support for both mandatory,
> thus supporting low-delay applications.
>

I agree. For live streaming, sign-all and Wong-Lam's signining of Merkle 
trees are the two options to consider. Hence my proposal to add a 
reference to the Wong-Lam paper [DIGSIGFLOW] to Sec. 5 on Feb 14th. For 
video-on-demand, the Merkle hash trees as described in the draft are the 
way to go, IMHO, as they allow fast time-till-playback compared to e.g. 
BitTorrent's approach (=download all hashes beforehand)

CU,
      Arno

[DIGSIGFLOW] Chung Kei Wong and Simon S. Lam. "Digital Signatures for
Flows and Multicasts". IEEE/ACM Transactions on Networking,
Volume 7,  Issue 4, pp. 502-513, Aug 1999.
http://dx.doi.org/10.1109/90.793005

---

From: [email-masked]
Date: Mon, 9 Apr 2012 17:46:14 +0800

According pplive's paper, the unit of content advertisement and the unit 
of content transmission used by pplive are different. pplive uses 2MB-size 
chuck as the unit of content advertisement, and 1KB as the unit of content 
transmission.
Do we need to adopt this method to reduce MHT size and bitmap size?

> _______________________________________________
> ppsp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ppsp
> 

--------------------------------------------------------
ZTE Information Security Notice: The information contained in this mail is solely property of the sender's organization. This mail communication is confidential. Recipients named above are obligated to maintain secrecy and are not permitted to disclose the contents of this communication to others.
This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify the originator of the message. Any views expressed in this message are those of the individual sender.
This message has been scanned for viruses and Spam by ZTE Anti-Spam system.

---

From: Arno Bakker <[email-masked]>
Date: Tue, 10 Apr 2012 13:19:46 +0200

On 09/04/2012 11:46, [email-masked] wrote:
> of content transmission used by pplive are different. pplive uses 
> 2MB-size chuck as the unit of content advertisement, and 1KB as the unit 
> of content transmission.

Hi

the size of the Merkle Hash Tree (MHT) depends on the transmission unit.

Availability could be reported in larger units, as a way to compress the
map. But some variants of run-length encoding may work as well.
For example, note that people watch the content linearly in PPSP. So the
first part of the availability map will be filled, and is therefore
easily compressible. The current bin numbers (on-the-wire) and binmaps
(self-compressing data structure for storing a bitmap in-core) can
compress such ranges.

This maybe something to discuss in the usage guide, as the peer protocol
will support multiple chunk addressing schemes.

CU,
    Arno

---

From: zhangyunfei <[email-masked]>
Date: Thu, 12 Apr 2012 16:39:36 +0800

Hi all, 
     Please see inline. Thanks.

Yunfei

zhangyunfei

发件人： li.lichun1
发送时间： 2012-04-09 17:46
收件人： arno
抄送： ppsp; ppsp-bounces
主题： Re: [ppsp] Proposal to resolve Issue 10 + 13

According pplive's paper, the unit of content advertisement and the unit of content transmission used by pplive are different. pplive uses 2MB-size chuck as the unit of content advertisement, and 1KB as the unit of content transmission. 
Do we need to adopt this method to reduce MHT size and bitmap size?

> IMHO, Binary trees is 1st year computer science stuff ;o)
[Yunfei] 
Compared with range expression, Bin numbering and Binmap may has some inefficiency in some cases. For example,Peer A holds chunk #0,4,8,12, the binmap cannot be expressed by a bin number in higher layer, say, 1,3,7, etc.. In this case, the efficiency of MHT cannot be realized.So can we say that bin has merits of efficiency?

---

From: Arno Bakker <[email-masked]>
Date: Thu, 12 Apr 2012 10:51:01 +0200

On 12/04/2012 10:39, zhangyunfei wrote:
> /[Yunfei]/
> Compared with range expression, Bin numbering and Binmap may has some 
> inefficiency in some cases. For example,Peer A holds chunk #0,4,8,12, 
> the binmap cannot be expressed by a bin number in higher layer, say, 
> 1,3,7, etc.. In this case, the efficiency of MHT cannot be realized.So 
> can we say that bin has merits of efficiency?
> 

You are right that in some cases the compression doesn't work,
but in many it does. To avoid confusion consider this tree:

                           7
                          / \
                        /     \
                      /         \
                    /             \
                  3                11
                 / \              / \
                /   \            /   \
               /     \          /     \
              1       5        9       13
             / \     / \      / \      / \
            0   2   4   6    8   10  12   14

0-2, 0-6, 8-14, etc. can be expressed by a single bin (1,3,11 resp.)
4-10 cannot, as that range lies in two different subtrees, so that
requires 2 bin numbers (5+9).

CU,
    Arno

---

From: zhangyunfei <[email-masked]>
Date: Wed, 18 Apr 2012 15:00:15 +0800

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

BR
Yunfei

zhangyunfei

From: Arno Bakker
Date: 2012-04-12 16:51
To: ppsp
Subject: Re: [ppsp]回复: Re: Proposal to resolve Issue 10 + 13

                           7
                          / \
                        /     \
                      /         \
                    /             \
                  3                11
                 / \              / \
                /   \            /   \
               /     \          /     \
              1       5        9       13
             / \     / \      / \      / \
            0   2   4   6    8   10  12   14

CU,
    Arno

---

From: Arno Bakker <[email-masked]>
Date: Wed, 18 Apr 2012 09:31:26 +0200

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.

> 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

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: Wed, 18 Apr 2012 18:34:45 +0800

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

Hi Yunfei and all

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

[Yunfei] I need more time to reply on this:)

Regards,
    Arno