1use super::{
8 params::{Algorithm, VegasParams},
9 rtt::RoundtripTimeEstimator,
10 CongestionControlAlgorithm, CongestionSignals, CongestionWindow, State,
11};
12use crate::Result;
13
14use tor_error::{error_report, internal};
15
16#[derive(Clone, Debug, Default)]
20pub(crate) struct BdpEstimator {
21 bdp: u32,
23}
24
25impl BdpEstimator {
26 fn get(&self) -> u32 {
28 self.bdp
29 }
30
31 fn update(
36 &mut self,
37 cwnd: &CongestionWindow,
38 rtt: &RoundtripTimeEstimator,
39 signals: &CongestionSignals,
40 ) {
41 if rtt.clock_stalled() {
43 self.bdp = if signals.channel_blocked {
44 cwnd.get()
47 .saturating_sub(signals.channel_outbound_size)
48 .max(cwnd.min())
49 } else {
50 cwnd.get()
51 };
52 } else {
53 let min_rtt_usec = rtt.min_rtt_usec().unwrap_or(u32::MAX);
59 let ewma_rtt_usec = rtt.ewma_rtt_usec().unwrap_or(u32::MAX);
60 self.bdp = cwnd
61 .get()
62 .saturating_mul(min_rtt_usec)
63 .saturating_div(ewma_rtt_usec);
64 }
65 }
66}
67
68#[derive(Clone, Debug)]
78pub(crate) struct Vegas {
79 params: VegasParams,
81 bdp: BdpEstimator,
84 cwnd: CongestionWindow,
87 num_cell_until_sendme: u32,
89 num_sendme_until_cwnd_update: u32,
92 num_sendme_per_cwnd: u32,
95 num_inflight: u32,
98 is_blocked_on_chan: bool,
102}
103
104impl Vegas {
105 pub(crate) fn new(params: VegasParams, state: &State, cwnd: CongestionWindow) -> Self {
107 Self {
108 params,
109 bdp: BdpEstimator::default(),
110 num_cell_until_sendme: cwnd.sendme_inc(),
111 num_inflight: 0,
112 num_sendme_per_cwnd: 0,
113 num_sendme_until_cwnd_update: cwnd.update_rate(state),
114 cwnd,
115 is_blocked_on_chan: false,
116 }
117 }
118}
119
120impl CongestionControlAlgorithm for Vegas {
121 fn uses_stream_sendme(&self) -> bool {
122 false
124 }
125 fn is_next_cell_sendme(&self) -> bool {
126 self.num_inflight % self.cwnd.sendme_inc() == 0
129 }
130
131 fn can_send(&self) -> bool {
132 self.num_inflight < self.cwnd.get()
133 }
134
135 fn cwnd(&self) -> Option<&CongestionWindow> {
136 Some(&self.cwnd)
137 }
138
139 fn sendme_received(
150 &mut self,
151 state: &mut State,
152 rtt: &mut RoundtripTimeEstimator,
153 signals: CongestionSignals,
154 ) -> Result<()> {
155 self.num_sendme_until_cwnd_update = self.num_sendme_until_cwnd_update.saturating_sub(1);
157 self.num_sendme_per_cwnd = self.num_sendme_per_cwnd.saturating_sub(1);
159
160 self.bdp.update(&self.cwnd, rtt, &signals);
167
168 if rtt.is_ready() {
171 if signals.channel_blocked {
172 if !self.is_blocked_on_chan {
175 self.num_sendme_until_cwnd_update = 0;
176 }
177 } else {
178 if self.is_blocked_on_chan {
181 self.num_sendme_until_cwnd_update = 0;
182 }
183 }
184 }
185 self.is_blocked_on_chan = signals.channel_blocked;
186
187 if !rtt.is_ready() && !self.is_blocked_on_chan {
189 debug_assert!(self.num_inflight >= self.cwnd.sendme_inc());
193 self.num_inflight = self.num_inflight.saturating_sub(self.cwnd.sendme_inc());
194 return Ok(());
195 }
196
197 let queue_use = self.cwnd.get().saturating_sub(self.bdp.get());
200
201 self.cwnd.eval_fullness(
203 self.num_inflight,
204 self.params.cwnd_full_gap(),
205 self.params.cwnd_full_min_pct().as_percent(),
206 );
207
208 if state.in_slow_start() {
210 if queue_use < self.params.cell_in_queue_params().gamma() && !self.is_blocked_on_chan {
211 if self.cwnd.is_full() {
213 let inc = self
215 .cwnd
216 .rfc3742_ss_inc(self.params.cell_in_queue_params().ss_cwnd_cap());
217
218 if (inc * self.cwnd.sendme_per_cwnd())
221 <= (self.cwnd.increment() * self.cwnd.increment_rate())
222 {
223 *state = State::Steady;
224 }
225 }
226 } else {
227 self.cwnd
229 .set(self.bdp.get() + self.params.cell_in_queue_params().gamma());
230 *state = State::Steady;
232 }
233
234 if self.cwnd.get() >= self.params.ss_cwnd_max() {
236 self.cwnd.set(self.params.ss_cwnd_max());
237 *state = State::Steady;
238 }
239 } else if self.num_sendme_until_cwnd_update == 0 {
240 if queue_use > self.params.cell_in_queue_params().delta() {
242 self.cwnd.set(
244 self.bdp.get() + self.params.cell_in_queue_params().delta()
245 - self.cwnd.increment(),
246 );
247 } else if queue_use > self.params.cell_in_queue_params().beta()
248 || self.is_blocked_on_chan
249 {
250 self.cwnd.dec();
252 } else if self.cwnd.is_full() && queue_use < self.params.cell_in_queue_params().alpha()
253 {
254 self.cwnd.inc();
256 }
257 }
258
259 if self.num_sendme_until_cwnd_update == 0 {
261 self.num_sendme_until_cwnd_update = self.cwnd.update_rate(state);
262 }
263 if self.num_sendme_per_cwnd == 0 {
264 self.num_sendme_per_cwnd = self.cwnd.sendme_per_cwnd();
265 }
266
267 if self.params.cwnd_full_per_cwnd() != 0 {
269 if self.num_sendme_per_cwnd == self.cwnd.sendme_per_cwnd() {
270 self.cwnd.reset_full();
271 }
272 } else if self.num_sendme_until_cwnd_update == self.cwnd.update_rate(state) {
273 self.cwnd.reset_full();
274 }
275
276 self.num_inflight = self.num_inflight.saturating_sub(self.cwnd.sendme_inc());
278 Ok(())
279 }
280
281 fn sendme_sent(&mut self) -> Result<()> {
282 self.num_cell_until_sendme = self.cwnd.sendme_inc();
284 Ok(())
285 }
286
287 fn data_received(&mut self) -> Result<bool> {
288 if self.num_cell_until_sendme == 0 {
289 error_report!(internal!("Congestion control unexptected data cell"), "");
293 return Ok(false);
294 }
295
296 self.num_cell_until_sendme = self.num_cell_until_sendme.saturating_sub(1);
298
299 Ok(self.num_cell_until_sendme == 0)
302 }
303
304 fn data_sent(&mut self) -> Result<()> {
305 self.num_inflight = self.num_inflight.saturating_add(1);
307 Ok(())
308 }
309
310 #[cfg(feature = "conflux")]
311 fn inflight(&self) -> Option<u32> {
312 Some(self.num_inflight)
313 }
314
315 #[cfg(test)]
316 fn send_window(&self) -> u32 {
317 self.cwnd.get()
318 }
319
320 fn algorithm(&self) -> Algorithm {
321 Algorithm::Vegas(self.params)
322 }
323}
324
325#[cfg(test)]
326#[allow(clippy::print_stderr)]
327pub(crate) mod test {
328 #![allow(clippy::bool_assert_comparison)]
330 #![allow(clippy::clone_on_copy)]
331 #![allow(clippy::dbg_macro)]
332 #![allow(clippy::mixed_attributes_style)]
333 #![allow(clippy::print_stderr)]
334 #![allow(clippy::print_stdout)]
335 #![allow(clippy::single_char_pattern)]
336 #![allow(clippy::unwrap_used)]
337 #![allow(clippy::unchecked_duration_subtraction)]
338 #![allow(clippy::useless_vec)]
339 #![allow(clippy::needless_pass_by_value)]
340 use std::{
343 collections::VecDeque,
344 time::{Duration, Instant},
345 };
346 use tor_units::Percentage;
347
348 use super::*;
349 use crate::congestion::{
350 params::VegasParamsBuilder,
351 test_utils::{new_cwnd, new_rtt_estimator},
352 };
353
354 impl Vegas {
355 pub(crate) fn set_inflight(&mut self, v: u32) {
357 self.num_inflight = v;
358 }
359 fn is_blocked_on_chan(&self) -> bool {
361 self.is_blocked_on_chan
362 }
363 fn set_is_blocked_on_chan(&mut self, v: bool) {
365 self.is_blocked_on_chan = v;
366 }
367 }
368
369 #[derive(Debug)]
372 struct TestVectorParams {
373 sent_usec_in: u64,
375 got_sendme_usec_in: u64,
376 or_conn_blocked_in: bool,
377 inflight_in: u32,
378 ewma_rtt_usec_out: u32,
380 min_rtt_usec_out: u32,
381 cwnd_out: u32,
382 in_slow_start_out: bool,
383 cwnd_full_out: bool,
384 blocked_chan_out: bool,
385 }
386
387 impl From<[u32; 10]> for TestVectorParams {
388 fn from(arr: [u32; 10]) -> Self {
389 Self {
390 sent_usec_in: u64::from(arr[0]),
391 got_sendme_usec_in: u64::from(arr[1]),
392 or_conn_blocked_in: arr[2] == 1,
393 inflight_in: arr[3],
394 ewma_rtt_usec_out: arr[4],
395 min_rtt_usec_out: arr[5],
396 cwnd_out: arr[6],
397 in_slow_start_out: arr[7] == 1,
398 cwnd_full_out: arr[8] == 1,
399 blocked_chan_out: arr[9] == 1,
400 }
401 }
402 }
403
404 struct VegasTest {
405 params: VecDeque<TestVectorParams>,
406 rtt: RoundtripTimeEstimator,
407 state: State,
408 vegas: Vegas,
409 }
410
411 impl VegasTest {
412 fn new(vec: Vec<[u32; 10]>) -> Self {
413 let mut params = VecDeque::new();
414 for values in vec {
415 params.push_back(values.into());
416 }
417 let state = State::default();
418 Self {
419 params,
420 rtt: new_rtt_estimator(),
421 vegas: Vegas::new(build_vegas_params(), &state, new_cwnd()),
422 state,
423 }
424 }
425
426 fn run_once(&mut self, p: &TestVectorParams) {
427 eprintln!("Testing vector: {:?}", p);
428 self.vegas.set_inflight(p.inflight_in);
430 self.vegas.set_is_blocked_on_chan(p.or_conn_blocked_in);
431
432 let now = Instant::now();
433 self.rtt
434 .expect_sendme(now + Duration::from_micros(p.sent_usec_in));
435 let ret = self.rtt.update(
436 now + Duration::from_micros(p.got_sendme_usec_in),
437 &self.state,
438 self.vegas.cwnd().expect("No CWND"),
439 );
440 assert!(ret.is_ok());
441
442 let signals = CongestionSignals::new(p.or_conn_blocked_in, 0);
443 let ret = self
444 .vegas
445 .sendme_received(&mut self.state, &mut self.rtt, signals);
446 assert!(ret.is_ok());
447
448 assert_eq!(self.rtt.ewma_rtt_usec().unwrap(), p.ewma_rtt_usec_out);
449 assert_eq!(self.rtt.min_rtt_usec().unwrap(), p.min_rtt_usec_out);
450 assert_eq!(self.vegas.cwnd().expect("No CWND").get(), p.cwnd_out);
451 assert_eq!(
452 self.vegas.cwnd().expect("No CWND").is_full(),
453 p.cwnd_full_out
454 );
455 assert_eq!(self.state.in_slow_start(), p.in_slow_start_out);
456 assert_eq!(self.vegas.is_blocked_on_chan(), p.blocked_chan_out);
457 }
458
459 fn run(&mut self) {
460 while let Some(param) = self.params.pop_front() {
461 self.run_once(¶m);
462 }
463 }
464 }
465
466 pub(crate) fn build_vegas_params() -> VegasParams {
467 const OUTBUF_CELLS: u32 = 62;
468 VegasParamsBuilder::default()
469 .cell_in_queue_params(
470 (
471 3 * OUTBUF_CELLS, 4 * OUTBUF_CELLS, 5 * OUTBUF_CELLS, 3 * OUTBUF_CELLS, 600, )
477 .into(),
478 )
479 .ss_cwnd_max(5_000)
480 .cwnd_full_gap(4)
481 .cwnd_full_min_pct(Percentage::new(25))
482 .cwnd_full_per_cwnd(1)
483 .build()
484 .expect("Unable to build Vegas parameters")
485 }
486
487 #[test]
488 fn test_vectors() {
489 let vec1 = vec![
490 [100000, 200000, 0, 124, 100000, 100000, 155, 1, 0, 0],
491 [200000, 300000, 0, 155, 100000, 100000, 186, 1, 1, 0],
492 [350000, 500000, 0, 186, 133333, 100000, 217, 1, 1, 0],
493 [500000, 550000, 0, 217, 77777, 77777, 248, 1, 1, 0],
494 [600000, 700000, 0, 248, 92592, 77777, 279, 1, 1, 0],
495 [700000, 750000, 0, 279, 64197, 64197, 310, 1, 0, 0], [750000, 875000, 0, 310, 104732, 64197, 341, 1, 1, 0],
497 [875000, 900000, 0, 341, 51577, 51577, 372, 1, 1, 0],
498 [900000, 950000, 0, 279, 50525, 50525, 403, 1, 1, 0],
499 [950000, 1000000, 0, 279, 50175, 50175, 434, 1, 1, 0],
500 [1000000, 1050000, 0, 279, 50058, 50058, 465, 1, 1, 0],
501 [1050000, 1100000, 0, 279, 50019, 50019, 496, 1, 1, 0],
502 [1100000, 1150000, 0, 279, 50006, 50006, 527, 1, 1, 0],
503 [1150000, 1200000, 0, 279, 50002, 50002, 558, 1, 1, 0],
504 [1200000, 1250000, 0, 550, 50000, 50000, 589, 1, 1, 0],
505 [1250000, 1300000, 0, 550, 50000, 50000, 620, 1, 0, 0], [1300000, 1350000, 0, 550, 50000, 50000, 635, 1, 1, 0],
507 [1350000, 1400000, 0, 550, 50000, 50000, 650, 1, 1, 0],
508 [1400000, 1450000, 0, 150, 50000, 50000, 650, 1, 0, 0], [1450000, 1500000, 0, 150, 50000, 50000, 650, 1, 0, 0], [1500000, 1550000, 0, 550, 50000, 50000, 664, 1, 1, 0], [1500000, 1600000, 0, 550, 83333, 50000, 584, 0, 1, 0], [1600000, 1650000, 0, 550, 61111, 50000, 585, 0, 1, 0], [1650000, 1700000, 0, 550, 53703, 50000, 586, 0, 1, 0],
514 [1700000, 1750000, 0, 100, 51234, 50000, 586, 0, 0, 0], [1750000, 1900000, 0, 100, 117078, 50000, 559, 0, 0, 0], [1900000, 2000000, 0, 100, 105692, 50000, 558, 0, 0, 0], [2000000, 2075000, 0, 500, 85230, 50000, 558, 0, 1, 0], [2075000, 2125000, 1, 500, 61743, 50000, 557, 0, 1, 1], [2125000, 2150000, 0, 500, 37247, 37247, 558, 0, 1, 0], [2150000, 2350000, 0, 500, 145749, 37247, 451, 0, 1, 0], ];
522 VegasTest::new(vec1).run();
523
524 let vec2 = vec![
525 [100000, 200000, 0, 124, 100000, 100000, 155, 1, 0, 0],
526 [200000, 300000, 0, 155, 100000, 100000, 186, 1, 1, 0],
527 [350000, 500000, 0, 186, 133333, 100000, 217, 1, 1, 0],
528 [500000, 550000, 1, 217, 77777, 77777, 403, 0, 1, 1], [600000, 700000, 0, 248, 92592, 77777, 404, 0, 1, 0], [700000, 750000, 1, 404, 64197, 64197, 403, 0, 0, 1], [750000, 875000, 0, 403, 104732, 64197, 404, 0, 1, 0],
532 ];
533 VegasTest::new(vec2).run();
534
535 let vec3 = vec![
536 [18258527, 19002938, 0, 83, 744411, 744411, 155, 1, 0, 0],
537 [18258580, 19254257, 0, 52, 911921, 744411, 186, 1, 1, 0],
538 [20003224, 20645298, 0, 164, 732023, 732023, 217, 1, 1, 0],
539 [20003367, 21021444, 0, 133, 922725, 732023, 248, 1, 1, 0],
540 [20003845, 21265508, 0, 102, 1148683, 732023, 279, 1, 1, 0],
541 [20003975, 21429157, 0, 71, 1333015, 732023, 310, 1, 0, 0],
542 [20004309, 21707677, 0, 40, 1579917, 732023, 310, 1, 0, 0],
543 ];
544 VegasTest::new(vec3).run();
545
546 let vec4 = vec![
547 [358297091, 358854163, 0, 83, 557072, 557072, 155, 1, 0, 0],
548 [358297649, 359123845, 0, 52, 736488, 557072, 186, 1, 1, 0],
549 [359492879, 359995330, 0, 186, 580463, 557072, 217, 1, 1, 0],
550 [359493043, 360489243, 0, 217, 857621, 557072, 248, 1, 1, 0],
551 [359493232, 360489673, 0, 248, 950167, 557072, 279, 1, 1, 0],
552 [359493795, 360489971, 0, 279, 980839, 557072, 310, 1, 0, 0],
553 [359493918, 360490248, 0, 310, 991166, 557072, 341, 1, 1, 0],
554 [359494029, 360716465, 0, 341, 1145346, 557072, 372, 1, 1, 0],
555 [359996888, 360948867, 0, 372, 1016434, 557072, 403, 1, 1, 0],
556 [359996979, 360949330, 0, 403, 973712, 557072, 434, 1, 1, 0],
557 [360489528, 361113615, 0, 434, 740628, 557072, 465, 1, 1, 0],
558 [360489656, 361281604, 0, 465, 774841, 557072, 496, 1, 1, 0],
559 [360489837, 361500461, 0, 496, 932029, 557072, 482, 0, 1, 0],
560 [360489963, 361500631, 0, 482, 984455, 557072, 482, 0, 1, 0],
561 [360490117, 361842481, 0, 482, 1229727, 557072, 481, 0, 1, 0],
562 ];
563 VegasTest::new(vec4).run();
564 }
565}