| 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 |
#![expect( |
| 8 |
clippy::cast_possible_truncation, |
| 9 |
clippy::cast_sign_loss, |
| 10 |
reason = "OK in tests." |
| 11 |
)] |
| 12 |
|
| 13 |
use std::{ |
| 14 |
ops::Sub, |
| 15 |
time::{Duration, Instant}, |
| 16 |
}; |
| 17 |
|
| 18 |
use test_fixture::now; |
| 19 |
|
| 20 |
use super::{IP_ADDR, MTU, RTT}; |
| 21 |
use crate::{ |
| 22 |
cc::{ |
| 23 |
classic_cc::ClassicCongestionControl, |
| 24 |
cubic::{ |
| 25 |
convert_to_f64, Cubic, CUBIC_ALPHA, CUBIC_BETA_USIZE_DIVIDEND, |
| 26 |
CUBIC_BETA_USIZE_DIVISOR, CUBIC_C, CUBIC_FAST_CONVERGENCE, |
| 27 |
}, |
| 28 |
CongestionControl as _, |
| 29 |
}, |
| 30 |
packet::PacketType, |
| 31 |
pmtud::Pmtud, |
| 32 |
recovery::SentPacket, |
| 33 |
rtt::RttEstimate, |
| 34 |
}; |
| 35 |
|
| 36 |
const fn cwnd_after_loss(cwnd: usize) -> usize { |
| 37 |
cwnd * CUBIC_BETA_USIZE_DIVIDEND / CUBIC_BETA_USIZE_DIVISOR |
| 38 |
} |
| 39 |
|
| 40 |
const fn cwnd_after_loss_slow_start(cwnd: usize, mtu: usize) -> usize { |
| 41 |
(cwnd + mtu) * CUBIC_BETA_USIZE_DIVIDEND / CUBIC_BETA_USIZE_DIVISOR |
| 42 |
} |
| 43 |
|
| 44 |
fn fill_cwnd(cc: &mut ClassicCongestionControl<Cubic>, mut next_pn: u64, now: Instant) -> u64 { |
| 45 |
while cc.bytes_in_flight() < cc.cwnd() { |
| 46 |
let sent = SentPacket::new( |
| 47 |
PacketType::Short, |
| 48 |
next_pn, |
| 49 |
now, |
| 50 |
true, |
| 51 |
Vec::new(), |
| 52 |
cc.max_datagram_size(), |
| 53 |
); |
| 54 |
cc.on_packet_sent(&sent, now); |
| 55 |
next_pn += 1; |
| 56 |
} |
| 57 |
next_pn |
| 58 |
} |
| 59 |
|
| 60 |
fn ack_packet(cc: &mut ClassicCongestionControl<Cubic>, pn: u64, now: Instant) { |
| 61 |
let acked = SentPacket::new( |
| 62 |
PacketType::Short, |
| 63 |
pn, |
| 64 |
now, |
| 65 |
true, |
| 66 |
Vec::new(), |
| 67 |
cc.max_datagram_size(), |
| 68 |
); |
| 69 |
cc.on_packets_acked(&[acked], &RttEstimate::from_duration(RTT), now); |
| 70 |
} |
| 71 |
|
| 72 |
fn packet_lost(cc: &mut ClassicCongestionControl<Cubic>, pn: u64) { |
| 73 |
const PTO: Duration = Duration::from_millis(120); |
| 74 |
let p_lost = SentPacket::new( |
| 75 |
PacketType::Short, |
| 76 |
pn, |
| 77 |
now(), |
| 78 |
true, |
| 79 |
Vec::new(), |
| 80 |
cc.max_datagram_size(), |
| 81 |
); |
| 82 |
cc.on_packets_lost(None, None, PTO, &[p_lost], now()); |
| 83 |
} |
| 84 |
|
| 85 |
fn expected_tcp_acks(cwnd_rtt_start: usize, mtu: usize) -> u64 { |
| 86 |
(f64::from(i32::try_from(cwnd_rtt_start).unwrap()) |
| 87 |
/ f64::from(i32::try_from(mtu).unwrap()) |
| 88 |
/ CUBIC_ALPHA) |
| 89 |
.round() as u64 |
| 90 |
} |
| 91 |
|
| 92 |
#[test] |
| 93 |
fn tcp_phase() { |
| 94 |
let mut cubic = ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU)); |
| 95 |
|
| 96 |
// change to congestion avoidance state. |
| 97 |
cubic.set_ssthresh(1); |
| 98 |
|
| 99 |
let mut now = now(); |
| 100 |
let start_time = now; |
| 101 |
// helper variables to remember the next packet number to be sent/acked. |
| 102 |
let mut next_pn_send = 0; |
| 103 |
let mut next_pn_ack = 0; |
| 104 |
|
| 105 |
next_pn_send = fill_cwnd(&mut cubic, next_pn_send, now); |
| 106 |
|
| 107 |
// This will start with TCP phase. |
| 108 |
// in this phase cwnd is increase by CUBIC_ALPHA every RTT. We can look at it as |
| 109 |
// increase of MAX_DATAGRAM_SIZE every 1 / CUBIC_ALPHA RTTs. |
| 110 |
// The phase will end when cwnd calculated with cubic equation is equal to TCP estimate: |
| 111 |
// CUBIC_C * (n * RTT / CUBIC_ALPHA)^3 * MAX_DATAGRAM_SIZE = n * MAX_DATAGRAM_SIZE |
| 112 |
// from this n = sqrt(CUBIC_ALPHA^3/ (CUBIC_C * RTT^3)). |
| 113 |
let num_tcp_increases = (CUBIC_ALPHA.powi(3) / (CUBIC_C * RTT.as_secs_f64().powi(3))) |
| 114 |
.sqrt() |
| 115 |
.floor() as u64; |
| 116 |
|
| 117 |
for _ in 0..num_tcp_increases { |
| 118 |
let cwnd_rtt_start = cubic.cwnd(); |
| 119 |
// Expected acks during a period of RTT / CUBIC_ALPHA. |
| 120 |
let acks = expected_tcp_acks(cwnd_rtt_start, cubic.max_datagram_size()); |
| 121 |
// The time between acks if they are ideally paced over a RTT. |
| 122 |
let time_increase = |
| 123 |
RTT / u32::try_from(cwnd_rtt_start / cubic.max_datagram_size()).unwrap(); |
| 124 |
|
| 125 |
for _ in 0..acks { |
| 126 |
now += time_increase; |
| 127 |
ack_packet(&mut cubic, next_pn_ack, now); |
| 128 |
next_pn_ack += 1; |
| 129 |
next_pn_send = fill_cwnd(&mut cubic, next_pn_send, now); |
| 130 |
} |
| 131 |
|
| 132 |
assert_eq!(cubic.cwnd() - cwnd_rtt_start, cubic.max_datagram_size()); |
| 133 |
} |
| 134 |
|
| 135 |
// The next increase will be according to the cubic equation. |
| 136 |
|
| 137 |
let cwnd_rtt_start = cubic.cwnd(); |
| 138 |
// cwnd_rtt_start has change, therefore calculate new time_increase (the time |
| 139 |
// between acks if they are ideally paced over a RTT). |
| 140 |
let time_increase = RTT / u32::try_from(cwnd_rtt_start / cubic.max_datagram_size()).unwrap(); |
| 141 |
let mut num_acks = 0; // count the number of acks. until cwnd is increased by cubic.max_datagram_size(). |
| 142 |
|
| 143 |
while cwnd_rtt_start == cubic.cwnd() { |
| 144 |
num_acks += 1; |
| 145 |
now += time_increase; |
| 146 |
ack_packet(&mut cubic, next_pn_ack, now); |
| 147 |
next_pn_ack += 1; |
| 148 |
next_pn_send = fill_cwnd(&mut cubic, next_pn_send, now); |
| 149 |
} |
| 150 |
|
| 151 |
// Make sure that the increase is not according to TCP equation, i.e., that it took |
| 152 |
// less than RTT / CUBIC_ALPHA. |
| 153 |
let expected_ack_tcp_increase = expected_tcp_acks(cwnd_rtt_start, cubic.max_datagram_size()); |
| 154 |
assert!(num_acks < expected_ack_tcp_increase); |
| 155 |
|
| 156 |
// This first increase after a TCP phase may be shorter than what it would take by a regular |
| 157 |
// cubic phase, because of the proper byte counting and the credit it already had before |
| 158 |
// entering this phase. Therefore We will perform another round and compare it to expected |
| 159 |
// increase using the cubic equation. |
| 160 |
|
| 161 |
let cwnd_rtt_start_after_tcp = cubic.cwnd(); |
| 162 |
let elapsed_time = now - start_time; |
| 163 |
|
| 164 |
// calculate new time_increase. |
| 165 |
let time_increase = |
| 166 |
RTT / u32::try_from(cwnd_rtt_start_after_tcp / cubic.max_datagram_size()).unwrap(); |
| 167 |
let mut num_acks2 = 0; // count the number of acks. until cwnd is increased by MAX_DATAGRAM_SIZE. |
| 168 |
|
| 169 |
while cwnd_rtt_start_after_tcp == cubic.cwnd() { |
| 170 |
num_acks2 += 1; |
| 171 |
now += time_increase; |
| 172 |
ack_packet(&mut cubic, next_pn_ack, now); |
| 173 |
next_pn_ack += 1; |
| 174 |
next_pn_send = fill_cwnd(&mut cubic, next_pn_send, now); |
| 175 |
} |
| 176 |
|
| 177 |
let expected_ack_tcp_increase2 = |
| 178 |
expected_tcp_acks(cwnd_rtt_start_after_tcp, cubic.max_datagram_size()); |
| 179 |
assert!(num_acks2 < expected_ack_tcp_increase2); |
| 180 |
|
| 181 |
// The time needed to increase cwnd by MAX_DATAGRAM_SIZE using the cubic equation will be |
| 182 |
// calculated from: W_cubic(elapsed_time + t_to_increase) - W_cubic(elapsed_time) = |
| 183 |
// MAX_DATAGRAM_SIZE => CUBIC_C * (elapsed_time + t_to_increase)^3 * MAX_DATAGRAM_SIZE + |
| 184 |
// CWND_INITIAL - CUBIC_C * elapsed_time^3 * MAX_DATAGRAM_SIZE + CWND_INITIAL = |
| 185 |
// MAX_DATAGRAM_SIZE => t_to_increase = cbrt((1 + CUBIC_C * elapsed_time^3) / CUBIC_C) - |
| 186 |
// elapsed_time (t_to_increase is in seconds) |
| 187 |
// number of ack needed is t_to_increase / time_increase. |
| 188 |
let expected_ack_cubic_increase = |
| 189 |
(((CUBIC_C.mul_add((elapsed_time).as_secs_f64().powi(3), 1.0) / CUBIC_C).cbrt() |
| 190 |
- elapsed_time.as_secs_f64()) |
| 191 |
/ time_increase.as_secs_f64()) |
| 192 |
.ceil() as u64; |
| 193 |
// num_acks is very close to the calculated value. The exact value is hard to calculate |
| 194 |
// because the proportional increase (i.e. curr_cwnd_f64 / (target - curr_cwnd_f64) * |
| 195 |
// MAX_DATAGRAM_SIZE_F64) and the byte counting. |
| 196 |
assert_eq!(num_acks2, expected_ack_cubic_increase + 2); |
| 197 |
} |
| 198 |
|
| 199 |
#[test] |
| 200 |
fn cubic_phase() { |
| 201 |
let mut cubic = ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU)); |
| 202 |
let cwnd_initial_f64 = convert_to_f64(cubic.cwnd_initial()); |
| 203 |
// Set last_max_cwnd to a higher number make sure that cc is the cubic phase (cwnd is calculated |
| 204 |
// by the cubic equation). |
| 205 |
cubic.set_last_max_cwnd(cwnd_initial_f64 * 10.0); |
| 206 |
// Set ssthresh to something small to make sure that cc is in the congection avoidance phase. |
| 207 |
cubic.set_ssthresh(1); |
| 208 |
let mut now = now(); |
| 209 |
let mut next_pn_send = 0; |
| 210 |
let mut next_pn_ack = 0; |
| 211 |
|
| 212 |
next_pn_send = fill_cwnd(&mut cubic, next_pn_send, now); |
| 213 |
|
| 214 |
let k = (cwnd_initial_f64.mul_add(10.0, -cwnd_initial_f64) |
| 215 |
/ CUBIC_C |
| 216 |
/ convert_to_f64(cubic.max_datagram_size())) |
| 217 |
.cbrt(); |
| 218 |
let epoch_start = now; |
| 219 |
|
| 220 |
// The number of RTT until W_max is reached. |
| 221 |
let num_rtts_w_max = (k / RTT.as_secs_f64()).round() as u64; |
| 222 |
for _ in 0..num_rtts_w_max { |
| 223 |
let cwnd_rtt_start = cubic.cwnd(); |
| 224 |
// Expected acks |
| 225 |
let acks = cwnd_rtt_start / cubic.max_datagram_size(); |
| 226 |
let time_increase = RTT / u32::try_from(acks).unwrap(); |
| 227 |
for _ in 0..acks { |
| 228 |
now += time_increase; |
| 229 |
ack_packet(&mut cubic, next_pn_ack, now); |
| 230 |
next_pn_ack += 1; |
| 231 |
next_pn_send = fill_cwnd(&mut cubic, next_pn_send, now); |
| 232 |
} |
| 233 |
|
| 234 |
let expected = (CUBIC_C * ((now - epoch_start).as_secs_f64() - k).powi(3)) |
| 235 |
.mul_add( |
| 236 |
convert_to_f64(cubic.max_datagram_size()), |
| 237 |
cwnd_initial_f64 * 10.0, |
| 238 |
) |
| 239 |
.round() as usize; |
| 240 |
|
| 241 |
assert_within(cubic.cwnd(), expected, cubic.max_datagram_size()); |
| 242 |
} |
| 243 |
assert_eq!(cubic.cwnd(), cubic.cwnd_initial() * 10); |
| 244 |
} |
| 245 |
|
| 246 |
fn assert_within<T: Sub<Output = T> + PartialOrd + Copy>(value: T, expected: T, margin: T) { |
| 247 |
if value >= expected { |
| 248 |
assert!(value - expected < margin); |
| 249 |
} else { |
| 250 |
assert!(expected - value < margin); |
| 251 |
} |
| 252 |
} |
| 253 |
|
| 254 |
#[test] |
| 255 |
fn congestion_event_slow_start() { |
| 256 |
let mut cubic = ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU)); |
| 257 |
|
| 258 |
_ = fill_cwnd(&mut cubic, 0, now()); |
| 259 |
ack_packet(&mut cubic, 0, now()); |
| 260 |
|
| 261 |
assert_within(cubic.last_max_cwnd(), 0.0, f64::EPSILON); |
| 262 |
|
| 263 |
// cwnd is increased by 1 in slow start phase, after an ack. |
| 264 |
assert_eq!( |
| 265 |
cubic.cwnd(), |
| 266 |
cubic.cwnd_initial() + cubic.max_datagram_size() |
| 267 |
); |
| 268 |
|
| 269 |
// Trigger a congestion_event in slow start phase |
| 270 |
packet_lost(&mut cubic, 1); |
| 271 |
|
| 272 |
// last_max_cwnd is equal to cwnd before decrease. |
| 273 |
let cwnd_initial_f64 = convert_to_f64(cubic.cwnd_initial()); |
| 274 |
assert_within( |
| 275 |
cubic.last_max_cwnd(), |
| 276 |
cwnd_initial_f64 + convert_to_f64(cubic.max_datagram_size()), |
| 277 |
f64::EPSILON, |
| 278 |
); |
| 279 |
assert_eq!( |
| 280 |
cubic.cwnd(), |
| 281 |
cwnd_after_loss_slow_start(cubic.cwnd_initial(), cubic.max_datagram_size()) |
| 282 |
); |
| 283 |
} |
| 284 |
|
| 285 |
#[test] |
| 286 |
fn congestion_event_congestion_avoidance() { |
| 287 |
let mut cubic = ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU)); |
| 288 |
|
| 289 |
// Set ssthresh to something small to make sure that cc is in the congection avoidance phase. |
| 290 |
cubic.set_ssthresh(1); |
| 291 |
|
| 292 |
// Set last_max_cwnd to something smaller than cwnd so that the fast convergence is not |
| 293 |
// triggered. |
| 294 |
cubic.set_last_max_cwnd(3.0 * convert_to_f64(cubic.max_datagram_size())); |
| 295 |
|
| 296 |
_ = fill_cwnd(&mut cubic, 0, now()); |
| 297 |
ack_packet(&mut cubic, 0, now()); |
| 298 |
|
| 299 |
assert_eq!(cubic.cwnd(), cubic.cwnd_initial()); |
| 300 |
|
| 301 |
// Trigger a congestion_event in slow start phase |
| 302 |
packet_lost(&mut cubic, 1); |
| 303 |
|
| 304 |
let cwnd_initial_f64 = convert_to_f64(cubic.cwnd_initial()); |
| 305 |
assert_within(cubic.last_max_cwnd(), cwnd_initial_f64, f64::EPSILON); |
| 306 |
assert_eq!(cubic.cwnd(), cwnd_after_loss(cubic.cwnd_initial())); |
| 307 |
} |
| 308 |
|
| 309 |
#[test] |
| 310 |
fn congestion_event_congestion_avoidance_2() { |
| 311 |
let mut cubic = ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU)); |
| 312 |
|
| 313 |
// Set ssthresh to something small to make sure that cc is in the congection avoidance phase. |
| 314 |
cubic.set_ssthresh(1); |
| 315 |
|
| 316 |
// Set last_max_cwnd to something higher than cwnd so that the fast convergence is triggered. |
| 317 |
let cwnd_initial_f64 = convert_to_f64(cubic.cwnd_initial()); |
| 318 |
cubic.set_last_max_cwnd(cwnd_initial_f64 * 10.0); |
| 319 |
|
| 320 |
_ = fill_cwnd(&mut cubic, 0, now()); |
| 321 |
ack_packet(&mut cubic, 0, now()); |
| 322 |
|
| 323 |
assert_within(cubic.last_max_cwnd(), cwnd_initial_f64 * 10.0, f64::EPSILON); |
| 324 |
assert_eq!(cubic.cwnd(), cubic.cwnd_initial()); |
| 325 |
|
| 326 |
// Trigger a congestion_event. |
| 327 |
packet_lost(&mut cubic, 1); |
| 328 |
|
| 329 |
assert_within( |
| 330 |
cubic.last_max_cwnd(), |
| 331 |
cwnd_initial_f64 * CUBIC_FAST_CONVERGENCE, |
| 332 |
f64::EPSILON, |
| 333 |
); |
| 334 |
assert_eq!(cubic.cwnd(), cwnd_after_loss(cubic.cwnd_initial())); |
| 335 |
} |
| 336 |
|
| 337 |
#[test] |
| 338 |
fn congestion_event_congestion_avoidance_no_overflow() { |
| 339 |
const PTO: Duration = Duration::from_millis(120); |
| 340 |
let mut cubic = ClassicCongestionControl::new(Cubic::default(), Pmtud::new(IP_ADDR, MTU)); |
| 341 |
|
| 342 |
// Set ssthresh to something small to make sure that cc is in the congection avoidance phase. |
| 343 |
cubic.set_ssthresh(1); |
| 344 |
|
| 345 |
// Set last_max_cwnd to something higher than cwnd so that the fast convergence is triggered. |
| 346 |
let cwnd_initial_f64 = convert_to_f64(cubic.cwnd_initial()); |
| 347 |
cubic.set_last_max_cwnd(cwnd_initial_f64 * 10.0); |
| 348 |
|
| 349 |
_ = fill_cwnd(&mut cubic, 0, now()); |
| 350 |
ack_packet(&mut cubic, 1, now()); |
| 351 |
|
| 352 |
assert_within(cubic.last_max_cwnd(), cwnd_initial_f64 * 10.0, f64::EPSILON); |
| 353 |
assert_eq!(cubic.cwnd(), cubic.cwnd_initial()); |
| 354 |
|
| 355 |
// Now ack packet that was send earlier. |
| 356 |
ack_packet(&mut cubic, 0, now().checked_sub(PTO).unwrap()); |
| 357 |
} |