[Ndn-interest] ccn-lite FLIC

Christopher.Wood at parc.com Christopher.Wood at parc.com
Mon Nov 23 11:00:41 PST 2015


Dear all, 

as a proof of concept, we have implemented FLIC manifests (File-Like ICN Collections) in ccn-lite: The code works for the NDN and CCNx1.0 encoding (but is not endorsed in any way). 

Please find some details and insights below and let us know your thoughts and comments! 

Best, 
Christian Tschudin and Chris Wood 

--- 

As a proof of concept, we implemented the FLIC manifest. 

FLIC stands for "File-Like ICN Collection", which is another word for 
"minimal manifests" or "immutable single objects". The implementation 
for ccn-lite is on GitHub under the "flic-manifest" branch, see 

  https://github.com/cn-uofbasel/ccn-lite/tree/flic-manifest 

** 
A preliminary specification for FLIC was also written but no longer 
matches the code. We are working on updating this draft ASAP so that 
everything is in sync. The writeup can be found at 

  https://github.com/tschudin/icn-llc-rfc 
** 

Our prototype consists of one program, ccn-lite-flic.c, that serves 
two purposes: 

a) Create chunks/segments out of a local file, writes them 
   to the file system 
   (Other programs can then serve/publish them to the ICN network: 
   in our case this is done by ccn-lite-relay.c) 

   - Approach: create a tree datastructure inside ICN content messages. 
     Leaf nodes are pure content nodes, tree-internal nodes are 
     called manifests. The top (root) manifest stands for the 
     whole data collection and serves as entry point. All nodes 
     are linked through (pointed at) via their SHA256 value. 

   - Only the root manifest has a name. All other data objects are 
     nameless and unsigned, including the sub-manifests. 

   - Signing of the root manifest also works, as was described in 
     Baugher et al. (Currently, ccn-lite only has HMAC256 signatures). 

   - We generate a "deep tree" i.e., a linear sequence of manifests. 
     Construction is "backwards" (leaf nodes and sub-manifests must 
     exist before we can point at them). 


b) Retrieve a FLIC via Interest/Content messages 

   Retrieval is via an object's hash value (ObjHashRestriction 
   selector for CCNx, implicit hash for NDN) except for the root 
   manifest which is retrieved via name. 

   The "tree traversal strategy" in our case degenerates into a 
   linear pass through the list. But the implemented algorithm can 
   handle any tree structure (or acyclic graph). 

We have tested our code, both for CCNx1.0 and NDN TLV encoding, for 
files up to a 1 GByte. Such a size results in almost 19'000 segments 
each being 64'000 Bytes long. The corresponding tree is 11 levels 
deep and each (sub-)manifest hosts up to 1777 pointers to other 
objects. 

In the case above, beside avoiding 19'000 signatures, the FLIC 
approach also saves 19'000 times the space for the name that would 
have to be put in each of these objects.  With a hypothetical name 
length of 60 (resulting in 80 code bytes), this is a savings of 
1.5 MBytes. With chunks being smaller than 4KB, this would become 
24 MBytes or more. 


FLIC Grammar: 

   ManifestMsg := Name? HashGroup+ 
   HashGroup   := MetaData? (DataPointer | ManifestPtr)+ 
   DataPointer := HashValue 
   ManifestPtr := HashValue 
   HashValue   := OCTET[32] 

   MetaData    := Property* 
   Property    := Locator | DataBlockSize | OverallDataSize | 
                  OverallDataSHA256Digest | ... 


Code complexity, rough figures 

ccn-lite-flic.c:  (total 950 LoC) 
   360 LoC  manifest tree creation incl signing 
   160 LoC  manifest tree retrieval incl signature checking 

   120 LoC  small packet compiler (s-expr to TLV) 
   100 LoC  encoding neutrality 
   210 LoC  cmd line parsing, misc 

Note: packet en-/decoding routines etc are pulled from a library. 
The core of ccn-lite also required 50 or so LoCs in order to support 
nameless objects (forwarding, CS matching, packet disassembler). 


Insights: 

- Code effort is low, especially for an in-network pre-cacher 
  that wants to collect a whole tree. 

- The degenerated tree (in form of a sequence of manifests) SHOULD 
  be mandated if the network is supposed to do pre-caching: 
  Only such a "deep tree" permits constant per-FLIC memory footprint 
  as we can use tail recursion (implemented in ccn-lite-flic.c) 

- We demonstrate a method that does not require chunk or 
  segment numbers (which would be different for CCNx and NDN): 
  all you need is the name of the root manifest to start with. 

- The debate is open regarding the use of ObjHashRestriction 
  in CCNx (or the implicit hash component in NDN) for retrieving 
  *named* objects - currently we restrict our work to nameless 
  objects, except for the root manifest. 

// eof 





More information about the Ndn-interest mailing list