Proposed By:
============
Erik Guttman
Matt Peterson
Description
===========
There has been a lot of discussion of the proposal rev-2608-2.
I propose that we REJECT rev-2608-2 and open a new revision
discussion on the limited support for search filters proposed
by Matt Peterson: http://www.geocrawler.com/archives/3/12970/2001/7/0/6135105
Please discuss this proposal on the mailing list, if you have any
strong feelings about it.
rev-2608-2 is:
Description
===========
Search filters may only be a single term '(a=b)' or a sequence
of terms conjoined together '(&(a=b)(c=d)(e=f))'. '!', '|' And
multiple nesting is not supported.
The reason for requiring simplified search filters is to reduce the
complexity of SA implementation.
My new proposal is:
Description
===========
Search filters are defined in RFC 2608 to comply with LDAP
search filter rules (excluding extensible matching rules).
Support for arbitrarily nested logical functions '&', '|' and '!'
requires complex query interpretation code and implies that the
data store for service agents be designed to accomodate such
searches efficiently. This makes implementation of SLP on very
small platforms difficult.
Dropping support for arbitrary search filters entirely and instead
adopting a subset of these filters for SLP would simplify the
implementation. At the same time, it would limit the capability
of the protocol to express genuinely useful conditions.
Note that query support is already optional - but it is all or
nothing. If a service type supports any attributes, full search
filter support is required. This proposal is a 'middle ground'
compromise.
This proposal is for a class of limited support - for SAs - which
would be OPTIONAL to implement. In this case, the rule is simply
support for either single atomic terms (like '(a=4)') or a conjoined
list of such terms '(&(a=4)(b=3)(c=snort*snort))'.
An SA which receives a service request containing a search filter
which it cannot evaluate (with '|' terms, nested '&' terms, '!' terms,
etc.) would fail to evaluate it. If the request was multicast -
the request would be dropped. If the request were unicast, an error
of code MSG_NOT_SUPPORTED is returned.
The UA can infer that the SA only supports limited queries because
(a) all SAs support SrvRqsts. (b) MSG_NOT_SUPPORTED in response to
a SrvRqst will be defined to mean that the SA cannot support complex
search filters.
This is wire compatible with existing SLP implementations. First,
multicast convergence will work as before. New SAs with limited
capabilities were not present (or discoverable) by legacy UAs, so they
will not miss anything they could've found before. No new error codes
can be returned to confuse legacy software.
Future versions will be instructed that they SHOULD use simple query
filters in multicast requests as some SAs may only implement limited
search filters.
Note that a clever API can break up a compound query into multiple
non-compound ones: "(|(A=1)(B=1))" can be issued as "(A=1)" and "(B=1)"
'!' support can be supported on the UA side by acquiring attributes
associated with service instances and checking to see if the desired
attribute instance is not present. A better way to do this would be
to simply not expose or support '!' and compound queries at the
API at all - which the API implementation MAY do. This is justified
by the fact that there are very few existing or even plausible human
interfaces which support disjunctions or negations.
DAs MUST implement full search filter support.
Summary of previous discussion
==============================
Date: Thu, 19 Jul 2001 13:06:06 -0400
From: "Mayer, Jim"
Subject: RE: [Srvloc-discuss] rev-2608-2 reevaluation
To: "'Erik Guttman'" , srvloc-discuss@lists.sourceforge.net
Erik,
A couple of comments on your proposal:
The description says:
> Support for arbitrarily nested logical functions '&', '|' and '!'
> requires complex query interpretation code and implies that the
> data store for service agents be designed to accommodate such
> searches efficiently. This makes implementation of SLP on very
> small platforms difficult.
Whether or not supporting nested logical functions is complex is subjective,
so to avoid an "it is, no it isn't" sort of argument I won't say more than I
just said about that issue. I think, however, that the last two statements
contradict each other. An SA supporting a LARGE number of registrations
might need to optimize its data store, but very small platforms will, by
definition, only support a few registrations. If there are only a few
registrations, then a simple linear application of the search filter will do
just fine.
The description also says:
> This proposal is for a class of limited support - for SAs - which
> would be OPTIONAL to implement. In this case, the rule is simply
> support for either single atomic terms (like '(a=4)') or
> a conjoined list of such terms '(&(a=4)(b=3)(c=snort*snort))'.
We need to clearly specifically whether the wildcarding is limited (perhaps
to a single "*") or supports the full LDAPv3 syntax. I think it should
support the full syntax (i.e. multiple "*" characters).
The description also says:
> An SA which receives a service request containing a search filter
> which it cannot evaluate (with '|' terms, nested '&'
> terms, '!' terms, etc.) would fail to evaluate it. If the
> request was multicast - the request would be dropped. If the
> request were unicast, an error of code MSG_NOT_SUPPORTED is returned.
>
> The UA can infer that the SA only supports limited queries because
> (a) all SAs support SrvRqsts. (b) MSG_NOT_SUPPORTED in
> response to a SrvRqst will be defined to mean that the SA cannot
> support complex search filters.
I have a problem with the logic here. It seems to me that these rules imply
that an SA that does not support a given search filter will not respond at
all to a multicast request. If that is the case, then a UA will have no way
of knowing if a multicast request missed a potentially matching service.
The suggested test doesn't seem adequate to me, because a UA would have to
potentially test every available SA!
Anyway, the end result seems to be a system where full LDAPv3 searches are
unreliable and therefore effectively useless in the absence of a DA.
The proposal also states:
> Future versions will be instructed that they SHOULD use
> simple query filters in multicast requests as some SAs
> may only implement limited search filters.
As I stated earlier, I already have one application that makes complex
queries. They come about because I am mechanically combining queries from
several sources. The ability to nest query expressions is a very powerful
tool, and not just for queries typed directly by people.
I also have a major concern about recommending that only simple query
filters be used in multicast requests. The problem is that an API client
does not know and should not have to know whether a DA is present or not. I
always thought this was fundamental to the design of SLP. If we go ahead
with this proposal, then I think we have broken that fundamental principal.
The proposal also states:
> attribute instance is not present. A better way to do
> this would be to simply not expose or support '!' and compound
> queries at the API at all - which the API implementation
> MAY do. This is justified by the fact that there are very
> few existing or even plausible human interfaces which support
> disjunctions or negations.
I disagree strongly with this statement, and have seen a number of UI's that
implement negation very nicely. The usual pattern is to:
(1) specify one or more patterns that must match
(2) specify one or more patterns that must not match
An example would be:
Find me all of the web pages that reference
SLP but do not contain the words
"SPOKEN LANGUAGE PROCESSING"
or, even better:
Find me color printers in building 1234 that are not in a restricted
area.
In fact, most internet search engines, which are not only plausible but
widely used, support these features. A quick check shows that the following
search engines all support some form of negation or disjunction:
http://www.google.com (advanced search)
http://www.altavista.digital.com (advanced search)
http://northernlight.com
Xerox's "DocuShare" product supports this as well. Even search engines that
do not support nesting typically support exclusion word lists (e.g. "+SLP
-SPOKEN").
Finally, even if you accept that few human interfaces support disjunctions
or negations (which I don't), the statement belies the fact that arbitrary
Boolean operations arise naturally out of machine based manipulation of
search criteria.
I'm sorry to be so negative about the proposal, but I just don't think that
eliminating or restricting search terms is a good idea. Small SA
implementations can use simple data structures and simple implementations of
search filters. If we want to promote the use of SLP, then perhaps we
should look into producing a public domain implementation of a simple query
processor that could be used in small systems. I think that would be more
effective than restricting the search syntax, and would not damage the
overall usefullness of SLP.
-- Jim
-------------------------------------------------------------
Date: Fri, 20 Jul 2001 10:33:25 +0200 (MET DST)
From: "Erik Guttman"
Subject: RE: [Srvloc-discuss] rev-2608-2 reevaluation
To: "Mayer, Jim"
Cc: "'Erik Guttman'" , srvloc-discuss@lists.sourceforge.net
Jim,
Thanks for your well thought through comments.
> The description says:
>
> > Support for arbitrarily nested logical functions '&', '|' and '!'
> > requires complex query interpretation code and implies that the
> > data store for service agents be designed to accommodate such
> > searches efficiently. This makes implementation of SLP on very
> > small platforms difficult.
>
> Whether or not supporting nested logical functions is complex is subjective,
> so to avoid an "it is, no it isn't" sort of argument I won't say more than I
> just said about that issue.
With all due respect, having implemented this several times and looked
at most implementations of SLP so far, I can say with certainty that
support for arbitrary search filters is at least an order of magnitude
more complex than support for simple conjoined requests.
In the nested case, you have to keep track of, then merge distinct
branches of evaluation (for ORs) and negate the entire result (for NOTs).
Further, one must consider optimizations for efficient access in big
service stores, which drop AND terms and accept ORs terms as soon as
possible.
In the conjunction case, you need only evaluate in a linear fashion
until something fails to be true, then you can drop the entry from
the result set.
---
> I think, however, that the last two statements
> contradict each other. An SA supporting a LARGE number of registrations
> might need to optimize its data store, but very small platforms will, by
> definition, only support a few registrations. If there are only a few
> registrations, then a simple linear application of the search filter will do
> just fine.
That's fair to say. OK.
---
> The description also says:
>
> > This proposal is for a class of limited support - for SAs - which
> > would be OPTIONAL to implement. In this case, the rule is simply
> > support for either single atomic terms (like '(a=4)') or
> > a conjoined list of such terms '(&(a=4)(b=3)(c=snort*snort))'.
>
> We need to clearly specifically whether the wildcarding is limited (perhaps
> to a single "*") or supports the full LDAPv3 syntax. I think it should
> support the full syntax (i.e. multiple "*" characters).
We agreed to continue to support wildcards (as per LDAP search filters)
in rev-2608- .
---
> The description also says:
>
> > An SA which receives a service request containing a search filter
> > which it cannot evaluate (with '|' terms, nested '&'
> > terms, '!' terms, etc.) would fail to evaluate it. If the
> > request was multicast - the request would be dropped. If the
> > request were unicast, an error of code MSG_NOT_SUPPORTED is returned.
> >
> > The UA can infer that the SA only supports limited queries because
> > (a) all SAs support SrvRqsts. (b) MSG_NOT_SUPPORTED in
> > response to a SrvRqst will be defined to mean that the SA cannot
> > support complex search filters.
>
> I have a problem with the logic here. It seems to me that these rules imply
> that an SA that does not support a given search filter will not respond at
> all to a multicast request. If that is the case, then a UA will have no way
> of knowing if a multicast request missed a potentially matching service.
I agree there is a problem. Let me spell it out even more clearly.
The UA has no way of knowing whether a request is being unicast to
DAs or multicast to SAs. If the UA uses a complex query it may get
a different answer in the two cases. DAs will handle it, some SAs
will not.
The answer is to make multicasting complex query filters more chatty
on the network and more complex to handle on the client side. Some
APIs may even reject complex queries (we could define a new error
code for this) since they lack the necessary support to handle them
in the multicast case. And if they can't handle them in the multicast
case, they should never accept these queries. It makes no sense to
have inconsistent API behavior depending on whether there are DAs
present in the network or not.
> The suggested test doesn't seem adequate to me, because a UA would have to
> potentially test every available SA!
I did not intend the above to be a test - but I see how you arrived at
this idea. This indeed would be a bad approach!
> Anyway, the end result seems to be a system where full LDAPv3 searches are
> unreliable and therefore effectively useless in the absence of a DA.
Indeed, they are useless in the presense of a DA since you can't be sure
all UAs know about the DA. SLP has to return the same answer whether a
DA is present or not.
I believe the answer is to decompose complex queries at the API and
issue them as simple queries in the multicast case. See below.
---
> The proposal also states:
>
> > Future versions will be instructed that they SHOULD use
> > simple query filters in multicast requests as some SAs
> > may only implement limited search filters.
>
> As I stated earlier, I already have one application that makes complex
> queries. They come about because I am mechanically combining queries from
> several sources. The ability to nest query expressions is a very powerful
> tool, and not just for queries typed directly by people.
>
> I also have a major concern about recommending that only simple query
> filters be used in multicast requests. The problem is that an API client
> does not know and should not have to know whether a DA is present or not. I
> always thought this was fundamental to the design of SLP. If we go ahead
> with this proposal, then I think we have broken that fundamental principal.
The api client would not be the one to issue simple queries. It would
be the API itself, issuing requests to the underlying SLP implementation.
A query for
(|(&(|(a=b)(c=d))(e=f))(&(g=h)(i=j)))
could be automatically parsed and broken down into
(&(a=b)(e=f))
(&(c=d)(e=f))
(&(g=h)(i=j))
The results of these three queries could be collated by the
API and returned to the client app which made the request.
A little more difficult to support is the '!' filter.
In this case, the attributes of the service instances
need to be obtained - using an attribute request, or better
yet, the attribute list extension to the service reply (so
no additional requests are needed!)
(&(a=b)(!(c=d)))
Could be supported by a request
(a=b)
Then, the API will scan the associated attributes for each
service instance returned in the reply. If 'c=d' is true,
the service instance is rejected.
---
> The proposal also states:
>
> > attribute instance is not present. A better way to do
> > this would be to simply not expose or support '!' and compound
> > queries at the API at all - which the API implementation
> > MAY do. This is justified by the fact that there are very
> > few existing or even plausible human interfaces which support
> > disjunctions or negations.
>
> I disagree strongly with this statement, and have seen a number of UI's that
> implement negation very nicely. The usual pattern is to:
You argue this very convincingly. I concede the point.
---
> I'm sorry to be so negative about the proposal, but I just don't think that
> eliminating or restricting search terms is a good idea.
I am glad you are ensuring we consider this carefully.
---
> Small SA implementations can use simple data structures and
> simple implementations of search filters.
There is no simple implementation of nested search filters. By
simple, I mean "fits on a single page of code." Support simple
search filters (only single terms or conjoined single terms)
can be supported on a single page of code. Even a yacc grammar
(let alone the handlers) of the entire grammar excedes a single
page.
> If we want to promote the use of SLP, then perhaps we
> should look into producing a public domain implementation of a simple query
> processor that could be used in small systems. I think that would be more
> effective than restricting the search syntax, and would not damage the
> overall usefullness of SLP.
I have taken that route. My 'simple query processor' for full search
filters is well over 2000 lines of code, in my mini-SLP code implementation.
I also tried in this implementation to require very little memory (stack
and heap) during evaluation, which is a requirement for small devices.
My truly simple query handler for the simple search filters is 250 lines
of Java. This is in my as-yet-unreleased 'kslp' code. I am pursuing
public source licensing of this internally at Sun right now.
In neither case do I try to really compress the code - I log errors,
comment my code, etc. So this is a fair comparison of complexity.
---
I still urge that we allow SAs to ignore complex queries. This will
significantly lower the barrier to entry for small device manufacturers
supporting SLP. The current solution (no attribute support) makes SLP
hardly more attractive than the competitors to SLP (UPnP, DNS SRV RRs,
etc.) I think the compromise allows for the power of SLP without the
burden of it. An SLP SA which supports
- simple queries
- mesh enhancements (only find one mesh-enhanced DA and basta!)
- doesn't support PR lists
- supports attrlist extensions but not attribute request
would be very small indeed and fully functional.
---
Regards,
Erik
-----------------------------
Date: Fri, 20 Jul 2001 14:08:51 -0700 (PDT)
From: "James Kempf"
Subject: RE: [Srvloc-discuss] rev-2608-2 reevaluation
To: Erik.Guttman@Sun.COM, srvloc-discuss@lists.sourceforge.net, JMayer@crt.xerox.com
I agree with Jim on this issue. I think it makes sense to maintain as
much LDAP compatibility as possible, and allowing partial queries
will only confuse and complicate UA implementations. I think the
amount of confusion and complexity in the UA will probably be much
more than the amount of complexity to actually implement the query handler
since implementing the query parser is just a parsing exercise and
the evaulation would need to be done even for the simpler case.
If people don't want to implement the query parser from scratch they
can use the one in OpenSLP.
The only case where I can see a possible reason to simplify is eliminating
'!', and I'm not convinced that it is worth removing the LDAP compatibility.
jak
-----------------------------
Date: Mon, 23 Jul 2001 12:30:41 +0200 (MET DST)
From: "Erik Guttman"
Subject: RE: [Srvloc-discuss] rev-2608-2 reevaluation
To: "James Kempf"
Cc: Erik.Guttman@Sun.COM, srvloc-discuss@lists.sourceforge.net, JMayer@crt.xerox.com
Jim,
I will persist, along with Matt and Mikael Pahmp, in pressing this as
*the most significant improvement* in SLPv2bis in terms of improving
SLPv2 adoption and compliance.
> I agree with Jim on this issue. I think it makes sense to maintain as
> much LDAP compatibility as possible, and allowing partial queries
> will only confuse and complicate UA implementations.
It is far far simpler for UAs to decompose queries than it is for SAs
to parse and interpret complex queries. UAs have to compile a list of
replies anyway, so doing so for distinct decomposed queries is hardly
more difficult than it would be anyway. The only difficult thing to
support (either on the UA or SA side) is the '!' operation.
> I think the
> amount of confusion and complexity in the UA will probably be much
> more than the amount of complexity to actually implement the query handler
> since implementing the query parser is just a parsing exercise and
> the evaulation would need to be done even for the simpler case.
I disagree.
> If people don't want to implement the query parser from scratch they
> can use the one in OpenSLP.
This is not an option in very small platforms.
> The only case where I can see a possible reason to simplify is eliminating
> '!', and I'm not convinced that it is worth removing the LDAP compatibility.
I doubt LDAP clients will be back-ended with SLP, so there is no
compatibility issue. We need to ensure that all SLP queries can
be back-ended by LDAP, and that remains supported whatever we
decide.
Erik