Subject: Re: Capability Negotiation for OCP

From: Alex Rousskov <[email-masked]>
Date: Mon, 2 Jun 2003 12:39:46 -0600 (MDT)

On Thu, 17 Apr 2003, The Purple Streak, Hilarie Orman wrote:

> PPP, IPSec and IKE use "offer, select".  The trick is to spell out
> the complete set of selections at offer time.  Don't say (A1 or A2)
> and (B1 or B2) if (A1 and B2) is not permitted - say instead
>
> 	{ A2 and (B1 or B2) } or { A1 and B1}

I am adding negotiation mechanisms to the OCP draft. While describing
how negotiation works, I realized that providing a _complete_
selection "menu" in one offer would require very deep nesting of OCP
data structures or very long OR lists for some negotiations. I was
surprised that a protocol like PPP (RFC 1661) could handle that
(something the above examples imply) and read the PPP specs.

My current understanding is that PPP does not spell out all possible
selections in each offer.  Instead, it spells out one selection (e.g.,
"A2 and B1"). If that selection is rejected, a different selection is
provided (e.g., "A2 and B2"). There may be better places to quote, but
here is one direct quote from "6.2. Authentication-Protocol"

    An implementation MUST NOT include multiple Authentication-
    Protocol Configuration Options in its Configure-Request packets.
    Instead, it SHOULD attempt to configure the most desirable
    protocol first.  If that protocol is Configure-Nak'd, then the
    implementation SHOULD attempt the next most desirable protocol in
    the next Configure-Request.

I am sending this message to provide an example where multiple offer
messages are used. I am not, at this point, advocating either approach
(a single complex and complete offer versus a series of simple
incomplete offers, each requiring immediate response). If you have any
preferences or suggestions, please voice them!

Thank you,

Alex.

P.S. I did not have enough energy/time to understand whether IKE and
     IPSec support multiple offer messages within the same negotiation
     phase. They do support multiple OR choices within one message.

---

From: Graham Klyne <[email-masked]>
Date: Tue, 03 Jun 2003 10:05:01 +0100

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).

One of my goals was to avoid the kind of ordering-dependency you describe 
for PPP -- in my view, although that makes implementation easier, it also 
increases the scope for unintended outcomes.  But, then, the RFC2533 
algorithm doesn't really provide for selecting a preferred feature among 
available alternatives, even though the format used has a rudimentary 
mechanism to express such preferences.  There are some theoretical problems 
in doing this in a completely general fashion.

FWIW, there's also an implementation, in Java, of the RFC2533 algorithm 
available at:
   http://www.ninebynine.org/Software/Intro.html#RFC2533FeatureSetMatching
to demonstrate that the RFC2533 matching algorithm is reasonably realizable.

One of the things I noticed when playing with the algorithm, which involves 
automatically converting the feature expression to "disjunctive normal 
form", is that one can easily end up with long lists of ANDed 
conditions.  Similar applies to "conjunctive normal form", where one ends 
up with long lists of ORed conditions.  But at least, using this kind of 
framework, one isn't forced to actually *transmit* these long lists.

#g
--

>      phase. They do support multiple OR choices within one message.

-------------------
Graham Klyne
<[email-masked]>
PGP: 0FAA 69FF C083 000B A2E9  A131 01B9 1C7A DBCA CB5E

---

From: Alex Rousskov <[email-masked]>
Date: Tue, 3 Jun 2003 09:48:31 -0600 (MDT)

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!

---

From: Graham Klyne <[email-masked]>
Date: Wed, 04 Jun 2003 00:24:04 +0100

Some other data points to maybe consider...

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.

On ordering, that may be a difficult dependency to evolve away from once it 
has been introduced.

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)")

#g
--

-------------------
Graham Klyne
<[email-masked]>

---

From: Alex Rousskov <[email-masked]>
Date: Wed, 4 Jun 2003 09:21:31 -0600 (MDT)

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:

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.

---

From: Graham Klyne <[email-masked]>
Date: Wed, 04 Jun 2003 22:06:49 +0100

>will not negotiate with you about anything else until I know who you

Oh yes... I was referring to ordering in the very narrow sense of lexical 
ordering within a capability expression having a bearing on what the 
expression actually means.

#g

-------------------
Graham Klyne
<[email-masked]>