use crate::platform::{Duration, Instant};
pub const PROBE_JITTER: Duration = Duration::from_millis(250);
pub const PROBE_INTERVAL: Duration = Duration::from_millis(250);
pub const PROBES: u8 = 3;
pub const TIEBREAK_DEFER: Duration = Duration::from_secs(1);
pub const CONFLICT_BURST: u8 = 15;
pub const CONFLICT_WINDOW: Duration = Duration::from_secs(10);
pub const CONFLICT_BACKOFF: Duration = Duration::from_secs(5);
pub const ANNOUNCE_INTERVAL: Duration = Duration::from_secs(1);
pub const ANNOUNCEMENTS_MIN: u8 = 2;
pub const ANNOUNCEMENTS_MAX: u8 = 8;
pub const MULTICAST_INTERVAL: Duration = Duration::from_secs(1);
pub const DEFEND_INTERVAL: Duration = Duration::from_millis(250);
pub const SHARED_DELAY_MIN: Duration = Duration::from_millis(20);
pub const SHARED_DELAY_MAX: Duration = Duration::from_millis(120);
pub const KNOWN_ANSWER_DELAY_MIN: Duration = Duration::from_millis(400);
pub const KNOWN_ANSWER_DELAY_MAX: Duration = Duration::from_millis(500);
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum Action {
Probe,
Announce,
Goodbye,
Rename,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum Phase {
Idle,
Probing,
Announcing,
Established,
Renaming,
Leaving,
}
#[derive(Debug, Clone)]
pub struct Schedule {
phase: Phase,
due: Instant,
sent: u8,
announcements: u8,
conflicts: u8,
window: Instant,
throttled: bool,
}
impl Default for Schedule {
fn default() -> Self {
Self::new()
}
}
impl Schedule {
#[must_use]
pub const fn new() -> Self {
Self {
phase: Phase::Idle,
due: Instant::ZERO,
sent: 0,
announcements: ANNOUNCEMENTS_MIN,
conflicts: 0,
window: Instant::ZERO,
throttled: false,
}
}
#[must_use]
pub const fn with_announcements(mut self, n: u8) -> Self {
self.announcements = if n < ANNOUNCEMENTS_MIN {
ANNOUNCEMENTS_MIN
} else if n > ANNOUNCEMENTS_MAX {
ANNOUNCEMENTS_MAX
} else {
n
};
self
}
#[must_use]
pub const fn phase(&self) -> Phase {
self.phase
}
#[must_use]
pub const fn may_respond(&self) -> bool {
matches!(self.phase, Phase::Announcing | Phase::Established)
}
pub fn start(&mut self, now: Instant, randomness: u32) {
self.phase = Phase::Probing;
self.sent = 0;
self.due = now.saturating_add(self.first_probe_delay(randomness));
}
pub fn updated(&mut self, now: Instant) {
if matches!(self.phase, Phase::Announcing | Phase::Established) {
self.phase = Phase::Announcing;
self.sent = 0;
self.due = now;
}
}
pub fn on_conflict(&mut self, now: Instant, randomness: u32) {
self.note_conflict(now);
match self.phase {
Phase::Probing => {
self.phase = Phase::Renaming;
self.due = now;
self.sent = 0;
}
Phase::Announcing | Phase::Established => self.start(now, randomness),
Phase::Idle | Phase::Renaming | Phase::Leaving => {}
}
}
pub fn on_tiebreak_loss(&mut self, now: Instant) {
if matches!(self.phase, Phase::Probing) {
self.sent = 0;
self.due = now.saturating_add(TIEBREAK_DEFER);
}
}
pub fn renamed(&mut self, now: Instant, randomness: u32) {
if matches!(self.phase, Phase::Renaming) {
self.start(now, randomness);
}
}
pub fn stop(&mut self, now: Instant) {
if self.may_respond() {
self.phase = Phase::Leaving;
self.due = now;
self.sent = 0;
} else {
self.phase = Phase::Idle;
}
}
#[must_use]
pub const fn wake_at(&self) -> Option<Instant> {
match self.phase {
Phase::Idle | Phase::Established => None,
_ => Some(self.due),
}
}
pub fn poll(&mut self, now: Instant) -> Option<Action> {
if self.wake_at().is_none_or(|due| now < due) {
return None;
}
match self.phase {
Phase::Probing if self.sent >= PROBES => {
self.phase = Phase::Announcing;
self.sent = 0;
Some(self.announce(now))
}
Phase::Probing => Some(self.probe(now)),
Phase::Announcing => Some(self.announce(now)),
Phase::Renaming => Some(Action::Rename),
Phase::Leaving => {
self.phase = Phase::Idle;
Some(Action::Goodbye)
}
Phase::Idle | Phase::Established => None,
}
}
fn probe(&mut self, now: Instant) -> Action {
self.sent = self.sent.saturating_add(1);
self.due = now.saturating_add(PROBE_INTERVAL);
Action::Probe
}
fn announce(&mut self, now: Instant) -> Action {
let mut interval = ANNOUNCE_INTERVAL;
for _ in 0..self.sent {
interval = interval.saturating_add(interval);
}
self.sent = self.sent.saturating_add(1);
if self.sent >= self.announcements {
self.phase = Phase::Established;
} else {
self.due = now.saturating_add(interval);
}
Action::Announce
}
fn first_probe_delay(&self, randomness: u32) -> Duration {
let jitter = Duration::from_micros(
u64::from(randomness)
.checked_rem(PROBE_JITTER.as_micros())
.unwrap_or(0),
);
if self.throttled {
CONFLICT_BACKOFF.saturating_add(jitter)
} else {
jitter
}
}
fn note_conflict(&mut self, now: Instant) {
if self.conflicts == 0 || now.saturating_duration_since(self.window) >= CONFLICT_WINDOW {
self.window = now;
self.conflicts = 1;
self.throttled = false;
} else {
self.conflicts = self.conflicts.saturating_add(1);
}
if self.conflicts >= CONFLICT_BURST {
self.throttled = true;
}
}
#[must_use]
pub const fn is_throttled(&self) -> bool {
self.throttled
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum Answering {
Probe,
Unique,
Shared,
KnownAnswerSuppression,
}
#[must_use]
pub fn response_delay(answering: Answering, randomness: u32) -> Duration {
let pick = |low: Duration, high: Duration| -> Duration {
let span = high.as_micros().saturating_sub(low.as_micros());
let draw = u64::from(randomness).checked_rem(span).unwrap_or(0);
low.saturating_add(Duration::from_micros(draw))
};
match answering {
Answering::Probe | Answering::Unique => Duration::ZERO,
Answering::Shared => pick(SHARED_DELAY_MIN, SHARED_DELAY_MAX),
Answering::KnownAnswerSuppression => pick(KNOWN_ANSWER_DELAY_MIN, KNOWN_ANSWER_DELAY_MAX),
}
}
#[derive(Debug, Clone)]
pub struct MulticastLimiter<const N: usize> {
last: [(Instant, bool); N],
}
impl<const N: usize> Default for MulticastLimiter<N> {
fn default() -> Self {
Self::new()
}
}
impl<const N: usize> MulticastLimiter<N> {
#[must_use]
pub const fn new() -> Self {
Self {
last: [(Instant::ZERO, false); N],
}
}
#[must_use]
pub fn earliest(&self, index: usize, defending: bool) -> Instant {
match self.last.get(index) {
Some(&(_, false)) | None => Instant::ZERO,
Some(&(at, true)) => at.saturating_add(if defending {
DEFEND_INTERVAL
} else {
MULTICAST_INTERVAL
}),
}
}
#[must_use]
pub fn may_send(&self, index: usize, now: Instant, defending: bool) -> bool {
now >= self.earliest(index, defending)
}
pub fn sent(&mut self, index: usize, now: Instant) {
if let Some(slot) = self.last.get_mut(index) {
*slot = (now, true);
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum Tiebreak {
Won,
Lost,
Identical,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Tiebreaker<'a> {
pub class: u16,
pub kind: u16,
pub rdata: &'a [u8],
}
impl Tiebreaker<'_> {
#[must_use]
pub fn cmp_lexicographic(&self, other: &Self) -> core::cmp::Ordering {
self.class
.cmp(&other.class)
.then(self.kind.cmp(&other.kind))
.then_with(|| self.rdata.cmp(other.rdata))
}
}
#[must_use]
pub fn tiebreak<'a, 'b>(
ours: impl IntoIterator<Item = Tiebreaker<'a>>,
theirs: impl IntoIterator<Item = Tiebreaker<'b>>,
) -> Tiebreak {
let mut ours = ours.into_iter();
let mut theirs = theirs.into_iter();
loop {
return match (ours.next(), theirs.next()) {
(None, None) => Tiebreak::Identical,
(Some(_), None) => Tiebreak::Won,
(None, Some(_)) => Tiebreak::Lost,
(Some(mine), Some(yours)) => match mine.cmp_lexicographic(&yours) {
core::cmp::Ordering::Equal => continue,
core::cmp::Ordering::Greater => Tiebreak::Won,
core::cmp::Ordering::Less => Tiebreak::Lost,
},
};
}
}
#[cfg(test)]
mod tests {
use super::*;
type Seen<T> = heapless::Vec<T, 32>;
fn drive(schedule: &mut Schedule, steps: usize) -> (Instant, Seen<Action>) {
let mut now = Instant::ZERO;
let mut seen = Seen::new();
for _ in 0..steps {
let Some(due) = schedule.wake_at() else { break };
now = due;
if let Some(action) = schedule.poll(now) {
seen.push(action).expect("fewer than 32 actions");
}
}
(now, seen)
}
#[test]
fn startup_probes_three_times_then_announces_twice() {
let mut schedule = Schedule::new();
schedule.start(Instant::ZERO, 0);
let (_, actions) = drive(&mut schedule, 8);
assert_eq!(
actions.as_slice(),
&[
Action::Probe,
Action::Probe,
Action::Probe,
Action::Announce,
Action::Announce
]
);
assert_eq!(schedule.phase(), Phase::Established);
}
#[test]
fn the_probes_are_250ms_apart_and_the_name_is_claimed_750ms_in() {
let mut schedule = Schedule::new();
schedule.start(Instant::ZERO, 0);
let mut at = [Instant::ZERO; 4];
for slot in &mut at {
let due = schedule.wake_at().expect("scheduled");
*slot = due;
let _ = schedule.poll(due);
}
assert_eq!(at[0], Instant::ZERO);
assert_eq!(at[1], Instant::ZERO.saturating_add(PROBE_INTERVAL));
assert_eq!(
at[2],
Instant::ZERO.saturating_add(Duration::from_millis(500))
);
assert_eq!(
at[3],
Instant::ZERO.saturating_add(Duration::from_millis(750))
);
}
#[test]
fn the_first_probe_is_jittered_within_250ms() {
for randomness in [0u32, 1, 999, 249_999, 250_000, u32::MAX] {
let mut schedule = Schedule::new();
schedule.start(Instant::ZERO, randomness);
let due = schedule.wake_at().expect("scheduled");
assert!(due.saturating_duration_since(Instant::ZERO) < PROBE_JITTER);
}
}
#[test]
fn nothing_is_answered_until_the_first_announcement() {
let mut schedule = Schedule::new();
assert!(!schedule.may_respond());
schedule.start(Instant::ZERO, 0);
for _ in 0..PROBES {
let due = schedule.wake_at().expect("scheduled");
assert_eq!(schedule.poll(due), Some(Action::Probe));
assert!(!schedule.may_respond(), "a probed name is not yet owned");
}
let due = schedule.wake_at().expect("scheduled");
assert_eq!(schedule.poll(due), Some(Action::Announce));
assert!(schedule.may_respond());
}
#[test]
fn announcement_intervals_double() {
let mut schedule = Schedule::new().with_announcements(4);
schedule.start(Instant::ZERO, 0);
let mut announced = Seen::<Instant>::new();
for _ in 0..16 {
let Some(due) = schedule.wake_at() else { break };
if schedule.poll(due) == Some(Action::Announce) {
let _ = announced.push(due);
}
}
assert_eq!(announced.len(), 4);
let gap = |a: usize, b: usize| announced[b].saturating_duration_since(announced[a]);
assert_eq!(gap(0, 1), Duration::from_secs(1));
assert_eq!(gap(1, 2), Duration::from_secs(2));
assert_eq!(gap(2, 3), Duration::from_secs(4));
}
#[test]
fn announcement_count_is_clamped_to_the_rfcs_range() {
assert_eq!(Schedule::new().with_announcements(0).announcements, 2);
assert_eq!(Schedule::new().with_announcements(1).announcements, 2);
assert_eq!(Schedule::new().with_announcements(200).announcements, 8);
}
#[test]
fn a_conflict_while_probing_renames() {
let mut schedule = Schedule::new();
schedule.start(Instant::ZERO, 0);
let due = schedule.wake_at().expect("scheduled");
assert_eq!(schedule.poll(due), Some(Action::Probe));
schedule.on_conflict(due, 0);
assert_eq!(schedule.phase(), Phase::Renaming);
assert_eq!(schedule.poll(due), Some(Action::Rename));
assert_eq!(schedule.poll(due), Some(Action::Rename));
schedule.renamed(due, 0);
assert_eq!(schedule.phase(), Phase::Probing);
}
#[test]
fn a_conflict_once_established_reprobes_rather_than_renaming() {
let mut schedule = Schedule::new();
schedule.start(Instant::ZERO, 0);
let (now, _) = drive(&mut schedule, 8);
assert_eq!(schedule.phase(), Phase::Established);
schedule.on_conflict(now, 0);
assert_eq!(schedule.phase(), Phase::Probing);
assert!(!schedule.may_respond());
}
#[test]
fn a_tiebreak_loss_defers_a_second_and_reprobes_without_renaming() {
let mut schedule = Schedule::new();
schedule.start(Instant::ZERO, 0);
let due = schedule.wake_at().expect("scheduled");
let _ = schedule.poll(due);
schedule.on_tiebreak_loss(due);
assert_eq!(schedule.phase(), Phase::Probing);
assert_eq!(
schedule.wake_at().expect("scheduled"),
due.saturating_add(TIEBREAK_DEFER)
);
let (_, actions) = drive(&mut schedule, 8);
assert_eq!(
actions.iter().filter(|a| **a == Action::Probe).count(),
usize::from(PROBES)
);
}
#[test]
fn fifteen_conflicts_in_ten_seconds_throttles_the_next_probe() {
let mut schedule = Schedule::new();
let mut now = Instant::ZERO;
schedule.start(now, 0);
for _ in 0..CONFLICT_BURST {
now = now.saturating_add(Duration::from_millis(100));
schedule.on_conflict(now, 0);
if schedule.phase() == Phase::Renaming {
let _ = schedule.poll(now);
schedule.renamed(now, 0);
}
}
assert!(schedule.is_throttled());
let due = schedule.wake_at().expect("scheduled");
assert!(due.saturating_duration_since(now) >= CONFLICT_BACKOFF);
}
#[test]
fn conflicts_spread_past_the_window_do_not_throttle() {
let mut schedule = Schedule::new();
let mut now = Instant::ZERO;
schedule.start(now, 0);
for _ in 0..40 {
now = now.saturating_add(CONFLICT_WINDOW);
schedule.on_conflict(now, 0);
if schedule.phase() == Phase::Renaming {
let _ = schedule.poll(now);
schedule.renamed(now, 0);
}
assert!(!schedule.is_throttled());
}
}
#[test]
fn an_update_reannounces_without_reprobing() {
let mut schedule = Schedule::new();
schedule.start(Instant::ZERO, 0);
let (now, _) = drive(&mut schedule, 8);
schedule.updated(now);
let (_, actions) = drive(&mut schedule, 8);
assert_eq!(actions.as_slice(), &[Action::Announce, Action::Announce]);
}
#[test]
fn an_update_while_probing_is_ignored() {
let mut schedule = Schedule::new();
schedule.start(Instant::ZERO, 0);
let due = schedule.wake_at().expect("scheduled");
let _ = schedule.poll(due);
schedule.updated(due);
assert_eq!(schedule.phase(), Phase::Probing);
}
#[test]
fn stopping_an_established_name_says_goodbye_once() {
let mut schedule = Schedule::new();
schedule.start(Instant::ZERO, 0);
let (now, _) = drive(&mut schedule, 8);
schedule.stop(now);
assert_eq!(schedule.poll(now), Some(Action::Goodbye));
assert_eq!(schedule.phase(), Phase::Idle);
assert_eq!(schedule.wake_at(), None);
assert_eq!(schedule.poll(now), None);
}
#[test]
fn stopping_a_name_that_was_never_announced_says_nothing() {
let mut schedule = Schedule::new();
schedule.start(Instant::ZERO, 0);
let due = schedule.wake_at().expect("scheduled");
let _ = schedule.poll(due);
schedule.stop(due);
assert_eq!(schedule.phase(), Phase::Idle);
assert_eq!(schedule.poll(due), None);
}
#[test]
fn an_established_schedule_has_no_wakeup() {
let mut schedule = Schedule::new();
schedule.start(Instant::ZERO, 0);
let (now, _) = drive(&mut schedule, 8);
assert_eq!(schedule.wake_at(), None, "§8.3: no periodic announcements");
assert_eq!(
schedule.poll(now.saturating_add(Duration::from_secs(3600))),
None
);
}
#[test]
fn polling_early_yields_nothing_and_does_not_advance() {
let mut schedule = Schedule::new();
schedule.start(Instant::ZERO, 12_345);
let due = schedule.wake_at().expect("scheduled");
assert_eq!(schedule.poll(Instant::ZERO), None);
assert_eq!(schedule.wake_at(), Some(due));
}
#[test]
fn response_delays_match_the_rfcs_ranges() {
let ms = Duration::from_millis;
for randomness in [0u32, 7, 5_000, 99_999, u32::MAX] {
assert_eq!(response_delay(Answering::Probe, randomness), Duration::ZERO);
assert_eq!(
response_delay(Answering::Unique, randomness),
Duration::ZERO
);
let shared = response_delay(Answering::Shared, randomness);
assert!(shared >= ms(20) && shared < ms(120), "{shared:?}");
let known = response_delay(Answering::KnownAnswerSuppression, randomness);
assert!(known >= ms(400) && known < ms(500), "{known:?}");
}
assert_ne!(
response_delay(Answering::Shared, 0),
response_delay(Answering::Shared, 50_000)
);
}
#[test]
fn the_rfcs_own_numbers_are_the_constants() {
assert_eq!(PROBE_JITTER, Duration::from_millis(250));
assert_eq!(PROBE_INTERVAL, Duration::from_millis(250));
assert_eq!(PROBES, 3);
assert_eq!(TIEBREAK_DEFER, Duration::from_secs(1));
assert_eq!(CONFLICT_BURST, 15);
assert_eq!(CONFLICT_WINDOW, Duration::from_secs(10));
assert_eq!(CONFLICT_BACKOFF, Duration::from_secs(5));
assert_eq!(ANNOUNCE_INTERVAL, Duration::from_secs(1));
assert_eq!(ANNOUNCEMENTS_MIN, 2);
assert_eq!(ANNOUNCEMENTS_MAX, 8);
assert_eq!(MULTICAST_INTERVAL, Duration::from_secs(1));
assert_eq!(DEFEND_INTERVAL, Duration::from_millis(250));
assert_eq!(SHARED_DELAY_MIN, Duration::from_millis(20));
assert_eq!(SHARED_DELAY_MAX, Duration::from_millis(120));
assert_eq!(KNOWN_ANSWER_DELAY_MIN, Duration::from_millis(400));
assert_eq!(KNOWN_ANSWER_DELAY_MAX, Duration::from_millis(500));
}
#[test]
fn a_record_may_not_be_multicast_twice_within_a_second() {
let mut limiter = MulticastLimiter::<4>::new();
let now = Instant::ZERO.saturating_add(Duration::from_secs(10));
assert!(limiter.may_send(0, now, false), "nothing sent yet");
limiter.sent(0, now);
assert!(!limiter.may_send(0, now.saturating_add(Duration::from_millis(999)), false));
assert!(limiter.may_send(0, now.saturating_add(MULTICAST_INTERVAL), false));
assert!(limiter.may_send(1, now, false));
}
#[test]
fn defending_a_name_only_waits_250ms() {
let mut limiter = MulticastLimiter::<2>::new();
let now = Instant::ZERO.saturating_add(Duration::from_secs(10));
limiter.sent(0, now);
let at = now.saturating_add(DEFEND_INTERVAL);
assert!(limiter.may_send(0, at, true), "§6's probe exception");
assert!(!limiter.may_send(0, at, false));
}
#[test]
fn an_untracked_slot_is_never_rate_limited() {
let mut limiter = MulticastLimiter::<1>::new();
limiter.sent(9, Instant::ZERO.saturating_add(Duration::from_secs(10)));
assert!(limiter.may_send(9, Instant::ZERO, false));
}
#[test]
fn rfc_8_2_address_example() {
let lower = Tiebreaker {
class: 1,
kind: 1,
rdata: &[169, 254, 99, 200],
};
let higher = Tiebreaker {
class: 1,
kind: 1,
rdata: &[169, 254, 200, 50],
};
assert_eq!(tiebreak([higher], [lower]), Tiebreak::Won);
assert_eq!(tiebreak([lower], [higher]), Tiebreak::Lost);
}
#[test]
fn class_beats_type_beats_rdata() {
let big_class = Tiebreaker {
class: 2,
kind: 1,
rdata: &[0],
};
let big_type = Tiebreaker {
class: 1,
kind: 255,
rdata: &[0],
};
let big_rdata = Tiebreaker {
class: 1,
kind: 1,
rdata: &[255],
};
assert_eq!(tiebreak([big_class], [big_type]), Tiebreak::Won);
assert_eq!(tiebreak([big_type], [big_rdata]), Tiebreak::Won);
}
#[test]
fn a_prefix_loses_to_what_extends_it() {
let short = Tiebreaker {
class: 1,
kind: 16,
rdata: &[1, 2],
};
let long = Tiebreaker {
class: 1,
kind: 16,
rdata: &[1, 2, 0],
};
assert_eq!(tiebreak([long], [short]), Tiebreak::Won);
}
#[test]
fn a_longer_set_wins_and_identical_sets_do_not_conflict() {
let a = Tiebreaker {
class: 1,
kind: 16,
rdata: &[1],
};
let b = Tiebreaker {
class: 1,
kind: 33,
rdata: &[2],
};
assert_eq!(tiebreak([a, b], [a]), Tiebreak::Won);
assert_eq!(tiebreak([a], [a, b]), Tiebreak::Lost);
assert_eq!(tiebreak([a, b], [a, b]), Tiebreak::Identical);
assert_eq!(
tiebreak(core::iter::empty(), core::iter::empty()),
Tiebreak::Identical
);
}
}