Subject: Re: [Sip] draft-ietf-sip-body-handling-01

From: [email-masked]
Date: Mon, 3 Mar 2008 16:21:00 -0500

From: "DRAGE, Keith \(Keith\)" <[email-masked]>

   Now would be a good time to speak if you think that there are open
   issues that need to be addressed in this draft, as these are all meant
   to be closed before WGLC.

I don't know if this is an open issue, but it does appear that (with
the features we are including) determining if a body can be
successfully processed is an NP-complete problem.  I suppose that the
processing time isn't such a problem (as only pathological cases will
take exponential time), but it indicates that any straightforward
algorithm to determine how to process a body will have to be able to
backtrack and retry previously made decisiions, which adds quite a bit
of complexity.

Dale
_______________________________________________
Sip mailing list  https://www.ietf.org/mailman/listinfo/sip
This list is for NEW development of the core SIP Protocol
Use [email-masked] for questions on current sip
Use [email-masked] for new developments on the application of sip

---

From: Paul Kyzivat <[email-masked]>
Date: Mon, 03 Mar 2008 19:06:36 -0500

Dale,

Can you explain more about how you reached this conclusion?

	Paul

---

From: [email-masked]
Date: Tue, 4 Mar 2008 22:34:51 -0500

From: Paul Kyzivat <[email-masked]>

It started when I was thinking that what this draft needs (IMHO) is to
have a statement of "what the rules are", that is, the rules for
interpreting or deciding whether to accept a body, with all the rules
written in one place, so we can stare at them and see if anything is
missing.  (So far, we've been writing text to explain ambiguous points
in the previous texts, but a textual structure like that makes it hard
to see if you've really covered all the cases.)

I then started to outline in my head how I would organize such a
statement:
    defaulting rules for Content-Disposition
    scoping and validity of 'cid'
    assumptions about accepting and processing non-multipart types
    accepting and processing rules for each multipart type

At that point, I noticed that there could be interdependencies between
accepting one part and accepting another part.  That is usually the
signal that the problem in question is NP-complete.  (In practice,
meaning that deciding what to do could take an amount of time which is
the exponential of the number of body parts to be considered, and that
the decision algorithm requires backtracking.)

So I then attempted to prove that the problem was NP-complete by the
process of reducing the problem "3-satisfiability" to the problem of
determining if a body is acceptable.  And it turns out that is fairly
simple.

In order to make this construction work, I needed to assume the
following features of our body-part scheme, all of which seem to be
accepted as requirements:

    If all parts of a multipart/mixed are marked handling=required,
    then the body can be processed only if all the parts can be
    processed.

    A multipart/alternative with 2 parts can be processed if either
    part can be processed, and one part must be chosen for processing,
    leaving the other part un-processed.

    A part can contain 'cid' URLs, which cause the referenced parts to
    be processed.

    A part marked "Content-Disposition: by-reference; handling=required"
    can only be processed if a previous component referencing it via a
    'cid' URL is processed.

What makes this situation problematic is not that deciding whether and
how to process a complex body make take exponential time (since that
will generally happen only in pathological cases), but rather that
most straightforward algorithms for making the decision will have to
implement backtracking (which will sometimes be required even in
non-pathological cases).

(Here beginneth the technical part.)

The reduction is as follows:

http://en.wikipedia.org/wiki/NP-complete
http://en.wikipedia.org/wiki/Reduction_%28complexity%29
http://en.wikipedia.org/wiki/3-satisfiability#3-satisfiability

Choose an instance of the 3-satisfiability problem, that is: a set of
boolean variables A, B, C, etc. and a formula composed of:
	a series of "clauses" joined by AND, consisting of
		a series of variables and their negations joined by OR.
The problem is to determine if there is any assignment of truth values
to the variables which makes the formula true, that is, which makes
true one of the variables or negations in each of the clauses.

For example, choose 4 variables A, B, C, and D, and the formula

(A OR B OR C) AND (B OR NOT-C OR D) AND (NOT-A OR NOT-B OR NOT-D)

This can be satisfied by setting A=TRUE, B=FALSE, C=TRUE, and D=FALSE.

Construct a multipart/mixed with each component labeled
handling=required.  Within that, for each variable, have a part which
is multipart/alternate with 2 parts.  If processing chooses the first
part of the part corresponding to a variable, that will model the
variable being TRUE.  If processing chooses the second part of the
part corresponding to a variable, that will model the variable being
FALSE.

For example, our body starts:

	multipart/mixed
		multipart/alternative;handling=required
			first part corresponding to A (not yet specified)
			second part corresponding to NOT-A
		multipart/alternative;handling=required
			first part corresponding to B
			second part corresponding to NOT-B
		multipart/alternative;handling=required
			first part corresponding to C
			second part corresponding to NOT-C
		multipart/alternative;handling=required
			first part corresponding to D
			second part corresponding to NOT-D

For each clause of the formula, add an additional body part, marked
"Content-Disposition: by-reference; handling=required".  Give the part
a 'cid' URL.  The ability of the recipient to successfully process
this part will model making the corresponding clause TRUE.

For example, our body is now:

	multipart/mixed
		multipart/alternative;handling=required
			first part corresponding to A (not yet specified)
			second part corresponding to NOT-A
		multipart/alternative;handling=required
			first part corresponding to B
			second part corresponding to NOT-B
		multipart/alternative;handling=required
			first part corresponding to C
			second part corresponding to NOT-C
		multipart/alternative;handling=required
			first part corresponding to D
			second part corresponding to NOT-D
		part (not otherwise specified);by-reference;handling=required;cid=clause1
		part (not otherwise specified);by-reference;handling=required;cid=clause2
		part (not otherwise specified);by-reference;handling=required;cid=clause3

We now want to arrange things so that one of the last 3 parts can be
successfully processed only if we choose for processing one of the
earlier parts that corresponds to a variable value that will make the
corresponding clause true.  This is done by embedding forward
references in the variable-corresponding parts that refer to the
clause-corresponding parts.

For example:

	multipart/mixed
		multipart/alternative;handling=required
			first part corresponding to A
				references cid:clause1
			second part corresponding to NOT-A
				references cid:clause3
		multipart/alternative;handling=required
			first part corresponding to B
				references cid:clause1
				references cid:clause2
			second part corresponding to NOT-B
				references cid:clause3
		multipart/alternative;handling=required
			first part corresponding to C
				references cid:clause1
			second part corresponding to NOT-C
				references cid:clause2
		multipart/alternative;handling=required
			first part corresponding to D
				references cid:clause2
			second part corresponding to NOT-D
				references cid:clause3
		part;by-reference;handling=required;cid=clause1
		part;by-reference;handling=required;cid=clause2
		part;by-reference;handling=required;cid=clause3

In order to process this body, the recipient must choose exactly one
of each pair of bodies in the multipart/alternative body parts.  This
choice is equivalent to choosing a set of values for the variables.
The references embedded in the chosen parts refer to the body parts
that correspond to the clauses which are made true by the
corresponding variable's value.  In order to successfully process the
final body parts, the recipient must have chosen a set of variable
values that makes all of the clauses true.

Dale

---

From: Paul Kyzivat <[email-masked]>
Date: Wed, 05 Mar 2008 08:36:36 -0500

Dale,

A very interesting analysis.

A lot of this hinges on what it means to "process" or "handle" a part.

In the case of parts that are not "by-reference" I suppose the meaning 
of handling the part should be included in the definition of the 
content-disposition. (This is currently better for some dispositions 
than others. Its really weak for "render".)

And "by-reference" isn't really different - it needs to define what 
handling means for it too. We need to sharpen that up. And how we do 
that impacts your analysis.

Specifically, if we define "by-reference" to mean that processing it is 
just a matter of making it accessible to be processed by a reference 
then things are ok. In that case it is ok if a reference to it is never 
processed. The only failure is if a reference containing a cid: is 
processed and the referent can't be found because it or some container 
of it was not processed.

	Does that help?
	Paul

---

From: [email-masked]
Date: Wed, 5 Mar 2008 17:30:21 -0500

Does that help?

There's no way of knowing until a clear and allegedly complete set of
rules is enunciated.  The question is not to eliminate this one
problem but to make it verifiable that no problems remain.

Dale