Subject: Compression analysis of perfect atom-based compressor

From: Roberto Peon <[email-masked]>
Date: Thu, 4 Apr 2013 16:55:53 -0700

Here is some data based on an analysis of a perfect (i.e. resource
unconstrained) atom-based compressor.
I've removed any serialization sizes from this-- this will hold true for
HeaderDiff or Delta or whatever, presupposing it does atom-based
compression.

Feel free to jump to the bottom for take-aways if looking at the data is
boring :)

The top most compressible headers are (key% is the percentage of the
compressible bytes where were from the key):
                       |compressed
key-name               |  bytes     key%  val%
-----------------------+-----------------------
user-agent             |  2443472  9.37% 90.63%
cookie                 |  1957141  2.88% 97.12%
referer                |  1340198 11.89% 88.11%
via                    |   980712  4.53% 95.47%
accept-charset         |   700174 32.62% 67.38%
accept-language        |   685850 48.86% 51.14%
accept-encoding        |   676516 49.53% 50.47%
cache-control          |   571590 50.27% 49.73%
date                   |   544049 16.31% 83.69%
x-cache-lookup         |   523453 37.32% 62.68%
content-type           |   521956 50.88% 49.12%
:host                  |   506321 23.66% 76.34%
accept                 |   416278 32.65% 67.35%
x-cache                |   414766 28.26% 71.74%
last-modified          |   398843 58.89% 41.11%
proxy-connection       |   389619 63.48% 36.52%
server                 |   369522 32.27% 67.73%
:path                  |   337031 35.55% 64.45%
content-length         |   313985 94.79%  5.21%
expires                |   305406 35.69% 64.31%
:method                |   239569 70.02% 29.98%
:status                |   237574 70.61% 29.39%
p3p                    |   206589  2.93% 97.07%
accept-ranges          |   198471 73.02% 26.98%
content-encoding       |   124912 81.30% 18.70%
vary                   |   110368 22.38% 77.62%
age                    |    70211 66.89% 33.11%
set-cookie             |    66181 23.90% 76.10%
etag                   |    62416 48.63% 51.37%
x-powered-by           |    54561 46.49% 53.51%
x-content-type-options |    47171 77.61% 22.39%
x-varnish-server       |    33947 51.61% 48.39%
x-varnish              |    33376 89.04% 10.96%
x-xss-protection       |    28685 58.73% 41.27%
x-cdn                  |    27428 23.06% 76.94%
location               |    26152 19.79% 80.21%
transfer-encoding      |    25147 72.94% 27.06%
xcache                 |    24800 18.75% 81.25%
...

The distribution of backreferences is falls off extremely quickly as
distance from the newest element increases:
1       35460
2       20774
3       16886
4       12926
5       9601
6       6947
7       5100
8       4304
9       3658
10      3313
11      2789
12      2710
13      2678
14      2354
15      2372
16      2180
17      2066
18      2023
19      1979
20      1885
21      1888
22      1799
23      1724
24      1673
25      1584
26      1530
27      1506
28      1435
29      1395
30      1305
31      1355
32      1283
33      1305
34      1341
35      1339
36      1178
37      1200
38      1223
39      1169
40      1180
41      1111
42      1105
43      1074
44      1079
45      1043
46      1050
47      1030
48      972
49      963
50      942
51      935
52      916
...

I've attached a png of a graph of this (y axis=frequency, x-axis=dist from
newest element).
The knee in the graph is very nice indeed.

Take aways?

   - We need a better survey of headers from everywhere :)
   - Compression over our corpus should scale favorably with small table
   (and state) size.
   - Encoding index as dist-from-newest really works well, and LRU appears
   to be extremely effective as an expiration policy (the attached graph looks
   good).
   - We're getting substantial compression from both key and value
   backreferences/tokenization.
   - Algorithmically, there isn't a whole lot to do-- the devil is really
   in the serialization details and the tradeoffs involved in
   generating/parsing. There are obvious tweaks that compressors could do when
   space constrained (e.g. looking at the first table, above, as the likely
   benefit and making decisions based upon that), but the data which suggests
   that the LRU is so effective also suggests that this benefit is likely
   limited unless they can predict the future :)

-=R

---

From: Mark Nottingham <[email-masked]>
Date: Fri, 5 Apr 2013 11:02:38 +1100

How did you handle connection coalescing (the "streamifier" issue)?

Cheers,

On 05/04/2013, at 10:55 AM, Roberto Peon <[email-masked]> wrote:

> Here is some data based on an analysis of a perfect (i.e. resource unconstrained) atom-based compressor.
> I've removed any serialization sizes from this-- this will hold true for HeaderDiff or Delta or whatever, presupposing it does atom-based compression.
> 
> Feel free to jump to the bottom for take-aways if looking at the data is boring :)
> 
> The top most compressible headers are (key% is the percentage of the compressible bytes where were from the key):
>                        |compressed
> The distribution of backreferences is falls off extremely quickly as distance from the newest element increases:
> 1       35460
> 2       20774
> 3       16886
> 4       12926
> 5       9601
> 6       6947
> 7       5100
> 8       4304
> 9       3658
> 10      3313
> 11      2789
> 12      2710
> 13      2678
> 14      2354
> 15      2372
> 16      2180
> 17      2066
> 18      2023
> 19      1979
> 20      1885
> 21      1888
> 22      1799
> 23      1724
> 24      1673
> 25      1584
> 26      1530
> 27      1506
> 28      1435
> 29      1395
> 30      1305
> 31      1355
> 32      1283
> 33      1305
> 34      1341
> 35      1339
> 36      1178
> 37      1200
> 38      1223
> 39      1169
> 40      1180
> 41      1111
> 42      1105
> 43      1074
> 44      1079
> 45      1043
> 46      1050
> 47      1030
> 48      972
> 49      963
> 50      942
> 51      935
> 52      916
> ...
> 
> I've attached a png of a graph of this (y axis=frequency, x-axis=dist from newest element).
> 	• We need a better survey of headers from everywhere :)
> 	• Compression over our corpus should scale favorably with small table (and state) size.
> 	• Encoding index as dist-from-newest really works well, and LRU appears to be extremely effective as an expiration policy (the attached graph looks good).
> 	• We're getting substantial compression from both key and value backreferences/tokenization.
> 	• Algorithmically, there isn't a whole lot to do-- the devil is really in the serialization details and the tradeoffs involved in generating/parsing. There are obvious tweaks that compressors could do when space constrained (e.g. looking at the first table, above, as the likely benefit and making decisions based upon that), but the data which suggests that the LRU is so effective also suggests that this benefit is likely limited unless they can predict the future :)
> 
> -=R
> 
> 

--
Mark Nottingham   http://www.mnot.net/

---

From: Roberto Peon <[email-masked]>
Date: Thu, 4 Apr 2013 17:52:31 -0700

It used the default streamifier.
Happy to provide data with whatever streamifier...
-=R
On Apr 4, 2013 5:02 PM, "Mark Nottingham" <[email-masked]> wrote:

> >       • Encoding index as dist-from-newest really works well, and LRU
> appears to be extremely effective as an expiration policy (the attached
> graph looks good).
> >       • Algorithmically, there isn't a whole lot to do-- the devil is
> really in the serialization details and the tradeoffs involved in

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 5 Apr 2013 16:02:43 +0000

> -----Original Message-----
> From: Roberto Peon [mailto:[email-masked]]
> Sent: vendredi 5 avril 2013 01:56
> To: HTTP Working Group
> Subject: Compression analysis of perfect atom-based compressor
> 
[snip]

> Take aways?
> 
> *	We need a better survey of headers from everywhere :)
> 
> *	Compression over our corpus should scale favorably with small table
> (and state) size.
> 
> *	Encoding index as dist-from-newest really works well, and LRU
> appears to be extremely effective as an expiration policy (the attached graph
> looks good).

For HeaderDiff, we changed the expiration policy on the encoder side to use LRU: we found it was more effective than our previous "smart" algorithm.

> *	We're getting substantial compression from both key and value
> *	Algorithmically, there isn't a whole lot to do-- the devil is really in the
> serialization details and the tradeoffs involved in generating/parsing. There
> are obvious tweaks that compressors could do when space constrained (e.g.
> looking at the first table, above, as the likely benefit and making decisions
> based upon that), but the data which suggests that the LRU is so effective
> also suggests that this benefit is likely limited unless they can predict the
> future :)
> 

For information, here is the size of the literal values that have to be transmitted.

Requests
---------
header name                              | Encoded value size
:path                                    |   1454063 
referer                                  |    245761 
cookie                                   |    112619 
user-agent                               |     63628 
accept                                   |     23975 
:host                                    |     22855 
accept-language                          |     12325 
accept-charset                           |     11100 
accept-encoding                          |      9223 
if-modified-since                        |      3915 
nt_w3c                                   |      2650 
:scheme                                  |      2623 
:method                                  |      1961

Responses
---------
header name                              | Encoded value size
last-modified                            |    266750 
expires                                  |    199575 
date                                     |    155803 
etag                                     |    114298 
set-cookie                               |    110527 
via                                      |     84709 
cache-control                            |     65506 
location                                 |     61699 
content-length                           |     49104 
x-amz-cf-id                              |     43120 
x-amz-id-2                               |     38960 
x-varnish                                |     32757 
p3p                                      |     28416 
content-type                             |     27362 
age                                      |     25023 
content-disposition                      |     22147 
x-cache                                  |     15376 
x-cache-lookup                           |     13911 
server                                   |     13199 
x-amz-request-id                         |      9168 
x-fb-debug                               |      7348 
vary                                     |      4688 
x-json                                   |      4384 

To get any compression on these values we can use:
- Deflate (I'm not sure it will get any traction in the group ;-)).
- Prefix sharing (we're looking for a way to make it fully secure).
- Static Huffman encoding (it adds some computational costs).
- Typed codec (it should work well with last-modified, expires, date...).

Hervé.

---

From: "Martin Nilsson" <[email-masked]>
Date: Fri, 05 Apr 2013 18:55:15 +0200

>    - We need a better survey of headers from everywhere :)

I just captured 251'644 requests on a mobile site and counted the number  
of occurrences of every header, and it is quite the zoo of browser  
specific, device specific and network specific information added to these  
requests. Significant amount of request size is spent on wap profile  
headers like this, which obviously would benefit greatly from compression.

"X-WAP-Profile-Diff: 1; <?xml version=\"1.0\"?><rdf:RDF  
xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\"  
xmlns:prf=\"http://www.wapforum.org/UAPROF/ccppschema-19991014#\"><!--  
browser vendor site: Default description of properties  
--><rdf:Description><prf:CcppAccept><rdf:Bag><rdf:li>application/vnd.wap.wmlscriptc</rdf:li><rdf:li>text/vnd.wap.wml</rdf:li><rdf:li>application/vnd.wap.xhtml+xml</rdf:li><rdf:li>application/xhtml+xml</rdf:li><rdf:li>text/xml</rdf:li><rdf:li>text/html</rdf:li><rdf:li>text/css</rdf:li><rdf:li>multipart/mixed</rdf:li><rdf:li>*/*</rdf:li></rdf:Bag></prf:CcppAccept></rdf:Description></rdf:RDF>,2;  
<?xml version=\"1.0\"?><rdf:RDF  
xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\"  
xmlns:prf=\"http://www.wapforum.org/UAPROF/ccppschema-19991014#\"><!--  
browser vendor site: Default description of properties  
--><rdf:Description><prf:CcppAccept-Charset><rdf:Bag><rdf:li>*</rdf:li></rdf:Bag></prf:CcppAccept-Charset></rdf:Description></rdf:RDF>,3;  
<?xml version=\"1.0\"?><rdf:RDF  
xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\"  
xmlns:prf=\"http://www.wapforum.org/UAPROF/ccppschema-19991014#\"><!--  
browser vendor site: Default description of properties  
--><rdf:Description><prf:CcppAccept-Language><rdf:Seq><rdf:li>en</rdf:li></rdf:Seq></prf:CcppAccept-Language></rdf:Description></rdf:RDF>"

The problem is how to create an exportable version of this kind of  
information. As you can see in the list, there is a ton of private  
information. The toplist of headers, cut off at a 100 count:

user-agent           253841
host                 251654
accept               172367
connection           169545
x-wap-profile        168415
accept-encoding      160263
accept-language      147588
accept-charset       142473
x-forwarded-for      76146
cookie2              72529
referer              58741
cache-control        51080
via                  46627
cookie               44593
content-length       36777
content-type         33884
drm-version          32665
x-nokia-musicshop-version 23321
x-nokia-musicshop-bearer 23318
if-modified-since    13569
x-wap-profile-diff   10942
wap-connection       10271
x-network-info       9805
pragma               9576
x-msisdn             8332
x-up-calling-line-id 8027
x-wap-proxy-cookie   7501
x-nokia-device-type  7359
x-mobile-gateway     7359
x-country-code       7339
x-nokia-remotesocket 6474
x-nokia-localsocket  6371
x-up_devcap-screendepth 6247
x-nokia-gateway-id   5081
x-nokia-msisdn       5034
rim_cod_selection    5006
msisdn               4634
proxy-connection     4568
x-nokia-bearer       4455
profile              4117
x-bluecoat-via       3981
range                3702
clientip             3437
x-piper-id           3436
keep-alive           2988
http_x_msisdn        2679
rat                  2665
x-ucbrowser-ua       2355
x-ucbrowser-device   2118
x-ucbrowser-device-ua 2118
proxy-authorization  1967
nbg-imp-mobile       1956
nbg-imp-omitlog      1956
x-nsn-proxytype      1956
nbg-imp-msisdn       1956
nbg-imp-userpref     1956
nbg-imp-proxy        1956
nbg-imp-user-agent   1954
if-range             1925
x-up-forwarded-for   1821
pnp                  1805
x-forwarded-port     1804
x-forwarded-proto    1804
x-nokiasession       1603
x-up-3ggp-imeisv     1591
x-up-sgsn-ip         1591
client-ip            1473
x-ebo-ua             1357
x-roaming            1336
imsi                 1286
x-nokia-upgradeid    1141
y-msisdn             1122
x-source-id          1089
x-nokia-ipaddress    1065
x-nokia-chargingid   1044
x-nokia-imsi         1031
x-nokia-maxdownlinkbitrate 1004
x-nokia-maxuplinkbitrate 993
apn                  981
x-rat-type           897
x-nsn-maxuplinkbitrate 892
x-nsn-bearer         892
x-nsn-gateway-id     892
x-up-bear-type       892
x-nsn-maxdownlinkbitrate 892
x-wap-client-ip      864
x-nokia-roamingind   788
x-nokia-prepaidind   787
x-nokia-rattype      787
x-imei               786
x-msp-clid           780
x-msp-ag             774
x-rim-transcode-content 746
ua-cpu               739
te                   681
x-ucbrowser-phone-ua 600
x-ucbrowser-phone    600
ip                   546
x-cnection           539
x-xxy-connection     506
bearer-indication    505
x-up-subno           465
surrogate-capability 416
x-wap-network-client-ip 396
x-brazil-forwarded-for 396
x-wap-clientid       383
x-nokia-connection_mode 362
max-forwards         344
x-fh-ip              338
x-fh-msisdn          338
x-fh-apn             338
x-wap-fh-subscriber-info 338
x-fh-event-id        338
x-fh-sgsn-ip         337
x-fh-virtual-gateway 337
x-fh-port            337
x-up-devcap-screendepth 328
x-up-devcap-screenpixels 328
user-ip              325
x-huawei-imsi        312
x-mms-prepaid-flag   308
x-mms-sgsnip         308
x-mms-sgsnmccmnc     308
q-ua                 299
ua-pixels            295
ua-voice             295
ua-color             295
ua-os                289
x-ip-address         287
called-station-id    279
schar_h              274
context_id           274
sgsn-ip-address      273
bearer-type          273
charging-characteristics 273
nas-ip-address       273
ip-address           273
accounting-session-id 273
x-nokia-roamingid    257
x-nokia-prepaidid    257
x-wap-network-client-msisdn 257
x-nokia-ggsnipaddress 243
x-rim-accept-encoding 235
x-rim-img-setting    235
x-rim-image-threshold 235
x-rim-gw-properties  235
x-wap-msisdn         226
x-up-bearer-type     225
imsisdn              221
x-up-subscriber-cos  219
x-nokia-sgsnipaddress 213
x-wap-personalization 205
x-up-user-location-info 193
x-up-ch-rat-type     193
x-up-nai             193
x-network-client-ip  192
http_client_ip       174
encoding-version     166
x-method             136
 from                 132
xxxxxxxxxx           112
x-up-devcap-cc       111
ipaddr               111
dnt                  104
x-nokia.wia.accept.original 103
x-nbg_transactionid  102
x-wap-client-sdu-size 102
x-wap-gateway        102
x-wap-session-id     102
device-stock-ua      101
x-online-host        101

/Martin Nilsson

-- 
Using Opera's revolutionary email client: http://www.opera.com/mail/

---

From: Mark Nottingham <[email-masked]>
Date: Sat, 6 Apr 2013 18:18:52 +1100

On 06/04/2013, at 3:55 AM, Martin Nilsson <[email-masked]> wrote:

> I just captured 251'644 requests on a mobile site and counted the number of occurrences of every header, and it is quite the zoo of browser specific, device specific and network specific information added to these requests. Significant amount of request size is spent on wap profile headers like this, which obviously would benefit greatly from compression.
> 
> "X-WAP-Profile-Diff: 1; <?xml version=\"1.0\"?><rdf:RDF xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\" xmlns:prf=\"http://www.wapforum.org/UAPROF/ccppschema-19991014#\"><!-- browser vendor site: Default description of properties --><rdf:Description><prf:CcppAccept><rdf:Bag><rdf:li>application/vnd.wap.wmlscriptc</rdf:li><rdf:li>text/vnd.wap.wml</rdf:li><rdf:li>application/vnd.wap.xhtml+xml</rdf:li><rdf:li>application/xhtml+xml</rdf:li><rdf:li>text/xml</rdf:li><rdf:li>text/html</rdf:li><rdf:li>text/css</rdf:li><rdf:li>multipart/mixed</rdf:li><rdf:li>*/*</rdf:li></rdf:Bag></prf:CcppAccept></rdf:Description></rdf:RDF>,2; <?xml version=\"1.0\"?><rdf:RDF xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\" xmlns:prf=\"http://www.wapforum.org/UAPROF/ccppschema-19991014#\"><!-- browser vendor site: Default description of properties --><rdf:Description><prf:CcppAccept-Charset><rdf:Bag><rdf:li>*</rdf:li></rdf:Bag></prf:CcppAccept-Charset></rdf:Description></rdf:RDF>,3; <?xml version=\"1.0\"?><rdf:RDF xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\" xmlns:prf=\"http://www.wapforum.org/UAPROF/ccppschema-19991014#\"><!-- browser vendor site: Default description of properties --><rdf:Description><prf:CcppAccept-Language><rdf:Seq><rdf:li>en</rdf:li></rdf:Seq></prf:CcppAccept-Language></rdf:Description></rdf:RDF>"

Wow. Hardly know where to start with that one...

> The problem is how to create an exportable version of this kind of information. As you can see in the list, there is a ton of private information. The toplist of headers, cut off at a 100 count:

...

I think it depends on what we want to do with the data. E.g., if it's suitable for feeding into the compression-test suite, you could do so and report the results back to us, or you could come to some agreement with the implementers about sharing the data under terms your lawyers are comfortable with (blech, but still..).

If it's just getting characteristics of the traces to inform our discussions, you could just continue to post your observations, and take requests for other summaries of the data.

Cheers,