transport/cc: investigate more CWND reduction on Slow Start exit to avoid multiple losses

[omansfeld]

Due to the rapid growth in slow start we get double or triple loss on slow start exit. There have been some more discussions on it in #3112 (comment). See also the below slide deck from @mwelzl:

https://datatracker.ietf.org/meeting/120/materials/slides-120-iccrg-ssthresh-after-slow-start-overshoot-01.pdf

I did some brief experimentation on the simulator with a 10 MIB upload on 50 MBIT bandwidth and 40ms latency.

using current Cubic factor (reducing by 0.7 on loss): 25.48 Mb/s

• triple loss

using Reno factor (reducing by 0.5 on loss): 23.00 Mb/s

• double loss, but more inefficient than Cubic

reducing by 0.4 on loss: 35.32 Mb/s

• just one loss and much better throughput!

I reckon this will still be somewhat relevant even if we switch to heuristic based slow start at some point, because heuristics can fail in which case we'd still have slow start exit on loss and might see the same effect.

[omansfeld]

Copied over additional information from @mxinden's dublicate issue:

Neqo does Cubic by default.

neqo/neqo-transport/src/cc/classic_cc.rs

Line 747 in d665fc3

Cubic::default(),

On Slow Start exit, it will simply delegate congestion window reduction to Cubic.

neqo/neqo-transport/src/cc/classic_cc.rs

Lines 634 to 638 in d665fc3

	let (cwnd, acked_bytes) = self.cc_algorithm.reduce_cwnd(
	self.congestion_window,
	self.acked_bytes,
	self.max_datagram_size(),
	);

Cubic will reduce to 0.7 of the congestion window.

neqo/neqo-transport/src/cc/cubic.rs

Lines 124 to 155 in d665fc3

	/// `CUBIC_BETA` = 0.7;
	///
	/// <https://datatracker.ietf.org/doc/html/rfc9438#name-constants-of-interest>
	///
	/// > To balance between the scalability and convergence speed, CUBIC sets the multiplicative
	/// > window
	/// > decrease factor to 0.7 while Standard TCP uses 0.5. While this improves the scalability of
	/// > CUBIC, a side effect of this decision is slower convergence, especially under low
	/// > statistical multiplexing environments.
	///
	/// <https://datatracker.ietf.org/doc/html/rfc9438#name-principle-4-for-the-cubic-d>
	///
	/// For implementation reasons neqo uses a dividend and divisor approach with `usize` typing to
	/// construct `CUBIC_BETA = 0.7`.
	pub const BETA_USIZE_DIVIDEND: usize = 7;
	/// > CUBIC multiplicative decrease factor
	///
	/// <https://datatracker.ietf.org/doc/html/rfc9438#name-constants-of-interest>
	///
	/// > To balance between the scalability and convergence speed, CUBIC sets the multiplicative
	/// > window
	/// > decrease factor to 0.7 while Standard TCP uses 0.5. While this improves the scalability of
	/// > CUBIC, a side effect of this decision is slower convergence, especially under low
	/// > statistical
	/// > multiplexing environments.
	///
	/// <https://datatracker.ietf.org/doc/html/rfc9438#name-principle-4-for-the-cubic-d>
	///
	/// For implementation reasons neqo uses a dividend and divisor approach with `usize` typing to
	/// construct `CUBIC_BETA = 0.7`
	pub const BETA_USIZE_DIVISOR: usize = 10;

0.7 makes sense with Cubic's growth behavior (e.g. known previous wmax), not with Slow Starts exponential growth behavior without any previous anchor point.

RFC 9002's New Reno algorithm requires a reduction of 0.5:

On entering a recovery period, a sender MUST set the slow start threshold to half the value of the congestion window when loss is detected.

https://datatracker.ietf.org/doc/html/rfc9002#section-7.3.2

@mwelzl's research suggests, that 0.5 might not even be enough in most cases. See simple example on slide 5 below.

https://datatracker.ietf.org/meeting/120/materials/slides-120-iccrg-ssthresh-after-slow-start-overshoot-01.pdf

(Also discussed in #3112 (comment).)

We should consider exiting Slow start with less than our current 0.7 Cubic reduction factor.

//CC Previously discussed with Martin and @omansfeld.

[larseggert]

What does Linux do?

[mwelzl]

Linux = Linux Cubic TCP? AFAIK, back off the same from slow start as in congestion avoidance. Nobody does what I suggest, yet ;-)

[martinthomson]

The question I have is whether this one change is the only thing we need to be contemplating. 0.4 rather than 0.7 seems pretty well-supported by the evidence. However, 0.7^2 is higher and 0.7^3 is less than 0.4, how much of that factor is based on the (unknown) queue size component? Is there a different algorithm that would be better to employ immediately after exiting slow start, or is Cubic still good? If Cubic is still good, are the parameters we give it OK?

What Oskar's results show is that the final throughput is highly dependent on the point the congestion window is at when you start into a congestion avoidance phase proper. That is, once all the losses from the overshoot of slow start settle. THAT is dominated by RTT in many cases. Or is that just a question of whether we should be looking at an entirely different algorithm?

[mwelzl]

Re: "well-supported by the evidence": note that my model (and Linux tests, but these were Reno) in the slides only deals with a single connection over a single bottleneck. How common that problem is, how often multiple backoffs after slow start happen in reality, and how to properly fix it is unanswered.... I do want to write a paper about this and would welcome collaboration! Right now, waiting for data to be collected by a student :-) I'd absolutely love it if I could include data from Mozilla! for which I probably need: #backoffs before a full ACK arrives; min RTT and max RTT in slow start (because of my heuristics proposal, see below).

Primarily, the big unknown (as you correctly state) that will influence whether backing off by a value < 0.5 is better is the queue length: the problem only happens beyond a certain minimum queue length.

My idea would be to introduce heuristics, e.g. based on RTT growth, to make a decision, but this can have various problems of course.... which is why this is research and nothing I'm bringing to the IETF before that research is done. Also very correct: it depends on the point cwnd is at when starting into CA! Would it be good to start at cwnd = 1/2 BDP? Would it be better to set it to a value just below the BDP? For very short flows, there's probably an answer that depends on the flow length, and for long ones, the answer is probably "it doesn't matter".

Well... just my 2c here.

[omansfeld]

I'd absolutely love it if I could include data from Mozilla! for which I probably need: #backoffs before a full ACK arrives; min RTT and max RTT in slow start (because of my heuristics proposal, see below)

@mwelzl While this is definitely interesting we currently don't have cycles to work on it. We would be happy to review and merge a PR adding those metrics though!

As a first step metrics would have to be added and exposed as stats here in neqo, e.g. in CongestionControlStats.

neqo/neqo-transport/src/stats.rs

Lines 139 to 149 in b3338f9

	pub struct CongestionControlStats {
	/// Total number of congestion events caused by packet loss, total number of
	/// congestion events caused by ECN-CE marked packets, and number of
	/// spurious congestion events, where congestion was incorrectly inferred
	/// due to packets initially considered lost but subsequently acknowledged.
	/// The latter indicates instances where the congestion control algorithm
	/// overreacted to perceived losses.
	pub congestion_events: EnumMap<CongestionEvent, usize>,
	/// Whether this connection has exited slow start.
	pub slow_start_exited: bool,
	}

Most of the logic around congestion control is happening in the ClassicCongestionControl struct and it's implementations.

neqo/neqo-transport/src/cc/classic_cc.rs

Line 109 in b3338f9

pub struct ClassicCongestionControl<T> {

Afterwards there'd need to be a patch on the Firefox side integrating those stats into telemetry collection, find this example: https://phabricator.services.mozilla.com/D275053

On a side-note a small heads up: We are working on implementing algorithmic slow start exit (e.g. HyStart++) in #2858. Once that lands I imagine the data will be less valuable for you as we won't be seeing as many loss-exits anymore. So this might be kinda time-sensitive.