Subject: [icnrg] Some clarifying points about FLIC

From: <[email-masked]>
Date: Mon, 25 Jan 2016 17:22:32 +0000

There were some questions about the FLIC block size at the interim 
meeting in Paris. We wanted to restate these questions on the mailing 
list and give our justification of the answers. See below for more 
details.

In general the confusion seemed to be based (a) on the name and usage of 
properties (like "block size") and (b) how they are inherited from child 
to parent manifests. 

FLIC chose the abstraction of the HashGroup (= set of pointers) to 
encapsulate properties that apply to all set members. As we show below 
they do introduce some subtleties in edge cases, but of modest 
complexity. 

Per-pointer descriptions are functionally equivalent to HashGroups. 
They do not have inheritance problems (because they do not offer 
inheritance) but come with a price: They are more costly in terms of 
space e.g., a size per pointer consumes more space than one size per 
HashGroup. 

FLIC optimizes for the common case: Because all data must be available 
at manifest creation time, encoding can be done with uniform properties 
(easily 10'000s of pointers in the case of a video) and parameters do 
not change often. Moreover, when inheritance does occur, separate 
HashGroups are used to isolate different properties. For example, when 
appending data to an already existing FLIC, one might want to use a 
different block size for the fresh data. Thus, a new HashGroup would be 
used to encapsulate the manifest tree with the different block size. 

Regarding the naming, we are considering renaming some terms in the FLIC 
specification. We agree that some terms like block size can be (have 
been) misleading. A better name would be "sub-tree application data 
size", or "content length per entry", together with "content length 
overall". Below, however, you will still find the old names. 

We are working on updating the FLIC specification to incorporate these
clarifying points. 

Best, 
Christian Tschudin and Christopher Wood 

--- 

Question: What does the FLIC block size actually represent? 

Answer: The FLIC block size is a property of a HashGroup and applies to 
all its entries except the last. It is a mere optimization to facilitate 
seeking but strictly speaking is not required for FLIC to work. For 
example, consider the following FLIC: 

M = (manifest 
      (hashgroup 
          (metadata 
              (blocksize=1K) 
              (totalsize=3K) 
          ) 
          (dataptr=h1) // D1 
          (dataptr=h2) // D2 
          (dataptr=h3) // D3 
       ) 
) 

In this case, we know that D1, D2, and D3 point to content of equal 
size (1K). Now consider another example: 

M = (manifest 
      (hashgroup 
          (metadata 
              (blocksize=10K) 
              (totalsize=21K) 
          ) 
          (manifestptr=h1) // M1 
          (manifestptr=h2) // M2 
          (dataptr=h3) // D3 
      ) 
   ) 

In this case, we know that M1 and M2 each contain 10K of application 
data, whereas D3 contains 1K of data. The block size concept is thus 
tightly linked to the way FLICs are produced by chunking data into 
pieces of identical size, except the last chunk for the remainder. 

--- 

Question: How can one quickly seek to a given position inside a large 
FLIC? 

Answer: Fast seeking (without having to sequentially fetch all content 
data) works by skipping over entries for which we know their size. 

It's simple, really. The byte offset of the data pointed at by pointer 
P_i (in a HashGroup with block size B and total size S) is computed as 
follows: 

   offset = (i * B) 

Recall that the total size of each pointer (except the last) is equal 
to the block size. (Again, this is part of the confusion, since "block size" seems 
to imply the size of a single node in a tree but is really the size of an entire 
sub-tree). If P_n is the last pointer in a HashGroup, its size is 
calculated as 

   size = S - ((n - 1) * B) 

Seeking is done as follows: 

Input: seek_pos P, a FLIC manifest with a HashGroup having 
       block size B, totalsize S and N entries 
Output: blockindex i and offset o, or out-of-range error 
Algo: 
   if (P >= S) 
      return out-of-range 
   i = floor(P / B) # seek_pos / block size
   if (i >= N) 
      return out-of-range # bad FLIC encoding 
   o = S - (i * B) 
   return (i, o) 

Note: If the pointer at position i is a manifest pointer, this algorithm 
has to be called once more, seeking to seek_pos o inside that manifest. 

--- 

Question: What purpose does the "totalContentHash" of a HashGroup serve? 

Answer: This is used for *content-addressable* queries. 

While preparing the FLIC manifest tree, the producer can compute the 
*content hash of the data* to be FLICed and put it in a metadata entry. 
Linux distros, for example, expose this value to check integrity. The 
content server can then offer to return (FLIC) objects based on their 
content hash, side-by-side with access through the hash of the root 
manifest (which might depend on arbitrary meta data). 

Note that content-addressable query is currently not supported at the 
forwarding level by either CCNx (CotentObjectHashRestriction) nor NDN (full 
name). However, it can be offered by a repository server at the name 
level, e.g., /some/provider/prefix/lookup-by-content/SHA256HASHOFCONTENT 

The ccn-lite-repo256 server implements such an interface. 

--- 

Question: Why bother having a redundant or unnecessary locator? 

Answer: The locator is an optional metadata entry and is not redundant. 
If we want the ability to create a FLIC which points to parts of data 
located at different sites, this is needed. Otherwise, each HashGroup 
would inherit the locator of its parent manifest and thus the data must 
be colocated together for the whole tree, which would be quite 
restrictive for concatenation purposes. 

// eof