Re: [quicwg/base-drafts] Improve ACK_ECN frame encoding (e.g., use bit-vector) (#1439)

[Martin Thomson <[e-mail]>]

Coming back to this (because I want this closed, and the current situation is annoying me a little).

In general, there are three common things that we might want to signal:

1. a packet was received and it had the default marking (whatever the expectations are regarding that)
2. a packet was not received (a gap)
3. a packet was received with an ECN-CE marking

Receiving a packet with a non-default marking (either no marking at all, or ECT(1) if ECT(0) is expected) is an error condition and one that we don't necessarily want to optimize for.

So here is my suggestion, stealing the design @kazuho proposed, which includes bit-packing varints (something I'm not super-happy about, but the alternatives all seem to be worse, so I'm holding my nose a little).

```
 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     Largest Acknowledged (i)                ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                          ACK Delay (i)                      ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   Marking(8)  |        ACK Block Count (i)                  ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                           ACK (i)                          ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                          [ACK (i) ...]                     ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
```

Largest Acknowledged and ACK Delay are the same as always.

The Marking field takes three values that describes what the "default marking" is for packets that are acknowledged in this frame.  It takes three values: 0 means that it's ECT(0), 1 means ECT(1), and 2 means that there is no marking.  This means that if you get non-default markings, or you lose markings, then you might need to send multiple ACK frames.  (This is just for the sake of an example; I imagine that it would be better to define three types of ACK frame here to save the octet.)

The ACK Block Count indicates how many additional ACK blocks are signaled past the first.

Each ACK is a single varint.  A type is encoded into the lowest bit of the integer value.  Recovering type is stateful.  The observation is that though there are three types, the same type can't be repeated.  So, starting with the assumption that things start with a type of "gap", you can cover all possible angles.

Thus, a frame can be decoded using the following pseudocode:

```python
largest_acknowledged = read_varint()
ack_delay = read_varint()
default_marking = read_octet()
ack_count = read_varint()

ack_type = 0
default_types = [ 'ECT(0)', 'ECT(1)', 'unmarked' ]
ack_types  = ['gap', default_types[default_marking], 'marked']
start = largest_acknowledged
for i in range(0, ack_count+1):
   ack = read_varint()
   ack_type =  (ack_type + 1 + (ack&1)) % 3
   end = start + 1 + (ack>>1)
   print(f'{ack_types[ack_type]} from {start} to {end}\n')
   start = end + 1
```

The consequences of a change like this that I can see:

* It is much less efficient to signal changes in default marking (a design goal, see above)
* Markings are expressed perfectly (no counts and the associated problems with overcounting we have today)
* A gap can be signaled at the end of a block (we might want to forbid this explicitly: I can't see any point in allowing it)
* There is just one ACK frame format, even if it takes three frame type codepoints to express

Yes, the processing is a tiny bit more complicated, but I think that these changes represent a net win.

-- 
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/1439#issuecomment-409422427