1use crate::net::qdnf::errors::QdnfError;
4
5use super::constraints::{path_feasible, PathConstraint};
6use super::select::CandidatePath;
7
8#[repr(C)]
10#[derive(Clone, Copy, Debug, PartialEq, Eq)]
11pub struct HysteresisPolicy {
12 pub hold_down_unix: u64,
13 pub improve_cost_threshold: u16,
15 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
48pub 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
71pub 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(¤t.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
88pub 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(¤t.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(¤t.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#[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
187pub 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
211pub 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
232pub 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(¤t, &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(¤t.metrics, &constraint),
346 Err(QdnfError::Denied)
347 );
348 assert!(path_feasible(&candidate.metrics, &constraint).is_ok());
349 assert!(!should_replace(¤t, &candidate, &policy, 1, 0));
350 assert!(decide_replace(
351 ¤t,
352 &candidate,
353 &constraint,
354 &policy,
355 1,
356 0
357 ));
358 let mut out = [CandidatePath::EMPTY; 3];
359 let n = hold_planned_routes(¤t, &[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 ¤t,
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 ¤t,
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 ¤t,
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}