Subject: Re: draft-heath-ppp-v44-02.txt

From: [email-masked]
Date: Wed, 15 Jan 2003 15:51:57 -0800

Vernon

I am talking about apples to apples comparisons over a packet network 
environment where a stream of IP sized 1500 byte packets is compressed 
between two peers where:
---  typical internet data is used, such as mail, HTML, word, etc. files. 
From actual mail folders and web HTML's, etc.
---  comparable memory usage for each algorithm.  Thus a LZS 2048 history 
is compared to LZW (V.42bis) 2048 dictionary (11 bits) and LZJH (V.44) 
2048 dictionary (11 bits) such that with tables, etc. the memory usage is 
roughly equal +/- 20%. 

In that environment LZS and LZJH both get better compression than LZW (in 
all my testing over the past 3 years) and LZJH gets better than LZS.  LZS 
supports only a 2048 history so I guess if you compare it to LZW with a 15 
bit word size (32K dictionary) then it would do better than LZS.  I have 
also tested LZW and LZJH against a LZS clone that supports various history 
sizes and the results were similiar using comparable history and 
dictionary sizes.

Using the above I have compared LZJH with LZW for all dictionary sizes up 
through 13 bits and LZJH is clearly a superior algorithm.  While a 200% 
improvement with LZJH certainly is not normal and is only with some highly 
compressible files, almost all HTML will provide 60% - 100% improvement. 

In an environment where the dictionary is cleared after every IP packet 
LZW is very inferior to LZJH and LZS.

I agree that there are plenty of claims of compression performance all 
over the place.  That is why you have to bound MIP's and memory to get an 
apples to apples comparison.   You can trash the ITU if you please but 
they were at least forward looking enough to:
--- require competing compression algorithms to get at least 20% better 
compression than V.42bis over a set of typical internet files while using 
no more than 20% more MIP's and no more than 20% more memory than V.42bis 
(i.e. the new algorithm had to run on existing hardware).  Tests were run 
using dictionary sizes from 512 through 8192. 
--- recognize that LZJH was a better compression solution and adopt it as 
V.44 despite the fact that virtually 100% of the worlds modems at that 
time had V.42bis.  They felt that as new modems were built V.44 would be 
phased in.  The fact that V.42bis was the current de facto choice did not 
stop the ITU from adopting something better.
--- recognize that the Calgary and Canterbury corpus were not 
representative of data being downloaded in todays internet and create a 
set of test files that are representative.
--- run comparison tests against HTML files from web sites worldwide with 
many different languages.

I would assume that the IETF is forward looking enough want to allow PPP 
implementors the choice if something better comes along regardless of the 
number of current CCP options and regardless of a current de facto choice. 
 Most will run their own comparisons and decide for themselves which is 
best based on MIP's, memory, or other contraints which they may have.

I would be happy to provide you with the source of LZJH if you want to run 
your own comparisons.

Yes, it is going to be an Informational RFC.

Jeff

Vernon Schryver <[email-masked]>
Sent by: [email-masked]
01/15/2003 12:55 PM

        To:     [email-masked]
        cc:     [email-masked], [email-masked], [email-masked], 
[email-masked], [email-masked]
        Subject:        Re: draft-heath-ppp-v44-02.txt

> From: [email-masked]

> ...
> I think  you are confusing V.44 compression with V.42bis compression. 
V.44 
> compression (i.e. LZJH) is sufficiently different from LZW that no 
Unisys 
> or other LZW variant license fees are required for it's use.

oh.

> In answer to your question, V.44 in this environment gets anywhere from 
> 20% to 200% better compression than LZW, and thus BSD PPP, depending on 
> the data.  For HTML, etc. type web pages it is closer to the 200%.  V.44 

> also gets better compression than LZS by ~10%.   With faster execution 
> times.

On which corpus was this measured and with which PPP implementations?
When comparing to LZW, what size dictionary was used, the typical,
barely useful 9 or 10-bit of v.42bis or something reasonable?

I ask because the archives of this mailing list have plenty of marketing
statements of compression performance (made up facts), although not as
many as in the open literature (trade rags).

I also ask because your numbers seem backwards.  LZS as it is in PPP is
a terrible compression scheme compared to others including LZW.  I cannot
imagine something bettering LZS by only 10% but LZW with a reasonable
dictionary by 200%.  For that matter, I cannot imagine anything beating
LZW with a reasonable dictionary size by 200%.  There simply is not that
much entropy in LZW output, unless you do something dishonest such as
using 9-bit codes or clearing the dictionary on every packet.

> The substantial increase in compression ratios that LZJH gets over LZW 
is 
> the reason the ITU adopted V.44 in the first place to replace V.42bis in 

> modems.
> ...

I don't want to offend anyone, but the ITU is at least as bad as any
other standards organization and frequently (or almost always) makes
decisions for one set of reasons (e.g. patent fees) while claiming to
have other reasons.  In a case like this, what the ITU thinks is
completely irrelevant.  What does matter is measured performance and
the recipes for evalutating and repeating those measurements.

The bigger question remains.  Is the de facto choice of LZS good enough,
bad as it is on compression effectiveness grounds?
Is v.44 enough better to justify adding to the CCP babel?  How many
implementations of v.44 PPP compression can reasonably be expected given
the market dominence of LZS?

Finally, I have a question about the expected status of a v.44 RFC.
It would be Informational, right?

Vernon Schryver    [email-masked]