[Ndn-interest] In-network name discovery -- Re: NDN protocol principles: no privacy?

[Dave Oran (oran)]

> On Mar 15, 2016, at 6:58 PM, Tai-Lin Chu <tailinchu at gmail.com> wrote:
> 
>>> And a note note.  It is not LPM! 
> 
> 
> This is a serious mistake from me. I apologize to everyone that is confused by it.
> 
>> If so, I don’t understand how you can design a non-terminating search algorithm unless you allow unbounded exclusion sets 
> 
> Could you explain more?
> 
Sure. Without some deterministic globally-agreed matching algorithm, each subsequent request for a name could return something longer or shorter and the only way to converge onto a useful name that can be used to aglrothmically construct the name you are looking for is to either:
a) keep adding exclusions until every possible name in existence in the tree above the desired name is excluded, leaving only the one you really want, or
b) ensure that any name which is a prefix of another name in fact resolves to a manifest or other data structure that enumerates the names underneath, so you can explicitly traverse the hierarchy.

If you can do (b), then you can effectively take the DNS approach of popping up to the root and navigating from there.

But NDN does not mandate that (b) always works.

>> The requirement for in-network discovery is in fact neither necessary NOR sufficient. If the network nodes that are doing this magic in fact have very small caches, or no caches at all (think a mesh sensor network with no large-memory nodes)
> 
> I acknowledge your point that in-network discovery is not necessary. However, I want to know about how one implements out-of-network discovery, and how this out-of-network discovery mechanism differs from ndn’s tree-based mechanism.
> 
Mark Mosko gave one example. My (b) above is another (albeit inefficient). There’s another consideration which also pushes one to having discovery services - application root of trust. It doesn’t do you any good to get able to pull random stuff out of router caches unless you can also pull out the necessary keying material to check the authenticity of the data. That means an application needs to have at least one built-in name and associated trust assertion to start navigating from: the name of the root of trust. If you can do that I would argue that the manifest tree approach to discovery can do everything else - the only thing you need a discovery service to hold in each network partition is the names and associated objects of each application root of trust that is in use in that network partition. Of course if the network is not partitioned, you can always get to the authoritative publisher of these objects, in which case in-network discovery is just an optimization like other forms of caching.

> Like I said, I think discovery protocol is very important to ndn (either in- or out-of-network). If we rely on some out-of-network service, and NDN becomes limited without it, we should probably remove “universality” as one of the principles because:
> 
> 1. we now need TWO or more protocols (need to include this discovery protocol, and perhaps many other supporting protocols) not one common protocol. In addition, a device needs to consider what kind of discovery protocol is available.
We need at least one upper level protocol on top of NDN to deal with trust schemas and keying.

> 2. it needs some infrastructure communication for discovery.
Which can be layered on NDN L3 just fine, so it doesn’t require some alternative L3 protocol.

> 
> This really devalues NDN.
> 
I disagree. While this is a highly imperfect analogy, the fact that IP today does not work in any practically useful way without DNS, I think it’s just fine for NDN (or CCN) to not work without a universally available discovery protocol built on top. From a implementation efficiency and simplicity point of view, if a very small volume of the communications need the discovery features, we can avoid some very expensive mechanisms in the forwarding path of the NDN routers.

> Although I am not a big fan of the current in-network discovery, I think it is wiser to improve it instead of removing it.
If we can find a way to improve it to the point it doesn’t add substantial complexity and performance problems, I’m all ears.

DaveO.

> 
> 
> 
> 
>> On Mar 15, 2016, at 12:11 PM, Dave Oran (oran) <oran at cisco.com> wrote:
>> 
>> 
>>> On Mar 15, 2016, at 10:58 AM, Alex Afanasyev <aa at CS.UCLA.EDU> wrote:
>>> 
>>>> 
>>>> On Mar 15, 2016, at 10:43 AM, <Ignacio.Solis at parc.com> <Ignacio.Solis at parc.com> wrote:
>>>> 
>>>> On 3/15/16, 9:11 AM, "Ndn-interest on behalf of Burke, Jeff" <ndn-interest-bounces at lists.cs.ucla.edu on behalf of jburke at remap.UCLA.edu> wrote:
>>>> 
>> [SNIP]
>> 
>>>> Can we have a clear example of where the in-network-layer name discovery is required and provides a benefit?
>>> 
>>> In order to support data retrieval **not only in infrastructure-based, always connected Internet**, but also in systems that can be infrequently connected (e.g., disaster environment, vehicular environments, some sensor networks, and many more example), you HAVE TO have the in-network discovery.  There is simply no way it is possible to have an "oracle" that can tell you what is there.
>>> 
>> I disagree.
>> The requirement is that within any partition of the network that needs to operate autonomously, there has to be a service instance that can answer bootstrapping/discovery queries. The requirement for in-network discovery is in fact neither necessary NOR sufficient. If the network nodes that are doing this magic in fact have very small caches, or no caches at all (think a mesh sensor network with no large-memory nodes) then in-network discover mechanisms will fail. Further, if in order to obtain an useful bootstrapping data you have to flood rather than route to a discovery service, there are some obvious scalability and DDoS concerns.
>> 
>>> I think Tai Lin in one of the previous emails correctly noted that with immutable data packets, it is simply impossible to not have in-network discovery.
>> We need a crisp definition  of an “immutable data packet” to continue this discussion productively. If the only immutable property is on hash-based names and you ONLY can request data by hash-name, then you have only immutable packets. On the other hand, if you can have different packets, with different hashes, that bind the same name (minus the hash) to different data, the useful application-meaningful data is not immutable. It’s also important to add time to the semantics here, such that applications may operatie correctly if and only if there is only one *unexpired* packet with a given name emitted by a publisher in a given expiration period.
>> 
>>> The communication will not work otherwise without having an out-of-band channel to tell you what to fetch.  What is the best way to achieve this is a completely different question.
>>> 
>>> And a note note.  It is not LPM!  It is fetching data with interests that don't have a full name (if needed with hash digest.
>> Actually, this is an interesting point. Are you saying you can return *ANY* prefix match? If so, I don’t understand how you can design a non-terminating search algorithm unless you allow unbounded exclusion sets (which might be needed in practice even *with* LPM).
>> 
>> 
>>> 
>>> ---
>>> Alex
>>> 
>>> _______________________________________________
>>> 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
>