Skip to main content

qualia_core_db/net/qdnf/route/
ads.rs

1//! E08.6 — verified topology facts vs untrusted price/energy/latency adverts.
2
3use crate::net::qdnf::errors::QdnfError;
4
5use super::constraints::{edge_feasible, path_feasible, PathConstraint};
6use super::select::{CandidatePath, PathMetrics, MAX_PARETO_IN};
7use super::validate::ValidatedEdge;
8
9/// At most this many untrusted adverts are explored, and only among feasible paths.
10pub const MAX_EXPLORE: usize = 4;
11
12#[repr(u8)]
13#[derive(Clone, Copy, Debug, PartialEq, Eq)]
14pub enum MetricProvenance {
15    VerifiedTopology = 0,
16    UntrustedAdvert = 1,
17}
18
19#[repr(C)]
20#[derive(Clone, Copy, Debug, PartialEq, Eq)]
21pub struct AdvertisedMetric {
22    pub provenance: MetricProvenance,
23    pub cost: u16,
24    pub latency_ms: u32,
25    pub energy_uj: u32,
26    pub energy_known: bool,
27}
28
29/// Advert bound to a planned first hop. Untrusted copies never admit a new path.
30#[repr(C)]
31#[derive(Clone, Copy, Debug, PartialEq, Eq)]
32pub struct PathAdvert {
33    pub first_hop: u8,
34    pub dest: u8,
35    pub metric: AdvertisedMetric,
36}
37
38fn overlay_energy(verified: &PathMetrics, advert: &AdvertisedMetric) -> (u32, bool) {
39    if advert.energy_known {
40        (advert.energy_uj, true)
41    } else if verified.energy_known {
42        (verified.energy_uj, true)
43    } else {
44        (0, false)
45    }
46}
47
48/// Overlay advert metrics. Unknown energy stays unknown, never a free zero.
49pub fn overlay_metrics(verified: &PathMetrics, advert: &AdvertisedMetric) -> PathMetrics {
50    let (energy_uj, energy_known) = overlay_energy(verified, advert);
51    PathMetrics {
52        cost: advert.cost,
53        latency_ms: advert.latency_ms,
54        energy_uj,
55        energy_known,
56        failure_domain: verified.failure_domain,
57    }
58}
59
60fn apply_metric_fields(edge: &ValidatedEdge, advert: &AdvertisedMetric) -> ValidatedEdge {
61    let verified = PathMetrics {
62        cost: edge.cost,
63        latency_ms: edge.latency_ms,
64        energy_uj: edge.energy_uj,
65        energy_known: edge.energy_known,
66        failure_domain: edge.failure_domain,
67    };
68    let m = overlay_metrics(&verified, advert);
69    let mut e = *edge;
70    e.cost = m.cost;
71    e.latency_ms = m.latency_ms;
72    e.energy_uj = m.energy_uj;
73    e.energy_known = m.energy_known;
74    e
75}
76
77/// Untrusted ads cannot make an infeasible verified edge feasible.
78pub fn admit_advert(
79    edge: &ValidatedEdge,
80    advert: &AdvertisedMetric,
81    constraint: &PathConstraint,
82) -> Result<ValidatedEdge, QdnfError> {
83    match advert.provenance {
84        MetricProvenance::VerifiedTopology => {
85            let e = apply_metric_fields(edge, advert);
86            edge_feasible(&e, constraint)?;
87            Ok(e)
88        }
89        MetricProvenance::UntrustedAdvert => {
90            edge_feasible(edge, constraint)?;
91            Ok(apply_metric_fields(edge, advert))
92        }
93    }
94}
95
96fn matches(path: &CandidatePath, advert: &PathAdvert) -> bool {
97    path.first_hop == advert.first_hop && path.dest == advert.dest
98}
99
100fn apply_to_path(path: &mut CandidatePath, advert: &PathAdvert) {
101    path.metrics = overlay_metrics(&path.metrics, &advert.metric);
102}
103
104/// Among already-feasible paths only, consider at most [`MAX_EXPLORE`] untrusted ads.
105pub fn explore_untrusted(
106    feasible: &[CandidatePath],
107    adverts: &[PathAdvert],
108    constraint: &PathConstraint,
109    out: &mut [CandidatePath],
110) -> Result<usize, QdnfError> {
111    let n_in = feasible.len();
112    if n_in > MAX_PARETO_IN {
113        return Err(QdnfError::Capacity);
114    }
115    if out.is_empty() && n_in > 0 {
116        return Err(QdnfError::Capacity);
117    }
118    let mut tmp = [CandidatePath::EMPTY; MAX_PARETO_IN];
119    let mut n = 0usize;
120    let mut src = 0usize;
121    while src < n_in {
122        if path_feasible(&feasible[src].metrics, constraint).is_ok() {
123            tmp[n] = feasible[src];
124            n += 1;
125        }
126        src += 1;
127    }
128    let mut explored = 0usize;
129    let mut a = 0usize;
130    while a < adverts.len() {
131        let adv = adverts[a];
132        a += 1;
133        let mut hit = None;
134        let mut i = 0usize;
135        while i < n {
136            if matches(&tmp[i], &adv) {
137                hit = Some(i);
138                break;
139            }
140            i += 1;
141        }
142        let idx = match hit {
143            Some(i) => i,
144            None => continue,
145        };
146        match adv.metric.provenance {
147            MetricProvenance::VerifiedTopology => apply_to_path(&mut tmp[idx], &adv),
148            MetricProvenance::UntrustedAdvert => {
149                if explored >= MAX_EXPLORE {
150                    continue;
151                }
152                apply_to_path(&mut tmp[idx], &adv);
153                explored += 1;
154            }
155        }
156    }
157    let copy = n.min(out.len());
158    let mut i = 0usize;
159    while i < copy {
160        out[i] = tmp[i];
161        i += 1;
162    }
163    Ok(copy)
164}
165
166#[cfg(test)]
167mod tests {
168    use super::*;
169    use crate::net::qdnf::route::index::AdjacencyIndex;
170    use crate::net::qdnf::route::plan::plan_routes;
171    use crate::net::qdnf::route::validate::{insert, TopologyRecord, PROFILE_P0};
172    use crate::net::qdnf::types::StrongDigest;
173
174    fn rec(origin: u8, from: u8, to: u8, seq: u32, cost: u16, realm: u8) -> TopologyRecord {
175        TopologyRecord {
176            origin,
177            origin_digest: {
178                let mut d = StrongDigest::ZERO;
179                d.0[0] = origin;
180                d.0[47] = 1;
181                d
182            },
183            scope: 1,
184            from,
185            to,
186            sequence: seq,
187            expiry_unix: 100,
188            withdrawn: false,
189            bidirectional: true,
190            cost,
191            latency_ms: 1,
192            energy_uj: 1,
193            energy_known: true,
194            realm_bit: realm,
195            profile: PROFILE_P0,
196            failure_domain: from,
197            digest: StrongDigest::ZERO,
198        }
199    }
200
201    fn edge_from(r: TopologyRecord) -> ValidatedEdge {
202        ValidatedEdge {
203            origin: r.origin,
204            from: r.from,
205            to: r.to,
206            sequence: r.sequence,
207            expiry_unix: r.expiry_unix,
208            withdrawn: r.withdrawn,
209            bidirectional: r.bidirectional,
210            cost: r.cost,
211            latency_ms: r.latency_ms,
212            energy_uj: r.energy_uj,
213            energy_known: r.energy_known,
214            realm_bit: r.realm_bit,
215            profile: r.profile,
216            failure_domain: r.failure_domain,
217            scope: r.scope,
218        }
219    }
220
221    fn path(first: u8, dest: u8, cost: u16, lat: u32) -> CandidatePath {
222        let mut p = CandidatePath::EMPTY;
223        p.first_hop = first;
224        p.dest = dest;
225        p.hop_len = 1;
226        p.hops[0] = first;
227        p.metrics = PathMetrics {
228            cost,
229            latency_ms: lat,
230            energy_uj: 1,
231            energy_known: true,
232            failure_domain: first,
233        };
234        p
235    }
236
237    #[test]
238    fn untrusted_zero_cost_cannot_bypass_forbidden_realm() {
239        let mut index = AdjacencyIndex::new(1);
240        insert(&rec(1, 1, 2, 1, 0, 5), 1, 1, None, &mut index).unwrap();
241        insert(&rec(1, 1, 3, 2, 40, 0), 1, 1, None, &mut index).unwrap();
242        insert(&rec(3, 3, 2, 1, 40, 0), 1, 1, None, &mut index).unwrap();
243        let c = PathConstraint {
244            permitted_realms: 1u64 << 0,
245            min_profile: PROFILE_P0,
246            max_cost: u16::MAX,
247            deadline_ms: 0,
248            require_loop_free: true,
249            max_energy_uj: 0,
250        };
251        let cheap = edge_from(rec(1, 1, 2, 1, 0, 5));
252        let advert = AdvertisedMetric {
253            provenance: MetricProvenance::UntrustedAdvert,
254            cost: 0,
255            latency_ms: 0,
256            energy_uj: 0,
257            energy_known: true,
258        };
259        assert_eq!(admit_advert(&cheap, &advert, &c), Err(QdnfError::Denied));
260        let mut out = [CandidatePath::EMPTY; 3];
261        let n = plan_routes(&index, 1, 2, &c, 1, &mut out).unwrap();
262        assert_eq!(n, 1);
263        assert_eq!(out[0].first_hop, 3);
264        assert_ne!(out[0].metrics.cost, 0);
265    }
266
267    #[test]
268    fn untrusted_cannot_make_infeasible_cost_feasible() {
269        let edge = edge_from(rec(1, 1, 2, 1, 80, 0));
270        let c = PathConstraint {
271            permitted_realms: u64::MAX,
272            min_profile: 0,
273            max_cost: 10,
274            deadline_ms: 0,
275            require_loop_free: true,
276            max_energy_uj: 0,
277        };
278        assert_eq!(edge_feasible(&edge, &c), Err(QdnfError::Denied));
279        let advert = AdvertisedMetric {
280            provenance: MetricProvenance::UntrustedAdvert,
281            cost: 0,
282            latency_ms: 1,
283            energy_uj: 1,
284            energy_known: true,
285        };
286        assert_eq!(admit_advert(&edge, &advert, &c), Err(QdnfError::Denied));
287    }
288
289    #[test]
290    fn unknown_energy_is_not_zero() {
291        let verified = PathMetrics {
292            cost: 4,
293            latency_ms: 4,
294            energy_uj: 0,
295            energy_known: false,
296            failure_domain: 1,
297        };
298        let advert = AdvertisedMetric {
299            provenance: MetricProvenance::UntrustedAdvert,
300            cost: 1,
301            latency_ms: 1,
302            energy_uj: 0,
303            energy_known: false,
304        };
305        let over = overlay_metrics(&verified, &advert);
306        assert!(!over.energy_known);
307        assert_eq!(over.energy_uj, 0);
308        let c = PathConstraint {
309            permitted_realms: u64::MAX,
310            min_profile: 0,
311            max_cost: u16::MAX,
312            deadline_ms: 0,
313            require_loop_free: true,
314            max_energy_uj: 10,
315        };
316        assert_eq!(path_feasible(&over, &c), Err(QdnfError::Incomplete));
317    }
318
319    #[test]
320    fn explore_caps_untrusted_at_max_explore() {
321        let mut feasible = [CandidatePath::EMPTY; 5];
322        let mut adverts = [PathAdvert {
323            first_hop: 0,
324            dest: 9,
325            metric: AdvertisedMetric {
326                provenance: MetricProvenance::UntrustedAdvert,
327                cost: 0,
328                latency_ms: 0,
329                energy_uj: 1,
330                energy_known: true,
331            },
332        }; 5];
333        let mut i = 0u8;
334        while i < 5 {
335            feasible[i as usize] = path(i + 1, 9, 10, 10);
336            adverts[i as usize].first_hop = i + 1;
337            adverts[i as usize].metric.cost = i as u16;
338            i += 1;
339        }
340        let mut out = [CandidatePath::EMPTY; 5];
341        let n = explore_untrusted(&feasible, &adverts, &PathConstraint::UNRESTRICTED, &mut out)
342            .unwrap();
343        assert_eq!(n, 5);
344        assert_eq!(out[0].metrics.cost, 0);
345        assert_eq!(out[3].metrics.cost, 3);
346        assert_eq!(out[4].metrics.cost, 10);
347    }
348}