Subject: RE: OCP header encoding

From: "Martin Stecher" <[email-masked]>
Date: Fri, 16 May 2003 15:07:19 +0200

Alex,

while MIME optimization may be worth to look at, I don't think that your optimization helps a lot.

After parsing the header size you still need to search for the colon, extract the header name and check it by case-insensitive string comparison against your list of supported headers in order to know whether you can skip them or not.
If you then decide to skip, you have the size to forward to the next header.

But the effort to determine the skip-decision is already 95% of the work. The lookup of the CRLF characters in normal MIME headers is only a minor task in header parsing.

If optimizing MIME, the headers or at least standard headers should come with an (optional) header ID which makes it fast to determine which header it is. If that ID is then combined with the size, it could really help.
On the other hand, you will need to deal with some sort of header registration service and solve the customized extension header problem.

And will this then still look like MIME or is it then already close to a binary format?

The application message meta data in the OCP payload will often be MIME headers. Often this meta data is quite long in today's typical applications.
I expect the OCP metadata to be much less.
So, if the application message's meta data needs to be parsed as MIME, does it make much sense to introduce optimized MIME for the OCP metadata?

Although I have some sympathy for optimized MIME and binary formats, I currently prefer to stick with MIME headers for OCP metadata.

Regards
Martin

> -----Original Message-----
> From: Alex Rousskov [mailto:[email-masked]]
> Sent: Thursday, May 15, 2003 11:31 PM
> To: [email-masked]
> Subject: OCP header encoding
> 
> 
> 
> 
> Let's define OCP "headers" as everything transmitted using OCP except
> for application message data and metadata. Application message data
> and metadata is, essentially, OCP payload.
> 
> I can think of four basic ways to encode OCP headers. I will mention
> all four below and then indicate my current choice. If you disagree or
> have any related insights, please let me know.
> 
> 	1. Binary encoding: All headers are encoded using
> 	   well-defined binary structures. Often, binary
> 	   headers have fixed length. They are easy/fast to
> 	   "parse" but difficult to debug. Some binary
> 	   protocols allow for zero-copy implementations
> 	   on network-order machines with appropriate word
> 	   size. Irrelevant message parts or extensions
> 	   are usually easy to skip without much parsing.
> 	   Extensions are usually difficult to support.
> 
> 	   Examples are IP, TCP, DNS, ICP/DHCP, WebMUX, and
> 	   application protocols using XDR (External Data
> 	   Representation) standard. There is no Single True
> 	   Standard for binary headers; everybody reinvents
> 	   the wheel.
> 
> 
> 	2. MIME: MIME headers usually consist of a "special"
> 	   first line followed by name-value pairs formatted
> 	   following one of the MIME-like standards. Canonical
> 	   examples are easy to parse, but 100% compliant
> 	   implementation are probably non-existent due to
> 	   complexity and mess in MIME-related standards.
> 	   Parsing performance is so-so. Debugging and
> 	   tracing is easy. Extensions are easy to add but
> 	   difficult to ignore without parsing them first.
> 
> 	   Examples are HTTP, SMTP, ICAP, BEEP, SIP. There is no
> 	   Single True Standard for MIME headers; everybody
> 	   reinvents the wheel (by altering basic MIME
> 	   requirements and by inventing their own "special"
> 	   first lines).
> 
> 	3. Optimized MIME (for the lack of a better name):
> 	   This approach is similar to MIME, but it optimizes
> 	   encoding to be easily parsable by documenting a
> 	   simple and rigid format. The performance is
> 	   optimized by providing explicit length for
> 	   variable-length structures. Known length makes
> 	   skipping extensions fast. This is still a text-based
> 	   approach so it is not as fast as binary encoding.
> 	   Debugging and tracing is relatively easy, but
> 	   typing a raw message by hand using telnet is difficult.
> 
> 	   I could not find any examples, though several protocols
> 	   use the elements of the above approach, such as
> 	   NetStrings and alike. Here is an illustration:
> 
> 		123-command parameter parameter CRLF
> 		34-name1: value1 CRLF
> 		45-name2: value21 value22 CRLF
> 		...
> 		CRLF
> 
> 	   Where 123, 34, and 256 are lengths of the corresponding
> 	   lines . An implementation can ignore the line without
> 	   parsing most of its content because the size is known
> 	   in advance.
> 
> 	   This approach can be extended to encode the entire
> 	   header so that the size of the entire header is
> 	   known in advance. This approach can be scaled down
> 	   by using known-sizes for certain string values
> 	   only, and not for all headers. Etc.
> 
> 	4. XML (not discussed here since we want to avoid it).
> 
> My current preference is #3. I would consider going binary instead,
> but I think that will scare too many ICAP folks off. I think MIME must
> not be used "as is" because it is virtually impossible to support
> fully and efficiently.
> 
> However I am not quite sure how far we should go in #3 to help
> parsers. If we remove most of the lengths, then ICAP and HTTP folks
> would feel very comfortable. We can just use a strict grammar for line
> formats instead. On the other hand, knowing header sizes in advance
> and skipping unknown extensions is an attractive optimization. Some
> even argue that it improves security because of fewer buffer overruns,
> but I am not sure that's a valid statement.
> 
> Any comments? What would be your preference? We must keep it simple,
> but should we try to make is almost identical to HTTP/ICAP or should
> we optimize further?
> 
> Thanks,
> 
> Alex.
> 
>

---

From: Alex Rousskov <[email-masked]>
Date: Fri, 16 May 2003 08:46:44 -0600 (MDT)

On Fri, 16 May 2003, Martin Stecher wrote:

> After parsing the header size you still need to search for the
> colon, extract the header name and check it by case-insensitive
> string comparison against your list of supported headers in order to
> know whether you can skip them or not. If you then decide to skip,
> you have the size to forward to the next header.

I disagree. Here is an optimized version:

	1. Parse the length (one scan until you find a non-digit).
	2. Check characters at two or three positions within the
	   now-isolated header (while traversing your recompiled
	   "known headers" tree that tells you which positions to
	   look at).
	3. If any position does not match, you are done -- this
	   is not a header you care about. If all positions match,
	   you know the unique name of the header you care about,
	   proceed.
	4. Check the candidate header name using strncmp (one scan).

I do not know whether the above optimization is common, but we use it
successfully in Web Polygraph for HTTP headers. If you take a list of
all headers you care about and build an optimized decision tree for
that list, you will see that 1, 2, or 3 character lookups is usually
all it takes to identify any known candidate, even for a long name
list. This is because header name strings are rather "long", while the
information they carry is very "short".

What makes it slower in HTTP is that you still have to parse any MIME
header you decided to skip.

Furthermore, we can define all headers to be case-sensitive (I do not
see why not) and come up with very short names. Actually, a few
MIME-based protocols (e.g., SIP) even allow for short "aliases"! For
example, "From" is equivalent to "f", "Call-ID" is equivalent to "i".

> But the effort to determine the skip-decision is already 95% of the
> work. The lookup of the CRLF characters in normal MIME headers is
> only a minor task in header parsing.

The above optimization makes skip-decision very cheap. Also, if an
implementation just looks for CRLF to find the end of a MIME header
field, that implementation violates MIME. CRLF alone does not
terminate a field ( "CR LF not-space" does, but only in simple,
canonical cases).

> If optimizing MIME, the headers or at least standard headers should
> come with an (optional) header ID which makes it fast to determine
> which header it is. If that ID is then combined with the size, it
> could really help. On the other hand, you will need to deal with
> some sort of header registration service and solve the customized
> extension header problem.

See above for a solution that does not require a registration service
or IDs while providing almost equivalent benefits.

> And will this then still look like MIME or is it then already close

The only visual difference is that every "line" starts with a number.
It is still a true text-based format.

> The application message meta data in the OCP payload will often be
> MIME headers. Often this meta data is quite long in today's typical
> applications.

True.

> I expect the OCP metadata to be much less.

I agree, at least for the bulk of OCP messages.

> So, if the application message's meta data needs to be parsed as
> MIME, does it make much sense to introduce optimized MIME for the
> OCP metadata?

It may make sense because:
	- not all OCP agents would care or even know about MIME
	  metadata, while all OCP agents have to care about OCP headers
	- OCP headers are used with all OCP messages while MIME
	  metadata is used with just a few (those meta-have
	  messages that pass metadata to the other side).
	- using MIME "as is" will produce many OCP implementations
	  that will not pass compliance tests

Finally, it is probably possible to make the new format parsable by
old MIME code with no or minimum changes (depending on the old code
interface). Working on it...

> Although I have some sympathy for optimized MIME and binary formats,
> I currently prefer to stick with MIME headers for OCP metadata.

Noted. Perhaps some of the above arguments may tilt your preference in
the other direction. If not, perhaps the simplicity of the format will
(when it is published). If not, we can still go back to the bad old
MIME once optimization details are known and considered.

Thank you for a prompt feedback!

Alex.