1use 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#[repr(C)]
15#[derive(Clone, Copy, Debug, PartialEq, Eq)]
16pub struct PathMetrics {
17 pub cost: u16,
18 pub latency_ms: u32,
20 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 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
108pub 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}