Debian Codegraph @

third_party/rust/neqo-transport/src/rtt.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 // Tracking of sent packets and detecting their loss.
8
9 use std::{
10 cmp::{max, min},
11 time::{Duration, Instant},
12 };
13
14 use neqo_common::{qlog::NeqoQlog, qtrace};
15
16 use crate::{
17 ackrate::{AckRate, PeerAckDelay},
18 packet::PacketBuilder,
19 qlog::{self, QlogMetric},
20 recovery::RecoveryToken,
21 stats::FrameStats,
22 };
23
24 /// The smallest time that the system timer (via `sleep()`, `nanosleep()`,
25 /// `select()`, or similar) can reliably deliver; see `neqo_common::hrtime`.
26 pub const GRANULARITY: Duration = Duration::from_millis(1);
27 // Defined in -recovery 6.2 as 333ms but using lower value.
28 pub const INITIAL_RTT: Duration = Duration::from_millis(100);
29
30 /// The source of the RTT measurement.
31 #[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
32 pub enum RttSource {
33 /// RTT guess from a retry or dropping a packet number space.
34 Guesstimate,
35 /// Ack on an unconfirmed connection.
36 Ack,
37 /// Ack on a confirmed connection.
38 AckConfirmed,
39 }
40
41 #[derive(Debug)]
42 pub struct RttEstimate {
43 first_sample_time: Option<Instant>,
44 latest_rtt: Duration,
45 smoothed_rtt: Duration,
46 rttvar: Duration,
47 min_rtt: Duration,
48 ack_delay: PeerAckDelay,
49 best_source: RttSource,
50 }
51
52 impl RttEstimate {
53 fn init(&mut self, rtt: Duration) {
54 // Only allow this when there are no samples.
55 debug_assert!(self.first_sample_time.is_none());
56 self.latest_rtt = rtt;
57 self.min_rtt = rtt;
58 self.smoothed_rtt = rtt;
59 self.rttvar = rtt / 2;
60 }
61
62 #[cfg(test)]
63 pub fn from_duration(rtt: Duration) -> Self {
64 Self {
65 first_sample_time: None,
66 latest_rtt: rtt,
67 smoothed_rtt: rtt,
68 rttvar: Duration::from_millis(0),
69 min_rtt: rtt,
70 ack_delay: PeerAckDelay::default(),
71 best_source: RttSource::Ack,
72 }
73 }
74
75 pub fn set_initial(&mut self, rtt: Duration) {
76 qtrace!("initial RTT={rtt:?}");
77 if rtt >= GRANULARITY {
78 // Ignore if the value is too small.
79 self.init(rtt);
80 }
81 }
82
83 /// For a new path, prime the RTT based on the state of another path.
84 pub fn prime_rtt(&mut self, other: &Self) {
85 self.set_initial(other.smoothed_rtt + other.rttvar);
86 self.ack_delay = other.ack_delay.clone();
87 }
88
89 pub fn set_ack_delay(&mut self, ack_delay: PeerAckDelay) {
90 self.ack_delay = ack_delay;
91 }
92
93 pub fn update_ack_delay(&mut self, cwnd: usize, mtu: usize) {
94 self.ack_delay.update(cwnd, mtu, self.smoothed_rtt);
95 }
96
97 pub fn is_guesstimate(&self) -> bool {
98 self.best_source == RttSource::Guesstimate
99 }
100
101 pub fn update(
102 &mut self,
103 qlog: &NeqoQlog,
104 mut rtt_sample: Duration,
105 ack_delay: Duration,
106 source: RttSource,
107 now: Instant,
108 ) {
109 debug_assert!(source >= self.best_source);
110 self.best_source = max(self.best_source, source);
111
112 // Limit ack delay by max_ack_delay if confirmed.
113 let mad = self.ack_delay.max();
114 let ack_delay = if self.best_source == RttSource::AckConfirmed && ack_delay > mad {
115 mad
116 } else {
117 ack_delay
118 };
119
120 // min_rtt ignores ack delay.
121 self.min_rtt = min(self.min_rtt, rtt_sample);
122 // Adjust for ack delay unless it goes below `min_rtt`.
123 if rtt_sample - self.min_rtt >= ack_delay {
124 rtt_sample -= ack_delay;
125 }
126
127 if self.first_sample_time.is_none() {
128 self.init(rtt_sample);
129 self.first_sample_time = Some(now);
130 } else {
131 // Calculate EWMA RTT (based on {{?RFC6298}}).
132 let rttvar_sample = self.smoothed_rtt.abs_diff(rtt_sample);
133
134 self.latest_rtt = rtt_sample;
135 self.rttvar = (self.rttvar * 3 + rttvar_sample) / 4;
136 self.smoothed_rtt = (self.smoothed_rtt * 7 + rtt_sample) / 8;
137 }
138 qtrace!(
139 "RTT latest={:?} -> estimate={:?}~{:?}",
140 self.latest_rtt,
141 self.smoothed_rtt,
142 self.rttvar
143 );
144 qlog::metrics_updated(
145 qlog,
146 &[
147 QlogMetric::LatestRtt(self.latest_rtt),
148 QlogMetric::MinRtt(self.min_rtt),
149 QlogMetric::SmoothedRtt(self.smoothed_rtt),
150 QlogMetric::RttVariance(self.rttvar),
151 ],
152 now,
153 );
154 }
155
156 /// Get the estimated value.
157 pub const fn estimate(&self) -> Duration {
158 self.smoothed_rtt
159 }
160
161 pub fn pto(&self, confirmed: bool) -> Duration {
162 let mut t = self.estimate() + max(4 * self.rttvar, GRANULARITY);
163 if confirmed {
164 t += self.ack_delay.max();
165 }
166 t
167 }
168
169 /// Calculate the loss delay based on the current estimate and the last
170 /// RTT measurement received.
171 pub fn loss_delay(&self) -> Duration {
172 // kTimeThreshold = 9/8
173 // loss_delay = kTimeThreshold * max(latest_rtt, smoothed_rtt)
174 // loss_delay = max(loss_delay, kGranularity)
175 let rtt = max(self.latest_rtt, self.smoothed_rtt);
176 max(rtt * 9 / 8, GRANULARITY)
177 }
178
179 pub const fn first_sample_time(&self) -> Option<Instant> {
180 self.first_sample_time
181 }
182
183 #[cfg(test)]
184 pub const fn latest(&self) -> Duration {
185 self.latest_rtt
186 }
187
188 pub const fn rttvar(&self) -> Duration {
189 self.rttvar
190 }
191
192 pub const fn minimum(&self) -> Duration {
193 self.min_rtt
194 }
195
196 pub fn write_frames(
197 &mut self,
198 builder: &mut PacketBuilder,
199 tokens: &mut Vec<RecoveryToken>,
200 stats: &mut FrameStats,
201 ) {
202 self.ack_delay.write_frames(builder, tokens, stats);
203 }
204
205 pub fn frame_lost(&mut self, lost: &AckRate) {
206 self.ack_delay.frame_lost(lost);
207 }
208
209 pub fn frame_acked(&mut self, acked: &AckRate) {
210 self.ack_delay.frame_acked(acked);
211 }
212 }
213
214 impl Default for RttEstimate {
215 fn default() -> Self {
216 Self {
217 first_sample_time: None,
218 latest_rtt: INITIAL_RTT,
219 smoothed_rtt: INITIAL_RTT,
220 rttvar: INITIAL_RTT / 2,
221 min_rtt: INITIAL_RTT,
222 ack_delay: PeerAckDelay::default(),
223 best_source: RttSource::Guesstimate,
224 }
225 }
226 }