use crate::report::WindowSummary;
const SILENCE_WEIGHT: i64 = 5;
const LOSS_EVIDENCE: i64 = 12 * SILENCE_WEIGHT;
#[non_exhaustive]
#[derive(Debug, Clone, Copy)]
pub struct WindowLimits {
pub initial: u32,
pub floor: u32,
pub ceiling: u32,
pub slow_start_threshold: u32,
}
impl WindowLimits {
pub const fn new(initial: u32, floor: u32, ceiling: u32, slow_start_threshold: u32) -> Self {
Self {
initial,
floor,
ceiling,
slow_start_threshold,
}
}
pub const fn fixed(capacity: u32) -> Self {
Self {
initial: capacity,
floor: capacity,
ceiling: capacity,
slow_start_threshold: capacity,
}
}
const fn adaptive(&self) -> bool {
self.floor < self.ceiling
}
}
#[derive(Debug, Clone)]
pub struct CongestionWindow {
limits: WindowLimits,
window: f64,
threshold: f64,
in_flight: u32,
since_reduction: u32,
epoch: u32,
peak: usize,
reductions: u32,
silence_evidence: i64,
admission_over: bool,
}
impl CongestionWindow {
pub fn new(limits: WindowLimits) -> Self {
let window = f64::from(
limits
.initial
.clamp(limits.floor, limits.ceiling.max(limits.floor)),
);
Self {
limits,
window,
threshold: f64::from(limits.slow_start_threshold),
in_flight: 0,
since_reduction: 0,
epoch: 0,
peak: window as usize,
reductions: 0,
silence_evidence: 0,
admission_over: false,
}
}
pub fn capacity(&self) -> usize {
(self.window as usize).max(1)
}
pub fn in_flight(&self) -> usize {
self.in_flight as usize
}
pub fn has_room(&self) -> bool {
self.in_flight() < self.capacity()
}
pub fn record_send(&mut self) {
self.in_flight = self.in_flight.saturating_add(1);
self.since_reduction = self.since_reduction.saturating_add(1);
}
pub fn record_resend(&mut self) {
self.since_reduction = self.since_reduction.saturating_add(1);
}
pub fn release(&mut self) {
self.in_flight = self.in_flight.saturating_sub(1);
}
pub(crate) fn record_answer(&mut self) {
self.observe_first_outcome(false);
self.record_progress();
}
pub(crate) fn record_loss(&mut self) {
if !self.admission_over {
self.record_congestion();
}
}
pub(crate) fn record_ambiguous_silence(&mut self) {
if !self.admission_over && self.observe_first_outcome(true) > LOSS_EVIDENCE {
self.record_congestion();
}
}
pub(crate) fn stop_admitting(&mut self) {
self.admission_over = true;
}
fn observe_first_outcome(&mut self, silent: bool) -> i64 {
let step = if silent { SILENCE_WEIGHT } else { -1 };
self.silence_evidence = (self.silence_evidence + step).max(self.credit_in_flight());
self.silence_evidence
}
fn credit_in_flight(&self) -> i64 {
-SILENCE_WEIGHT * i64::from(self.in_flight)
}
pub fn record_progress(&mut self) {
if !self.limits.adaptive() {
return;
}
let step = if self.window < self.threshold {
1.0
} else {
1.0 / self.window
};
self.window = (self.window + step).min(f64::from(self.limits.ceiling));
self.peak = self.peak.max(self.capacity());
}
pub fn record_congestion(&mut self) {
if !self.limits.adaptive() || self.since_reduction < self.epoch {
return;
}
self.threshold = (self.window / 2.0).max(f64::from(self.limits.floor));
self.window = self.threshold;
self.epoch = self.capacity() as u32;
self.since_reduction = 0;
self.reductions = self.reductions.saturating_add(1);
self.silence_evidence = self.credit_in_flight();
}
pub fn release_all(&mut self) {
self.in_flight = 0;
}
pub fn summary(&self) -> WindowSummary {
WindowSummary {
capacity: self.capacity(),
peak: self.peak,
reductions: self.reductions,
adaptive: self.limits.adaptive(),
at_floor: self.limits.adaptive() && self.capacity() <= self.limits.floor as usize,
}
}
}
#[cfg(test)]
mod tests {
#[test]
fn crossed_bounds_freeze_the_window_rather_than_panicking() {
let window = CongestionWindow::new(WindowLimits::new(10, 100, 50, 20));
assert_eq!(window.capacity(), 100, "the floor wins");
assert!(
!window.summary().adaptive,
"and a range with nothing in it cannot move"
);
}
#[test]
fn a_frozen_window_neither_grows_nor_cuts() {
let mut window = CongestionWindow::new(WindowLimits::new(10, 100, 50, 20));
let before = window.capacity();
window.record_send();
window.record_progress();
window.record_congestion();
assert_eq!(window.capacity(), before);
assert_eq!(window.summary().reductions, 0);
}
use super::*;
fn limits() -> WindowLimits {
WindowLimits::new(16, 4, 512, 64)
}
#[test]
fn slow_start_doubles_the_window_every_round_trip() {
let mut window = CongestionWindow::new(limits());
assert_eq!(window.capacity(), 16);
for _ in 0..16 {
window.record_progress();
}
assert_eq!(window.capacity(), 32);
for _ in 0..32 {
window.record_progress();
}
assert_eq!(window.capacity(), 64);
}
#[test]
fn past_the_threshold_the_window_grows_by_one_per_round_trip() {
let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 4096, 64));
assert_eq!(window.capacity(), 64);
for _ in 0..(8 * 64) {
window.record_progress();
}
assert_eq!(
window.capacity(),
71,
"eight round trips of linear growth, less the rounding that adding \
one over a window at a time costs"
);
}
#[test]
fn one_overloaded_moment_cuts_the_window_once_and_not_fifty_times() {
let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 512));
assert_eq!(window.capacity(), 64);
for _ in 0..50 {
window.record_congestion();
}
assert_eq!(window.capacity(), 32, "halved, and only once");
assert_eq!(window.summary().reductions, 1);
}
#[test]
fn a_second_window_of_probes_earns_a_second_reduction() {
let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 512));
window.record_congestion();
assert_eq!(window.capacity(), 32);
for _ in 0..32 {
window.record_send();
}
window.record_congestion();
assert_eq!(window.capacity(), 16);
assert_eq!(window.summary().reductions, 2);
}
#[test]
fn reduction_stops_at_the_floor() {
let mut window = CongestionWindow::new(WindowLimits::new(64, 8, 512, 512));
for _ in 0..20 {
window.record_congestion();
for _ in 0..64 {
window.record_send();
}
}
assert_eq!(window.capacity(), 8);
}
#[test]
fn growth_stops_at_the_ceiling() {
let mut window = CongestionWindow::new(WindowLimits::new(16, 4, 32, 1024));
for _ in 0..1000 {
window.record_progress();
}
assert_eq!(window.capacity(), 32);
assert_eq!(window.summary().peak, 32);
}
#[test]
fn silence_frees_the_slot_it_was_holding() {
let mut window = CongestionWindow::new(WindowLimits::new(4, 2, 512, 512));
for _ in 0..4 {
window.record_send();
}
assert!(!window.has_room(), "the window is full of open questions");
window.release();
window.record_progress();
assert!(
window.has_room(),
"and one of them has now been answered by silence"
);
assert!(
window.capacity() > 4,
"which is not congestion, so the window opens rather than closing"
);
}
#[test]
fn a_retry_costs_no_slot() {
let mut window = CongestionWindow::new(WindowLimits::new(4, 2, 512, 512));
window.record_send();
window.release();
assert_eq!(window.in_flight(), 0);
window.record_resend();
assert_eq!(window.in_flight(), 0, "the slot went back at the timeout");
}
#[test]
fn a_recovery_does_not_free_a_second_slot() {
let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 512));
window.record_send();
window.release();
window.record_resend();
window.record_congestion();
assert_eq!(window.in_flight(), 0);
}
#[test]
fn a_fixed_window_ignores_every_signal() {
let mut window = CongestionWindow::new(WindowLimits::fixed(64));
for _ in 0..100 {
window.record_progress();
window.record_congestion();
window.record_send();
}
assert_eq!(window.capacity(), 64);
assert_eq!(window.summary().reductions, 0);
assert!(!window.summary().adaptive);
}
#[test]
fn an_occasional_ambiguous_silence_among_answers_moves_nothing() {
let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 64));
for outcome in 0..(64 * 20) {
if outcome % 20 == 0 {
window.record_ambiguous_silence();
} else {
window.record_answer();
}
}
assert_eq!(window.summary().reductions, 0, "one in twenty is not loss");
}
#[test]
fn a_tenth_of_first_outcomes_silent_is_not_loss() {
let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 64));
let mut state: u64 = 0x2545_f491_4f6c_dd1d;
for _ in 0..(64 * 50) {
state = state
.wrapping_mul(6_364_136_223_846_793_005)
.wrapping_add(1_442_695_040_888_963_407);
if (state >> 33).is_multiple_of(10) {
window.record_ambiguous_silence();
} else {
window.record_answer();
}
}
assert_eq!(window.summary().reductions, 0, "one in ten is not loss");
}
#[test]
fn silence_heard_bunched_behind_its_answers_is_not_loss() {
let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 64));
for round in 1..=64u32 {
for _ in 0..64 {
window.record_send();
}
for _ in 0..58 {
window.release();
window.record_answer();
}
if round.is_multiple_of(8) {
for _ in 0..(6 * 8) {
window.release();
window.record_ambiguous_silence();
}
}
}
assert_eq!(window.summary().reductions, 0, "{:?}", window.summary());
}
#[test]
fn ambiguous_silence_at_a_share_of_loss_cuts_the_window() {
let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 64));
for round in 1..=16u32 {
for _ in 0..64 {
window.record_send();
}
for _ in 0..48 {
window.release();
window.record_answer();
}
if round.is_multiple_of(4) {
for _ in 0..(16 * 4) {
window.release();
window.record_ambiguous_silence();
}
}
}
assert!(window.summary().reductions > 0, "one in four is loss");
assert!(window.capacity() < 64);
}
#[test]
fn silence_left_in_flight_after_the_last_admission_is_not_weighed_as_loss() {
let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 64));
for _ in 0..(64 * 4) {
window.record_answer();
}
window.stop_admitting();
for _ in 0..64 {
window.record_ambiguous_silence();
}
assert_eq!(window.summary().reductions, 0);
}
#[test]
fn a_dropped_probe_heard_after_the_last_admission_does_not_cut() {
let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 64));
window.stop_admitting();
window.record_loss();
assert_eq!(window.summary().reductions, 0, "nothing left to pace");
let mut admitting = CongestionWindow::new(WindowLimits::new(64, 4, 512, 64));
admitting.record_loss();
assert_eq!(
admitting.summary().reductions,
1,
"while admitting, it cuts"
);
}
#[test]
fn a_window_that_was_cut_climbs_back_slowly_rather_than_doubling() {
let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 512));
window.record_congestion();
assert_eq!(window.capacity(), 32);
for _ in 0..(2 * 32) {
window.record_progress();
}
assert_eq!(
window.capacity(),
33,
"two round trips buy two probes, not two doublings"
);
}
}