Skip to main content

qualia_core_db/net/qdnf/route/
select.rs

1//! Pareto selection of at most three next hops. Metrics stay independently typed.
2
3use crate::net::qdnf::errors::QdnfError;
4pub use crate::net::qdnf::resolve::records::{
5    project_rar_to_network_quins, select_routes, RarKeyRole, ResolveOutcome, RouteAdvert,
6    VerifiedRar, MAX_RAR_ROUTES,
7};
8
9pub const MAX_PATH_HOPS: usize = 16;
10pub const MAX_SELECTED: usize = 3;
11pub const MAX_PARETO_IN: usize = 16;
12
13/// Independently typed path metrics. Do not collapse these into one scalar.
14#[repr(C)]
15#[derive(Clone, Copy, Debug, PartialEq, Eq)]
16pub struct PathMetrics {
17    pub cost: u16,
18    /// Additive latency bound. Not an end-to-end p95.
19    pub latency_ms: u32,
20    /// `0` with `energy_known == false` is unknown, not free.
21    pub energy_uj: u32,
22    pub energy_known: bool,
23    pub failure_domain: u8,
24}
25
26impl PathMetrics {
27    pub const EMPTY: Self = Self {
28        cost: 0,
29        latency_ms: 0,
30        energy_uj: 0,
31        energy_known: true,
32        failure_domain: 0,
33    };
34}
35
36#[repr(C)]
37#[derive(Clone, Copy, Debug, PartialEq, Eq)]
38pub struct CandidatePath {
39    pub dest: u8,
40    pub first_hop: u8,
41    pub hops: [u8; MAX_PATH_HOPS],
42    pub hop_len: u8,
43    pub metrics: PathMetrics,
44}
45
46impl CandidatePath {
47    pub const EMPTY: Self = Self {
48        dest: 0,
49        first_hop: 0,
50        hops: [0; MAX_PATH_HOPS],
51        hop_len: 0,
52        metrics: PathMetrics::EMPTY,
53    };
54
55    /// `true` when `simple`.
56    pub fn is_simple(&self) -> bool {
57        let n = self.hop_len as usize;
58        if n > MAX_PATH_HOPS {
59            return false;
60        }
61        let mut i = 0usize;
62        while i < n {
63            let mut j = i + 1;
64            while j < n {
65                if self.hops[i] == self.hops[j] {
66                    return false;
67                }
68                j += 1;
69            }
70            i += 1;
71        }
72        true
73    }
74}
75
76fn dominates(a: &CandidatePath, b: &CandidatePath) -> bool {
77    let mut strict = false;
78    if a.metrics.cost > b.metrics.cost {
79        return false;
80    }
81    if a.metrics.cost < b.metrics.cost {
82        strict = true;
83    }
84    if a.metrics.latency_ms > b.metrics.latency_ms {
85        return false;
86    }
87    if a.metrics.latency_ms < b.metrics.latency_ms {
88        strict = true;
89    }
90    if a.metrics.energy_known && b.metrics.energy_known {
91        if a.metrics.energy_uj > b.metrics.energy_uj {
92            return false;
93        }
94        if a.metrics.energy_uj < b.metrics.energy_uj {
95            strict = true;
96        }
97    }
98    strict
99}
100
101fn better_tie(a: &CandidatePath, b: &CandidatePath) -> bool {
102    if a.first_hop != b.first_hop {
103        return a.first_hop < b.first_hop;
104    }
105    a.dest < b.dest
106}
107
108/// Remove B only when A is no worse on every comparable metric and strictly better
109/// on at least one. At most three results; prefer distinct failure domains.
110pub fn pareto_select(
111    candidates: &[CandidatePath],
112    out: &mut [CandidatePath],
113) -> Result<usize, QdnfError> {
114    if out.is_empty() {
115        return Err(QdnfError::Capacity);
116    }
117    let n_in = candidates.len();
118    if n_in > MAX_PARETO_IN {
119        return Err(QdnfError::Capacity);
120    }
121    let mut keep = [false; MAX_PARETO_IN];
122    let mut i = 0usize;
123    while i < n_in {
124        if !candidates[i].is_simple() {
125            i += 1;
126            continue;
127        }
128        let mut dominated = false;
129        let mut j = 0usize;
130        while j < n_in {
131            if i != j && candidates[j].is_simple() && dominates(&candidates[j], &candidates[i]) {
132                dominated = true;
133                break;
134            }
135            j += 1;
136        }
137        keep[i] = !dominated;
138        i += 1;
139    }
140    let mut tmp = [CandidatePath::EMPTY; MAX_PARETO_IN];
141    let mut m = 0usize;
142    i = 0;
143    while i < n_in {
144        if keep[i] {
145            tmp[m] = candidates[i];
146            m += 1;
147        }
148        i += 1;
149    }
150    i = 0;
151    while i < m {
152        let mut best = i;
153        let mut k = i + 1;
154        while k < m {
155            if better_tie(&tmp[k], &tmp[best]) {
156                best = k;
157            }
158            k += 1;
159        }
160        tmp.swap(i, best);
161        i += 1;
162    }
163    let cap = out.len().min(MAX_SELECTED);
164    let mut used_domain = [false; 256];
165    let mut n = 0usize;
166    i = 0;
167    while i < m && n < cap {
168        let d = tmp[i].metrics.failure_domain as usize;
169        if !used_domain[d] {
170            out[n] = tmp[i];
171            used_domain[d] = true;
172            n += 1;
173        }
174        i += 1;
175    }
176    i = 0;
177    while i < m && n < cap {
178        let mut already = false;
179        let mut k = 0usize;
180        while k < n {
181            if out[k].first_hop == tmp[i].first_hop && out[k].dest == tmp[i].dest {
182                already = true;
183                break;
184            }
185            k += 1;
186        }
187        if !already {
188            out[n] = tmp[i];
189            n += 1;
190        }
191        i += 1;
192    }
193    Ok(n)
194}
195
196#[cfg(test)]
197mod tests {
198    use super::*;
199
200    fn cand(
201        first: u8,
202        dest: u8,
203        cost: u16,
204        lat: u32,
205        energy: u32,
206        known: bool,
207        dom: u8,
208    ) -> CandidatePath {
209        let mut p = CandidatePath::EMPTY;
210        p.first_hop = first;
211        p.dest = dest;
212        p.hop_len = 1;
213        p.hops[0] = first;
214        p.metrics = PathMetrics {
215            cost,
216            latency_ms: lat,
217            energy_uj: energy,
218            energy_known: known,
219            failure_domain: dom,
220        };
221        p
222    }
223
224    #[test]
225    fn route_d_dominated_candidate_dropped() {
226        let cands = [
227            cand(2, 9, 10, 10, 10, true, 1),
228            cand(3, 9, 20, 20, 20, true, 2),
229            cand(4, 9, 5, 5, 5, true, 3),
230        ];
231        let mut out = [CandidatePath::EMPTY; 4];
232        let n = pareto_select(&cands, &mut out).unwrap();
233        assert_eq!(n, 1);
234        assert_eq!(out[0].first_hop, 4);
235    }
236
237    #[test]
238    fn route_d_at_most_three_results() {
239        let cands = [
240            cand(1, 9, 10, 40, 1, true, 1),
241            cand(2, 9, 20, 30, 1, true, 2),
242            cand(3, 9, 30, 20, 1, true, 3),
243            cand(4, 9, 40, 10, 1, true, 4),
244        ];
245        let mut out = [CandidatePath::EMPTY; 8];
246        let n = pareto_select(&cands, &mut out).unwrap();
247        assert_eq!(n, 3);
248        assert_eq!(out[0].first_hop, 1);
249        assert_eq!(out[1].first_hop, 2);
250        assert_eq!(out[2].first_hop, 3);
251    }
252
253    #[test]
254    fn equal_metrics_tie_break_lower_first_hop() {
255        let cands = [
256            cand(5, 9, 10, 10, 10, true, 1),
257            cand(2, 9, 10, 10, 10, true, 2),
258        ];
259        let mut out = [CandidatePath::EMPTY; 3];
260        let n = pareto_select(&cands, &mut out).unwrap();
261        assert_eq!(n, 2);
262        assert_eq!(out[0].first_hop, 2);
263        assert_eq!(out[1].first_hop, 5);
264    }
265
266    #[test]
267    fn looping_path_is_dropped() {
268        let mut looped = cand(2, 9, 1, 1, 1, true, 1);
269        looped.hop_len = 3;
270        looped.hops = [2, 3, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
271        let ok = cand(4, 9, 8, 8, 8, true, 2);
272        let mut out = [CandidatePath::EMPTY; 3];
273        let n = pareto_select(&[looped, ok], &mut out).unwrap();
274        assert_eq!(n, 1);
275        assert_eq!(out[0].first_hop, 4);
276    }
277
278    #[test]
279    fn empty_out_is_capacity() {
280        let cands = [cand(1, 2, 1, 1, 1, true, 1)];
281        let mut out: [CandidatePath; 0] = [];
282        assert_eq!(pareto_select(&cands, &mut out), Err(QdnfError::Capacity));
283    }
284
285    #[test]
286    fn select_routes_and_rar_quin_projection_roundtrip_via_route_select() {
287        use crate::net::qdnf::types::{DniCoordinate, StrongDigest};
288        use crate::NQuin;
289
290        let mut target = StrongDigest::ZERO;
291        target.0[0] = 0x42;
292        let adv = RouteAdvert {
293            target,
294            dni: DniCoordinate {
295                network_id: 1,
296                realm_id: 1,
297                node_id: 2,
298                service_id: 3,
299            },
300            not_before_unix: 10,
301            expires_unix: 100,
302            sequence: 4,
303            key_role: RarKeyRole::RouteUpdate,
304        };
305        let mut out = [adv; 4];
306        let (n, outcome) = select_routes(&target, &[adv], 50, &mut out).unwrap();
307        assert_eq!(n, 1);
308        assert_eq!(outcome, ResolveOutcome::Routes);
309
310        let mut routes = [DniCoordinate::ZERO; MAX_RAR_ROUTES];
311        routes[0] = adv.dni;
312        let rar = VerifiedRar {
313            rar_digest: StrongDigest([0x11; 48]),
314            target_digest: target,
315            signer_digest: StrongDigest([0x22; 48]),
316            key_role: RarKeyRole::CapabilityInvocation,
317            sequence: 4,
318            route_epoch: 3,
319            issued_at_unix: 10,
320            expires_at_unix: 100,
321            routes,
322            route_count: 1,
323        };
324        let mut quins = [NQuin::default(); 4];
325        let qn = project_rar_to_network_quins(&rar, &mut quins);
326        assert_eq!(qn, 2);
327        assert!(quins[0].verify_ecc_parity());
328        assert!(quins[1].verify_ecc_parity());
329    }
330}