Re: Unified ACK frame encoding

[Jana Iyengar <[e-mail]>]

Thanks for picking this one up, Martin. As I've said to you and to Kazuho,
I think if we can unify ACK and ACK_ECN frames "reasonably", I think
there's a lot of value in having a single frame format. The question of
course is if we can make this reasonable, so thanks for trying.

I need to think some more when I'm not as fried as I am right now, but I'm
not convinced about the encoding yet. A couple of more simplifying
assumptions might help:
1. A receiver receives 3 types of packets: Non-ECT, ECT, CE. It only
reports packets it has received.
2. We can assume that a sender uses ECT(0) or ECT(1), not both. Let's call
this default-ECT. If a future mechanism wants to use both, they can define
a new ACK frame. (Magnus and I checked on this with David Black, and he
agrees on the use of a single default ECT value.)

This means that you only need to report 3 types of ranges.

Further, if you have a separate bit to communicate ECN/non-ECN, meaning
that the receiver has seen ECT/CE bits and will echo them back, or the
receiver has not seen ECT/CE bits and won't echo them back, then you have 1
or 2 types of ranges.
ECN bit = 0: every range is of packets received, there's no ECN echo. This
is exactly the same ACK format as what we have now.
ECN bit = 1: ranges are of 2 types, default-ECT or CE. We need exactly 1
bit here to distinguish between these two ranges.

I'm aware that if we move this ECN bit to the frame type, then we end up
with two ACK frames again, but this is still far more unified than what we
have now. I'm also aware that we need a way for a receiver to say that it
received non-default ECT, but that can be separate, or an error even, and a
receiver could stop reporting ECN assuming that a network box is messing
with the bits.

On Wed, Aug 8, 2018 at 8:54 PM Martin Thomson <[e-mail]>
wrote:

> (More long emails. Sorry, I'm trying to either close these issues or
> prepare us for the interim.)
>
> We decided to take ACK_ECN to address an immediate need, but
> recognized that the encoding was suboptimal.  In the issue (see
> https://github.com/quicwg/base-drafts/issues/1439) we've
> beendiscussing an option for frame encoding that fixes a bunch of
> issues. That discussion covered a lot of ground, but here is my
> summary.
>
> This is what we have currently (using C/TLS style notation because I
> don't think ASCII art works in email):
>
>    struct ACK {
>       varint largest_acknowledged;
>       varint delay;
>       varint additional_block_count;
>       varint first_block;
>       struct {
>          varint gap;
>          varint block;
>       } blocks[additional_block_count];
>    };
>
>    struct ACK_ECN {
>       ACK ack;
>       varint ect0_count;
>       varint ect1_count;
>       varint ecnce_count;
>    };
>
> The most obvious issues are:
>
> A. There are two inconsistent encodings for acknowledgments depending
> on whether ECN is enabled.
> B. ACK_ECN has more overhead than ACK.  Ideally there are fewer
> disincentives to use ACK_ECN.
> C. The counting scheme is imprecise (you don't always know which
> packet was CE marked, and that could matter), which makes counting of
> ECN markings fragile in the presence of ACK loss.  This can lead to
> ECN being disabled despite it being fully functional.
> D. ECN counters always increase, and so they take more space to encode
> over time.
>
> Kazuho suggested a scheme that adds some modest complexity, but I
> think that it works and reduces other complexities such that it's
> probably a net win on the complexity front.  It also fixes these
> issues at the same time.
>
> The observation is that there are 5 things that you might want to say
> about any given packet number:
>
> 0. say nothing (i.e., I'm not acknowledging this packet; this is a gap)
> 1. packet received, no marking
> 2. packet received with an ECT(0) marking
> 3. packet received with an ECT(1) marking
> 4. packet received with an ECN-CE marking
>
> Now, the current system of describing ranges of packets is still
> pretty good.  An expression of the form "the next N packets are of
> type X" gets us an encoding that is small and fits traffic patterns
> well.  No point changing what is a fundamentally good encoding.
>
> So, we retain the maximum packet number and the idea of expressing
> ranges of packets. But each range is a tuple that expresses both the
> type of acknowledgement (or lack thereof) for that range and how many
> packets are in the range.
>
> That would produce an ACK frame in the following basic shape:
>
>    struct ACK {
>       varint largest_acknowledged;
>       varint delay;
>       varint range_count;
>       struct {
>          enum {gap,unmarked,ect0,ect1,ecnce} type;
>          varint count;
>       } ranges[range_count];
>    };
>
> The problem now is that we lost efficiency in a big way because the
> enum takes up a ton of space, for just 5 values.
>
> If we observe that there are 5 types, but you don't need to repeat the
> same type, then we can express the type in two bits.  That is, the
> type is interpreted as:
>
>    type = last_type + 1 + encoded_type (mod 5)
>
> Kazuho suggested that we pack these bits into the low two bits of a
> varint.  It's a little ugly, but I can't see a better option.  For
> instance, defining a new varint type would be considerably worse.  In
> addition to not being able to reuse varint code, my testing on
> encodings showed that a defining a new type with flags before the
> 2-bit length is surprisingly expensive.
>
> This produces a format like this:
>
>    struct ACK {
>       varint largest_acknowledged;
>       varint delay;
>       varint range_count;
>       varint ranges[range_count];
>    };
>
> As you can see, this is a considerable simplification.  The only trick
> is that more data is packed into each range value.  These values are
> encoded using something like:
>
>    encoded_type = (type + 4 - last_type) % 5
>        // encoded_type = type - last_type - 1 (mod 5)
>    range = encoded_type | (count << 2)
>
> The cost is that ranges take one more byte once they get above 16
> packets rather than at 64 packets as before.  It's also possible with
> this to encode a non-acknowledgment at the end of an ACK frame, which
> I think we can either prohibit or ignore.  But it fixes all the above
> problems.
>
> Is this a change worth making?
>
> Cheers,
> Martin
>
>
> A side note: This works whether we encode a count (as here) or a total
> number of octets (as has been proposed).  Similarly, we could count
> from the bottom rather than the top if we wanted to.  Those decisions
> are orthogonal to this; I'm trying as much as possible to retain the
> current design.
>
> Another note: We already have an issue on file for an ACK frame
> example.  That is still planned and that should help with interpreting
> the text.
>
>