Subject: Congestion Control Questions

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

I am looking at the recovery and congestion control draft, and I have a
couple of questions regarding congestion control. Congestion control
attempts to limit traffic to the capacity of the path, in order to avoid
building long queues. When the path is shared, congestion control also
aims at giving every participant a fair share. But there is a first
question: how do we express the capacity of the path? Is it packets per
second or bytes per second?

Christian Huitema

---

From: Roland Zink <[email-masked]>
Date: Fri, 25 Aug 2017 21:04:29 +0200

With TCP the congestion control happened in the kernel outside the reach 
of most programmers. Now with QUIC you give it to app programmers. Will 
they use a fair algorithm or will they try to "optimize" it for their 
app? What can be done if somebody use a not so fair scheme?

Packets can be short or long, so usually the link capacity is given in 
bytes per second or bits per second.

Roland

---

From: "Salz, Rich" <[email-masked]>
Date: Fri, 25 Aug 2017 19:09:07 +0000

➢ What can be done if somebody use a not so fair scheme?
    
Probably nothing, and that is okay.  We cannot control what applications do.

---

From: Victor Vasiliev <[email-masked]>
Date: Fri, 25 Aug 2017 12:43:24 -0700

That has historically varied across TCP implementations.  Linux TCP does
congestion control in unit of packets, while FreeBSD one does it in unit of
bytes.  Google QUIC used to have both, but we eventually settled on bytes
as it performed better in our experiments.

Pacing rate appears to be almost always expressed in bits per second, so
typically packets per second is converted to bytes per second using MSS as
packet size for that purpose.

---

From: Christian Huitema <[email-masked]>
Date: Fri, 25 Aug 2017 13:18:57 -0700

On 8/25/2017 12:04 PM, Roland Zink wrote:
> With TCP the congestion control happened in the kernel outside the
> reach of most programmers. Now with QUIC you give it to app
> programmers. Will they use a fair algorithm or will they try to
> "optimize" it for their app? What can be done if somebody use a not so
> fair scheme?

Well, application programmers do have an incentive to not create
congestion, because congestion causes losses and delays that degrades
the application's performance. But I agree with you, they do not have an
incentive to ensure fair sharing.

With current in kernel TCP implementations, application programmers can
play games by opening multiple connections. With an in-process transport
like QUIC, they can achieve the same result by tweaking the parameters
of the congestion control algorithm. For example, if QUIC recommends New
Reno, they can tweak the increase and decrease coefficients to simulate
N connections, and thus get N times their "fair share". At one point,
Google QUIC did in fact have a congestion control option to set this
"number of simulated connections". The rationale was that they competed
with browsers that would open two connections to a given site, so they
might just as well simulate two connections.

The end game is probably generalized implementations of AQM algorithms
in network routers. If the routers implement some variation of fair
queuing, it does not matter whether the congestion control
implementation strives for fairness or not. That will give a serious
incentive to the application to use the congestion control algorithms
that best suits their need, which is normally a balance between minimize
delays, minimizes losses or maximize throughput. Different applications
may well pick different points in that curve. There is of course a ton
of research on possible algorithms.

But for now, the WG has a simple mandate: specify a congestion control
algorithm similar to TCP's New Reno.

> bytes per second or bits per second.

Yes, but there is per packet overhead. Sending 1000 packets with a one
byte payload is not the same as sending 1 packet with a 1000 bytes payload.

Also, the original New Reno specification was pretty much expressed in
terms of packets. For example, in congestion avoidance mode it increases
the TCP congestion window by one packet length per round trip.
>> second or bytes per second?
I assume that this will be bytes per second, but I question the decision
in the draft to not include the length of ACK in the total. That seems
arbitrary. Why exempting ACK and not exempting MAXDATA, for example? It
is certainly possible in some network configurations to saturate a low
speed uplink by sending too many ACKs for data received through a high
speed downlink.

Since all packets are acknowledged, summing the length of all packets in
flight is much easier than keeping track of what exactly was inside the
packets.

-- 
Christian Huitema

---

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

On 8/25/2017 12:43 PM, Victor Vasiliev wrote:
> That has historically varied across TCP implementations.  Linux TCP
> does congestion control in unit of packets, while FreeBSD one does it
> in unit of bytes.  Google QUIC used to have both, but we eventually
> settled on bytes as it performed better in our experiments.
>
> Pacing rate appears to be almost always expressed in bits per second,
> so typically packets per second is converted to bytes per second using
> MSS as packet size for that purpose.

OK, I suppose we can go with that in the recovery draft, since that does
match most TCP implementations. But reading the draft again, I have
another question, concerning "recovery". The current recovery draft says
that "Recovery is a period of time beginning with detection of a lost
packet. It ends when all packets outstanding at the time recovery began
have been acknowledged or lost."That's OK, it can be implemented. But
that's different from the actual New Reno spec.

In New Reno, implementations enter discovery when a packet is lost, and
exit discovery when the packet is finally successfully retransmitted and
acknowledged. But there is no such thing as packet retransmission in
QUIC. When a packet is lost, the corresponding frames may or may not be
retransmitted. So the text in the recovery draft finesses that, by
requesting that the entire flight be "acknowledged or lost", but not
actually retransmitted.

Which goes back to the reliance on pseudo code. It would be nice if
there was text explaining how the QUIC algorithm differs from New Reno,
and why.

-- 

Christian Huitema

---

From: "Swindells, Thomas (Nokia - GB/Cambridge, UK)" <[email-masked]>
Date: Mon, 28 Aug 2017 13:41:25 +0000

> Which goes back to the reliance on pseudo code. It would be nice if there was
> text explaining how the QUIC algorithm differs from New Reno, and why.

I think this statement actually gets to the route of the problem. 
My understanding (presumption) is that a Quic implementation doesn't have to use New Reno or any particular algorithm - an implementation could use BBR for instance if it wants. However there are a number of requirements that any algorithm must meet to be a conforming quic implementation - your previous excellent list of statements/explanations summed up many of these (Should all packets be acknowledged, etc). Currently however the spec interweaves the generic requirements with pseudo code for a particular implementation suggestion. It may well be worth having a suggested congestion control algorithm, but this should probably be separated into an appendix/separate section with the fundamental behaviours and requirements clearly defined first.

Thomas

---

From: Gorry Fairhurst <[email-masked]>
Date: Mon, 28 Aug 2017 18:02:37 +0100

> My understanding (presumption) is that a Quic implementation doesn't have to use New Reno or any particular algorithm - an implementation could use BBR for instance if it wants. However there are a…
The charter calls for congestion control using a  standardized 
congestion controller as a default scheme for QUIC. That I was assuming 
was RENO-based, as Christian noted.

I can really see merits in having a generic requirements document for 
congestion control requirements - although I am not keen though on 
seeing a Reno-like implementation only in an annexe; I guess the 
RENO-based spec could alternately become a separate document. I'm 
expecting in future, there may be other CC's that are specified by the 
IETF, probably based on algorithms that the IETF has evaluated reached 
consensus upon - BBR isn't one of those yet.

Gorry

---

From: Mirja Kühlewind <[email-masked]>
Date: Mon, 28 Aug 2017 19:23:06 +0200

My thinking actually was that the recovery and congestion control schemes are in a separate document because this gives you the flexibility to specify alternatives in future. If there are parts in this document that are mandatory for all future instances of this version of QUIC or specify requirements, they should go into the main transport spec. However, I think all we really need in the main spec is a requirement to do congestion control at all; everything else in the recovery/cc draft should be sender-side only and can therefore be changed without requiring any negotiation or changes by the other end.

Mirja

> Am 28.08.2017 um 19:02 schrieb Gorry Fairhurst <[email-masked]>:
> 
> The charter calls for congestion control using a  standardized congestion controller as a default scheme for QUIC. That I was assuming was RENO-based, as Christian noted.
> 
> I can really see merits in having a generic requirements document for congestion control requirements - although I am not keen though on seeing a Reno-like implementation only in an annexe; I guess the RENO-based spec could alternately become a separate document. I'm expecting in future, there may be other CC's that are specified by the IETF, probably based on algorithms that the IETF has evaluated reached consensus upon - BBR isn't one of those yet.
> 
> Gorry
>

---

From: Gorry Fairhurst <[email-masked]>
Date: Mon, 28 Aug 2017 18:30:42 +0100

> My thinking actually was that the recovery and congestion control schemes are in a separate document because this gives you the flexibility to specify alternatives in future. If there are parts in…
This also seems like it would work. I suspect RFC8085 gives a basic 
requirement anyway to do CC.

Gorry

---

From: Christian Huitema <[email-masked]>
Date: Mon, 28 Aug 2017 12:35:51 -0700

I agree with Mirja. It would be much clearer to separate recovery and congestion.

-- Christian Huitema 

> On Aug 28, 2017, at 10:30 AM, Gorry Fairhurst <[email-masked]> wrote:
> 
> This also seems like it would work. I suspect RFC8085 gives a basic requirement anyway to do CC.
> 
> Gorry
>

---

From: Spencer Dawkins at IETF <[email-masked]>
Date: Tue, 29 Aug 2017 09:37:13 -0500

FWIW,

On Mon, Aug 28, 2017 at 12:23 PM, Mirja Kühlewind <
[email-masked]> wrote:

> My thinking actually was that the recovery and congestion control schemes
> are in a separate document because this gives you the flexibility to
> specify alternatives in future.

That was certainly my understanding, when we were doing the charter.

> If there are parts in this document that are mandatory for all future
> instances of this version of QUIC or specify requirements, they should go
> into the main transport spec. However, I think all we really need in the
> main spec is a requirement to do congestion control at all;

I would support that ... but, just to take a QUIC(!) sample ...

> everything else in the recovery/cc draft should be sender-side only and
> can therefore be changed without requiring any negotiation or changes by
> the other end.

I'm hoping that's true, but feel I should ask if people are thinking about
behavior that's NOT sender-side only, right about here, in this thread.

Spencer

---

From: "Philipp S. Tiesel" <[email-masked]>
Date: Wed, 30 Aug 2017 10:45:53 +0200

> On 29. Aug 2017, at 16:37, Spencer Dawkins at IETF <[email-masked]> wrote:

…

> everything else in the recovery/cc draft should be sender-side only and can therefore be changed without requiring any negotiation or changes by the other end.
> 
> I'm hoping that's true, but feel I should ask if people are thinking about behavior that's NOT sender-side only, right about here, in this thread.

At the moment, I see one case where this assumption does not hold: purely ECN based congestion control. In this case, the receiver must agree to notify the sender about ECN marked packets. 
Can be mitigated easily by negotiation ECN and fall back to loss based CC if not available, but this _is_ some kind of negotiation.

I guess requiring sender-side behaviour only unless negotiated otherwise will do the trick. 

AVE!
  Philipp S. Tiesel / phils…
-- 
   {phils}--->---([email-masked])--->---(http://phils.in-panik.de)----,
      wenn w eine   aube ist dn      man au dran dre en                   |
           o     Schr        an muss     hc         h   (Kurt Schwitters) |
:wq!  <----(phone: +49-179-6737439)---<---(jabber: [email-masked])----'

---

From: Spencer Dawkins at IETF <[email-masked]>
Date: Wed, 30 Aug 2017 10:03:30 -0500

Hi, Philipp,

On Wed, Aug 30, 2017 at 3:45 AM, Philipp S. Tiesel <[email-masked]>
wrote:

> > I'm hoping that's true, but feel I should ask if people are thinking
> about behavior that's NOT sender-side only, right about here, in this
> thread.
>
> At the moment, I see one case where this assumption does not hold: purely
> ECN based congestion control. In this case, the receiver must agree to
> notify the sender about ECN marked packets.
> Can be mitigated easily by negotiation ECN and fall back to loss based CC
> if not available, but this _is_ some kind of negotiation.
>

I knew that, but BOY, it didn't come out in my question! I think I've been
talking about ECN enough lately that I'm taking it as a given, especially
based on the last testing results I saw in Prague. Thanks for making that
explicit.

Anything else? :-)

Spencer

---

From: Christian Huitema <[email-masked]>
Date: Wed, 30 Aug 2017 12:04:16 -0700

> Anything else? :-)

I can think of cooperative schemes between the peers. For example, the
receiver has a good idea of the packet reordering properties of the
network, how long can an out of order packet be delayed. One can imagine
the receiver passing that information to the sender in a special frame,
for more efficient recovery. The receiver could also observe properties
of the received stream such as bunching of packets, or some clever
statistical analysis that we have not thought off yet. That too could be
passed in a special frame. The peers could also negotiate a lower
priority congestion algorithm, e.g. using LEDBAT instead of New Reno.

All this is of course speculative. And maybe it points to the need for a
simple extension mechanism, so we can experiment with this sort of
things. I could think of:

* defining an extension ID as a 32 bit number;
* adding a supported extension list in the transport parameters, with an
implicit negotiation,
* adding an extended frame format, starting with a length and a 32 bit
extension ID.

But to come back to your original question, we can certainly start by
assuming that congestion control and recovery algorithms are sender only.

-- 
Christian Huitema

---

From: Spencer Dawkins at IETF <[email-masked]>
Date: Wed, 30 Aug 2017 17:30:23 -0500

Hi, Christian,

On Wed, Aug 30, 2017 at 2:04 PM, Christian Huitema <[email-masked]>
wrote:

> the receiver passing that information to the sender in a special frame, for
> more efficient recovery. The receiver could also observe properties of the
> received stream such as bunching of packets, or some clever statistical
> analysis that we have not thought off yet. That too could be passed in a
> special frame. The peers could also negotiate a lower priority congestion
> algorithm, e.g. using LEDBAT instead of New Reno.
>
> simple extension mechanism, so we can experiment with this sort of things.
> I could think of:
>

Thanks for your thoughts on this (which sound very useful to me), and I'm
fine making that starting assumption (modulo ECN, which I *hope* people
think is a baseline for transport functionality in 2017, which is why *I*
forget to mention it).

 ADs have to ask ... ;-)

Spencer

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 30 Aug 2017 22:20:05 -0700

A few thoughts:

- On recovery: NewReno's mechanism in TCP is exactly as Christian says, but
that's because that was the only way to implement a recovery period in TCP.
The motivation of the "recover" period in NewReno was for two reasons: (i)
to avoid multiple cutbacks within an RTT, and (ii) to allow clocking out of
retransmissions on "partial acks". I'm happy to go into the details of
these if necessary, but for now I'll point to the sacks paper
<ftp://ftp.ee.lbl.gov/papers/sacks.ps.Z> for more detailed analysis. The
actions required during recovery changes quite a bit with QUIC, since we do
not have the same problems. Specifically, QUIC does not *need* the concept
of partial acks, since all acks carry detailed information.

QUIC is probably closer to loss recovery with TCP SACK than NewReno, but
even there, RFC 6675 (which specifies a loss recovery algorithm with TCP
SACK) is conservative because of the possibility that a receiver might
renege on previously SACKed blocks. A QUIC receiver cannot renege on any
received packets, so we do not need to wait for the equivalent of the
"cumulative ack" point to move past the recovery point. So, the QUIC
algorithm waits for an RTT to ensure that there aren't multiple cwnd
cutbacks within an RTT, which is exactly what is specified.

I agree that describing all this in the doc would be useful, and I'll get
to doing that shortly.

- On bytes vs packets: as Victor said, bytes is the right thing to do
congestion control on since congestion is expected to be in bytes, not
packets, but gating should be in packets. This is what the spec tries to
express.

- On ACK frames: it was a conscious decision to not include acks in
congestion control because they also cannot be gated by congestion control.
This point can certainly be debated, but I would suggest that we tread a
bit carefully when thinking about ACKs and congestion control, since CC
tends to be quite sensitive to ACK timing.

- I agree that more text needs to be written around the pseudo code but I'm
not keen to split the congestion control and loss recovery mechanisms into
two docs yet. I'd be happy to reconsider this when we've fleshed the doc
out more -- I do see the merit in splitting them, but from an editorial
perspective, I'd suggest that we leave them together for now and split them
later if needed.

---

From: "Eggert, Lars" <[email-masked]>
Date: Thu, 31 Aug 2017 07:05:40 +0000

On 2017-8-30, at 21:04, Christian Huitema <[email-masked]> wrote:
> I can think of cooperative schemes between the peers. For example, the receiver has a good idea of the packet reordering properties of the network, how long can an out of order packet be delayed. One can imagine the receiver passing that information to the sender in a special frame, for more efficient recovery. The receiver could also observe properties of the received stream such as bunching of packets, or some clever statistical analysis that we have not thought off yet. That too could be passed in a special frame. The peers could also negotiate a lower priority congestion algorithm, e.g. using LEDBAT instead of New Reno.

You should read "Re-architecting datacenter networks and stacks for low latency and high performance", which you can get to by searching for "NDP" on http://conferences.sigcomm.org/sigcomm/2017/program.html and following the link there. (The ACM DL has this really crappy referrer-based open-access system.)

That paper just won the SIGCOMM best paper award. It's of course about datacenters, but the idea of receiver-driven congestion control and loss-recovery is pretty central to its idea. (And to a lot of the information-centric networking architectures, but they are further from the current Internet model.)

Oh, and make sure you watch https://youtu.be/BO0QhaxBRr0 before reading the NDP paper :-)

Lars

---

From: Mirja Kühlewind <[email-masked]>
Date: Thu, 31 Aug 2017 18:50:40 +0200

Hi Christian,

first two quick comments:

- delaying ACKs and potentially negotiating about it is under discussion in 
issue #230

- using e.g LEDBAT is from the transport point of view after all a 
sender-only decision because it's the sender that need to implement a way to 
decide when to send out which packet. If the sender needs additional 
information from the receiver which scheme should be used that should 
probably be communicated in the application itself.

Having that said of course there is theoretically the possibility to 
implement every algorithm or even parts of the algorithm on each side. The 
only thing that changes is which information you need to send forth and back 
between the sender and receiver, e.g. the receiver could just tell the sender 
continuously the sending rate. However, in quic I think we already decided 
which information to send, namely all the information available in the ACK 
frame (+ ECN information where the format is still tbd). And therefore the 
exact implementation of a congestion control algorithm is a sender-side 
decision (with an interface to the application to configure the algorithm 
that should be used).

Mirja

On 30.08.2017 21:04, Christian Huitema wrote:
> receiver has a good idea of the packet reordering properties of the network, 
> how long can an out of order packet be delayed. One can imagine the receiver 
> passing that information to the sender in a special frame, for more efficient 
> recovery. The receiver could also observe properties of the received stream 
> such as bunching of packets, or some clever statistical analysis that we have 
> not thought off yet. That too could be passed in a special frame. The peers 
> could also negotiate a lower priority congestion algorithm, e.g. using LEDBAT 
> instead of New Reno.
> 
> simple extension mechanism, so we can experiment with this sort of things. I 
> could think of:
>