use crate::error::{Error, ErrorCode, Result};
use crate::platform::Duration;
use crate::platform::Instant;
pub const MRP_MAX_TRANSMISSIONS: u32 = 5;
pub const MRP_BACKOFF_BASE: (u64, u64) = (16, 10);
pub const MRP_BACKOFF_JITTER: (u64, u64) = (1, 4);
pub const MRP_BACKOFF_MARGIN: (u64, u64) = (11, 10);
pub const MRP_BACKOFF_THRESHOLD: u32 = 1;
pub const MRP_STANDALONE_ACK_TIMEOUT: Duration = Duration::from_millis(200);
pub const SESSION_IDLE_INTERVAL: Duration = Duration::from_millis(500);
pub const SESSION_ACTIVE_INTERVAL: Duration = Duration::from_millis(300);
pub const SESSION_ACTIVE_THRESHOLD: Duration = Duration::from_millis(4000);
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct MrpParams {
pub idle_interval: Duration,
pub active_interval: Duration,
pub active_threshold: Duration,
}
impl Default for MrpParams {
fn default() -> Self {
Self {
idle_interval: SESSION_IDLE_INTERVAL,
active_interval: SESSION_ACTIVE_INTERVAL,
active_threshold: SESSION_ACTIVE_THRESHOLD,
}
}
}
impl MrpParams {
#[must_use]
pub fn clamped(self) -> Self {
const MAX_INTERVAL: Duration = Duration::from_millis(3_600_000);
const MAX_THRESHOLD: Duration = Duration::from_millis(65_535);
Self {
idle_interval: min(self.idle_interval, MAX_INTERVAL),
active_interval: min(self.active_interval, MAX_INTERVAL),
active_threshold: min(self.active_threshold, MAX_THRESHOLD),
}
}
#[must_use]
pub fn base_interval(&self, peer_active: bool) -> Duration {
let i = if peer_active {
self.active_interval
} else {
self.idle_interval
};
i.mul_ratio(MRP_BACKOFF_MARGIN.0, MRP_BACKOFF_MARGIN.1)
}
}
const fn min(a: Duration, b: Duration) -> Duration {
if a.as_micros() <= b.as_micros() { a } else { b }
}
#[must_use]
pub fn backoff(base_interval: Duration, n: u32) -> Duration {
let exponent = n.saturating_sub(MRP_BACKOFF_THRESHOLD);
let mut d = base_interval;
for _ in 0..exponent {
d = d.mul_ratio(MRP_BACKOFF_BASE.0, MRP_BACKOFF_BASE.1);
}
d
}
#[must_use]
pub fn with_jitter(backoff: Duration, randomness: u32) -> Duration {
const RESOLUTION: u64 = 1 << 16;
let draw = u64::from(randomness) % RESOLUTION;
let denominator = RESOLUTION.saturating_mul(MRP_BACKOFF_JITTER.1);
let extra = backoff.mul_ratio(draw.saturating_mul(MRP_BACKOFF_JITTER.0), denominator);
backoff.saturating_add(extra)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum OnTimeout {
Retransmit {
counter: u32,
attempt: u32,
},
SendStandaloneAck {
counter: u32,
},
GiveUp {
counter: u32,
},
Nothing,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Mrp {
params: MrpParams,
pending_tx: Option<PendingTx>,
pending_ack: Option<PendingAck>,
last_heard: Option<Instant>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct PendingTx {
counter: u32,
sent: u32,
deadline: Instant,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct PendingAck {
counter: u32,
deadline: Instant,
}
impl Mrp {
#[must_use]
pub fn new(params: MrpParams) -> Self {
Self {
params: params.clamped(),
pending_tx: None,
pending_ack: None,
last_heard: None,
}
}
#[must_use]
pub const fn params(&self) -> MrpParams {
self.params
}
#[must_use]
pub const fn is_awaiting_ack(&self) -> bool {
self.pending_tx.is_some()
}
#[must_use]
pub const fn awaiting(&self) -> Option<u32> {
match self.pending_tx {
Some(tx) => Some(tx.counter),
None => None,
}
}
#[must_use]
pub fn peer_active(&self, now: Instant) -> bool {
match self.last_heard {
Some(t) => now.saturating_duration_since(t) < self.params.active_threshold,
None => false,
}
}
pub fn note_peer_activity(&mut self, now: Instant) {
self.last_heard = Some(now);
}
pub fn on_send(&mut self, counter: u32, now: Instant, randomness: u32) -> Result<()> {
if self.pending_tx.is_some() {
return Err(Error::new(ErrorCode::Busy));
}
let base = self.params.base_interval(self.peer_active(now));
let deadline = now.saturating_add(with_jitter(backoff(base, 0), randomness));
self.pending_tx = Some(PendingTx {
counter,
sent: 1,
deadline,
});
Ok(())
}
pub fn take_piggyback(&mut self) -> Option<u32> {
self.pending_ack.take().map(|a| a.counter)
}
pub fn on_reliable_received(&mut self, counter: u32, now: Instant, _duplicate: bool) {
self.note_peer_activity(now);
self.pending_ack = Some(PendingAck {
counter,
deadline: now.saturating_add(MRP_STANDALONE_ACK_TIMEOUT),
});
}
pub fn on_ack(&mut self, counter: u32, now: Instant) -> bool {
self.note_peer_activity(now);
match self.pending_tx {
Some(tx) if tx.counter == counter => {
self.pending_tx = None;
true
}
_ => false,
}
}
#[must_use]
pub fn poll_deadline(&self) -> Option<Instant> {
match (self.pending_tx, self.pending_ack) {
(Some(tx), Some(ack)) => Some(min_instant(tx.deadline, ack.deadline)),
(Some(tx), None) => Some(tx.deadline),
(None, Some(ack)) => Some(ack.deadline),
(None, None) => None,
}
}
pub fn on_timeout(&mut self, now: Instant, randomness: u32) -> OnTimeout {
if let Some(ack) = self.pending_ack
&& ack.deadline.is_elapsed_at(now)
{
self.pending_ack = None;
return OnTimeout::SendStandaloneAck {
counter: ack.counter,
};
}
if let Some(tx) = self.pending_tx
&& tx.deadline.is_elapsed_at(now)
{
if tx.sent >= MRP_MAX_TRANSMISSIONS {
self.pending_tx = None;
return OnTimeout::GiveUp {
counter: tx.counter,
};
}
let base = self.params.base_interval(self.peer_active(now));
let wait = with_jitter(backoff(base, tx.sent), randomness);
let attempt = tx.sent;
self.pending_tx = Some(PendingTx {
counter: tx.counter,
sent: tx.sent.saturating_add(1),
deadline: now.saturating_add(wait),
});
return OnTimeout::Retransmit {
counter: tx.counter,
attempt,
};
}
OnTimeout::Nothing
}
pub fn close(&mut self) {
self.pending_tx = None;
self.pending_ack = None;
}
}
const fn min_instant(a: Instant, b: Instant) -> Instant {
if a.as_micros() <= b.as_micros() { a } else { b }
}
#[cfg(test)]
mod tests {
use super::*;
fn table_21_base() -> Duration {
MrpParams::default().base_interval(true)
}
#[test]
fn the_margin_is_applied_to_the_peer_interval() {
let p = MrpParams::default();
assert_eq!(p.base_interval(true).as_millis(), 330, "1.1 * 300");
assert_eq!(p.base_interval(false).as_millis(), 550, "1.1 * 500");
}
fn round_ms(d: Duration) -> u64 {
d.as_micros().saturating_add(500).wrapping_div(1_000)
}
#[test]
fn the_backoff_curve_matches_core_table_21() {
let base = table_21_base();
let expected = [330u64, 330, 528, 845, 1352];
for (n, want) in expected.iter().enumerate() {
let got = backoff(base, n as u32);
assert_eq!(round_ms(got), *want, "transmission #{n}");
}
assert_eq!(backoff(base, 0).as_micros(), 330_000);
assert_eq!(backoff(base, 2).as_micros(), 528_000);
assert_eq!(backoff(base, 3).as_micros(), 844_800);
assert_eq!(backoff(base, 4).as_micros(), 1_351_680);
}
#[test]
fn maximum_jitter_matches_core_table_21() {
let base = table_21_base();
let expected = [413u64, 413, 660, 1056, 1690];
for (n, want) in expected.iter().enumerate() {
let got = round_ms(with_jitter(backoff(base, n as u32), u32::MAX));
assert!(
got.abs_diff(*want) <= 1,
"transmission #{n}: got {got}, table says {want}"
);
}
}
#[test]
fn jitter_only_ever_adds() {
let base = table_21_base();
for n in 0..MRP_MAX_TRANSMISSIONS {
let plain = backoff(base, n);
for r in [0u32, 1, 1000, u32::MAX / 2, u32::MAX] {
let jittered = with_jitter(plain, r);
assert!(jittered >= plain, "n={n} r={r}");
assert!(
jittered <= plain.saturating_add(plain.mul_ratio(1, 4)),
"n={n} r={r}: more than 25% added"
);
}
}
}
#[test]
fn a_zero_draw_is_the_unjittered_backoff() {
let base = table_21_base();
assert_eq!(with_jitter(backoff(base, 0), 0), backoff(base, 0));
}
#[test]
fn an_acknowledgement_stops_the_timer() {
let mut mrp = Mrp::new(MrpParams::default());
let t0 = Instant::ZERO;
mrp.on_send(7, t0, 0).expect("first send");
assert!(mrp.is_awaiting_ack());
assert_eq!(mrp.awaiting(), Some(7));
assert!(mrp.poll_deadline().is_some());
assert!(mrp.on_ack(7, t0), "the pending message is acknowledged");
assert!(!mrp.is_awaiting_ack());
assert_eq!(mrp.poll_deadline(), None);
}
#[test]
fn an_acknowledgement_for_something_else_is_ignored() {
let mut mrp = Mrp::new(MrpParams::default());
mrp.on_send(7, Instant::ZERO, 0).expect("send");
assert!(!mrp.on_ack(6, Instant::ZERO), "not the pending counter");
assert!(mrp.is_awaiting_ack(), "still waiting");
}
#[test]
fn one_pending_retransmission_per_exchange() {
let mut mrp = Mrp::new(MrpParams::default());
mrp.on_send(1, Instant::ZERO, 0).expect("first");
assert_eq!(
mrp.on_send(2, Instant::ZERO, 0).unwrap_err().code(),
ErrorCode::Busy
);
}
#[test]
fn the_ladder_is_five_transmissions_then_give_up() {
let mut mrp = Mrp::new(MrpParams::default());
let mut now = Instant::ZERO;
mrp.on_send(42, now, 0).expect("send");
let mut attempts = heapless::Vec::<u32, 8>::new();
while let Some(deadline) = mrp.poll_deadline() {
now = deadline;
match mrp.on_timeout(now, 0) {
OnTimeout::Retransmit { counter, attempt } => {
assert_eq!(counter, 42, "the counter never changes");
let _ = attempts.push(attempt);
}
OnTimeout::GiveUp { counter } => {
assert_eq!(counter, 42);
break;
}
other => panic!("unexpected {other:?}"),
}
}
assert_eq!(&attempts[..], &[1, 2, 3, 4]);
assert!(!mrp.is_awaiting_ack(), "giving up clears the state");
}
#[test]
fn the_cumulative_time_matches_core_table_21() {
let mut mrp = Mrp::new(MrpParams::default());
mrp.note_peer_activity(Instant::ZERO);
let mut now = Instant::ZERO;
mrp.on_send(1, now, 0).expect("send");
let expected = [330u64, 660, 1188, 2033, 3385];
let mut totals = heapless::Vec::<u64, 8>::new();
let mut rounded_sum = 0u64;
let mut previous = Instant::ZERO;
while let Some(deadline) = mrp.poll_deadline() {
now = deadline;
rounded_sum =
rounded_sum.saturating_add(round_ms(now.saturating_duration_since(previous)));
previous = now;
let _ = totals.push(rounded_sum);
if matches!(mrp.on_timeout(now, 0), OnTimeout::GiveUp { .. }) {
break;
}
}
assert_eq!(
&totals[..],
&expected[..],
"cumulative retransmission times"
);
assert_eq!(
now.saturating_duration_since(Instant::ZERO).as_micros(),
3_384_480,
"the exact total, before the table's per-step rounding"
);
}
#[test]
fn a_reliable_message_schedules_a_standalone_acknowledgement() {
let mut mrp = Mrp::new(MrpParams::default());
let t0 = Instant::ZERO;
mrp.on_reliable_received(9, t0, false);
let deadline = mrp.poll_deadline().expect("an ack deadline");
assert_eq!(
deadline.saturating_duration_since(t0),
MRP_STANDALONE_ACK_TIMEOUT
);
assert_eq!(
mrp.on_timeout(deadline, 0),
OnTimeout::SendStandaloneAck { counter: 9 }
);
assert_eq!(mrp.poll_deadline(), None, "and then nothing is pending");
}
#[test]
fn a_piggyback_cancels_the_standalone_acknowledgement() {
let mut mrp = Mrp::new(MrpParams::default());
mrp.on_reliable_received(9, Instant::ZERO, false);
assert_eq!(mrp.take_piggyback(), Some(9));
assert_eq!(mrp.poll_deadline(), None, "nothing left to send alone");
assert_eq!(mrp.take_piggyback(), None, "and only once");
}
#[test]
fn a_duplicate_is_still_acknowledged() {
let mut mrp = Mrp::new(MrpParams::default());
mrp.on_reliable_received(9, Instant::ZERO, true);
assert_eq!(mrp.take_piggyback(), Some(9));
}
#[test]
fn an_idle_peer_gets_the_idle_interval() {
let mut mrp = Mrp::new(MrpParams::default());
let t0 = Instant::ZERO;
mrp.on_send(1, t0, 0).expect("send");
let deadline = mrp.poll_deadline().expect("a deadline");
assert_eq!(
deadline.saturating_duration_since(t0).as_millis(),
550,
"a peer never heard from is idle: 1.1 * 500"
);
}
#[test]
fn an_active_peer_gets_the_active_interval() {
let mut mrp = Mrp::new(MrpParams::default());
let t0 = Instant::ZERO;
mrp.note_peer_activity(t0);
mrp.on_send(1, t0, 0).expect("send");
let deadline = mrp.poll_deadline().expect("a deadline");
assert_eq!(deadline.saturating_duration_since(t0).as_millis(), 330);
}
#[test]
fn a_peer_goes_idle_after_the_active_threshold() {
let mut mrp = Mrp::new(MrpParams::default());
mrp.note_peer_activity(Instant::ZERO);
assert!(mrp.peer_active(Instant::from_micros(0)));
let just_inside = Instant::ZERO
.saturating_add(SESSION_ACTIVE_THRESHOLD)
.saturating_sub(Duration::from_micros(1));
assert!(mrp.peer_active(just_inside));
let at_threshold = Instant::ZERO.saturating_add(SESSION_ACTIVE_THRESHOLD);
assert!(!mrp.peer_active(at_threshold), "the comparison is strict");
}
#[test]
fn peer_parameters_from_the_network_are_clamped() {
let hostile = MrpParams {
idle_interval: Duration::from_secs(86_400),
active_interval: Duration::from_secs(86_400),
active_threshold: Duration::from_secs(86_400),
};
let safe = hostile.clamped();
assert_eq!(safe.idle_interval.as_millis(), 3_600_000);
assert_eq!(safe.active_interval.as_millis(), 3_600_000);
assert_eq!(safe.active_threshold.as_millis(), 65_535);
assert_eq!(Mrp::new(hostile).params(), safe);
}
#[test]
fn both_a_retransmission_and_an_acknowledgement_can_be_due() {
let mut mrp = Mrp::new(MrpParams::default());
let t0 = Instant::ZERO;
mrp.on_send(1, t0, 0).expect("send");
mrp.on_reliable_received(2, t0, false);
let first = mrp.poll_deadline().expect("a deadline");
assert_eq!(
first.saturating_duration_since(t0),
MRP_STANDALONE_ACK_TIMEOUT
);
assert!(matches!(
mrp.on_timeout(first, 0),
OnTimeout::SendStandaloneAck { counter: 2 }
));
assert!(mrp.poll_deadline().is_some());
assert!(mrp.is_awaiting_ack());
}
#[test]
fn an_early_timeout_does_nothing() {
let mut mrp = Mrp::new(MrpParams::default());
mrp.on_send(1, Instant::ZERO, 0).expect("send");
assert_eq!(
mrp.on_timeout(Instant::from_micros(1), 0),
OnTimeout::Nothing
);
assert!(mrp.is_awaiting_ack(), "and changes nothing");
}
#[test]
fn closing_abandons_everything() {
let mut mrp = Mrp::new(MrpParams::default());
mrp.on_send(1, Instant::ZERO, 0).expect("send");
mrp.on_reliable_received(2, Instant::ZERO, false);
mrp.close();
assert_eq!(mrp.poll_deadline(), None);
assert!(!mrp.is_awaiting_ack());
}
}