Subject: Re: [ppsp] [decade] Object naming in -req and -arch

From: "Y. Richard Yang" <[email-masked]>
Date: Tue, 10 Jul 2012 13:23:05 +0800

Hi Peng, Dirk,

I am cc'ing the ppsp list as well. You raised a good point on the
distinction between one object and a sequence of objects. To generalize, we
can discuss even a set of objects (no ordering), and a set of equivalence
objects (dynamic streaming that interleaves different resolutions). Your
arguement against MTH is higher overhead in the general case (end to end
arguements). How much exactly is the overhead? Decade may benefit from the
analysis from ppsp. Since streaming is considered as the main app, how much
overhead if decade has to build on top?

Thanks!

Richard

On Tuesday, July 10, 2012, Peng Zhang wrote:

> Hi Dirk and all,
>
> I agree that the NI specification meets the basic requirement of DECADE
> (without optimization on "early name generation").
>
> As for the Merkle Hash Tree, or MTH, it is a integrity-assurance method
> for a sequence of objects. It is critical to the PPSP protocol. But i
> wonder wether we should incorporate it in our design:
>
> First, DECADE is targeted at general content distribution applications,
> and for applications other than P2P streaming, there is no great value of
> using Merkle Hash Tree. It may cause high overhead to these applications
> due "meta data" including signatures and full hashes should be exchanged.
>
> Still, we can discuss more on how to better incorporate PPSP based on NI
> without hurting the general application of DECADE. Thanks.
>
> B,
>
> Peng.
>
>
> On Jul 9, 2012, at 12:35 PM, Dirk Kutscher wrote:
>
> Hi Peng and all,****
> ** **
> Thanks for the discussion.****
> ** **
> So, I think it’s good to check the requirements and assess
> draft-farrell-decade-ni accordingly. I personally that it meets the ones
> you listed in your earlier message.****
> ** **
> One of the interesting features is that the NI specification defines a
> common format that enables the integration of hashes (or other
> cryptographic functions’ output) into names and corresponding validation
> steps on nodes. The explicit signaling of the function that is actually
> used allows for application-specific usage (if so needed) and for some
> agility regarding crypto algorithms. A DECADE protocol specification could
> specify the usage of the scheme, MANDATORY to implement algorithms etc more
> specifically.****
> ** **
> One of the, IMO, important things that have not been discussed
> sufficiently is the question about PPSP compatibility that Richard Yang
> brought up.****
> ** **
> My view on this is as follows: the PPSP Merkle Hash Tree approach for
> static and live content has requirements on the **object** and **meta-data
> ** format.  For example, chunks have to carry sibling and uncle hashes.
> Specifically, for live streaming with dynamic trees, chunks have to provide
> chunk signatures (block signature, chunk position in the block, and the
> digests of the sibling to the way to the root).****
> ** **
> For both static object and live streaming with
>
>

---

From: Arno Bakker <[email-masked]>
Date: Tue, 10 Jul 2012 09:49:16 +0200

Hi all

I'll try to clarify the rationale and practical overhead of the Merkle 
Hash Trees in PPSP. For static content, MHTs enable content integrity 
protection using self-certified naming. Using a hash tree instead of a 
single hash is useful in all situations where the content is distributed
in parts (=a sequence of objects as you mention it) that are immediately 
used. In particular, when the parts are delivered to a higher level app 
upon receipt they must be integrity checked beforehand. This applies to 
streaming, but perhaps also to other P2P apps using DECADE.

Even if parts are not immediately used, an integrity check on parts can 
help to improve efficiency in a P2P context. An end-to-end integrity 
check when the content is completely downloaded is sufficient, but for
efficiency it would be nice to know if the individual parts are correct
instead of finding out at the end, especially for large content.

Note that Merkle Hash Trees support both partial and end-to-end 
integrity checks. When a peer has a copy of the content and the name of 
the object (=its root hash in the MHT) he can calculate the MHT from the 
content and compare the calculated root hash to the name. He does not 
need to receive any of the intermediary hashes from others, if that is 
not required.

Which brings us to the topic of overhead. As discussed in Sec. 5.5 of
http://www.ietf.org/id/draft-ietf-ppsp-peer-protocol-02.txt
the size of the MHT depends on the number of chunks (objects) at the 
base of the tree. That number depends on the size of the chunks that are 
processed immediately in the P2P application. For PPSP over UDP over 
Ethernet these chunks are small. For other P2P apps the chunks may be 
bigger.

How much of the MHT tree actually needs to be sent over the wire to a 
receiving peer depends on the download policy used. For a linear 
download only part of the tree needs to be transmitted, as the other 
part of the tree is calculated by the receiving peer while downloading.
In the example in Sec. 5.5, only 7 of the 16 hashes in the tree are 
actually transmitted.

Note that swift, the protocol on which the PPSP peer protocol is based 
was actually designed as a generic transport protocol, unifying regular 
downloads, VOD and live streaming. So it still supports efficient 
non-streaming download policies like BitTorrent's rarest first. In other 
words, its origins fits the general distribution nature of DECADE.

Regards,
      Arno

On 10/07/2012 07:23, Y. Richard Yang wrote:
> distinction between one object and a sequence of objects. To generalize,
> we can discuss even a set of objects (no ordering), and a set of
> equivalence objects (dynamic streaming that interleaves different
> resolutions). Your arguement against MTH is higher overhead in the
> general case (end to end arguements). How much exactly is the overhead?
> Decade may benefit from the analysis from ppsp. Since streaming is
> considered as the main app, how much overhead if decade has to build on top?
>
> Thanks!
>
> Richard
>
>     I agree that the NI specification meets the basic requirement of
>     DECADE (without optimization on "early name generation").
>
>     As for the Merkle Hash Tree, or MTH, it is a integrity-assurance
>     method for a sequence of objects. It is critical to the PPSP
>     protocol. But i wonder wether we should incorporate it in our design:
>
>     First, DECADE is targeted at general content distribution
>     applications, and for applications other than P2P streaming, there
>     is no great value of using Merkle Hash Tree. It may cause high
>     overhead to these applications due "meta data" including signatures
>     and full hashes should be exchanged.
>
>     Still, we can discuss more on how to better incorporate PPSP based
>     on NI without hurting the general application of DECADE. Thanks.
>