Debian Codegraph @

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

raw
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 }