Multiple ACK frames

[ianswett]

Currently the QUIC spec does not discuss sending multiple ack frames in one packet, and the way it's structured implies largest acked must always increase. There are plans to use a new initial packet number and a new connection ID when migrating, making multiple ack frames valuable, if not strictly necessary, since otherwise you won't be able to continue acking pre-migration packets.

Additionally, this could allow the ack frame to be simpler by making all ack block lengths 1 byte long, instead of the current 1/2/4/6.

[martinthomson]

@ianswett, I like the idea that this could be made simpler. I had thought of sending multiple frames, but not the fact that it could be a way to make ACK frames smaller and less complicated.

[mikkelfj]

What about the case where you have a long fat pipe and more acks to send than fits within an ack frame, or even a single MTU? Do you always only send the earliest acks? And when do you decide to no longer send these and progress with larger acks. You might not receive ack acks because both ends stick to old ranges. The now defunct STOP_WAITING set a clear lower bound that appear to be less obvious now.

[mikkelfj]

Related: If we ignore timestamp section of ack frames, the ACK Delay field requires a timestamp stored for every packet, or at least makes it difficult to handle without it. This is because we might not be able to sent up to largest received packet. I propose allowing the ACK Delay field to be 1) absent, or 2) set to zero, or 3) or set to 0xffff when delay information is not readily available. The value of ACK Delay in this case is limited anyway. It could be required that ACK frames SHOULD provide ack delay when the largest acked is also the largest received.

As to the ignored timestamp section, this section can selectively drop some timestamps and only delilver a representative subset. Further, it will be drained quickly while Ack frames must repeat over packet ranges and retain more information. Therefore the timestamp section is not a good source of information for ACK Delay.

[ianswett]

I agree that if we want to be able to ack an entire flight(ie: up to 2^32) packets, we can't move to a single byte format. Which makes me question the idea of simplifying the ack frame to only have 1 byte ranges.

STOP_WAITING doesn't help us in that case, because we wouldn't expect to receive a STOP_WAITING for a packet until at least an RTT later, and I believe the concern is having more packets in flight than fit into an ack frame?

Re: "This is because we might not be able to send up to the largest received packet"(in the ack). The ack delay is always relative to the time the largest acked was received, so only one timestamp per ack frame is necessary. Second, it's intended newer packets are always acked instead of continuing to ack older packets which have already been sent in many acks. GQUIC used to stop acking new packets when it wasn't sure if acks had been received, and it caused many more problems than it solved, which makes sense given packets are typically acked many times before they can no longer be acked. I can create a PR to clarify that.

[ianswett]

I accidentally hit the immediate submit button instead of creating a reviewable PR. I added the sentence "When this is necessary, the receiver SHOULD acknowledge newly received packets and stop acknowledging packets received in the past."

If you have any other suggestions, tell me or send me a PR.

[mikkelfj]

I don't have the full overview, but I am concerned that there can be so many packets in flight that you would have to send acks very frequently if you always must include the largest received. Allowing acks to be sent in multiple frames - likely in multiple packets - would deal with this problem except that early retransmission would kick in prematurely if not handled carefully, and except for the ack delay issue mentioned. So if it works sending the latest, then fine, I'm just having an uneasy feeling about it. Sending just the oldest could risk lockup so that is not the answer either.

10Gbit/s link, 10Kbits/MTU, 100ms rtt: 10^10/10^4*0.1 = 10^5 packets in flight.

From what I could read of studies around, packet reordering tend to concentrate on latest transmitted burst, but up 30% of packets can easily be reordered even if not very much out of order. This means that frequent sending ACK's might miss some reordered packets, forcing these to be retransmitted even though they arrive shortly after. Due to reordering in WAN that ACK frame would fill up quickly despite large addressing space. Sending ACKS less frequent would reduce the gaps as reordered packets arrive, but increase the risk of having to never ack some packets.

I'm not sure how GQUIC is being tested, but moving large volumes of data, e.g. syncing CDN caches over backbones could stress the system differently from HTTP/2 browsing.

It is really hard to be sure without real-life testing or at least simulation. My intuition just tells this could be a problem.

[mikkelfj]

If the stance is that STOP_WAITING is too late to be efficient, which sounds reasonable, what is the point of claiming that sender SHOULD not send alredy acked ack frames? Unless both endpoints transmit other data aggressively, the ackacks could be many RTTs in distance, and otherwise they would be spaced about one RTT. Resending already acked acks can reduce gaps (but also grow the length field size), except those at the tail.

Tracking those ackacks is significant extra book keeping except for tail truncation and given the number of packets potentially in flight, I suggest removing tracking of ack acks and use a lower bound which could either be STOP_WAITING, or a much smaller ackack concept that only tracks the least unacknowledged (i.e. last gap) in each transmitted ack frame. This could be worded something like: SHOULD not sent acknowledgements of packets earlier than the least unacknowledged packet of any ack frame that has received an ack. Acknowledgments of other packets in acknowledged ACK frames MAY be retransmitted, especially when this can reduce gaps. (This does not consider additional ack frames not starting at largest received - semantics would then be unclear).

On clarity of ack frame: it is not immediately obvious that ack frame blocks are stored in decreasing order, although with careful reading it can be deduced, especially when it is clear that largest_acknowledged is always the largest received.

[ianswett]

If multiple frames are used, some advice on loss recovery between them is definitely helpful as well to avoid spurious retransmits, though as long as packet number is always increasing, you wouldn't expect a lot of larger packet numbers being acked before smaller ones.

Packet reordering is fairly common, though as you point out most reordering is relatively small scale. Currently QUIC's acking policy is designed to mimic TCP's, though that could change if we wanted better performance with reordering. When to send acks is orthogonal to how the sender should conduct loss detection when it receives those acks.

The current wording about tracking ackacks is intended to be flexible, because I think there are a few approaches which may work well and we haven't been able to experiment with them enough to know what is best. Tracking the least unacknowledged and only removing blocks below that could end up taking a very long time to stop acking older packets, since I think it would only drop one range per RTT? Currently GQUIC is tracking the largest acked and removing ack blocks less than that when an ack is acked, which allows for 1RTT of reordering but could probably be improved in cases with really heavy reordering.

[mikkelfj]

Tracking the least unacknowledged and only removing blocks below that could end up taking a very long time to stop acking older packets, since I think it would only drop one range per RTT?

I agree, but my intention was to soften the current wording in the draft quoted below, not to extend the time an ack must be transmitted, but rather extend the time and ack is permitted to be transmitted, which is different:

Once an ACK frame has been acknowledged, the packets it acknowledges SHOULD not be acknowledged again.

Respecting the above appears to provide little benefit. But even if packets are no longer actively being acknowledged when an ack from is acknowledge by peer (ack ack), an implementation is obliged to assume that a super fast ack ack might occur and therefore has to track the content of transmitted ack frames, which seems unnecessary. My proposal was to reduce this bookkeeping be just storing a lower bound in ack frame restransmission buffer, rather than the full content. Or possibly remove the sentence and allow ack frames to be forgotten once sent.

On loss/reordering - I just read about 5G mobile networks - these are designed to peak at 32Gbits/s - that could create some interesting use cases.

[martinthomson]

This is all very interesting, but I'm wondering about something. How often do you ACK a contiguous range of packets that is >256 packets long? Do you ever ACK a range that is >65536 packets long?

32Gbps doesn't bother me that much: as long as you have enough spare capacity for lots of ACK frames - which can only really happen on a grossly asymmetric link - you can treat ACKs as you do DATA. Send and retransmit them in the same way, including all of the standard repair strategies (inc. FRTO). Yes it means tracking what was acknowledged and when, but you have a few orders of magnitude less state to maintain.

[mikkelfj]

You can't treat ack frames as data because data can be buffered externally such as via a memory mapped file - stream frames only need to store the header in a retransmission buffer. Ideally ack frames need not be stored at all, or they could store just a few range limits. Detailed ack frame storage is a complication.

[ianswett]

I believe #595 is a sufficiently good fix for now.

[ianswett]

PR #877