Subject: [icnrg] Manifest discussion - today at 5:40pm in Hilton cafe

From: <[email-masked]>
Date: Mon, 20 Jul 2015 10:36:44 +0000

All -

As mentioned during today’s ICNRG session, we’re holding a BOF to discuss Manifests for anyone who is interested.

When: Today (Monday, July 20th) at 5:40 pm
Where: Hilton cafe, mezzanine level

Hope you can join us!

Laura (and Nacho, Marc, Glenn & Glenn)

---

From: [email-masked]
Date: Mon, 20 Jul 2015 12:43:36 +0200 (CEST)

oh well, I'm already back in Basel ...

Hope that my writeup can influence the discussion, glad that I rushed in 
producing it.

best, christian

On Mon, 20 Jul 2015, [email-masked] wrote:

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

---

From: "Thompson, Jeff" <[email-masked]>
Date: Tue, 21 Jul 2015 08:24:05 +0000

Hi Christian,

One of the original motivations for a manifest to point to other "sub" manifests is that not all the hashes for a large file can fit in a one-packet manifest. (One packet so that it is only signed once.) But at the BOF meeting we discussed using existing mechanisms for signing multiple-packet content (Merkle tree signature, etc.) So you could have a manifest with a long list of hashes that span multiple packets, but only sign the manifest once. This might decrease the need to think of the manifest of a tree where each node or leaf is only once packet. What do you think?

- Jeff T

On 2015/7/20, 3:43, "icnrg on behalf of [email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]> on behalf of [email-masked]<mailto:[email-masked]>> wrote:

best, christian

On Mon, 20 Jul 2015, [email-masked]<mailto:[email-masked]> wrote:

All -

Hope you can join us!

Laura (and Nacho, Marc, Glenn & Glenn)
_______________________________________________
icnrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/icnrg

---

From: [email-masked]
Date: Wed, 22 Jul 2015 08:38:41 +0200 (CEST)

Hi Jeff,

so this list of hashes means a single-level, fat tree, right?

I see the following problem: How do you split the list of hashes with 
chunked manifests? I mean: is chunking ignoring inner datastructure 
boundaries (= usual chunking behavior) or respecting them (unusual)?

As a picture, first the "mercyless chunking":

--start-of-chunk-0
manifest {
   content {
     meta { ... }
     tableOfHashes {
       hash1,
       hash2,
       ha
--snip-and-start-of-chunk-1
manifest {
   content {
         sh3,
       hash4
     }
   }
}
--end-of-chunk-1

And now the packet-and-data-structure-aware chunked manifest of a fat 
tree:

--start-of-chunk-0
manifest {
   meta { ... }
   tableOfHashes {
     hash1,
     hash2
   }
}
--start-of-chunk-1
manifest {
   tableOfHashes {
     hash3,
     hash4
   }
}
--end-of-chunk-1

The latter case looks clean but is not easy to program and perhaps even 
unsuited: what if the meta section does not fit in a single packet? Then 
you have to do mercyless chunking, or have several individual meta 
sections (with each field having to fit in the remaining space of a 
packet). Having several self-contained meta sections spread over 
multiple chunk means that you have to collect all chunks before being 
sure to have seen all meta sections (or have a special 
"this-is-the-last-meta" tag), or force meta to be a link etc etc

Chunking is not only ugly at the nameing level - it also is ugly to 
program. Better have a clean packet-aware and chunk-numberless "byte 
container" solution for everything, including manifests with fat trees.

best, christian

On Tue, 21 Jul 2015, Thompson, Jeff wrote:

> Hi Christian,
> 
> One of the original motivations for a manifest to point to other "sub"
> manifests is that not all the hashes for a large file can fit in a
> one-packet manifest. (One packet so that it is only signed once.) But at the
> BOF meeting we discussed using existing mechanisms for signing
> multiple-packet content (Merkle tree signature, etc.) So you could have a
> manifest with a long list of hashes that span multiple packets, but only
> sign the manifest once. This might decrease the need to think of the
> manifest of a tree where each node or leaf is only once packet. What do you
> think?
> 
> - Jeff T
> 
> On 2015/7/20, 3:43, "icnrg on behalf of [email-masked]"
> <[email-masked] on behalf of [email-masked]> wrote:
>
> As mentioned during today’s ICNRG session, we’re holding a BOF
> to discuss Manifests for anyone who is interested.
>

---

From: David Oran <[email-masked]>
Date: Wed, 22 Jul 2015 13:45:07 +0200

As I mentioned in the discussion, an alternative to linear chunking of manifests is instead to keep each piece as an atomic content object and construct a tree of manifests signed using a Merkle tree signature over the whole thing.

We’re probably going to need hierarchical Manifests (or something similar) to describe collections of objects, so we’ll wind up needing tree traversal anyway…

DaveO.

> On Jul 22, 2015, at 8:38 AM, [email-masked] wrote:
> 
> Hi Jeff,
> 
> I see the following problem: How do you split the list of hashes with chunked manifests? I mean: is chunking ignoring inner datastructure boundaries (= usual chunking behavior) or respecting them (unusual)?
> 
> And now the packet-and-data-structure-aware chunked manifest of a fat tree:
> 
> --start-of-chunk-0
> manifest {
>  meta { ... }
>  tableOfHashes {
>    hash1,
>    hash2
>  }
> }
> --start-of-chunk-1
> manifest {
>  tableOfHashes {
>    hash3,
>    hash4
>  }
> }
> --end-of-chunk-1
> 
> The latter case looks clean but is not easy to program and perhaps even unsuited: what if the meta section does not fit in a single packet? Then you have to do mercyless chunking, or have several individual meta sections (with each field having to fit in the remaining space of a packet). Having several self-contained meta sections spread over multiple chunk means that you have to collect all chunks before being sure to have seen all meta sections (or have a special "this-is-the-last-meta" tag), or force meta to be a link etc etc
> 
> Chunking is not only ugly at the nameing level - it also is ugly to program. Better have a clean packet-aware and chunk-numberless "byte container" solution for everything, including manifests with fat trees.
> 
> best, christian
> 
>

---

From: <[email-masked]>
Date: Wed, 22 Jul 2015 12:41:29 +0000

Here’s an example of what I was trying to say at the table.  One can have a tree of manifests, but the manifests can be named sequentially too.  So, I could ask for an interest window of manifests and get all 3 manifests in 1 RTT.  Chunk 0 of the manifest still has the rolled-up signing.

— start
Name: /foo/bar.jpg/manifest/chunk=0
Prefix #1: /foo/bar.jpg/data, startChunk = 0
ListOfHashes (prefix # : object hash)
1: 0x1234 (chunk #0 of data stream)
…
1: 0x3443 (chunk #39)
0: 0xaaaa (chunk #1 of manifest stream)
0: 0xbbbb (chunk #2 of manifest stream)
Signature (supposedly with a key authorized for /foo/bar.jpg)

— start
Name: /foo/bar.jpg/manifest/chunk=1
Prefix #1: /foo/bar.jpg/data, startChunk = 40
ListOfHashes
1: 0x234234 (chunk #40)
…
1: 0x242345 (chunk #79)
No Signature

— start
Name: /foo/bar.jpg/manifest/chunk=2
Prefix #1: /foo/bar.jpg/data, startChunk = 80
ListOfHashes
1: 0x234234 (chunk #80)
…
1: 0x242345 (chunk #99)
No Signature

— data objects (no signatures)
Name: /foo/bar.jpg/data/chunk=0
Name: /foo/bar.jpg/data/chunk=1
Name: /foo/bar.jpg/data/chunk=...
Name: /foo/bar.jpg/data/chunk=99

Marc

> On Jul 22, 2015, at 1:45 PM, David Oran <[email-masked]> wrote:
>

---

From: [email-masked]
Date: Wed, 22 Jul 2015 19:44:59 +0200 (CEST)

Hi Marc,

so it seems that the driving force for you is getting as much packets 
with hash values as possible in the first round of requests, hence your 
interest in "linear chunking"/"fat tree".

(If I remember correctly from our interop I saw in the traces that you 
send six interests, regardless whether the requested object only is one 
packet long or not).

Do you have some rationale and target size in mind why three or six 
manifest packets in the first RTT would be benefitial? Why ask for so 
many hashes in advance? (a second RTT is needed anyway before you have 
actual content.)

Some back-of-the-envelope calulation on how far can you go with just one 
manifest packet:

Assume a 4KB manifest chunk, minus fixed header, name, signature, link 
to ACS, TLV overhead etc, leaves perhaps 3KB for the hash list.

Each hash with its TLV needs 36B, hence 85 hash values in the first 
packet. In your example you had 42 hashes (of course). Is 42 or 85 not 
enough?

best ,christian

On Wed, 22 Jul 2015, [email-masked] wrote:

> Here’s an example of what I was trying to say at the table.  One can 
> have a tree of manifests, but the manifests can be named sequentially 
> too.  So, I could ask for an interest window of manifests and get all 
> 3 manifests in 1 RTT.  Chunk 0 of the manifest still has the rolled-up 
> signing.
>
> — start

---

From: <[email-masked]>
Date: Wed, 22 Jul 2015 20:52:24 +0000

In the example I gave, the manifest stream is under a different chunked namespace than the data stream.  That was to illustrate the use of multiple names, not as a requirement.  I think it’s still an open question what is the right naming to balance performance, security, and and namespace design goals.

One could combine the manifests and content objects in to one chunked stream (the approach NDN manifests take, I believe), in which case one would get both manifests and data in one chunked namespace while still deriving the benefits of aggregated signing.

In regards to what is the right number to download in the first RTT, I don’t have an exact answer (see below for an example however).  Our stack does 6 as the initial interest window, but it is expecting 1500 byte chunks (maybe 1000 bytes of hashes or about 30 hashes), so that initial window is only for 9000 bytes.

There has not been much discussion of this yet, but when one switches to downloading based on hash name, one needs a good buffer of hashes to keep busy.  If you run out of hashes waiting for the next manifest the whole stream stalls.

Here’s an example of optimum window size (I’ve rounded some numbers so everything is generally +/- 1).  Let’s say you have a 50 msec RTT at 10 Mbps (1.25 MBps), you have a 62.5 KB BW-delay product.  If each content  object is 1500 bytes, then you have a 42 object pipe (or 16 at 4000 bytes).  If I can fit 30 hashes in a manifest, then I need a 1.4 manifests per RTT.  So, fetching 3 to start out with is not unreasonable.

The general approximate formula (assuming no loss and no congestion) then is:

CS = chunk size (bytes)
BDP = BW (KB/sec) * delay (msec)
HPM = hashes per manifest
manifests per RTT = floor(BDP / CS) / HPM
manifests per RTT = floor(62,500 / 1500) / 30 = 1.4

So I need 2 in one RTT then 1 in the next RTT, then 2 then 1, etc.

Marc

> On Jul 22, 2015, at 7:44 PM, [email-masked] wrote:
> 
> Hi Marc,
> 
> so it seems that the driving force for you is getting as much packets with hash values as possible in the first round of requests, hence your interest in "linear chunking"/"fat tree".
> 
> (If I remember correctly from our interop I saw in the traces that you send six interests, regardless whether the requested object only is one packet long or not).
> 
> Do you have some rationale and target size in mind why three or six manifest packets in the first RTT would be benefitial? Why ask for so many hashes in advance? (a second RTT is needed anyway before you have actual content.)
> 
> Some back-of-the-envelope calulation on how far can you go with just one manifest packet:
> 
> Assume a 4KB manifest chunk, minus fixed header, name, signature, link to ACS, TLV overhead etc, leaves perhaps 3KB for the hash list.
> 
> Each hash with its TLV needs 36B, hence 85 hash values in the first packet. In your example you had 42 hashes (of course). Is 42 or 85 not enough?
> 
> best ,christian
> 
>