[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