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

From: Arno Bakker <[email-masked]>
Date: Thu, 12 Jul 2012 08:23:35 +0200

Hi Peng

On 11/07/2012 23:25, Peng Zhang wrote:
> Hi Arno,
>
> Thanks for the clarification. In my understanding, MHT over single hash
> can enable immediate integrity check before the whole media file is
> received, which is critical for streaming applications. But the client
> can also download hashes of every piece, just like in BitTorrent. Does
> it reduce a lot startup latency or server load by using MHT? Thanks.
>

The gains of using MHT depend on the chunk size. For PPSP we prefer 
chunks of 1K that fit in an UDP packet carried over Ethernet. In that 
case, for a 4 GB file, there are 4 M chunks, resulting in 80 MB of leaf 
hashes when SHA1 is used. Transferring that beforehand as in BitTorrent 
definitely increases latency ;o)

> For DECADE, It supports integrity check on piece/chunk level, so that
> client can verify that the received piece corresponds to the piece name.
> DECADE is unaware of what file this piece belongs to, and thus does not
> provide end-to-end integrity check. For file level, we leave the
> integrity check to applications. Thus, imo, we should not include MHT in
> the design of DECADE. But MHT can be built on top of DECADE, which means
> applications can still use MHT to implement integrity check for themselves.
>

You are right, if DECADE doesn't provide "links" between chunks, MHTs at 
the DECADE level make no sense. Using MHTs at the app level instead as 
you say does make sense and is easy, just build all the piece 
names/piece hashes into a tree.

Regards,
       Arno

---

From: Arno Bakker <[email-masked]>
Date: Fri, 13 Jul 2012 09:12:45 +0200

On 12/07/2012 22:28, Peng Zhang wrote:
>
> On Jul 12, 2012, at 2:23 AM, Arno Bakker wrote:
>
>> chunks of 1K that fit in an UDP packet carried over Ethernet. In
>> that case, for a 4 GB file, there are 4 M chunks, resulting in 80
>> MB of leaf hashes when SHA1 is used. Transferring that beforehand
>> as in BitTorrent definitely increases latency ;o)
> Yes, if the chunk size is only 1KB, and each chunk is verified
> individually, we cannot afford to send all hashes beforehand. While
> in the worst case without optimization, almost 2*80M = 160M hashes
> needs to be sent to the receiver, will that be a large overhead
> compared to 4G? Do we really need such a small chunk size? Maybe I
> miss some previous discussion on this.

Hi

For PPSP we want to use UDP as we don't need the in-order and 
reliability features of TCP, and want flexibility to use differnet 
congestion control algorithms and handle NATs. With Ethernet as the 
dominant MAC layer at present and an unreliable transport we don't want 
datagrams to exceed the Ethernet MTU, otherwise the chance of losing a 
datagram increases (an UDP packet taking N IP packets will not be 
delivered when only 1 IP packet is lost). Hence, we use chunks of ~1K.

A good practice in P2P networks is to not forward data you have not 
verified. So to forward the 1K chunks directly we need to be able to 
verify their integrity at this granularity, enter Merkle Hash Trees.
We think the resulting overhead due to the size of the tree is 
acceptable, as it is easy to optimize the number of hashes transmitted
in our use cases.

CU,
     Arno

---

From: Peng Zhang <[email-masked]>
Date: Thu, 12 Jul 2012 16:28:50 -0400

On Jul 12, 2012, at 2:23 AM, Arno Bakker wrote:

> The gains of using MHT depend on the chunk size. For PPSP we prefer chunks of 1K that fit in an UDP packet carried over Ethernet. In that case, for a 4 GB file, there are 4 M chunks, resulting in 80 MB of leaf hashes when SHA1 is used. Transferring that beforehand as in BitTorrent definitely increases latency ;o)
Yes, if the chunk size is only 1KB, and each chunk is verified individually, we cannot afford to send all hashes beforehand. While in the worst case without optimization, almost 2*80M = 160M hashes needs to be sent to the receiver, will that be a large overhead compared to 4G? Do we really need such a small chunk size? Maybe I miss some previous discussion on this.
> You are right, if DECADE doesn't provide "links" between chunks, MHTs at the DECADE level make no sense. Using MHTs at the app level instead as you say does make sense and is easy, just build all the piece names/piece hashes into a tree.
Yes, Exactly.

---

From: Songhaibin <[email-masked]>
Date: Thu, 19 Jul 2012 02:35:29 +0000

I know little about Merkle Hash Tree. So I searched and learned some from the Internet. My feeling is MHT is useful for pre-stored objects. But it is less useful for live contents. IMO, the co-relation of the objects besides naming the object itself adds extra complexity in DECADE environment. Or is there any good reason to use it?

Just my 2 cents,
-Haibin

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Arno Bakker
> Sent: Friday, July 13, 2012 3:13 PM
> To: Peng Zhang
> Cc: ppsp; decade
> Subject: Re: [decade] [ppsp] Object naming in -req and -arch
>