[Ndn-interest] any comments on naming convention?

christian.tschudin at unibas.ch christian.tschudin at unibas.ch
Fri Sep 19 12:47:09 PDT 2014


Marc, thanks for that example and the routing comment, which reinforces 
my suspicion that we are trying to do too much, in too specific ways.

The writeup below is probably out of scope for the nameing convention 
and encoding debate, but might serve as a background for the goals of 
these marked components. In a nutshell: serializing marked components 
has built-in assumptions which might not hold in all cases, so 
alternatives should be considered, also encoding wise. I believe that in 
the forwarding architecture we should distinguish the 
"name-under-routing" (high-speed) from the 
"name-in-the-interest-or-data-object" (subject to slow path treatment), 
which are currently collapsed.

Analysis:

I write the semantics of your name
    /foo/bar/v1/<metadata marker>bibliography/v0/s0

in the usual object oriented way (this is encapsulate-to-the-left) as

    ((((/foo/bar).getVersion(1)).getMetadata(bibliography)).getVersion(0)).getSegment(0)

The problem is (looking from a named-function perspective) that each of 
these function invocations can happen anywhere, not necessarily where 
the /foo/bar data is.

Your Metadata example is insightful, because metadata really is a new 
object. If a computing center stores thumbnails on a different server 
than bibliography or legal copyright notices or the concerned object 
itself, and if you want to route on the metadata parameter ("thumbnail") 
instead of "bibliography" (or the name of the underlying object), you 
are in trouble: with LPM on the serialized name, this is not possible. 
Or you would have to inject metdadata routes for every possible version 
of the /foo/bar:

FIB:

/foo/bar/v --> rightFace

/foo/bar/v0/<metadata marker>bibliography --> leftFace
/foo/bar/v1/<metadata marker>bibliography --> leftFace
/foo/bar/v2/<metadata marker>bibliography --> leftFace
...

because with LPM, you cannot have something like:

/foo/bar/v --> rightFace
/foo/bar/v*/<metadata marker>bibliography --> leftFace


To continue the analysis, here is a writeup of the semantics in a more 
explicit form than the OO-syntax-sugar-way from above suggests:

name  how it is produced

#1  = /foo/bar
#2  = (#1.getVersion) (#1, 1)
#3  = (#2.getMetadata) (#2, bibliography)
#4  = (#3.getVersion) (#3, 0)
#5  = (#4.getSegment) (#4, 0)

Reading example: The getMetadata() function is specific to the version 1 
instance of the /foo/bar object - this function neither has to reside at 
the same place as the object itself nor does it have to 
produce/reference an object that resides at the same place. Note that 
three "parameters" are involved: the function name, the object name, and 
the 'bibliography' value. In order to produce intermediate result #4, 
you have to

- locate the function (its name is "#2.getMetadata")
- locate the data ("#2")
- find an execution place, to which you also provide the
   'bibliography' value

Potentially, all these three places are different.

But even if you claim that typically they are not, the result can be at 
another place: The location of result #4 in the metadata case could be 
different for 'thumbnails' than 'copyright' or 'bibliography': in fact, 
it could be anywhere on the planet (and was computed by the getMetadata 
function - there is no way to infer it from the elements in the original 
name).

So this comes back to my suspicion that every marker location 
potentially is a routing inflection point. If you intend to do routing 
decision on the flat (oo-way) encoding, and because only one /foo/bar 
name has been given, you restrict that retrieving and processing can and 
will happen only at a single place or in marker sequence. The problem 
really is that the names of intermediate results may point to other 
locations but are never spelled out while in general we have a 
name-rewriting situation.


Design options

This leads to different "solutions":

1) Impose a "locality doctrin": the stem name MUST be enough to locate
    that single place where object, the referenced functions, and
    any other object related data reside.

2) Ban "getMetadata()" and any other marker that potentially could
    lead to other locations than implied by the stem name (which cannot
    be captured by LPM). The getVersion() is probably safe because of
    the contextualization (a new chapter version will be the new context
    of an even newer section in the name tree, hence LPM is fine).

3) Separate 'name-under-routing' from 'name-in-the-message': It can be
    that some markers "rewrite" the routing target, hence we need a
    way of keeping the signed message intact but inform the forwarding
    that another name should be routed on. The use of the fixed
    header comes to mind:

    fixedHeaderMsg {
       . version, TTL, etc
       . name-under-routing = point to name in msg
       . optional headers
       . msg = interest(/foo/bar/v1/<metadata marker>bibliography/v0/s0))
    }

      -->

    fixedHeaderMsg {
       . version, TTL, etc
       . name-under-routing = point to name in optional headers
       . optional headers
           name-under-routing = /foo/bibliography-owner/v0/bar/v1/s0
       . msg = interest(/foo/bar/v1/<metadata marker>bibliography/v0/s0))
    }

    Or, for NDN, wrapping the message in another one:

    msg = interest(
             nameMangling(
               /foo/bibliography-owner/v0/bar/v1/s0,
               /foo/bar/v1/<metadata marker>bibliography/v0/s0
             )
          )

    Of course, rewriting/repointing is what named-functions need
    in order to work on a request by letting the network decide on
    the flow of processing through different locations. It seems to
    me that markers, especially getMetadata(), was already a step
    into named-function land.

4) If one feels uncomfortable with this rewriting at header level,
    the solution is to return a redirection back to the requestor,
    which would have to relaunch the query with the name it learned.
    This means that the packet format imposes edge-only processing,
    which could have easily been solved at the lower routing level:

    -> interest(/foo/bar/v1/<metadata marker>bibliography/v0/s0)))
    <- data("please visit /foo/bibliography-owner/v0/bar/v1/s0")
    -> interest(/foo/bibliography-owner/v0/bar/v1/s0)
    <- data(finally arrives and burned 20'000 miles)

Thanks, christian



On Wed, 17 Sep 2014, Marc.Mosko at parc.com wrote:

> As Tai-Lin’s example shows, there can always be multiple 
> encapsulations.  This is also very common for the “metadata” markers, 
> /foo/bar/v1/<metadata marker>bibliography/v0/s0, for example, where 
> the left name is encapsulated by a metadata object that describes it 
> via some second object.
>
> Christian’s question was specifically about a “core router”.  I 
> seriously doubt core routers would have FIB entries that go out to 
> application names or beyond as part of the ICN routing protocol. 
> That said, they might have some special internal or administrative 
> routes that include such things.
>
> Routers, beyond core routers, will have such routes when you get to 
> data centers or enterprises.
>
> Also, in some implementations, there is little difference between the 
> FIB and the PIT.  If I remember correctly, in the 0.x ccnd PIT names 
> were inserted in the same name tree as the FIB to find the LMP of a 
> content object on the reverse path, then walk up the name tree to find 
> all other possible matches for a returning content object.
>
> Marc
>
> On Sep 16, 2014, at 4:39 PM, Tai-Lin Chu <tailinchu at gmail.com> wrote:
>
>>> If not, then LPM for the forwarding can be constrained to the (encapsulated) untyped name components up to the first marker - all following bytes will not influence routing. PIT and CS is another story.
>>
>> I assume that it is up to and "not including" the first marker. What
>> you just said in my opinion limits the typed component to be placed in
>> the end of a name, and I don't think this limit will be good. For
>> example, /folder1/v1/file1/v2. According to your statement, file1 will
>> not influence routing, but I think it should.
>>
>>
>> IMHO, the only one requirement of allocating new types for typed
>> components is necessity. i.e. Will this typed component help upper
>> layer or router to process this packet differently (perhaps more
>> efficiently)?
>>
>>
>>
>>
>>
>> On Tue, Sep 16, 2014 at 3:56 PM,  <christian.tschudin at unibas.ch> wrote:
>>> Hi Marc,
>>>
>>> a question regarding the insightful encapsulation-to-the-left view (and
>>> taking up Tai-Lin's routing question):
>>>
>>> I see that demux is useful for end nodes where the applications are sitting.
>>> But are there important cases where core routers should demux, i.e. forward
>>> to different faces, based on that handful set of typed components we talk
>>> about?
>>>
>>> If not, then LPM for the forwarding can be constrained to the (encapsulated)
>>> untyped name components up to the first marker - all following bytes will
>>> not influence routing. PIT and CS is another story.
>>>
>>> best, christian
>>>
>>>
>>>
>>> On Tue, 16 Sep 2014, Marc.Mosko at parc.com wrote:
>>>
>>>> I am not sure why something being a typed name is related to routing.
>>>> Isn’t routing going to be over the full TLV representation of the name?  Or
>>>> do you consider the TLV “T” as separate from the name component and not used
>>>> in FIB or PIT matching?
>>>>
>>>> I think a serial version is more useful than a timestamp version.  In CCNx
>>>> 1.0, we have a type for both, but we generally use the serial version.  A
>>>> timestamp does not give distributed versioning, so like a serial version it
>>>> is only useful from a single publisher and it gives an easy way to determine
>>>> the next version.  It does, of course, require that the publisher maintain
>>>> state rather than rely on its real-time clock (or ntp) for its version
>>>> number.  A serial version number also allows unlimited version number
>>>> generation, whereas a quantized (e.g. milli-second) timestamp limits the
>>>> number of versions one can generate at a time without keeping state.
>>>>
>>>> As a general philosophy on named addresses, I see the hierarchical name
>>>> components as providing protocol encapsulation, essentially encapsulating
>>>> name components to the left (not all components are like this, but some
>>>> are).  For example, when you add a version component to a name it is a
>>>> statement that a versioning protocol has encapsulated and possibly modified
>>>> the content object identified by the left name. When a segmentation protocol
>>>> is applied to a content object, it encapsulates a name to the left.  They
>>>> serve a similar purpose to header encapsulation in traditional packets.
>>>> Therefore, I think that when a protocol is encapsulating the left-name,
>>>> those should be unambiguous and explicit.
>>>>
>>>> For protocols that everyone needs to understand, like versioning or
>>>> segmenting, those should be a standardized value, and not exclusive of other
>>>> protocols.  Someone might come out, for example, with a better segmentation
>>>> protocol and that should have a different identifier than the earlier
>>>> segmentation protocol.  Therefore, wherever you do your multiplexing you
>>>> need to coordinate.  That’s going to be either in the TLV “T” or in the
>>>> “key” of a “key=value” inside the “V”.
>>>>
>>>> Marc
>>>>
>>>> On Sep 16, 2014, at 10:21 AM, Tai-Lin Chu <tailinchu at gmail.com> wrote:
>>>>
>>>>> Summarize all types that people need (feel free to add some, and paste
>>>>> in your reply)
>>>>> - regular
>>>>> - segment
>>>>> - version (timestamp)
>>>>> - signature
>>>>> - key: assuming that the next regular component will be value. The
>>>>> value is empty if it sees another key component immediately after.
>>>>> - app-specific
>>>>>
>>>>>
>>>>> However, I am not convinced that we need version, signature, and
>>>>> app-specific as typed component. Will these change how packet routes?
>>>>>
>>>>>
>>>>>
>>>>> On Tue, Sep 16, 2014 at 8:47 AM, Junxiao Shi
>>>>> <shijunxiao at email.arizona.edu> wrote:
>>>>>>
>>>>>> Hi Jeff
>>>>>>
>>>>>> Please see my proposal of MarkedComponent
>>>>>>
>>>>>> <http://www.lists.cs.ucla.edu/pipermail/ndn-interest/2014-September/000085.html>,
>>>>>> which is a solution to eliminate ambiguity by defining a new type
>>>>>> specifically for key-value pair.
>>>>>>
>>>>>> Yours, Junxiao
>>>>>>
>>>>>> On Tue, Sep 16, 2014 at 8:18 AM, Burke, Jeff <jburke at remap.ucla.edu>
>>>>>> wrote:
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> Second, if the most important issue is eliminating ambiguity/aliasing,
>>>>>>> then why not define a new type that hints that the component can be
>>>>>>> interpreted as a key/value pair with some encoding convention?  This
>>>>>>> could
>>>>>>> enable an unambiguous, short list of commonly used conventions that
>>>>>>> you've
>>>>>>> mentioned (using marker-like keys),  while keeping information
>>>>>>> describing
>>>>>>> the data object in the name. It would also be very useful for
>>>>>>> applications
>>>>>>> that desire their own k/v representation for components, which Dave has
>>>>>>> argued for in other circumstances and we keep running across. It
>>>>>>> doesn't
>>>>>>> rule out use of hierarchy, and doesn't limit what an application
>>>>>>> defined
>>>>>>> keys could be.  Yet, it could be ignored in forwarding (just another
>>>>>>> component) and perhaps have a still-meaningful sort order (key, then
>>>>>>> value).
>>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> Ndn-interest mailing list
>>>>>> Ndn-interest at lists.cs.ucla.edu
>>>>>> http://www.lists.cs.ucla.edu/mailman/listinfo/ndn-interest
>>>>>>
>>>>> _______________________________________________
>>>>> Ndn-interest mailing list
>>>>> Ndn-interest at lists.cs.ucla.edu
>>>>> http://www.lists.cs.ucla.edu/mailman/listinfo/ndn-interest
>>>>
>>>>
>>>
>
>


More information about the Ndn-interest mailing list