Subject: Re: SVRLOC WG IMPORTANT: SLPv2 next step?

From: Erik Guttman <[email-masked]>
Date: Tue, 19 Sep 2000 11:54:19 +0200 (MET DST)

> On Wed, 30 Aug 2000, Erik Guttman wrote:
> > So are you happy with the slpv2bis-01 draft?
> 
>   No:
> 
> With regards to section 3.1.1:
> 
>   I do not feel that the issues raised regarding the complexity of
> implementing LDAPv3 search filters justifies the simplification of SLP
> search facilities. My reasons follow:
> 
>  * I have implemented the LDAPv3 search filter for OpenSLP (which should
> be included Any Day Now, see
> http://www.nexus.carleton.ca/~hughes/filter.tgz for the implementation),
> and found the task doable. Implementing the logical operators was the
> easiest part, since the code for `&` is almost identical to `|`s. 

That has not been common experience.  If you handle both & and | you
can get arbitrary nesting.  If you only handle & then there is only 
one level of nesting - which can be handled serially (no need for
recursive descent, etc.)

Remember the *CHIEF* resistance to SLP has been the complexity of
supporting LDAP search filters.  If we can make this support dead
simple (ie. handle it in a page or two of code) we will dissolve
over half of our opposition.

>  * In order to implement the `|` or `!` operators, some form of recursion
> on the filter string is necessary. Arbitrarily limiting the filter string
> to contain one `&`, while allowing an unlimited number of `|`s is
> nonsensical, as `&` will become a special case for parsing -- increasing
> complexity. 

! is a real pain since you have to *invert* the results from the previous
filtering.

| really means that you have different search filters you are gluing 
together.  With some reduction in efficiency on the network, these
filters could be sent separately.  We are not searching for fields in
a database - we are searching for services which have required features.
The *common case* is that there is a list of features we need.   It is
*farfetched* to say we need a disjoint set of feature (exclusive or).
Inclusive or can be managed using n separate queries and concatenating
the results.

>  * The removal of any operator limits SLP's applicability. Before causing
> such a dramatic reduction in SLP's potential functionality, it should be
> shown that the `&` operator greatly increases the complexity of filter
> parsing. This has not been done. 

We need to keep '&'!  No one has suggested getting rid of '&'!
 
>  * At some point during the discussion somebody mentioned the relative
> complexity of each of the entities on the network. As far as I recall,
> complexity was a spectrum, with UA/SA's being simple (possibly
> computationally bound), and DAs being complex (possibly with greater
> memory/processor resources). Removing the `&` weakens the role of the DA,
> since any UA that wishes to use multiple `&`s will have to do client side
> attribute checking. This does not follow with the aforementioned
> resource model.

I totally agree.  But we don't need multiple &s.  (&(a=b)(&(c=d)(d=e)))
is logically equivalent to (&(a=b)(c=d)(d=e)) - that is, we can do all
the conjunction we need with only one, initial, '&'.

It is much easier to understand this interface, too.  I have yet to see
a human interface which supports '!' or '|' which is comprehensible.  I
have seen many excellent interfaces which support '&' (a list of conditions,
check boxes, etc.)

> (I feel like I should get a t-shirt saying "Save the &". =)

Send me one!
 
>  Before stating that the LDAPv3 filters make SLP difficult to implement,
> it may be a good idea to find some supportive references. I was able to
> code and then refactor the search filter in less than two weeks. 

It took me longer :-)  In the end, every implementation I have seen has
been pretty complex, especially if the filter handling is to be done 
efficiently.  The goal is to have this be something that will fit on a
single page or two of code - that is what will win the hearts and minds
of the SLPv2 opponents I personally know.

>  Further, I don't see the point of removing the eliding of
> leading/trailing white space. Again, the code of eliding is relatively
> simple, and it avoids pesky white-space errors. 

Please discuss this further on the list, in regard to the WG ACTION:
comments requested for SLPv2bis final list of changes.

> In general:
> 
>  Reducing SLP's functionality will only harm SLP's utilization. As it is,
> SLP has not gained widespread acceptance (OpenSLP is the first opensource
> implementation of SLP. This indicates that few oft-used services use
> SLP). Weakening SLP's functionality condemns the protocol to disuse. 

I have argued that dropping '!' and '|' do not really reduce the
functionality of SLP - at least the core functionality.  I have
further argued that it will *increase* the acceptability of SLP
to drop these features.

Erik

---

From: Evan Hughes <[email-masked]>
Date: Tue, 19 Sep 2000 10:45:37 -0400 (EDT)

I really feel bad for constantly harping on this subject, but I feel
that it is important. Much of SLP's strength comes from its robust service
selection mechanisms; which are dependent on strong filters. 

> one level of nesting - which can be handled serially (no need for

   Arbitrary nesting is easily handled with recursion. Recursion stack
overflows are easily prevented with recursion counts. Here at Carleton,
there is a first-year programming course which asks students to code an
infix calculator: it's almost identical to the LDAPv3 search filters,
except that the operations are all mathematical. Predicates (the purely
boolean statements that LDAPv3 uses) are at a similar level of complexity.

   I'm not trying to trivialize the problem by saying that anyone can code
LDAPv3 search filters, but this is a textbook problem: solutions to it can
be found all over the place.

> supporting LDAP search filters. 

I have two responses to this point:

1.  In that case, keep strong search filters, but make them optional. That
way applications that require them (as I suspect most nontrivial
applications will) can use them. 

2.  Who has this resistance been from? I don't think SLP's day has come
yet: commercially, service discovery isn't a big issue yet (on most
networks, there are only a few types of resource that are even worth
discovering). As service discovery becomes more important, so will service
selection. If SLP does not have a robust service selection model, it will
be ignored. 

> If we can make this support dead simple (ie. handle it in a page or
> two of code) we will dissolve over half of our opposition.

I'm going to get a bit pedantic here. Please bear with me. 

Some metrics: These all come from my filtering code, which is available at
the aforementioned address. I'm sorry that I again reference my code, but
it's the implementation that I'm most familiar with. It's implementation
isn't too original, so I assume other implementations should be
comperable.

Functional predicate code (this code deals with locating operators and
performing boolean operations -- it does not include the 61 lines of
support functionality):
     
          217 lines (24 of which are comments, another 27 are blank) = 166

Boolean operations (just the prefix):

           60 lines (8 are comments, 10 are blank) = 42

Lines per boolean operator:
                         &       23 (3 c, 4b) =  16
                         |       23 (3 c, 4b) =  16
                         !       11 (1 c, 1b) =  10

Leaf operators (just the infix) -- This code does NOT evaluate the
operators, it only detects them and  their operands:
          115 lines (14c, 8b) = 93

As you can see, even including leaf operators and comments, all LDAPv3
parsing code will fit into four pages (of 8.5 by 11 paper). The boolean
operators that this discussion focuses on take less than a page of code. I
suspect that examining other implementations will yield similar results. 

> ! is a real pain since you have to *invert* the results from the previous

  The LDAPv3 search filters are purely predicates: they are not set
operations. All operations return either TRUE or FALSE. Inverting those
values shouldn't be too hard. 

> a database - we are searching for services which have required
> features. The *common case* is that there is a list of features we
> need.  It is *farfetched* to say we need a disjoint set of feature
> (exclusive or). Inclusive or can be managed using n separate queries
> and concatenating the results.

Your first point (let the UA do the work):

  Consider the problem of complexity of SLP service selection. There is a
UA who wants to find some service. There are a number of DAs/SAs who want
to provide that service (for the sake of clarity, I'll talk about those as
an individual DA). The cost of computation shared between the two is
1. That value can never change, meaning that we have a zero-sum game. 

Consider the following assumptions, 

 * DAs have more resources than UAs
 * There are more UAs than DAs
 * There will only ever be a few implementations of DAs (which are general
purpose)
 * There will be many, many implementations of UA (which highly specific)

  What you say is true. You can simplify the DA by making the SA do more
work. But that means increased complexity for all of the SA programmars
(which will probably outnumber the DA programmars). Since we're dealing
with a zero-sum game, any reduction in complexity of the DA means a
proportionate increase in the compexity of the SA. 

Your second point (common vs farfetched case):

  I don't think we have a representative sample of the uses of SLP.
Currently, there are a few users of it -- wait until the usage community
increases. Matt has apparently been corresponding with a fair number who
want some type of predicates. I assume that as this community grows, the
desire for "farfetched" (ie, highly selective) queries will grow.

> We need to keep '&'!  No one has suggested getting rid of '&'!

  By setting a finite number of allowed operators, the user (human or
application) is being limited in the selections it is allowed to
perform.

> >  * At some point during the discussion somebody mentioned the relative
[snip: my standard rant about complexity, see above]
> the conjunction we need with only one, initial, '&'.

  Very true. But by limiting the number 

> have seen many excellent interfaces which support '&' (a list of conditions,

  Ditto. But this is a UI issue, and hardly justification for modifying a
comparatively low level protocol. Besides, service selection is supposed
to be transparent. If the user wants to print to a printer, they shouldn't
be forced to compose an SLP query, the application/OS should do it for
them and return all appropriate responses. 

> efficiently. 

   But this is "fire and forget" code. It needs to be written once, and
then put in an airtight box to prevent bugs (ie coders with itchy
optimization fingers) from getting at it. The search filter
semantics/functionality is static: they won't be changing. I don't mean
that maintainability isn't an issue (it always is), I simply mean that
once it's written it shouldn't need to be revisited.

> The goal is to have this be something that will fit on a
> single page or two of code

   As I said, it does. =)

> - that is what will win the hearts and minds of the SLPv2 opponents I
> personally know.

 But what about those who want to select from amongst a pool of many
similar resources? The simplification of SLPv2 may make it useless to many
more people. 

> further argued that it will *increase* the acceptability of SLP

 My argument can be summed up as follows:
  * Boolean operators are simple to implement (in under 30 lines
each). Leaf operators are much more complex.
  * The SLP user community is still small, those who have not yet begun to
use SLP will likely need a rich service selection syntax (ie, by removing 
functionality to please the few now, you're disappointing the many later)
  * Reduction of DA functionality pushes more responsibility onto resource
starved UAs
  * Putting arbitrary constraints on the use of certain operators (ie,
only one '&') increases the complexity of code (see my previous email).

 I would like to make the following suggestion:
  * Since LDAPv3 filters allegedly (*grin*) discourage use of SLPv2, make
them optional. Allow SA/DAs not to implement them. Have them report that
when they send the DAadvert (or whatever the response is). 
  * Allow query forwarding from filterless DAs to filtered DAs using mSLP. 

e

---

From: Evan Hughes <[email-masked]>
Date: Tue, 19 Sep 2000 10:56:44 -0400 (EDT)

Ummm, this is sort of an addendum to the previous email. I thought of it
about 30 seconds after I sent the original. 

   A relatively small portion of predicate filtering code is dedicated to
actual boolean filters (according to my previous metrics, between 10%
(considering predicates only) and 5% (including the slp attribute
library). Most of it is involved in type specific comparison operations
and generic text parsing. 

  Since the boolean-operator portion of the code is such a small fraction,
why are we worrying about it? If we're worried about the opponents of SLP,
doesn't this just illustrate that we have to educate them further
regarding SLP's functionality?

e

---

From: Erik Guttman <[email-masked]>
Date: Tue, 19 Sep 2000 17:38:23 +0200 (MET DST)

Evan,

Thanks for your well worked out response.  I think we need to put it
to the WG list to decide this.  As the WG chair and doc editor, I will
go with whatever is decided.  We'll see what the consensus (possibly
rough) is, at the end of two weeks.

A few remarks though:

> * Since LDAPv3 filters allegedly (*grin*) discourage use of SLPv2, 
>   make them optional. Allow SA/DAs not to implement them. Have them 
>   report that when they send the DAadvert (or whatever the response is). 

I don't think that will work.  UAs need to know what kind of filter to
send.  Old UAs may send filters which new DAs and SAs don't support 
and get errors back.  But in the future, UAs will need to send filters
which won't get errors back.

> If we're worried about the opponents of SLP, doesn't this just 
> illustrate that we have to educate them further regarding SLP's
> functionality?

I shouldn't have used the word opponents - more like detractors.
They aren't just bigots - they have substantial arguments to back
up their opinion that SLP is 'ornate' and 'overfeatured' - especially
its support of attributes and full search filters.

Erik

---

From: Evan Hughes <[email-masked]>
Date: Tue, 19 Sep 2000 11:45:53 -0400 (EDT)

> rough) is, at the end of two weeks.

   Sounds fair. 

...
> its support of attributes and full search filters.

  Heh. Last week my advisors and I had a discussion on the merits of
inserting some sort of interpreter (Lua?) into DAs to allow for stronger
service selection (for QoS type stuff). After that, thinking of the LDAPv3
filters as anything more than "bare-bones" is difficult. =)

e

---

From: Matthew Peterson <[email-masked]>
Date: Tue, 19 Sep 2000 10:05:13 -0600

> filters as anything more than "bare-bones" is difficult. =)

I do not know what your advisors are working on exactly, but it might be
possible that they are trying to stretch SLP to fit a role that is not
compatible with its designed purpose.

Matt

---

From: Evan Hughes <[email-masked]>
Date: Tue, 19 Sep 2000 13:53:21 -0400 (EDT)

> compatible with its designed purpose.

   They want to use it for selecting services based on Quality of Service
type constraints. SLP is perfect for this application -- especially when
dealing with "legacy" services (http, ftp, nfs, backup, imap, etc). 

e