Skip to main content

qualia_core_db/net/qdnf/route/
plan.rs

1//! Production route planner. Feasibility first; never auto-publishes forwarding.
2
3use 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
12/// Plan at most three feasible next hops from `origin` to `dest`.
13///
14/// Does not publish [`super::forwarding::ForwardingGeneration`]. Callers publish
15/// only after this returns successfully.
16pub 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}