Subject: Proposal to replace ACK block count with ACK length

From: "Deval, Manasi" <[email-masked]>
Date: Mon, 11 Jun 2018 15:33:35 +0000

Hi All,

I was wondering why QUIC ACK header does not have a length field.

For example, while parsing the QUIC ACK, I find that an offload for segmentation or coalescing needs to identify an ACK interleaved between streams. As the ACK cannot be broken up and the chunk of ACK bytes needs to be moved as a block, reading the entire ACK to identify its length is a heavy lift.

Therefore, I'm proposing an ACK format with an ACK length instead of ACK block count.

What is the change?

*        ACK length is the first field, fixed length of 2 bytes.

*        ACK length is defined as the length of the entire ACK block, including the 2 byte ACK length.

*        ACK length replaces the ACK block count.

There is no change to Largest Acknowledged or ACK delay.

    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

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   |        ACK Length             |

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   |                     Largest Acknowledged (i) max 64 bit     ...

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   |                           ACK Delay (i)                     ...

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   |                          ACK Blocks (*)                     ...

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The advantages of the length field are:
-        Moving the ACK length to the front of the ACK allows the flexibility of either reading the entire ACK or reading the first 16 bits and skipping over the length. This is a useful feature for the case where ACK processing is split into multiple layers. Depending on the processor this is run on, there are different advantages -
o    If this is run on high end CPUs, the length helps identify the length for some SIMD modifications.
o   If this is a low end CPU, the multi-threading becomes more important for performance.
-        For the case where a receiver coalesce layer is augmenting the QUIC stack, I expect that it would separate the coalescing into stream frames, ACK frames and control frames. Availability of ACK length, simplifies this logic.
-        For a case where a transmit segmentation layer would like to make an intelligent decision on whether the ACK can be placed in a segment or not - it needs to know the size of ACK. Having to do a series of reads to identify the ACK size is inefficient.

Thanks,
Manasi

---

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 11 Jun 2018 11:43:15 -0400

On Mon, Jun 11, 2018 at 03:33:35PM +0000, Deval, Manasi wrote:
> -        Moving the ACK length to the front of the ACK allows the
>          flexibility of either reading the entire ACK or reading the
>          first 16 bits and skipping over the length. This is a useful
>          feature for the case where ACK processing is split into
>          multiple layers. Depending on the processor this is run on,
>          there are different advantages -

Just a note.  In my experience, the cost of parsing an ACK frame is
negligible compared to the cost of processing an ACK frame: that is,
poking at various memory locations to discard newly ACKed packets.

  - Dmitri.

---

From: Jana Iyengar <[email-masked]>
Date: Mon, 11 Jun 2018 15:11:25 -0700

You're right that we no longer have the ability to skip an ACK frame, and
this crept in when we moved to varints.

I believe your problem though is generally true of most frames not just
ACKs, since ids, packet numbers, and numbers in all frames are now all
varints. To skip any frame, you'll need to parse the varint fields in those
frames. If you have logic to process and skip varints, then skipping the
ack block section is merely repeating this operation (2*num_block+1) times.
Do you see specific value in skipping ACK frames over the other control
frames?

---

From: "Deval, Manasi" <[email-masked]>
Date: Tue, 12 Jun 2018 00:22:04 +0000

In general, varints require some specific logic for parsing. To skip over any header, I have to read every single varint. As the code sees Stream and ACK headers most frequently, that is my focus.  The Stream frame has a length in its third field.

ACK parsing, however, needs 6 + 2*num_blocks reads to identify length. There are two reads each for ‘largest acknowledged’, ‘ACK delay’ and ‘ACK block count’. The pain point is the total number of cycles parse an ACK. If I am processing 10M pps, where 10% - 30% of the packets have a piggybacked ACK, these cycles becomes a significant bottleneck.

Thanks,
Manasi

From: QUIC [mailto:[email-masked]] On Behalf Of Jana Iyengar
Sent: Monday, June 11, 2018 3:11 PM
To: Deval, Manasi <[email-masked]>; QUIC WG <[email-masked]>
Subject: Re: Proposal to replace ACK block count with ACK length

You're right that we no longer have the ability to skip an ACK frame, and this crept in when we moved to varints.
I believe your problem though is generally true of most frames not just ACKs, since ids, packet numbers, and numbers in all frames are now all varints. To skip any frame, you'll need to parse the varint fields in those frames. If you have logic to process and skip varints, then skipping the ack block section is merely repeating this operation (2*num_block+1) times. Do you see specific value in skipping ACK frames over the other control frames?

On Mon, Jun 11, 2018 at 8:43 AM Dmitri Tikhonov <[email-masked]<mailto:[email-masked]>> wrote:

  - Dmitri.

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 15 Jun 2018 09:11:01 -0700

I agree with Manasi here. This change would allow ack frame parsing to be
more self-contained, which is an advantage for the parser and also
potentially for parallelism (because you can quickly find the frame and
then process it in parallel).

-Ekr

On Mon, Jun 11, 2018 at 5:22 PM, Deval, Manasi <[email-masked]>
wrote:

> In general, varints require some specific logic for parsing. To skip over
> any header, I have to read every single varint. As the code sees Stream and
> ACK headers most frequently, that is my focus.  The Stream frame has a
> length in its third field.
>
>
>
> ACK parsing, however, needs 6 + 2*num_blocks reads to identify length.
> There are two reads each for ‘largest acknowledged’, ‘ACK delay’ and ‘ACK
> block count’. The pain point is the total number of cycles parse an ACK. If
> I am processing 10M pps, where 10% - 30% of the packets have a piggybacked
> ACK, these cycles becomes a significant bottleneck.
>
>
>
> Thanks,
>
> Manasi
>
>
>
>
>
>
>
> *From:* QUIC [mailto:[email-masked]] *On Behalf Of *Jana Iyengar
> *Sent:* Monday, June 11, 2018 3:11 PM
> *To:* Deval, Manasi <[email-masked]>; QUIC WG <[email-masked]>
> *Subject:* Re: Proposal to replace ACK block count with ACK length
>
>
>
> On Mon, Jun 11, 2018 at 8:43 AM Dmitri Tikhonov <
> [email-masked]> wrote:
>

---

From: Praveen Balasubramanian <[email-masked]>
Date: Fri, 15 Jun 2018 22:10:23 +0000

I agree as well since this can help reduce per packet processing overhead. ACKs are going to be the second most common frame type so no objections to special casing.

From: QUIC [mailto:[email-masked]] On Behalf Of Eric Rescorla
Sent: Friday, June 15, 2018 9:11 AM
To: Deval, Manasi <[email-masked]>
Cc: Jana Iyengar <[email-masked]>; QUIC WG <[email-masked]>
Subject: Re: Proposal to replace ACK block count with ACK length

I agree with Manasi here. This change would allow ack frame parsing to be more self-contained, which is an advantage for the parser and also potentially for parallelism (because you can quickly find the frame and then process it in parallel).

-Ekr

On Mon, Jun 11, 2018 at 5:22 PM, Deval, Manasi <[email-masked]<mailto:[email-masked]>> wrote:
In general, varints require some specific logic for parsing. To skip over any header, I have to read every single varint. As the code sees Stream and ACK headers most frequently, that is my focus.  The Stream frame has a length in its third field.

Thanks,
Manasi

From: QUIC [mailto:[email-masked]<mailto:quic-bounces@ietf..org>] On Behalf Of Jana Iyengar
Sent: Monday, June 11, 2018 3:11 PM
To: Deval, Manasi <[email-masked]<mailto:[email-masked]>>; QUIC WG <[email-masked]<mailto:[email-masked]>>
Subject: Re: Proposal to replace ACK block count with ACK length

  - Dmitri.

---

From: Jana Iyengar <[email-masked]>
Date: Fri, 15 Jun 2018 15:50:31 -0700

I don't have a strong opinion on this. I'm certainly not opposed to it.
Does anyone have a strong opposition?

On Fri, Jun 15, 2018 at 3:10 PM Praveen Balasubramanian <[email-masked]>
wrote:

> I agree as well since this can help reduce per packet processing overhead.
> ACKs are going to be the second most common frame type so no objections to
> special casing.
>
>
>
> *From:* QUIC [mailto:[email-masked]] *On Behalf Of *Eric Rescorla
> *Sent:* Friday, June 15, 2018 9:11 AM
> *To:* Deval, Manasi <[email-masked]>
> *Cc:* Jana Iyengar <[email-masked]>; QUIC WG <[email-masked]>
> *From:* QUIC [mailto:[email-masked] <quic-bounces@ietf..org>] *On
> Behalf Of *Jana Iyengar

---

From: Martin Thomson <[email-masked]>
Date: Fri, 15 Jun 2018 16:19:13 -0700

When we discussed this before, some people observed that this creates
a need to encode in two passes.  That's the trade-off here.  (Not
expressing an opinion.)
On Fri, Jun 15, 2018 at 3:51 PM Jana Iyengar <[email-masked]> wrote:
> On Fri, Jun 15, 2018 at 3:10 PM Praveen Balasubramanian <[email-masked]> wrote:
>>
>> On Mon, Jun 11, 2018 at 5:22 PM, Deval, Manasi <[email-masked]> wrote:
>>
>> On Mon, Jun 11, 2018 at 8:43 AM Dmitri Tikhonov <[email-masked]> wrote:
>>

---

From: Marten Seemann <[email-masked]>
Date: Sat, 16 Jun 2018 08:46:05 +0700

This proposal increases the size of the ACK frame by 1 byte in the common
case (less than 63 ACK ranges), since the ACK length field here always
consumes 2 bytes, whereas the ACK Block Count is a variable-length integer.
Considering how much work we put into minimising the size of the frames,
this feels like a step in the wrong direction.

Regarding the processing cost, I agree with Dmitri. Handling an ACK frame
requires looping over and making changes to a data structure that keeps
track of sent packets. This is much more expensive than simply parsing a
bunch of varints in the ACK frame. It seems unlikely that a multi-threaded
packet parser would offer any real-world performance benefits.

On Sat, Jun 16, 2018 at 6:19 AM Martin Thomson <[email-masked]>
wrote:

> >> I agree as well since this can help reduce per packet processing
> overhead. ACKs are going to be the second most common frame type so no
> objections to special casing.
> >>
> >>
> >>
> >> I agree with Manasi here. This change would allow ack frame parsing to
> be more self-contained, which is an advantage for the parser and also
> >> In general, varints require some specific logic for parsing. To skip
> over any header, I have to read every single varint. As the code sees
> Stream and ACK headers most frequently, that is my focus.  The Stream frame
> has a length in its third field.
> >>
> >>
> >>
> >> You're right that we no longer have the ability to skip an ACK frame,
> and this crept in when we moved to varints.
> >>
> >> On Mon, Jun 11, 2018 at 8:43 AM Dmitri Tikhonov
> <dtikhonov@litespeedtech..com> wrote:
> >>

---

From: Kazuho Oku <[email-masked]>
Date: Sat, 16 Jun 2018 10:57:13 +0900

> a need to encode in two passes.  That's the trade-off here.  (Not

I am not sure if we have that trade-off.

ACK frame as currently defined needs to be generated in two-pass
because the size of the ACK Block Count field depends on the number of
blocks you would actually emit, unless the QUIC stack maintains the
number of gaps in the ACK queue.

And I think that the proposed change would be fine because it does not
necessary increase the size of the ACK frame, if we remove ACK Block
Count field in exchange.

Instead of relying on the field, a receiver of the ACK frame can read
blocks until it consumes the number of bytes specified by the length
of the frame.

>>> On Mon, Jun 11, 2018 at 8:43 AM Dmitri Tikhonov <dtikhonov@litespeedtech..com> wrote:
>>>

-- 
Kazuho Oku

---

From: Christian Huitema <[email-masked]>
Date: Sat, 16 Jun 2018 00:10:42 -0700

> necessary increase the size of the ACK frame, if we remove ACK Block
Ack block count is generally one byte, the length would have to be two
bytes most of the time, especially if one wants to avoid 2 passes. So
that's one extra byte.
> blocks until it consumes the number of bytes specified by the length
Modulo handling of ECN counters, of course. In the ECN proposal, we have
three varints at the end of the ack frame, and that would make parsing a
variable number of ack blocks more interesting. So if we take the length
proposal, we have to make sure that the ECN counters  get moved before
the ack blocks.

-- Christian Huitema

---

From: "Eggert, Lars" <[email-masked]>
Date: Sat, 16 Jun 2018 08:01:29 +0000

On 2018-6-16, at 3:46, Marten Seemann <[email-masked]> wrote:
> Regarding the processing cost, I agree with Dmitri. Handling an ACK frame requires looping over and making changes to a data structure that keeps track of sent packets. This is much more expensive than simply parsing a bunch of varints in the ACK frame. It seems unlikely that a multi-threaded packet parser would offer any real-world performance benefits.

+1

Lars

---

From: Kazuho Oku <[email-masked]>
Date: Sat, 16 Jun 2018 18:25:58 +0900

> bytes most of the time, especially if one wants to avoid 2 passes. So

I am not sure if that is true.

I think that it would be safe to assume that most of the blocks or
gaps will be smaller than 65. On a high bandwidth scenario, some of
the blocks could become bigger than that, but IIUC having many big
blocks with gaps within is unlikely.

Therefore, we can assume that an ACK Length field of one-octet can
hold up to nearly 30 pairs of blocks and gaps (whereas one-octet ACK
Block Count can hold up to 63).

I think that that would be enough. Or, I would argue that if we think
that having nearly 30 pairs is not enough, I wonder that 63 could be
not enough as well.

Besides, I would like to note also that you can implement
space-efficient one-pass encoding of an ACK frame even if we replace
the Block Count field with a variable-length ACK Length field. For
one-pass encoding, I'd assume that you retain the size of each block
(or gap) and update that as new frames arrive. What you would do is as
you update the size of the block (or gap), you update the expected
size of the ACK frame as well. The size increments by one when the
size of the block becomes greater than 63, or decrements by one when
the size of the gap becomes smaller than 64.

> proposal, we have to make sure that the ECN counters  get moved before

Agreed.

-- 
Kazuho Oku

---

From: Eric Rescorla <[email-masked]>
Date: Sat, 16 Jun 2018 13:12:39 -0700

> packet parser would offer any real-world performance benefits.

I don't want to overstate the benefit here, but my point isn't that parsing
is expensive but that if you want to have a multithreaded packet processing
system, then it's nice to have a simpler data structure (the unparsed ACK
block) to hand to the ACK processing thread.

-Ekr

>> >> I believe your problem though is generally true of most frames not
>> just ACKs, since ids, packet numbers, and numbers in all frames are now all

---

From: Ian Swett <[email-masked]>
Date: Sat, 16 Jun 2018 19:34:28 -0400

I'm not a fan of this proposal, because I think it is impractical to drop
the number of ack blocks, because with the ECN proposal it becomes
impractically complex to parse.

If we don't remove the number of ack blocks, then the ack frame is larger,
but I don't think the extra size field is useful for most implementations.
Also, it means the length can disagree with the actual length, which add
complexity and the possibility of writing error-prone code.  The idea of
someone offloading ack processing and then proceeding to trust the length
seems like someone could get wrong and cause some concerning issues.

My experience is multithreaded packet processing is more cost and work than
it's worth.  Sure you can't fill a 100G NIC with one connection, but that
seems like an academic problem, not one for workloads I've seen.  Typically
the extra cost of multithreading outweighs its value.

To be clear, I don't think this is an awful idea, but I also don't see the
value and it adds complexity.  I read Manasi's email, but I don't think I
understand why any of those matter in practice.

On Sat, Jun 16, 2018 at 4:13 PM Eric Rescorla <[email-masked]> wrote:

> I don't want to overstate the benefit here, but my point isn't that
> parsing is expensive but that if you want to have a multithreaded packet
> processing system, then it's nice to have a simpler data structure (the
> unparsed ACK block) to hand to the ACK processing thread.
>
> -Ekr
>
>
>
>>> >> I agree with Manasi here. This change would allow ack frame parsing
>>> to be more self-contained, which is an advantage for the parser and also
>>> >> ACK parsing, however, needs 6 + 2*num_blocks reads to identify
>>> length. There are two reads each for ‘largest acknowledged’, ‘ACK delay’
>>> and ‘ACK block count’. The pain point is the total number of cycles parse
>>> an ACK. If I am processing 10M pps, where 10% - 30% of the packets have a
>>> piggybacked ACK, these cycles becomes a significant bottleneck.
>>> >>
>>> >>
>>> >>
>>> >> Thanks,
>>> >>
>>> >> Manasi
>>> >>
>>> >>
>>> >>
>>> >>
>>> >>
>>> >>
>>> >>

---

From: Kazuho Oku <[email-masked]>
Date: Sun, 17 Jun 2018 21:54:04 +0900

> impractically complex to parse.

For the ECN proposal, as Christian has suggested, we can move the ECN
counters before the ACK blocks. Then, it would not be complex to
parse.

And my view is that parsing becomes easier if we replace ACK Block
Count with ACK Frame Length.

Now, with ACK Block Count, we need to check the remaining number of
blocks and the remaining space in the packet payload for every block
that we parse. Failing to check either leads to a bug or a security
issue.

If we switch to ACK Frame Length, we need to only check the remaining
space in the frame.

I think that this is the biggest benefit of replacing ACK Block Count
with ACK Frame Length. OTOH the downside is that you need extra one to
two bits (one if the size of block / gap is expected to be below 65,
two if they are expected to be above that) for encoding ACK Frame
Length compared to ACK Block Count.

Having said that, I honestly wonder if all the frames could have it's
length being encoded (either explicitly or either as a signal that
says "to the end of the packet"). Consider something like below:

|0| frame-type (7) | frame-payload-length (i) | frame-payload (*) |
 or
|1| frame-type (7) | frame-payload (*) |

When MSB of the first octet set to zero, the length of the frame
payload is designated by the varint that immediately follows the frame
type.
When MSB of the first octet set to one, the length of the frame
payload spans to the end of the packet.

In this encoding, we can always omit the Length field of a STREAM
frame. So the overhead for carrying stream data will be indifferent in
practice.

For the ACK frame, we can omit the ACK Block Count field. And the
overhead will be one to two bits if the ACK frame is sent in the
middle of the packet (thereby using the encoding with explicit frame
payload length), or one octet or more shorter if ACK is the last frame
of the packet.

We are likely to see increase of overhead for most of the other types
of frames, but I do not think that would be an issue considering that
they will be far seldom seen compared to STREAMs and ACKs.

To summarize, my anticipation is that we can make all the frames
self-contained (i.e. the length can be determined without the
knowledge of how each frame is encoded) without any overhead, if we
agree on making the frame type space 1 bit smaller.

Finally, the biggest benefit of using a self-contained encoding of
frames is that we would have the ability to introduce new optional
frames without negotiation. By making the frames self-contained, QUIC
endpoints will have the freedom of ignoring the frames that they do
not understand.

Being able to send QUIC frames defined in extensions without
negotiating using Transport Parameters will be a win in both terms of
security (because clients' TP is sent in clear) and flexibility
(because we will be possible to send the extensions before we figure
out whether the peer supports that extension).

>>> this feels like a step in the wrong direction..
>>>
>>>> >> potentially for parallelism (because you can quickly find the frame and then
>>>> >> process it in parallel).
>>>> >>
>>>> >>
>>>> >>
>>>> >> -Ekr
>>>> >>
>>>> >>
>>>> >>
>>>> >>
>>>> >>
>>>> >> over any header, I have to read every single varint. As the code sees Stream
>>>> >> and ACK headers most frequently, that is my focus.  The Stream frame has a
>>>> >> length. There are two reads each for ‘largest acknowledged’, ‘ACK delay’ and
>>>> >> ‘ACK block count’. The pain point is the total number of cycles parse an
>>>> >> ACK. If I am processing 10M pps, where 10% - 30% of the packets have a
>>>> >> frames. If you have logic to process and skip varints, then skipping the ack
>>>> >> block section is merely repeating this operation (2*num_block+1) times. Do
>>>> >> you see specific value in skipping ACK frames over the other control frames?
>>>> >>
>>>> >>
>>>> >>
>>>> >>
>>>> >>

-- 
Kazuho Oku

---

From: Marten Seemann <[email-masked]>
Date: Sun, 17 Jun 2018 20:36:22 +0700

At least for my implementation, parsing doesn't become easier, it becomes
more complex with this proposal. My varint-parser always consumes as many
bytes as the varint requires, so after parsing a varint, I'd have to
introduce an additional check that this didn't overflow the ACK length
(e.g. consider that I parsed the ACK frame so far that only 2 bytes are
remaining according to ACK length field, but the next varint is 4 bytes
long).

In general, we've been moving the wire image towards making every encodable
value valid. This proposal moves us away from that principle:
* some small values are always invalid (the length can never be between 0
and 3)
* a lot of intermediate values are invalid (if the boundary falls inside a
varint, as described above)
Both these cases can't occur with the current ACK frame format.

On Sun, Jun 17, 2018 at 7:54 PM Kazuho Oku <[email-masked]> wrote:

> 2018-06-17 8:34 GMT+09:00 Ian Swett <ianswett=[email-masked]
> >:
> >>>> >> To: Deval, Manasi <[email-masked]>; QUIC WG <[email-masked]
> >

---

From: Kazuho Oku <[email-masked]>
Date: Sun, 17 Jun 2018 22:48:23 +0900

2018-06-17 22:36 GMT+09:00 Marten Seemann <[email-masked]>:
> introduce an additional check that this didn't overflow the ACK length (e.g.
> consider that I parsed the ACK frame so far that only 2 bytes are remaining
> according to ACK length field, but the next varint is 4 bytes long).

Isn't your varint parser checking that it has not (or will not) run
across the end of the packet payload for every ACK block it parses?
I'd assume that you would be doing that, because I think that is
necessary to avoid buffer overrun.

What I am saying that that check could be converted to a overrun check
against the end of the "frame payload", and that checking the
remaining block count becomes unnecessary, in case we replace ACK
Block Count with ACK Frame Length.

-- 
Kazuho Oku

---

From: Marten Seemann <[email-masked]>
Date: Sun, 17 Jun 2018 20:59:03 +0700

Maybe it's specific to Go, but I'm using a single io.Reader for the whole
packet, so as long as the packet payload is long enough, the varint parsing
will not fail.
I don't think that specifics of programming languages matter here though,
and I'm sure both frame formats can be reasonably implemented in C as well
as in Go. The reasons I'm opposed to Manasi's proposal are that it moves us
away from the principle that only reasonable values should be encodable,
and that it increases the size of the ACK frame, for the questionable
benefit of being able to parallelise the frame parser.

On Sun, Jun 17, 2018 at 8:48 PM Kazuho Oku <[email-masked]> wrote:

> (e.g.
> >> > value and it adds complexity.  I read Manasi's email, but I don't
> think
> >> > I
> >> >>> track of sent packets. This is much more expensive than simply
> parsing
> >> >>> a
> >> >>>> > I don't have a strong opinion on this. I'm certainly not opposed
> to
> >> >>>> > it.
> >> >>>> >> length. There are two reads each for ‘largest acknowledged’,
> ‘ACK
> >> >>>> >> delay’ and
> >> >>>> >> varints. To skip any frame, you'll need to parse the varint
> fields
> >> >>>> >> in those
> >> >>>> >> >          flexibility of either reading the entire ACK or
> reading
> >> >>>> >> > the
> >> >>>> >> >          multiple layers. Depending on the processor this is
> run
> >> >>>> >> > on,

---

From: "Deval, Manasi" <[email-masked]>
Date: Sun, 17 Jun 2018 21:24:39 +0000

Hi All,

I have made a list of objections to the proposal and the solutions to those objections discussed on this thread.

a.      Co-existence of length field with ECN field and ACK blocks.

Christian suggested to move the ECN fields to precede the ACK blocks. This is an elegant solution. Parsing entire list of ACK blocks to review ECN bits would have been annoying, even though it can work.

b.      There are two cases to be parsed – entire ACK and parse ACK to identify length. There are some reservations when ACK parsing gets harder for the case where the entire header needs to be parsed.

Agreement from several folks here. In the original ACK defined in draft 12 of the slide, one would count down number of ACK blocks to get to the end of the packet. In the proposal I made, one would count down the length to identify the end of the packet. The logic is very similar in cycle count and complexity. Several folks also commented to this effect.

c.      Multi-threaded packet processing

I would expect that there are 10s of 1000s of connections in use at any time for a server with a high speed link. Multi-threading to handle each of these flows / connections in parallel is necessity to be able to support large number of connections on a high speed link. Tx segmentation, Rx coalescing are well known strategies to reduce the processing cost. In initial stages, code is often written as a single-threaded and then re-factored to parallelize cycle intensive operations. In order to allow this protocol to scale in future, I would suggest we do not preclude this case.

d.      Increase in ACK size by 1 byte.

I do not see this as a serious issue but if folks but we can consider making this a varint, if others have strong feelings about it. It’s a trade-off : 2 reads to save 1 byte.

e.      Every encodable value should be valid

Not every length will be valid. This is inherent to lengths. This same issue ails the ‘payload length’ in QUIC header. Not only does the issue exist for small values, it also applies to large values since data stream will be sent after crypto negotiation.  E.g.  - how does one craft a payload with 62 bit payload length in a large header?

Thanks,

Manasi

From: Marten Seemann [mailto:[email-masked]]
Sent: Sunday, June 17, 2018 6:59 AM
To: Kazuho Oku <[email-masked]>
Cc: Ian Swett <ianswett=[email-masked]>; Eric Rescorla <[email-masked]>; Jana Iyengar <[email-masked]>; Praveen Balasubramanian <[email-masked]>; IETF QUIC WG <[email-masked]>; Martin Thomson <[email-masked]>; Deval, Manasi <[email-masked]>
Subject: Re: Proposal to replace ACK block count with ACK length

Maybe it's specific to Go, but I'm using a single io.Reader for the whole packet, so as long as the packet payload is long enough, the varint parsing will not fail.
I don't think that specifics of programming languages matter here though, and I'm sure both frame formats can be reasonably implemented in C as well as in Go. The reasons I'm opposed to Manasi's proposal are that it moves us away from the principle that only reasonable values should be encodable, and that it increases the size of the ACK frame, for the questionable benefit of being able to parallelise the frame parser.

On Sun, Jun 17, 2018 at 8:48 PM Kazuho Oku <[email-masked]<mailto:[email-masked]>> wrote:

> On Sun, Jun 17, 2018 at 7:54 PM Kazuho Oku <[email-masked]<mailto:[email-masked]>> wrote:
>>
>> 2018-06-17 8:34 GMT+09:00 Ian Swett
>> <ianswett=[email-masked]<mailto:[email-masked]>>:
>> > On Sat, Jun 16, 2018 at 4:13 PM Eric Rescorla <[email-masked]<mailto:[email-masked]>> wrote:
>> >>
>> >> On Fri, Jun 15, 2018 at 6:46 PM, Marten Seemann
>> >> <[email-masked]<mailto:[email-masked]>>
>> >> wrote:
>> >>>
>> >>> On Sat, Jun 16, 2018 at 6:19 AM Martin Thomson
>> >>> <[email-masked]<mailto:[email-masked]>>
>> >>> wrote:
>> >>>>
>> >>>> On Fri, Jun 15, 2018 at 3:51 PM Jana Iyengar <[email-masked]<mailto:[email-masked]>>
>> >>>> wrote:
>> >>>> >
>> >>>> > On Fri, Jun 15, 2018 at 3:10 PM Praveen Balasubramanian
>> >>>> > <[email-masked]<mailto:[email-masked]>> wrote:
>> >>>> >>
>> >>>> >> From: QUIC [mailto:[email-masked]<mailto:[email-masked]>] On Behalf Of Eric
>> >>>> >> Rescorla
>> >>>> >> To: Deval, Manasi <[email-masked]<mailto:[email-masked]>>
>> >>>> >> Cc: Jana Iyengar <[email-masked]<mailto:[email-masked]>>; QUIC WG <[email-masked]<mailto:[email-masked]>>
>> >>>> >> On Mon, Jun 11, 2018 at 5:22 PM, Deval, Manasi
>> >>>> >> <[email-masked]<mailto:[email-masked]>> wrote:
>> >>>> >>
>> >>>> >> From: QUIC [mailto:[email-masked]<mailto:[email-masked]>] On Behalf Of Jana
>> >>>> >> Iyengar
>> >>>> >> <dtikhonov@litespeedtech..com<mailto:dtikhonov@litespeedtech..com>> wrote:
>> >>>> >>

--
Kazuho Oku

---

From: "Deval, Manasi" <[email-masked]>
Date: Tue, 19 Jun 2018 18:21:35 +0000

Hi All,

Do we have agreement here to create a new PR?

Thanks,
Manasi

From: Deval, Manasi
Sent: Sunday, June 17, 2018 2:25 PM
To: Marten Seemann <[email-masked]>; Kazuho Oku <[email-masked]>
Cc: Ian Swett <ianswett=[email-masked]>; Eric Rescorla <[email-masked]>; Jana Iyengar <[email-masked]>; Praveen Balasubramanian <[email-masked]>; IETF QUIC WG <[email-masked]>; Martin Thomson <[email-masked]>
Subject: RE: Proposal to replace ACK block count with ACK length

Hi All,

Thanks,

Manasi

From: Marten Seemann [mailto:[email-masked]]
Sent: Sunday, June 17, 2018 6:59 AM
To: Kazuho Oku <[email-masked]<mailto:[email-masked]>>
Cc: Ian Swett <ianswett=[email-masked]<mailto:ianswett=[email-masked]>>; Eric Rescorla <[email-masked]<mailto:[email-masked]>>; Jana Iyengar <[email-masked]<mailto:[email-masked]>>; Praveen Balasubramanian <[email-masked]<mailto:[email-masked]>>; IETF QUIC WG <[email-masked]<mailto:[email-masked]>>; Martin Thomson <[email-masked]<mailto:[email-masked]>>; Deval, Manasi <[email-masked]<mailto:[email-masked]>>
Subject: Re: Proposal to replace ACK block count with ACK length

--
Kazuho Oku

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Tue, 19 Jun 2018 11:25:47 -0700

I don’t think you addressed e) at all. Clearly there is an end of buffer
check, but that is not the same as requiring additonal checks at many other
levels.

On 19 June 2018 at 20.22.03, Deval, Manasi ([email-masked]) wrote:

Not every length will be valid. This is inherent to lengths. This same
issue ails the ‘payload length’ in QUIC header. Not only does the issue
exist for small values, it also applies to large values since data stream
will be sent after crypto negotiation.  E.g.  - how does one craft a
payload with 62 bit payload length in a large header?

---

From: Ian Swett <[email-masked]>
Date: Tue, 19 Jun 2018 14:25:49 -0400

I'm still not interested in this change, for the reasons I stated above.

On Tue, Jun 19, 2018 at 2:21 PM Deval, Manasi <[email-masked]>
wrote:

> *From:* Deval, Manasi
> *Sent:* Sunday, June 17, 2018 2:25 PM
> *To:* Marten Seemann <[email-masked]>; Kazuho Oku <
> [email-masked]>
> *Cc:* Ian Swett <ianswett=[email-masked]>; Eric Rescorla <
> [email-masked]>; Jana Iyengar <[email-masked]>; Praveen Balasubramanian
> <[email-masked]>; IETF QUIC WG <[email-masked]>; Martin Thomson <
> [email-masked]>
> *Subject:* RE: Proposal to replace ACK block count with ACK length
>
>
>
> Hi All,
>
>
>
> I have made a list of objections to the proposal and the solutions to
> those objections discussed on this thread.
>
>
>
> Christian suggested to move the ECN fields to precede the ACK blocks. This
> is an elegant solution. Parsing entire list of ACK blocks to review ECN
> bits would have been annoying, even though it can work.
>
>
>
> b.      There are two cases to be parsed – entire ACK and parse ACK to
> identify length. There are some reservations when ACK parsing gets harder
> for the case where the entire header needs to be parsed.
>
>
>
> Agreement from several folks here. In the original ACK defined in draft 12
> of the slide, one would count down number of ACK blocks to get to the end
> of the packet. In the proposal I made, one would count down the length to
> identify the end of the packet. The logic is very similar in cycle count
> and complexity. Several folks also commented to this effect.
>
>
>
> I would expect that there are 10s of 1000s of connections in use at any
> time for a server with a high speed link. Multi-threading to handle each of
> these flows / connections in parallel is necessity to be able to support
> large number of connections on a high speed link. Tx segmentation, Rx
> coalescing are well known strategies to reduce the processing cost. In
> initial stages, code is often written as a single-threaded and then
> re-factored to parallelize cycle intensive operations. In order to allow
> this protocol to scale in future, I would suggest we do not preclude this
> case.
>
>
>
> I do not see this as a serious issue but if folks but we can consider
> making this a varint, if others have strong feelings about it. It’s a
> trade-off : 2 reads to save 1 byte.
>
>
>
> *From:* Marten Seemann [mailto:[email-masked]
> <[email-masked]>]
> *Sent:* Sunday, June 17, 2018 6:59 AM
> *To:* Kazuho Oku <[email-masked]>
> *Cc:* Ian Swett <ianswett=[email-masked]>; Eric Rescorla <
> [email-masked]>; Jana Iyengar <[email-masked]>; Praveen Balasubramanian
> <[email-masked]>; IETF QUIC WG <[email-masked]>; Martin Thomson <
> [email-masked]>; Deval, Manasi <[email-masked]>
> >> <ianswett=[email-masked]>:
> >> >> <[email-masked]>
> >> >> wrote:
> >> >>>
> >> >>> <[email-masked]>
> >> >>> wrote:
> >> >>>>
> >> >>>> > <[email-masked]> wrote:
> >> >>>> >>
> >> >>>> >> <[email-masked]> wrote:
> >> >>>> >>

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 19 Jun 2018 12:11:32 -0700

> check, but that is not the same as requiring additonal checks at many other

Not Manasi, but I don't understand (e).

Here's the relevant section of the Minq decoder.

    func (f *ackFrame) unmarshal(buf []byte) (int, error) {
        // Omitted the section that decoded the header

        // Now decode each block
        for i := uint64(0); i < f.AckBlockCount; i++ {
            blk := &ackBlock{}
            n, err := syntax.Unmarshal(buf, blk)
            if err != nil {
                return 0, err
            }
            buf = buf[n:]
            read += n

            f.AckBlockSection = append(f.AckBlockSection, blk)
        }

        return read, nil
    }

You pass in the entire remainder of the packet and then it parses
out the ACK frame and then returns the amount consumed.

If we were to change to what Manasi proposes, it would look like:

    func (f *ackFrame) unmarshal(buf []byte) (int, error) {
        // Omitted the section that decoded the header

        // Trim the buffer to the remainder length
        if f.AckLength > len(buf) {
                return 0, ProtocolInvalidError
        }
        buf = buf[f.AckLength:]

        for len(buf) > 0 {
            blk := &ackBlock{}
            n, err := syntax.Unmarshal(buf, blk)
            if err != nil {
                return 0, err
            }
            buf = buf[n:]
            read += n

            f.AckBlockSection = append(f.AckBlockSection, blk)
        }

        return read, nil
    }

Is your concern here the additional length check after the
comment "Trim the buffer"? Something else?

-Ekr

---

From: "Deval, Manasi" <[email-masked]>
Date: Tue, 19 Jun 2018 20:19:05 +0000

I have the same question as Eric.

From: Eric Rescorla [mailto:[email-masked]]
Sent: Tuesday, June 19, 2018 12:12 PM
To: Mikkel Fahnøe Jørgensen <[email-masked]>
Cc: Kazuho Oku <[email-masked]>; Deval, Manasi <[email-masked]>; Marten Seemann <[email-masked]>; Praveen Balasubramanian <[email-masked]>; Jana Iyengar <[email-masked]>; IETF QUIC WG <[email-masked]>; Martin Thomson <[email-masked]>; Ian Swett <ianswett=[email-masked]>
Subject: Re: Proposal to replace ACK block count with ACK length

On Tue, Jun 19, 2018 at 11:25 AM, Mikkel Fahnøe Jørgensen <[email-masked]<mailto:[email-masked]>> wrote:
I don’t think you addressed e) at all. Clearly there is an end of buffer check, but that is not the same as requiring additonal checks at many other levels.

        // Now decode each block

        return read, nil
    }

        for len(buf) > 0 {
            blk := &ackBlock{}

        return read, nil
    }

-Ekr

On 19 June 2018 at 20.22.03, Deval, Manasi ([email-masked]<mailto:[email-masked]>) wrote:

---

From: "Deval, Manasi" <[email-masked]>
Date: Tue, 19 Jun 2018 20:21:19 +0000

Hi Ian,

Here is another attempt to solve the objections you raised:

>I'm not a fan of this proposal, because I think it is impractical to drop the number of ack blocks, because with the ECN proposal it becomes impractically complex to parse.
Is there a reason the proposal from Christian does not solve this problem?

>If we don't remove the number of ack blocks, then the ack frame is larger, but I don't think the extra size field is useful for most implementations.  Also, it means the length can disagree with the actual length, which add complexity and the possibility of writing error-prone code.  The idea of someone offloading ack processing and then proceeding to trust the length seems like someone could get wrong and cause some concerning issues.
The risk of disagreement between ack blocks and ack block count is same as the risk of disagreement between ack blocks and ack length. Either way this needs to be counted up while creating the ACK and counted down while parsing it. The possibility of error is the same. Getting the ack block count wrong is as problematic as getting the ack length wrong. Do you agree?

>My experience is multithreaded packet processing is more cost and work than it's worth.  Sure you can't fill a 100G NIC with one connection, but that seems like an academic problem, not one for workloads I've seen.  Typically the extra cost of multithreading outweighs its value.
The value is two fold – pre-processing and multi-threading. If we pre-process the received packets such that ACKs and streams can be coalesced, the receive side can indicate a large chunk of information though the kernel, reducing the cost of system call and protocol overhead. This is the same concept as UDP segmentation taken a step further on receive side. After this chunk is indicated into the QUIC protocol, the protocol may process stream and ACK in parallel. While folks may or may not utilize this, there is an advantage here.

Thanks,
Manasi

From: Ian Swett [mailto:[email-masked]]
Sent: Tuesday, June 19, 2018 11:26 AM
To: Deval, Manasi <[email-masked]>
Cc: Marten Seemann <[email-masked]>; Kazuho Oku <[email-masked]>; Eric Rescorla <[email-masked]>; Jana Iyengar <[email-masked]>; Praveen Balasubramanian <[email-masked]>; IETF QUIC WG <[email-masked]>; Martin Thomson <[email-masked]>
Subject: Re: Proposal to replace ACK block count with ACK length

On Tue, Jun 19, 2018 at 2:21 PM Deval, Manasi <[email-masked]<mailto:[email-masked]>> wrote:
Hi All,

Thanks,
Manasi

From: Deval, Manasi
Sent: Sunday, June 17, 2018 2:25 PM
To: Marten Seemann <[email-masked]<mailto:[email-masked]>>; Kazuho Oku <[email-masked]<mailto:[email-masked]>>
Cc: Ian Swett <ianswett=[email-masked]<mailto:[email-masked]>>; Eric Rescorla <[email-masked]<mailto:[email-masked]>>; Jana Iyengar <[email-masked]<mailto:[email-masked]>>; Praveen Balasubramanian <[email-masked]<mailto:[email-masked]>>; IETF QUIC WG <[email-masked]<mailto:[email-masked]>>; Martin Thomson <[email-masked]<mailto:[email-masked]>>
Subject: RE: Proposal to replace ACK block count with ACK length

Hi All,

Thanks,

Manasi

--
Kazuho Oku

---

From: Marten Seemann <[email-masked]>
Date: Wed, 20 Jun 2018 08:43:49 +0700

Hi Manasi,

> The risk of disagreement between ack blocks and ack block count is same
as the risk of disagreement between ack blocks and ack length. Either way
this needs to be counted up while creating the ACK and counted down while
parsing it. The possibility of error is the same. Getting the ack block
count wrong is as problematic as getting the ack length wrong. Do you agree?

I disagree. Let's take an example of an ACK frame with one ACK range, that
needs a 2 byte varint to represent the First ACK Block and another 2 byte
varint to represent the Gap.
With your proposal:

   1. The values 0 and 1 are invalid, since the length fields itself is
   included in the length.
   2. The values 2, 3, ..., (2 + len(LargestAcknowledged) + len(AckDelay))
   - 1 are invalid, since the length needs to include the Largest Acknowledged
   and the Ack Delay.
   3. The value 2 + len(LargestAcknowledged) + len(AckDelay) would be the
   first valid value, and correspond to an ACK frame with no blocks.
   4. The value 2 + len(LargestAcknowledged) + len(AckDelay) + 1 is
   invalid, since it would cut the varint for the First ACK Block
   5. The value 2 + len(LargestAcknowledged) + len(AckDelay) + 2 is
   invalid, since it would cut the frame after the First ACK Block (but every
   block must be followed by a gap length)
   6. The value 2 + len(LargestAcknowledged) + len(AckDelay) + 3 is
   invalid, since it would cut the varint for the Gap
   7. Finally, the value 2 + len(LargestAcknowledged) + len(AckDelay) +
   4 is valid

There are *a lot* of invalid values that you can encode into the ACK length
field. More importantly, *none* of these error cases exists with the
current frame format.
The *only* error case that can occur with our current format is that the
packet is too short for the number of ACK blocks that are supposed to
contained in the frame. This can occur with your proposal as well (in
addition to the error cases listed above).

My concern is not that it's impossible or even particularly hard to catch
these errors, but I dislike the property that some (in fact, most)
encodable values are invalid.

Best,
Marten

On Wed, Jun 20, 2018 at 3:21 AM Deval, Manasi <[email-masked]>
wrote:

> >If we don't remove the number of ack blocks, then the ack frame is
> larger, but I don't think the extra size field is useful for most
> implementations.  Also, it means the length can disagree with the actual
> length, which add complexity and the possibility of writing error-prone
> code.  The idea of someone offloading ack processing and then proceeding to
> trust the length seems like someone could get wrong and cause some
> concerning issues.
>
> The risk of disagreement between ack blocks and ack block count is same as
> the risk of disagreement between ack blocks and ack length. Either way this
> needs to be counted up while creating the ACK and counted down while
> parsing it. The possibility of error is the same. Getting the ack block
> count wrong is as problematic as getting the ack length wrong. Do you agree?
>
>
>
> >My experience is multithreaded packet processing is more cost and work
> than it's worth.  Sure you can't fill a 100G NIC with one connection, but
> that seems like an academic problem, not one for workloads I've seen.
> Typically the extra cost of multithreading outweighs its value.
>
> The value is two fold – pre-processing and multi-threading. If we
> pre-process the received packets such that ACKs and streams can be
> coalesced, the receive side can indicate a large chunk of information
> though the kernel, reducing the cost of system call and protocol
> overhead. This is the same concept as UDP segmentation taken a step further
> on receive side. After this chunk is indicated into the QUIC protocol, the
> protocol may process stream and ACK in parallel. While folks may or may not
> utilize this, there is an advantage here.
>
>
>
> Thanks,
>
> Manasi
>
>
>
>
>
> *From:* Ian Swett [mailto:[email-masked]]
> *Sent:* Tuesday, June 19, 2018 11:26 AM
> *Cc:* Marten Seemann <[email-masked]>; Kazuho Oku <
> [email-masked]>; Eric Rescorla <[email-masked]>; Jana Iyengar <
> [email-masked]>; Praveen Balasubramanian <[email-masked]>; IETF
> QUIC WG <[email-masked]>; Martin Thomson <[email-masked]>
>
>

---

From: Ian Swett <[email-masked]>
Date: Thu, 21 Jun 2018 16:27:00 -0400

I agree the ack blocks should be at the end of the ACK_ECN frame, and I
asked Magnus to move them there(and he has kindly done so in his PR).  This
will make it substantially easier to truncate ACK blocks when necessary.

But like Marten, I think this would make most implementations, including
mine, more complex.

On Tue, Jun 19, 2018 at 9:44 PM Marten Seemann <[email-masked]>
wrote:

>    2. The values 2, 3, ..., (2 + len(LargestAcknowledged)
>    + len(AckDelay)) - 1 are invalid, since the length needs to include the
>    Largest Acknowledged and the Ack Delay.
> There are *a lot* of invalid values that you can encode into the ACK
> length field. More importantly, *none* of these error cases exists with the
> current frame format.
>> >I'm not a fan of this proposal, because I think it is impractical to
>> drop the number of ack blocks, because with the ECN proposal it becomes
>> [email-masked]>; Jana Iyengar <[email-masked]>; Praveen
>> Balasubramanian <[email-masked]>; IETF QUIC WG <[email-masked]>;
>> Martin Thomson <[email-masked]>
>> Christian suggested to move the ECN fields to precede the ACK blocks.
>> This is an elegant solution. Parsing entire list of ACK blocks to review
>> ECN bits would have been annoying, even though it can work.
>>
>>
>>
>> Agreement from several folks here. In the original ACK defined in draft
>> 12 of the slide, one would count down number of ACK blocks to get to the
>> end of the packet. In the proposal I made, one would count down the length
>> to identify the end of the packet. The logic is very similar in cycle count
>> [email-masked]>; Jana Iyengar <[email-masked]>; Praveen
>> Balasubramanian <[email-masked]>; IETF QUIC WG <[email-masked]>;
>> Martin Thomson <[email-masked]>; Deval, Manasi <
>> [email-masked]>
>> >> > larger,
>> >> > than
>> >> > To be clear, I don't think this is an awful idea, but I also don't
>> see
>> >> > the
>> >> >>>> > I don't have a strong opinion on this. I'm certainly not
>> opposed to
>> >> >>>> > it.
>> >> >>>> >> overhead. ACKs are going to be the second most common frame
>> type
>> >> >>>> >> so no
>> >> >>>> >> over any header, I have to read every single varint. As the
>> code
>> >> >>>> >> sees Stream
>> >> >>>> >> block section is merely repeating this operation
>> (2*num_block+1)
>> >> >>>> >> times. Do
>> >> >>>> >> >          first 16 bits and skipping over the length. This is
>> a
>> >> >>>> >> > useful
>> >> >>>> >> Just a note.  In my experience, the cost of parsing an ACK
>> frame
>> >> >>>> >> is
>> >> >>>> >> negligible compared to the cost of processing an ACK frame:
>> that
>> >> >>>> >> is,

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Thu, 21 Jun 2018 17:14:49 -0400

Missed that mail.

My concern was mostly that you when several people raises concerns about a
protocol design principle being changed, you need to argue why such a
change is viable rather than just - need to check EOB anyway.

You code goes some way to address that. I didn’t go through it in detail
(I’m beyond my code line limit for today) but there could can be problems
such as:

ACK frame with length prefix says it does not exceed end of buffer. Parser
reads all data and confirms this fact, so frame is accepted. What it might
miss is that the length points after the end of the parse block leaving
undetermined data hanging. Not saying this actually happens, but that is a
concern.

Personally, I actually like a length prefix, and generally don’t see a
problem with it. But I’d prefer if it was a global principle then rather
than mixing those concepts. When this is done in a generic fashion, and end
pointer can be passed everywhere, and as soon as something does fit
cleanly, abort the connection.

The MQTT packet framing uses a length prefix uniformly:

http://www.steves-internet-guide.com/mqtt-protocol-messages-overview/

Mikkel

On 19 June 2018 at 21.12.13, Eric Rescorla ([email-masked]) wrote:

---

From: "Deval, Manasi" <[email-masked]>
Date: Thu, 21 Jun 2018 23:08:51 +0000

I feel that the requirement to have every value valid is somewhat academic. The length value provides much more value than the block count and the fact that certain values can never be achieved is an inherent property of the length.

One interesting observation is that this property is not limited to length. One can even make a similar argument about ACK block count. The maximum number of ACK blocks that can be defined will not always have a meaningful value. In out examples, 0,1,2,3 are all valid. If I set the value of ACK block count to have lower two bits to be 11, the maximum value is of ACK blocks is – 4611686018427387903. This is the same value of largest acknowledged so if the ACK block count was set to this value, it would still be meaningless.

Thanks,
Manasi

From: Marten Seemann [mailto:[email-masked]]
Sent: Tuesday, June 19, 2018 6:44 PM
To: Deval, Manasi <[email-masked]>
Cc: Ian Swett <[email-masked]>; Kazuho Oku <[email-masked]>; Eric Rescorla <[email-masked]>; Jana Iyengar <[email-masked]>; Praveen Balasubramanian <[email-masked]>; IETF QUIC WG <[email-masked]>; Martin Thomson <[email-masked]>
Subject: Re: Proposal to replace ACK block count with ACK length

Hi Manasi,

> The risk of disagreement between ack blocks and ack block count is same as the risk of disagreement between ack blocks and ack length. Either way this needs to be counted up while creating the ACK…

I disagree. Let's take an example of an ACK frame with one ACK range, that needs a 2 byte varint to represent the First ACK Block and another 2 byte varint to represent the Gap.
With your proposal:

  1.  The values 0 and 1 are invalid, since the length fields itself is included in the length.
  2.  The values 2, 3, ..., (2 + len(LargestAcknowledged) + len(AckDelay)) - 1 are invalid, since the length needs to include the Largest Acknowledged and the Ack Delay.
  3.  The value 2 + len(LargestAcknowledged) + len(AckDelay) would be the first valid value, and correspond to an ACK frame with no blocks.
  4.  The value 2 + len(LargestAcknowledged) + len(AckDelay) + 1 is invalid, since it would cut the varint for the First ACK Block
  5.  The value 2 + len(LargestAcknowledged) + len(AckDelay) + 2 is invalid, since it would cut the frame after the First ACK Block (but every block must be followed by a gap length)
  6.  The value 2 + len(LargestAcknowledged) + len(AckDelay) + 3 is invalid, since it would cut the varint for the Gap
  7.  Finally, the value 2 + len(LargestAcknowledged) + len(AckDelay) + 4 is valid
There are *a lot* of invalid values that you can encode into the ACK length field. More importantly, *none* of these error cases exists with the current frame format.
The *only* error case that can occur with our current format is that the packet is too short for the number of ACK blocks that are supposed to contained in the frame. This can occur with your proposal as well (in addition to the error cases listed above).

My concern is not that it's impossible or even particularly hard to catch these errors, but I dislike the property that some (in fact, most) encodable values are invalid.

Best,
Marten

On Wed, Jun 20, 2018 at 3:21 AM Deval, Manasi <[email-masked]<mailto:[email-masked]>> wrote:
Hi Ian,

Thanks,
Manasi

From: Ian Swett [mailto:[email-masked]<mailto:[email-masked]>]
Sent: Tuesday, June 19, 2018 11:26 AM
To: Deval, Manasi <[email-masked]<mailto:[email-masked]>>
Cc: Marten Seemann <[email-masked]<mailto:[email-masked]>>; Kazuho Oku <[email-masked]<mailto:[email-masked]>>; Eric Rescorla <[email-masked]<mailto:[email-masked]>>; Jana Iyengar <[email-masked]<mailto:[email-masked]>>; Praveen Balasubramanian <[email-masked]<mailto:[email-masked]>>; IETF QUIC WG <[email-masked]<mailto:[email-masked]>>; Martin Thomson <[email-masked]<mailto:[email-masked]>>

Thanks,
Manasi

From: Deval, Manasi

Hi All,

Thanks,

Manasi

>> > drop

--
Kazuho Oku

---

From: Ian Swett <[email-masked]>
Date: Thu, 21 Jun 2018 21:48:04 -0400

On Thu, Jun 21, 2018 at 7:08 PM Deval, Manasi <[email-masked]>
wrote:

> I feel that the requirement to have every value valid is somewhat
> academic. The length value provides much more value than the block count
>

This is a key point we disagree on.  I see no value in a length field.  I
believe it having value is predicated on the idea that multi-core QUIC
packet processing is a good idea?  I fear efforts to multithread processing
of a single QUIC packet are not only a waste of time, but also a potential
source of correctness issues.

In my experience, the CPU cost of sending is much higher than receiving, so
I have a really difficult time imagining multi-core receive being
worthwhile.

and the fact that certain values can never be achieved is an inherent
> property of the length.
>
>
>
> One interesting observation is that this property is not limited to
> length. One can even make a similar argument about ACK block count. The
> maximum number of ACK blocks that can be defined will not always have a
> meaningful value. In out examples, 0,1,2,3 are all valid. If I set the
> value of ACK block count to have lower two bits to be 11, the maximum value
> is of ACK blocks is – 4611686018427387903. This is the same value of
> largest acknowledged so if the ACK block count was set to this value, it
> would still be meaningless.
>
>
>
> Thanks,
>
> Manasi
>
>
>
>
>
>
>
> *From:* Marten Seemann [mailto:[email-masked]]
> *Sent:* Tuesday, June 19, 2018 6:44 PM
> *Cc:* Ian Swett <[email-masked]>; Kazuho Oku <[email-masked]>;
> Eric Rescorla <[email-masked]>; Jana Iyengar <[email-masked]>; Praveen

---

From: Nick Banks <[email-masked]>
Date: Fri, 22 Jun 2018 02:20:19 +0000

I agree that changing this for the sake of multi-threaded usage isn’t worth it, but I do think the change has merit for the goal of improving the efficiency of parsing through all the frames quickly. The hardware can use this to help find the correct frames in packets to coalesce together. The code shouldn’t have to pay the penalty of walking every ack block if it’s not interested in the information there.

Sent from my Windows 10 phone
[HxS - 15254 - 16.0.10228.20075]

________________________________
From: QUIC <[email-masked]> on behalf of Ian Swett <ianswett=[email-masked]>
Sent: Thursday, June 21, 2018 6:48:04 PM
To: Deval, Manasi
Cc: Eric Rescorla; Jana Iyengar; Praveen Balasubramanian; Marten Seemann; IETF QUIC WG; Martin Thomson; Kazuho Oku
Subject: Re: Proposal to replace ACK block count with ACK length

On Thu, Jun 21, 2018 at 7:08 PM Deval, Manasi <[email-masked]<mailto:[email-masked]>> wrote:
I feel that the requirement to have every value valid is somewhat academic. The length value provides much more value than the block count

This is a key point we disagree on.  I see no value in a length field.  I believe it having value is predicated on the idea that multi-core QUIC packet processing is a good idea?  I fear efforts to multithread processing of a single QUIC packet are not only a waste of time, but also a potential source of correctness issues.

In my experience, the CPU cost of sending is much higher than receiving, so I have a really difficult time imagining multi-core receive being worthwhile.

and the fact that certain values can never be achieved is an inherent property of the length.

Thanks,
Manasi

From: Marten Seemann [mailto:[email-masked]<mailto:[email-masked]>]
Sent: Tuesday, June 19, 2018 6:44 PM
To: Deval, Manasi <[email-masked]<mailto:[email-masked]>>
Cc: Ian Swett <[email-masked]<mailto:[email-masked]>>; Kazuho Oku <[email-masked]<mailto:[email-masked]>>; Eric Rescorla <[email-masked]<mailto:[email-masked]>>; Jana Iyengar <[email-masked]<mailto:[email-masked]>>; Praveen Balasubramanian <[email-masked]<mailto:[email-masked]>>; IETF QUIC WG <[email-masked]<mailto:[email-masked]>>; Martin Thomson <[email-masked]<mailto:[email-masked]>>
Subject: Re: Proposal to replace ACK block count with ACK length

Hi Manasi,

Best,
Marten

Thanks,
Manasi

Thanks,
Manasi

From: Deval, Manasi

Hi All,

Thanks,

Manasi

>> >>>> >> <[email-masked]<mailto:manasi.deval@intel..com>> wrote:
>> >>>> >>

--
Kazuho Oku

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 22 Jun 2018 12:45:17 +0900

2018-06-22 8:08 GMT+09:00 Deval, Manasi <[email-masked]>:
> I feel that the requirement to have every value valid is somewhat academic.

I think that Marten is correct in pointing out that making the ACK
frame self-containing (by having a field that represents the number of
octets being consumed by the frame) would be an exception from the
design pattern we have.

Look at STREAM frame. The field is not self-contained. Instead, it has
a Length field for the Stream Data, which is a leaf. The same goes for
NEW_CONNECTION_ID frame (that has the length field for Connection ID
field (which is also a leaf)), CONNECTION_CLOSE (length field for
Reason Phase).

I agree with Marten, Mikkel (and possibly others as well) that having
consistency is important.

Therefore, I agree with Mikkel that we should consider making every
frame self-contained or keeping every frame as-is (i.e. not
self-contained).

FWIW, as described in the latter half of
https://www.ietf.org/mail-archive/web/quic/current/msg04287.html, it
is possible to make every frame self-contained *and* also make ACK
frames smaller than the current draft. Making every frame
self-contained gives us the possibility to send new extension frames
without negotiation.

I do not think that I would push for making every frame self-contained
by myself (because I do not think it meets the high bar to have a
change at such a late moment of standardization), but as stated, my
preference goes to seeing every frame made self-contained or none of
them made as such.

> The length value provides much more value than the block count and the fact
> that certain values can never be achieved is an inherent property of the
> length.
>
>
>
> One interesting observation is that this property is not limited to length.
> One can even make a similar argument about ACK block count. The maximum
> number of ACK blocks that can be defined will not always have a meaningful
> value. In out examples, 0,1,2,3 are all valid. If I set the value of ACK
> block count to have lower two bits to be 11, the maximum value is of ACK
> blocks is – 4611686018427387903. This is the same value of largest
> acknowledged so if the ACK block count was set to this value, it would still
> be meaningless.
>
>
>
> Thanks,
>
> Manasi
>
>
>
>
>
>
>
> Cc: Ian Swett <[email-masked]>; Kazuho Oku <[email-masked]>; Eric
> Rescorla <[email-masked]>; Jana Iyengar <[email-masked]>; Praveen
> Balasubramanian <[email-masked]>; IETF QUIC WG <[email-masked]>; Martin
> Thomson <[email-masked]>
>
>
>> needs to be counted up while creating the ACK and counted down while parsing
>> it. The possibility of error is the same. Getting the ack block count wrong
>> is as problematic as getting the ack length wrong. Do you agree?
>
>
>
> The values 0 and 1 are invalid, since the length fields itself is included
> in the length.
> The values 2, 3, ..., (2 + len(LargestAcknowledged) + len(AckDelay)) - 1 are
> invalid, since the length needs to include the Largest Acknowledged and the
> Ack Delay.
> The value 2 + len(LargestAcknowledged) + len(AckDelay) would be the first
> valid value, and correspond to an ACK frame with no blocks.
> The value 2 + len(LargestAcknowledged) + len(AckDelay) + 1 is invalid, since
> it would cut the varint for the First ACK Block
> The value 2 + len(LargestAcknowledged) + len(AckDelay) + 2 is invalid, since
> it would cut the frame after the First ACK Block (but every block must be
> followed by a gap length)
> The value 2 + len(LargestAcknowledged) + len(AckDelay) + 3 is invalid, since
> it would cut the varint for the Gap
> Finally, the value 2 + len(LargestAcknowledged) + len(AckDelay) + 4 is valid
>
> field. More importantly, *none* of these error cases exists with the current
> frame format.
>
> these errors, but I dislike the property that some (in fact, most) encodable
> values are invalid.
>
>
>
> Best,
>
> Marten
>
>
>
>
>
> needs to be counted up while creating the ACK and counted down while parsing
> it. The possibility of error is the same. Getting the ack block count wrong
> is as problematic as getting the ack length wrong. Do you agree?
>
>
>
> coalesced, the receive side can indicate a large chunk of information though
> the kernel, reducing the cost of system call and protocol overhead. This is
> the same concept as UDP segmentation taken a step further on receive side.
> After this chunk is indicated into the QUIC protocol, the protocol may
> process stream and ACK in parallel. While folks may or may not utilize this,
> there is an advantage here.
>
>
>
> Thanks,
>
> Manasi
>
>
>
>
>
> Cc: Marten Seemann <[email-masked]>; Kazuho Oku
> <[email-masked]>; Eric Rescorla <[email-masked]>; Jana Iyengar
> <[email-masked]>; Praveen Balasubramanian <[email-masked]>; IETF
> Cc: Ian Swett <ianswett=[email-masked]>; Eric Rescorla
> <[email-masked]>; Jana Iyengar <[email-masked]>; Praveen Balasubramanian
> <[email-masked]>; IETF QUIC WG <[email-masked]>; Martin Thomson
> is an elegant solution. Parsing entire list of ACK blocks to review ECN bits
> would have been annoying, even though it can work.
>
>
>
> of the slide, one would count down number of ACK blocks to get to the end of
> the packet. In the proposal I made, one would count down the length to
> identify the end of the packet. The logic is very similar in cycle count and
> complexity. Several folks also commented to this effect.
>
>
>
> I would expect that there are 10s of 1000s of connections in use at any time
> for a server with a high speed link. Multi-threading to handle each of these
> flows / connections in parallel is necessity to be able to support large
> number of connections on a high speed link. Tx segmentation, Rx coalescing
> are well known strategies to reduce the processing cost. In initial stages,
> code is often written as a single-threaded and then re-factored to
> parallelize cycle intensive operations. In order to allow this protocol to
> scale in future, I would suggest we do not preclude this case.
>
>
>
> I do not see this as a serious issue but if folks but we can consider making
> this a varint, if others have strong feelings about it. It’s a trade-off : 2
> reads to save 1 byte.
>
>
>
> Not every length will be valid. This is inherent to lengths. This same issue
> ails the ‘payload length’ in QUIC header. Not only does the issue exist for
> small values, it also applies to large values since data stream will be sent
> after crypto negotiation.  E.g.  - how does one craft a payload with 62 bit
> payload length in a large header?
>
>
>
>
>
> Thanks,
>
> Manasi
>
>
>
>
>
> Cc: Ian Swett <ianswett=[email-masked]>; Eric Rescorla
> <[email-masked]>; Jana Iyengar <[email-masked]>; Praveen Balasubramanian
> <[email-masked]>; IETF QUIC WG <[email-masked]>; Martin Thomson
> <[email-masked]>; Deval, Manasi <[email-masked]>
> away from the principle that only reasonable values should be encodable, and
> that it increases the size of the ACK frame, for the questionable benefit of
> being able to parallelise the frame parser.
>
>
>

-- 
Kazuho Oku

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 22 Jun 2018 06:11:05 -0700

It seems like there are two questions at hand here:

1. Would it be architecturally better to have frames have a consistent
self-contained
representation?
2. Is it enough better that we should do so now.

I agree with Kazuho that (a) we don't have that representation now and (b)
it would
be a better design to do so. I'm perhaps somewhat more positive on (2) than
he
is. I don't think it's critically important that we make the change, but if
we were
to hold a consensus call, I think I would be in favor. I'd certainly be
interested
in looking at a proposal if someone else were to make one.

-Ekr

On Thu, Jun 21, 2018 at 8:45 PM, Kazuho Oku <[email-masked]> wrote:

> academic.
> as
> length
> current
> as
> though
> This
> bits
> 12
> and
> time
> making
> issue
> and

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Fri, 22 Jun 2018 11:00:52 -0400

As I said earlier, I also favour a length prefix. But, Ian does have a
point:

Writing data is generally more expensive than reading data. Especially if
you have to traverse long data structures to find the length before you can
start writing and/or you may have to conservatively reserve extra space for
a length field.

So before deciding one way or the other, the cost of writing needs to be
well understood, also in scenarios with large MTU’s.

In the flatbuffers space that I’m involved with, streaming has turned to be
an issue because data cannot be transmitted in parts without index data on
a separate channel to recombined fragments. A simple, but non-standard,
change in the format would fix this. JSON and CoAP allows streaming, but
many other formats do not, including later versions of protocol buffers, as
I understand.

An odd consequence of making both read and write efficient is that length
better work better if stored at the end and packets read backwards. This
requires a single total length prefix but this is stored in the datagram
header. This is probably too odd-ball, but still a consideration worth
noting.

The second best alternative may therefore be to allow writes to be fast and
reads to be decent.

Yet, I still like length prefixes if they could be made write efficient
because high performance low-latency processes care zero about ACK and can
consume a packet directly while a background process handles all the
latency insensitive ACK and retransmission logic.

The question is also, where is the pressure: an IoT aggregator might be
massively read intensive while a web cache would be very write intensive.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 22 June 2018 at 15.12.09, Eric Rescorla ([email-masked]) wrote:

-Ekr

On Thu, Jun 21, 2018 at 8:45 PM, Kazuho Oku <[email-masked]> wrote:

> > To: Deval, Manasi <[email-masked] <[email-masked]>>
> > To: Deval, Manasi <[email-masked] <[email-masked]>>
> > Cc: Ian Swett <ianswett=[email-masked]
> <[email-masked]..org>>; Eric Rescorla
> > Cc: Ian Swett <ianswett=[email-masked]
> <[email-masked]..org>>; Eric Rescorla
> >> Both these cases can't occur with the current ACK frame format..
> >>

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Fri, 22 Jun 2018 12:15:01 -0400

Another option is to write out frames as is without length except as needed
for varints. When a packet is nearly done, a run-length encoded frame index
is placed in the packet tail. It could also include the frame types. A
reader can now directly find or skip ACK frames and the writer does not
have to compute lengths before writing. Of course, the reader needs to be
able to locate the index at the tail which can be tricky with coalesced
packets, but not impossible. Isn’t this largely how zip-files work?

Mikkel

On 22 June 2018 at 17.00.52, Mikkel Fahnøe Jørgensen ([email-masked])
wrote:

Kind Regards,
Mikkel Fahnøe Jørgensen

-Ekr