lib/quic/src/connection/recovery/rtt.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 /// One millisecond establishes how fine the timing rules are willing to be, so the loss delay and
4 /// the probe wait are each held at or above it.
5 pub const granularity_ns: u64 = std.time.ns_per_ms;
6
7 /// A connection assumes the path costs 333 milliseconds until it measures, so the first probe
8 /// deadline rests on this value before any acknowledgment arrives. A fresh estimator opens with
9 /// that duration as its smoothed value and half of it as its variation.
10 pub const initial_ns: u64 = 333 * std.time.ns_per_ms;
11
12 /// Holds what one connection has learned about how long the path takes, so the loss and probe rules
13 /// can read its fields once `Connection.roundTrip` hands one back. The struct keeps the most recent
14 /// measurement, the smallest seen, a smoothed value, a measure of spread, and whether anything has
15 /// been measured yet.
16 pub const Estimator = struct {
17 latest_ns: u64 = 0,
18 minimum_ns: u64 = 0,
19 smoothed_ns: u64 = initial_ns,
20 variation_ns: u64 = initial_ns / 2,
21 sampled: bool = false,
22
23 /// Folds one fresh measurement into what the connection already knows for each ACK that settles
24 /// a packet the peer owed an answer to. The very first measurement seeds the smallest and the
25 /// smoothed value with itself, and the spread with half of itself. Each later measurement moves
26 /// the smoothed value by an eighth and the spread by a quarter, so a single odd measurement
27 /// cannot swing either far. The caller settles the peer's delay before it calls, so the figure
28 /// arriving here has already met the cap and been reduced to zero when the space demands it.
29 /// That delay comes off the measurement only while the answer stays at or above the smallest
30 /// seen. Each product and sum holds at the maximum once it reaches it.
31 pub fn update(self: *Estimator, latest_ns: u64, delay_ns: u64) void {
32 std.debug.assert(latest_ns != 0);
33 self.latest_ns = latest_ns;
34 if (!self.sampled) {
35 self.sampled = true;
36 self.minimum_ns = latest_ns;
37 self.smoothed_ns = latest_ns;
38 self.variation_ns = latest_ns / 2;
39 return;
40 }
41 self.minimum_ns = @min(self.minimum_ns, latest_ns);
42 const adjusted_ns = adjusted(latest_ns, self.minimum_ns, delay_ns);
43 const deviation_ns = difference(self.smoothed_ns, adjusted_ns);
44 self.variation_ns = (self.variation_ns *| 3 +| deviation_ns) / 4;
45 self.smoothed_ns = (self.smoothed_ns *| 7 +| adjusted_ns) / 8;
46 }
47 };
48
49 /// Measures the gap between a packet going out and its answer coming back, so the connection can
50 /// turn one settled packet into a measurement. A clock that has not moved yields nothing to
51 /// measure, and the call offers none.
52 pub fn sample(sent_ns: u64, received_ns: u64) ?u64 {
53 if (received_ns <= sent_ns) return null;
54 return received_ns - sent_ns;
55 }
56
57 /// Turns one ACK frame's delay field into nanoseconds, because an ACK frame carries its delay
58 /// scaled by the sender's own exponent. The field counts microseconds shifted left by the peer's
59 /// exponent. A figure too large for 64 bits stops at the largest u64 value.
60 pub fn delayNs(encoded: u62, exponent: u5) u64 {
61 const microseconds = @as(u128, encoded) << exponent;
62 const nanoseconds = microseconds * std.time.ns_per_us;
63 return std.math.cast(u64, nanoseconds) orelse std.math.maxInt(u64);
64 }
65
66 /// Works out how much of the gap the peer says it spent before answering. The call settles the two
67 /// questions that decide whether an ACK's delay counts at all, so the caller hands the answer
68 /// straight to `update`. Initial and Handshake acknowledgments carry no delay field, and the caller
69 /// passes false to say so, so the call yields zero. A cap applies only after the handshake is
70 /// confirmed, so the caller passes none before then.
71 pub fn reportedDelayNs(reported: bool, encoded: u62, exponent: u5, maximum_ns: ?u64) u64 {
72 if (!reported) return 0;
73 const delay_ns = delayNs(encoded, exponent);
74 const maximum = maximum_ns orelse return delay_ns;
75 return @min(delay_ns, maximum);
76 }
77
78 /// Takes the peer's delay out of one measurement, so the floor it respects keeps the estimate above
79 /// what the path costs. The call refuses when doing so would push the answer under the smallest gap
80 /// ever seen, and leaves the measurement whole. A smallest and a delay whose sum runs over leave
81 /// the measurement whole as well.
82 fn adjusted(latest_ns: u64, minimum_ns: u64, delay_ns: u64) u64 {
83 const floor_ns = std.math.add(u64, minimum_ns, delay_ns) catch return latest_ns;
84 if (latest_ns < floor_ns) return latest_ns;
85 std.debug.assert(latest_ns >= delay_ns);
86 return latest_ns - delay_ns;
87 }
88
89 fn difference(left: u64, right: u64) u64 {
90 return if (left > right) left - right else right - left;
91 }
92
93 test "RFC 9002 section 5.3 the first sample seeds the smoothed estimate and variation" {
94 var estimator = Estimator{};
95 estimator.update(100 * std.time.ns_per_ms, 5 * std.time.ns_per_ms);
96 try std.testing.expect(estimator.sampled);
97 try std.testing.expectEqual(100 * std.time.ns_per_ms, estimator.latest_ns);
98 try std.testing.expectEqual(100 * std.time.ns_per_ms, estimator.minimum_ns);
99 try std.testing.expectEqual(100 * std.time.ns_per_ms, estimator.smoothed_ns);
100 try std.testing.expectEqual(50 * std.time.ns_per_ms, estimator.variation_ns);
101 }
102
103 test "RFC 9002 section 5.3 a later sample folds in at one eighth and one quarter" {
104 var estimator = Estimator{};
105 estimator.update(100 * std.time.ns_per_ms, 0);
106 estimator.update(200 * std.time.ns_per_ms, 0);
107 const smoothed = (100 * std.time.ns_per_ms * 7 + 200 * std.time.ns_per_ms) / 8;
108 const variation = (50 * std.time.ns_per_ms * 3 + 100 * std.time.ns_per_ms) / 4;
109 try std.testing.expectEqual(smoothed, estimator.smoothed_ns);
110 try std.testing.expectEqual(variation, estimator.variation_ns);
111 try std.testing.expectEqual(100 * std.time.ns_per_ms, estimator.minimum_ns);
112 }
113
114 test "RFC 9002 section 5.3 acknowledgment delay lowers a sample above the minimum" {
115 var estimator = Estimator{};
116 estimator.update(100 * std.time.ns_per_ms, 0);
117 estimator.update(150 * std.time.ns_per_ms, 20 * std.time.ns_per_ms);
118 const adjusted_ns = 130 * std.time.ns_per_ms;
119 const smoothed = (100 * std.time.ns_per_ms * 7 + adjusted_ns) / 8;
120 try std.testing.expectEqual(smoothed, estimator.smoothed_ns);
121 }
122
123 test "RFC 9002 section 5.3 acknowledgment delay never lowers a sample below the minimum" {
124 var estimator = Estimator{};
125 estimator.update(100 * std.time.ns_per_ms, 0);
126 estimator.update(110 * std.time.ns_per_ms, 50 * std.time.ns_per_ms);
127 const smoothed = (100 * std.time.ns_per_ms * 7 + 110 * std.time.ns_per_ms) / 8;
128 try std.testing.expectEqual(smoothed, estimator.smoothed_ns);
129 }
130
131 test "RFC 9002 section 5.1 a sample needs the clock to advance" {
132 try std.testing.expectEqual(@as(?u64, null), sample(10, 10));
133 try std.testing.expectEqual(@as(?u64, null), sample(11, 10));
134 try std.testing.expectEqual(@as(?u64, 1), sample(10, 11));
135 try std.testing.expectEqual(@as(?u64, std.math.maxInt(u64)), sample(0, std.math.maxInt(u64)));
136 }
137
138 test "RFC 9000 section 19.3 the delay field scales by the peer exponent and saturates" {
139 try std.testing.expectEqual(@as(u64, 8_000), delayNs(1, 3));
140 try std.testing.expectEqual(@as(u64, 0), delayNs(0, 20));
141 try std.testing.expectEqual(@as(u64, std.math.maxInt(u64)), delayNs(std.math.maxInt(u62), 20));
142 }
143
144 test "RFC 9002 section 5.3 Initial and Handshake acknowledgments report no delay" {
145 try std.testing.expectEqual(@as(u64, 0), reportedDelayNs(false, 12_500, 3, null));
146 try std.testing.expectEqual(@as(u64, 0), reportedDelayNs(false, 12_500, 3, 1));
147 }
148
149 test "RFC 9002 section 5.3 max_ack_delay caps the reported delay only once confirmed" {
150 const reported_ns = 100 * std.time.ns_per_ms;
151 const maximum_ns = 25 * std.time.ns_per_ms;
152 try std.testing.expectEqual(reported_ns, reportedDelayNs(true, 12_500, 3, null));
153 try std.testing.expectEqual(maximum_ns, reportedDelayNs(true, 12_500, 3, maximum_ns));
154 try std.testing.expectEqual(@as(u64, 8_000), reportedDelayNs(true, 1, 3, maximum_ns));
155 }
156
157 test "RFC 9002 section 5.3 an extreme sample leaves the estimate total" {
158 var estimator = Estimator{};
159 estimator.update(std.math.maxInt(u64), 0);
160 estimator.update(std.math.maxInt(u64), std.math.maxInt(u64));
161 try std.testing.expect(estimator.smoothed_ns != 0);
162 try std.testing.expectEqual(@as(u64, std.math.maxInt(u64)), estimator.minimum_ns);
163 }