Re: [quicwg/base-drafts] QPACK improvement: wrap absolute index values (#1644)

[Dmitri Tikhonov <[e-mail]>]

> I think doubling-or-more is attempting to guard against a situation where X was valid pre-wrap but about to expire, then enough entries are added that X is valid again post-wrap, and there's confusion about whether a new frame refers to the old or new one, correct? If so,

Almost, but not quite (or maybe we _are_ talking about the same thing -- in that case, apologies):  The particular values of the index -- pre-wrap or post-wrap -- do not really matter, as what matters is where they are relative to the position of the latest entry -- either to the left of it or to the right of it.

> the existing prohibition on evicting entries which still have references should ensure that there's no confusion

Please note that a dynamic entry may have no references (e.g. a speculative update).  The encoder is currently allowed to insert an unlimited number of entries into the table -- and evict them -- if no headers reference them.

The purpose of making the window larger than `MaxEntries` is to provide low and high boundaries.  Since the numbers wrap, the decoder must be able to classify an incoming _Largest Reference_ as something that it is supposed to possess (the lower bound, or past) or as a future reference that the header block should be blocked on (the upper bound).

The low bound is the absolute index of the decoder's newest entry in the dynamic table minus `MaxEntries` plus one.  A difference of `MaxEntries` or more would indicate that the encoder has inserted more than `MaxEntries` into the dynamic table, which is an error.

Thus, the window must be at least `MaxEntries` to cover entries that may already exist.  Because the index wraps, we need more room for the "future" entries -- those on which the header block will block on.  The proposal is to extend the window another `MaxEntries` and place additional restrictions on the encoder to guarantee that no more than that number of entries be unacknowledged.

The full range of values can be separated into two broad sections, Past and Future:

```
  1                                                                       MaxAbsIndexId

  |                Past                             |              Future             |
  |  Error area     |   Current Dynamic Table     X |                                 |

                                                  ^
                                                  |
                                                  /
                                      Latest Entry
```

_(Absolute index value increases from left to right and then wraps around.  The diagram has `X = MaxEntries` for convenience.)_

After classifying the incoming _Largest Reference_ as Past or Future, the decoder either:
- Marks the header block as blocked and parks the stream (Future);
- Processes the header block (Past, with _Largest Reference_ pointing to a valid table entry); or
- Produces an error if the _Largest Reference_ points to an already-evicted entry.

Reserving `MaxEntries` for the lower bound and a healthy number of entries for the future entries makes for rules that are easy to reason about.  This gives us a theoretical guarantee, so to speak, without using arguments such as "in practice, entries are larger then the fixed overhead."  A smaller window, I am afraid, will require much more complicated rules.

-- 
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/1644#issuecomment-411894178