On Wed, 4 Jun 2003, Graham Klyne wrote:
I believe some sip/sdp-related work on content negotiation looked at
this (RFC2533) and decided that they did not want to go with the
full algebraic complexity. So (I think) they took an approach of
profiling the structure to use a normal-form subset which is
inherently easier to process. A possible advantage of this approach
is that it leaves a clear path to introduce more general forms of
expression of they are later found to be needed. Sorry, I have no
specific references for this.
I think this is what we are doing right now as well. We use a
normalized disjunction, essentially. It is simple and can be extended
if we need something more complex.
On ordering, that may be a difficult dependency to evolve away from
once it has been introduced.
I agree, but some ordering is impossible to avoid. For example, one
may want to encrypt connection before talking about _anything_ else.
That introduces an order dependency: negotiate encryption first and
everything else later. Authentication has a similar side-effect (I
will not negotiate with you about anything else until I know who you
are).
Also, one of our requirements is that some features can be
[re]negotiated in the middle of a transaction. Supporting this in a
sane way requires partial negotiation (negotiation of a subset of
features) which is very similar to ordering.
And finally, having some similarities with the RFC2533 approach,
there has been research into a topic known as "description logics"
over the past (approx) 15 years that takes a slightly different
slice on the use of logical expressions to describe things. The
goal of this work has been to balance expressive power with
computational tractability. (It can be shown that a fully
generalized solution based on first order predicate logic is not
always decideable.) The key idea is being able to perform a
subsumption computation, finding a description that minimally
subsumes two or more given descriptions. I found a paper by Alex
Borgida was a useful introduction, though there are many others:
http://citeseer.nj.nec.com/borgida95description.html
or:
http://www.cs.rutgers.edu/~borgida/
(Look for "Description Logics in Data Management (1995)")
Hmm... Looks interesting. I think we may need to investigate all these
options if we decide to increase the current level of complexity
to express more complicated configuration dependencies. I remain
hopeful that our current simple scheme is enough for OPES needs, but
I would not be surprised if I am proven wrong by real-world demands.
Thank you,
Alex.
At 09:48 03/06/03 -0600, Alex Rousskov wrote:
On Tue, 3 Jun 2003, Graham Klyne wrote:
I don't know if it helps, but some similar issues to those you
mention were addressed in the content negotiation work I did a while
back (RFC2533).
Thanks for the pointer! It looks like your RFC may be very useful to
OCP implementors, especially if we decide to support complex feature
expressions like "(A2 and (B1 or B2)) or (A1 and B1)" as opposed to
simple (but, as you note, potentially very long) "normal" AND/OR
lists. My undestanding is that RFC 2533 outlines a way to
pragmatically match [complex] feature expressions in negotiation
offers with available/desired capabilities, also a [complex] feature
expression. A how-to document replacing a dry book on boolean algebra,
sort of.
My current intention is to use very simple expressions. I convinced
myself that it is the right starting point after looking at what
negotiation mechanisms are offered by a few existing protocols that
are somewhat similar to OCP (BEEP, PPP, IKE*, etc). I did not find
anything that supports negotiation using really complicated feature
expressions. Yet, these protocols "work". Thus, I decided it would be
OK to start with something simple and extend the interface only of
actual need is detected.
I also agree that ordering dependency may lead to suboptimal
negotiations. However, again, it looks like our environment is simple
and structured enough to marginalize that risk.
Your application domain is probably different -- it already has a
pressing need for complicated content descriptions.
Thank you,
Alex.
P.S. RFC 2533 is the first RFC I have seen that mentions Prolog,
nice work!