//! Implementation of the Trickle timer defined in [RFC 6206]. The algorithm allows node in a lossy
//! shared medium to exchange information in a highly robust, energy efficient, simple, and
//! scalable manner. Dynamically adjusting transmission windows allows Trickle to spread new
//! information fast while sending only a few messages per hour when information does not change.
//!
//! **NOTE**: the constants used for the default Trickle timer are the ones from the [Enhanced
//! Trickle].
//!
//! [RFC 6206]: https://datatracker.ietf.org/doc/html/rfc6206
//! [Enhanced Trickle]: https://d1wqtxts1xzle7.cloudfront.net/71402623/E-Trickle_Enhanced_Trickle_Algorithm_for20211005-2078-1ckh34a.pdf?1633439582=&response-content-disposition=inline%3B+filename%3DE_Trickle_Enhanced_Trickle_Algorithm_for.pdf&Expires=1681472005&Signature=cC7l-Pyr5r64XBNCDeSJ2ha6oqWUtO6A-KlDOyC0UVaHxDV3h3FuVHRtcNp3O9BUfRK8jeuWCYGBkCZgQT4Zgb6XwgVB-3z4TF9o3qBRMteRyYO5vjVkpPBeN7mz4Tl746SsSCHDm2NMtr7UVtLYamriU3D0rryoqLqJXmnkNoJpn~~wJe2H5PmPgIwixTwSvDkfFLSVoESaYS9ZWHZwbW-7G7OxIw8oSYhx9xMBnzkpdmT7sJNmvDzTUhoOjYrHTRM23cLVS9~oOSpT7hKtKD4h5CSmrNK4st07KnT9~tUqEcvGO3aXdd4quRZeKUcCkCbTLvhOEYg9~QqgD8xwhA__&Key-Pair-Id=APKAJLOHF5GGSLRBV4ZA
use crate::{
rand::Rand,
time::{Duration, Instant},
};
#[derive(Debug, PartialEq, Eq)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
pub(crate) struct TrickleTimer {
i_min: u32,
i_max: u32,
k: usize,
i: Duration,
t: Duration,
t_exp: Instant,
i_exp: Instant,
counter: usize,
}
impl TrickleTimer {
/// Creat a new Trickle timer using the default values.
///
/// **NOTE**: the standard defines I as a random value between [Imin, Imax]. However, this
/// could result in a t value that is very close to Imax. Therefore, sending DIO messages will
/// be sporadic, which is not ideal when a network is started. It might take a long time before
/// the network is actually stable. Therefore, we don't draw a random numberm but just use Imin
/// for I. This only affects the start of the RPL tree and speeds up building it. Also, we
/// don't use the default values from the standard, but the values from the _Enhanced Trickle
/// Algorithm for Low-Power and Lossy Networks_ from Baraq Ghaleb et al. This is also what the
/// Contiki Trickle timer does.
pub(crate) fn default(now: Instant, rand: &mut Rand) -> Self {
use super::consts::{
DEFAULT_DIO_INTERVAL_DOUBLINGS, DEFAULT_DIO_INTERVAL_MIN,
DEFAULT_DIO_REDUNDANCY_CONSTANT,
};
Self::new(
DEFAULT_DIO_INTERVAL_MIN,
DEFAULT_DIO_INTERVAL_MIN + DEFAULT_DIO_INTERVAL_DOUBLINGS,
DEFAULT_DIO_REDUNDANCY_CONSTANT,
now,
rand,
)
}
/// Create a new Trickle timer.
pub(crate) fn new(i_min: u32, i_max: u32, k: usize, now: Instant, rand: &mut Rand) -> Self {
let mut timer = Self {
i_min,
i_max,
k,
i: Duration::ZERO,
t: Duration::ZERO,
t_exp: Instant::ZERO,
i_exp: Instant::ZERO,
counter: 0,
};
timer.i = Duration::from_millis(2u32.pow(timer.i_min) as u64);
timer.i_exp = now + timer.i;
timer.counter = 0;
timer.set_t(now, rand);
timer
}
/// Poll the Trickle timer. Returns `true` when the Trickle timer signals that a message can be
/// transmitted. This happens when the Trickle timer expires.
pub(crate) fn poll(&mut self, now: Instant, rand: &mut Rand) -> bool {
let can_transmit = self.can_transmit() && self.t_expired(now);
if can_transmit {
self.set_t(now, rand);
}
if self.i_expired(now) {
self.expire(now, rand);
}
can_transmit
}
/// Returns the Instant at which the Trickle timer should be polled again. Polling the Trickle
/// timer before this Instant is not harmfull, however, polling after it is not correct.
pub(crate) fn poll_at(&self) -> Instant {
self.t_exp.min(self.i_exp)
}
/// Signal the Trickle timer that a consistency has been heard, and thus increasing it's
/// counter.
pub(crate) fn hear_consistent(&mut self) {
self.counter += 1;
}
/// Signal the Trickle timer that an inconsistency has been heard. This resets the Trickle
/// timer when the current interval is not the smallest possible.
pub(crate) fn hear_inconsistency(&mut self, now: Instant, rand: &mut Rand) {
let i = Duration::from_millis(2u32.pow(self.i_min) as u64);
if self.i > i {
self.reset(i, now, rand);
}
}
/// Check if the Trickle timer can transmit or not. Returns `false` when the consistency
/// counter is bigger or equal to the default consistency constant.
pub(crate) fn can_transmit(&self) -> bool {
self.k != 0 && self.counter < self.k
}
/// Reset the Trickle timer when the interval has expired.
fn expire(&mut self, now: Instant, rand: &mut Rand) {
let max_interval = Duration::from_millis(2u32.pow(self.i_max) as u64);
let i = if self.i >= max_interval {
max_interval
} else {
self.i + self.i
};
self.reset(i, now, rand);
}
pub(crate) fn reset(&mut self, i: Duration, now: Instant, rand: &mut Rand) {
self.i = i;
self.i_exp = now + self.i;
self.counter = 0;
self.set_t(now, rand);
}
pub(crate) const fn max_expiration(&self) -> Duration {
Duration::from_millis(2u32.pow(self.i_max) as u64)
}
pub(crate) const fn min_expiration(&self) -> Duration {
Duration::from_millis(2u32.pow(self.i_min) as u64)
}
fn set_t(&mut self, now: Instant, rand: &mut Rand) {
let t = Duration::from_micros(
self.i.total_micros() / 2
+ (rand.rand_u32() as u64
% (self.i.total_micros() - self.i.total_micros() / 2 + 1)),
);
self.t = t;
self.t_exp = now + t;
}
fn t_expired(&self, now: Instant) -> bool {
now >= self.t_exp
}
fn i_expired(&self, now: Instant) -> bool {
now >= self.i_exp
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn trickle_timer_intervals() {
let mut rand = Rand::new(1234);
let mut now = Instant::ZERO;
let mut trickle = TrickleTimer::default(now, &mut rand);
let mut previous_i = trickle.i;
while now <= Instant::from_secs(100_000) {
trickle.poll(now, &mut rand);
if now < Instant::ZERO + trickle.max_expiration() {
// t should always be inbetween I/2 and I.
assert!(trickle.i / 2 < trickle.t);
assert!(trickle.i > trickle.t);
}
if previous_i != trickle.i {
// When a new Interval is selected, this should be double the previous one.
assert_eq!(previous_i * 2, trickle.i);
assert_eq!(trickle.counter, 0);
previous_i = trickle.i;
}
now += Duration::from_millis(100);
}
}
#[test]
fn trickle_timer_hear_inconsistency() {
let mut rand = Rand::new(1234);
let mut now = Instant::ZERO;
let mut trickle = TrickleTimer::default(now, &mut rand);
trickle.counter = 1;
while now <= Instant::from_secs(10_000) {
trickle.poll(now, &mut rand);
if now < trickle.i_exp && now < Instant::ZERO + trickle.min_expiration() {
assert_eq!(trickle.counter, 1);
} else {
// The first interval expired, so the counter is reset.
assert_eq!(trickle.counter, 0);
}
if now == Instant::from_secs(10) {
// We set the counter to 1 such that we can test the `hear_inconsistency`.
trickle.counter = 1;
assert_eq!(trickle.counter, 1);
trickle.hear_inconsistency(now, &mut rand);
assert_eq!(trickle.counter, 0);
assert_eq!(trickle.i, trickle.min_expiration());
}
now += Duration::from_millis(100);
}
}
#[test]
fn trickle_timer_hear_consistency() {
let mut rand = Rand::new(1234);
let mut now = Instant::ZERO;
let mut trickle = TrickleTimer::default(now, &mut rand);
trickle.counter = 1;
let mut transmit_counter = 0;
while now <= Instant::from_secs(10_000) {
trickle.hear_consistent();
if trickle.poll(now, &mut rand) {
transmit_counter += 1;
}
if now == Instant::from_secs(10_000) {
use super::super::consts::{
DEFAULT_DIO_INTERVAL_DOUBLINGS, DEFAULT_DIO_REDUNDANCY_CONSTANT,
};
assert!(!trickle.poll(now, &mut rand));
assert!(trickle.counter > DEFAULT_DIO_REDUNDANCY_CONSTANT);
// We should never have transmitted since the counter was higher than the default
// redundancy constant.
assert_eq!(transmit_counter, 0);
}
now += Duration::from_millis(100);
}
}
}