Subject: (out of the blue) OCP header encoding issues

From: Keith Moore <[email-masked]>
Date: Mon, 19 May 2003 18:44:11 -0400

[note: I'm not on this list, and I probably don't care enough about OPES
to follow discussion on the list.  (I have read this thread in the
list archives, but I don't have the broader context).  I have done
some thinking about presentation encodings in protocols, and someone who
knew of that work forwarded this to me and suggested that I follow up.]

Regarding binary vs. text encoding:  There are really three important
aspects to this question -

1. the way records are delimited 
2. the ability to cope with a transmission channel that isn't
   transparent.
3. the ability of humans to read the protocol without specialized tools.

Consideration #2: text is really useful if you're trying to run a
protocol over some antiquated communications channel (like SMTP or
BITNET in the case of MIME) that is transparent to text but not to
arbitrary binary values. It's not clear how useful it is in the context
of a new protocol.

Consideration #3: text is is really useful if the human-readable
protocol elements are ASCII-only, and you're running the protocol over a
bare TCP stream. OTOH if you're trying to support I18N (which you pretty
much have to do these days), or if you want to run over an encrypted
channel, it's not clear how useful it is for the protocol elements to be
ASCII.  But I don't want to discount this too much - being able to
diagnose protocol problems without specialized tools really can be
useful.

This leaves consideration #1 - how records are delimited.  You have
this consideration regardless of whether you use binary or text, and
it's pretty much the same question either way.  Actually I'd say that
how you delimit records is the fundamental question, not whether you
use text or binary.  You basically have two choices: length counts or
end-of-record delimiters.

End-of-record delimeters are attractive in that you don't have to know
the length of a record in advance before you start writing it - but they
do have some disadvantages: you don't know the length of a record before
you start reading it either, and if you're going to want the ability
to transmit arbitrary octet values within a record then you need some
kind of quoting mechanism, which introduces more complexity.   Once you
have that quoting mechanism you can't use ordinary printf statements (or
whatever) to emit protocol bits.

Length counts make transparency easy, but might be unattractive if some
records will be so large that you don't want to buffer the whole record
before transmitting any of it.  

If you try to have both a length count and an end-of-record delimiter,
you immediately need to ask what happens when the two get out-of-sync. 
Which one wins?  Does one win in one implementation and another one win
in a different implementation?  (and do you want inconsistent behavior
across different implementations?)   Does a single broken length count
result in failure to parse subsequent records?  Is the additional
complexity required to maintain both worth the benefit?

other issues:

Typing

How many data types for protocol elements do you need?  Do you want to
coerce everything into "text", or do you want to allow binary integers
also?  Do you need multiple sizes of integers?   Unsigned and signed? 
Floating point?  Special types for things like dates?

(in the case of 822 messages, the vast majority of the attributes are
strings, so expecting everything to be text on the wire is not a huge
problem.  that might or might not be the case for your protocol.)

The fewer types your presentation layer supports, the more you'll need
to explicitly convert between native types and protocol types.  OTOH the
more types your presentation layer supports the greater the potential
for silly states and type mismatches.  (what happens when you need to
store UTF-8 into a string that's supposed to be ASCII?)

Regularity

It's really useful if the decoder (encoder) don't need to have specific
knowledge of the particular protocol elements they're reading (writing).
This is one of the big problems with rfc[2]822/MIME/HTTP/etc headers-
the field delimiters are uniform, but each field has a potentially
different syntax with different delimiters, different rules for
transparency, etc.  (The 822 header structure was adequate to describe
simple plain-text messages, but it's not so good for complex message
structures with lots of descriptive metadata.)

Extensibility 

Sometimes it's really useful if you can add additional protocol elements
to a record (say to extend a protocol) without resulting in an
incompatible record structure.  (822 headers are extensible in that you
can add new fields without changing the meaning of existing fields;
however, it's hard to add new data elements within a field.)

Opacity 

If some of your protocol engines need to pass data from one peer to
another without examining it themselves, it's useful if the protocol can
treat that chunk of data as "opaque" - merely copying it from one peer
to the other without decoding and re-encoding it (and potentially
changing its representation).   Also, if an inner protocol element is
malformed, it's useful it this doesn't break parsing of the outer
protocol element.

Similarly, if you have protocol elements that are going to be subjected
to digital signatures and/or integrity checks, it's useful if the
application can treat those protocol elements as 'opaque' for the
purpose of signing/verification and not always have to deal with them in
decoded form.  (this has been difficult in 822, since there's no clear
distinction between things that are changable in transit and things that
are not) 

Mapping between internal and external representation 

It is useful if there is a good impedance match between internal
(in-memory) and external (on the wire) representation of data elements. 
For instance, if the presentation layer supports arbitrary-length
integers, this is not easily handled by programming languages that
assume fixed-length integers.  Or if the programming language insists
that character strings be in unicode (so that comparisons with string
and character constants work) but the presentation layer doesn't specify
a charset.

Also, any time there is a need to map complex data structures from (to)
a format where variable-length data elements are located by sequential
scanning (e.g. 822 headers, XDR, BER, etc.) to (from) a format where
variable-length data elements are located by following pointers (typical
in-memory representation), there can be a number of efficiency losses.

There is also what I would call "reblocking inefficiency" - if you have
to copy or transform data from one layer in order to use it in another
layer, that slows things down.  An example would be having to copy
multiple lines of an 822 header into a string representing a single
field, then you had to parse that field into individual sub-fields,
then to decode individual sub-fields (like an encoded-word or a
domain name encoded per IDN), etc.

Familiarity and mindshare

Any new bit of technology imposes a learning curve, and many people
naturally prefer immediately starting work with familiar tools, to
learning new tools.  (I'm certainly guilty: I still do much of my
programing in C; the computational linear algebra people I work with
still do lots of theirs in FORTRAN.)

822/MIME/HTTP headers are familiar, but they are also fairly irregular. 
I have written a lot of C code written to handle them- routines to parse
dates, address lists (with comments), content-type fields,
content-disposition fields, encoded-words, addresses, etc. IMHO, their
apparent simplicity is somewhat of an illusion.  Another problem
with having 822 headers appear so simple is that syntax errors are
fairly common.

---

From reading recent messages on the list there seems to be a bit of
support for using 822-style headers, presumably due to familiarity and
mindshare considerations.  If the WG does decide to go this route I
encourage it to define a single syntax which is shared by all fields,
and which provides adequate nesting, etc. for your protocol's needs,
while leaving some room for extensibility. (Offhand I'd recommend
something resembling LISP expressions.)  

However you may find that when you actually think about the whole
protocol that the degree of familiarity and mindshare benefit isn't as
much as you previously thought.

And if you want to consider a reasonably-complete non-text alternative, 
you might take a look at BLOB:

http://www.cs.utk.edu/~moore/draft-moore-rescap-blob-02.txt

BLOB certainly wasn't designed for OPES, but it was designed as a 
representation to store metadata associated with network-accessible
resources.  And it tries to deal with several of the considerations
above.  In particular, the amount of code required to encode or decode
BLOBs is quite small.  The tradeoff is that programs that use BLOBs
manipulate a generic data structure rather than one which is specific to
the PDU in use.  Still, I've written a lot of code to deal with 822
message headers, and I find BLOBs much easier to deal with.

Thanks for reading,

Keith

---

From: Alex Rousskov <[email-masked]>
Date: Mon, 19 May 2003 23:07:52 -0600 (MDT)

On Mon, 19 May 2003, Keith Moore wrote:

> [note: I'm not on this list, and I probably don't care enough about
> OPES to follow discussion on the list.  (I have read this thread in
> the list archives, but I don't have the broader context).  I have
> done some thinking about presentation encodings in protocols, and
> someone who knew of that work forwarded this to me and suggested
> that I follow up.]

Thank you for detailed/thoughtful comments! I hope you will continue to
review our work from time to time. As you may know by now, we have
decided to take the first step towards a text-based protocol. The first
rough draft has been posted [1]. The current version of the BNF (RFC
2234) is quoted below.

        message = name [parameters] [payload] "." CRLF

        parameters = [anonym-parameters] [CRLF named-parameters]
        payload = data

        anonym-parameters = *anonym-parameter
        anonym-parameter = SP value
        named-parameters = *named-parameter
        named-parameter = name ":" SP value CRLF

        name = ALPHA *safe-OCTET
        value = bare-value / quoted-value
        bare-value = <1>*safe-OCTET
        quoted-value = DQUOTE data DQUOTE
        data = size ":" <n>OCTET                     ; n == size

        safe-OCTET = ALPHA / DIGIT / "-" / "_"
        size = %d0-2147483647

Here are 4 examples of short control messages (omitting CRLF at the end
of each message):

     i-am-here.
     data-pause 22 1.
     data-end 22 1 200.
     do-you-support "28:http://iana.org/opes/ocp/TLS".

Here is an example of a more complex message that carries application
data (omitting CRLF at the end of each line):

     data-have 1 3 0 8865
     modp: 75
     x-info: "26:twenty six octet extension"
     8865:<... 8865 bytes of data ...>.

I think we managed to avoid several pitfalls you are talking about
below, but more work remains. Please keep in mind that the current draft
does not necessarily represent any consensus of the working group.

One of the major differences between our protocol and protocols like
HTTP is that we have many very small "control" messages in addition to a
few possibly large messages that carry payloads. HTTP has, essentially,
one shot: a request message has to contain all information about client
desires and a response message has to contain everything about the
server reaction. With SMTP, there are a few control messages but they
are pretty much limited to initial negotiations. We have a bidirectional
pipeline of control and "data" messages.

> ...  Actually I'd say that how you delimit records is the
> fundamental question, not whether you use text or binary.  You
> basically have two choices: length counts or end-of-record
> delimiters.

I agree. We currently use length counts for "unsafe" and possibly large
protocol "atoms" such as complicated parameter values ('quoted-value'
above) or application data ('payload' above). Everything else is
delimiter-based. Thus, we avoid expensive/awkward "octet stuffing" but
keep messages human-friendly.

> End-of-record delimeters are attractive in that you don't have to
> know the length of a record in advance before you start writing it

True. However, as far as basic protocol elements are concerned, in my
experience, you always know the length in advance except for when
writing numbers. If you do not know the length, something else is
broken in the design (e.g., protocol lacks chunking support for raw
data).

IMO, the primary practical feature (some would say advantage) of
delimiters is that they allow for human-friendly syntax. For example,

	GET / HTTP/1.0 CRLF

is much more friendly to a human than the equivalent

	3:GET1:/4:HTTP1:/3:1.02:CRLF

or something of that kind. Note that computer "preferences" are quite
the opposite -- the second example leaves fewer possibilities for errors
in a general context.

> - but they do have some disadvantages: you don't know the length of
> a record before you start reading it either,

This is usually not a problem for performance-sensitive protocols
because their implementations read using raw data buffers anyway. If
one cares about performance, one allocates I/O buffers and not header
structures (where possible).

> and if you're going to want the ability to transmit arbitrary octet
> values within a record then you need some kind of quoting mechanism,
> which introduces more complexity.  Once you have that quoting
> mechanism you can't use ordinary printf statements (or whatever) to
> emit protocol bits.

Yes, quoting (i.e., octet stuffing) is very inefficient because it
requires every agent to look at every octet of the supposedly opaque
data. This is why we are avoiding it in the protocol.

> Length counts make transparency easy, but might be unattractive if
> some records will be so large that you don't want to buffer the
> whole record before transmitting any of it.

That's why chunking support (in some shape or form) is a must for any
modern protocol.

> Floating point?  Special types for things like dates?

We do not have these problems yet (we only have two or three simple
"types" that cover all current needs), but I suspect we may have to
add more types and suffer the consequences.

> (in the case of 822 messages, the vast majority of the attributes
> are strings, so expecting everything to be text on the wire is not a
> huge problem.  that might or might not be the case for your
> protocol.)

Since we decided to start with a text-based approach, we use text for
everything but payload. This is a [performance] problem, but the
current consensus is that readability and ease of ICAP migration are
more important.

> knowledge of the particular protocol elements they're reading (writing).

Yes, this is essential for being able to support extensions. I think we
are OK with the current syntax.

> Extensibility
>
> Sometimes it's really useful if you can add additional protocol
> elements to a record (say to extend a protocol) without resulting in
> an incompatible record structure.  (822 headers are extensible in
> that you can add new fields without changing the meaning of existing
> fields; however, it's hard to add new data elements within a field.)

On a syntax level, our protocol has similar property: it is easy to
add new fields ('named-parameter' above), but not new elements within
a known field. The design assumption is that each field represents an
atomic "thing" that should not need more data elements. However, I am
sure there will be cases when what was perceived as a complete atom
becomes a collection of smaller particles that need more elements for
completeness.

> another without examining it themselves, it's useful if the protocol
> can treat that chunk of data as "opaque" - merely copying it from
> one peer to the other without decoding and re-encoding it (and
> potentially changing its representation).  Also, if an inner
> protocol element is malformed, it's useful it this doesn't break
> parsing of the outer protocol element.

I think our current NetString-like approach for data and metadata
passing works well here.

> Similarly, if you have protocol elements that are going to be
> subjected to digital signatures and/or integrity checks, it's useful
> if the application can treat those protocol elements as 'opaque' for
> the purpose of signing/verification and not always have to deal with
> them in decoded form.  (this has been difficult in 822, since
> there's no clear distinction between things that are changable in
> transit and things that are not)

Good point! Signing payloads should be OK. I think we do not have any
variability in the header syntax, except that a value can be quoted even
if it does not need to be. We will have to decide whether that makes
signing headers difficult _if_ we need to sign them. Added to the to-do
list.

> (in-memory) and external (on the wire) representation of data
> elements.  For instance, if the presentation layer supports
> arbitrary-length integers, this is not easily handled by programming
> languages that assume fixed-length integers.  Or if the programming
> language insists that character strings be in unicode (so that
> comparisons with string and character constants work) but the
> presentation layer doesn't specify a charset.
>
> Also, any time there is a need to map complex data structures from
> (to) a format where variable-length data elements are located by
> sequential scanning (e.g. 822 headers, XDR, BER, etc.) to (from) a
> format where variable-length data elements are located by following
> pointers (typical in-memory representation), there can be a number
> of efficiency losses.
>
> There is also what I would call "reblocking inefficiency" - if you
> have to copy or transform data from one layer in order to use it in
> another layer, that slows things down.  An example would be having
> to copy multiple lines of an 822 header into a string representing a
> single field, then you had to parse that field into individual
> sub-fields, then to decode individual sub-fields (like an
> encoded-word or a domain name encoded per IDN), etc.

While our situation is better than MIME (e.g., we do not have implied
LWS and octet stuffing), we still suffer inefficiency since all
numbers in the protocol are text-based and most computers cannot
compute symbolically. Not sure we can do much better here unless we
switch to binary representation.

> 822/MIME/HTTP headers are familiar, but they are also fairly
> irregular.  I have written a lot of C code written to handle them-
> routines to parse dates, address lists (with comments), content-type
> fields, content-disposition fields, encoded-words, addresses, etc.
> IMHO, their apparent simplicity is somewhat of an illusion.
> Another problem with having 822 headers appear so simple is that
> syntax errors are fairly common.

Our current syntax is very strict, but message headers "look like"
canonical MIME. It remains to be seen whether we stroke the right
balance.

> support for using 822-style headers, presumably due to familiarity
> and mindshare considerations.  If the WG does decide to go this
> route I encourage it to define a single syntax which is shared by
> all fields, and which provides adequate nesting, etc. for your
> protocol's needs, while leaving some room for extensibility.
> (Offhand I'd recommend something resembling LISP expressions.)

I think we did what you are suggesting, except there is no support for
"nesting". Extensions are supported by adding more 'named-parameters' to
a message. Do you know of any text-based protocol that is not XML-based
but supports nesting?

> protocol that the degree of familiarity and mindshare benefit isn't
> as much as you previously thought.
>

Thanks a lot for the pointer (the URL you really meant was [2])! BLOB is
certainly an interesting animal.  If nothing else, it looks simpler and
more straightforward than XDR approach, and may become a candidate if we
decide to switch to the binary path. Are there any production-quality
protocols built on top of BLOB?

Thank you,

Alex.

[1] http://www.measurement-factory.com/tmp/opes/
[2] http://www.cs.utk.edu/~moore/blob/draft-moore-rescap-blob-02.txt

---

From: "The Purple Streak, Hilarie Orman" <[email-masked]>
Date: Mon, 19 May 2003 23:11:40 -0600

Thanks for the words of wisdom, Keith.  I'm sure we'll refer to this
often as we move forward.

Hilarie

---

From: Keith Moore <[email-masked]>
Date: Tue, 20 May 2003 16:23:01 -0400

> Thank you for detailed/thoughtful comments! I hope you will continue
> to review our work from time to time. As you may know by now, we have
> decided to take the first step towards a text-based protocol. The
> first rough draft has been posted [1]. The current version of the BNF
> (RFC 2234) is quoted below.

the first thing I notice is that there's no provision for structure
within a 'value'.  my guess is, sooner or later, you'll need it.
if rfc 822 had had a uniform way of representing lists of things in
message headers, (especially if those 'things' could themselves be 
lists), we probably would not have ended up with such a baroque
assortment of header field syntaxes today.

I don't think the Hollerith constants help much :)  if they're short,
you probably don't benefit much from the count; if they're potentially
long (say more than 1000 bytes), the whole use of record terminators
needs to be re-thought.

I do like the idea to have both named parameters and positional
parameters.  I've considered adding a similar feature to BLOB.

> HTTP is that we have many very small "control" messages in addition to
> a few possibly large messages that carry payloads. HTTP has,
> essentially, one shot: a request message has to contain all
> information about client desires and a response message has to contain
> everything about the server reaction. With SMTP, there are a few
> control messages but they are pretty much limited to initial
> negotiations. We have a bidirectional pipeline of control and "data"
> messages.

that's fine, but it doesn't affect the presentation layer too much -
unless you need to multiplex chunk either control messages or data and
multiplex between them.

> writing numbers.

it can be a pain, because you can no longer "just print" the text and
the delimiters, you now need to emit byte-counted text.

 If you do not know the length, something else is
> the opposite -- the second example leaves fewer possibilities for
> errors in a general context.

actually I disagree- the potential for programmer error is far higher
for the second example, and you'll have far more problems with
programming bugs than you have with transmissions getting corrupted. if
you're going to use a text format, best to keep it simple.

> because their implementations read using raw data buffers anyway.

depends on whether the data elements are smaller than the buffers.

> becomes a collection of smaller particles that need more elements for

that's my guess also.

> I think our current NetString-like approach for data and metadata

you don't have the problem with individual atoms so much as with
aggregates, and I don't see how your proposal supports those.
(for that matter, I don't know whether OPES needs them.)

> variability in the header syntax, except that a value can be quoted
> even if it does not need to be. 

can the order of fields be varied?  is there ever a need to group
several fields together and treat them as an aggregate? 

> canonical MIME. It remains to be seen whether we stroke the right

be aware that having things "look like" MIME means that people will
treat them like MIME, and expect to be able to use MIME headers from
other protocols, wrap long lines like MIME does, add comments, 
use encoded-words, etc.  there's a camel attached to that nose.

> "nesting". Extensions are supported by adding more 'named-parameters'
> to a message. Do you know of any text-based protocol that is not
> XML-based but supports nesting?

seems like I've seen a couple, but don't have references offhand.

> > And if you want to consider a reasonably-complete non-text
> > alternative, you might take a look at BLOB:
> Thanks a lot for the pointer (the URL you really meant was [2])!

thanks for the correction.

> BLOB
> is certainly an interesting animal.  If nothing else, it looks simpler
> and more straightforward than XDR approach, and may become a candidate
> if we decide to switch to the binary path. Are there any
> production-quality protocols built on top of BLOB?

not to my knowledge.  (then again, the same is true of what you're
proposing...).  and who knows, BLOB might just be too ugly or too
unfamiliar.  it's hard for me to tell, since I'm the one who designed
it.  mostly I offer it as an example of where you might end up if you
try to deal with the considerations I listed.

Keith

---

From: Alex Rousskov <[email-masked]>
Date: Tue, 20 May 2003 15:08:17 -0600 (MDT)

On Tue, 20 May 2003, Keith Moore wrote:

> within a 'value'.  my guess is, sooner or later, you'll need it. if
> rfc 822 had had a uniform way of representing lists of things in

I agree that we need to add value "types" of some sort. On the other
hand, our current needs are limited to integers and strings, which are
already supported by the current syntax. It is possible, though not
yet known, that the current syntax will support any value type we will
need. In other words, all our types will be simple atoms.

As for lists of values and such, we will need to decide whether

	named-parameter = name ":" SP value

needs to be replaced with more flexible

	named-parameter = name ":" 1*(SP value)

or whether repeated parameter names (for value "lists") and different
parameter names (for value "structures") should be used instead.

> I don't think the Hollerith constants help much :)  if they're
> short, you probably don't benefit much from the count; if they're
> potentially long (say more than 1000 bytes), the whole use of record
> terminators needs to be re-thought.

The idea behind our use of Hollerith constants or NetStrings in
parameters is to avoid octet stuffing. Record delimiters do not help
if your parameter contains a record delimiter -- you have to use
backslashes or other octet stuffing methods which are ugly and
expensive.

> parameters.  I've considered adding a similar feature to BLOB.

This was partially inspired by BEEP, I think. HTTP has similar feature
(request and status lines), but it is less exposed/obvious.

> it can be a pain, because you can no longer "just print" the text
> and the delimiters, you now need to emit byte-counted text.

... which is equivalent to "just printing" two things, the text length
and the text contents, so I do not sense the pain you are talking
about. Octet stuffing is much more painful because you cannot print
text at all. Instead, you have to print individual characters,
escaping some of them. I guess we just disagree on this [subjective]
subject.

> depends on whether the data elements are smaller than the buffers.

It is not important whether the data element fits (because you do not
parse it; you can stop reading or chain I/O buffers and such to
accommodate large data if needed). What is important is that the octet
counter fits, and it does because it is less than 16 octets long.

> aggregates, and I don't see how your proposal supports those. (for
> that matter, I don't know whether OPES needs them.)

The current syntax can support aggregates by adding or repeating named
parameters:

	s-a: first-atomic-component-of-s
	s-b: second-atomic-component-of-s

or
	l: first-list-element-of-l
	l: second-list-element-of-l

This is probably OK for occasional use, but I agree that we may need
more "direct" support if we find ourselves using the above hack too
often. As I mentioned above, it would be trivial to extend the
named-parameter syntax to support these:

	s: first-atomic-component-of-s second-atomic-component-of-s

	l: first-list-element-of-l second-list-element-of-l

> > > them in decoded form.

Good point again! :-) Named-parameter order is not fixed and extension
parameters can be inserted, adding more variability to OCP "headers".
We will need to address this in a digital signature context. Added to
the to-do list.

> other protocols, wrap long lines like MIME does, add comments, use
> encoded-words, etc.  there's a camel attached to that nose.

True. We already have some warnings against blind MIME usage.
Providing reference implementations and testing services may help a
bit as well. I am sure that no matter what we do, there will be
violations, but I would rather have clear violations of simple syntax
than hidden incompatibilities of MIME implementations.

Thank you,

Alex.