Skip to main content

qualia_core_db/net/qdnf/route/
hysteresis.rs

1//! E08.5 — hold-down, hysteresis, and repair. Alternating ads must not flap.
2
3use crate::net::qdnf::errors::QdnfError;
4
5use super::constraints::{path_feasible, PathConstraint};
6use super::select::CandidatePath;
7
8/// Replacement policy. Hold-down is in unix seconds; improve deltas are strict.
9#[repr(C)]
10#[derive(Clone, Copy, Debug, PartialEq, Eq)]
11pub struct HysteresisPolicy {
12    pub hold_down_unix: u64,
13    /// Replacement cost must be at least this much lower.
14    pub improve_cost_threshold: u16,
15    /// Replacement additive latency must be at least this many ms lower.
16    pub improve_latency_ms: u32,
17}
18
19impl HysteresisPolicy {
20    pub const STRICT: Self = Self {
21        hold_down_unix: 60,
22        improve_cost_threshold: 1,
23        improve_latency_ms: 1,
24    };
25}
26
27fn usable(path: &CandidatePath) -> bool {
28    path.hop_len > 0 && path.is_simple()
29}
30
31fn meets_improve(
32    current: &CandidatePath,
33    candidate: &CandidatePath,
34    policy: &HysteresisPolicy,
35) -> bool {
36    let cost_delta = current.metrics.cost.saturating_sub(candidate.metrics.cost);
37    let lat_delta = current
38        .metrics
39        .latency_ms
40        .saturating_sub(candidate.metrics.latency_ms);
41    let cost_ok = candidate.metrics.cost < current.metrics.cost
42        && cost_delta >= policy.improve_cost_threshold;
43    let lat_ok = candidate.metrics.latency_ms < current.metrics.latency_ms
44        && lat_delta >= policy.improve_latency_ms;
45    cost_ok || lat_ok
46}
47
48/// Keep `current` unless it is unusable or a replacement meets threshold after hold-down.
49pub fn should_replace(
50    current: &CandidatePath,
51    candidate: &CandidatePath,
52    policy: &HysteresisPolicy,
53    now_unix: u64,
54    last_change_unix: u64,
55) -> bool {
56    if !usable(candidate) {
57        return false;
58    }
59    if !usable(current) {
60        return true;
61    }
62    if current.first_hop == candidate.first_hop && current.dest == candidate.dest {
63        return false;
64    }
65    if now_unix.saturating_sub(last_change_unix) < policy.hold_down_unix {
66        return false;
67    }
68    meets_improve(current, candidate, policy)
69}
70
71/// Constraint-aware repair: infeasible current is replaced immediately.
72pub fn decide_replace(
73    current: &CandidatePath,
74    candidate: &CandidatePath,
75    constraint: &PathConstraint,
76    policy: &HysteresisPolicy,
77    now_unix: u64,
78    last_change_unix: u64,
79) -> bool {
80    let current_ok = usable(current) && path_feasible(&current.metrics, constraint).is_ok();
81    let cand_ok = usable(candidate) && path_feasible(&candidate.metrics, constraint).is_ok();
82    if !current_ok {
83        return cand_ok;
84    }
85    should_replace(current, candidate, policy, now_unix, last_change_unix)
86}
87
88/// After [`super::plan::plan_routes`], keep `current` unless repair/hysteresis switches.
89pub fn hold_planned_routes(
90    current: &CandidatePath,
91    planned: &[CandidatePath],
92    constraint: &PathConstraint,
93    policy: &HysteresisPolicy,
94    now_unix: u64,
95    last_change_unix: u64,
96    out: &mut [CandidatePath],
97) -> Result<usize, QdnfError> {
98    if out.is_empty() {
99        return Err(QdnfError::Capacity);
100    }
101    let mut alt = CandidatePath::EMPTY;
102    let mut have_alt = false;
103    let mut i = 0usize;
104    while i < planned.len() {
105        let p = planned[i];
106        if usable(&p)
107            && (p.first_hop != current.first_hop || p.dest != current.dest)
108            && path_feasible(&p.metrics, constraint).is_ok()
109        {
110            alt = p;
111            have_alt = true;
112            break;
113        }
114        i += 1;
115    }
116    let switch = if have_alt {
117        decide_replace(
118            current,
119            &alt,
120            constraint,
121            policy,
122            now_unix,
123            last_change_unix,
124        )
125    } else {
126        !usable(current) || path_feasible(&current.metrics, constraint).is_err()
127    };
128    let mut n = 0usize;
129    if switch && have_alt {
130        out[0] = alt;
131        n = 1;
132        i = 0;
133        while i < planned.len() && n < out.len() {
134            let p = planned[i];
135            if usable(&p) && (p.first_hop != alt.first_hop || p.dest != alt.dest) {
136                out[n] = p;
137                n += 1;
138            }
139            i += 1;
140        }
141        return Ok(n);
142    }
143    if usable(current) && path_feasible(&current.metrics, constraint).is_ok() {
144        out[0] = *current;
145        n = 1;
146        i = 0;
147        while i < planned.len() && n < out.len() {
148            let p = planned[i];
149            if usable(&p) && (p.first_hop != current.first_hop || p.dest != current.dest) {
150                out[n] = p;
151                n += 1;
152            }
153            i += 1;
154        }
155        return Ok(n);
156    }
157    i = 0;
158    while i < planned.len() && n < out.len() {
159        if usable(&planned[i]) {
160            out[n] = planned[i];
161            n += 1;
162        }
163        i += 1;
164    }
165    if n == 0 {
166        Err(QdnfError::NoRoute)
167    } else {
168        Ok(n)
169    }
170}
171
172/// Compact next-hop that withdrew. `last_down_unix == 0` means not held.
173#[repr(C)]
174#[derive(Clone, Copy, Debug, PartialEq, Eq)]
175pub struct HopHoldDown {
176    pub hop: u8,
177    pub last_down_unix: u64,
178}
179
180impl HopHoldDown {
181    pub const EMPTY: Self = Self {
182        hop: 0,
183        last_down_unix: 0,
184    };
185}
186
187/// True while `now` is still inside the hold-down window after withdrawal.
188pub fn hop_is_held_down(entry: &HopHoldDown, now_unix: u64, policy: &HysteresisPolicy) -> bool {
189    if entry.hop == 0 || entry.last_down_unix == 0 {
190        return false;
191    }
192    now_unix.saturating_sub(entry.last_down_unix) < policy.hold_down_unix
193}
194
195fn first_hop_held(
196    first_hop: u8,
197    held: &[HopHoldDown],
198    now_unix: u64,
199    policy: &HysteresisPolicy,
200) -> bool {
201    let mut i = 0usize;
202    while i < held.len() {
203        if held[i].hop == first_hop && hop_is_held_down(&held[i], now_unix, policy) {
204            return true;
205        }
206        i += 1;
207    }
208    false
209}
210
211/// Drop planned paths whose first hop is still in hold-down after a flap.
212pub fn suppress_held_hops(
213    planned: &[CandidatePath],
214    held: &[HopHoldDown],
215    policy: &HysteresisPolicy,
216    now_unix: u64,
217    out: &mut [CandidatePath],
218) -> usize {
219    let mut n = 0usize;
220    let mut i = 0usize;
221    while i < planned.len() && n < out.len() {
222        let p = planned[i];
223        if usable(&p) && !first_hop_held(p.first_hop, held, now_unix, policy) {
224            out[n] = p;
225            n += 1;
226        }
227        i += 1;
228    }
229    n
230}
231
232/// Partition heal: suppress held-down first hops, then apply replacement hysteresis.
233///
234/// A flapping hop cannot rejoin merely because `current` became unusable. After
235/// the timer, [`hold_planned_routes`] may admit it again.
236pub fn admit_healed_routes(
237    current: &CandidatePath,
238    planned: &[CandidatePath],
239    held: &[HopHoldDown],
240    constraint: &PathConstraint,
241    policy: &HysteresisPolicy,
242    now_unix: u64,
243    last_change_unix: u64,
244    out: &mut [CandidatePath],
245) -> Result<usize, QdnfError> {
246    if out.is_empty() {
247        return Err(QdnfError::Capacity);
248    }
249    let mut filtered = [CandidatePath::EMPTY; 16];
250    let n_f = suppress_held_hops(planned, held, policy, now_unix, &mut filtered);
251    let effective = if first_hop_held(current.first_hop, held, now_unix, policy) {
252        CandidatePath::EMPTY
253    } else {
254        *current
255    };
256    if n_f == 0 {
257        if usable(&effective) && path_feasible(&effective.metrics, constraint).is_ok() {
258            out[0] = effective;
259            return Ok(1);
260        }
261        return Err(QdnfError::NoRoute);
262    }
263    hold_planned_routes(
264        &effective,
265        &filtered[..n_f],
266        constraint,
267        policy,
268        now_unix,
269        last_change_unix,
270        out,
271    )
272}
273
274#[cfg(test)]
275mod tests {
276    use super::*;
277    use crate::net::qdnf::route::select::{pareto_select, PathMetrics};
278
279    fn cand(
280        first: u8,
281        dest: u8,
282        cost: u16,
283        lat: u32,
284        energy: u32,
285        known: bool,
286        dom: u8,
287    ) -> CandidatePath {
288        let mut p = CandidatePath::EMPTY;
289        p.first_hop = first;
290        p.dest = dest;
291        p.hop_len = 1;
292        p.hops[0] = first;
293        p.metrics = PathMetrics {
294            cost,
295            latency_ms: lat,
296            energy_uj: energy,
297            energy_known: known,
298            failure_domain: dom,
299        };
300        p
301    }
302
303    fn cheap() -> CandidatePath {
304        cand(2, 9, 1, 100, 1, true, 1)
305    }
306
307    fn fast() -> CandidatePath {
308        cand(3, 9, 100, 1, 1, true, 2)
309    }
310
311    #[test]
312    fn hold_down_prevents_oscillation() {
313        let policy = HysteresisPolicy::STRICT;
314        let mut current = cheap();
315        let mut last = 0u64;
316        let mut t = 1u64;
317        while t < 60 {
318            let next = if t % 2 == 1 { fast() } else { cheap() };
319            if should_replace(&current, &next, &policy, t, last) {
320                current = next;
321                last = t;
322            }
323            t += 1;
324        }
325        assert_eq!(current.first_hop, cheap().first_hop);
326        assert_eq!(last, 0);
327        assert!(!should_replace(&cheap(), &fast(), &policy, 59, 0));
328        assert!(should_replace(&cheap(), &fast(), &policy, 60, 0));
329    }
330
331    #[test]
332    fn infeasible_current_is_replaced_immediately() {
333        let policy = HysteresisPolicy::STRICT;
334        let current = cand(2, 9, 100, 100, 1, true, 1);
335        let candidate = cand(3, 9, 10, 10, 1, true, 2);
336        let constraint = PathConstraint {
337            permitted_realms: u64::MAX,
338            min_profile: 0,
339            max_cost: 20,
340            deadline_ms: 0,
341            require_loop_free: true,
342            max_energy_uj: 0,
343        };
344        assert_eq!(
345            path_feasible(&current.metrics, &constraint),
346            Err(QdnfError::Denied)
347        );
348        assert!(path_feasible(&candidate.metrics, &constraint).is_ok());
349        assert!(!should_replace(&current, &candidate, &policy, 1, 0));
350        assert!(decide_replace(
351            &current,
352            &candidate,
353            &constraint,
354            &policy,
355            1,
356            0
357        ));
358        let mut out = [CandidatePath::EMPTY; 3];
359        let n = hold_planned_routes(&current, &[candidate], &constraint, &policy, 1, 0, &mut out)
360            .unwrap();
361        assert_eq!(n, 1);
362        assert_eq!(out[0].first_hop, 3);
363    }
364
365    #[test]
366    fn distinct_failure_domain_preferred() {
367        let cands = [
368            cand(2, 9, 10, 40, 1, true, 1),
369            cand(3, 9, 40, 10, 1, true, 1),
370            cand(4, 9, 20, 30, 1, true, 2),
371        ];
372        let mut out = [CandidatePath::EMPTY; 2];
373        let n = pareto_select(&cands, &mut out).unwrap();
374        assert_eq!(n, 2);
375        assert_ne!(out[0].metrics.failure_domain, out[1].metrics.failure_domain);
376    }
377
378    #[test]
379    fn held_down_first_hop_cannot_rejoin_during_timer() {
380        let policy = HysteresisPolicy::STRICT;
381        let current = CandidatePath::EMPTY;
382        let flap = cheap();
383        let held = [HopHoldDown {
384            hop: flap.first_hop,
385            last_down_unix: 10,
386        }];
387        let constraint = PathConstraint::UNRESTRICTED;
388        let mut out = [CandidatePath::EMPTY; 3];
389        assert!(hop_is_held_down(&held[0], 11, &policy));
390        assert_eq!(
391            admit_healed_routes(
392                &current,
393                &[flap],
394                &held,
395                &constraint,
396                &policy,
397                11,
398                10,
399                &mut out
400            ),
401            Err(QdnfError::NoRoute)
402        );
403        assert!(!hop_is_held_down(&held[0], 70, &policy));
404        let n = admit_healed_routes(
405            &current,
406            &[flap],
407            &held,
408            &constraint,
409            &policy,
410            70,
411            10,
412            &mut out,
413        )
414        .unwrap();
415        assert_eq!(n, 1);
416        assert_eq!(out[0].first_hop, flap.first_hop);
417    }
418
419    #[test]
420    fn alternate_not_held_is_used_while_flap_is_suppressed() {
421        let policy = HysteresisPolicy::STRICT;
422        let current = CandidatePath::EMPTY;
423        let flap = cheap();
424        let alt = fast();
425        let held = [HopHoldDown {
426            hop: flap.first_hop,
427            last_down_unix: 1,
428        }];
429        let mut out = [CandidatePath::EMPTY; 3];
430        let n = admit_healed_routes(
431            &current,
432            &[flap, alt],
433            &held,
434            &PathConstraint::UNRESTRICTED,
435            &policy,
436            2,
437            1,
438            &mut out,
439        )
440        .unwrap();
441        assert_eq!(n, 1);
442        assert_eq!(out[0].first_hop, alt.first_hop);
443        assert_ne!(out[0].first_hop, flap.first_hop);
444    }
445}