1use crate::net::qdnf::errors::QdnfError;
4
5use super::constraints::{edge_feasible, path_feasible, PathConstraint};
6use super::index::{AdjacencyIndex, MAX_ADMITTED_EDGES};
7use super::select::{pareto_select, CandidatePath, PathMetrics, MAX_PARETO_IN, MAX_PATH_HOPS};
8use super::validate::ValidatedEdge;
9
10const MAX_NODES: usize = 256;
11
12pub fn plan_routes(
17 index: &AdjacencyIndex,
18 origin: u8,
19 dest: u8,
20 constraint: &PathConstraint,
21 now_unix: u64,
22 out: &mut [CandidatePath],
23) -> Result<usize, QdnfError> {
24 if out.is_empty() {
25 return Err(QdnfError::Capacity);
26 }
27 if origin == 0 || dest == 0 {
28 return Err(QdnfError::Range);
29 }
30 if origin == dest {
31 out[0] = CandidatePath::EMPTY;
32 out[0].dest = dest;
33 out[0].first_hop = origin;
34 return Ok(1);
35 }
36
37 let mut live = [ValidatedEdge::EMPTY; MAX_ADMITTED_EDGES];
38 let n_live = index.live_edges(now_unix, &mut live);
39 if n_live == 0 {
40 return Err(QdnfError::NoRoute);
41 }
42
43 let mut topo_reach = false;
44 let mut gen = [CandidatePath::EMPTY; MAX_PARETO_IN];
45 let mut n_gen = 0usize;
46
47 let mut neigh = 1u8;
48 loop {
49 if n_gen >= MAX_PARETO_IN {
50 break;
51 }
52 if let Some(edge) = directed_edge(&live[..n_live], origin, neigh) {
53 match first_hop_path(
54 &live[..n_live],
55 origin,
56 neigh,
57 dest,
58 edge,
59 constraint,
60 now_unix,
61 ) {
62 Ok(path) => {
63 topo_reach = true;
64 gen[n_gen] = path;
65 n_gen += 1;
66 }
67 Err(QdnfError::NoRoute) => {}
68 Err(QdnfError::Denied) | Err(QdnfError::Incomplete) => {
69 if reachable(&live[..n_live], origin, neigh, dest, now_unix) {
70 topo_reach = true;
71 }
72 }
73 Err(e) => return Err(e),
74 }
75 }
76 if neigh == 255 {
77 break;
78 }
79 neigh += 1;
80 }
81
82 if n_gen == 0 {
83 return Err(if topo_reach {
84 QdnfError::Denied
85 } else {
86 QdnfError::NoRoute
87 });
88 }
89
90 let n = pareto_select(&gen[..n_gen], out)?;
91 if n == 0 {
92 if topo_reach {
93 Err(QdnfError::Denied)
94 } else {
95 Err(QdnfError::NoRoute)
96 }
97 } else {
98 Ok(n)
99 }
100}
101
102fn directed_edge(live: &[ValidatedEdge], from: u8, to: u8) -> Option<ValidatedEdge> {
103 let mut i = 0usize;
104 while i < live.len() {
105 let e = live[i];
106 if e.from == from && e.to == to {
107 return Some(e);
108 }
109 if e.bidirectional && e.to == from && e.from == to {
110 return Some(e);
111 }
112 i += 1;
113 }
114 None
115}
116
117fn first_hop_path(
118 live: &[ValidatedEdge],
119 origin: u8,
120 hop: u8,
121 dest: u8,
122 first: ValidatedEdge,
123 constraint: &PathConstraint,
124 now_unix: u64,
125) -> Result<CandidatePath, QdnfError> {
126 if now_unix >= first.expiry_unix || first.withdrawn {
127 return Err(QdnfError::NoRoute);
128 }
129 match edge_feasible(&first, constraint) {
130 Ok(()) => {}
131 Err(QdnfError::Denied) | Err(QdnfError::Incomplete) | Err(QdnfError::Revoked) => {
132 return Err(QdnfError::Denied);
133 }
134 Err(e) => return Err(e),
135 }
136 let mut path = CandidatePath::EMPTY;
137 path.dest = dest;
138 path.first_hop = hop;
139 path.hops[0] = hop;
140 path.hop_len = 1;
141 path.metrics = PathMetrics {
142 cost: first.cost,
143 latency_ms: first.latency_ms,
144 energy_uj: first.energy_uj,
145 energy_known: first.energy_known,
146 failure_domain: first.failure_domain,
147 };
148 if hop == dest {
149 path_feasible(&path.metrics, constraint).map_err(map_budget)?;
150 return Ok(path);
151 }
152 dijkstra_continue(live, origin, hop, dest, constraint, now_unix, &mut path)?;
153 path_feasible(&path.metrics, constraint).map_err(map_budget)?;
154 if constraint.require_loop_free && !path.is_simple() {
155 return Err(QdnfError::Denied);
156 }
157 Ok(path)
158}
159
160fn map_budget(err: QdnfError) -> QdnfError {
161 match err {
162 QdnfError::Incomplete => QdnfError::Incomplete,
163 _ => QdnfError::Denied,
164 }
165}
166
167fn dijkstra_continue(
168 live: &[ValidatedEdge],
169 origin: u8,
170 start: u8,
171 dest: u8,
172 constraint: &PathConstraint,
173 now_unix: u64,
174 path: &mut CandidatePath,
175) -> Result<(), QdnfError> {
176 let mut dist = [u16::MAX; MAX_NODES];
177 let mut lat = [u32::MAX; MAX_NODES];
178 let mut energy = [u32::MAX; MAX_NODES];
179 let mut known = [false; MAX_NODES];
180 let mut prev = [u8::MAX; MAX_NODES];
181 let mut used = [false; MAX_NODES];
182 dist[start as usize] = 0;
183 lat[start as usize] = 0;
184 energy[start as usize] = 0;
185 known[start as usize] = true;
186
187 let mut step = 0usize;
188 while step < MAX_NODES {
189 let mut best = u16::MAX;
190 let mut u = usize::MAX;
191 let mut i = 0usize;
192 while i < MAX_NODES {
193 if !used[i] && dist[i] < best {
194 best = dist[i];
195 u = i;
196 } else if !used[i] && dist[i] == best && u != usize::MAX && i < u {
197 u = i;
198 }
199 i += 1;
200 }
201 if u == usize::MAX {
202 break;
203 }
204 used[u] = true;
205 if u as u8 == dest {
206 break;
207 }
208 let mut e = 0usize;
209 while e < live.len() {
210 let edge = live[e];
211 e += 1;
212 if now_unix >= edge.expiry_unix || edge.withdrawn {
213 continue;
214 }
215 let (from, to) = match directed_pair(&edge, u as u8) {
216 Some(p) => p,
217 None => continue,
218 };
219 if from != u as u8 {
220 continue;
221 }
222 if to == origin || to == start {
223 continue;
224 }
225 if edge_feasible(&edge, constraint).is_err() {
226 continue;
227 }
228 let v = to as usize;
229 let cand = match dist[u].checked_add(edge.cost) {
230 Some(c) => c,
231 None => continue,
232 };
233 let lat_c = match lat[u].checked_add(edge.latency_ms) {
234 Some(c) => c,
235 None => continue,
236 };
237 let e_known = known[u] && edge.energy_known;
238 let e_c = if e_known {
239 match energy[u].checked_add(edge.energy_uj) {
240 Some(c) => c,
241 None => continue,
242 }
243 } else {
244 energy[u]
245 };
246 if cand < dist[v] || (cand == dist[v] && (u as u8) < prev[v]) {
247 dist[v] = cand;
248 lat[v] = lat_c;
249 energy[v] = e_c;
250 known[v] = e_known;
251 prev[v] = u as u8;
252 }
253 }
254 step += 1;
255 }
256 if dist[dest as usize] == u16::MAX {
257 return Err(QdnfError::NoRoute);
258 }
259 let mut stack = [0u8; MAX_PATH_HOPS];
260 let mut sn = 0usize;
261 let mut cur = dest;
262 let mut guard = 0usize;
263 while cur != start && guard < MAX_PATH_HOPS {
264 if sn >= MAX_PATH_HOPS {
265 return Err(QdnfError::Capacity);
266 }
267 stack[sn] = cur;
268 sn += 1;
269 let p = prev[cur as usize];
270 if p == u8::MAX {
271 return Err(QdnfError::NoRoute);
272 }
273 cur = p;
274 guard += 1;
275 }
276 if cur != start {
277 return Err(QdnfError::NoRoute);
278 }
279 let mut hop_len = 1u8;
280 let mut k = sn;
281 while k > 0 {
282 k -= 1;
283 if hop_len as usize >= MAX_PATH_HOPS {
284 return Err(QdnfError::Capacity);
285 }
286 path.hops[hop_len as usize] = stack[k];
287 hop_len += 1;
288 }
289 path.hop_len = hop_len;
290 let base = path.metrics;
291 path.metrics.cost = match base.cost.checked_add(dist[dest as usize]) {
292 Some(c) => c,
293 None => return Err(QdnfError::Range),
294 };
295 path.metrics.latency_ms = match base.latency_ms.checked_add(lat[dest as usize]) {
296 Some(c) => c,
297 None => return Err(QdnfError::Range),
298 };
299 path.metrics.energy_known = base.energy_known && known[dest as usize];
300 if path.metrics.energy_known {
301 path.metrics.energy_uj = match base.energy_uj.checked_add(energy[dest as usize]) {
302 Some(c) => c,
303 None => return Err(QdnfError::Range),
304 };
305 } else {
306 path.metrics.energy_uj = 0;
307 }
308 Ok(())
309}
310
311fn directed_pair(edge: &ValidatedEdge, u: u8) -> Option<(u8, u8)> {
312 if edge.from == u {
313 Some((edge.from, edge.to))
314 } else if edge.bidirectional && edge.to == u {
315 Some((edge.to, edge.from))
316 } else {
317 None
318 }
319}
320
321fn reachable(live: &[ValidatedEdge], origin: u8, start: u8, dest: u8, now_unix: u64) -> bool {
322 if start == dest {
323 return true;
324 }
325 let mut seen = [false; MAX_NODES];
326 let mut stack = [0u8; MAX_NODES];
327 let mut sp = 1usize;
328 stack[0] = start;
329 seen[start as usize] = true;
330 seen[origin as usize] = true;
331 while sp > 0 {
332 sp -= 1;
333 let u = stack[sp];
334 let mut i = 0usize;
335 while i < live.len() {
336 let e = live[i];
337 i += 1;
338 if now_unix >= e.expiry_unix || e.withdrawn {
339 continue;
340 }
341 let to = if e.from == u {
342 e.to
343 } else if e.bidirectional && e.to == u {
344 e.from
345 } else {
346 continue;
347 };
348 if to == dest {
349 return true;
350 }
351 if !seen[to as usize] {
352 seen[to as usize] = true;
353 if sp < MAX_NODES {
354 stack[sp] = to;
355 sp += 1;
356 }
357 }
358 }
359 }
360 false
361}
362
363#[cfg(test)]
364mod tests {
365 use super::*;
366 use crate::net::qdnf::route::index::AdjacencyIndex;
367 use crate::net::qdnf::route::validate::{insert, TopologyRecord, PROFILE_P0};
368 use crate::net::qdnf::types::StrongDigest;
369
370 fn rec(origin: u8, from: u8, to: u8, seq: u32, cost: u16) -> TopologyRecord {
371 TopologyRecord {
372 origin,
373 origin_digest: {
374 let mut d = StrongDigest::ZERO;
375 d.0[0] = origin;
376 d.0[47] = 1;
377 d
378 },
379 scope: 1,
380 from,
381 to,
382 sequence: seq,
383 expiry_unix: 100,
384 withdrawn: false,
385 bidirectional: true,
386 cost,
387 latency_ms: 1,
388 energy_uj: 1,
389 energy_known: true,
390 realm_bit: 0,
391 profile: PROFILE_P0,
392 failure_domain: from,
393 digest: StrongDigest::ZERO,
394 }
395 }
396
397 #[test]
398 fn route_b_disconnected_dest_is_noroute() {
399 let mut index = AdjacencyIndex::new(1);
400 insert(&rec(1, 1, 2, 1, 1), 1, 1, None, &mut index).unwrap();
401 let mut out = [CandidatePath::EMPTY; 3];
402 assert_eq!(
403 plan_routes(&index, 1, 5, &PathConstraint::UNRESTRICTED, 1, &mut out),
404 Err(QdnfError::NoRoute)
405 );
406 }
407
408 #[test]
409 fn route_b_equal_costs_are_deterministic() {
410 let mut index = AdjacencyIndex::new(1);
411 insert(&rec(1, 1, 2, 1, 2), 1, 1, None, &mut index).unwrap();
412 insert(&rec(2, 2, 4, 1, 2), 1, 1, None, &mut index).unwrap();
413 insert(&rec(1, 1, 3, 2, 2), 1, 1, None, &mut index).unwrap();
414 insert(&rec(3, 3, 4, 1, 2), 1, 1, None, &mut index).unwrap();
415 let mut out = [CandidatePath::EMPTY; 3];
416 let n = plan_routes(&index, 1, 4, &PathConstraint::UNRESTRICTED, 1, &mut out).unwrap();
417 assert!(n >= 1);
418 assert_eq!(out[0].first_hop, 2);
419 assert_eq!(out[0].metrics.cost, 4);
420 }
421
422 #[test]
423 fn expired_edge_is_not_used() {
424 let mut index = AdjacencyIndex::new(1);
425 let mut stale = rec(1, 1, 2, 1, 1);
426 stale.expiry_unix = 5;
427 insert(&stale, 1, 1, None, &mut index).unwrap();
428 insert(&rec(1, 1, 3, 2, 9), 1, 1, None, &mut index).unwrap();
429 insert(&rec(3, 3, 2, 1, 9), 1, 1, None, &mut index).unwrap();
430 let mut out = [CandidatePath::EMPTY; 3];
431 let n = plan_routes(&index, 1, 2, &PathConstraint::UNRESTRICTED, 5, &mut out).unwrap();
432 assert_eq!(n, 1);
433 assert_eq!(out[0].first_hop, 3);
434 }
435
436 #[test]
437 fn withdrawn_edge_is_not_used() {
438 let mut index = AdjacencyIndex::new(1);
439 insert(&rec(1, 1, 2, 1, 1), 1, 1, None, &mut index).unwrap();
440 let mut w = rec(1, 1, 2, 2, 1);
441 w.withdrawn = true;
442 insert(&w, 1, 1, None, &mut index).unwrap();
443 insert(&rec(1, 1, 3, 3, 8), 1, 1, None, &mut index).unwrap();
444 insert(&rec(3, 3, 2, 1, 8), 1, 1, None, &mut index).unwrap();
445 let mut out = [CandidatePath::EMPTY; 3];
446 let n = plan_routes(&index, 1, 2, &PathConstraint::UNRESTRICTED, 1, &mut out).unwrap();
447 assert_eq!(n, 1);
448 assert_eq!(out[0].first_hop, 3);
449 assert_eq!(index.live_count(1), 2);
450 }
451
452 #[test]
453 fn unknown_energy_required_bound_not_selected() {
454 let mut index = AdjacencyIndex::new(1);
455 let mut unknown = rec(1, 1, 2, 1, 1);
456 unknown.energy_known = false;
457 unknown.energy_uj = 0;
458 insert(&unknown, 1, 1, None, &mut index).unwrap();
459 insert(&rec(1, 1, 3, 2, 20), 1, 1, None, &mut index).unwrap();
460 insert(&rec(3, 3, 2, 1, 20), 1, 1, None, &mut index).unwrap();
461 let c = PathConstraint {
462 permitted_realms: u64::MAX,
463 min_profile: 0,
464 max_cost: u16::MAX,
465 deadline_ms: 0,
466 require_loop_free: true,
467 max_energy_uj: 100,
468 };
469 let mut out = [CandidatePath::EMPTY; 3];
470 let n = plan_routes(&index, 1, 2, &c, 1, &mut out).unwrap();
471 assert_eq!(n, 1);
472 assert_eq!(out[0].first_hop, 3);
473 assert!(out[0].metrics.energy_known);
474 }
475
476 #[test]
477 fn plan_does_not_publish_forwarding() {
478 let mut index = AdjacencyIndex::new(1);
479 insert(&rec(1, 1, 2, 1, 1), 1, 1, None, &mut index).unwrap();
480 let mut out = [CandidatePath::EMPTY; 3];
481 plan_routes(&index, 1, 2, &PathConstraint::UNRESTRICTED, 1, &mut out).unwrap();
482 assert_eq!(index.published().lookup_next(2), Err(QdnfError::Incomplete));
483 }
484}