Subject: [quicwg/base-drafts] Referencing strategy (#1129)

From: Martin Thomson <[email-masked]>
Date: Tue, 20 Feb 2018 19:49:16 -0800

(This is a little more nebulous than my other issues, but I think that there are concrete things that can be written down that will improve things.)

Referencing entries near the end of the table in a new header block is hazardous. If you just compress as you do in HPACK, you can end up pinning entries in the header table, making it impossible to add new entries. Thus, you have to stop referencing entries as they get nearer to the table capacity limit.

The draft isn't particularly good about explaining this exposure or outlining strategies that might be used to manage this (or the impact it might have on the selection of header table size, for example).

One framework for thinking about this is probably:

An encoder attempts new header fields to the header table at a certain rate.  Under ideal conditions, the insertion of header fields is never blocked by outstanding references to entries that might be evicted as a result of the insertion.  Under these ideal conditions, header fields enter the table at some rate, H.  Note that a new connection might see a higher rate of insertions, but the expectation is that the empty table will be able to absorb those insertions.  That is, H averages out in the long term to |H|.

New removals from the table are possible after one round trip if the header field is not referenced in that round trip.  Thus, an encoder preserves its ability to insert at a rate of |H| if it refrains from using the last |H|*RTT of the table.  To allow for both delays in delivering acknowledgments and variance in RTT and H, an encoder might choose to use a higher value that takes variance into consideration.  In extremis: (Mh*|H| + Nh*Hvar)*(Mr*RTT + Nr*RTTvar) where Mx > 1 and Nx > 0.  An encoder could measure these values and adapt the amount of buffer it reserves, or choose typical values.

A decoder should allow for this safety margin and - assuming no other constraints on space - set a table size that is this amount larger than is ideal for compression.  A decoder has to choose values based on typical (or some percentile, e.g., 90th) values, because it can't resize the table for each connection.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1129

---

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 26 Feb 2018 13:17:23 +0000 (UTC)

What is *rate*? In particular, what is the denominator?

Does there exist an effective referencing strategy without making the encoder learn more about the outside world -- RTT, what time it is?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1129#issuecomment-368500972

---

From: afrind <[email-masked]>
Date: Mon, 26 Feb 2018 09:23:34 -0800

Here's a simple referencing strategy:

An implementation would define a 'draining index', which is the smallest absolute index it may reference. Once there is an insert that reduces free space below the encoder's minimum threshold, increase draining index such that the size of the referenceable headers in the table is less than table size - min free space.  The reference count on the headers in the unreferenceable portion of the table should quickly fall to 0.

I think what Martin describes is a very precise way to calculate the optimal amount of free space to maintain, but he also suggests an encoder could "choose typical values".

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1129#issuecomment-368579476

---

From: Mike Bishop <[email-masked]>
Date: Mon, 26 Feb 2018 10:52:51 -0800

And (mostly as a note for whichever of us writes this PR), note that there's no pinning problem with a duplicate instruction referencing entries in this range, so the encoder algorithm should still look for matches, then encode as a duplicate, then a reference to the new entry.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1129#issuecomment-368607846

---

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 26 Feb 2018 13:13:28 -0800

> the encoder algorithm should still look for matches, then encode as a duplicate, then a reference to the new entry.

The encoder does not have to encode an entry as a duplicate each time it uses it, does it?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1129#issuecomment-368652419

---

From: afrind <[email-masked]>
Date: Mon, 26 Feb 2018 13:25:52 -0800

Duplication is never required.  It's just an optimization to keep important headers in the table when they are near the end.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1129#issuecomment-368656056

---

From: Mike Bishop <[email-masked]>
Date: Mon, 26 Feb 2018 22:08:18 +0000 (UTC)

The proposed algorithm is that the encoder should segment off the last part of the table as "risky to use."  In this proposed algorithm, entries in that region shouldn't be used, but a good alternative is to duplicate them and then use the newly-added non-risky entry.  (Although a reference to it has the potential to block.)

Obviously, this is just a sample algorithm, and implementations can choose different approaches, either more aggressive about duplicating or less.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1129#issuecomment-368668300

---

From: Martin Thomson <[email-masked]>
Date: Mon, 26 Feb 2018 22:41:53 +0000 (UTC)

That is the algorithm that my implementation follows.  I always choose to risk blocking.  You only get blocking if the frames are separated in transit, and proximal writes increases the chances of landing in the same packet.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1129#issuecomment-368677243