RE: Proposal to replace ACK block count with ACK length

["Deval, Manasi" <[e-mail]>]

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 <[e-mail]>; Kazuho Oku <[e-mail]>
Cc: Ian Swett <ianswett=[e-mail]>; Eric Rescorla <[e-mail]>; Jana Iyengar <[e-mail]>; Praveen Balasubramanian <[e-mail]>; IETF QUIC WG <[e-mail]>; Martin Thomson <[e-mail]>
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.


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:[e-mail]]
Sent: Sunday, June 17, 2018 6:59 AM
To: Kazuho Oku <[e-mail]<mailto:[e-mail]>>
Cc: Ian Swett <ianswett=[e-mail]<mailto:ianswett=[e-mail]>>; Eric Rescorla <[e-mail]<mailto:[e-mail]>>; Jana Iyengar <[e-mail]<mailto:[e-mail]>>; Praveen Balasubramanian <[e-mail]<mailto:[e-mail]>>; IETF QUIC WG <[e-mail]<mailto:[e-mail]>>; Martin Thomson <[e-mail]<mailto:[e-mail]>>; Deval, Manasi <[e-mail]<mailto:[e-mail]>>
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 <[e-mail]<mailto:[e-mail]>> wrote:
2018-06-17 22:36 GMT+09:00 Marten Seemann <[e-mail]<mailto:[e-mail]>>:
> 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).

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.

>
> 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 <[e-mail]<mailto:[e-mail]>> wrote:
>>
>> 2018-06-17 8:34 GMT+09:00 Ian Swett
>> <ianswett=[e-mail]<mailto:[e-mail]>>:
>> > 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.
>>
>> 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).
>>
>> > 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 <[e-mail]<mailto:[e-mail]>> wrote:
>> >>
>> >> On Fri, Jun 15, 2018 at 6:46 PM, Marten Seemann
>> >> <[e-mail]<mailto:[e-mail]>>
>> >> wrote:
>> >>>
>> >>> 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.
>> >>
>> >>
>> >> 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
>> >>
>> >>
>> >>>
>> >>> On Sat, Jun 16, 2018 at 6:19 AM Martin Thomson
>> >>> <[e-mail]<mailto:[e-mail]>>
>> >>> wrote:
>> >>>>
>> >>>> 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 <[e-mail]<mailto:[e-mail]>>
>> >>>> wrote:
>> >>>> >
>> >>>> > 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
>> >>>> > <[e-mail]<mailto:[e-mail]>> 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:[e-mail]<mailto:[e-mail]>] On Behalf Of Eric
>> >>>> >> Rescorla
>> >>>> >> Sent: Friday, June 15, 2018 9:11 AM
>> >>>> >> To: Deval, Manasi <[e-mail]<mailto:[e-mail]>>
>> >>>> >> Cc: Jana Iyengar <[e-mail]<mailto:[e-mail]>>; QUIC WG <[e-mail]<mailto:[e-mail]>>
>> >>>> >> 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
>> >>>> >> <[e-mail]<mailto:[e-mail]>> 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:[e-mail]<mailto:[e-mail]>] On Behalf Of Jana
>> >>>> >> Iyengar
>> >>>> >> Sent: Monday, June 11, 2018 3:11 PM
>> >>>> >> To: Deval, Manasi <[e-mail]<mailto:[e-mail]>>; QUIC WG
>> >>>> >> <[e-mail]<mailto:[e-mail]>>
>> >>>> >> 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
>> >>>> >> <dtikhonov@litespeedtech..com<mailto:dtikhonov@litespeedtech..com>> wrote:
>> >>>> >>
>> >>>> >> 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.
>> >>>> >>
>> >>>> >>
>> >>>>
>> >>
>> >
>>
>>
>>
>> --
>> Kazuho Oku



--
Kazuho Oku