use std::{
collections::VecDeque,
time::{Duration, Instant},
};
use crate::model::host::status::StatusProtocol;
pub const DEFAULT_RTT_SAMPLES: usize = 10;
const MIN_RTT_SAMPLES: usize = 1;
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RttSource {
Direct,
SegmentWide,
FirstToNeighbour,
}
#[non_exhaustive]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RttSample {
pub at: Instant,
pub rtt: Duration,
pub source: RttSource,
pub protocol: Option<StatusProtocol>,
}
fn median(mut samples: Vec<Duration>) -> Option<Duration> {
if samples.is_empty() {
return None;
}
samples.sort_unstable();
let mid = samples.len() / 2;
if samples.len() % 2 == 1 {
Some(samples[mid])
} else {
Some(samples[mid - 1] + (samples[mid] - samples[mid - 1]) / 2)
}
}
impl RttSample {
fn resolves_the_link(&self) -> bool {
matches!(
self.protocol,
Some(StatusProtocol::Arp | StatusProtocol::Ndp)
)
}
}
#[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 {
let max_samples = max_samples.max(MIN_RTT_SAMPLES);
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.max(MIN_RTT_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)
}
pub(crate) fn round_trips(&self) -> Vec<Duration> {
if !self.has_direct() {
return self.tightest_bound().into_iter().collect();
}
let crossed: Vec<Duration> = self
.rtt_history
.iter()
.filter(|sample| sample.source == RttSource::Direct && !sample.resolves_the_link())
.map(|sample| sample.rtt)
.collect();
if crossed.is_empty() {
self.direct().collect()
} else {
crossed
}
}
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, None);
}
pub fn add_rtt_from(&mut self, rtt: Duration, protocol: StatusProtocol) {
self.add_rtt_at(Instant::now(), rtt, Some(protocol));
}
pub fn add_first_to_neighbour_rtt_from(&mut self, rtt: Duration, protocol: StatusProtocol) {
self.push(RttSample {
at: Instant::now(),
rtt,
source: RttSource::FirstToNeighbour,
protocol: Some(protocol),
});
}
pub fn add_segment_wide_rtt(&mut self, rtt: Duration) {
self.push(RttSample {
at: Instant::now(),
rtt,
source: RttSource::SegmentWide,
protocol: None,
});
}
pub fn add_segment_wide_rtt_from(&mut self, rtt: Duration, protocol: StatusProtocol) {
self.push(RttSample {
at: Instant::now(),
rtt,
source: RttSource::SegmentWide,
protocol: Some(protocol),
});
}
pub(crate) fn restore_rtt(
&mut self,
rtt: Duration,
source: RttSource,
protocol: Option<StatusProtocol>,
) {
self.push(RttSample {
at: Instant::now(),
rtt,
source,
protocol,
});
}
fn add_rtt_at(&mut self, time: Instant, rtt: Duration, protocol: Option<StatusProtocol>) {
self.push(RttSample {
at: time,
rtt,
source: RttSource::Direct,
protocol,
});
}
#[must_use]
pub fn rtt_protocol(&self) -> Option<StatusProtocol> {
let mut named = self.rtt_history.iter().filter_map(|s| s.protocol.clone());
let first = named.next()?;
named.all(|other| other == first).then_some(first)
}
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();
}
median(self.direct().collect())
}
pub(crate) fn median_round_trip(&self) -> Option<Duration> {
median(self.round_trips())
}
pub(crate) fn round_trips_resolve_the_link(&self) -> bool {
let mut direct = self
.rtt_history
.iter()
.filter(|sample| sample.source == RttSource::Direct)
.peekable();
direct.peek().is_some() && direct.all(RttSample::resolves_the_link)
}
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.saturating_add(rtt), count.saturating_add(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 = total.saturating_add(rtt.abs_diff(previous));
previous = rtt;
gaps = gaps.saturating_add(1);
}
(gaps > 0).then(|| total / gaps)
}
pub(crate) fn take_window(&mut self, later: HostTelemetry) {
if later.rtt_history.is_empty() {
return;
}
self.max_samples = self.max_samples.max(later.max_samples);
self.rtt_history = later.rtt_history;
while self.rtt_history.len() > self.max_samples {
self.rtt_history.pop_front();
}
}
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(DEFAULT_RTT_SAMPLES)
}
}
#[cfg(test)]
mod tests {
#[test]
fn round_trips_are_named_by_the_probe_that_measured_them() {
let mut telemetry = HostTelemetry::default();
telemetry.add_rtt_from(Duration::from_micros(90), StatusProtocol::Arp);
telemetry.add_rtt_from(Duration::from_micros(110), StatusProtocol::Arp);
assert_eq!(telemetry.rtt_protocol(), Some(StatusProtocol::Arp));
}
#[test]
fn round_trips_from_two_probes_are_named_by_neither() {
let mut telemetry = HostTelemetry::default();
telemetry.add_rtt_from(Duration::from_micros(90), StatusProtocol::Arp);
telemetry.add_rtt_from(Duration::from_micros(220), StatusProtocol::TcpSyn);
assert_eq!(telemetry.rtt_protocol(), None);
}
#[test]
fn a_wait_is_sized_from_answers_across_the_ip_stack_rather_than_the_resolution() {
let mut telemetry = HostTelemetry::default();
telemetry.add_rtt_from(Duration::from_millis(246), StatusProtocol::Arp);
telemetry.add_rtt_from(Duration::from_millis(18), StatusProtocol::TcpSyn);
telemetry.add_rtt_from(Duration::from_millis(80), StatusProtocol::Ndp);
telemetry.add_rtt(Duration::from_millis(20));
assert_eq!(
telemetry.round_trips(),
[18, 20].map(Duration::from_millis),
"the SYN's, and the one no probe was named for"
);
}
#[test]
fn a_host_that_answered_only_the_resolution_is_sized_from_it() {
let mut telemetry = HostTelemetry::default();
telemetry.add_segment_wide_rtt_from(Duration::from_millis(5), StatusProtocol::IcmpEcho);
telemetry.add_rtt_from(Duration::from_millis(246), StatusProtocol::Arp);
telemetry.add_rtt_from(Duration::from_millis(90), StatusProtocol::Arp);
assert_eq!(
telemetry.round_trips(),
[246, 90].map(Duration::from_millis),
"a direct answer still outranks the segment-wide bound"
);
}
#[test]
fn round_trips_nobody_named_stay_unnamed() {
let mut telemetry = HostTelemetry::default();
telemetry.add_rtt(Duration::from_micros(90));
assert_eq!(telemetry.rtt_protocol(), None);
}
use super::*;
#[test]
fn a_window_is_never_smaller_than_one_sample() {
let mut asked_for_none = HostTelemetry::new(0);
assert_eq!(asked_for_none.max_samples(), MIN_RTT_SAMPLES);
asked_for_none.add_rtt(Duration::from_millis(5));
assert_eq!(asked_for_none.history().len(), 1, "the sample is kept");
assert_eq!(asked_for_none.min_rtt(), Some(Duration::from_millis(5)));
let mut narrowed = HostTelemetry::new(4);
narrowed.add_rtt(Duration::from_millis(1));
narrowed.add_rtt(Duration::from_millis(2));
narrowed.set_max_samples(0);
assert_eq!(narrowed.max_samples(), MIN_RTT_SAMPLES);
assert_eq!(
narrowed.history().len(),
1,
"trimmed to the floor, not to nothing"
);
}
#[test]
fn segment_wide_samples_alone_give_every_statistic_one_figure() {
let mut bounded = HostTelemetry::new(10);
bounded.add_segment_wide_rtt(Duration::from_millis(10));
bounded.add_segment_wide_rtt(Duration::from_millis(90));
let tightest = Some(Duration::from_millis(10));
assert_eq!(bounded.min_rtt(), tightest);
assert_eq!(bounded.max_rtt(), tightest, "not the slowest of the two");
assert_eq!(bounded.median_rtt(), tightest, "not their median, 50");
assert_eq!(bounded.average_rtt(), tightest, "not their mean, 50");
bounded.add_rtt(Duration::from_millis(20));
assert_eq!(bounded.min_rtt(), Some(Duration::from_millis(20)));
assert_eq!(bounded.max_rtt(), Some(Duration::from_millis(20)));
}
#[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);
}
}