Re: Unified ACK frame encoding

[Kazuho Oku <[e-mail]>]

2018-08-09 15:36 GMT+09:00 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.

I am happy to see us arguing for unified frame type.

IMO, the format that Martin and I have proposed has two important
properties: unified frame type and precise signaling (i.e. indication
of which PN was received with which ECN flags).

I do not think that you have missed the latter (because your
suggestion retains that property), but I would like to reemphasize the
importance of having precise signals (Martin has covered that in his
original mail).

> 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.

It's good to know that we can possibly go with having just 4 states
(including gaps) rather than 5. Because if the number of the states
can be reduced to 4, the modes can be encoded without making the
diff-modulo calculation.

Having that said, I might prefer having 5 states that encodes into 2
bits rather than having 4 states, if having 4 states means that we
need to have a "prefilter" (i.e. a logic that remembers the default
ECT flag and do things if a non-default ECT flag is observed). In my
view, doing the diff-modulo calculation is easier than having a
"prefilter" that has it's own state that is bound to the lifetime of
the 5-tuple.

>
> 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.

I am not sure if I like the approach, because it requires QUIC stacks
to do a two-pass on the ack queue. I would rather prefer having an ACK
frame format that allows us to serialize the ack queue (which will be
an ordered list of PNs with ECN flags associated to each PN) in
one-pass.

>
> 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.
>>
>



-- 
Kazuho Oku