| 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 |
// Pacer |
| 8 |
|
| 9 |
use std::{ |
| 10 |
cmp::min, |
| 11 |
fmt::{self, Debug, Display, Formatter}, |
| 12 |
time::{Duration, Instant}, |
| 13 |
}; |
| 14 |
|
| 15 |
use neqo_common::qtrace; |
| 16 |
|
| 17 |
use crate::rtt::GRANULARITY; |
| 18 |
|
| 19 |
/// This value determines how much faster the pacer operates than the |
| 20 |
/// congestion window. |
| 21 |
/// |
| 22 |
/// A value of 1 would cause all packets to be spaced over the entire RTT, |
| 23 |
/// which is a little slow and might act as an additional restriction in |
| 24 |
/// the case the congestion controller increases the congestion window. |
| 25 |
/// This value spaces packets over half the congestion window, which matches |
| 26 |
/// our current congestion controller, which double the window every RTT. |
| 27 |
const PACER_SPEEDUP: usize = 2; |
| 28 |
|
| 29 |
/// A pacer that uses a leaky bucket. |
| 30 |
pub struct Pacer { |
| 31 |
/// Whether pacing is enabled. |
| 32 |
enabled: bool, |
| 33 |
/// The last update time. |
| 34 |
t: Instant, |
| 35 |
/// The maximum capacity, or burst size, in bytes. |
| 36 |
m: usize, |
| 37 |
/// The current capacity, in bytes. |
| 38 |
c: usize, |
| 39 |
/// The packet size or minimum capacity for sending, in bytes. |
| 40 |
p: usize, |
| 41 |
} |
| 42 |
|
| 43 |
impl Pacer { |
| 44 |
/// Create a new `Pacer`. This takes the current time, the maximum burst size, |
| 45 |
/// and the packet size. |
| 46 |
/// |
| 47 |
/// The value of `m` is the maximum capacity in bytes. `m` primes the pacer |
| 48 |
/// with credit and determines the burst size. `m` must not exceed |
| 49 |
/// the initial congestion window, but it should probably be lower. |
| 50 |
/// |
| 51 |
/// The value of `p` is the packet size in bytes, which determines the minimum |
| 52 |
/// credit needed before a packet is sent. This should be a substantial |
| 53 |
/// fraction of the maximum packet size, if not the packet size. |
| 54 |
pub fn new(enabled: bool, now: Instant, m: usize, p: usize) -> Self { |
| 55 |
assert!(m >= p, "maximum capacity has to be at least one packet"); |
| 56 |
Self { |
| 57 |
enabled, |
| 58 |
t: now, |
| 59 |
m, |
| 60 |
c: m, |
| 61 |
p, |
| 62 |
} |
| 63 |
} |
| 64 |
|
| 65 |
pub const fn mtu(&self) -> usize { |
| 66 |
self.p |
| 67 |
} |
| 68 |
|
| 69 |
pub fn set_mtu(&mut self, mtu: usize) { |
| 70 |
self.p = mtu; |
| 71 |
} |
| 72 |
|
| 73 |
/// Determine when the next packet will be available based on the provided RTT |
| 74 |
/// and congestion window. This doesn't update state. |
| 75 |
/// This returns a time, which could be in the past (this object doesn't know what |
| 76 |
/// the current time is). |
| 77 |
pub fn next(&self, rtt: Duration, cwnd: usize) -> Instant { |
| 78 |
if self.c >= self.p { |
| 79 |
qtrace!("[{self}] next {cwnd}/{rtt:?} no wait = {:?}", self.t); |
| 80 |
return self.t; |
| 81 |
} |
| 82 |
|
| 83 |
// This is the inverse of the function in `spend`: |
| 84 |
// self.t + rtt * (self.p - self.c) / (PACER_SPEEDUP * cwnd) |
| 85 |
let r = rtt.as_nanos(); |
| 86 |
let d = r.saturating_mul(u128::try_from(self.p - self.c).expect("usize fits into u128")); |
| 87 |
let add = d / u128::try_from(cwnd * PACER_SPEEDUP).expect("usize fits into u128"); |
| 88 |
let w = u64::try_from(add).map(Duration::from_nanos).unwrap_or(rtt); |
| 89 |
|
| 90 |
// If the increment is below the timer granularity, send immediately. |
| 91 |
if w < GRANULARITY { |
| 92 |
qtrace!("[{self}] next {cwnd}/{rtt:?} below granularity ({w:?})",); |
| 93 |
return self.t; |
| 94 |
} |
| 95 |
|
| 96 |
let nxt = self.t + w; |
| 97 |
qtrace!("[{self}] next {cwnd}/{rtt:?} wait {w:?} = {nxt:?}"); |
| 98 |
nxt |
| 99 |
} |
| 100 |
|
| 101 |
/// Spend credit. This cannot fail; users of this API are expected to call |
| 102 |
/// `next()` to determine when to spend. This takes the current time (`now`), |
| 103 |
/// an estimate of the round trip time (`rtt`), the estimated congestion |
| 104 |
/// window (`cwnd`), and the number of bytes that were sent (`count`). |
| 105 |
pub fn spend(&mut self, now: Instant, rtt: Duration, cwnd: usize, count: usize) { |
| 106 |
if !self.enabled { |
| 107 |
self.t = now; |
| 108 |
return; |
| 109 |
} |
| 110 |
|
| 111 |
qtrace!("[{self}] spend {count} over {cwnd}, {rtt:?}"); |
| 112 |
// Increase the capacity by: |
| 113 |
// `(now - self.t) * PACER_SPEEDUP * cwnd / rtt` |
| 114 |
// That is, the elapsed fraction of the RTT times rate that data is added. |
| 115 |
let incr = now |
| 116 |
.saturating_duration_since(self.t) |
| 117 |
.as_nanos() |
| 118 |
.saturating_mul(u128::try_from(cwnd * PACER_SPEEDUP).expect("usize fits into u128")) |
| 119 |
.checked_div(rtt.as_nanos()) |
| 120 |
.and_then(|i| usize::try_from(i).ok()) |
| 121 |
.unwrap_or(self.m); |
| 122 |
|
| 123 |
// Add the capacity up to a limit of `self.m`, then subtract `count`. |
| 124 |
self.c = min(self.m, (self.c + incr).saturating_sub(count)); |
| 125 |
self.t = now; |
| 126 |
} |
| 127 |
} |
| 128 |
|
| 129 |
impl Display for Pacer { |
| 130 |
fn fmt(&self, f: &mut Formatter) -> fmt::Result { |
| 131 |
write!(f, "Pacer {}/{}", self.c, self.p) |
| 132 |
} |
| 133 |
} |
| 134 |
|
| 135 |
impl Debug for Pacer { |
| 136 |
fn fmt(&self, f: &mut Formatter) -> fmt::Result { |
| 137 |
write!(f, "Pacer@{:?} {}/{}..{}", self.t, self.c, self.p, self.m) |
| 138 |
} |
| 139 |
} |
| 140 |
|
| 141 |
#[cfg(test)] |
| 142 |
mod tests { |
| 143 |
use std::time::Duration; |
| 144 |
|
| 145 |
use test_fixture::now; |
| 146 |
|
| 147 |
use super::Pacer; |
| 148 |
|
| 149 |
const RTT: Duration = Duration::from_millis(1000); |
| 150 |
const PACKET: usize = 1000; |
| 151 |
const CWND: usize = PACKET * 10; |
| 152 |
|
| 153 |
#[test] |
| 154 |
fn even() { |
| 155 |
let n = now(); |
| 156 |
let mut p = Pacer::new(true, n, PACKET, PACKET); |
| 157 |
assert_eq!(p.next(RTT, CWND), n); |
| 158 |
p.spend(n, RTT, CWND, PACKET); |
| 159 |
assert_eq!(p.next(RTT, CWND), n + (RTT / 20)); |
| 160 |
} |
| 161 |
|
| 162 |
#[test] |
| 163 |
fn backwards_in_time() { |
| 164 |
let n = now(); |
| 165 |
let mut p = Pacer::new(true, n + RTT, PACKET, PACKET); |
| 166 |
assert_eq!(p.next(RTT, CWND), n + RTT); |
| 167 |
// Now spend some credit in the past using a time machine. |
| 168 |
p.spend(n, RTT, CWND, PACKET); |
| 169 |
assert_eq!(p.next(RTT, CWND), n + (RTT / 20)); |
| 170 |
} |
| 171 |
|
| 172 |
#[test] |
| 173 |
fn pacing_disabled() { |
| 174 |
let n = now(); |
| 175 |
let mut p = Pacer::new(false, n, PACKET, PACKET); |
| 176 |
assert_eq!(p.next(RTT, CWND), n); |
| 177 |
p.spend(n, RTT, CWND, PACKET); |
| 178 |
assert_eq!(p.next(RTT, CWND), n); |
| 179 |
} |
| 180 |
|
| 181 |
#[test] |
| 182 |
fn send_immediately_below_granularity() { |
| 183 |
const SHORT_RTT: Duration = Duration::from_millis(10); |
| 184 |
let n = now(); |
| 185 |
let mut p = Pacer::new(true, n, PACKET, PACKET); |
| 186 |
assert_eq!(p.next(SHORT_RTT, CWND), n); |
| 187 |
p.spend(n, SHORT_RTT, CWND, PACKET); |
| 188 |
assert_eq!( |
| 189 |
p.next(SHORT_RTT, CWND), |
| 190 |
n, |
| 191 |
"Expect packet to be sent immediately, instead of being paced below timer granularity" |
| 192 |
); |
| 193 |
} |
| 194 |
} |