File-Like ICN Collections (FLIC)

3.1. Terminology

Data Object:

a CCNx nameless Content Object that usually only has Payload. It might also have an ExpiryTime to limit the lifetime of the data.¶

Direct Pointer:

borrowed from inode terminology, it is a CCNx link using a content object hash restriction and a locator name to point to a Data Object.¶

Hash Group:

KA collection of pointers. A Manifest should have atleast one Hash Group. A Hash Group may have its own associated meta data and Name Constructor.¶

Indirect Pointer:

borrowed from inode terminology, it is a CCNx link using a content object hash restriction and a locator name to point to a manifest content object.¶

Internal Manifest:

some or all pointers are indirect. The order and number of each is up to the manifest builder. By convention, all the direct manifests come first, then the indirect.¶

Leaf Manifest:

all pointers are direct pointers.¶

Locator:

A routing hint in an Interest used by forwarding to get the Interest to where it can be matched based on its Name Constructor-derived name.¶

Manifest:

a CCNx ContentObject with PayloadType 'Manifest' and a Payload of the encoded manifest. A leaf manifest only has direct pointers. An internal manifest has a mixture of direct and indirect pointers.¶

Manifest Waste:

a metric used to measure the amount of waste in a manifest tree. Waste is the number of unused pointers. For example, a leaf manifest might be able to hold 40 direct pointers, but only 30 of them are used, so the waste of this node is 10. Manifest tree waste is the sum of waste over all manifests in a tree.¶

Name Constructor:

The specification of how to construct an Interest for a Manifest entry.¶

Root Manifest:

A signed, named, manifest that points to nameless manifest nodes. This structure means that the internal tree structure of internal and leaf manifests have no names and thus may be located anywhere in a namespace, while the root manifest has a name to fetch it by.¶

Top Manifest:

One useful manifest structure is to use a Root manifest that points to a single Internal manifest called the Top Manifest. The Top manifest the begins the structure used to organize manifests. It is also possible to elide the two and use only a root manifest that also serves in the role of the top manifest.¶

3.2. Locators

Locators are routing hints used by forwarders to get an Interest to a node in the network that can resolve the Interest's name. In some naming conventions, the name might only be a hash-based name so the Locator is the only available routing information. Locators exist in both CCNx and NDN, though the specific protocol mechanisms differ. A FLIC manifest represents locators in the same way for both ICN protocols inside Name Constructors (Section 3.3), though they are encoded differently in the underlying protocol. See Section 3.9 for encoding differences.¶

A manifest Node may define one or more Locator prefixes that can be used in the construction of Interests from the pointers in the manifest. The Locators are inherited when walking a manifest tree, so they do not need to be defined everywhere. It is RECOMMENDED that only the Root manifest contain Locators so that a single operation can update the locators. One use case when storing application payloads at different replicas is to replace the Root manifest with a new one that contains locators for the current replicas.¶

3.3. Name Constructors

A Manifest may define zero or more name constructors in NameConstructorDefinitions (NCD) located in the Manifest Node. An NCD associates a Name Constructor Id (NCID) to a Name Constructor. The NCID is used in other parts of the Manifest to refer to that specific definition.¶

A manifest organizes pointers inside Hash Groups. Each Hash Group uses an NCID to indicate what Name Constructor to use to fetch the pointers inside the group.¶

NCID 0 is the default name constructor. If it is not defined in an NCD, it is assumed to be a HashNamingConstructor. A Manifest may re-define the default as needed.¶

A Manifest MUST use locally unique NCIDs in the NCD.¶

NCDs and their associated NCIDs are inherited as one traverses a manifest. That is, a manifest consumer must remember the NCDs as it traverses manifests. If it encounters a HashGroup that uses an unknown NCID, the RECOMMENDED action is to report a malformed manifest to the user.¶

A Manifest may update an NCID. If a child manifest re-defines an NCID, the manifest consumer MUST use the new definition from that point forward under that Manifest branch.¶

It is RECOMMENDED that only the root or similar top-level manifest define NCDs and they not be re-defined in subsequent manifests.¶

We expect that an application constructing a Manifest will take one of three approaches to name constructors. The advantage of using, or re-defining, the default name constructor is that any hash groups that use it do not need to specify an NCID and thus might save some space.¶

• A manifest might define (or use) a default name constructor and mix subsequent Manifest and Data objects under that same namespace. The manifest only needs to use one Hash Group and can freely mix Manifest and Data pointers.¶

• A manifest might define (or use) a default name constructor for subsequent Manifests and define a second NCD for the application data. This places all subsequent manifests under the default constructor and places all application data under the second NCD. The Manifest must use at least two Hash Groups.¶

  There are a few options on how to organize the Hash Groups:¶

  (1)

  Manifest Hash Group followed by Data Hash group,¶

  (2)

  Data Hash Group followed by Manifest Hash Group,¶

  (3)

  Intermix multiple manifest and data hash groups for interleaved reading, or¶

  (4)

  use a data-on-leaf only approach: the interior manifests would use the manifest hash group and the leaves would use the data hash group. Other organizations are possible.¶

• Define multiple NCDs for subsequent manifests and data, or not use the default NCD, or use some other organization.¶

In this specification, we define the following four types of Name Constructors. Additional name constructor types may be specified in a subsequent revision of the specification. Here, we informally define the name constructors. Section 3.6 specifies the encoding of each name constructor.¶

Type 0 (Interest-Derived Naming):

Use whatever name was used in the Interest to retrieve this Manifest, less a hash component, and append the desired hash value.¶

Type 1 (Data-Derived Naming):

Use the Manifest Name, less a hash component, as the Interest name, and append the desired hash value.¶

Type 2 (Prefix List):

The NCD specifies a list of 1 or more name prefixes. The consumer may use any (or all) of those prefixes with the desired hash appended.¶

Type 3 (Segmented Naming):

As in Type 2, but the consumer MUST track Segment Numbers. If the Hash Group provides Segment Number annotations for each pointer, it MUST use those numbers. Otherwise, the consumer MUST use a 0-based counter that follows the traversal order.¶

In Type 0, the consumer uses some name N to fetch a manifest. When the consumer receives the Manifest back, it begins issuing interests for the content using the same name N, but with the hash pointers from the manifest.¶

In Type 1, the consumer uses some name N to fetch a manifest. The consumer receives a manifest back with name M inside the Manifest Content Object. The consumer then uses the name M plus hash pointers from the manifest.¶

In Type 2, the consumer receives a manifest and begins traversing it. If it visits a Hash Group with a PrefixSchema Name Constructor, then that Name Constructor provides a list of 1 or more locators to use. The consumer may use any or all of the provided locators, plus the hash pointer, to fetch the contents.¶

In Type 3, if a Hash Group has a SegmentedSchema Name Constructor, then the consumer uses the same mechanism as Type 2, but with the addition of a Segment Number in the name. Segmented naming is only compatible with deterministic traversal orders or if the Manifest provides Segment Number annotations for each pointer. If the Hash Group provides hints about other traversal orders, then it must also provide Segment Number annotations for each prefix.¶

3.4. Manifest Metadata

The FLIC Manifest may be extended by defining TLVs that apply to the Manifest as a whole, or alternatively, individually to every data object pointed to by the Manifest. This basic specification does not specify any, but metadata TLVs may be defined through additional RFCs or via Vendor TLVs. FLIC uses a Vendor TLV structure identical to [RFC8609] for vendor-specific annotations that require no standardization process.¶

For example, some applications may find it useful to allow specialized consumers such as repositories (for example [repository]) or enhanced forwarder caches to pre-place, or adaptively pre-fetch data in order to improve robustness and/or retrieval latency. Metadata can supply hints to such entities about what subset of the compound object to fetch and in what order.¶

3.5. Pointer Annotations

FLIC allows each manifest pointer to be annotated with extra data. Annotations allow applications to exploit metadata about each Data Object pointed to without having to first fetch the corresponding Content Object. This specification defines one such annotation. The SizeAnnotation specifies the number of application layer octets covered by the pointer.¶

An annotation may, for example, give hints about a desirable traversal order for fetching the data, or an importance/precedence indication to aid applications that do not require every content object pointed to in the manifest to be fetched. This can be very useful for real-time or streaming media applications that can perform error concealment when rendering the media.¶

Additional annotations may be defined through additional RFCs or via Vendor TLVs. FLIC uses a Vendor TLV structure identical to [RFC8609] for vendor-specific annotations that require no standardization process.¶

3.6. Manifest Grammar (ABNF)

The manifest grammar is mostly, but not entirely independent of the ICN protocol used to encode and transport it. The TLV encoding therefore follows the corresponding ICN protocol, so for CCNx FLIC uses 2 octet length, 2 octet type and for NDN uses the 1/3/5 octet types and lengths (see [NDNTLV] for details). There are also some differences in how one structures and resolves links. [RFC8569] defines HashValue and Link for CCNx encodings. The NDN ImplicitSha256DigestComponent defines HashValue and NDN Delegation (from Link Object) defines Link for NDN. Section 3.9 below specifies these differences.¶

The basic structure of a FLIC manifest comprises a security context, a node, and an authentication tag. The security context and authentication tag are not needed if the node is unencrypted. A node is made up of a set of metadata, the NodeData, that applies to the entire node, and one or more HashGroups that contain pointers.¶

The NodeData element defines the namespaces used by the manifest. There may be multiple namespaces, depending on how one names subsequent manifests or data objects. Each HashGroup may reference a single namespace to control how one forms Interests from the HashGroup. If one is using separate namespaces for manifests and application data, one needs at least two hash groups. For a manifest structure of "MMMDDD," (where M means manifest (indirect pointer) and D means data (direct pointer)) for example, one would have a first HashGroup for the child manifests with its namespace and a second HashGroup for the data pointers with the other namespace. If one used a structure like "MMMDDDMMM," then one would need three hash groups.¶

TYPE = 2OCTET / {1,3,5}OCTET ; As per CCNx or NDN TLV
LENGTH = 2OCTET / {1,3,5}OCTET ; As per CCNx or NDN TLV

Manifest = TYPE LENGTH [SecurityCtx] (EncryptedNode / Node) [AuthTag]

SecurityCtx = TYPE LENGTH AlgorithmCtx
AlgorithmCtx = AEADCtx / RsaKemCtx
AuthTag = TYPE LENGTH *OCTET ; e.g. AEAD authentication tag
EncryptedNode = TYPE LENGTH *OCTET ; Encrypted Node

Node = TYPE LENGTH [NodeData] 1*HashGroup
NodeData = TYPE LENGTH [SubtreeSize] [SubtreeDigest] [Locators]
           0*Vendor 0*NcDef
SubtreeSize = TYPE LENGTH INTEGER
SubtreeDigest = TYPE LENGTH HashValue

NcDef = TYPE LENGTH NcId NcSchema
NcId = TYPE LENGTH INTEGER
NcSchema = InterestDerivedSchema / DataDerivedSchema /
           PrefixSchema / SegmentedSchema
InterestDerivedSchema = TYPE LENGTH [ProtocolFlags]
DataDerivedSchema = TYPE LENGTH [ProtocolFlags]
PrefixSchema = TYPE LENGTH Locators [ProtocolFlags]
SegmentedSchema = TYPE LENGTH Locators [ProtocolFlags]

Locators = TYPE LENGTH 1*Link
HashValue = TYPE LENGTH *OCTET ; As per ICN Protocol
Link = TYPE LENGTH *OCTET ; As per ICN protocol

ProtocolFlags = TYPE LENGTH *OCTET
                ; ICN-specific flags, e.g. must be fresh

HashGroup = TYPE LENGTH [GroupData] (Ptrs / AnnotatedPtrs)
Ptrs = TYPE LENGTH *HashValue
AnnotatedPtrs = TYPE LENGTH *PointerBlock
PointerBlock = TYPE LENGTH *Annotation Ptr
Ptr = TYPE LENGTH HashValue

Annotation = SizeAnnotation / SegmentIdAnnotation / Vendor
SizeAnnotation = TYPE LENGTH Integer
SegmentIdAnnotation = TYPE LENGTH Integer
Vendor = TYPE LENGTH PEN *OCTET

GroupData = TYPE LENGTH [NcId] [LeafSize] [LeafDigest]
            [SubtreeSize] [SubtreeDigest] [StartSegmentId]
LeafSize = TYPE LENGTH INTEGER
LeafDigest = TYPE LENGTH HashValue
StartSegmentId = TYPE LENGTH Integer

AEADCtx = TYPE LENGTH AEADData
AEADData = KeyNum AEADNonce Mode
KeyNum = TYPE LENGTH INTEGER
AEADNonce = TYPE LENGTH 1*OCTET
AEADMode = TYPE LENGTH (AEAD_AES_128_GCM / AEAD_AES_256_GCM /
           AEAD_AES_128_CCM / AEAD_AES_128_CCM)

RsaKemCtx = 2 LENGTH RsaKemData
RsaKemData = KeyId AEADNonce AEADMode WrappedKey LocatorPrefix
KeyId = TYPE LENGTH HashValue; ID of Key Encryption Key
WrappedKey = TYPE LENGTH 1*OCTET
LocatorPrefix = TYPE LENGTH Link

SecurityCtx:

information about how to decrypt an EncryptedNode. The structure will depend on the specific encryption algorithm.¶

AlgorithmId:

The ID of the encryption method (e.g. preshared key, a broadcast encryption scheme, etc.)¶

AlgorithmData:

The context for the encryption algorithm.¶

EncryptedNode:

An opaque octet string with an optional authentication tag (i.e. for AEAD authentication tag)¶

Node:

A plain-text manifest node. The structure allows for in-place encryption/decryption.¶

NodeData:

the metadata about the Manifest node¶

SubtreeSize:

The size of all application data at and below the Node or Group¶

SubtreeDigest:

The cryptographic digest of all application data at and below the Node or Group¶

Locators:

An array of routing hints to find the manifest components¶

HashGroup:

A set of child pointers and associated metadata¶

Ptrs:

A list of one or more Hash Values¶

GroupData:

Metadata that applies to a HashGroup¶

LeafSize:

Size of all application data immediately under the Group (i.e. via direct pointers)¶

LeafDigest:

Digest of all application data immediately under the Group¶

StartSegmentId:

If using¶

Ptr:

The ContentObjectHash of a child, which may be a data ContentObject (i.e. with Payload) or another Manifest Node.¶

3.7. Manifest Trees

 preorder(node)
    if (node = null)
       return
    visit(node)
    for (i = 0, i < node.child.length, i++)
       preorder(node.child[i])

reverse_preorder(node)
   if (node = null)
       return
   for (i = node.child.length - 1, i >= 0, i-- )
       reverse_preorder(node.child[i]) visit(node)

M0 ____
|      \
HG1    HG2
| \    |  \
M1 D2  D3  D4
|
HG3
|  \
D0 D1

3.8. Manifest Encryption Modes

This document specifies two encryption modes. The first is a preshared key mode, where the parties are assumed to have the decryption keys already. It uses AES-GCM or AES-CCM. This is useful, for example, when using a key agreement protocol such as CCNxKE [I-D.wood-icnrg-ccnxkeyexchange]. The second is an RSA key encapsulation mode (RsaKem [RFC5990]), which may be used for group keying.¶

Additional modes may be defined in subsequent specifications. We expect that an RSA KemDem mode and Elliptic Curve mode should be specified.¶

All encryption modes use standard encryption algorithms and specifications. Where appropriate, we adopt the TLS 1.2 standards for how to use the encryption algorithms. This section specifies how to encode algorithm parameters or ICN-specific data.¶

For group key based encryption, we use RsaKem. This specification only details the pertinent aspects of the encryption. It describes how a consumer locates the appropriate keys in the ICN namespace. It does not specify aspects of a key manager which may or may not be used as part of key distribution and management, nor does it specify the protocol between a key manager and a publisher. In its simpliest form, the publisher could be the key manager, in which case there is no extra protocol needed between the publisher and key manager.¶

While the preshared key algorithm is limited in use, the AES encryption mode described applies to the group key mechanisms too. The group key mechanism facilitates the distribution of the shared key without an on-line key agreement protocol like (the expired draft) CCNxKE [I-D.wood-icnrg-ccnxkeyexchange].¶

3.9. Protocol Encodings

ManifestContentObject = TYPE LENGTH [Name] [ExpiryTime]
                        PayloadType Payload
Name = TYPE LENGTH *OCTET ; As per RFC8569
ExpiryTime = TYPE LENGTH *OCTET ; As per RFC8569
PayloadType = TYPE LENGTH T_PAYLOADTYPE_FLIC ; Value TBD
Payload : TYPE LENGTH *OCTET ; the serialized Manifest object

5.1. Locating FLIC leaf and manifest nodes

The names of manifest and data objects are often missing or not unique, unless using specific naming conventions. In this example, we show how using manifest locators is used to generate Interests. Take for example the figure below where the root manifest is named by hash h0. It has nameless children with hashes with hashes h1 ... hN.¶

Objects:
manifest(name=/a/b/c, ptr=h1, ptr=hN)  - has hash h0
nameless(data1)                        - has hash h1
...
nameless(dataN)                        - has hash hN

Query for the manifest:
interest(name=/a/b/c, implicitDigest=h0)

After obtaining the manifest, the client fetches the contents. In this first instance, the manifest does not provide any Locators data structure, so the client must continue using the name it used for the manifest.¶

interest(name=/a/b/c, implicitDigest=h1)
...
interest(name=/a/b/c, implicitDigest=hN)

Using the locator metadata entry, this behavior can be changed:¶

Objects:
manifest(name=/a/b/c,
hashgroup(loc=/x/y/z, ptr=h1)
hashgroup(ptr=h2)             - has hash h0
nameless(data1)               - has hash h1
nameless(data2)               - has hash h2

Queries:
interest(name=/a/b/c, implicitDigest=h0)
interest(name=/x/y/z, implicitDigest=h1)
interest(name=/a/b/c, implicitDigest=h2)

5.2. Seeking

Fast seeking (without having to sequentially fetch all content) works by skipping over entries for which we know their size. The following expression shows how to compute the byte offset of the data pointed at by pointer P_i, call it offset_i. In this formula, let P_i.size represent the Size value of the i-th pointer.¶

offset_i = \sum_{k=1}^{i-1} > P_k.size

With this offset, seeking is done as follows:¶

Input: seek_pos P, a FLIC manifest with a hash group having N entries
Output: pointer index i and byte offset o, or out-of-range error
Algorithm:
offset = 0
for i in 1..N do
   if (P > offset + P_i.size)
      return (i, P - offset)
   offset += P_i.size
return out-of-range

Seeking in a BlockHashGroup is different since offsets can be quickly computed. This is because the size of each pointer P_i except the last is equal to the SizePerPtr value. For a BlockHashGroup with N pointers, OverallByteCount D, and SizePerPointer L, the size of P_N is equal to the following:¶

D - ((N - 1) * L)

In a BlockHashGroup with k pointers, the size of P_k is equal to:¶

D - L * (k - 1)

Using these, the seeking algorithm can be thus simplified to the following:¶

Input: seek_pos P, a FLIC manifest with a hash group having
                   OverallByteCount S and SizePerPointer L.
Output: pointer index i and byte offset o, or out-of-range error
Algorithm:
if (P > S)
   return out-of-range
i = floor(P / L)
if (i > N)
   return out-of-range # bad FLIC encoding
o = P mod L
return (i, o)

5.3. Block-level de-duplication

Consider a huge file, e.g. an ISO image of a DVD or program in binary be patched. In this case, all existing encoded ICN chunks can remain in the repository while only the chunks for the patch itself is added to a new manifest data structure, as is shown in the diagram below. For example, the venti archival file system of Plan9 [venti] uses this technique.¶

old_mfst -  - > h1 --> oldData1  <-- h1 < -  -  new_mfst
         \  - > h2 --> oldData2  <-- h2 < -  - /
          \            replace3  <-- h5 < -  -/
           \- > h3 --> oldData3              /
            \ > h4 --> oldData4  <-- h4 < - /

5.4. Growing ICN collections

A log file, for example, grows over time. Instead of having to re- FLIC the grown file it suffices to construct a new manifest with a manifest pointer to the old root manifest plus the sequence of data hash pointers for the new data (or additional sub-manifests if necessary).¶

old data < -  -  -  mfst_old <-- h_old -  - mfst_new
                                            /
new data1 <-- h_1 -  -  -  -  -  -  -  -  -/
new data2                                 /
...                                      /
new dataN <-- h_N -  -  -  -  -  -  -  -/

5.5. Re-publishing a FLIC under a new name

There are several use cases for republishing a collection under a new namespace, or having one collection exist under several namespaces:¶

• It can happen that a publisher's namespace is part of a service provider's prefix. When switching provider, the publisher may want to republish the old data under a new name.¶
• A publishes wishes to distribute its content to several repositories and would like a result to be delivered from the repository for consumers who have good connectivity to that repository. For example, the publisher /alpha wishes to place content at /beta and /gamma, but routing only to /alpha would not send a request to either /beta or /gamma. The operators of of /beta and /gamma could create a named and signed version of the root manifest with appropriate keys (or delegate that to /alpha) so the results are always delivered by the corresponding repository without having to change the bulk of the manifest tree.¶

This can easily be achieved with a single nameless root manifest for the large FLIC plus arbitrarily many per-name manifests (which are signed by whomever wants to publish this data):¶

data < - nameless_mfst() <-- h  < - mfst(/com/example/east/the/flic)
                                < - mfst(/com/example/west/old/the/flic)
                                < - mfst(/internet/archive/flic234)

This example points out the problem of HashGroups having their own locator metadata elements: A retriever would be urged to follow these hints which are "hardcoded" deep inside the FLIC but might have become outdated. We therefore recommend to name FLIC manifests only at the highest level (where these names have no locator function). Child nodes in a FLIC manifest should not be named as these names serve no purpose except retrieving a sub-tree's manifest by name, if would be required.¶