| 1 |
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or |
| 2 |
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license |
| 3 |
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your |
| 4 |
// option. This file may not be copied, modified, or distributed |
| 5 |
// except according to those terms. |
| 6 |
|
| 7 |
//! CUBIC congestion control |
| 8 |
|
| 9 |
use std::{ |
| 10 |
fmt::{self, Display}, |
| 11 |
time::{Duration, Instant}, |
| 12 |
}; |
| 13 |
|
| 14 |
use neqo_common::qtrace; |
| 15 |
|
| 16 |
use crate::cc::classic_cc::WindowAdjustment; |
| 17 |
|
| 18 |
/// > C is a constant fixed to determine the aggressiveness of window |
| 19 |
/// > increase in high BDP networks. |
| 20 |
/// |
| 21 |
/// <https://datatracker.ietf.org/doc/html/rfc8312#section-4.1> |
| 22 |
/// |
| 23 |
/// See discussion for rational for concrete value. |
| 24 |
/// |
| 25 |
/// <https://datatracker.ietf.org/doc/html/rfc8312#section-5.1> |
| 26 |
pub const CUBIC_C: f64 = 0.4; |
| 27 |
/// TCP-friendly region additive factor |
| 28 |
/// |
| 29 |
/// <https://datatracker.ietf.org/doc/html/rfc8312#section-4.2> |
| 30 |
pub const CUBIC_ALPHA: f64 = 3.0 * (1.0 - 0.7) / (1.0 + 0.7); |
| 31 |
|
| 32 |
/// `CUBIC_BETA` = 0.7; |
| 33 |
/// |
| 34 |
/// > Principle 4: To balance between the scalability and convergence speed, |
| 35 |
/// > CUBIC sets the multiplicative window decrease factor to 0.7 while Standard |
| 36 |
/// > TCP uses 0.5. While this improves the scalability of CUBIC, a side effect |
| 37 |
/// > of this decision is slower convergence, especially under low statistical |
| 38 |
/// > multiplexing environments. |
| 39 |
/// |
| 40 |
/// <https://datatracker.ietf.org/doc/html/rfc8312#section-3> |
| 41 |
pub const CUBIC_BETA_USIZE_DIVIDEND: usize = 7; |
| 42 |
pub const CUBIC_BETA_USIZE_DIVISOR: usize = 10; |
| 43 |
|
| 44 |
/// The fast convergence ratio further reduces the congestion window when a |
| 45 |
/// congestion event occurs before reaching the previous `W_max`. |
| 46 |
/// |
| 47 |
/// See formula defined below. |
| 48 |
/// |
| 49 |
/// <https://www.rfc-editor.org/rfc/rfc8312#section-4.6> |
| 50 |
pub const CUBIC_FAST_CONVERGENCE: f64 = 0.85; // (1.0 + CUBIC_BETA) / 2.0; |
| 51 |
|
| 52 |
/// The minimum number of multiples of the datagram size that need |
| 53 |
/// to be received to cause an increase in the congestion window. |
| 54 |
/// When there is no loss, Cubic can return to exponential increase, but |
| 55 |
/// this value reduces the magnitude of the resulting growth by a constant factor. |
| 56 |
/// A value of 1.0 would mean a return to the rate used in slow start. |
| 57 |
const EXPONENTIAL_GROWTH_REDUCTION: f64 = 2.0; |
| 58 |
|
| 59 |
/// Convert an integer congestion window value into a floating point value. |
| 60 |
/// This has the effect of reducing larger values to `1<<53`. |
| 61 |
/// If you have a congestion window that large, something is probably wrong. |
| 62 |
pub fn convert_to_f64(v: usize) -> f64 { |
| 63 |
let mut f_64 = f64::from(u32::try_from(v >> 21).unwrap_or(u32::MAX)); |
| 64 |
f_64 *= 2_097_152.0; // f_64 <<= 21 |
| 65 |
#[expect(clippy::cast_possible_truncation, reason = "The mask makes this safe.")] |
| 66 |
let v_trunc = (v & 0x1f_ffff) as u32; |
| 67 |
f_64 += f64::from(v_trunc); |
| 68 |
f_64 |
| 69 |
} |
| 70 |
|
| 71 |
#[derive(Debug, Default)] |
| 72 |
pub struct Cubic { |
| 73 |
/// Maximum Window size two congestion events ago. |
| 74 |
/// |
| 75 |
/// > With fast convergence, when a congestion event occurs, before the |
| 76 |
/// > window reduction of the congestion window, a flow remembers the last |
| 77 |
/// > value of W_max before it updates W_max for the current congestion |
| 78 |
/// > event. |
| 79 |
/// |
| 80 |
/// <https://datatracker.ietf.org/doc/html/rfc8312#section-4.6> |
| 81 |
last_max_cwnd: f64, |
| 82 |
/// Estimate of Standard TCP congestion window for Cubic's TCP-friendly |
| 83 |
/// Region. |
| 84 |
/// |
| 85 |
/// > Standard TCP performs well in certain types of networks, for example, |
| 86 |
/// > under short RTT and small bandwidth (or small BDP) networks. In |
| 87 |
/// > these networks, we use the TCP-friendly region to ensure that CUBIC |
| 88 |
/// > achieves at least the same throughput as Standard TCP. |
| 89 |
/// |
| 90 |
/// <https://datatracker.ietf.org/doc/html/rfc8312#section-4.2> |
| 91 |
estimated_tcp_cwnd: f64, |
| 92 |
/// > K is the time period that the above function takes to increase the |
| 93 |
/// > current window size to W_max if there are no further congestion events |
| 94 |
/// |
| 95 |
/// <https://datatracker.ietf.org/doc/html/rfc8312#section-4.1> |
| 96 |
k: f64, |
| 97 |
/// > W_max is the window size just before the window is reduced in the last |
| 98 |
/// > congestion event. |
| 99 |
/// |
| 100 |
/// <https://datatracker.ietf.org/doc/html/rfc8312#section-4.1> |
| 101 |
w_max: f64, |
| 102 |
/// > the elapsed time from the beginning of the current congestion |
| 103 |
/// > avoidance |
| 104 |
/// |
| 105 |
/// <https://datatracker.ietf.org/doc/html/rfc8312#section-4.1> |
| 106 |
ca_epoch_start: Option<Instant>, |
| 107 |
/// Number of bytes acked since the last Standard TCP congestion window increase. |
| 108 |
tcp_acked_bytes: f64, |
| 109 |
} |
| 110 |
|
| 111 |
impl Display for Cubic { |
| 112 |
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
| 113 |
write!( |
| 114 |
f, |
| 115 |
"Cubic [last_max_cwnd: {}, k: {}, w_max: {}, ca_epoch_start: {:?}]", |
| 116 |
self.last_max_cwnd, self.k, self.w_max, self.ca_epoch_start |
| 117 |
)?; |
| 118 |
Ok(()) |
| 119 |
} |
| 120 |
} |
| 121 |
|
| 122 |
#[expect(clippy::doc_markdown, reason = "Not doc items; names from RFC.")] |
| 123 |
impl Cubic { |
| 124 |
/// Original equations is: |
| 125 |
/// K = cubic_root(W_max*(1-beta_cubic)/C) (Eq. 2 RFC8312) |
| 126 |
/// W_max is number of segments of the maximum segment size (MSS). |
| 127 |
/// |
| 128 |
/// K is actually the time that W_cubic(t) = C*(t-K)^3 + W_max (Eq. 1) would |
| 129 |
/// take to increase to W_max. We use bytes not MSS units, therefore this |
| 130 |
/// equation will be: W_cubic(t) = C*MSS*(t-K)^3 + W_max. |
| 131 |
/// |
| 132 |
/// From that equation we can calculate K as: |
| 133 |
/// K = cubic_root((W_max - W_cubic) / C / MSS); |
| 134 |
/// |
| 135 |
/// <https://www.rfc-editor.org/rfc/rfc8312#section-4.1> |
| 136 |
fn calc_k(&self, curr_cwnd: f64, max_datagram_size: usize) -> f64 { |
| 137 |
((self.w_max - curr_cwnd) / CUBIC_C / convert_to_f64(max_datagram_size)).cbrt() |
| 138 |
} |
| 139 |
|
| 140 |
/// W_cubic(t) = C*(t-K)^3 + W_max (Eq. 1) |
| 141 |
/// t is relative to the start of the congestion avoidance phase and it is in seconds. |
| 142 |
/// |
| 143 |
/// <https://www.rfc-editor.org/rfc/rfc8312#section-4.1> |
| 144 |
fn w_cubic(&self, t: f64, max_datagram_size: usize) -> f64 { |
| 145 |
(CUBIC_C * (t - self.k).powi(3)).mul_add(convert_to_f64(max_datagram_size), self.w_max) |
| 146 |
} |
| 147 |
|
| 148 |
fn start_epoch( |
| 149 |
&mut self, |
| 150 |
curr_cwnd_f64: f64, |
| 151 |
new_acked_f64: f64, |
| 152 |
max_datagram_size: usize, |
| 153 |
now: Instant, |
| 154 |
) { |
| 155 |
self.ca_epoch_start = Some(now); |
| 156 |
// reset tcp_acked_bytes and estimated_tcp_cwnd; |
| 157 |
self.tcp_acked_bytes = new_acked_f64; |
| 158 |
self.estimated_tcp_cwnd = curr_cwnd_f64; |
| 159 |
if self.last_max_cwnd <= curr_cwnd_f64 { |
| 160 |
self.w_max = curr_cwnd_f64; |
| 161 |
self.k = 0.0; |
| 162 |
} else { |
| 163 |
self.w_max = self.last_max_cwnd; |
| 164 |
self.k = self.calc_k(curr_cwnd_f64, max_datagram_size); |
| 165 |
} |
| 166 |
qtrace!("[{self}] New epoch"); |
| 167 |
} |
| 168 |
} |
| 169 |
|
| 170 |
impl WindowAdjustment for Cubic { |
| 171 |
#[expect( |
| 172 |
clippy::cast_possible_truncation, |
| 173 |
clippy::cast_sign_loss, |
| 174 |
reason = "Cast from f64 to usize." |
| 175 |
)] |
| 176 |
fn bytes_for_cwnd_increase( |
| 177 |
&mut self, |
| 178 |
curr_cwnd: usize, |
| 179 |
new_acked_bytes: usize, |
| 180 |
min_rtt: Duration, |
| 181 |
max_datagram_size: usize, |
| 182 |
now: Instant, |
| 183 |
) -> usize { |
| 184 |
let curr_cwnd_f64 = convert_to_f64(curr_cwnd); |
| 185 |
let new_acked_f64 = convert_to_f64(new_acked_bytes); |
| 186 |
if self.ca_epoch_start.is_none() { |
| 187 |
// This is a start of a new congestion avoidance phase. |
| 188 |
self.start_epoch(curr_cwnd_f64, new_acked_f64, max_datagram_size, now); |
| 189 |
} else { |
| 190 |
self.tcp_acked_bytes += new_acked_f64; |
| 191 |
} |
| 192 |
|
| 193 |
// Cubic concave or convex region |
| 194 |
// |
| 195 |
// <https://datatracker.ietf.org/doc/html/rfc8312#section-4.3> |
| 196 |
// <https://datatracker.ietf.org/doc/html/rfc8312#section-4.4> |
| 197 |
let time_ca = self |
| 198 |
.ca_epoch_start |
| 199 |
.map_or(min_rtt, |t| { |
| 200 |
if now + min_rtt < t { |
| 201 |
// This only happens when processing old packets |
| 202 |
// that were saved and replayed with old timestamps. |
| 203 |
min_rtt |
| 204 |
} else { |
| 205 |
now + min_rtt - t |
| 206 |
} |
| 207 |
}) |
| 208 |
.as_secs_f64(); |
| 209 |
let target_cubic = self.w_cubic(time_ca, max_datagram_size); |
| 210 |
|
| 211 |
// Cubic TCP-friendly region |
| 212 |
// |
| 213 |
// <https://datatracker.ietf.org/doc/html/rfc8312#section-4.2> |
| 214 |
let max_datagram_size = convert_to_f64(max_datagram_size); |
| 215 |
let tcp_cnt = self.estimated_tcp_cwnd / CUBIC_ALPHA; |
| 216 |
let incr = (self.tcp_acked_bytes / tcp_cnt).floor(); |
| 217 |
if incr > 0.0 { |
| 218 |
self.tcp_acked_bytes -= incr * tcp_cnt; |
| 219 |
self.estimated_tcp_cwnd += incr * max_datagram_size; |
| 220 |
} |
| 221 |
|
| 222 |
// Take the larger cwnd of Cubic concave or convex and Cubic |
| 223 |
// TCP-friendly region. |
| 224 |
// |
| 225 |
// > When receiving an ACK in congestion avoidance (cwnd could be |
| 226 |
// > greater than or less than W_max), CUBIC checks whether W_cubic(t) is |
| 227 |
// > less than W_est(t). If so, CUBIC is in the TCP-friendly region and |
| 228 |
// > cwnd SHOULD be set to W_est(t) at each reception of an ACK. |
| 229 |
// |
| 230 |
// <https://datatracker.ietf.org/doc/html/rfc8312#section-4.2> |
| 231 |
let target_cwnd = target_cubic.max(self.estimated_tcp_cwnd); |
| 232 |
|
| 233 |
// Calculate the number of bytes that would need to be acknowledged for an increase |
| 234 |
// of `max_datagram_size` to match the increase of `target - cwnd / cwnd` as defined |
| 235 |
// in the specification (Sections 4.4 and 4.5). |
| 236 |
// The amount of data required therefore reduces asymptotically as the target increases. |
| 237 |
// If the target is not significantly higher than the congestion window, require a very |
| 238 |
// large amount of acknowledged data (effectively block increases). |
| 239 |
let mut acked_to_increase = |
| 240 |
max_datagram_size * curr_cwnd_f64 / (target_cwnd - curr_cwnd_f64).max(1.0); |
| 241 |
|
| 242 |
// Limit increase to max 1 MSS per EXPONENTIAL_GROWTH_REDUCTION ack packets. |
| 243 |
// This effectively limits target_cwnd to (1 + 1 / EXPONENTIAL_GROWTH_REDUCTION) cwnd. |
| 244 |
acked_to_increase = acked_to_increase.max(EXPONENTIAL_GROWTH_REDUCTION * max_datagram_size); |
| 245 |
acked_to_increase as usize |
| 246 |
} |
| 247 |
|
| 248 |
fn reduce_cwnd( |
| 249 |
&mut self, |
| 250 |
curr_cwnd: usize, |
| 251 |
acked_bytes: usize, |
| 252 |
max_datagram_size: usize, |
| 253 |
) -> (usize, usize) { |
| 254 |
let curr_cwnd_f64 = convert_to_f64(curr_cwnd); |
| 255 |
// Fast Convergence |
| 256 |
// |
| 257 |
// If congestion event occurs before the maximum congestion window before the last |
| 258 |
// congestion event, we reduce the the maximum congestion window and thereby W_max. |
| 259 |
// check cwnd + MAX_DATAGRAM_SIZE instead of cwnd because with cwnd in bytes, cwnd may be |
| 260 |
// slightly off. |
| 261 |
// |
| 262 |
// <https://www.rfc-editor.org/rfc/rfc8312#section-4.6> |
| 263 |
self.last_max_cwnd = |
| 264 |
if curr_cwnd_f64 + convert_to_f64(max_datagram_size) < self.last_max_cwnd { |
| 265 |
curr_cwnd_f64 * CUBIC_FAST_CONVERGENCE |
| 266 |
} else { |
| 267 |
curr_cwnd_f64 |
| 268 |
}; |
| 269 |
self.ca_epoch_start = None; |
| 270 |
( |
| 271 |
curr_cwnd * CUBIC_BETA_USIZE_DIVIDEND / CUBIC_BETA_USIZE_DIVISOR, |
| 272 |
acked_bytes * CUBIC_BETA_USIZE_DIVIDEND / CUBIC_BETA_USIZE_DIVISOR, |
| 273 |
) |
| 274 |
} |
| 275 |
|
| 276 |
fn on_app_limited(&mut self) { |
| 277 |
// Reset ca_epoch_start. Let it start again when the congestion controller |
| 278 |
// exits the app-limited period. |
| 279 |
self.ca_epoch_start = None; |
| 280 |
} |
| 281 |
|
| 282 |
#[cfg(test)] |
| 283 |
fn last_max_cwnd(&self) -> f64 { |
| 284 |
self.last_max_cwnd |
| 285 |
} |
| 286 |
|
| 287 |
#[cfg(test)] |
| 288 |
fn set_last_max_cwnd(&mut self, last_max_cwnd: f64) { |
| 289 |
self.last_max_cwnd = last_max_cwnd; |
| 290 |
} |
| 291 |
} |