Subject: bohe and delta experimentation...

From: James M Snell <[email-masked]>
Date: Wed, 16 Jan 2013 14:07:23 -0800

After going a number of scenarios with bohe using a variety of
stream-compression scenarios it's painfully obvious that there is really no
way around the CRIME issue when using stream-compression. So with that, I'm
turning my attention to the use of Roberto's delta encoding and exploring
whether or not binary optimized values can make a significant difference
(as opposed to simply dropping in huffman-encoded text everywhere).

I'm starting with dates first...

Right now, dates in http/1 requests are rather inefficient. The existing
date-time format wastes a significant amount of space, albeit across only a
relatively few headers. On the plus side, these tend to compress well, but
given that the dates change frequently request-to-request, they will be
short-lived in the delta context.

Given this, I decided to run a test scenario for compressing RFC3999 dates
as text vs. using a compact binary encoding. I generated a sample of 100k
randomly generated RFC3999 timestamps that variably include milliseconds
and timezone offsets, I then used that to generate a date-time specific
symbol map and used a static huffman coding. Then, given a sample of 100k
more randomly generated timestamps, the average compression was 12-13 bytes
for the date value. (average length of the uncompressed timestamp is 24
bytes).. so pretty good compression using a symbol tree specifically
optimized for date-times.

By comparison, I devised a simple binary coding for dates using the
following format:

+-+---+---+-------------------+
|M|TZH|TZM|   year (16-bit)   |
+-+---+---+-----+-------------+
| month (4-bit) | day (5-bit) |
+---------------+-------------+
| hour (5-bit)  | minute (6)  |
+---------------+-------------+
| second (6 bit)| millis (31) |
+---------------+-------------+
|d|tz hrs (5 bit)| tz min (6) |
+-----------------------------+

M, TZH and TZM are single bit flags. When M is set, the value includes a
31-bit millisecond field. When TZH is set, it includes timezone offset
hours, and when TZM is set, it includes timezone offset minutes. The d
field (last row) is a single bit indicating positive or negative timezone
offset.

The minimum possible binary encoding is 6-bytes, which includes the first
three flag bits, year, month, day, hour, minute and second. The maximum
possible encoding is 11-bytes which includes full timezone offset and
milliseconds. Giving an average encoding of 8-bytes over any sample size of
randomly generated timestamps.

While the binary encoding is certainly more efficient, I'm not yet certain
if those 4-bytes are worth the effort, but it does improve the overall
compression ratio for the message as a whole.

Either way, regardless of whether we huffman code or binary code the date
values, we should require that RFC3339/ISO8601 timestamps be used for all
date headers within the http/2 header encoding as those are going to
compress much better than the current http/1 date format.

Entity Tags are another area where binary values may be useful. Currently,
ETag values generally tend to be hex or base64 encoded binary data. By
simply allowing the etag to be dropped in as a set of bytes in the encoded
header we can cut the transmitted size of those tags in half. The format
I'm considering for these is:

   +-+------+-----------+
   |W|len(7)| octets... |
   +-+------+-----------+

Where W is a single bit flag indicating weak or not, len is the number of
encoded octets for the entity tag. (I'm wondering, tho, whether or not we
could get away with dropping the entire concept of a "weak entity tag")

By optimizing dates and entity tags this way, we end up with optimized
encodings for a good number of commonly used headers (date, last-modified,
expires, etag, if-none-match, if-match, if-modified-since, etc), and we can
eliminate the need for doing any compression on those values at all.

Another set of headers we can optimize within delta are the numeric values
for Content-Length, :status, Expires, etc. Rather than encoding those as
ascii strings, we would simply encode them as their numeric value.

Will be turning my attention to cookie values next. I'm considering whether
or not we should produce a code-tree that is specific to cookie headers
and/or allow for purely binary values.

- James

---

From: Mark Nottingham <[email-masked]>
Date: Thu, 17 Jan 2013 09:28:59 +1100

On 17/01/2013, at 9:07 AM, James M Snell <[email-masked]> wrote:

> After going a number of scenarios with bohe using a variety of stream-compression scenarios it's painfully obvious that there is really no way around the CRIME issue when using stream-compression. So with that, I'm turning my attention to the use of Roberto's delta encoding and exploring whether or not binary optimized values can make a significant difference (as opposed to simply dropping in huffman-encoded text everywhere).
> 
> Right now, dates in http/1 requests are rather inefficient. The existing date-time format wastes a significant amount of space, albeit across only a relatively few headers. On the plus side, these tend to compress well, but given that the dates change frequently request-to-request, they will be short-lived in the delta context. 
> 
> Given this, I decided to run a test scenario for compressing RFC3999 dates as text vs. using a compact binary encoding. I generated a sample of 100k randomly generated RFC3999 timestamps that variably include milliseconds and timezone offsets, I then used that to generate a date-time specific symbol map and used a static huffman coding. Then, given a sample of 100k more randomly generated timestamps, the average compression was 12-13 bytes for the date value. (average length of the uncompressed timestamp is 24 bytes).. so pretty good compression using a symbol tree specifically optimized for date-times.
> 
> By comparison, I devised a simple binary coding for dates using the following format:
> 
> M, TZH and TZM are single bit flags. When M is set, the value includes a 31-bit millisecond field. When TZH is set, it includes timezone offset hours, and when TZM is set, it includes timezone offset minutes. The d field (last row) is a single bit indicating positive or negative timezone offset.
> 
> The minimum possible binary encoding is 6-bytes, which includes the first three flag bits, year, month, day, hour, minute and second. The maximum possible encoding is 11-bytes which includes full timezone offset and milliseconds. Giving an average encoding of 8-bytes over any sample size of randomly generated timestamps.
> 
> While the binary encoding is certainly more efficient, I'm not yet certain if those 4-bytes are worth the effort, but it does improve the overall compression ratio for the message as a whole.

Just for comparison - in the simple encoding, I get it to 8 bytes (at least before year 2038), and it's textual (just the hex for the number of seconds since the epoch).

E.g.,

HTTP/1: Sat, 03 Nov 2012 13:05:03 GMT
Simple: 5095167f

> Either way, regardless of whether we huffman code or binary code the date values, we should require that RFC3339/ISO8601 timestamps be used for all date headers within the http/2 header encoding as those are going to compress much better than the current http/1 date format.
> 
> Entity Tags are another area where binary values may be useful. Currently, ETag values generally tend to be hex or base64 encoded binary data.

That's a big assumption!

> By simply allowing the etag to be dropped in as a set of bytes in the encoded header we can cut the transmitted size of those tags in half. The format I'm considering for these is:
> 
>    +-+------+-----------+
>    |W|len(7)| octets... |
>    +-+------+-----------+
> 
> Where W is a single bit flag indicating weak or not, len is the number of encoded octets for the entity tag. (I'm wondering, tho, whether or not we could get away with dropping the entire concept of a "weak entity tag")

We decided not to drop it in HTTPbis, so assume that it'll stay (given we need to be able to convert 1 to 2 and back).

> By optimizing dates and entity tags this way, we end up with optimized encodings for a good number of commonly used headers (date, last-modified, expires, etag, if-none-match, if-match, if-modified-since, etc), and we can eliminate the need for doing any compression on those values at all.
> 
> Another set of headers we can optimize within delta are the numeric values for Content-Length, :status, Expires, etc. Rather than encoding those as ascii strings, we would simply encode them as their numeric value.
> 
> Will be turning my attention to cookie values next. I'm considering whether or not we should produce a code-tree that is specific to cookie headers and/or allow for purely binary values.

I could imagine setting a parameter on Set-Cookie that indicates its content is encoded in a certain way, which can be replayed as binary data. However, that information would also need to be in Cookie, which I *think* necessitates a new request header -- maybe Bookie?

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

---

From: James M Snell <[email-masked]>
Date: Wed, 16 Jan 2013 14:45:37 -0800

On Wed, Jan 16, 2013 at 2:28 PM, Mark Nottingham <[email-masked]> wrote:

>
> [snip]
> Just for comparison - in the simple encoding, I get it to 8 bytes (at
> least before year 2038), and it's textual (just the hex for the number of
> seconds since the epoch).
>
> E.g.,
>
Yep, saw that. The advantage I see with the strawman binary encoding is
that it provides for millisecond precision, includes timezone data, and
covers years up to 9999, in just 3 additional bytes.

>
> > Either way, regardless of whether we huffman code or binary code the
> date values, we should require that RFC3339/ISO8601 timestamps be used for
> all date headers within the http/2 header encoding as those are going to
> > Entity Tags are another area where binary values may be useful.
> Currently, ETag values generally tend to be hex or base64 encoded binary
> data.
>
> That's a big assumption!
>
>
Indeed ;-) ... Notice the way I hedged that with "generally tend" lol... I
was hoping no one would notice ;-) ... what I would imagine is that delta
op-codes could include a binary-or-text flag (there is existing space
available in Roberto's encoding). If that flag is set, then value is
assumed to be binary, otherwise it's text. This gives good backwards
compatibility by default but allows for more optimized binary values.

> > By simply allowing the etag to be dropped in as a set of bytes in the
> encoded header we can cut the transmitted size of those tags in half. The
> format I'm considering for these is:
> >
> >    +-+------+-----------+
> >    |W|len(7)| octets... |
> >    +-+------+-----------+
> >
> > Where W is a single bit flag indicating weak or not, len is the number
> of encoded octets for the entity tag. (I'm wondering, tho, whether or not
> we could get away with dropping the entire concept of a "weak entity tag")
>
> We decided not to drop it in HTTPbis, so assume that it'll stay (given we
> need to be able to convert 1 to 2 and back).
>
>
That's what I figured... :-/

> > Another set of headers we can optimize within delta are the numeric
> values for Content-Length, :status, Expires, etc. Rather than encoding
> those as ascii strings, we would simply encode them as their numeric value.
> >
> > Will be turning my attention to cookie values next. I'm considering
> whether or not we should produce a code-tree that is specific to cookie
> headers and/or allow for purely binary values.
>
> I could imagine setting a parameter on Set-Cookie that indicates its
> content is encoded in a certain way, which can be replayed as binary data.
> However, that information would also need to be in Cookie, which I *think*
> necessitates a new request header -- maybe Bookie?
>
>
Hmm... if we have the flag in the opcode would we still need this?
Obviously I'd rather avoid having yet another cookie header definition.

- James

---

From: Nico Williams <[email-masked]>
Date: Wed, 16 Jan 2013 16:47:33 -0600

On Wed, Jan 16, 2013 at 4:07 PM, James M Snell <[email-masked]> wrote:
> whether or not binary optimized values can make a significant difference (as
> opposed to simply dropping in huffman-encoded text everywhere).

Well, we could pursue enhanced session continuation (Phillip's term
for using MACs taken over nonces, among other things, instead of or in
addition to cookies).

But I think it'd be nice to explore compression of header names and of
some header values.  So let's,

>[...]
> hours, and when TZM is set, it includes timezone offset minutes. The d field
> (last row) is a single bit indicating positive or negative timezone offset.

You don't need 31 bits for milliseconds; 10 will do!  But sure, it's
nice to be able to get to microseconds, in which case 20 bits should
suffice, or nanoseconds, in which case 30 bits should suffice.  In no
case do we need 31 bits for fractions of seconds.  But at best we save
21 bits -- two bytes, or, if we're lucky, three.

> randomly generated timestamps.

But if everyone chooses to send the max then it's 11 vs. the 12 you
got with date string compression.  Too trivial a gain?

Of course, an encoding that uses, say, 44 bits for twos-complement (do
we need negative dates for this?) seconds since the Unix epoch + 20
for microseconds would always be 8 bytes, but we'd get no TZ
information, and TZ info would require at least two more bytes so...
we're back to about 10-12 bytes.  If we could do with just 34 bits for
seconds w/o negative dates we're getting closer to always 8 bytes.
And if we could do with just 33 bits for seconds ... we'd get to
exactly 8 bytes but at the price of a 2,242 year problem.

What if we use julian day?  Then we'd need 31 bits for days (which
allows us to go 1000 years into the future), 16 bits for seconds and
milliseconds, and now we're at 6 bytes + two more for TZ data.  And if
we encode TZ offset in terms of 15 minute increments then we get down
to just 7 bytes for the whole thing.  Seven bytes is pretty good, but
is it good enough to bother with this?

We can do slightly better if we don't allow dates in the past, set a
new epoch, and limit how far into the future our dates will go (we can
always allow for encoding far-future dates with many more bytes).  I
think we can probably get down to 6 bytes for dates, including TZ
information and milliseconds for the next few decades then go up to 7
bytes and so on.

> and/or allow for purely binary values.

Where cookies bear encrypted session state you won't be able to
compress them at all.  And it's not like the server can't do the
effort to set maximally-compressed cookies -- it should!  IMO: leave
cookies alone.

Nico
--

---

From: Mark Nottingham <[email-masked]>
Date: Thu, 17 Jan 2013 10:10:44 +1100

On 17/01/2013, at 9:45 AM, James M Snell <[email-masked]> wrote:

> Yep, saw that. The advantage I see with the strawman binary encoding is that it provides for millisecond precision, includes timezone data, and covers years up to 9999, in just 3 additional bytes.

Dates in HTTP are explicitly in UTC (we just call it "GMT"), so the timezone data isn't helping (and may be hurting).

Dates in HTTP have a granularity of one second; although people ask for finer granularity from time to time, giving them this capability is IMO asking for trouble (because clock sync and the speed of light / disk, combined with people's ignorance of distributed systems, leads to lots of bugs).

That said, we could make millisecond granularity available in HTTP/2 dates, as long as it's OK for that resolution to be lost when converting to HTTP/1. The other approach would be to introduce new headers that have the resolution and are able to transit a HTTP/1 connection, but the cost is pretty high there...

WRT years up to 9999 -- yes. The method I used consumes an extra byte after 2106... and then another in 4147. However, just one more byte buys up to 36812!

What's the use case for separating out hours from minutes? Given that most uses for dates in HTTP are driven by caching, and therefore need a direct, numeric comparison, why not just send the number?

> Indeed ;-) ... Notice the way I hedged that with "generally tend" lol... I was hoping no one would notice ;-) ... what I would imagine is that delta op-codes could include a binary-or-text flag (there is existing space available in Roberto's encoding). If that flag is set, then value is assumed to be binary, otherwise it's text. This gives good backwards compatibility by default but allows for more optimized binary values.

That information will be lost on a HTTP/1 hop. It would be good to discuss how important that is; if it's really just optimisation information, it might be OK...

The bigger impact that I can see is that people will now need to flag their ETags as "binary-compatible" or not when they set them, etc. Ew.

> Hmm... if we have the flag in the opcode would we still need this? Obviously I'd rather avoid having yet another cookie header definition.

See above.

Cheers,

---

From: James M Snell <[email-masked]>
Date: Wed, 16 Jan 2013 15:10:55 -0800

On Wed, Jan 16, 2013 at 2:47 PM, Nico Williams <[email-masked]>wrote:

> field
Yes, 31 bits was intentional overkill just for the strawman. I'm generally
unconvinced that we would need anything more than millisecond precision,
allowing us to drop to a max of 9-bytes.

> exactly 8 bytes but at the price of a 2,242 year problem.
One of the nice thing about the strawman encoding I used is that it is a
field-for-field representation of the RFC3339 timestamp. It encodes exactly
the same information and can represent the full range of dates supported by
the date-time construct. Other variations may shave off one or two
additional bytes but either lose information or are far more limited in the
values they can express. Suppose we decided to adjust the millisecond field
to 10 bits as you suggest we have a worse case of 9-bytes, best case of 6.
Seems like a reasonable compromise to me.

> whether

Yeah, that's what I suspect also. Allowing for binary cookie values can
allow us to avoid extra bits on the wire but compression here typically
doesn't help for these at all, regardless of how optimized our code tree
is.

---

From: Roberto Peon <[email-masked]>
Date: Wed, 16 Jan 2013 15:13:24 -0800

Everything ends up as binary on either side today. So long as it arrives in
the form that was transmitted, it doesn't matter what the encoding is.
Cookies today are all mostly encoded in something from that binary, with
the most likely being base-64 encoding. Base-64 encoding is highly
compressible (using entropy coding). Encryption makes LZ77 and its ilk not
efficient, but that is a separate thingie entirely :)

-=R

On Wed, Jan 16, 2013 at 2:47 PM, Nico Williams <[email-masked]>wrote:

> (as

---

From: Nico Williams <[email-masked]>
Date: Wed, 16 Jan 2013 17:20:59 -0600

> Seems like a reasonable compromise to me.

The variations I mentioned also encode the same information without
losing anything at all.  The downside of going the julian day or
seconds since epoch approaches is that they require more computation,
but I think we can burn those CPU cycles since they won't incur many
cache misses -- it's fast and saves bytes on the wire where it
matters.

The question is: is it worth the trouble?  I don't have an answer to
that, but I'm inclined to say that yes, we should represent dates/time
in an already very small format.

> doesn't help for these at all, regardless of how optimized our code tree is.

Right, because cookies are mostly either randomly generated crap or
encrypted state, and those can't compress *at all*.

---

From: Nico Williams <[email-masked]>
Date: Wed, 16 Jan 2013 17:23:07 -0600

> Dates in HTTP are explicitly in UTC (we just call it "GMT"), so the timezone data isn't helping (and may be hurting).

TZ should be in a separate header then.  It helps the server to know
what TZ a user is in.

> Dates in HTTP have a granularity of one second; although people ask for finer granularity from time to time, giving them this capability is IMO asking for trouble (because clock sync and the speed…

Well, sub-second resolution can help if you're building, say, a
timesync protocol.  (Since every app protocol now has to run over
HTTP... NTP is no longer good enough.  j/k)

> WRT years up to 9999 -- yes. The method I used consumes an extra byte after 2106... and then another in 4147. However, just one more byte buys up to 36812!

Good!

---

From: Mark Nottingham <[email-masked]>
Date: Thu, 17 Jan 2013 10:25:03 +1100

> TZ should be in a separate header then.  It helps the server to know

That's been discussed quite a bit already, and is separable from HTTP/2. For starters, the Date header is seldom sent in requests...

---

From: Nico Williams <[email-masked]>
Date: Wed, 16 Jan 2013 17:35:01 -0600

>> WRT years up to 9999 -- yes. The method I used consumes an extra byte after 2106... and then another in 4147. However, just one more byte buys up to 36812!

If we use seconds since epoch, set a new epoch, use a variable length
integer encoding for seconds since epoch, we get to 32 bits for a few
decades.  Four bytes.

If we use Julian days, set a new epoch, use a variable length integer
encoding for julian day then we can get down to 13-14 bits to start.
Add 12 bits for seconds, or multiply days by 3600 and add seconds and
we're under 32 bits -- almost as low as 24, but still 4 bytes.  Can't
get much better.

---

From: Mark Nottingham <[email-masked]>
Date: Thu, 17 Jan 2013 10:39:53 +1100

> we're under 32 bits -- almost as low as 24, but still 4 bytes.  Can't

Yep, but you either need to make the epoch start at least a few years ago (old Last-Modified times, is important for heuristic freshness), OR keep it signed (losing a bit).

And I think you need more than 12 bits for seconds in a day...

---

From: Nico Williams <[email-masked]>
Date: Wed, 16 Jan 2013 17:45:09 -0600

> And I think you need more than 12 bits for seconds in a day...

Oops, for some reason I thought of seconds in an hour.  So 5 more
bits, and we're about even with seconds since epoch.  Either way
getting from 24 bytes to 4 is pretty good, and no compression scheme
will do better.

---

From: James M Snell <[email-masked]>
Date: Wed, 16 Jan 2013 15:45:39 -0800

On Wed, Jan 16, 2013 at 3:10 PM, Mark Nottingham <[email-masked]> wrote:

> Dates in HTTP are explicitly in UTC (we just call it "GMT"), so the
> timezone data isn't helping (and may be hurting).
>
> Dates in HTTP have a granularity of one second; although people ask for
> finer granularity from time to time, giving them this capability is IMO
> asking for trouble (because clock sync and the speed of light / disk,
> combined with people's ignorance of distributed systems, leads to lots of
> bugs).
>
>
Agreed... if we can drop the timezone info entirely and just assume
everything is GMT we're good. As for millisecond precision, I do question
whether it's truly necessary but it's possible for us to at least support
the option. Assuming we omit timezone and default to seconds-only, we're
down to six bytes and seven bytes with milliseconds.

> That said, we could make millisecond granularity available in HTTP/2
> dates, as long as it's OK for that resolution to be lost when converting to
> HTTP/1. The other approach would be to introduce new headers that have the
> resolution and are able to transit a HTTP/1 connection, but the cost is
> pretty high there...
>
> WRT years up to 9999 -- yes. The method I used consumes an extra byte
> after 2106... and then another in 4147. However, just one more byte buys up
> to 36812!
>
>
I'm generally convinced that 9999 is likely going to be more than
sufficient for header values ;-)

> What's the use case for separating out hours from minutes? Given that most
> uses for dates in HTTP are driven by caching, and therefore need a direct,
> numeric comparison, why not just send the number?
>
>
The rational here was is provide a field-for-field mapping of rfc3339
date-times as efficiently as possible... basically just trying to baseline
on a single model for expressing dates rather than having to convert
between several. That, of course, is not critical.

> > Indeed ;-) ... Notice the way I hedged that with "generally tend" lol...
> I was hoping no one would notice ;-) ... what I would imagine is that delta
> That information will be lost on a HTTP/1 hop. It would be good to discuss
> how important that is; if it's really just optimisation information, it
> might be OK...
>
> The bigger impact that I can see is that people will now need to flag
> their ETags as "binary-compatible" or not when they set them, etc. Ew.
>
>
Yeah, that's certainly a major consideration. First question is, would
binary encoding make a significant difference, second question is: is it
worth the costs. In this case, I suspect that the payoff is not going to be
significant but it's worth spending at least a little bit of time
investigating it.

- James

On Wed, Jan 16, 2013 at 3:10 PM, Mark Nottingham <[email-masked]> wrote:

> Dates in HTTP are explicitly in UTC (we just call it "GMT"), so the
> timezone data isn't helping (and may be hurting).
>
> Dates in HTTP have a granularity of one second; although people ask for
> finer granularity from time to time, giving them this capability is IMO
> asking for trouble (because clock sync and the speed of light / disk,
> combined with people's ignorance of distributed systems, leads to lots of
> bugs).
>
> That said, we could make millisecond granularity available in HTTP/2
> dates, as long as it's OK for that resolution to be lost when converting to
> HTTP/1. The other approach would be to introduce new headers that have the
> resolution and are able to transit a HTTP/1 connection, but the cost is
> pretty high there...
>
> WRT years up to 9999 -- yes. The method I used consumes an extra byte
> after 2106... and then another in 4147. However, just one more byte buys up
> to 36812!
>
> What's the use case for separating out hours from minutes? Given that most
> uses for dates in HTTP are driven by caching, and therefore need a direct,
> numeric comparison, why not just send the number?
>
>
> > Indeed ;-) ... Notice the way I hedged that with "generally tend" lol...
> I was hoping no one would notice ;-) ... what I would imagine is that delta
> That information will be lost on a HTTP/1 hop. It would be good to discuss
> how important that is; if it's really just optimisation information, it
> might be OK...
>
> The bigger impact that I can see is that people will now need to flag
> their ETags as "binary-compatible" or not when they set them, etc. Ew.
>
>

---

From: Roberto Peon <[email-masked]>
Date: Wed, 16 Jan 2013 15:48:01 -0800

How about setting epoch as the first request in the connection? :)
-=R

On Wed, Jan 16, 2013 at 3:45 PM, Nico Williams <[email-masked]>wrote:

> > Yep, but you either need to make the epoch start at least a few years
> ago (old Last-Modified times, is important for heuristic freshness), OR
> keep it signed (losing a bit).
> >

---

From: Roberto Peon <[email-masked]>
Date: Wed, 16 Jan 2013 15:49:02 -0800

Er, by which I mean that dates can be relative to the time stamped by
something and kept for the connection duration. That would reduce the
number of bits needed by a fair margin, assuming that is desirable.
-=R

---

From: Nico Williams <[email-masked]>
Date: Wed, 16 Jan 2013 17:53:19 -0600

On Wed, Jan 16, 2013 at 5:49 PM, Roberto Peon <[email-masked]> wrote:
> something and kept for the connection duration. That would reduce the number
> of bits needed by a fair margin, assuming that is desirable.

Associating state with connections would be quite a change, and it
doesn't work with middleboxes anyways.  If the epoch ends up in a
cookie then we gain nothing, and probably lose some bytes as well.

Nico
--

---

From: James M Snell <[email-masked]>
Date: Wed, 16 Jan 2013 16:01:27 -0800

I'd still like to retain the option of sub-second precision but this works
for me. Losing precision when translating to http/1 is acceptable.

---

From: Roberto Peon <[email-masked]>
Date: Wed, 16 Jan 2013 16:04:14 -0800

If we're doing compression, we're associating state with connections anyway.

-=R

On Wed, Jan 16, 2013 at 3:53 PM, Nico Williams <[email-masked]>wrote:

> number

---

From: Mark Nottingham <[email-masked]>
Date: Thu, 17 Jan 2013 11:10:05 +1100

> in an already very small format.

I definitely think it's worth consideration. I just put a flag (compress_dates; you have to set it in source, at least for now) on the simple compressor that lets you see the difference between compression and none...

* Without date compression:

732 req messages processed
              compressed | ratio min   max   std
req  http1       195,386 | 1.00  1.00  1.00  0.00
req simple        82,768 | 0.42  0.16  0.87  0.18

732 res messages processed
              compressed | ratio min   max   std
res  http1       159,968 | 1.00  1.00  1.00  0.00
res simple        92,188 | 0.58  0.12  0.89  0.16

* With date compression:

732 req messages processed
              compressed | ratio min   max   std
req  http1       195,386 | 1.00  1.00  1.00  0.00
req simple        82,357 | 0.42  0.16  0.87  0.18

732 res messages processed
              compressed | ratio min   max   std
res  http1       159,968 | 1.00  1.00  1.00  0.00
res simple        79,930 | 0.50  0.13  0.87  0.15

Note that the traces we currently have don't have If-Modified-Since in them very much, since they were started with a clean cache; this is why there's little difference in requests (Date doesn't occur much in reqs). 

Of course, we can get to the similar results by many other means...

Cheers,

---

From: James M Snell <[email-masked]>
Date: Wed, 16 Jan 2013 16:19:53 -0800

On Wed, Jan 16, 2013 at 4:10 PM, Mark Nottingham <[email-masked]> wrote:

> I definitely think it's worth consideration. I just put a flag
> (compress_dates; you have to set it in source, at least for now) on the
> simple compressor that lets you see the difference between compression and
> none...
>
>
+1 ... what's certain is that the specific encoding isn't critically
important, let's just pick the one that uses the fewest number of bytes and
includes all the information we need (or can optionally use) and go with
that. No amount of compression is going to do better.

 - James

---

From: Nico Williams <[email-masked]>
Date: Wed, 16 Jan 2013 18:25:18 -0600

> If we're doing compression, we're associating state with connections anyway.

As long as it's transparent and hop-by-hop, it works.  That would work
dates, huh.

---

From: Mark Nottingham <[email-masked]>
Date: Thu, 17 Jan 2013 11:47:54 +1100

> As long as it's transparent and hop-by-hop, it works.  That would work

The other factor is that if it's connection-specific, each hop will have to keep that state and properly translate it to the next one, introducing the possibility for errors.

---

From: Patrick McManus <[email-masked]>
Date: Wed, 16 Jan 2013 20:13:48 -0500

timestamps pretty clearly shouldn't have timezones in them.. that just
makes them harder to deal with and frankly creates a privacy/fingerprinting
problem.

I'd actually like the timestamp format to support sub millisecond
timescales.. (maybe another 8 bits) to help http scale in both directions.

---

From: Martin Thomson <[email-masked]>
Date: Wed, 16 Jan 2013 17:16:43 -0800

I'm less concerned about that sort of error than I am with getting
epoch right in the first place.  Though I note that you would want
this per-stream and possibly per-direction to allow for proper,
translation free multiplexing at intermediaries.  That seems like more
work than can be justified for a very modest saving over the already
significant gain.

---

From: Martin Thomson <[email-masked]>
Date: Wed, 16 Jan 2013 17:18:39 -0800

> timescales.. (maybe another 8 bits) to help http scale in both directions.

There have been times when I have wanted better-than-second resolution
on HTTP dates.  I'm not sure that nanosecond resolution is really
necessary, but I'm not fundamentally opposed to the idea.

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Thu, 17 Jan 2013 11:03:11 +0000

Content-Type: text/plain; charset=ISO-8859-1
--------
In message <[email-masked]>

>Then, given a sample of 100k
>for the date value.

<hat="Certified Time Nut">

With an 8 bytes fixed field, you could have 2 billion years with
~4 msec resolution if you just packed it as a binary number.

As a bonus, it's cheap to work with in computers...

If you do leading zero suppression it will be only five bytes for
most of the first century.

Please also loose any and all mention of timezones:  All timestamps
SHALL be UTC in HTTP, we do really not want to have to keep track
of fickle politicians fudging timezones on our load-balancers.

</hat>

-- 
Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
[email-masked]         | TCP/IP since RFC 956
FreeBSD committer       | BSD since 4.3-tahoe    
Never attribute to malice what can adequately be explained by incompetence.

---

From: RUELLAN Herve <[email-masked]>
Date: Thu, 17 Jan 2013 16:50:58 +0000

James,

> -----Original Message-----
> From: James M Snell [mailto:[email-masked]]
> Sent: mercredi 16 janvier 2013 23:07
> To: [email-masked]
> Subject: bohe and delta experimentation...
> 
> After going a number of scenarios with bohe using a variety of stream-
> compression scenarios it's painfully obvious that there is really no way
> around the CRIME issue when using stream-compression. So with that, I'm

From our dataset (see [1]), about 20% of the response headers are dates. The second type of values to optimize would be integer, that correspond to roughly 15% of the response headers.

One caveat: sometimes the value of a header that should be a date is not a date. Therefore an escape mechanism must be provided to encode these values.

Another interesting thing to investigate is encoding a value relatively to a previous value, as was proposed by Willy Tarreau. This is especially efficient for URLs.

Hervé.

[1] http://www.ietf.org/proceedings/85/slides/slides-85-httpbis-1.pdf

---

From: Frédéric Kayser <[email-masked]>
Date: Thu, 17 Jan 2013 21:16:25 +0100 (CET)

Hello,
state of the art compressors revert base64 encoding before compression et redo it during decompression (would be a nice feature to have when dealing with HTML/CSS files embedding files using Data URI scheme RFC 2397, but that's not in the header).

I find BOHE interesting but I don't like the idea of mixing what is basically ASCII text (7 bits values with most of the C0 control codes never used) and binary data (full 8 bits wide values, the way it's used in BOHE it also means a lot of values in the low end -near zero-).
An entropy coder will have to cope with a larger alphabet than just ASCII since it is "polluted" by binary data (if it appears infrequently it may end up taking more than 8-bits).

I would like to keep BOHE main principles (build a pre-agreed dictionary of the most common terms, record numerical values in "binary" and not text) but without introducing 8-bits values (avoiding the [00..1F] range would be nice too). It could lead to smaller Huffman tables (eventually order 1 context modelling) and less header overhead. A superfast 8 7-bits values to 7 8-bits values transformation could also be performed instead of using a full-featured entropy coder (Huffman or arithmetic coding), it could be interesting for HTTP servers to have different compression options.

Another point that has not been mentioned here is internationalisation:
http://www.w3.org/International/articles/idn-and-iri/

Why not get rid of punycode and percent-escaping in the headers? Converting them to plain UTF-8 (could be followed by an UTF-8 to 7-bits transformation).

Regards

----- Mail original -----
De: "Roberto Peon" <[email-masked]>
À: "Nico Williams" <[email-masked]>
Cc: "James M Snell" <[email-masked]>, [email-masked]
Envoyé: Jeudi 17 Janvier 2013 00:13:24
Objet: Re: bohe and delta experimentation...

Everything ends up as binary on either side today. So long as it arrives in the form that was transmitted, it doesn't matter what the encoding is. 
Cookies today are all mostly encoded in something from that binary, with the most likely being base-64 encoding. Base-64 encoding is highly compressible (using entropy coding). Encryption makes LZ77 and its ilk not efficient, but that is a separate thingie entirely :) 

-=R 

On Wed, Jan 16, 2013 at 2:47 PM, Nico Williams < [email-masked] > wrote: 

Nico 
--

---

From: Nico Williams <[email-masked]>
Date: Thu, 17 Jan 2013 14:50:11 -0600

> I find BOHE interesting but I don't like the idea of mixing what is basically ASCII text (7 bits values with most of the C0 control codes never used) and binary data (full 8 bits wide values, the w…

This is silly: we already have text and binary mixed all over the
place, such as in DNS, PKIX, Kerberos, SSHv2, and so on, and that's
never been a problem.  And how else should we encode textual values in
binary protocols anyways?  (I mean, besides using a Unicode encoding
rather than ASCII.)

> An entropy coder will have to cope with a larger alphabet than just ASCII since it is "polluted" by binary data (if it appears infrequently it may end up taking more than 8-bits).

Well, yes, so what?  We already apply generic compression algorithms
to so much mixed text and binary.  Clearly information theory does not
say it's impossible.

Nico
--

---

From: "Martin J. Dürst" <[email-masked]>
Date: Fri, 18 Jan 2013 15:36:48 +0900

> One caveat: sometimes the value of a header that should be a date is not a date. Therefore an escape mechanism must be provided to encode these values.

Or just drop it? It doesn't mean anything anyway, I guess.

Regards,   Martin.

---

From: "Martin J. Dürst" <[email-masked]>
Date: Fri, 18 Jan 2013 16:05:50 +0900

> number of bits needed by a fair margin, assuming that is desirable.

I was thinking about something similar, but on a bigger scale. If we 
have an encoding that can cover about 80 years (this is a simplification 
from Unix time does, which is 1970-2037 with 31 bits), then if we assume 
every server around the globe understands that we are currently 
somewhere between 2010 and 2020, we could just use that as a very rough 
base point. In that case, we can't use a strict offset, because that 
would make dates move around every time we move to a new decade. But 
what we can do is to just rotate around. For this rotation to work, we 
have to leave some empty space. Below is a very very rough table of how 
something like this could work.

Assume we have three bits in a prefix to label 8 different decades. Then 
in each decade as indicated below on the left side, the prefixes would 
be used with the meaning as indicated at the top of the table.

            1970 1980 1990 2000 2010 2020 2030 2040 2050 2060 2070 2080
             -    -    -    -    -    -    -    -    -    -    -    -
            1980 1990 2000 2010 2020 2030 2040 2050 2060 2070 2080 2090

1970-1980    0    1    2    3    x    x    x    x    x    x    x    x
1980-1990    0    1    2    3    4    x    x    x    x    x    x    x
1990-2000    0    1    2    3    4    5    x    x    x    x    x    x
2000-2010    x    1    2    3    4    5    6    x    x    x    x    x
2010-2020    x    x    2    3    4    5    6    7    x    x    x    x
2020-2030    x    x    x    3    4    5    6    7    0    x    x    x
2030-3040    x    x    x    x    4    5    6    7    0    1    x    x
2040-2050    x    x    x    x    x    5    6    7    0    1    2    x
2050-2060    x    x    x    x    x    x    6    7    0    1    2    3

So as an example, in our current decade, we would use prefix 2 to 
indicated dates between 1990 and 2000, prefix 4 to indicate dates in our 
decade, and prefix 7 to indicate dates between 2040 and 2050. Prefixes 0 
and 1 are on purpose currently out of service to avoid any 
misunderstadings (does prefix 0 refer to 1970-80 or to 2050-60?). This 
way we avoid problems at the start/end of a decade, when some servers 
might think they are still in the old decade, where some others already 
think they are in the new decade.

This is just a very rough sketch; the decades should be non-overlapping 
(1991-2000), it shouldn't be exactly decades, but some other intervals 
that we can cover with an exact number of bits. And maybe the 
past/future balance isn't ideal (currently 2 past and 3 future decades, 
maybe just 1 future and 4 past is better, or so).

Anyway, I hope you can see the basic principles of the system: Use a 
rotating scheme with a very rough current anchoring and a wide-enough 
period of slack to avoid ambiguities.

Regards,    Martin.

> On Wed, Jan 16, 2013 at 3:48 PM, Roberto Peon<[email-masked]>  wrote:
>
>> On Wed, Jan 16, 2013 at 3:45 PM, Nico Williams<[email-masked]>wrote:
>>
>>> On Wed, Jan 16, 2013 at 5:39 PM, Mark Nottingham<[email-masked]>  wrote:
>>>> On 17/01/2013, at 10:35 AM, Nico Williams<[email-masked]>
>>> wrote:

---

From: Mark Nottingham <[email-masked]>
Date: Fri, 18 Jan 2013 18:09:17 +1100

I feel like we're starting to focus a bit too closely on dates here (not just you, Martin!).

Let's look at the bigger picture, and other headers, before getting too deep here; we're talking about saving a handful of bytes at this point, and we haven't yet looked at URLs, etc. 

Cheers,

On 18/01/2013, at 6:05 PM, Martin J. Dürst <[email-masked]> wrote:

> I was thinking about something similar, but on a bigger scale. If we have an encoding that can cover about 80 years (this is a simplification from Unix time does, which is 1970-2037 with 31 bits), then if we assume every server around the globe understands that we are currently somewhere between 2010 and 2020, we could just use that as a very rough base point. In that case, we can't use a strict offset, because that would make dates move around every time we move to a new decade. But what we can do is to just rotate around. For this rotation to work, we have to leave some empty space. Below is a very very rough table of how something like this could work.
> 
> Assume we have three bits in a prefix to label 8 different decades. Then in each decade as indicated below on the left side, the prefixes would be used with the meaning as indicated at the top of the table.
> 
> So as an example, in our current decade, we would use prefix 2 to indicated dates between 1990 and 2000, prefix 4 to indicate dates in our decade, and prefix 7 to indicate dates between 2040 and 2050. Prefixes 0 and 1 are on purpose currently out of service to avoid any misunderstadings (does prefix 0 refer to 1970-80 or to 2050-60?). This way we avoid problems at the start/end of a decade, when some servers might think they are still in the old decade, where some others already think they are in the new decade.
> 
> This is just a very rough sketch; the decades should be non-overlapping (1991-2000), it shouldn't be exactly decades, but some other intervals that we can cover with an exact number of bits. And maybe the past/future balance isn't ideal (currently 2 past and 3 future decades, maybe just 1 future and 4 past is better, or so).
> 
> Anyway, I hope you can see the basic principles of the system: Use a rotating scheme with a very rough current anchoring and a wide-enough period of slack to avoid ambiguities.
> 
> Regards,    Martin.
> 
>

---

From: Frédéric Kayser <[email-masked]>
Date: Fri, 18 Jan 2013 09:11:48 +0100

Well, it's basic information theory, the header in its text form can be seen as an information source (with it's own alphabet and own probability distribution), binary data is a different one (bigger alphabet) with a different probability distribution (for instance with a bias toward zero if references to common strings are numbered starting from zero).

If you treat these two different information sources as a single source (since they end up in the same file -header in this case-) you'll have to cope with a bigger alphabet and a probability distribution that never really fits either of the sources (this can be seen like two players speaking different languages trying to play Scrabble forming words in their mother tongue but the game set is in fact designed for a third language or rather something like Esperanto, it will work but only up to a point and with a limited gaming experience).

For better compression both sources should be handled separately and this could be done with BOHE since fields are being tagged as text or binary (we could even imagine handling it as 3 sources:  text fields, binary fields and BOHE structure), but for relatively small data samples (hopefully headers are smaller than 4 kB) providing 2 or 3 Huffman tables could prove itself inefficient because of the overhead involved.
Dynamic Huffman could be a solution but it implies more computation and may take to much time to reflect the underlying probability distribution (slow start).
Another way would be to mimic one information source characteristics with the other one, this works if data coming from one source outnumbers the other one (for instance 2 or 3 times more text than binary data) in this case binary data could be transformed to look like text (limited to 7-bits, avoid C0 control codes) it works even better if a bias in one source can be remapped in the other one (i.e. binary values near zero become lowercase letters).

If the compression method cannot use LZ77/LZW/BWT (to hinder CRIME attacks) we should pay special attention to data modeling and the entropy coders to achieve interesting gains.

Frédéric

---

From: Amos Jeffries <[email-masked]>
Date: Fri, 18 Jan 2013 22:18:03 +1300

On 17/01/2013 12:25 p.m., Mark Nottingham wrote:
> On 17/01/2013, at 10:23 AM, Nico Williams wrote:
>
>> On Wed, Jan 16, 2013 at 5:10 PM, Mark Nottingham wrote:

Indeed. The main use of dates in HTTP/1 is communication about objects 
stored on the server and the client has no visible use for information 
about server timezone.

The main use-cases I hear presented for transferring TZ information are 
content personalization or user tracking by the server. In both cases it 
ought to be an optional header which can be a) suppressed by users not 
wanting to distribute such information about themselves and b) used by 
the serve in Vary: lists to signal the content customization.

Amos

---

From: Amos Jeffries <[email-masked]>
Date: Fri, 18 Jan 2013 22:21:40 +1300

> we're under 32 bits -- almost as low as 24, but still 4 bytes.  Can't

Noting that the Julian calendar was deprecated around 400 years ago. We 
are on Greogrian calendar these days.

Amos

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Fri, 18 Jan 2013 11:22:31 +0000

>are on Greogrian calendar these days.

The rumours of MJDs demise are certainly premature ;-)

There is one particular compelling argument for using a day-based
time representation:  It makes it possible communicate clearly when
faced with unpredictable leap-seconds.

A six byte format could be:

	Day			16 bits
	Fractional-Day		32 bits

The Day would be counted relative to a recent epoch (dec 21 2012 ? :-)
which would give us 179 years range into the future.

Time of day would be counted in units of 25 microseconds since
midnight UTC.  (A one byte shorter alternative would count in units
of 10 milliseconds.)

The crucial trick is that the fractional day field is an incomplete
radix, which leaves room for the variable length of day forced on us
with the current definition of UTC, while at the same time using
the day as the primary radix, allowing POSIX compliant operating
systems to not get confused.

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 18 Jan 2013 13:58:12 +0000

I'll try a shot at the URLs. Experimental data show that URLs often share the same beginning: for requests targeting a web sites, the URLs will usually start with the same scheme and host and possibly port. The beginning of the path is also usually shared by several URLs.

Therefore an efficient encoding for an URL is as a delta from a previous URL: the number of shared characters at the beginning, and the new characters. To reduce the state that need to be stored, it is possible to use only the previous URL as a reference.

Regards,

Hervé.

> From: Mark Nottingham [mailto:[email-masked]]
> Sent: vendredi 18 janvier 2013 08:09
> To: Martin J. Dürst
> Cc: Roberto Peon; Nico Williams; James M Snell; [email-masked]
> Subject: Re: bohe and delta experimentation...
> 
> Let's look at the bigger picture, and other headers, before getting too deep
> here; we're talking about saving a handful of bytes at this point, and we
> haven't yet looked at URLs, etc.
> 
> Cheers,
> 
> 
> > I was thinking about something similar, but on a bigger scale. If we have an
> encoding that can cover about 80 years (this is a simplification from Unix time
> does, which is 1970-2037 with 31 bits), then if we assume every server
> around the globe understands that we are currently somewhere between
> 2010 and 2020, we could just use that as a very rough base point. In that case,
> we can't use a strict offset, because that would make dates move around
> every time we move to a new decade. But what we can do is to just rotate
> around. For this rotation to work, we have to leave some empty space.
> Below is a very very rough table of how something like this could work.
> >
> > Assume we have three bits in a prefix to label 8 different decades. Then in
> each decade as indicated below on the left side, the prefixes would be used
> with the meaning as indicated at the top of the table.
> >
> > So as an example, in our current decade, we would use prefix 2 to indicated
> dates between 1990 and 2000, prefix 4 to indicate dates in our decade, and
> prefix 7 to indicate dates between 2040 and 2050. Prefixes 0 and 1 are on
> purpose currently out of service to avoid any misunderstadings (does prefix 0
> refer to 1970-80 or to 2050-60?). This way we avoid problems at the start/end
> of a decade, when some servers might think they are still in the old decade,
> where some others already think they are in the new decade.
> >
> (1991-2000), it shouldn't be exactly decades, but some other intervals that
> we can cover with an exact number of bits. And maybe the past/future
> balance isn't ideal (currently 2 past and 3 future decades, maybe just 1 future
> and 4 past is better, or so).
> >
> >>>> ago (old Last-Modified times, is important for heuristic
> >>>> freshness), OR keep it signed (losing a bit).
> >>>>>
> >>>> getting from 24 bytes to 4 is pretty good, and no compression
> >>>> scheme will do better.
> >>>>
> >>>>
> >>>
> >>
> 
> --

---

From: Willy Tarreau <[email-masked]>
Date: Fri, 18 Jan 2013 15:11:30 +0100

Hi Hervé,

> Therefore an efficient encoding for an URL is as a delta from a previous URL: the number of shared characters at the beginning, and the new characters. To reduce the state that need to be stored, i…

Some testing was already done with this several months ago and showed
promising results. However, I didn't have enough captures to play with
and I recall that Roberto had was more reserved on whether this would
work all the time or not.

I must admit that another issue concerns the amount of state to be kept
between two requests on intermediaries. Some unusually long URIs can be
several kB large, which would cause a real pain if they have to persist
during idle time.

Regards,
Willy

---

From: Willy Tarreau <[email-masked]>
Date: Fri, 18 Jan 2013 15:13:11 +0100

On Fri, Jan 18, 2013 at 03:11:30PM +0100, Willy Tarreau wrote:
> promising results.
(...)

Just found the link, "several months ago" was in June !

   http://comments.gmane.org/gmane.ietf.http-wg/10774

Willy

---

From: Roberto Peon <[email-masked]>
Date: Fri, 18 Jan 2013 09:22:11 -0800

This makes URLs vulnerable to the CRIME attack, and URLs definitely do
contain sensitive information often :(

This is true for anything which allows partial matches (I just can't figure
out how date could be sensitive, but if it could, even the encoding
suggested earlier by me would be dangerous).

I dropped exactly this (prefix match) functionality from delta early on
because of this.
-=R
On Jan 18, 2013 5:58 AM, "RUELLAN Herve" <[email-masked]> wrote:

> I'll try a shot at the URLs. Experimental data show that URLs often share
> the same beginning: for requests targeting a web sites, the URLs will
> usually start with the same scheme and host and possibly port. The
> beginning of the path is also usually shared by several URLs.
>
> Therefore an efficient encoding for an URL is as a delta from a previous
> URL: the number of shared characters at the beginning, and the new
> characters. To reduce the state that need to be stored, it is possible to
> use only the previous URL as a reference.
>
> Regards,
>
> Hervé.
>
> > I feel like we're starting to focus a bit too closely on dates here (not
> just you,
> > Martin!).
> >
> have an
> indicated
> that

---

From: Willy Tarreau <[email-masked]>
Date: Fri, 18 Jan 2013 19:18:19 +0100

Hi Roberto,

> I dropped exactly this (prefix match) functionality from delta early on

If we consider that anything is sensible to the CRIME attack, then we need
to go fully stateless I guess, otherwise it will be too hard to find out
what is safe to reuse and what is risky :-/

Willy

---

From: "Martin Nilsson" <[email-masked]>
Date: Fri, 18 Jan 2013 19:25:15 +0100

> work all the time or not.

Opera Mini uses a similar approach where common URI prefix is sent by the  
server and then used for inlines and links.

/Martin Nilsson

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

---

From: Roberto Peon <[email-masked]>
Date: Fri, 18 Jan 2013 11:22:51 -0800

Heh. We have more information about what is safe and what is not safe than
that!

Things we have fairly high confidence about w.r.t. CRIME:
  Partial-text matches are unsafe for any potentially sensitive field.
  Full-atom matches are safe for any field, including those with
potentially sensitive information.
  Dynamic entropy-coding, where the code-tables change based on input is
unsafe
  Static entropy-coding, where the code-tables have no relation to user
input is safe.

-=R

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 18 Jan 2013 14:40:41 -0500

> short-lived in the delta context.

Why do HTTP request messages have dates in them anyhow?

If they do not cause a state machine to behave differently then lets get
rid of them.

Dates that are content metadata are useful but putting the time in a
synchronous protocol has always seemed rather silly to me. The only use I
can see is to find out if the requester can config their machine to have
the right TOD on the clock. If that is all we are worried about then DNS
type 32 bit dates would be fine. DateTime in the DNS actually wraps every
UNIX epoch.

Given that we could eliminate the date altogether much of the time, having
the format wrap every 65 years or so does not seem a big problem to me.

Given that the universe we are in will wear out in a finite time it seems
unnecessary to use more than a 64 bit count of miliseconds or such. that is
only 8 bytes and easier to manage than the proposed format.

-- 
Website: http://hallambaker.com/

---

From: Willy Tarreau <[email-masked]>
Date: Fri, 18 Jan 2013 20:55:34 +0100

> type 32 bit dates would be fine. DateTime in the DNS actually wraps every

We could also have a date relative to the moment it's emitted. That way,
we get rid of the synchronization issues and risk of overflows while
keeping a short format (32 bit).

Just an idea.
Willy

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Fri, 18 Jan 2013 20:08:48 +0000

Content-Type: text/plain; charset=ISO-8859-1
--------
In message <[email-masked]>, Willy Tarreau writes:
>> the right TOD on the clock.

And that can be a very significant piece of information if you are
a bank or stock exchange, but HTTP requests are a totally inane way
to find out and we should not propagate that mistake.

---

From: "Adrien W. de Croy" <[email-masked]>
Date: Sat, 19 Jan 2013 01:00:31 +0000

------ Original Message ------
From: "Phillip Hallam-Baker" <[email-masked]>
>>stream-compression scenarios it's painfully obvious that there is 
>>really no way around the CRIME issue when using stream-compression. So 
>>with that, I'm turning my attention to the use of Roberto's delta 
>>encoding and exploring whether or not binary optimized values can make 
>>a significant difference (as opposed to simply dropping in 
>>huffman-encoded text everywhere).
>>
>>Right now, dates in http/1 requests are rather inefficient. The 
>>existing date-time format wastes a significant amount of space, albeit 
>>across only a relatively few headers. On the plus side, these tend to 
>>compress well, but given that the dates change frequently 
>>request-to-request, they will be short-lived in the delta context.
>

Date is used in caching, with Last-Modified it is used to calculate age 
of resource when served for purposes of estimating max-age for heuristic 
caching.

This presumes the same clock was used to generate Date as Last-Modified.

So I don't think we can lose it.

Adrien

---

From: RUELLAN Herve <[email-masked]>
Date: Mon, 21 Jan 2013 14:07:14 +0000

I agree that in the general case, partial-text matches are unsafe when considering CRIME attack. After all, this is the basis of the Deflate mechanism.

However, I would think that the more limited usage I proposed for URLs is mostly safe:
- First it doesn't mix different sources of information: URLs are kept with URLs. If URLs are considered as sensitive, this isn't great as the CRIME attack vector was based on URLs.
- Second, only the most recent URLs are kept in cache: after a few tries from the attacker, the cache will contain only the URLs used by the attacker, and the attack target will have been evicted from the cache.

Therefore, I think that using a common prefix to encode URLs in a more compact way is safe. In addition, we should probably take a deeper look at the CRIME attack, and include in HTTP/2.0 other mechanism to prevent it, or at least to decrease the risks linked to it. For example, there could be rules on how HTTP/2.0 sessions can be reused.

Hervé.

> From: Roberto Peon [mailto:[email-masked]]
> Sent: vendredi 18 janvier 2013 20:23
> To: Willy Tarreau
> Cc: RUELLAN Herve; Nico Williams; Martin J. Dürst; Mark Nottingham; James
> M Snell; [email-masked]
>   Full-atom matches are safe for any field, including those with potentially
> sensitive information.
>   Static entropy-coding, where the code-tables have no relation to user input
> is safe.
> 
> -=R
> 
>