IFX Mail Archive: IFX> Conneg issue

IFX> Conneg issue

From: MAEDA toru (maeda.toru@canon.co.jp)
Date: Sun Nov 26 2000 - 21:40:42 EST

  • Next message: gsonger@netreon.com: "Re: IFX> Minutes from IPP FAX Meeting (Boston)"

    McIntyre-san

    In generally speaking, Conneg-tag has following problems;

    (1) Difficult to analyze
    G3FAX capabilities can be encoded to Conneg-tag, but it is difficult to
    convert opposite direction.
    It is difficult to analyze Conneg-tag by a G3FAX based IFAX system.

    (2) Redundancy of expression
    There is no limit of redundant and complicated expression in Conneg-tag.
    G3FAX capabilities can be expressed in thousands Byte using Conneg-tag format,
    while it can be expressed within 108bit in DIS signal of T.30.

    (3) Standard
    Conneg-tag is standardized as RFC2879,
    while DIS signal of T.30 is not standardized in IETF for fax capabilities
    expression.
    DIS signal of T.30 is well defined and has a proof of inter connectiveties
    between fax manufacturers,
    but Conneg-tag does not.
    We need some Internet Draft for standardization of fax capabilities such as
    DIS MIME type.

    Following is just analogy;
    English can be translated in Esperanto which is synthesized language as a
    perfect language and defined in RFC.
    American people want to use English to communicate each other, but do not
    want to use Esperanto.

    At 11:44 00/11/22 -0800, McIntyre, Lloyd wrote:
    >Paul,
    >The note from Graham Klyne, see below, addresses the conneg combinatory
    >explosion issue raised in item 4 of your meeting summary.
    >
    >Lloyd
    >
    > > -----Original Message-----
    > > From: pmoore@peerless.com [mailto:pmoore@peerless.com]
    > > Sent: Monday, November 20, 2000 8:56 AM
    > > To: ifx@pwg.org
    > > Subject: IFX> Second IPP fax meeting
    > >
    > >
    >---snip---
    > >
    > > 4. We discussed conneg. Somebody with actual implementation
    > > experience pointed
    > > out that it was very unwieldy - you get a combinatory
    > > explosion in most
    > > non-trivial cases. Still nobody has come up with a better idea.
    > >
    >---snip---
    >
    >
    >-----Original Message-----
    >From: Graham Klyne [mailto:GK@Dial.pipex.com]
    >Sent: Tuesday, November 21, 2000 1:35 PM
    >To: McIntyre, Lloyd
    >Subject: Re: FW: IFX> Second IPP fax meeting
    >
    >
    >At 10:34 AM 11/21/00 -0800, you wrote:
    > >Graham,
    > >Any feedback on item 4 below?
    >
    >Lloyd,
    >
    >Yes...
    >
    >Combinatorial explosion can be an issue; for most expressions, I think it
    >is manageable in all but the most memory-constrained environments. I think
    >the fax examples are about as complex as an expression should get. To
    >minimize the combinatorial effect, my suggestions are:
    >
    >(a) don't attempt to expand or simplify an expression until actually trying
    >to match another,
    >
    >(b) use a generate/test strategy that discards unmatched options before
    >proceeding to generate the next. In some cases, a whole branch of the
    >expression tree can be discarded without further expansion. In any case,
    >only possible matches are stored.
    >
    >(c) try to keep simple alternatives (set expressions) together; e.g.
    >rather than expanding
    > (feature=[a,b,c])
    >to
    > (| (feature=a) (feature=b) (feature=c))
    >keep it as a primitive comparison. This will require an extension to the
    >simple expression processing logic so that expressions like:
    > (& (F=[a,b,c]) (F=[a,c,e] )
    >can be reduced to:
    > (F=[a,c])
    >
    >
    >I think it is also possible to perform a degree of "factorization" on the
    >feature expressions, so that alternative constructs containing features not
    >mentioned elsewhere are kept intact (rather than transformed to disjunctive
    >normal form), without changing the ultimate result.
    >
    >
    >I have been planning to add some of these improvements to my sample code,
    >but had never got around to it.
    >
    >
    >When reducing to disjunctive normal form, the main cause of combinatorial
    >explosion is inner disjunctions:
    > (& (| (A) (B) (C) )
    > (| (D) (E) (F) ) )
    >gives rise to:
    > (| (& (A) (D) )
    > (& (A) (E) )
    > (& (A) (F) )
    > (& (B) (D) )
    > (& (B) (E) )
    > (& (B) (F) )
    > (& (C) (D) )
    > (& (C) (E) )
    > (& (C) (F) ) )
    >so any heuristic that limits unnecessary expansion of these can reduce the
    >combinatorial effects. This factor might be considered in designing the
    >construction and combination of feature sets.
    >
    >
    >#g
    >
    >------------
    >Graham Klyne
    >(GK@ACM.ORG)

    *****************************
    Toru MAEDA
    CANON Inc. OIP Technology Adv. 3
    *****************************



    This archive was generated by hypermail 2b29 : Sun Nov 26 2000 - 21:39:29 EST