Subject: Re: Compact name for CSeq: (and for everything else)

From: Henning Schulzrinne <[email-masked]>
Date: Sun, 30 May 1999 11:12:54 -0400

Scott Petrack wrote:
> 
> For a particular application I am doing I have a severe bandwidth
> constraint, and since CSeq: is a mandatory field, I would like to ask that
> you bless a compact name for it. I'll vote for "q".

The one problem I have with creating abbreviations for headers such as
CSeq is that it immediately breaks all implementations. This wouldn't be
so bad for informational headers (Organization, Subject, Priority, etc.)
[and we might indeed want to do this], but is more serious for headers
like CSeq, which are necessary for a proxy or UAS to process the
request. Given that the savings is 3 bytes, I have to admit to a certain
reluctance to breaking all existing implementations. (I know that we
have no "legal" obligation to be backward compatible as we move to Draft
Standard, but it doesn't exactly help the reputation of the protocol to
make what may seem like gratuitous, but crucial, changes to basic
aspects of it.)

Assuming you are carrying a real media stream, I have to assume that
your access bandwidth is at least 2.4 kb/s. At that rate, a 200-byte SIP
request would take about one second to transmit. Not great, but you can
still get decent post-dial delay performance.

If you have a continuous stream, it might be better to use a lower-layer
compression mechanism (such as those in PPP). They will automatically
reduce CSeq to a few bits, as the string will make it quickly into the
dictionary. Thus, if you compare the actual on-the-wire bit count of an
INVITE with Cseq and an INVITE with q, I wouldn't be surprised if there
would be no difference in size at all.

To test the hypothesis, I created some SIP-only INVITE request of the
form

INVITE Y&,=n#)&); SIP/2.0
v:SIP/2.0/UDP bcde
f:petrack
t:Y&,=n#)&);
q:1 INVITE
c:application/sdp
l:100

where the To and request-URI are randomly generated 10-character strings
and the From and Via headers are constant. I'm assuming here that the
proxy adds the local domain, for example. When "sending" 13 of these
requests, each with a different random request-URI, To and Length, we
get the following results for the total of 13 requests and the average
request size:

using Cseq: uncompressed=1345 bytes (103 bytes/request); gzip'ed: 353
bytes (27.15 B/r)
using q:    uncompressed=1306 bytes (100 bytes/request); gzip'ed: 352
bytes (27.07 B/r)

Thus, for this example, we get a grand effective saving of 0.08 bytes
per request, or a little more than 0.6 bits/request. I'd imagine that
this saving gets even smaller as the number of INVITE requests increase.

> 
> In the next version I would be happy to see *every* header field have a
> one-letter compact form. If you make the compact form case sensitive this
> is easily done, otherwise perhaps you'll choose a character other than
> ":" (colon) for the second byte. (e.g. make the compact form of
> "Authorization" be "a:" and the short form of "Accept:" be "a/"). At
> the very least let's have a short form for the more common optional
> headers. (I need one for "Warning:", for error processing).
> 
> I know that many people have OC-48s to the desktop, but I don't have one
> to my wireless PDA (no, that's not my application ;-)). And while it is
> true that some of the fields are of necessity very long (like long sip
> addresses), I can deal with that by rewriting certain names in proxies.
> Of course I can use the same proxies to rewrite "CSeq:" as "q:", but I
> think there is a big win if we can all agree on compact encodings that we
> can all use.
> 
> Could we all agree on a letter NOW at least for the mandatory CSeq: field?
> If no one cares I vote for "q:", just because it's in CSeq and is not
> too common. If one of the SIP authors would publish a complete list of
> compact names, that would be great. (I vote for "w:" for Warning:)
> 
> Thanks,
> 
> Scott

-- 
Henning Schulzrinne   http://www.cs.columbia.edu/~hgs

---

From: Scott Petrack <[email-masked]>
Date: Tue, 1 Jun 1999 15:05:12 -0400 (EDT)

OK, I'll come clean.

1. I want all SIP headers to be fixed length. All the compact forms have
two bytes (a letter and a colon), and I would like to be able to 
process a lot of headers very quickly. 

2. As far as backward compatibility goes, in any 
case the standard says I have to accept the long and the short form from
an "older system". 
If I start talking to a system that doesn't understand the new compact
form, I will get a "bad request" error, and I hope the correct Warning:
line with decent warn text, and I promise I will send the long form. 
But for the few million messages I intend to process, the gain of 
having fixed length headers on processing is very useful.

Scott

---

From: Scott Petrack <[email-masked]>
Date: Sun, 30 May 1999 10:43:55 -0400 (EDT)

For a particular application I am doing I have a severe bandwidth
constraint, and since CSeq: is a mandatory field, I would like to ask that
a compact name be chosen for it. I'll vote for "q". 

Could the authors publish a letter at least for the mandatory CSeq: field?
If no one cares I vote for "q:", just because it's in CSeq and is not
too common. If you could fix a complete list of  compact names, that would
be great. (I need one now for "Warning:", maybe "w"), but 
in the meantime, just the Cseq: would be very helpful indeed.

Thanks, 

Scott

---

From: Henning Schulzrinne <[email-masked]>
Date: Tue, 01 Jun 1999 17:54:08 -0400

> process a lot of headers very quickly.

My hunch is that the difference in processing speed will be completely
invisible. You can still have a "fast path" that checks whether this is
a X: case. If not, you go into slow path for the one or two headers that
are not. Slow path here means an extra strcmp. You can even compare CSeq
to an integer in one instruction, if you like (kind of why ftp commands
were 4 characters long)...

---

From: Mark Handley <[email-masked]>
Date: Tue, 01 Jun 1999 15:00:03 -0700

>were 4 characters long)...

I have to agree with Henning here - I can't see a case where I really
believe this will make any significant difference.  I'd prefer not to
make any changes to the spec that adversely affect its stability
unless there's a really strong case.  

Cheers,
	Mark

---

From: Christian Huitema <[email-masked]>
Date: Tue, 1 Jun 1999 18:33:58 -0400 (EDT)

On Jun 1,  3:05pm, Scott Petrack wrote:
> Subject: Re: Compact name for CSeq: (and for everything else)
> OK, I'll come clean.
>

I would support Scott there. There is a lot to be gained in terms of
performance if the headers are short, and 2 bytes is as short as it gets.
 It enables a number of fast path optimizations, etc.

> case the standard says I have to accept the long and the short form from

Basically, this means that any long version will be treated out of the
fast path.  This is probably OK, since the emphasis would be on
compatibility, or user readability.

-- 
Christian Huitema
------------------------------
Please note my new address: [email-masked]
http://www.telcordia.com/

---

From: Eric Zimmerer <[email-masked]>
Date: Tue, 01 Jun 1999 17:35:01 -0600

Scott,

I read your confession with great sympathy.  

Level 3 and other carriers intend to send large volumes of SIP+ messages,
and the benefits of compact standard length headers are substantial.

Eric Zimmerer
Level 3 Communications, Inc.
Phone: 303-926-3142

OK, I'll come clean.

Scott

---

From: Henning Schulzrinne <[email-masked]>
Date: Tue, 01 Jun 1999 19:51:04 -0400

> and the benefits of compact standard length headers are substantial.

Since we are doing engineering here, would somebody please quantify
"substantial"? All my measurements indicate that parsing header names
itself plays no significant role, with or without abbreviation. Code
like

union line {
  int w;
  char c[...]
}

switch line.c[0]
C:
  /* using 4-byte comparison here */
  if (line.w == 'CSeq') {
  }
f: "from" code
t: "to" code
etc.

is within a microsecond of code without the extra CSeq header bytes.

The damage done to the protocol due to divergent versions and the extra
testing due to error conditions is far higher than the microsecond
saved.

Thus, before you make blanket statements, may I ask you (plural) to
please at least provide pseudo code and preferably measurements before
calling for major changes? That said, Eric, I really think you should
change your email address. It is at least 13 bytes too long. [email-masked]
must save each SMTP agent at least a millisecond or two. (And remember:
there already are and always will be far more email messages than phone
calls....) :-)

---

From: Jonathan Rosenberg <[email-masked]>
Date: Tue, 01 Jun 1999 20:15:10 -0400

> and the benefits of compact standard length headers are substantial.

I think some quantitative analysis would help here. So, here's a minimal
SIP message, with minimal SDP:

INVITE sip:a SIP/2.0
f:sip:b
t:sip:b
i:0@0
CSeq:0 INVITE
c:application/sdp
l:73

v=0
o=a 0 0 IN IP4 1.1.1.1
s=a
t=0 0
m=audio 1 RTP/AVP 0
c=IN IP4 2.2.2.2

The SIP component has 80 bytes (don't forget the CR), and the SDP has
73. A SIP message without SDP could be 57 bytes (remove the Content
Length and Content Type headers). So:

                   Size with CSeq     Size with q    %reduction
SIP w/ SDP            153                150             3/153 = 1.96%
SIP w/o SDP            57                54              3/57 = 5.2%

So, we are not talking significant reductions, particularly in the
presence of SDP (the typical case). In the case of SIP+, there would
also be an ISUP payload (I'm not sure of the size), so the reduction is
probably less than 1%.

If we couple this with RTP, its even less. Lets assume a low rate code,
say 5.3 kbps g.723.1, and the average 3 minute call. Lets be
conservative, and go for a 120ms packetization delay. Thats 79.5 bytes
of payload, + 12 for RTP (I'll ignore UDP/IP since I did for the SIP
computation) = 91.5 -> 92 bytes per packet. There are 1500 packets in a
3 minute call (180 s / 120ms), for a total of 138,000 bytes total. This
is way way more than the 350 bytes it would roughly take for the
transaction.

> having fixed length headers on processing is very useful.

Alas, compatibility isn't that simple. Unknown headers are ignored. So,
since "q" is unknown, it will be ignored by both proxies and UA's. You
can force it to be recognized (and thus get the error back that you
mention), but this needs a Require header AND a Proxy-Require header.
So, the 3 bytes you save on CSeq are totally lost to Require and
Proxy-Require. There is no short form for Require/Proxy-Require either,
but even if there was, it would still be more than three bytes for the
whole thing.

-Jonathan R.

-- 
Jonathan D. Rosenberg                       Lucent Technologies
Member of Technical Staff                   101 Crawfords Corner Rd.
High Speed Networks Research                Holmdel, NJ 07733
FAX: (732) 834-5379                         Rm. 4C-526
EMAIL: [email-masked]
URL: http://www.cs.columbia.edu/~jdrosen

---

From: Jonathan Rosenberg <[email-masked]>
Date: Tue, 01 Jun 1999 22:29:27 -0400

Oops. It was pointed out to me that the UAS (and the proxy) would still
choke on the request with "q". This is because it would not see a CSeq,
and thus return a 400 error thinking the request was malformed. The UAC
could then resubmit the request with the full CSeq.

The problem I describe would exist for non-mandatory headers, though.

-Jonathan R.

> Jonathan Rosenberg wrote:
> >
>

---

From: Scott Petrack <[email-masked]>
Date: Fri, 4 Jun 1999 00:52:04 -0400 (EDT)

Jonathan,

I thought it was a stroke of luck that there wasn't a short form
for CSeq:, which is mandatory.
It gives us the opportunity to say that "any implementation
which understands "q:" MUST understand ALL the compact forms." 
Since as you noticed, CSeq will get back an error, it can be used to check
all the others. 

This mechanism is efficient enough, it seems to me. A client or server
will learn
pretty quickly whether a particular server or client can handle the new
short form, and act accordingly. 

(BTW, I realize I was also wrong before -- Proxy-Authenticate and
Proxy-Require cannot be distiguished by the first two bytes. I would 
choose compact forms like "p-" and "r-" for these ;-)).

Scott

[BTW, sorry Jonathan, you're not getting personal mail from me, I forgot
that the bell-labs.com smtp server won't accept mail from my linux box
because my box's DNS name doesn't reverse resolve. But you'll get this
through confctrl....]

---

From: Scott Petrack <[email-masked]>
Date: Fri, 4 Jun 1999 00:13:07 -0400 (EDT)

> were 4 characters long)...

Henning, your note seems very pursuasive, it seems to me:

1. I am asking that all "common" SIP headers (at least) be of fixed
length, in the same way that "kind of why ftp commands are 4 characters
long". 

I want a "fast path" for EVERY required header. If SIP is going to be used
to route a LARGE number of invitations, it definitely helps to have all
headers be of a fixed length. I realize that in many  applications
there is not a big win, because there is so much string processing going
on, but surely you can see that there are applications where this can be 
reduced to a minimum and fixed length fields can make for vastly simpler
implementations.

Yes, I am aware that Cseq is 4 bytes, but then I have to throw away the
Colon.  And there are other fields
that are not 4 bytes. yes, I can just compare the first 2, and then 
throw away the rest, but this is nervewracking, and also less fast.
Why not just write down a list so that we can all use the same one? It is
a very short list (there are about 40 header fields in all now). 

As I argued before,
there is no backward compatibility problem -- an implementation that
cannot understand the new compact form will return a 400 Bad Request and
then the implementation will know to try the long form. If I can't figure
out in advance which to use, it will only slow down my server, so clearly
it's in my interest to do it correctly. 

I'm not suggesting that everyone do this, only that there be a single list
of compact forms. 

At the very least I'd like it written down that  all SIP headers will have
unique two first bytes.

I am finding that parsing of the variable length header fields is a
significant overhead in my application, and that moving to fixed length
headers makes for simple fast clear code. That's all.

Scott

---

From: Scott Petrack <[email-masked]>
Date: Fri, 4 Jun 1999 00:24:38 -0400 (EDT)

The issue is not so much *compact* headers, as much as *single fixed 
length* headers. In fact, fixed 2 byte length headers (although 4 would be
okay too, as Henning points out). Fixed length headers that can be
compared in a single instruction make a *huge* difference when processing
large numbers of packets, compared to a strcmp.

Today, it is possible to read the first two bytes of each required header
and "guess" the rest. But there is no guarantee that this will work
forever.

It is true that HTTP's progress did not suffer because of the strcmps
needed to implement an HTTP server. But surely it is well known that the
strcmps slowed processing down? 

All I want to do is to avoid as many strcmps as possible, by extending
work already done in a backward compatible manner.

Scott

---

From: Lars Berggren <[email-masked]>
Date: Fri, 04 Jun 1999 11:32:17 +0200

> it's in my interest to do it correctly.

How does the server know which CSeq to use in the 400 response if it
does not understand the compact name for that header? How will it detect
retransmissions of the same request? However, this seems to me like a
more general problem of returning a failure response when the request
was malformed.
/Lars

-- 
Lars Berggren       <[email-masked]>
Intertex Data AB    tel: +46-8-6282828
Sundbyberg, Sweden  fax: +46-8-6286414

---

From: Anders Kristensen <[email-masked]>
Date: Fri, 04 Jun 1999 12:24:10 +0100

> large numbers of packets, compared to a strcmp.

I have a couple of problems with this proposal.

First, changing the ':' separator to a '/' makes SIP even more
incompatible with RFC822 and HTTP.  IMHO this is not an option. This is
only a problem because there's only 25 US-ASCII letters, but actually,
given that SIP headers are all Unicode theres's no shortage of
single-letter names to choose from. We could start using the danish
letters æ, ø, and å right now ;-).

Secondly, I think in general having optional forms for things is just a
bad idea. It was a bad idea to make RCF822 headers names
case-insensitive but that we have to live with now. I think it was
probably also a bad idea to allow compact forms for various SIP headers.
It means parsers and higher level code has do *more* work, not less, and
it actually makes other optimizations harder to do.

Thirdly, the gain you're talking about is likely to be noise compared to
other processing (usually) going on.  Just consider the overhead of
parsing and constructing an in-memory representation of From, To, and
Contact headers.  Anyway, my 'gut feeling' is that servers can easily be
engineered to cope with the overhead of SIP as it stands.

> strcmps slowed processing down?

But like you say, it hardly had any effect on the popularity of the Web,
since processing power was quite adequate to handle it. In fact it was
far more important that the protocol was simple. Your proposal is IMHO
an unnecessary optimization. It adds special cases to the protocol for
small (and undocumented) gains.

Sorry for posting so much opinion and so little Scientific Truth ;-)

Cheers,
Anders

-- 
Anders Kristensen <[email-masked]>,
http://www-uk.hpl.hp.com/people/ak/
Hewlett-Packard Labs, Bristol, UK

---

From: Anders Kristensen <[email-masked]>
Date: Fri, 04 Jun 1999 12:30:46 +0100

> short form, and act accordingly.

So you're saying that the 'q' short form for 'CSeq' is a backwards
compatible change because the caller will be able to figure out when a
callee is incompatible because the protocol will just break down.  I
don't know if this can be called backwards compatibilty.

Anders

---

From: Henning Schulzrinne <[email-masked]>
Date: Fri, 04 Jun 1999 09:37:04 -0400

> large numbers of packets, compared to a strcmp.

Given that the difference is *huge*, it should be easy to quantify. So
far, there has been no indication of any experiment that indicates any
difference, absolute or relative, but (I hope) I provided a plausible
explanation why keeping CSeq as is makes no perceptible difference.

To emphasize: we are talking about one extra if and equality comparison
for each packet, since presumably the other (non-Cseq) headers of
interest are already short. This probably works out to a few RISC
instructions. With branch prediction, I'd be surprised if this adds more
than 1 microsecond of packet processing delay.

Presumably your server isn't just inspecting SIP requests for their
inherent beauty, but rather doing something interesting with them.
Anything interesting, such as a database lookup or script execution, is
going to take more than one hundred times the parsing cost, in my
estimation (and measured experience).

> and "guess" the rest. But there is no guarantee that this will work

Since it is unlikely that we will add more mandatory headers, this will
not be a problem for proxies.

> strcmps slowed processing down?

If it is *well known*, one might be able to produce a citation. Again, I
think it is reasonable that people who want to introduce yet more
special cases prove their case by more than just assertion.

---

From: Jonathan Rosenberg <[email-masked]>
Date: Fri, 04 Jun 1999 09:39:30 -0400

> more general problem of returning a failure response when the request

This is a good point. The server will probably not reflect the "q" in
the 400 response. Mine won't at least, since it only copies the fields
it knows about into the response. In general, I think it would be a bad
idea for a server to copy headers from the request into its responses if
it didn't understand the header. This means that the client which sent
the q would need to be prepared to match responses to its request where
the q was missing. This seems a real pain.

Detecting retransmissions of the same request at the server is not a
problem, since the retransmitted requests still match the original one,
even though they are malformed. 

Scott - I, along with others I think, have a hard time with the claim
that making all the header fields a fixed length is such a big savings.
Yes, you can avoid a few strcmps, but compared to other operations (say
loop detection, handling retransmissions, Via processing, and parsing
the rest of the message (especially line folding)), it seems like a drop
in the bucket. Can you perhaps explain *why* this is such a huge
savings? 

Thanks,
Jonathan R.

---

From: Anup Rao <[email-masked]>
Date: Fri, 04 Jun 1999 08:15:21 -0700

Scott Petrack wrote:

[SNIP]

> strcmps slowed processing down?

Way back when we had the text vs. binary debate for RTSP, I concluded that this was not an issue. I
think the top 2 things to deal with in a HTTP server are :-

a) Connection setup/management
   (particularly with one connection/transaction)
b) Network I/O and File I/O

And the fact that you need to make system calls for both a), b).

In contrast, strcmps dont come close since  they are implemented in the calling process's space.
Agreed that this point of view is somewhat Unix-centric but I dont see how they can change much in
any OS.

Not that I am denying that strcmps are slower than comparing ints/longs :).  SIP does not really
have to deal with a) or b) above and so one is surely tempted to save on header parsing - but that
does not go far. From/To/Via processing is happens almost as often(in terms of order) as the base
message parsing, and is pretty complex. I think the bottom line is that this is the price one pays
for extensibility. 

-Anup.

---

From: "David Oran" <[email-masked]>
Date: Wed, 16 Jun 1999 11:10:55 -0400

Who said you had to do STRCMPS? You could do a 26-way TRIE and get your
answer in Log(n) memory references for headers unique in N characters.
Variable length doesn't need to cost much at all.

Anyway, I thought this all started with bandwidth savings (which doesn't
seem to matter either here...).

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]On Behalf Of
> Scott Petrack
> Sent: Friday, June 04, 1999 12:25 AM
> To: Eric Zimmerer
> Cc: [email-masked]; [email-masked]; [email-masked];
> [email-masked]; Henning Schulzrinne
> Subject: Re: Re[2]: Compact name for CSeq: (and for everything else)
>
>