Subject: Unified ACK frame encoding

From: Martin Thomson <[email-masked]>
Date: Thu, 9 Aug 2018 13:54:01 +1000

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

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 8 Aug 2018 23:36:02 -0700

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.

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 9 Aug 2018 16:06:45 +0900

2018-08-09 15:36 GMT+09:00 Jana Iyengar <[email-masked]>:
> 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.
>
> 1. A receiver receives 3 types of packets: Non-ECT, ECT, CE. It only reports
> packets it has received.
> 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..)

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 = 1: ranges are of 2 types, default-ECT or CE. We need exactly 1 bit
> here to distinguish between these two ranges.
>

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.

-- 
Kazuho Oku

---

From: "Brian Trammell (IETF)" <[email-masked]>
Date: Thu, 9 Aug 2018 09:52:08 +0200

hi Jana, all,

Also fried, but I've had a quick look at this...

> On 9 Aug 2018, at 08:36, Jana Iyengar <[email-masked]> wrote:
> 
> 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.

+1 to this -- if we find not-quite-varints in packet numbers uncomfortable, I can't see us finding rolling five-in-four encoding in the low bits of a different not-quite-varint less so.

> 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 also seems reasonable to me, and AFAICT lines up with all the current proposals for using ECT0/1 signaling.

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

+1. I'm really not bothered by pushing some of the ACK signaling bits into the frame type (especially if we describe these frames in a unified way, as we do with STREAM frames), as long as the structure of the frames is identical.

Cheers,

Brian

> 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 <[email-masked]> wrote:

---

From: Ian Swett <[email-masked]>
Date: Thu, 9 Aug 2018 16:14:31 -0400

There are a few things I like about this proposal:
1) It makes ECN and ACK_ECN either the same(or more similar)
2) As Kazuho said, it provides more precise feedback about which packets
were marked, which avoids some edge cases we've had to write up in the
current text around ack loss and being unsure of exactly when recovery is
exited.
3) It doesn't get more expensive as the connection goes on.  This is an
unfortunate property of the current design.

I find Jana's variation on this particularly interesting, because if ECN
isn't negotiated, I don't think there a reason to add any overhead.  From
personal experience, if you find a form of feedback valuable(whether it's
ECN or timestamps for one-way-delay), then you're happy to consume a few
extra bytes to get better feedback.  If the extra information isn't useful
for whatever reason, it's just wasted bytes.

So overall this seems like an improvement we should do, but I'd prefer a
variant that doesn't increase the ACK frame size when ECN is disabled or
there are no ECN marks to report.  FYI, if we need to steal a bit from the
number of ack blocks, I'm ok with that since I expect more than 32 ack
blocks to be very rare.

On Thu, Aug 9, 2018 at 3:52 AM Brian Trammell (IETF) <[email-masked]>
wrote:

> > 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.
>
> +1 to this -- if we find not-quite-varints in packet numbers
> uncomfortable, I can't see us finding rolling five-in-four encoding in the
> low bits of a different not-quite-varint less so.
>
> > 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..)
>
> > 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.
> have now.
> +1. I'm really not bothered by pushing some of the ACK signaling bits into
> the frame type (especially if we describe these frames in a unified way, as
> we do with STREAM frames), as long as the structure of the frames is
> identical.
>
> Cheers,
>
> Brian
>
> > 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.
> >

---

From: Martin Thomson <[email-masked]>
Date: Mon, 13 Aug 2018 16:29:43 +1000

On Fri, Aug 10, 2018 at 6:15 AM Ian Swett <[email-masked]> wrote:
> 2) As Kazuho said, it provides more precise feedback about which packets were marked, which avoids some edge cases we've had to write up in the current text around ack loss and being unsure of exactly when recovery is exited.
> 3) It doesn't get more expensive as the connection goes on.  This is an unfortunate property of the current design.
>
> I find Jana's variation on this particularly interesting, because if ECN isn't negotiated, I don't think there a reason to add any overhead.  From personal experience, if you find a form of feedback valuable(whether it's ECN or timestamps for one-way-delay), then you're happy to consume a few extra bytes to get better feedback.  If the extra information isn't useful for whatever reason, it's just wasted bytes.

OK, 4 values is definitely easier to reason about.  Merging ECT(0) and
ECT(1) into the same bucket is easy as long as we're OK with that.
The simpler encoding is easier to describe and write code for, and we
can just tolerate (or reject) two adjacent ranges of the same type,
just as we might tolerate (or reject) a trailing gap.

> So overall this seems like an improvement we should do, but I'd prefer a variant that doesn't increase the ACK frame size when ECN is disabled or there are no ECN marks to report.  FYI, if we need to steal a bit from the number of ack blocks, I'm ok with that since I expect more than 32 ack blocks to be very rare.

This is very close to a variant I suggested on the issue, which we
agreed pretty quickly wasn't great.  You can create two ACK frames,
one with the full expressiveness, and another that has the potential
to encode the ECN information.  Call the second one ACK_ECN...

I'm not convinced that optimizing for the awkward space between 16 and
64 is worth the extra complexity of a variant encoding of the frame.
There are other ways to optimize for the cost of that occasional octet
that seem like they would be more fruitful (like truncating ACK frames
more aggressively).

---

From: Magnus Westerlund <[email-masked]>
Date: Fri, 24 Aug 2018 16:51:20 +0200

Hi,

Catching up. I have posted on github 
(https://github.com/quicwg/base-drafts/issues/1439) some consideration 
what this implies in regards to ack frame sizes for different cases 
discussed.

I think Martins design here with being able to switch between each 
different type of marking as well as being able to reasonably efficient 
encode any range lengths without issues are a good one. My analysis on 
the github isssue showed that in low rate changes is is equivalent to a 
single byte design as well as being better capable of handling longer 
ranges of the same type.

I think it is worth continuing with this one. If one wants to use the 
2-bit type field for an explicitly encoded 4 alternative one or use the 
delta encoding can of course be discussed. I would prefer the delta 
encoding to avoid the information loss and the need for specifying what 
is the default ECT value and what to do in situations with a none 
expected one.

Cheers

Magnus

-- 

Magnus Westerlund

----------------------------------------------------------------------
Network Architecture & Protocols, Ericsson Research
----------------------------------------------------------------------
Ericsson AB                 | Phone  +46 10 7148287
Torshamnsgatan 23           | Mobile +46 73 0949079
SE-164 80 Stockholm, Sweden | mailto: [email-masked]
----------------------------------------------------------------------

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 26 Aug 2018 15:54:34 -0700

On balance I don't think I'm in favor of this bit-packing technique because
it complicates the ordinary ACK frame even for people who don't care about
ECN (and not doing so was part of why we decided to have another frame type
in the first place). Moreover, it's not a scalable extension method, so
anything *else* we want to add to the ACK frame will just need some other
technique.

-Ekr

On Fri, Aug 24, 2018 at 7:51 AM, Magnus Westerlund <
[email-masked]> wrote:

> Hi,
>
> Catching up. I have posted on github (https://github.com/quicwg/bas
> e-drafts/issues/1439) some consideration what this implies in regards to
> ack frame sizes for different cases discussed.
>
> encode any range lengths without issues are a good one. My analysis on the
> github isssue showed that in low rate changes is is equivalent to a single
> byte design as well as being better capable of handling longer ranges of
> the same type.
>
> encoding to avoid the information loss and the need for specifying what is
> the default ECT value and what to do in situations with a none expected one.
>
> Cheers
>
> Magnus
>
>
>

---

From: Martin Thomson <[email-masked]>
Date: Mon, 27 Aug 2018 18:11:37 +1000

I think that this is simpler.  See
https://github.com/quicwg/base-drafts/pull/1706 for a draft.
On Mon, Aug 27, 2018 at 8:55 AM Eric Rescorla <[email-masked]> wrote:
>
> On balance I don't think I'm in favor of this bit-packing technique because it complicates the ordinary ACK frame even for people who don't care about ECN (and not doing so was part of why we decided to have another frame type in the first place). Moreover, it's not a scalable extension method, so anything *else* we want to add to the ACK frame will just need some other technique.
>
> -Ekr
>
>
> On Fri, Aug 24, 2018 at 7:51 AM, Magnus Westerlund <[email-masked]> wrote:
>>
>> Hi,
>>
>> Catching up. I have posted on github (https://github.com/quicwg/base-drafts/issues/1439) some consideration what this implies in regards to ack frame sizes for different cases discussed.
>>
>> I think Martins design here with being able to switch between each different type of marking as well as being able to reasonably efficient encode any range lengths without issues are a good one. My analysis on the github isssue showed that in low rate changes is is equivalent to a single byte design as well as being better capable of handling longer ranges of the same type.
>>
>> I think it is worth continuing with this one. If one wants to use the 2-bit type field for an explicitly encoded 4 alternative one or use the delta encoding can of course be discussed. I would prefer the delta encoding to avoid the information loss and the need for specifying what is the default ECT value and what to do in situations with a none expected one.
>>
>> Cheers
>>
>> Magnus
>>
>>
>>

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 27 Aug 2018 06:01:37 -0700

Yes, this PR reflects what I believed you were proposing. I believe the
objections I raised here continue to apply.

-Ekr

On Mon, Aug 27, 2018 at 1:11 AM, Martin Thomson <[email-masked]>
wrote:

> > On balance I don't think I'm in favor of this bit-packing technique
> because it complicates the ordinary ACK frame even for people who don't
> care about ECN (and not doing so was part of why we decided to have another
> frame type in the first place). Moreover, it's not a scalable extension
> method, so anything *else* we want to add to the ACK frame will just need
> some other technique.
> >
> > -Ekr
> >
> >
> >> Catching up. I have posted on github (https://github.com/quicwg/
> base-drafts/issues/1439) some consideration what this implies in regards
> to ack frame sizes for different cases discussed.
> >>
> >>>> 2) As Kazuho said, it provides more precise feedback about which
> packets were marked, which avoids some edge cases we've had to write up in
> the current text around ack loss and being unsure of exactly when recovery
> is exited.
> >>>> 3) It doesn't get more expensive as the connection goes on.  This is
> an unfortunate property of the current design.
> >>>>
> >>>> I find Jana's variation on this particularly interesting, because if
> ECN isn't negotiated, I don't think there a reason to add any overhead.
> From personal experience, if you find a form of feedback valuable(whether
> it's ECN or timestamps for one-way-delay), then you're happy to consume a
> few extra bytes to get better feedback.  If the extra information isn't
> useful for whatever reason, it's just wasted bytes.
> >>>
> >>>> So overall this seems like an improvement we should do, but I'd
> prefer a variant that doesn't increase the ACK frame size when ECN is
> disabled or there are no ECN marks to report.  FYI, if we need to steal a
> bit from the number of ack blocks, I'm ok with that since I expect more
> than 32 ack blocks to be very rare.
> >>>

---

From: Martin Thomson <[email-masked]>
Date: Tue, 28 Aug 2018 12:16:35 +1000

I'm not saying that these are invalid complaints, but I don't reach
the same conclusion on the subjective assessment of balance of
concerns.

I don't think that this is significantly more complicated than
existing code. Rather than switch on all four values of the type, zero
(gap) and non-zero (acknowledged) is simple enough.  Extension in the
future necessarily uses new frame types, which aren't constrained.
For v1, I really hope that no one attempts to extend before we ship.
On Mon, Aug 27, 2018 at 11:02 PM Eric Rescorla <[email-masked]> wrote:
>
> Yes, this PR reflects what I believed you were proposing. I believe the objections I raised here continue to apply.
>
> -Ekr
>
>
> On Mon, Aug 27, 2018 at 1:11 AM, Martin Thomson <[email-masked]> wrote:
>>
>> >>>> I find Jana's variation on this particularly interesting, because if ECN isn't negotiated, I don't think there a reason to add any overhead.  >From personal experience, if you find a form of feedback valuable(whether it's ECN or timestamps for one-way-delay), then you're happy to consume a few extra bytes to get better feedback.  If the extra information isn't useful for whatever reason, it's just wasted bytes.
>> >>>

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 28 Aug 2018 16:01:12 +0900

2018年8月27日(月) 7:55 Eric Rescorla <[email-masked]>:
>
> On balance I don't think I'm in favor of this bit-packing technique because it complicates the ordinary ACK frame even for people who don't care about ECN (and not doing so was part of why we decided to have another frame type in the first place).

IMO, Martin's PR (#1706) is in good balance.

The design provides two big design wins to QUIC stacks that care about
ECN: unified frame type and accurate signaling of ECN.

The design also removes the requirement of requiring QUIC stacks that
*do not care about ECN handling ACK_ECN in some way*. At the moment,
QUIC endpoints do not negotiate the use of ECN in a secure form, which
means that a middlebox can inject an Initial frame carrying an ACK_ECN
frame. All endpoints (even those do not care about ECN) need to handle
that in some way. One way to mitigate the issue is to forbid use of
ACK_ECN in Initial packets, but that requires us to have a special
case... that would be an additional complexity.

Considering these aspects, I think that having a unified frame type
that encodes the type of every ACK block is a reasonable solution.

The only thing I feel (a bit) uneasy about #1706 is that it only has
four modes, requiring some negotiation to handle ECT(1) markings. My
preference is to send 5 modes (possibly encoded in 2-bits as we have
discussed on list), so that we do not need to make changes to the QUIC
specification for ECN experiments / future extensions.

> Moreover, it's not a scalable extension method, so anything *else* we want to add to the ACK frame will just need some other technique.
>
> -Ekr
>
>
>> I think Martins design here with being able to switch between each different type of marking as well as being able to reasonably efficient encode any range lengths without issues are a good one. My analysis on the github isssue showed that in low rate changes is is equivalent to a single byte design as well as being better capable of handling longer ranges of the same type..
>>
>>>> I find Jana's variation on this particularly interesting, because if ECN isn't negotiated, I don't think there a reason to add any overhead.  From personal experience, if you find a form of feedback valuable(whether it's ECN or timestamps for one-way-delay), then you're happy to consume a few extra bytes to get better feedback.  If the extra information isn't useful for whatever reason, it's just wasted bytes..
>>>

-- 
Kazuho Oku

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Tue, 28 Aug 2018 01:49:00 -0700

I agree with Kazuho.

I wonder if the ECT(1) could be carried in two bits as follows:

If a single unmarked packet globally disables ECN, then we can have an ECN
mode signalling frame that is only sent once before any ACK frame with
unmarked packets. This signalling frame disables ECN. The two bit code is
still the same as Martin’s proposal, but now it is possible to distinguish
between ECT(1) and ECT(0) explicitly.

Due to packet loss and reordering, the ECN mode signalling frame can be out
of sync with ACK’s, but it may not be a problem that a few ACK frames are
misinterpreted for a while. If this is a concern, the ECN mode frame can be
a prefix to every ACK frame, at least for a while, or until the same frame
is received from peer.

Peers that do not are about ECN can just ignore the signalling frame (or
reflect it once) and treat non-zero two-bit code as an ACK.

On 28 August 2018 at 09.02.29, Kazuho Oku ([email-masked]) wrote:

because it complicates the ordinary ACK frame even for people who don't
care about ECN (and not doing so was part of why we decided to have another
frame type in the first place).

> Moreover, it's not a scalable extension method, so anything *else* we
want to add to the ACK frame will just need some other technique.
[email-masked]> wrote:
>>
>> Hi,
>>
>> Catching up. I have posted on github (
https://github.com/quicwg/base-drafts/issues/1439) some consideration what
this implies in regards to ack frame sizes for different cases discussed.
the same type..
2-bit type field for an explicitly encoded 4 alternative one or use the
delta encoding can of course be discussed. I would prefer the delta
encoding to avoid the information loss and the need for specifying what is
the default ECT value and what to do in situations with a none expected
one.
it's ECN or timestamps for one-way-delay), then you're happy to consume a
few extra bytes to get better feedback. If the extra information isn't
useful for whatever reason, it's just wasted bytes..
>>>> So overall this seems like an improvement we should do, but I'd prefer
a variant that doesn't increase the ACK frame size when ECN is disabled or
there are no ECN marks to report. FYI, if we need to steal a bit from the
number of ack blocks, I'm ok with that since I expect more than 32 ack
blocks to be very rare.

-- 
Kazuho Oku

---

From: "Eggert, Lars" <[email-masked]>
Date: Tue, 28 Aug 2018 08:55:32 +0000

> that encodes the type of every ACK block is a reasonable solution.

+1 (as an individual)

Lars

---

From: "Brian Trammell (IETF)" <[email-masked]>
Date: Tue, 28 Aug 2018 10:58:24 +0200

hi Kazuho, all,

> On 28 Aug 2018, at 09:01, Kazuho Oku <[email-masked]> wrote:
> 

+1.

I'm not sure it's a good idea to have a structural feature in the protocol that separates "stacks that don't care about ECN" from "stacks that care about ECN" -- to the extent possible, the design of the protocol and the text of the standard should not encourage the former while encouraging the latter.

Cheers,

Brian

---

From: Magnus Westerlund <[email-masked]>
Date: Tue, 28 Aug 2018 13:37:51 +0200

Hi,

In regards to the below specific point:

> specification for ECN experiments / future extensions.

I think usage of a single ECT code point are going to work fine. The 
reason has to do with how the ECT(0) and ECT(1) codepoints are defined 
for the experimental usage. In legacy the two ECT codepoint are the 
same, but by default a QUIC stack will mark only with ECT(0). Thus, 
reception of ECT(1) means a non-compliant path that does remarking that 
should not occur. ECT(1) will be used for alternative behaviours, 
including different ECN marking schemes such as in L4S. For a  QUIC 
endpoint to use ECT(1) as marking when sending it needs to have 
awareness of the experiment and implement the correct response 
functions. It also needs to agree with the receiver about this 
capability. Although possible it could be limited to that the receiver 
only needs to know that ECT marking will be ECT(1) and that should be 
reported. However it might imply additional receiver behaviour changes. 
Thus, I fully expect that any such experiment in QUIC will require 
either a version or a Transport Parameter.

Why I think a single ECT code point will be sufficient is that if one 
start using both ECT code point simultaneous in one connection one will 
have to treat this as a multi-path scenario as it is to be expected that 
ECT(0) packets will not see the same path treatment as ECT(1) marked 
packets. Thus, for safe handling of these differences one appear to need 
to apply more changes to reporting to ensure that one treats the packet 
correctly and measure both paths independently. Thus some other 
mechanism will be in place for path differentiation or one need another 
ACK format anyway to report different time offsets since last received 
packet with the two different ECT codepoints where received etc.

Because of the above I don't see a strong reason to require a reporting 
scheme that requires the ACK block to be able to report all 5 types of 
type values. But, I did find Martin's delta encoding proposal a clever 
solution that has the advantage of providing explicit information. If 
people find the additional complexity of that fine, I would say go for it.

Cheers

Magnus Westerlund

---

From: Ian Swett <[email-masked]>
Date: Tue, 28 Aug 2018 09:41:32 -0400

My understanding of Martin's 5 type proposal was it eliminated the
possibility of ambiguous encodings.  ie: ACK block followed by another ACK
block, etc.  If it's slightly more expressive and eliminates ambiguity,
that seems like a slight improvement, but it makes the implementation
somewhat more complex, so I am fine with either approach.

The major negative of this change from my perspective is the loss of 2
bits, which makes a single byte ACK block pretty useless in a lot of cases
it was formerly useful.  I'd still prefer an approach that didn't burn the
bits in cases when there were no marks by using a bit in the type byte(or
some other approach), but overall I think this is a move in the right
direction, because it removes a lot of complexity introduced to deal with
the old design's ambiguity.

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 28 Aug 2018 22:58:45 +0900

> either a version or a Transport Parameter.

To clarify, my point is that if we could have an ACK frame that can
transmit all 5 modes (4 ECN types + gaps) precisely, the sender of the
packets and the middleboxes can use the ECN flags in the way they
want, without requiring an update on the receiver.

As you imply, it is true that we might need to make changes to the
receiver on how frequent it sends acknowledgements when it receives a
packet with non-standard ECN mark. But that might not always be the
case.

So my anticipation is (was) that having such kind of ACK frame will
help us. But how much the benefit is depends on how such experiments
would be make in practice, and I could well be missing something.

Anyways, it is good to see us arguing about such a minor point :-) I
agree to the other points that you have stated.

-- 
Kazuho Oku

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 28 Aug 2018 07:05:45 -0700

> the same conclusion on the subjective assessment of balance of

Sure. Sounds like a topic for New York.

> (gap) and non-zero (acknowledged) is simple enough.

Maybe I'm looking at the wrong PR? It's not so much a matter of individual
code complexity, but rather about embedding something in length that's not
length. Aside from being odd, this makes having a uniform encoder/decoder
hard, which is a real cost, especially if you use mechanically generated
encoders.

>   Extension in the

Right, that's my complaint. We know that this is a piece of the protocol we
like to extend. Arguably ECN is an extension and we have at least one other
extension that's been floated (timestamp), but the structure you've
designed here has no internal extensibility points, so any *other*
extensions require a huge change where we just have a different frame type.
That seems like an overly rigid design.

Taking a step back, the "natural" design is just to have a type byte in
front of every ACK block. I.e.,

enum { gap(0), unmarked(1), ... } AckType

struct {
    AckType type;
    varint length;
    ...
} AckBlock;

As you observe, this costs us a byte for every block compared to your
design, because we're stealing two bits from length, although that's only
true to the extent to which one-byte lengths remain useful. If you are
consistently pushed over into two-byte lengths for lengths in the range
65-255, then your encoding is equally efficient to the natural one. And as
I said above, you're left with no extensibility.

I have two thoughts about this:
1. I'm actually not that worried about the extra byte here. It's true that
ACKs are common, but one byte one way or another isn't going to kill us.
2. If we are that worried about the extra byte, we can address that problem
by having "ACKs" and "Extended ACKs" where ACKs don't have a type field and
we use the frame type to distinguish them (I think this is what Ian is
alluding to downthread).

So, IMO either the natural design or one which has an optional type byte is
better than what you have here.

-Ekr

On Mon, Aug 27, 2018 at 11:02 PM Eric Rescorla <[email-masked]> wrote:
> >> >> I think it is worth continuing with this one. If one wants to use
> the 2-bit type field for an explicitly encoded 4 alternative one or use the
> >> >>>> 3) It doesn't get more expensive as the connection goes on.  This
> is an unfortunate property of the current design.
> >> >>>>
> >> >>>> I find Jana's variation on this particularly interesting, because
> if ECN isn't negotiated, I don't think there a reason to add any overhead.

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 28 Aug 2018 07:27:53 -0700

On Tue, Aug 28, 2018 at 7:05 AM, Eric Rescorla <[email-masked]> wrote:

> Right, that's my complaint. We know that this is a piece of the protocol
> we like to extend. Arguably ECN is an extension and we have at least one
> other extension that's been floated (timestamp), but the structure you've
> 65-255,

Correction: Ian pointed out to me that because of the two varint bits, we
actually pay an extra byte whenever the range length would fit in 6 bits,
but not 4, which is a lot worse, because lengths in the range 17-64 are
going to be quite common.

-Ekr

then your encoding is equally efficient to the natural one. And as I said
> above, you're left with no extensibility.
>
> 2. If we are that worried about the extra byte, we can address that
> problem by having "ACKs" and "Extended ACKs" where ACKs don't have a type
> field and we use the frame type to distinguish them (I think this is what
> Ian is alluding to downthread).
>
> So, IMO either the natural design or one which has an optional type byte
> is better than what you have here.
>
> -Ekr
>

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Tue, 28 Aug 2018 07:58:33 -0700

You could have an encoding where each block is a varlen integer with no bit
magic.

The blocks alternate between ACK and GAP such that the first block is an
ACK and a trailing GAP is ignored.

Each ACK has an implicit mode which is one of: { unmarked, ECT(0), ECT(1),
ECT(2), ECN-CE }

The mode defaults to ACK_UNMARKED.

A modifier byte can be inserted in front of a block. The modifier has the
value 0b110000xx, xx = ACK mode.
The rules out 62-bit block lengths, but that is hardly a concern.

The modifier values are enumerated as:

enum ack_modifier = {
    ACK_UNMARKED = 0xC0,
    ACK_ECT_0 = 0xC1,
    ACK_ECT_1 = 0xC2,
    ACK_ECN_CE = 0xC3
};

When a modifier is present, the ACK mode changes for all subsequent ACK
blocks until a new modifier is seen.
Furthermore a modifier byte is always followed by an ACK block even if the
preceding block was not a GAP; this makes it efficient to have ECT-CE
followed by ECT(0) and so forth.

Example:
The modifier byte is enumerated as the coded: ACK_UNMARKED, ACK_ECT_0,
ACK_ECT_1, ACK_ECN_CE
An ACK block is shown as ACK(n) or GAP(n) where n is the block length.

block count(6)

ACK_ECT_0, ACK(4),
GAP (2),
ACK_ECT_CE, ACK(1),
ACK_ECT_0(4),
GAP(20),
ACK(10)

Here there are four ACK blocks and 2 GAP blocks. The first ack block is
ECT(0) marked, the second ACK block as ECT_CE marked, the third ACK block
is ECT(0) marked, and the last ACK block is also ECT(0) marked.

A block length can be zero which is simply ignored. It is never necessary
to use a zero length block.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 28 August 2018 at 16.29.02, Eric Rescorla ([email-masked]) wrote:

-Ekr

>> >> >> SE-164 80 Stockholm, Sweden | mailto:
>> magnus.westerlund@ericsson..com <[email-masked]>

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Tue, 28 Aug 2018 08:14:44 -0700

ECT(2) was a typo, there are only 4 modes:  { unmarked, ECT(0), ECT(1),
ECN-CE }, but more could be added in the future since there are 64
available code points in total.

On 28 August 2018 at 16.58.34, Mikkel Fahnøe Jørgensen ([email-masked])
wrote:

enum ack_modifier = {
    ACK_UNMARKED = 0xC0,
    ACK_ECT_0 = 0xC1,
    ACK_ECT_1 = 0xC2,
    ACK_ECN_CE = 0xC3
};

Example:

block count(6)

ACK_ECT_0, ACK(4),
GAP (2),
ACK_ECT_CE, ACK(1),
ACK_ECT_0(4),
GAP(20),
ACK(10)

Kind Regards,
Mikkel Fahnøe Jørgensen

-Ekr

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Tue, 28 Aug 2018 08:18:01 -0700

More typos sorry, ACK_ECT_0(4), should read ACK_ECT_0, ACK(4) so the
example becomes:

block count(6)

ACK_ECT_0, ACK(4),
GAP (2),
ACK_ECT_CE, ACK(1),
ACK_ECT_0, ACK(4),
GAP(20),
ACK(10)

Kind Regards,
Mikkel Fahnøe Jørgensen

On 28 August 2018 at 17.14.44, Mikkel Fahnøe Jørgensen ([email-masked])
wrote:

block count(6)

ACK_ECT_0, ACK(4),
GAP (2),
ACK_ECT_CE, ACK(1),
ACK_ECT_0(4),
GAP(20),
ACK(10)

---

From: Christian Huitema <[email-masked]>
Date: Tue, 28 Aug 2018 11:47:10 -0700

On 8/28/2018 7:27 AM, Eric Rescorla wrote:

>
> Correction: Ian pointed out to me that because of the two varint bits,
> we actually pay an extra byte whenever the range length would fit in 6
> bits, but not 4, which is a lot worse, because lengths in the range
> 17-64 are going to be quite common.
>
> -Ekr

There is another cost, but it is only borne if the implementation
actually supports ECN. Suppose the node receives a string of packets
with alternating CE marking, something like
ECT(1)-ECT(1)-CE-ECT(1)-ECT(1)-CE-ECT(1)-ECT(1)-CE, etc. This is not a
theoretical case: in DC-TCP, equilibrium is reached when the queue size
at the bottleneck hovers around the low water mark, and the algorithm is
specifically designed to produced frequent feedback. Now, if you have
that, you end up encoding a series of short ranges in the ACK, which
makes it way longer than just saying "I received everything but 3
packets were marked as CE".

This inflates not just the size of the ACKs, but also the number of
ranges in the "SACK dashboard" that nodes have to keep to manage the
sending of ACKs. When packets are received out of order, ranges can
normally be coalesced, but with ECN they can only be coalesced if all
packets had the same ECN marking.

So there is indeed a cost. I also have some sympathy for EKR's argument
about future extensions. ECN is just one of the signals that peers may
want to use to manage congestion and recovery. If nodes want to make
thoughtful decisions, they will certainly also look at RTT or one way
delays, and maybe at out-of-order deliveries. Would we want to use bits
in the "gap-range-length" to indicate that for packet number 73 the one
way delay was longer than usual, or would we use some other extension
mechanism? And if we have another extension mechanism, why not use it
for ECN as well?

-- Christian Huitema

---

From: Mirja Kühlewind <[email-masked]>
Date: Fri, 31 Aug 2018 18:11:40 +0200

Hi Christian,

I think DCTCP-like behavior is a different case and you might want to 
have an (private) extension with a different ACK format for that case 
anyway.

I think the scenarios we should design for is that CE marks will show up 
in a similar pattern as loss with AQM (maybe slightly more because when 
you drop a packet, the queue actually shrinks, but I guess that can be 
neglected for now).

Mirja

---

From: Mirja Kühlewind <[email-masked]>
Date: Fri, 31 Aug 2018 18:18:08 +0200

Hi!

> want, without requiring an update on the receiver.

Yes, I think it is important to have a feedback scheme that would make 
it possible to experiment with the use of ECT(1) without changing the 
receiver. So if we don't find a way to send separate feedback for 
ECT(1), I would rather encode ECT(0) and ECT(1) with the same type 
(instead of ECT(1) and Not-ECT).

No matter what, if you don't send ECT(1) feedback separately, you will 
not be able to detect path mangling which either changes ECT(0) to 
ECT(1) or the other way around.

Note that while ECT(0) and ECT(1) should not (anymore) be mixed up in 
the same connection, it can still be a valid case to send some of your 
packets as Not-ECT (also probably not recommended for QUIC but e.g. TCP 
does mark control packets and retransmission as Not-ECT).

Mirja