Subject: [icnrg] CCNx Manifest Specification Draft

From: <[email-masked]>
Date: Sun, 19 Jul 2015 06:35:49 +0000

Hi folks:

Here is a preliminary draft of the CCNx Manifest specification. It covers the usage, design, and encoding of Manifests. Please be aware that all of these are subject to modification as our vision and goal of the Manifest is changed.

Nacho will be presenting slides based partly on this specification document as well as a future, more modular “manifest” data structure. The name of this new entity is still TBD. 

We believe the Manifest is a necessary construct for CCN and related ICN architectures. Consequently, we would greatly appreciate and welcome the community’s involvement in improving any elements of the specification. 

Regards,
Christopher Wood

---

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

Thanks, Chris for the manifest draft and also to Nacho for presenting 
yesterday so convincingly the case for them.

I would like to contribute by a simpler manifest concept, reducing to 
the max and resulting in a pure DAG data structure (directed acyclic 
graph): No chunk numbers, just hashes.

As was pointed out in the "manifest paper" by Baugher et al in 2012, 
this is the technique used in file systems like Venti, SFS and 
OceanStore. Also, I use the word "edge" instead of "links", to stress 
this even more.

A writeup of a simple DAG manifest follows. Looking forward to your 
comments!

Best, christian

---

I think that separating (a) the manifest packet from (b) the DAG data 
structure, helps in structuring and understanding the task of manifests.

Although puristic, I kept/included some features:
- sparse files
- simple compression: repeated content, zeros
- possibility to encrypt the graph structure
   (and avoiding that unauthorized network elements try to read such data)
- embedded content

One recommendation is that only manifest packets carry a name while the 
"data blocks" are name-less objects. These blocks either carry the 
content bytes or contain an array of hashes serving as edges. Using this 
type of edges eliminates chunk numbers, which to me seem overly complex 
to handle, as the corresponding paragraph in PARC's manifest draft 
demonstrates.

Without further introduction let's jump directly to the proposed packet 
structure, in NDN speak. Alternatively, below I provide an example for a 
more visual approach.

NDNpacket         ::= Interest | Data | NDNLP | Manifest |
                       DagLeaf | DagSha256Node | DagSha256EncrNode

Manifest          ::= MANIFEST-TYPE TLV-LENGTH  // "DAG manifest" packet
                         Name
                         ( DagSha256Node     // root of our SHA256-based directed
                         | DagSha256EncrNode // acyclic graph, possibly encrypted
                         | ... other manifest styles demuxed here
                         )
                         // "advanced" stuff, not part of this writeup
                         Meta? TableOfNames? HowToBuildTheNames?
                         HowToTraverseTheContent?
                         // the producer only signs this "inode" (manifest packet)
                         SignatureInfo
                         SignatureData

DagSha256Node     ::= DAG-SHA256-NODE-TYPE TLV-LENGTH  // "DAG node" packet
                         (DagSha256Edge | None | Zero | DagLeaf)+  // an array

DagSha256EncrNode ::= DAG-SHA256-ENCR-NODE-TYPE TLV-LENGTH
                         BYTES*

DagLeaf           ::= DAG-LEAF-TYPE TLV-LENGTH    // "DAG leaf" packet
                         BYTES*                    // aka "nameless object"

DagSha256Edge     ::= RepeatCount?
                       ( DagSha256DataDigest
                       | DagSha256NodeDigest
                       | DagSha256EncrNodeDigest )

RepeatCount       ::= REPEAT-COUNT-TYPE TLV-LENGTH
                         nonNegativeInteger

None              ::= NONE-TYPE TLV-LENGTH
                         nonNegativeInteger

Zero              ::= ZERO-TYPE TLV-LENGTH
                         nonNegativeInteger

DagSha256DataDigest ::= DAG-SHA256-DATA-DIGEST-TYPE TLV-LENGTH(=32)
                           BYTES{32}
                           // digest of a "DAG leaf" packet

DagSha256NodeDigest ::= DAG-SHA256-NODE-DIGEST-TYPE TLV-LENGTH(=32)
                           BYTES{32}
                           // digest of a "DAG node" packet

DagSha256EncrNodeDigest ::= DAG-SHA256-ENC-NODE-DIGEST TLV-LENGTH(=32)
                           BYTES{32}
                           // digest of an encrypted "DAG node" packet

Here is how DAG traversal (and ICN name construction) works: Starting 
from the manifest packet, take the name found inside the manifest and 
append the digests (in NDN, use maxsuffix=0) for fetching packets, or 
use the hash-restriction in case of CCNx. You will retrieve either a 
leaf of the DAG (=content bytes), or a non-leaf node of the DAG in which 
case you recurse depth-first. That is, the name found in the manifest 
packet "scopes" all hashes of the large object and serves as its routing 
hint.

This means that all packets for a large object have to come from the 
same prefix, which seems acceptable to me (over the option that large 
content objects can be served from a mix of different prefixes, as is 
envisaged in PARC's proposal). If you want to have multi-hosting, i.e. 
replicas visible at the application level, nothing prevents you to 
create multiple top-level manifest packets having different names but 
referring to the same digests. This would also be the way to go when 
using encrypted names (for protecting more than just the DAG structure).

The entry "None" is used to implement sparse files e.g., UNIX files with 
holes which can be used to represent core dumps. The integer value of 
such an entry indicates the size of the hole in bytes.

The entry "Zero" is used to compress long stretches of zeros. The 
integer value of such an entry indicates the stretch length in bytes.

I use "DagSha256" as a prefix for all data structure names in order to 
signal that another DAG edge encoding using e.g. SHA512 could be adopted 
in the future (needing another code point).

The DAG internal nodes and leafs are NDN packets needing no additional 
naming information (e.g. sequence number etc). This simple naming recipe 
is independent from the way manifest packets are named: A manifest can 
have a version number in its name and can be chunked, which also affects 
its name(s).

However, to keep the fetching of manifests simple, I suggest that (DAG) 
producers create manifests which fit in a single packet. This mimics the 
way that UNIX stores a file's inode in a single block. 
Single-packet-manifests can be obtained by using links towards other 
packets containing verbose metadata, for example. The goal is that a 
network element trying to read the DAG structure does not has to 
understand fancy name construction algorithms, even for the manifest 
packet itself.

Example

Imagine a large object that content-wise consists of six data blocks. 
Encoding-wise, this object is represented by five NDN packets, including 
the manifest. Note that the last block's bytes are embedded in the 
manifest packet and that the second to the forth block have identical 
content, hence they need only one leaf packet (and some entries in the 
DAG data structure) for their encoding.

The five packets are first shown in an informal data structure style:

Manifest {
   Name{ /a/b/c/d }
   DagSha256Node {
     DagSha256NodeDigest(hash=0x123)
     DagLeaf( DATABLOCK 6 )
   }
}

DagSha256Node { // has digest 0x123, is an array of edges
   DagSha256DataDigest(hash=0x456)
   repeat(3) DagSha256DataDigest(hash=0x789)
   DagSha256DataDigest(hash=0xabc)
}

DagLeaf { // has digest 0x456
   ... DATABLOCK 1
}

DagLeaf { // has digest 0x789
   ... DATABLOCK 2=3=4
}

DagLeaf { // has digest 0xabc
   ... DATABLOCK 5
}

The same example shown as an ASCII art diagram:

+----------+
| manifest |
+----------+
|DAG root: |
|   edge -----> +----------+
|   DATA6  |    | DAG node |
+----------+    +----------+
                 |   edge ----------------------------------> +----------+
                 |3x edge -------------------> +----------+   |  DATA1   |
                 |   edge ----> +----------+   |  DATA234 |   +----------+
                 +----------+   |  DATA5   |   +----------+
                                +----------+

Answering some of the design questions listed in PARC's draft:

1) I'm in favor of N-to-1 at the level of (advanced) manifest packets,
and 1:1 at the level of DAG packets.

2) The edge in the DAG data structure is always typed i.e. the hash
values for pointing to another DAG-internal node, or to a leaf node,
or to an encrypted DAG-internal node, are wrapped in separate TLVs.

3) The schema proposed here encodes just a tree without any traversal
assists. Shortcuts to specific leaf nodes, or offset tables etc, have
to be stored in auxiliary fields of the manifest packet, not in the
DAG nodes.

4) There is no support for sections and no length information in the
DAG nodes. See also answer 3.

The question to ask back: How would details about internal *sections*
of a large object be useful for most, if not all, network elements?
One can always add another layer of advanced manifests (listing
multiple sections) and let each section be completely and flatly
covered by the simpler DAG manifest.

However, making the total length an optional item in the DAG manifest
packet is useful. More specifically, I think that one should add the
length information to the *edges* (instead of inside the nodes) so
that one can skip the fetching of some sub-tree e.g., when
implementing a seek operation. [This is another indication that the
"edge" entry really is different from a "link"]. For privacy reasons,
length information should be optional rather than mandatory.

5) n.a.

Open issues:

In case of NDN: How will a signed interest for a manifest be handled?
Is removing the signature-related name components equivalent to using
the name in the manifest and will this match in the PIT and the CS?