Subject: Congestion control algorithm questions

From: Martin Thomson <[email-masked]>
Date: Thu, 24 Aug 2017 15:52:12 +1000

I've barely usable Internet access today, so I've had a lot of time to
contemplate congestion control.

I read through the congestion and loss recovery document and have a
few questions and observations.  These are in email form because I'm
not an expert on this stuff and it could be my poor understanding.

Firstly, the heavy reliance on pseudocode here is to the detriment of
clarity.  There are numerous examples of this, but here are two I
found to be unnecessarily obtuse:

1. I realize that some people have internalized the fact that
(end_of_recovery < largest_lost_packet.packet_number) and
(acked_packet.packet_number < end_of_recovery) mean that the
connection is out of recovery and in recovery respectively, but this
is not very clear.  I think that clarity would be improved
immeasurably by an IsInRecovery() function.  Maybe also some text.

2. The same goes for several other tests that are performed
throughout, in particular (congestion_window < ssthresh) which would
be better as IsInSlowStart() / not IsInCongestionAvoidance() /
CwndIncrease() == slow_start / CwndIncrease() == congestion_avoidance.

The next is that there are unused and undefined variables.
acket_packets/acked_packets is the one that I noticed most acutely
this time.  When the congestion control is given an ACK to process, I
infer that this means the sum of the lengths of newly acknowledged
packets in that ACK.  However this variable is derived, it needs to be
explicitly defined somehow.

Reading RFC 5681, its congestion avoidance algorithm is
SMSS*SMSS/cwnd, which takes a fair bit of effort to map to
acked_packets.bytes / cwnd.  If I'm right, the unstated assumption in
RFC 5681 is that the sender is transmitting as much as the cwnd
permits, it is sending every segment at the maximum size (SMSS) and
the receiver is acknowledging every segment it receives.  That way the
sender sends cwnd/SMSS segments every round trip and receives that
many acknowledgements.  This seems to be the only way that the stated
goal of an increase of 1*SMSS per RTT is achievable.

Aside: For those up to speed on TCP, can they explain why ACK
splitting isn't considered when in congestion avoidance?  So much
effort is spent on explaining why it's important during slow start,
then the spec seems to forget this.  Sure, the effect is not as
significant in congestion avoidance, but it's still baffling.  The
same applies if the sender sends more and smaller segments.  Surely
that leads to a larger increase in CWND in the same way that splitting
ACKs would.

It seems like QUIC attempts to address this by accounting for bytes
received.  The idea appears to be to trade this off against reducing
the rate at which the window expands in congestion avoidance on
connections that aren't using the full connection capacity.  I think
that the formula might be incorrect.  Currently, it is:

   congestion_window += acked_packets.bytes / congestion_window

I think that it probably wants to be something like:

   congestion_window += kDefaultMss * acked_packets.bytes / congestion_window

(Here I'm assuming that kDefaultMss =~ SMSS, though it seems like the
actual constant might need some better justification.  Would this
integrate MTU discovery if that were performed?  Or would this produce
the wrong outcome on paths with an unusual-sized MTU?)

Otherwise, the formula will produce an increase of one byte for every
round trip, or - more precisely - every time an entire congestion
window worth of data is acknowledged.  That seems a little too
cautious.

I found the description of when the congestion window is reset to be baffling:

> QUIC decreases the congestion window to the minimum value once the retransmission timeout has been confirmed to not be spurious when the first post-RTO acknowledgement is processed.

Maybe consider rephrasing that one.

---

From: Mirja Kühlewind <[email-masked]>
Date: Thu, 24 Aug 2017 12:58:35 +0200

Hi Martin, 

> Am 24.08.2017 um 07:52 schrieb Martin Thomson <[email-masked]>:
> 

Actually not 100% sure what you mean by ACK splitting, however, initially it was assumed that every packets gets acked, then delayed acks were introduced, which led to a too slower increase rate, which however isn’t really significant in CA. Nowadays almost all system implement appropriate byte count (ABC) [rfc3465] which counts bytes as the quic draft does. However, delaying acks in slow would still lead to packet burst of 4 (or more) instead of 2 packet (if no pacing is implemented), which could lead to earlier losses, causing slow start to end too early. Does that help?

---

From: Martin Thomson <[email-masked]>
Date: Fri, 25 Aug 2017 08:20:06 +1000

> Actually not 100% sure what you mean by ACK splitting, however, initially it was assumed that every packets gets acked, then delayed acks were introduced, which led to a too slower increase rate, w…

My impression was that byte counting was common, but it still seems
like an error in the RFC to not consider the possibility that someone
might generate an ACK for every byte they receive.  Using the math
there and a modest SMSS, I could force a connection into CA and then
cause your congestion controller to ratchet up by a megabyte per round
trip (assuming that I can get 1000 or so ACKs through, of course[1]).
That's more aggressive than slow start.  ABC obviously corrects that
problem, but it's odd that the RFC seems to forget this point.

I get that delayed acks can cause the window to jump up in more
discrete steps, leading to bursts of transmission, but that was part
of what pacing was intended to address, right?

[1] My current link is 6.3/0.18, so the notion of asymmetry is
fascinating to me right now.

---

From: Yoshifumi Nishida <[email-masked]>
Date: Thu, 24 Aug 2017 15:57:07 -0700

Hi Martin,

> problem, but it's odd that the RFC seems to forget this point.

I'm not sure why you think it is forgotten.
rfc5681 mentions using ABC to provide robustness against ACK division attack.
--
Yoshi

---

From: Martin Thomson <[email-masked]>
Date: Fri, 25 Aug 2017 09:08:08 +1000

> rfc5681 mentions using ABC to provide robustness against ACK division attack.

It's equation 3 that distresses me.  The remainder of the text does
mention it, but provides no formula.  cwnd += SMSS*min(N,SMSS)/cwnd
would be a fine formula to have included somewhere, but this is left
to the reader to work out for themselves.

Also, RFC 3465 defines the following algorithm during congestion avoidance:

   When
   bytes_acked becomes greater than or equal to the value of the
   congestion window, bytes_acked is reduced by the value of cwnd.
   Next, cwnd is incremented by a full-sized segment (SMSS).

That practically invites ACK division attacks.

---

From: Ian Swett <[email-masked]>
Date: Thu, 24 Aug 2017 19:52:26 -0400

Thanks for taking a close look at the draft.

> found to be unnecessarily obtuse:
Yes, the hope is that the pseudocode will compliment the text, but at this
point neither are completely sufficient.

> immeasurably by an IsInRecovery() function.  Maybe also some text.

Good suggestion.

> CwndIncrease() == slow_start / CwndIncrease() == congestion_avoidance.
InSlowStart() is also a good suggestion(and is actually present in the
GQUIC code).

> explicitly defined somehow.
SG, will attempt to fix this.

> goal of an increase of 1*SMSS per RTT is achievable.

Yes, most congestion control specs assume the sender is never
app-limited(which is ridiculous, but...).

QUIC is specified to count bytes(RFC 3465), so the packet size should not
matter.

The idea is for every CWND acknowledged, the CWND increases by SMSS.

> that leads to a larger increase in CWND in the same way that splitting

I think that is also fixed when implementations do appropriate byte
counting(RFC 3465)?

> the wrong outcome on paths with an unusual-sized MTU?)
Good catch, this is an error, assuming both variables are in bytes, which
they should be.

> > QUIC decreases the congestion window to the minimum value once the
> retransmission timeout has been confirmed to not be spurious when the first
> post-RTO acknowledgement is processed.
>
I can split it into two sentences, but the text is fairly accurate.

---

From: Yoshifumi Nishida <[email-masked]>
Date: Thu, 24 Aug 2017 17:15:35 -0700

Hi Martin,

> to the reader to work out for themselves.

Fair enough. But, in my interpretation, the equation 3 is used to
describe the concept (and it is "MAY use").
Also, since rfc3465 is an experimental, we can also try other similar
formulas if we want.

> That practically invites ACK division attacks.

Hmm, not sure how it invites ACK division attacks..
You can increase cwnd only when byte_acked >= cwnd.
--
Yoshi

---

From: Martin Thomson <[email-masked]>
Date: Fri, 25 Aug 2017 10:25:59 +1000

> You can increase cwnd only when byte_acked >= cwnd.

Oh, I see.  I misread.

---

From: Christian Huitema <[email-masked]>
Date: Thu, 24 Aug 2017 22:52:14 -0700

> found to be unnecessarily obtuse:
I must say that I have some very similar feedback. The liberal use of
pseudo-code in the recovery draft makes it seriously confusing.

The recovery part should be simple enough. QUIC has a monotonously
increasing packet sequence number, which simplifies the algorithm
greatly. The recovery can be summarized by a set of simple decisions:

1) Are all packets candidate for retransmission?
    No. Only those that contain important date.  There is no need to
even acknowledge the other packets.

2) Is this packet lost?
    The answer is Yes if another packet has already been acknowledged,
with a sequence number more than N packets greater that the candidate
packet.
    The answer is also Yes if another packet has already been
acknowledged, if it was sent more than delta-T after the candidate packet.
    And the answer is also Yes if more than Timer has elapsed since the
packet was sent.

The variables N, delta-T and Timer are parameter of the algorithm. By
default, they can be set to 3, the max of RTT/8 and 1 millisecond, and
RTT plus two RTT standard deviation, respectively. Using a more
conservative timer does not hurt much, because we expect that the
sequence number and Delta-T test will be sufficient in most cases. If we
were adventurous, we would add to the protocol some dynamic evaluation
of N and Delta-T, based on the observation of out of of order packet
deliveries. Of course, this is much easier to observe at the receiver,
so we would need to define a management frame to pass these parameters.
But I don't know whether we are that adventurous.

3) Can the senders do something to speed up retransmission?
In the absence of continuous traffic flow, the previous decision tree
degenerates to timer based retransmission. To speed things up,
implementations can generate extra traffic. For example, if no
acknowledgement is received after a short timer, they can send a
gratuitous packet that may trigger a further acknowledgement. That's the
essence of the "tail loss probe" algorithm of TCP, but things are really
simpler with monotonously increasing packet sequence numbers. There are
various plausible ways to send a gratuitous packet -- a Ping, a Max Data
Update, or repeating the oldest packet will all work.

Of course, implementations should avoid sending too many gratuitous
packets, because it can cause congestion. The typical implementation
will wait one min-RTT before sending the first tail loss probe, then
just wait for the regular timer based retransmission. But we may start
being creative. For example, if packets are waiting and the
implementation is sending a naked ACK for whatever reason, it does not
cost much to add a Ping to that.

This simple text encompasses SACK, RACK, and Tail-Loss Probe. And it is
very easy to implement.

-- 
Christian Huitema

---

From: Mirja Kühlewind <[email-masked]>
Date: Fri, 25 Aug 2017 10:26:08 +0200

Hi Christian,

just one minor side comment:

> Am 25.08.2017 um 07:52 schrieb Christian Huitema <[email-masked]>:
> 

You need to acknowledge all packets because the loss rate is/may be input for congestion control.

Mirja

---

From: Gorry Fairhurst <[email-masked]>
Date: Fri, 25 Aug 2017 09:43:28 +0100

On 25/08/2017, 09:26, Mirja Kühlewind wrote:
>> Am 25.08.2017 um 07:52 schrieb Christian Huitema<[email-masked]>:
>>
I agree there is a need to report *all* (or ACK virtually all) received 
segments - that doesn't mean the sender has to retransmit "lost" 
segments, but is one important input to a congestion controller that is 
"safe"  for deployment outside of a controlled environment.

Gorry

---

From: Christian Huitema <[email-masked]>
Date: Fri, 25 Aug 2017 10:44:38 -0700

On 8/25/2017 1:43 AM, Gorry Fairhurst wrote:
> I agree there is a need to report *all* (or ACK virtually all)
> received segments - that doesn't mean the sender has to retransmit
> "lost" segments, but is one important input to a congestion controller
> that is "safe"  for deployment outside of a controlled environment.

Yes, Mirja and Gory, you are both right. All received packets shall be
reported. But this goes back to Martin's original criticism of the
recovery draft. The reliance on pseudo-code obscures the reasoning, and
may leave aside important questions. So my original 3 point list should
be continued with another three points noted below. When it comes to
congestion control, there is a need for a similar effort of explanation
and simplification, but that should come later.

   4) Should all packets be acknowledged?

   Yes. All received packet numbers need to be reported in the ACK. This
is important both for congestion control, since loss of acknowledgements
may indicate a problem with the connection, and for ACK trimming, which
is described below. There is a subtle difference between the need to be
reported and the need to trigger acknowledgements. Packets that do not
contain retransmissible data, such as pure ACK, should not trigger
acknowledgement. Acknowledging pure acknowledgements would trigger an
"ACK of ACK" ping pong storm, and that must be avoided. The pure ACK
packets will be acknowledged the next time an important packet triggers
an acknowledgement.

   5) When should acknowledgements be sent?

   Acknowledgements should be sent shortly after important packets have
been received. There is tension between sending ACK too late, which will
confuse senders, and sending ACK too frequently, which causes excessive
network load. Different implementations of TCP have implemented
different strategies, such as either sending ACK after receiving 2 data
packets, or waiting for a short delay and sending coalesced ACK for all
packets received until then. In that case, the "ACK coalescing delay"
should not be larger than a fraction of the RTT, such as 1/4th or
1/10th, or maybe 1 millisecond if the RTT is very short.

  6) When should acknowledgement lists be trimmed?

   The ACK in QUIC contains a list of acknowledged ranges, separated by
holes. The holes normally correspond to packets that have not yet been
received, and maybe also to packets that have already been acknowledged.
This is similar to the SACK option in TCP, but with an important
difference. In TCP, the holes will be filled eventually by
retransmissions. In QUIC, this will not happen, because a given packet
number is only used once. The number of holes will thus increase over
the lifetime of a connection. In the absence of a trimming strategy, a
naive implementation would thus send ACK with ever increasing lists of
acknowledged ranges, eventually reaching the maximum number of ranges
allowed by the protocol, 255.

   Another difference between QUIC and TCP is that in QUIC
acknowledgement cannot be reneged. This means that acknowledgements need
not be repeated if the receiver who sends the ACK knows that the
original sender already received the information. This knowledge can be
derived from the "ACK of ACK". If the receiver receives an ACK of its
own ACK, it knows that the ranges described in that ACK have been noted
as received by the original sender. There is no point in repeating them,
and they should be trimmed.

-- 
Christian Huitema

---

From: "Lubashev, Igor" <[email-masked]>
Date: Fri, 25 Aug 2017 19:55:25 +0000

There is a conflict between "Packets that do not contain retransmissible data, such as pure ACK, should not trigger acknowledgement" and the need for trimming ACK lists.  In a degenerate case, you can have "important" packets arriving with packet number gaps, so the receiver is sending ACKs with an ever growing number of gaps.  However, since these are "pure ACK" packets, the sender does not ACK them, preventing the receiver from trimming these ACK lists.

- Igor

-----Original Message-----
From: Christian Huitema [mailto:[email-masked]] 
Sent: Friday, August 25, 2017 1:45 PM
To: [email-masked]; Mirja Kühlewind <[email-masked]>
Cc: [email-masked]
Subject: Re: Congestion control algorithm questions

On 8/25/2017 1:43 AM, Gorry Fairhurst wrote:
>>>      No. Only those that contain important date.  There is no need 
>>> to even acknowledge the other packets.

Yes, Mirja and Gory, you are both right. All received packets shall be reported. But this goes back to Martin's original criticism of the recovery draft. The reliance on pseudo-code obscures the reasoning, and may leave aside important questions. So my original 3 point list should be continued with another three points noted below. When it comes to congestion control, there is a need for a similar effort of explanation and simplification, but that should come later.

   Yes. All received packet numbers need to be reported in the ACK. This is important both for congestion control, since loss of acknowledgements may indicate a problem with the connection, and for ACK trimming, which is described below. There is a subtle difference between the need to be reported and the need to trigger acknowledgements. Packets that do not contain retransmissible data, such as pure ACK, should not trigger acknowledgement. Acknowledging pure acknowledgements would trigger an "ACK of ACK" ping pong storm, and that must be avoided. The pure ACK packets will be acknowledged the next time an important packet triggers an acknowledgement.

   Acknowledgements should be sent shortly after important packets have been received. There is tension between sending ACK too late, which will confuse senders, and sending ACK too frequently, which causes excessive network load. Different implementations of TCP have implemented different strategies, such as either sending ACK after receiving 2 data packets, or waiting for a short delay and sending coalesced ACK for all packets received until then. In that case, the "ACK coalescing delay"
should not be larger than a fraction of the RTT, such as 1/4th or 1/10th, or maybe 1 millisecond if the RTT is very short.

   The ACK in QUIC contains a list of acknowledged ranges, separated by holes. The holes normally correspond to packets that have not yet been received, and maybe also to packets that have already been acknowledged.
This is similar to the SACK option in TCP, but with an important difference. In TCP, the holes will be filled eventually by retransmissions. In QUIC, this will not happen, because a given packet number is only used once. The number of holes will thus increase over the lifetime of a connection. In the absence of a trimming strategy, a naive implementation would thus send ACK with ever increasing lists of acknowledged ranges, eventually reaching the maximum number of ranges allowed by the protocol, 255.

   Another difference between QUIC and TCP is that in QUIC acknowledgement cannot be reneged. This means that acknowledgements need not be repeated if the receiver who sends the ACK knows that the original sender already received the information. This knowledge can be derived from the "ACK of ACK". If the receiver receives an ACK of its own ACK, it knows that the ranges described in that ACK have been noted as received by the original sender. There is no point in repeating them, and they should be trimmed.

--
Christian Huitema

---

From: Christian Huitema <[email-masked]>
Date: Fri, 25 Aug 2017 16:10:16 -0700

> There is a conflict between "Packets that do not contain retransmissible data, such as pure ACK, should not trigger acknowledgement" and the need for trimming ACK lists.  In a degenerate case, you…
Good point. But the sender of the ACK can easily elicit a response. I
got from Jana that  "After sending 20 pure acks, recent gQUIC versions
send a flow control update. This is specified in the draft. This flow
control update automatically triggers an ack in the opposite direction,
avoiding the need at the receiver of acks to do anything special."
Receivers could also send a Ping when the ACK list has grown too long.
Either way, they will receive an ACK and they will be able to trim the
ACK list.

-- 
Christian Huitema