use std::{
collections::VecDeque,
time::{Duration, Instant},
};
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RttSource {
Direct,
SegmentWide,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct RttSample {
pub at: Instant,
pub rtt: Duration,
pub source: RttSource,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct HostTelemetry {
rtt_history: VecDeque<RttSample>,
max_samples: usize,
hop_counter: Option<u8>,
}
impl HostTelemetry {
pub fn new(max_samples: usize) -> Self {
Self {
rtt_history: VecDeque::with_capacity(max_samples),
max_samples,
hop_counter: None,
}
}
pub fn max_samples(&self) -> usize {
self.max_samples
}
pub fn set_max_samples(&mut self, max_samples: usize) {
self.max_samples = max_samples;
while self.rtt_history.len() > self.max_samples {
self.rtt_history.pop_front();
}
}
pub fn history(&self) -> &VecDeque<RttSample> {
&self.rtt_history
}
fn has_direct(&self) -> bool {
self.rtt_history
.iter()
.any(|sample| sample.source == RttSource::Direct)
}
fn direct(&self) -> impl Iterator<Item = Duration> + '_ {
self.rtt_history
.iter()
.filter(|sample| sample.source == RttSource::Direct)
.map(|sample| sample.rtt)
}
fn tightest_bound(&self) -> Option<Duration> {
self.rtt_history.iter().map(|sample| sample.rtt).min()
}
pub fn add_rtt(&mut self, rtt: Duration) {
self.add_rtt_at(Instant::now(), rtt);
}
pub fn add_segment_wide_rtt(&mut self, rtt: Duration) {
self.push(RttSample {
at: Instant::now(),
rtt,
source: RttSource::SegmentWide,
});
}
fn add_rtt_at(&mut self, time: Instant, rtt: Duration) {
self.push(RttSample {
at: time,
rtt,
source: RttSource::Direct,
});
}
fn push(&mut self, sample: RttSample) {
if self.max_samples == 0 {
return;
}
self.rtt_history.push_back(sample);
while self.rtt_history.len() > self.max_samples {
self.rtt_history.pop_front();
}
}
pub fn record_hop_counter(&mut self, arrived: u8) {
self.hop_counter = Some(arrived);
}
pub fn hop_counter(&self) -> Option<u8> {
self.hop_counter
}
pub fn min_rtt(&self) -> Option<Duration> {
if self.has_direct() {
self.direct().min()
} else {
self.tightest_bound()
}
}
pub fn max_rtt(&self) -> Option<Duration> {
if self.has_direct() {
self.direct().max()
} else {
self.tightest_bound()
}
}
pub fn median_rtt(&self) -> Option<Duration> {
if !self.has_direct() {
return self.tightest_bound();
}
let mut sorted: Vec<Duration> = self.direct().collect();
if sorted.is_empty() {
return None;
}
sorted.sort_unstable();
let mid = sorted.len() / 2;
if sorted.len() % 2 == 1 {
Some(sorted[mid])
} else {
Some(sorted[mid - 1] + (sorted[mid] - sorted[mid - 1]) / 2)
}
}
pub fn average_rtt(&self) -> Option<Duration> {
if !self.has_direct() {
return self.tightest_bound();
}
let (sum, count) = self
.direct()
.fold((Duration::ZERO, 0u32), |(sum, count), rtt| {
(sum + rtt, count + 1)
});
(count > 0).then(|| sum / count)
}
pub fn jitter(&self) -> Option<Duration> {
let mut samples = self.direct();
let mut previous = samples.next()?;
let mut total = Duration::ZERO;
let mut gaps = 0u32;
for rtt in samples {
total += rtt.abs_diff(previous);
previous = rtt;
gaps += 1;
}
(gaps > 0).then(|| total / gaps)
}
pub fn merge(&mut self, mut other: HostTelemetry) {
if let Some(arrived) = other.hop_counter {
self.hop_counter = Some(arrived);
}
if other.max_samples > self.max_samples {
self.max_samples = other.max_samples;
}
if self.max_samples == 0 {
return;
}
let mut combined: Vec<_> = self
.rtt_history
.drain(..)
.chain(other.rtt_history.drain(..))
.collect();
combined.sort_by_key(|sample| sample.at);
let start_idx = combined.len().saturating_sub(self.max_samples);
self.rtt_history
.extend(combined.into_iter().skip(start_idx));
}
}
impl std::fmt::Display for HostTelemetry {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self.average_rtt() {
Some(avg) => write!(
f,
"avg={:?}, jitter={:?}",
avg,
self.jitter().unwrap_or(Duration::ZERO)
),
None => write!(f, "no telemetry"),
}
}
}
impl Default for HostTelemetry {
fn default() -> Self {
Self::new(10)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_window_with_no_samples_reports_no_statistics() {
let empty = HostTelemetry::new(10);
assert_eq!(empty.average_rtt(), None);
assert_eq!(empty.median_rtt(), None);
assert_eq!(empty.jitter(), None);
assert_eq!(empty.min_rtt(), None);
assert_eq!(empty.max_rtt(), None);
}
#[test]
fn a_segment_wide_sample_never_dilutes_a_direct_one() {
let mut t = HostTelemetry::new(10);
t.add_segment_wide_rtt(Duration::from_millis(72));
t.add_rtt(Duration::from_millis(7));
t.add_segment_wide_rtt(Duration::from_millis(71));
t.add_rtt(Duration::from_millis(5));
assert_eq!(t.median_rtt(), Some(Duration::from_millis(6)));
assert_eq!(t.min_rtt(), Some(Duration::from_millis(5)));
assert_eq!(t.max_rtt(), Some(Duration::from_millis(7)));
assert_eq!(
t.history().len(),
4,
"the weaker samples are ranked below, not thrown away"
);
}
#[test]
fn ranking_does_not_depend_on_which_reply_arrived_first() {
let mut early = HostTelemetry::new(10);
early.add_rtt(Duration::from_millis(5));
early.add_segment_wide_rtt(Duration::from_millis(72));
let mut late = HostTelemetry::new(10);
late.add_segment_wide_rtt(Duration::from_millis(72));
late.add_rtt(Duration::from_millis(5));
assert_eq!(early.median_rtt(), late.median_rtt());
assert_eq!(early.median_rtt(), Some(Duration::from_millis(5)));
}
#[test]
fn a_host_with_only_segment_wide_samples_still_reports_latency() {
let mut t = HostTelemetry::new(10);
t.add_segment_wide_rtt(Duration::from_millis(72));
t.add_segment_wide_rtt(Duration::from_millis(219));
assert_eq!(t.min_rtt(), Some(Duration::from_millis(72)));
assert!(t.average_rtt().is_some());
}
#[test]
fn segment_wide_samples_report_the_tightest_bound_not_their_midpoint() {
let mut t = HostTelemetry::new(10);
t.add_segment_wide_rtt(Duration::from_millis(104));
t.add_segment_wide_rtt(Duration::from_millis(1_549));
assert_eq!(
t.median_rtt(),
Some(Duration::from_millis(104)),
"the reported figure has to be a reply the segment actually gave"
);
assert_eq!(t.max_rtt(), Some(Duration::from_millis(104)));
assert_eq!(t.average_rtt(), Some(Duration::from_millis(104)));
assert_eq!(
t.history().len(),
2,
"both replies stay on record; only the summary of them narrows"
);
}
#[test]
fn direct_samples_are_still_summarized_by_the_median() {
let mut t = HostTelemetry::new(10);
t.add_rtt(Duration::from_millis(5));
t.add_rtt(Duration::from_millis(7));
t.add_rtt(Duration::from_millis(200));
assert_eq!(t.median_rtt(), Some(Duration::from_millis(7)));
assert_eq!(t.max_rtt(), Some(Duration::from_millis(200)));
}
#[test]
fn the_average_is_the_mean_of_the_direct_samples() {
let mut t = HostTelemetry::new(5);
t.add_rtt(Duration::from_millis(10));
t.add_rtt(Duration::from_millis(20));
assert_eq!(t.average_rtt(), Some(Duration::from_millis(15)));
}
#[test]
fn jitter_averages_the_gaps_between_consecutive_samples() {
let mut t = HostTelemetry::new(5);
t.add_rtt(Duration::from_millis(100)); t.add_rtt(Duration::from_millis(110)); t.add_rtt(Duration::from_millis(105)); assert_eq!(
t.jitter(),
Some(Duration::from_millis(7) + Duration::from_micros(500))
);
}
#[test]
fn the_median_of_an_odd_window_is_its_middle_sample() {
let mut t = HostTelemetry::new(5);
t.add_rtt(Duration::from_millis(30));
t.add_rtt(Duration::from_millis(10));
t.add_rtt(Duration::from_millis(20));
assert_eq!(t.median_rtt(), Some(Duration::from_millis(20)));
}
#[test]
fn the_median_of_an_even_window_averages_the_two_central_samples() {
let mut t = HostTelemetry::new(5);
t.add_rtt(Duration::from_millis(10));
t.add_rtt(Duration::from_millis(20));
t.add_rtt(Duration::from_millis(30));
t.add_rtt(Duration::from_millis(50));
assert_eq!(t.median_rtt(), Some(Duration::from_millis(25)));
}
#[test]
fn the_median_barely_moves_for_a_single_outlier() {
let mut t = HostTelemetry::new(5);
t.add_rtt(Duration::from_millis(10));
t.add_rtt(Duration::from_millis(11));
t.add_rtt(Duration::from_millis(12));
t.add_rtt(Duration::from_secs(5)); t.add_rtt(Duration::from_millis(13));
assert_eq!(t.median_rtt(), Some(Duration::from_millis(12)));
}
#[test]
fn a_merge_widens_the_window_to_the_larger_of_the_two() {
let mut t1 = HostTelemetry::new(3);
let t2 = HostTelemetry::new(10);
t1.merge(t2);
assert_eq!(t1.max_samples(), 10);
}
#[test]
fn a_window_of_zero_stays_empty_across_a_merge() {
let mut t1 = HostTelemetry::new(0);
let t2 = HostTelemetry::new(0);
t1.merge(t2);
assert_eq!(t1.rtt_history.len(), 0);
}
}