[Ndn-interest] NDN Application with CanBePrefix flag

Mosko, Marc <mmosko@parc.com> mmosko at parc.com
Fri Apr 26 13:45:17 PDT 2019


Back in the first CCN (0.x) there was a repository command for namespace enumeration [1].  The request was of the form "ccnx:/xxx/yyy/%C1.E.be" and the response of the form "ccnx:/xxx/yyy/%C1.E.be/%C1.M.K%00<public_key_of_responding_repository>/%FD<version>/%00".  Thus, the response is specific to a given repository and versioned, so theoretically one could return a consistent set.

Name Enumeration does not return any information about the name (i.e. is it a name space or object or both or size, etc.).  It is just a list of names.

It also, as you could see, used prefix matching to do the name discovery.  One would also need to use selectors to iterate over responses from multiple repositories (which could miss some if a lower key arrived after a higher key and your iteration didn't allow for that).

Back to what Christian was talking about, I think it would not be practical to do this on router caches, so it would become a repo function.  As a repo function, where one could have a very large number of names under a prefix, you need to use a cursor of some sort.  You could also have a large number of replicas of the repo, so trying to merge them would become, I think, difficult, unless the repos themselves supported a merged directory listing of available content (even if it is not local).

I think this gets to the more fundamental concept of is a repo authoritative or cooperative (not authoritative for all content).  If every replica of a repo is authoritative, then it can respond to every request (unlike the original name enumeration, where a repo would not answer an interest if it did not have the prefix, in the hopes that another repo might).  Then you do not need to worry about merging responses.  If replicas are cooperative then you push the labor onto the clients.  If you run a sync protocol between your repos (at least for the names, if not the objects), then you can have authoritative name enumeration (or any of Christian's functions) without them all involving a possibly large distributed function call.

Marc

[1] https://github.com/ProjectCCNx/ccnx/blob/master/doc/technical/NameEnumerationProtocol.txt

________________________________________
From: Ndn-interest <ndn-interest-bounces at lists.cs.ucla.edu> on behalf of christian.tschudin at unibas.ch <christian.tschudin at unibas.ch>
Sent: Friday, April 26, 2019 9:50 AM
To: David R. Oran
Cc: ndn-interest
Subject: Re: [Ndn-interest] NDN Application with CanBePrefix flag

On Fri, 26 Apr 2019, David R. Oran wrote:

>> 2. I wonder if you have any plans to remove CanBePrefix flag in the
>> near future.
>>
> I can’t speak for the NDN team, obviously (I’m not part of the
> project and work primarily on CCNx, not NDN), but since discovery is an
> important/necessary function in any ICN system, if CanBePrefix ever gets
> removed it would be because it’s replaced with something more powerful
> and/or efficient, like an explicit discovery protocol on top of
> exact-match in the basic forwarders.

named functions, perhaps? Many possible candidates come to mind
(selectors were function calls, after all):

   ndn0.3_interest("/some/path", canBePrefix=True) -->
      what programmers really would like to do:

      /nfn/ndn0.1/rightmost("/some/path")
      /nfn/unix/ls("/some/path")
      /nfn/unix/find("/some/path")
      /nfn/glob(/nfn/unix/ls("/some/path"), "*.pdf")
      /nfn/newest() -> /nfn/tail(/nfn/sort(/nfn/unix/ls("/some/path")),1)

But: the functions will be complex I think, and I doubt that they can be
pushed into/down the basic forwarder, even not for exact match.

An example of a simple but challenging case would be a RIB pointing to
two repos, both having registered for the same prefix. A 'LS' request
must be sent to both repos, and on the return path the results be
merged. Easier to do this with manifests, but then the merging "basic
forwarder" must sign the combined manifest. And then we have not talked
about parametrized LS, yet (e.g. merging sorted file lists ..., and
making the entries unique), meaning that the real work still is done
outside the forwarder, we have no in-network aggregation gain.

Back to your suggested discovery protocol: it would have to be super
simple. Here is an idea: fetch first and last entry (instead of full
list), which would have a much easier merging task and could efficiently
work for lexicographically as well as time- or size-sorted lists. I like
two-line responses (and CAR/CDR) - too bad I failed to apply it to this
post ;-)

best, c


On Fri, 26 Apr 2019, David R. Oran wrote:

> On 25 Apr 2019, at 21:49, 김학서 wrote:
>
>> Dear All,
>>
>> I am currently designing a NDN application with CanBePrefix flag.(by
>> using interest.setCanBePrefix(true))
>>
>> I know that CanBePrefix flag is defined in the packet03transition
>> plan, and it is used in NDN platform.
>> However, I understand that setting CanBePrefix flag for Interest
>> packet may cause performance degradation issues for PIT processing.
>>
> Well, in high-speed forwarder algorithms, compared to exact match it can
> cost an order of magnitude or more of forwarding throughput.
>
>> My Questions are following :
>>
>>
>> 1. What do you think about design of applications using CanBePrefix
>> flag? If necessary, Can I use it?
>>
> Sure, as long as you use it sparingly. The primary suede is to do
> discovery - to get the first access to a portion of you namespace. From
> there traverse data either by predicting their names from the schema, or
> (my preferred method) using Manifests.
>
>> 2. I wonder if you have any plans to remove CanBePrefix flag in the
>> near future.
>>
> I can’t speak for the NDN team, obviously (I’m not part of the
> project and work primarily on CCNx, not NDN), but since discovery is an
> important/necessary function in any ICN system, if CanBePrefix ever gets
> removed it would be because it’s replaced with something more powerful
> and/or efficient, like an explicit discovery protocol on top of
> exact-match in the basic forwarders.
>
>
>> Best Regards,
>> HS Kim
>> _______________________________________________
>> Ndn-interest mailing list
>> Ndn-interest at lists.cs.ucla.edu
>> http://www.lists.cs.ucla.edu/mailman/listinfo/ndn-interest
>
> DaveO
> _______________________________________________
> 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