Debian Codegraph @

third_party/rust/neqo-transport/src/pace.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 // 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 }