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

[Arno Bakker <[e-mail]>]

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