[Nfd-dev] Please review the update of NDN-TLV spec, introducing implicit digest name component

[Alex Afanasyev]

On Oct 10, 2014, at 7:31 AM, Lan Wang (lanwang) <lanwang at memphis.edu> wrote:

> 
> On Oct 9, 2014, at 8:02 PM, Alex Afanasyev <alexander.afanasyev at ucla.edu> wrote:
> 
>> Hi all,
>> 
>> Quick background.  After many discussions, we concluded that it is important to amend current Name TLV definition,  to allow implicit digest component.  After this change, Interest that specify implicit digest, must use implicit digest component at the end of the Name in order for the forwarder/applications to consider it as implicit digest.  This explicit knowledge would allow us to simplify implementation of on-demand implicit digest calculation in NFD (with the old definition, there are several problems that prevented to implement this/significantly complicate implementation logic).
> 
> Can you elaborate a bit on the rationale?  The gerrit page doesn't offer much explanation or context.

There are two issues here:
- (correctness) Explicit definition of the digest algorithm, so it can be changed later without requiring any flag day
- (optimization) Simplification of the processing logic.

Let me elaborate on the second one.  We are assuming that the implicit digest will not be present in the majority of the Interests, therefore a lot of cpu cycles can be saved by calculating the digest only when needed.

With the old spec there are two issues of different importance:
- (not critical) it is not directly known when exactly Interest carries the digest.  

  One can guess that, but it would be just a guess. It would work most of the time, but can fail sometimes.  

- (critical) canonical ordering and selector processing.

  As it currently stays, implicit digest component has the same canonical ordering comparison rules as any other component.  Therefore, to guarantee that the selectors (especially, right/left child, exclude) are processed correctly, one must calculate digest before putting Data packet into the content store.

  Technically, we still can implement delayed digest calculation.  However, the implementation has to make sure that relevant packets in CS are re-indexed before processing relevant selectors (which is not trivial and we never end up implementing this).


Separating digest into a separate class, simplifies canonical ordering:  unique names without implicit digest and with implicit digest will be (should be) ordered the same.  When there are different Data packets with the same name (different implicit digest), then they may need to be reshuffled, but this is a special case.

Just a basic example.  The order without digest: 

(current spec)  /a; /a/b
(updated spec)  /a; /a/b

With the current spec, the with digest:

(current spec)  /a/b/<hash>; /a/<hash>
(updated spec)  /a/<hash>; /a/b/<hash>

--
Alex

> Lan
>> 
>> * * *
>> 
>> Please review the change to NDN-TLV spec: http://gerrit.named-data.net/#/c/1289/.  You can either leave comment in gerrit (+1 / -1) or give your feedback in this mailing list.
>> 
>> * * *
>> 
>> The change slightly redefines what NameComponent TLV is:
>> 
>> 
>>   Name ::= NAME-TYPE TLV-LENGTH NameComponent*
>> 
>>   NameComponent ::= GenericNameComponent |
>>                     ImplicitSha256DigestComponent
>> 
>>   GenericNameComponent ::= NAME-COMPONENT-TYPE TLV-LENGTH BYTE*
>> 
>>   ImplicitSha256DigestComponent ::= IMPLICIT-SHA256-DIGEST-COMPONENT-TYPE TLV-LENGTH(=32)
>>                                       BYTE{32}
>> 
>> 
>> - ``GenericNameComponent`` is a generic name component, without any restrictions on the content of the value.
>> 
>> - ``ImplicitSha256DigestComponent`` is an implicit SHA256 digest component and it is required to contain a value of 32 octets.
>> 
>> 
>> ---
>> Alex
>> 
>> 
>> _______________________________________________
>> Nfd-dev mailing list
>> Nfd-dev at lists.cs.ucla.edu
>> http://www.lists.cs.ucla.edu/mailman/listinfo/nfd-dev