Subject: [icnrg] Questions about an empty name segment

From: Atsushi Ooka <[email-masked]>
Date: Mon, 22 Oct 2018 19:23:40 +0900

Dear all.

I have some questions about an empty name segment
such as "ccnx:/NAME=" and "ccnx:/foo/bar/NAME=".

Why is an empty name segment needed, and how can it be used?

I have read Internet-Drafts (IDs) [1,2,3] and
confirmed the behavior of Metis [4] and iping [5];
however, it is not clear for me how to use them.

Thank you in advance.

Best regards,
Atsushi Ooka

[1] https://tools.ietf.org/html/draft-irtf-icnrg-ccnxmessages-08
[2] https://tools.ietf.org/html/draft-irtf-icnrg-ccnxsemantics-09
[3] https://tools.ietf.org/html/draft-mosko-icnrg-ccnxurischeme-01
[4] Metis (FD.IO sb-forwareder) https://wiki.fd.io/view/Sb-forwarder
[5] iping (FD.IO libicnet) https://wiki.fd.io/view/Libicnet

----------------------------------------------------------------------
Atsushi Ooka, Ph.D.

Network Science and Convergence Device Technology Laboratory,
Network System Research Institute,
National Institute of Information and Communications Technology (NICT)

E-mail: [email-masked]
Tel: +81-42-327-6847
URL: http://www.nict.go.jp
----------------------------------------------------------------------

---

From: <[email-masked]>
Date: Mon, 22 Oct 2018 18:32:54 +0000

Dr. Ooka,

Thank you for the question, as there are several important distinctions here.

=================
Definitions
=================

A Name has two primary use cases: (1) in a protocol message and in the PIT, (2) in an implementation’s FIB.

In case 1, the syntax of a Name is defined in the ABNF of [2], which correspond to the “exact” name concept (Sec 3 of [2]).  It identifies a specific content object, but not including the ConObjHash restriction (which would make it a “full” name).

In case 2, in the FIB, one wants the ability to specify the “prefix” name concept.  These specify a prefix of an exact name.

In a protocol message (case 1), the Name maybe (1.a) missing, (1.b) exactly 1 name segment, where the 1st name segment cannot be 0 length, or (1c) more than 1 name segment, where the 1st name segment cannot be 0 length, but any or all subsequent name segments could be 0 length.  In case 1.a, it is a so-called nameless object and processed as per the specs; note that here the name is missing, it is not a 0-length name.  In the PIT, the name is the same as it is in a protocol message (as the PIT records the protocol message’s name).

In the FIB in case 2, you can have (1.b) or (1.c) or a (2.a) 0-length name, or (2b) a 1-segment name with 0-length.  In case 2.a, this is considered the default route and would match any name.  In case 2.b, it is a typed default route and would match any name with a specific first name segment type.  In cases 1.b or 1.c, it works the obvious way.

In ccnxmessages, a 0-length name is defined as the NAME TLV with T = T_NAME, L = 0.  A 1-segment name with 0-length is (T = T_NAME, L = 4, V = (T = x, L = 0)), where x is some name segment type.

Note that in the specs we do not say how an implementation must encode a default route in its FIB.  We only specify how it is externally represented in the CCNX URI spec.  The actual value in the FIB or how the the implementation uses a default route is up to the implementation.  The default route, for example, could be in a separate data structure and only used if there’s no match in the FIB.

=================
Usage
=================

In an application (and thus in protocol messages), I do not think it is typical for a name segment to be empty, but this is a way to express a null value.  In CCNx 0.x, for example, a 0-length name segment was sometimes used because it was always short-lex sorted before any other value in the name segment.  Sometimes it used a 0-length name segment to represent the value “0” rather than encode a %00.  In CCNx 1.0 (the IETF spec), we steered away from this sort of usage because saving 1 byte was not considered as important as avoiding the confusion this sort of usage engendered.  Also, a competent compression scheme would fix the byte usage.  We preferred to encode a 0 as %00 and encode null as 0-length.

Here is a simple made-up example.  An application might have some application-defined name components where the name components might be “first_name” and “middle_name” and “family_name”.  Some people might not have a middle_name and in that case the application could represent null as a 0-length name component.  Another way to represent this would be to discard the middle_name name component.

Examples: 
ccnx:/name=foo/name=bar/name=my_app/APP:00=alice/APP:01=jane/APP:02=smith
ccnx:/name=foo/name=bar/name=my_app/APP:00=bob/APP:01=/APP:02=tucker

In a certain application, perhaps we use distinguished first name component types to distinguish a service, where we want different routing based on the _type_ of the name component, not the actual name.  For example, these two names should have different routing:

ccnx:/APP:00=gold/name=foo/name=bar => FIB prefix = ccnx:/APP:01=
ccnx:/APP:01=gold/name=foo/name=bar => FIB prefix = ccnx:/APP:01=

Note that we are routing on the name component _type_ not the _value_.

This same technique can also be used mid-way through the name, such as to distinguish between /NAME=foo/APP:00=silver and /NAME=foo/APP:01=silver.  

Marc

> On Oct 22, 2018, at 3:23 AM, Atsushi Ooka <[email-masked]> wrote:
> 
> Dear all.
> 
> _______________________________________________
> icnrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/icnrg

---

From: <[email-masked]>
Date: Mon, 22 Oct 2018 20:09:27 +0000

A minor correction, in the example

it should read, where the 1st FIB prefix is corrected to APP:00 from APP:01

ccnx:/APP:00=gold/name=foo/name=bar => FIB prefix = ccnx:/APP:00=
ccnx:/APP:01=gold/name=foo/name=bar => FIB prefix = ccnx:/APP:01=

Marc
________________________________________
From: icnrg [[email-masked]] on behalf of [email-masked] [[email-masked]]
Sent: Monday, October 22, 2018 11:32 AM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [icnrg] Questions about an empty name segment

Dr. Ooka,

=================
Definitions
=================

=================
Usage
=================

Examples:

Marc

---

From: Atsushi Ooka <[email-masked]>
Date: Thu, 25 Oct 2018 18:21:17 +0900

Dear Marc,

Thank you very much for your kind reply.
I mostly understand how to use a 0-length name, a 0-length name
component and nameless object.

Before your reply, I thought that T_APP TLV might be
application-dependent supplementary information, i.e., T_APP TLV might
be used by only applications and it might be ignored in matching
process in a router.

However, in my current understanding, T_APP TLV involves matching process.
Moreover, not only Value but also Type of name component are used in
the matching process.
If the type of 0-length name component in a FIB prefix is T_APP, the
FIB prefix acts as a typed default route.

Then, I have additional questions about the type of name component, as below.
I'd appreciate if you could answer the questions.
Thanks a lot.

(A) Is a T_NAMESEGMENT-type 0-length name segment possible on specifications?
     (Although it may not be typical and Metis [4] deletes such a name segment.)

(B) Which is correct about a FIB prefix with 0-length name component
that is NOT the 1st one? (e.g., "ccnx:/NAME=foo/APP:1=")
    (B.1) It acts as a typed default route against a name that has the
same prefix.
    (B.2) It acts as a typed wild-card that matches any name
components that has same type and is located in the same position.
        (e.g., Interest named "ccnx:/NAME=foo/APP:1=hoge/APP:2=fuga"
matches FIB prefix "ccnx:/NAME=foo/APP:1=/APP:2=fuga".)
    (B.3) The name component acts as null value and the FIB prefix
matches only a name that has the exactly same prefix.
        (i.e., Interest named "ccnx:/NAME=foo/APP:1=hoge" cannot match
FIB prefix "ccnx:/NAME=foo/APP:1=".)

(C) If (B.3) is true, is it assumed that a typed default route using
T_APP is used within only a local network?
    (This is because the 4096 types for T_APP seem to be too few
compared to the number of network applications all over the world.)

(D) If FIB has the prefix "ccnx:/NAME=", is it correct that only a
name with T_NAMESEGMENT-type 1st name component can match the prefix
and a name with T_APP-type 1st name component cannot match the prefix?

(E) The matching rule for T_ORG (organization specific) TLV is defined?
    In other words, does a incompatible router ignore the T_ORG TLV in
the matching process, or treat it as a normal name component?

Best regards,
Atsushi Ooka.

---

From: <[email-masked]>
Date: Thu, 25 Oct 2018 21:15:01 +0000

Dr Ooka,

You have another set of great questions.  I am going to reply in a more general form that I hope will answer all your specific questions.  I am going to do this at the Semantics level and not use any of the properties of the TLV encoding.  I will discuss what implications using the 2+2 TLV encoding has afterwards.  I also added a few in-line responses to your questions below.  It's a long reply email.

I will address the idea of the T_APP and T_ORG here.  A name component (aka path segment) is always evaluated regardless of type.  A forwarder does not need to understand any name components for forwarding, it can use memcmp() as explained below.  A forwarder is not applying any semantic knowledge about the type in forwarding [1].  An application, on the other hand, is applying some semantic meaning.  A FIB entry could, for example, include T_APP name components.  The reason we specifically carved out the T_APP type space is so applications can use name component types without worrying that a standardized value will overlap it.  One should expect that T_APP type space will overlap between applications.  

The same goes for T_ORG.  The forwarder does not care what the types are, they are compared as part of the name over the whole name.

Put more simply, the forwarder does not check the types of any name component.  It matches them as octet strings (or in C as uint16_t using the ccnxmessages encoding).  It matches all name components.

We expect the normal usage is to have a name like "/routable-prefix/app-id/app-dependent[/version][/chunk]", where /routable-prefix are the name components in the FIB, app-id identifies the app, and then the app-dependent use T_APP value as per the defined usage within app-id.  The trailing components might be a version id and a chunk identifier if using those optional name-based protocols.  That usage is not mandated. 

The IRTF spec does not explicitly allow name component type prefixing, i.e. ccnx:/name=foo/name= to be a prefix of ccnx:/name=foo/name=other.  The spec hints at it with the example URIs.  The Metis implementation does not allow type prefixing, it would only match two empty (0-length) name components as equal.

We structured the format of the Hop-by-hop Headers and  CCNx Message (the TLV part after the fixed headers) to require minimum structural schema validation.  You can put a T_ORG most anywhere and it will generally be skipped over by a non-conforming forwarder.  As the spec says "A T_ORG MAY be used as a path segment in a Name, in which case it is a regular path segment and is part of the regular name matching."  Because the name matching treats the V as an opaque octet string, they are matched as normal.

[1] some forwarders/caches/content stores may implement extra functionality that look a types, such as to prefetch chunks or look at versions.  This functionality, so long as not explicitly prohibited in the spec, can use whatever logic it wants and look at a name however it wants.

=====================
Name matching semantics
=====================

CCNx requires two operators on a name: equality "=" and is-prefix-of "<<" (in Metis it is metisTlvName_StartsWith(const MetisTlvName *name, const MetisTlvName *prefix)).  

One matches an Interest name (or a PIT entry) to a Content Object name with the equality operator (along with the other rules around content object hash restriction as per the spec).  One matches a FIB entry to an Interest name via the is-prefix-of operator.  Note that CCNx 1.0 does not require a less-than operator as there is no operation in the specs that requires sorting -- one may want to use one depending on data structures used in an implementation.  Metis, for example, defines a less-than operator using a short-lex definition (similar to CCNx 0.x).

A Name is an ordered set of name components (C_0, C_1, ..., C_j-1).  Each name component, C_i, is a tuple of two tokens (T_i, V_i) -- the type and value.  The type and value are octet strings we treat atomically (e.g. we don't need to worry if V_i is a substring of V_j, only if V_i equals V_j).  I will use the notation T(C_i) to mean the type of C_i and V(C_i) to mean its value.  The type must be non-empty while the value may be empty: |T| > 0 and |V| >= 0, where |x| means the length of x.

(1) For an octet string A and B, define the operator = the normal way: A and B are the same length and are byte-by-byte equal.

(2) For name components A and B, define the operator = as  "A = B <=> T(A) = T(B) and V(A) = V(B)".  T and V are octet strings.

(3 as per Metis) For name components A and B, define the operator << as "A << B <=> A = B".

(3 with type prefixing) For name components A and B, define the operator << as "A << B <=> T(A) = T(B) and (|V(A)| = 0 or V(A) = V(B))".

(4) For names A and B, define the operator = as "A = B <=> |A| = |B| and for i = 0...|A|-1: A[i] = B[i]" where |A| means the number of name components and A[i] means name component i of name A.

(5) For names A and B, define the operator << as "A << B <=> |A| <= |B| and for i = 0..|A|-2: A[i] = B[i] and for i = |A|-1: A[i] << B[i]".  Use the convention that if the range i...j does not exist (i.e. 0 .. -2) it evaluates to true.  If using 3 as per Metis, you can combine the two for loops and only use =.

Analysis:

Case (1) I will skip. It is the normal idea of equality of two octet strings.

Case (2) I will skip. It is the normal idea of equality of two structs.

Case (3 with type prefixing) has four sub-cases: (a) both non-zero length V, (b) A has 0-length V, B has positive length V, (c) A has positive length V, B has 0-length, and (d) both have 0-length V.  In all subcases the T(A) = T(B) clause is evaluated normally, as they must be non-zero length.  For all subcases, let us assume the types are the same.  In subcases (a) and (c), evaluate V(A) = V(B) as normal for octet strings.  If V(B) has 0 length, (c) will be false.  In subcase (b), the |V(A)| clause is true, so it will  match any V(B).  In subcase (d), two 0-length V's will match because the |V(A)| = 0 clause is true.

Some true examples, where I am making explicit the octet string nature of T and V.

(T={0x03}, V={0x01, 0x02}) << (T={0x03}, V={0x01, 0x02},
(T={0x01, 0x02}, V={}) << (T={0x01, 0x02}, V={0x00})
(T={0x01, 0x02}, V={}) << (T={0x01, 0x02}, V={})

Case (4) means that two zero-length names (having no name components) are equal.  For names with name components, they must be equal component-by-component.

Case (5) means that a zero-length name, A, is always a prefix of any other name because |A| <= |B| is always true and both for loops are empty and evaluate to true.  If the first name A is not empty, it must be equal to B up to the penultimate name component, and the final name component of A must be a prefix of the corresponding name component in B.

Some true examples.  I'll use strings here and denote an empty name component as {}.

((T=name, V={})) << ((T=name, V={}))
((T=name, V={})) << ((T=name, V=foo), (T=name, V=bar))
((T=name, V=foo)) << ((T=name, V=foo), (T=name, V=bar))
((T=name, V=foo), (T=name, V={})) << ((T=name, V=foo), (T=name, V=bar))
((T=name, V=foo), (T=name, V=bar)) << ((T=name, V=foo), (T=name, V=bar))
((T=name, V=foo), (T=name, V=bar)) << ((T=name, V=foo), (T=name, V=bar), (T=app:00, V=cat))

Some counter examples, where !<< means not-is-prefix-of.

((T=name, V={})) !<< ((T=name, V={}))
((T=name, V={})) !<< ((T=name, V=foo), (T=name, V=bar))
((T=name, V=foo)) !<< ((T=name, V=foo), (T=name, V=bar))
((T=name, V=foo), (T=name, V=bar)) !<< ((T=name, V=foo), (T=name, V={}))
((T=name, V=foo), (T=name, V=b)) !<< ((T=name, V=foo), (T=name, V=bar))
((T=name, V=foo), (T=name, V=bar)) !<< ((T=name, V=foo), (T=app:00, V=bar))

=====================
Implications of the 2+2 TLV
=====================

Because the 2+2 TLV does not admit any aliases, one can use memcmp().  That is, there is only one way to express a T value.  The NDN 1-3-5 format, for example, admits aliases so one must either validate that the shortest encoding is always used or use a different mechanism or define 0x00 is not the same as 0x0000 (e.g. does 0x00 == 0xFD0000?).  If one validates every T and V uses minimum encoding length, then you can use memcmp.

case (1) for octet strings A, B you can use memcmp() on the values the obvious way.

Case (2) for name components A and B), if L(A) = L(B), you can use memcmp(TLV_A, TLV_B, L(A)+4), where L(x) is the Length field of x and the +4 is because of the 4 bytes of T+L.  Doing it this way saves a branch in the C code because you do not need to check separately if T(A) = T(B).

Case (3 as per Metis) can be implemented as "if L(A) = L(B)  then return memcmp(TLV_A, TLV_B, LA(A)+4)==0 else return false" where TLV_x is a name component TLV.

Case (3 with type prefixing) can be rearranged to "if L(A) = 0 then return T(A) = T(B) else if L(A) = L(B)  then return memcmp(TLV_A, TLV_B, LA(A)+4)==0 else return false".

Case (4) can be implemented as "if L(A) = L(B) then return memcmp(TLV_A, TLV_B, L(A)+4) == 0 else return false", where TLV_x is the Name TLV (not a name component, those are in the Vs).  In Metis, where Metis_tlvName is the "V" portion of the name (i.e. the name component TLVs), it is implemented just as memcmp(V(A), V(B), |V(A)|) == 0.

Case (5) can use memcmp() in the obvious way in the two for loops based on the above cases.  In Metis, it is implemented as memcmp() on the name V's out to the length of the prefix, which it has already checked is less than or equal to B's V.

The default route works in Metis in (5) because POSIX memcmp says "Zero-length strings are always identical" so if the prefix is 0 length it will always memcmp to any other name.

Marc

________________________________________
From: Atsushi Ooka [[email-masked]]
Sent: Thursday, October 25, 2018 2:21 AM
To: Mosko, Marc <[email-masked]>; [email-masked]
Subject: Re: [icnrg] Questions about an empty name segment

Dear Marc,

I'm not sure what you mean by "on specifications" or where Metis deletes them.  Could you give an example of this?

In Metis it is B.3, though I would not call it a "null" value.  That is more of a semantic implication of 0-length.

As mentioned above, the T_APP name components are not expected to be unique _between_ apps.  One should use a name
that identifies the app then start using T_APPs.  Using T_APPs is optional, one could simply put it all in T_NAME name components and
use a command-marker like structure.

I would not expect T_APP name components to make it into the global FIB.  Whatever routing protocol is used should have rules about what is allowed.  We did not limit it in the packet format.

In a private network, one might use T_APPs in the FIB.  The packet spec tries to be as un-limiting as reasonable, but a particular instance and routing protocol should set sensible bounds.

If you allow type-prefixing then I think the answer to this is "yes".  See the examples and spec above.

As above, a forwarder does not care what the types are, it matches all name components (T, V) by (T, V).

Marc

Best regards,
Atsushi Ooka.

---

From: Atsushi Ooka <[email-masked]>
Date: Wed, 31 Oct 2018 17:25:14 +0900

Dear Marc,

Thank you very much for your perfect explanation.
That is so helpful that all my questions about the IRTF spec are resolved.

> I'm not sure what you mean by "on specifications" or where Metis deletes them.  Could you give an example of this?

What I tried to mean is whether the IRTF specifications allow or
prohibit a T_NAMESEGMENT-type 0-length name segment; e.g.,
"ccnx:/NAME=foo/NAME=/NAME=bar". In my current understanding, the IRTF
spec allows it.

On the other hand, Metis deletes such a name segment. For example,
when I tried the command "add route con0 ccnx:/foo/NAME=/bar 10" in
metis_control, Metis registered the FIB prefix "ccnx:/foo/bar", where
the 0-length name segment is deleted. At first, this behavior confused
me.

More specifically, all T_NAMESEGMENT-type 0-length name segments
except for the last one are deleted as follows:

* input:"ccnx:/NAME=" => Metis: "ccnx:/NAME=" (not deleted)
* input:"ccnx:/foo/bar/NAME=" => Metis: "ccnx:/foo/bar/NAME=" (not deleted)
* input:"ccnx:/foo/NAME=/bar" => Metis: "ccnx:/foo/bar" (deleted)
* input:"ccnx:/NAME=/foo/bar" => Metis: "ccnx:/bar" (deleted; This
case is additionally explained below.)
* input:"ccnx:/foo/NAME=/NAME=/bar/NAME=/NAME=" => Metis:
"ccnx:/foo/bar/NAME=" (deleted)
* input:"ccnx:/foo/APP:1=/bar" => Metis: "ccnx:/foo/APP:1=/bar" (not deleted)
* input:"ccnx:/APP:1=/foo/bar" => Metis: "ccnx:/APP:1=/foo/bar" (not deleted)

As long as I confirmed the command via wireshark, the string "NAME="
is replaced by the empty string before sending the command to Metis.
If a user inputs "ccnx:/foo/NAME=/bar", then Metis seems to receive
"ccnx:/foo//bar", which contains double slashes. Thus,
"ccnx:/NAME=/foo/bar" is converted to "ccnx:/bar" because Metis
receives "ccnx://foo/bar" and "//foo" may be treated as "authority",
which is defined in Sec. 2.1. of [3].

> > (B) Which is correct about a FIB prefix with 0-length name component that is NOT the 1st one? (e.g., "ccnx:/NAME=foo/APP:1=")
> >     (B.1) It acts as a typed default route against a name that has the same prefix.
> >     (B.2) It acts as a typed wild-card that matches any name components that has same type and is located in the same position.
> >     (B.3) The name component acts as null value and the FIB prefix matches only a name that has the exactly same prefix.
> >         (i.e., Interest named "ccnx:/NAME=foo/APP:1=hoge" cannot match FIB prefix "ccnx:/NAME=foo/APP:1=".)
> >

Your detailed description is really helpful for the questions (B) and (C).
My understanding is as follows:
* (B.1) is allowed as type-prefixing although there is not explicit
description about type-prefixing in the IRTF spec.
* (B.2) is not allowed.
* (B.3) is implemented in Metis although Metis prohibits all
type-prefixing not only in the Case (B) but also in the Case (C).

> > (C) If (B.3) is true, is it assumed that a typed default route using T_APP is used within only a local network?
> >     (This is because the 4096 types for T_APP seem to be too few compared to the number of network applications all over the world.)
> >
> As mentioned above, the T_APP name components are not expected to be unique _between_ apps.  One should use a name that identifies the app then start using T_APPs.  Using T_APPs is optional, one could simply put it all in T_NAME name components and use a command-marker like structure.
>

The question (C) was because I could not distinguish type-prefixing
and exact matching (Metis's behavior). In fact, Type-prefixing and
exact matching are different and they are not used together.
In my understanding,
* If using type-prefixing, a typed default route is not limited to
4096 patterns. A typed default route can include the identifier of the
app before 0-length T_APP such as "ccnx:/NAME=foo/NAME=bar/APP:n=".
* Otherwise (e.g., if using Metis), the usage of a typed default route
is not allowed; i.e., "ccnx:/APP:n=" does not act as a default route
and it matches only "ccnx:/APP:n=".

> > (D) If FIB has the prefix "ccnx:/NAME=", is it correct that only a name with T_NAMESEGMENT-type 1st name component can match the prefix and a name with T_APP-type 1st name component cannot match the prefix?
> >
> >     In other words, does a incompatible router ignore the T_ORG TLV in the matching process, or treat it as a normal name component?
> >

I also sufficiently understand these answers.

Thanks a lot again for your answers.

Best regards,
Atsushi Ooka.

---

From: <[email-masked]>
Date: Wed, 31 Oct 2018 21:03:27 +0000

Dr. OOka,

Regarding (A): Ok, I understand.  This is a bug.  The first name segment is not allowed to be empty, so metis_control should reject it.  A subsequent name segment that is empty should be passed as empty and exactly matched in the FIB.

Regarding (B): yes, though I'd emphasize that in B.1 it is only one example in the spec that indirectly suggests type prefix matching.  The intent in the specs is to always match names component-by-component based on equality of the pair (Type, Value) and not do type prefix matching.  When I implemented Metis, type prefixing was a bridge too far, so maybe one has one's answer there.   

Regarding (C): Almost yes.  A content object cannot have an empty 1st name segment (if it has a name, not just a hash), so if you are not doing type prefix matching it makes no sense to have an empty 1st name segment in the FIB.

In summary, I think it is interesting to think about type prefix matching as it gives one some of the flexibility as exclusions did in CCNx 0.x.  With exclusions, one could match a name up to a name segment and then require that it be, for example, a version number or segment number.  Type prefixing in CCNx 1.0 could give some of that flexibility at the FIB level (which might not even be the right place for it).  It is not equivalent by any means.    I think one could experiment with it.  Type prefix matching also makes ambiguous how one would match a 0-length name component if that is what one actually wanted to do, which is a dilemma in using type prefix matching. 

Marc

On 10/31/18, 1:25 AM, "Atsushi Ooka" <[email-masked]> wrote:

    Dear Marc,

    

    

    

    

    Best regards,
    Atsushi Ooka.