Subject: [icnrg] Comments on FLIC

From: Ken Calvert <[email-masked]>
Date: Sun, 3 May 2020 18:29:03 -0400

I have reviewed draft-irtf-icnrg-flic-02.  Overall it is a very good and useful document.

Context: I came to the document with general knowledge of CCN/NDN and understanding of the manifest concept, but without knowledge of the details of any proposed implementation.  I approached it as if I were going to implement or use the protocol from scratch.  There may be relevant drafts I haven't read, which would affect my understanding.

Two parts to this: (I) high-level suggestions on presentation, and (II) corrections and nits.

I. High-level/global suggestions
-----------------------------------------

0. Define a consistent terminology early, giving the meanings in terms of BOTH CCNx and NDN standard terminology, and then use that throughout. Currently some terms are defined only in CCNx terms, while others need to be more precisely defined in standard terms.  I guess what I'm saying is the "Terminology" section 3.1 did not help me much.  Example: the relationship among Links, Locators, Namespaces, Names, and Prefixes all need to be made clear.  Some of this may be due to this draft not yet reflecting the RFC terminology.  (I'd volunteer to help with that, as it would help me understand the latter better.)

1. The inode analogy is useful in the document's abstract and introduction for giving some intuition, but it may not be helpful beyond that.  The term "pointer", for example, is a basic computer science concept, and could be defined without citing inodes.  In some places (Section 4 and Appendix A) the inode model does seem most appropriate, while in others (Section 3), trees seem like the more useful paradigm, but because I was expecting inode-like structure, it was confusing.

2. Section 2 is more like a list of features than a set of "Design Goals". Stating design goals is fine, but they should be formulated as such, rather than as selling points of the protocol.  (This would also help reviewers of the specification.)

3. Move the use cases (Sections 4.1, 4.3-4.5) earlier in the document.  The notation used is self-explanatory, and IMO illustrates the utility and flexibility of the design better than what comes before.  For example, the earlier sections give the impression that it is necessary (or at least usual) to have BOTH Root and Top manifests (i.e., two levels of indirection); the use cases show that this isn't required, but also how it can be useful.

4. Putting the section containing the grammar earlier in Section 3 might make the rest of that section easier to understand.  But I'm not sure - see also #0 above.

5. I think "preferred" should be avoided in a specification.  Better to state what an approach or technique is good for (and why!), and let the reader decide whether it applies to any particular case (see also #3 above). I also suggest avoiding "typical" unless the scope is clear.

II. Corrections/nits
--------------------

1. Introduction
  7th paragraph - the sentence "A FLIC manifest encodes locators the same for both ICN protocols, though they are encoded differently in the underlying protocol." is self-contradictory.  Suspect the first "encodes" should be something else. Is this sentence necessary?

3.1 Terminology
  Internal Manifest - last sentence, s/direct manifests/direct pointers/ .

3.3 Namespaces
  "If using namespaces, typically there are two defined: one for the manifest namespace and one for the application data namespace. If the two are the same, they can share a namespace."  This seems to be a tautology, although perhaps it's just semantic ambiguity about what "the two" refers to.

3.4 Manifest Metadata
2nd paragraph seems out of place - it's completely unclear what it has to do with the first paragraph, or with the section header.

3.7.1 Traversal
  "The algorithms in Figure 2 show the in-order forward traversal code ..." Actually the code shows preorder [sic] traversal; "in-order" is a different thing.

  Next-to-last line of reverse_preorder should be indented; the last line should not be indented.

3.8 - I did not go over this carefully.

3.9.1 and 3.9.2 - both contain, in places, sentences like: "The Root Manifest content object has a name used to fetch the manifest....It has a set of Locators used to fetch the remainder of the manifest."  This makes it seem like double-indirection is required. Should there be an "if any" or similar in there somewhere?

3.10 Figure 9 - Including this figure at this point is not very useful - the reader understands indirection by this point, and it just raises the question why you would want to require three-deep manifest retrievals and 55% overhead to get to the actual data.

4.2 Seeking

  "...how to compute the byte offset of the data pointed at by pointer P_i, offset_i.  In this formula, let P_i represent the Size value of the i-th pointer."
I think you mean to say "...by pointer P_i, *call it* offset_i" in the first sentence, then "let P_i.size represent..." in the second sentence.

In the formula "offset_i = \sum_{i=1}^{i-1} P_i.size",  RHS should be \sum_{k=1}^{i-1} P_k.size.

The code after the second paragraph is also wrong, the condition should be
   if (P < offset + P_i.size) ...
Also the code indentation is a little off.

Paragraph below Figure 13 is garbled, the P_i in the last sentence should be P_N, and the formula should be:

D - ((N-1) * L)

Then the sentence after that basically says the same thing again.  The algorithm seems right though.

4.5 Re-publishing a FLIC under a new name.

Second bullet - "would like a local result to appear."  - not clear what this means. Apparently here prefixes (/beta, /gamma) are being used as names of "sites". One gets the idea that there is some common understanding that some parts of the namespace are tied to topology.  If that's the case, can some documentation be cited?

Same paragraph, "maniest" -> manifest.

Appendix A - code for building trees - I think interior_direct() is not indented properly, should be at the same level as interior_indirect().

Also, the statement in interior_indirect():  "reserve_count = min(m, segment.tail - segment.head)" - I suspect that should be

reserve_count = min(k, segment.tail - segment.head)

When I worked an example with 100 data blocks, k=20 and m = 5, I got a top manifest with 5 direct pointers and 4 indirect pointers, the latter pointing to 2nd-level manifests with 20, 25, 25, and 25 direct pointers, respectively. The 5 direct pointers (when there is room for 20) seems to contradict the comment that "we want the top of the tree packed".  With the suggested change, I end up with 20 direct pointers and 4 indirect in the top manifest, with the 2nd-level manifests containing 5, 25, 25 and 25 direct pointers.

Ken

---

From: "Dirk Kutscher" <[email-masked]>
Date: Mon, 04 May 2020 12:09:20 +0200

Hi Ken,

thanks a lot -- this is really helpful. Would be great if we could 
consider these comments for a FLIC update.

> Context: I came to the document with general knowledge of CCN/NDN and 
> understanding of the manifest concept, but without knowledge of the 
> details of any proposed implementation.  I approached it as if I were 
> going to implement or use the protocol from scratch.  There may be 
> relevant drafts I haven't read, which would affect my understanding.

No, I don't think there are other relevant drafts that should have been 
read before other than the CCNx specs.

Thanks,
Dirk

> 0. Define a consistent terminology early, giving the meanings in terms 
> of BOTH CCNx and NDN standard terminology, and then use that 
> throughout. Currently some terms are defined only in CCNx terms, while 
> others need to be more precisely defined in standard terms.  I guess 
> what I'm saying is the "Terminology" section 3.1 did not help me much. 
>  Example: the relationship among Links, Locators, Namespaces, Names, 
> and Prefixes all need to be made clear.  Some of this may be due to 
> this draft not yet reflecting the RFC terminology.  (I'd volunteer to 
> help with that, as it would help me understand the latter better.)
>
> 1. The inode analogy is useful in the document's abstract and 
> introduction for giving some intuition, but it may not be helpful 
> beyond that.  The term "pointer", for example, is a basic computer 
> science concept, and could be defined without citing inodes.  In some 
> places (Section 4 and Appendix A) the inode model does seem most 
> appropriate, while in others (Section 3), trees seem like the more 
> useful paradigm, but because I was expecting inode-like structure, it 
> was confusing.
>
> 2. Section 2 is more like a list of features than a set of "Design 
> Goals". Stating design goals is fine, but they should be formulated as 
> such, rather than as selling points of the protocol.  (This would also 
> help reviewers of the specification.)
>
> 3. Move the use cases (Sections 4.1, 4.3-4.5) earlier in the document. 
>  The notation used is self-explanatory, and IMO illustrates the 
> utility and flexibility of the design better than what comes before.  
> For example, the earlier sections give the impression that it is 
> necessary (or at least usual) to have BOTH Root and Top manifests 
> (i.e., two levels of indirection); the use cases show that this isn't 
> required, but also how it can be useful.
>
> 4. Putting the section containing the grammar earlier in Section 3 
> might make the rest of that section easier to understand.  But I'm not 
> sure - see also #0 above.
>
> 5. I think "preferred" should be avoided in a specification.  Better 
> to state what an approach or technique is good for (and why!), and let 
> the reader decide whether it applies to any particular case (see also 
> #3 above). I also suggest avoiding "typical" unless the scope is 
> clear.
>
>
> II. Corrections/nits
> --------------------
>
> 1. Introduction
>   7th paragraph - the sentence "A FLIC manifest encodes locators the 
> same for both ICN protocols, though they are encoded differently in 
> the underlying protocol." is self-contradictory.  Suspect the first 
> "encodes" should be something else. Is this sentence necessary?
>
> 3.1 Terminology
>   "If using namespaces, typically there are two defined: one for the 
> manifest namespace and one for the application data namespace. If the 
> two are the same, they can share a namespace."  This seems to be a 
> tautology, although perhaps it's just semantic ambiguity about what 
> "the two" refers to.
>
> 3.4 Manifest Metadata
> 2nd paragraph seems out of place - it's completely unclear what it has 
> to do with the first paragraph, or with the section header.
>
> 3.7.1 Traversal
>   "The algorithms in Figure 2 show the in-order forward traversal code 
> ..." Actually the code shows preorder [sic] traversal; "in-order" is a 
> different thing.
>
> 3.9.1 and 3.9.2 - both contain, in places, sentences like: "The Root 
> Manifest content object has a name used to fetch the manifest....It 
> has a set of Locators used to fetch the remainder of the manifest."  
> This makes it seem like double-indirection is required. Should there 
> be an "if any" or similar in there somewhere?
>
> 3.10 Figure 9 - Including this figure at this point is not very useful 
> - the reader understands indirection by this point, and it just raises 
> the question why you would want to require three-deep manifest 
> retrievals and 55% overhead to get to the actual data.
>
> 4.2 Seeking
>
>   "...how to compute the byte offset of the data pointed at by pointer 
> P_i, offset_i.  In this formula, let P_i represent the Size value of 
> the i-th pointer."
> I think you mean to say "...by pointer P_i, *call it* offset_i" in the 
> first sentence, then "let P_i.size represent..." in the second 
> sentence.
>
> Paragraph below Figure 13 is garbled, the P_i in the last sentence 
> should be P_N, and the formula should be:
>
> D - ((N-1) * L)
>
> Second bullet - "would like a local result to appear."  - not clear 
> what this means. Apparently here prefixes (/beta, /gamma) are being 
> used as names of "sites". One gets the idea that there is some common 
> understanding that some parts of the namespace are tied to topology.  
> If that's the case, can some documentation be cited?
>
> Appendix A - code for building trees - I think interior_direct() is 
> not indented properly, should be at the same level as 
> interior_indirect().
>
> Also, the statement in interior_indirect():  "reserve_count = min(m, 
> segment.tail - segment.head)" - I suspect that should be
>
> When I worked an example with 100 data blocks, k=20 and m = 5, I got a 
> top manifest with 5 direct pointers and 4 indirect pointers, the 
> latter pointing to 2nd-level manifests with 20, 25, 25, and 25 direct 
> pointers, respectively. The 5 direct pointers (when there is room for 
> 20) seems to contradict the comment that "we want the top of the tree 
> packed".  With the suggested change, I end up with 20 direct pointers 
> and 4 indirect in the top manifest, with the 2nd-level manifests 
> containing 5, 25, 25 and 25 direct pointers.
>
> Ken
>
>
>
>
>
>
> _______________________________________________
> icnrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/icnrg