Subject: Re: [lemonade] compression

From: Arnt Gulbrandsen <[email-masked]>
Date: Mon, 13 Mar 2006 18:39:54 +0100

Finally following up the short thread last autumn with some numbers, 
here's a short comparison of RFC 3749, draft-gulbrandsen-imap-deflate 
and draft-lemonade-lzip.

RFC 3749 and imap-deflate are very similar in terms of compression. In 
general, RFC 3749 will win over imap-deflate by about 20 bytes, 
independently of the length of the IMAP connection. Two minutes or two 
hours, doesn't matter. The difference is because 3749 negotiates 
compression at a cost of just two bytes (one in the client hello, one 
in the server).

For the IMAP conversation appended, here are the results comparing 
3749/deflate with lzip. These numbers are approximate: I took some 
working code and hacked it to produce numbers instead of work. I 
accidentally mangled the line endings, so all the numbers are off by 
some small factor (1%?).

The thread I used is just a few messages from lemonade. I just picked a 
random thread, and read a few messages using a fairly popular IMAP 
client, and played with the TCP connection until all passwords etc. 
were gone.

There are four commands, each with 1-4 untagged and one tagged response. 
I have numbered them a1 to a4.

Command a1 is compressed by all three to 42 bytes, much worse than its 
original 22. Its response is compressed to 70 bytes, from 123. The 
reason they do the same is that all three compressors use the same 
algorithm and do exactly the same work: Starting compression (which has 
overhead of about 20 bytes IIRC), learning that the compressed text 
contains ASCII, etc.

Command a2 is compressed by lzip from 202 to 170 bytes, and by 
3749/deflate to 138. The response is compressed by lzip from 3498 to 
1016 bytes, and by 3749/deflate to 899. lzip does worse than the two 
others because it pays the startup cost again, while the two others 
already have trained their compressors to know that there's lots of 
printable ASCII, '* FETCH' occurs often, etc.

Command a3 is compressed by lzip from 20 to 40 bytes (the same as the 
first command, really) and by 3749/deflate to 9 bytes. (Lzip pays the 
startup cost for the seventh time. The compressors in 3749/deflate have 
learnt from commands a1 and a2 approximately how an IMAP command looks, 
so they compress even a short command efficiently.) The response tells 
the same picture: 3749/deflate compresses the response from 2772 to 
1112 bytes, lzip manages 1284. The difference here is mostly that 
3749/deflate already knows that almost all bytes sent are ASCII words, 
while for lzip, the compressor has to learn it. There's also the usual 
20-byte startup fee.

Command a4 is 40 bytes again with lzip. With 3749/deflate it's 22. The 
response has an original size of 1078 characters. 3749/deflate 
compresses that to 280 characters. This result is so good becaus the 
response is pure text, and it's in the same thread as the a3 response. 
lzip doens't do so well: 559. Its compressor again has to learn 
everything from scratch, and it can't exploit the fact that threads 
frequently contain the same words and even sentences.

Summing up: All three lose a bit on their first command, about 20 bytes. 
3749/deflate win on the second and subsequent command. Lzip wins on the 
big command, loses on the two small commands. All three win on the 
responses, but 3749/deflate win much more, sometimes achieving results 
half the size of lzip's.

I'll be happy to repeat this survey with a bigger corpus, if it's 
desirable. I don't see the point, myself. The numbers are clear enough 
already.

Finally, I don't know whether the upstream comparison matters. I 
included the numbers because I thought they might matter for 
battery-powered devices where transmitting bytes to the server is 
expensive. Not my field. Downstream surely matters, and that's where 
3749/gulbrandsen win by a large margin.

Arnt
_______________________________________________
lemonade mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/lemonade

---

From: Tony Hansen <[email-masked]>
Date: Thu, 16 Mar 2006 18:16:21 -0500

Given the choice between draft-ietf-lemonade-compress-00.txt and
draft-gulbrandsen-imap-deflate-02.txt, I think that the latter,
draft-gulbrandsen-imap-deflate-02.txt, is a *better* choice to go
forward with as a solution for compression of the IMAP stream.

As I've said before, I think that Arnt's method is much simpler. And as
his measurements indicate, it also provides superior performance.

I'd like to nominate draft-gulbrandsen-imap-deflate-02.txt to *replace*
draft-ietf-lemonade-compress-00.txt as the group's compression mechanism
of choice.

	Tony Hansen
	[email-masked]

Arnt Gulbrandsen wrote:
> compression at a cost of just two bytes (one in the client hello, one in
> the server).
> 
> client, and played with the TCP connection until all passwords etc. were
> gone.
> 
> the same picture: 3749/deflate compresses the response from 2772 to 1112
> bytes, lzip manages 1284. The difference here is mostly that

---

From: Ned Freed <[email-masked]>
Date: Thu, 16 Mar 2006 17:50:48 -0800 (PST)

> forward with as a solution for compression of the IMAP stream.

I agree 100%. IMO the choices are between draft-gulbrandsen-imap-deflate-02.txt
and using TLS-layer compression (sorry, don't remember the RFC number). Either
one of these would be acceptable IMO.

> his measurements indicate, it also provides superior performance.

SImpler and superior compression are hard to argue with. I note that there are
probably ways to make the compression work better in
draft-ietf-lemonade-compress-00.txt  (by saving compression state between
commands) but this increases the complexity even more.

> draft-ietf-lemonade-compress-00.txt as the group's compression mechanism

+1

				Ned

---

From: "Stephane H. Maes" <[email-masked]>
Date: Thu, 16 Mar 2006 18:02:06 -0800

The comparison on compression seems to be a bit outdated as it seems based on old LZIP spec. Following the agreements from Beijing, we aren't even compressing commands anymore, so the TLS comparison is apples to oranges.

We are only compressing body parts, as such, TLS might win for compressing command syntax, but the one test that wasn't checked is TLS compressing an already compressed part...

Also attachment compression is essential. It is not clear if the test looked at that. IETF mailing lists do not really provide attachment use cases.... :)

So I don't think that it is a clear cut or that the numbers + argument below motivate yet supperiority of ne method over another. At least more evaluations are needed. Note I have no problem switching method if it turns out more efficient.
 
Thanks

Stephane

_____
Stephane H. Maes, PhD,
Director of Architecture, Mobile, Voice, and Communications Platforms, Oracle.
Ph: +1-203-300-7786 (mobile/SMS); Fax / Office UM: +1-650-607-6296
e-mail: [email-masked]
IM: shmaes (AIM/Y!/skype) or [email-masked] (MSN Messenger) or [email-masked] (Google)
 
-----Original Message-----
From: Tony Hansen [mailto:[email-masked]] 
Sent: Thursday, March 16, 2006 3:16 PM
To: Enhancements to Internet email to support diverse service enivronments
Subject: Re: [lemonade] compression

Given the choice between draft-ietf-lemonade-compress-00.txt and draft-gulbrandsen-imap-deflate-02.txt, I think that the latter, draft-gulbrandsen-imap-deflate-02.txt, is a *better* choice to go forward with as a solution for compression of the IMAP stream.

As I've said before, I think that Arnt's method is much simpler. And as his measurements indicate, it also provides superior performance.

I'd like to nominate draft-gulbrandsen-imap-deflate-02.txt to *replace* draft-ietf-lemonade-compress-00.txt as the group's compression mechanism of choice.

	Tony Hansen
	[email-masked]

Arnt Gulbrandsen wrote:
> The thread I used is just a few messages from lemonade. I just picked 
> a random thread, and read a few messages using a fairly popular IMAP 
> algorithm and do exactly the same work: Starting compression (which 
> has overhead of about 20 bytes IIRC), learning that the compressed 
> text contains ASCII, etc.
>
> startup cost for the seventh time. The compressors in 3749/deflate 
> have learnt from commands a1 and a2 approximately how an IMAP command 
> looks, so they compress even a short command efficiently.) The 
> response tells the same picture: 3749/deflate compresses the response 
> from 2772 to 1112 bytes, lzip manages 1284. The difference here is 
> mostly that 3749/deflate already knows that almost all bytes sent are 
> ASCII words, while for lzip, the compressor has to learn it. There's 
> also the usual 20-byte startup fee.
>
> 3749/deflate win on the second and subsequent command. Lzip wins on 
> the big command, loses on the two small commands. All three win on the

---

From: Arnt Gulbrandsen <[email-masked]>
Date: Fri, 17 Mar 2006 11:15:08 +0100

Oh, I didn't realize that lzip was dead. The new one looks considerably 
better in terms of protocol quality, but I fear it's even worse in 
terms of compression.

I'll do a comparison later today, perhaps tomorrow. I'll just tack 
another message with a big attachment onto the four-message thread I 
posted earlier, using different big attachments. Some PDFs, a word file 
or two, a zip file, etc.

Arnt

---

From: Dave Cridland <[email-masked]>
Date: Fri, 17 Mar 2006 11:22:05 +0000

On Fri Mar 17 10:15:08 2006, Arnt Gulbrandsen wrote:
> another message with a big attachment onto the four-message thread 
> I posted earlier, using different big attachments. Some PDFs, a 
> word file or two, a zip file, etc.

Whilst I'm basically in favour of stream compression based methods 
(TLS, COMPRESS=DEFLATE, etc), I feel I ought to note two advantages 
of LZIP-like mechanisms:

a) They're free to use alternate compression algorithms which don't 
make sense for streaming data, or are relatively expensive, since 
they're operating on a-priori known immutable data. So an LZIP-a-like 
could be made to use a Burrows-Wheeler Transform, or an Arithmetic 
Coding with prearranged model presets, or any number of other 
relatively expensive algorithms.

b) For data that is not compressed by whichever algorithm is used, 
the mechanism could return BINARY fetch items instead of LZIP fetch 
items, thus avoiding both the expanding data problem, and the 
wasteful decompression on the client.

However, streaming compression has other advantages:

1) It's highly reapplicable, whether in TLS or as a distinct command, 
between IMAP, ESMTP, and even ACAP for the wishful thinkers amongst 
us.

2) It applies to the general protocol babble, as well. This might 
even entirely outweigh the expanding data problem.

3) It applies to what the client sends, which in the typical mobile 
phone environment has the benefit of increasing battery life, as I 
understand things.

4) Where compression is possible, it's likely they'll achieve higher 
compression due to the algorithm's model, dictionary, etc being 
primed already for the majority of cases.

Dave.
-- 
           You see things; and you say "Why?"
   But I dream things that never were; and I say "Why not?"
    - George Bernard Shaw

---

From: Ned Freed <[email-masked]>
Date: Fri, 17 Mar 2006 06:49:33 -0800 (PST)

> relatively expensive algorithms.

Nothing prevents alternate compression schemes from being used in TLS.
In fact you should be able to switch compressions on the fly by
renegotiating. This is actually better than LZIP-like schemes because it
could be initiated by the server, which is in a better position to
know what compression would be best for a particular message.

But this is all theoretical and IMO likely to stay that way.. I doubt very much
that anyone will actually do such things - the added complexity is just not
worth it.

> wasteful decompression on the client.

The expansion problem should be insignificant if the compression format is well
designed.

> between IMAP, ESMTP, and even ACAP for the wishful thinkers amongst

Yep.

> even entirely outweigh the expanding data problem.

Right again. It is pretty common to deal with large numbers of small messages.

> phone environment has the benefit of increasing battery life, as I

Actually, with TLS-level compression at least you should be able to control
whether or not it applies to what the client sends.

> primed already for the majority of cases.

Agreed.

				Ned

---

From: Dave Cridland <[email-masked]>
Date: Fri, 17 Mar 2006 16:23:31 +0000

> that anyone will actually do such things - the added complexity is 
Wouldn't the compression renegotiation involve an extra round-trip? 
And in any case, there's obvious mechanisms which are LZIP-like, but 
involve the server selecting a compression algorithm. HTTP already 
has this kind of mechanism. I think this stands in favour of 
LZIP-like mechanisms, to be honest.

An uber-compression scheme could, of course, be defined for TLS which 
could not only switch algorithms by a unilateral symbol injection to 
the stream, but switch between models (or dictionaries, etc), thus 
allowing the data character to change when reading attachments and 
messages without degrading the model used for the IMAP protocol 
elements themselves. This is probably equally blue-sky, though.

> The expansion problem should be insignificant if the compression 
True, although again it's less if the entire attachment can be 
compressed in advance, and can be made to be zero with LZIP-like 
mechanisms. (Okay, BINARY is two octets longer than LZIP, and the 
theoretical minimum for a compression algorithm expansion in worst 
case is one octet, assuming an integer number of octets).

In any case, Deflate is good enough that it compresses most things, 
including JFIF files off digital cameras, etc. Gzipping a 146,525 
octet gzip as a quick test gave me an increase of 55 octets, which is 
comfortably low. (I would hope that's the file header plus one symbol 
per compressed block, less any compressibility of the original file 
header and trailer.)

> Right again. It is pretty common to deal with large numbers of 
Yes, although I'm really thinking in terms of compressing away common 
strings such as "\r\n* ", for instance.

Dave.

---

From: Ned Freed <[email-masked]>
Date: Fri, 17 Mar 2006 08:43:10 -0800 (PST)

> Wouldn't the compression renegotiation involve an extra round-trip?

Perhaps - I don't know enough about the protocol specifics in TLS to say. But
if choice of compression really matters to this extent, I doubt if the extra
round trip is going to matter that much.

> LZIP-like mechanisms, to be honest.

I disagree, but I also think this entire thing is so far out there it is
irrelevant.

> elements themselves. This is probably equally blue-sky, though.

Actually, I'd say it is less blue-sky than expecting either clients or servers
to analyze data and change compression on the fly. Pushing all the complexity
into the compression engine has some really attractive properties. But as long
as we're compression-method-agile (and any of these schemes can be designed
this way) any work in this space can be deferred.

> per compressed block, less any compressibility of the original file

Yes, I think that's more or less how it plays out.

				Ned