[Ndn-interest] Selector Protocol over exact matching

[Ignacio.Solis at parc.com]

On 10/3/14, 7:17 PM, "Burke, Jeff" <jburke at remap.ucla.edu> wrote:

>- Data names become about the query rather than about the data; this seems
>to be a fundamental design difference.  If the response to each interest
>includes a hash of the query, it can't be used to fulfill different
>queries that would have the same result. So some caching benefit is lost.
>(This seems like the basic tradeoff of exact match vs lpm+selectors.)

This is true only at the nodes that don’t speak the Selector Protocol.
The ones that do speak the protocol are free to decapsulate and use that
answer for other queries.


>- In the case where there are multiple publishers with different answers
>to the same selector protocol query, they would return different data for
>the same request.   In the current NDN case, this is disambiguated because
>the response includes the name of the data itself.  But in the selector
>protocol case, couldn't you have many answers to the question all sharing
>the same name?  

Yes.

However, in current NDN there is no requirement front he network for
responses to be unique.  A node can produce data D1, name it /a/b and sign
with key K1 and another node can produce data D2, name it /a/b and sign it
with key K2.  There is no way to enforce that they are the same.   So, for
all intents and purposes the network must be ready for same name,
different data.   This is no different.

To reflect your question, would it be possible in NDN for many answers to
have the same name?  If I issue an interest for /a in the example above,
both /a/b’s would be valid answers.  The network has no way to force
unique (assigned) naming.

Again. For every node that speaks the Selector Protocol they are free to
decapsulate answers and do something to them.

>- Further, without exclusions and without more specific names, how do you
>retrieve multiple answers to the same query?  Let's assume that in some
>cases this is a desired feature.

You’re free to use exclusions in the Selector Protocol.  Any node that
runs the protocol can give you more answers. The Selector Protocol works
effective exactly like NDN for any node that runs the protocol.

However, we obviously don’t recommend this as a solution, otherwise we
would keep selectors. What we do is answer queries with manifests, and
these in turn point you to specific responses.

Also, for the same query, we would argue that the same response is the
correct thing. If you ask: "Give me a document older than Monday” and you
get Tuesday.  That is a correct answer for any time you have the same
question.  If you ask: “Give me a document older than Monday that is not
Tuesday” that is effectively a different query.

The system does not forbid different answers for the same interest though.
 So if things go on different paths, or if the object availability
(caches) change, or if the lifetime of the object is 0 or something then
you may get a different answer.

>- How do you envision applications interacting with the selector protocol?
> Would they implement it directly or publish "normally named" content to a
>stack that then implements the protocol?

We envision applications eventually using an API. The API abstracts how
things are done underneath. There is no need for applications to
understand wire formats or any of that. Applications shouldn’t care how
integers are encoded. The API can expose the same feature set that you
want out of Selectors but it’s up to the network to implement those
features.  

Obviously the idea is that the network agrees with how things are
implemented.  So, for example, if you had an NDN app that used selectors
(and a reasonable API) we could easily add such functionality to our stack
so you could run over CCN. As a matter of fact, we could also add a few
modules (forwarder module, encoder module, etc) and run our stack (and
your app) on top of NFD if needed.   The networks wouldn’t be compatible,
but the apps wouldn’t know the difference in terms of basic functionality.


Nacho


>On 9/25/14, 1:10 AM, "Ignacio.Solis at parc.com" <Ignacio.Solis at parc.com>
>wrote:
>
>>On 9/25/14, 9:17 AM, "Marc.Mosko at parc.com" <Marc.Mosko at parc.com> wrote:
>>>In the CCNx 1.0 spec, one could also encode this a different way.  One
>>>could use a name like ³/mail/inbox/selector_matching/<hash of payload>²
>>>and in the payload include "exclude_before=(t=version, l=2, v=279) &
>>>sort=right².
>>
>>
>>I want to highlight this.
>>
>>There is a role that selectors can play in a network.  However, our
>>biggest issue with selectors is that they are mandated at the forwarder
>>level.  This means that every node must support selectors.
>>
>>We want to make sure that the core protocol is simple and efficient.
>>Exact matching gives us that.  If you¹re interested in selector matching
>>and searching, then create that protocol over exact matching.
>>
>>Marc just described a simple ³Selector Protocol", basically:
>>- Encode selectors (or any query you want) in the interest payload.
>>- Add a name segment to indicate that this is a selector based query
>>- Add a name segment to uniquely identify the query (a hash of the
>>payload
>>for example)
>>
>>Example:
>>name    = /mail/inbox/list/selector_matching/<hash of interest payload>
>>
>>payload = version > 100
>>
>>Topology:
>>
>>A ‹‹ B ‹‹ C
>>
>>A and C run the Selector Protocol
>>B does not run the Selector Protocol
>>
>>Now: 
>>- Any node that does not understand the Selector Protocol (B) forwards
>>normally and does exact matching.
>>- Any node that understands the Selector Protocol (C) can parse the
>>payload to find a match.
>>
>>If no match is found, forward the interest.
>>If a match is found, create a reply.
>>
>>The reply can contain 2 types of data:
>>- Structured data with links to the actual content objects
>>- Encapsulated content objects
>>
>>So, in our example, the Selector Protocol reply could be:
>>
>>name = /mail/inbox/list/selector_matching/<hash of interest payload>
>>payload =
>>  [  matching name = /mail/inbox/list/v101 ]
>>  [  embedded object < name = /mail/inbox/list/v101, payload = list,
>>signature = mail server > ]
>>signature = responding cache
>>
>>
>>
>>A few notes:
>>- Malicious nodes could inject false replies.  So, if C is malicious, it
>>can insert a reply linking to some random object or just return junk.
>>Well, this would be the case with regular selectors as well.  C could
>>reply with random crap or it could reply with a valid answer that is not
>>the optimal answer (so, for example, not the right-most child or
>>something).
>>This is something that we can¹t prevent.
>>
>>In the case of CCN, our fast path does not check signatures, so you
>>wouldn¹t be able to check the signature of the reply no matter what.  I¹m
>>unsure if NDN is still advocating that every node checks signatures.  If
>>you are, then this approach might not work for you.
>>
>>Nodes that DO understand the Selector Protocol can check the signature of
>>the encapsulated reply (if they wanted to).
>>Nodes that DO understand the Selector Protocol can unpack the reply, and
>>add the corresponding object to their cache, effectively enabling them to
>>answer other Selector Protocol queries.
>>
>>- The reply from the Selector Protocol enabled node (C), could:
>>‹  include a list of all valid answers
>>‹  embed no objects
>>‹  embed more than 1 object
>>‹  process complex queries, regex, etc.
>>
>>The Selector Protocol could also:
>>- include a method for authentication
>>- include a cursor or some other state between queries
>>
>>
>>I think this sort of protocol gives you everything you want while still
>>maintaining an exact match protocol as the core protocol.
>>
>>
>>What is this protocol missing to satisfy your needs?
>>Can we create a protocol that will satisfy your needs on top of exact
>>matching?
>>
>>
>>Nacho
>>
>>
>>
>>--
>>Nacho (Ignacio) Solis
>>Protocol Architect
>>Principal Scientist
>>Palo Alto Research Center (PARC)
>>+1(650)812-4458
>>Ignacio.Solis at parc.com
>>
>>
>>
>>
>>
>