Skip to main content

qualia_core_db/net/qdnf/route/
spf.rs

1//! Bounded SPF over authenticated adjacencies. At most three next hops.
2
3use crate::net::qdnf::errors::QdnfError;
4use crate::net::qdnf::types::DniCoordinate;
5
6pub const MAX_NODES: usize = 16;
7pub const MAX_NEXT_HOPS: usize = 3;
8
9#[repr(C)]
10#[derive(Clone, Copy, Debug, PartialEq, Eq)]
11pub struct LinkMetric {
12    pub from: u8,
13    pub to: u8,
14    pub cost: u16,
15    pub bidirectional: bool,
16}
17
18#[repr(C)]
19#[derive(Clone, Copy, Debug, PartialEq, Eq)]
20pub struct NextHop {
21    pub node: u8,
22    pub cost: u16,
23}
24
25#[repr(C)]
26#[derive(Clone, Copy, Debug, PartialEq, Eq)]
27pub struct SpfTable {
28    pub dest: [u8; MAX_NODES],
29    pub hops: [[NextHop; MAX_NEXT_HOPS]; MAX_NODES],
30    pub hop_counts: [u8; MAX_NODES],
31    pub nodes: usize,
32    pub origin: u8,
33    /// Bellman-Ford / Dijkstra dual shortest-path distance potentials `d(u)` (§6.2.4).
34    pub potentials: [u16; MAX_NODES],
35}
36
37impl SpfTable {
38    pub const EMPTY: Self = Self {
39        dest: [0; MAX_NODES],
40        hops: [[NextHop { node: 0, cost: 0 }; MAX_NEXT_HOPS]; MAX_NODES],
41        hop_counts: [0; MAX_NODES],
42        nodes: 0,
43        origin: 0,
44        potentials: [u16::MAX; MAX_NODES],
45    };
46
47    /// Return the Bellman-Ford dual shortest-path optimality witness potentials `d(u)`.
48    #[inline]
49    pub const fn dual_witness(&self) -> SpfDualWitness {
50        SpfDualWitness {
51            origin: self.origin,
52            potentials: self.potentials,
53        }
54    }
55}
56
57/// Bellman-Ford dual distance potential witness `d(u)` (§6.2.4).
58#[repr(C)]
59#[derive(Clone, Copy, Debug, PartialEq, Eq)]
60pub struct SpfDualWitness {
61    pub origin: u8,
62    pub potentials: [u16; MAX_NODES],
63}
64
65/// Deterministic Dijkstra with stable node-id tie-break. One-sided links are ignored.
66pub fn compute_spf(origin: u8, links: &[LinkMetric], out: &mut SpfTable) -> Result<(), QdnfError> {
67    *out = SpfTable::EMPTY;
68    let mut dist = [u16::MAX; MAX_NODES];
69    let mut prev = [u8::MAX; MAX_NODES];
70    let mut used = [false; MAX_NODES];
71    if (origin as usize) >= MAX_NODES {
72        return Err(QdnfError::Range);
73    }
74    dist[origin as usize] = 0;
75    for _ in 0..MAX_NODES {
76        let mut best = u16::MAX;
77        let mut u = usize::MAX;
78        for (i, (d, taken)) in dist.iter().zip(used.iter()).enumerate() {
79            if !taken && *d < best {
80                best = *d;
81                u = i;
82            } else if !taken && *d == best && u != usize::MAX && i < u {
83                u = i;
84            }
85        }
86        if u == usize::MAX {
87            break;
88        }
89        used[u] = true;
90        for link in links {
91            if !link.bidirectional {
92                continue;
93            }
94            if link.from as usize != u && link.to as usize != u {
95                continue;
96            }
97            let v = if link.from as usize == u {
98                link.to as usize
99            } else {
100                link.from as usize
101            };
102            if v >= MAX_NODES {
103                return Err(QdnfError::Range);
104            }
105            let cand = match dist[u].checked_add(link.cost) {
106                Some(c) => c,
107                None => return Err(QdnfError::Range),
108            };
109            if cand < dist[v] || (cand == dist[v] && (u as u8) < prev[v]) {
110                dist[v] = cand;
111                prev[v] = u as u8;
112            }
113        }
114    }
115    let mut n = 0usize;
116    for (i, d) in dist.iter().enumerate() {
117        if *d == u16::MAX {
118            continue;
119        }
120        out.dest[n] = i as u8;
121        if i as u8 == origin {
122            out.hop_counts[n] = 0;
123        } else {
124            let mut hop = i as u8;
125            let mut guard = 0;
126            while prev[hop as usize] != origin && prev[hop as usize] != u8::MAX && guard < MAX_NODES
127            {
128                hop = prev[hop as usize];
129                guard += 1;
130            }
131            out.hops[n][0] = NextHop {
132                node: hop,
133                cost: *d,
134            };
135            out.hop_counts[n] = 1;
136        }
137        n += 1;
138    }
139    out.nodes = n;
140    out.origin = origin;
141    out.potentials = dist;
142    Ok(())
143}
144
145/// Verify a Bellman-Ford dual shortest-path optimality witness in `O(|E|)` (§6.2.4):
146/// 1. `d(src) == 0`;
147/// 2. Dual feasibility `d(v) <= d(u) + w(u, v)` on every eligible bidirectional snapshot edge;
148/// 3. Tightness `d(v) == d(u) + w(u, v)` along every consecutive hop of `selected_path`.
149pub fn verify_spf_dual_witness(
150    origin: u8,
151    dest: u8,
152    links: &[LinkMetric],
153    potentials: &[u16; MAX_NODES],
154    selected_path: &[u8],
155) -> Result<(), QdnfError> {
156    if (origin as usize) >= MAX_NODES || (dest as usize) >= MAX_NODES {
157        return Err(QdnfError::Range);
158    }
159    if selected_path.is_empty()
160        || selected_path[0] != origin
161        || selected_path[selected_path.len() - 1] != dest
162    {
163        return Err(QdnfError::Malformed);
164    }
165    if potentials[origin as usize] != 0 {
166        return Err(QdnfError::Conflict);
167    }
168    // 1. Check dual feasibility d(v) <= d(u) + w(u, v) across all bidirectional edges in O(|E|)
169    let mut e = 0usize;
170    while e < links.len() {
171        let link = links[e];
172        if link.bidirectional {
173            let u = link.from as usize;
174            let v = link.to as usize;
175            if u >= MAX_NODES || v >= MAX_NODES {
176                return Err(QdnfError::Range);
177            }
178            if potentials[u] != u16::MAX {
179                let bound = potentials[u]
180                    .checked_add(link.cost)
181                    .ok_or(QdnfError::Range)?;
182                if potentials[v] > bound {
183                    return Err(QdnfError::Conflict);
184                }
185            }
186            if potentials[v] != u16::MAX {
187                let bound = potentials[v]
188                    .checked_add(link.cost)
189                    .ok_or(QdnfError::Range)?;
190                if potentials[u] > bound {
191                    return Err(QdnfError::Conflict);
192                }
193            }
194        }
195        e += 1;
196    }
197    // 2. Check tight equality d(v) == d(u) + w(u, v) along the selected path
198    let mut k = 0usize;
199    while k + 1 < selected_path.len() {
200        let u = selected_path[k];
201        let v = selected_path[k + 1];
202        if (u as usize) >= MAX_NODES || (v as usize) >= MAX_NODES {
203            return Err(QdnfError::Range);
204        }
205        let mut min_w = u16::MAX;
206        let mut found = false;
207        let mut j = 0usize;
208        while j < links.len() {
209            let link = links[j];
210            if link.bidirectional
211                && ((link.from == u && link.to == v) || (link.from == v && link.to == u))
212                && (!found || link.cost < min_w)
213            {
214                min_w = link.cost;
215                found = true;
216            }
217            j += 1;
218        }
219        if !found {
220            return Err(QdnfError::NoRoute);
221        }
222        let du = potentials[u as usize];
223        let dv = potentials[v as usize];
224        if du == u16::MAX || dv == u16::MAX {
225            return Err(QdnfError::Conflict);
226        }
227        let expected_dv = du.checked_add(min_w).ok_or(QdnfError::Range)?;
228        if dv != expected_dv {
229            return Err(QdnfError::Conflict);
230        }
231        k += 1;
232    }
233    Ok(())
234}
235
236/// DNI node marker.
237pub fn dni_node(coord: DniCoordinate) -> u8 {
238    (coord.node_id & 0xff) as u8
239}
240
241#[cfg(test)]
242mod tests {
243    use super::*;
244
245    #[test]
246    fn three_node_path_a_b_c() {
247        let links = [
248            LinkMetric {
249                from: 0,
250                to: 1,
251                cost: 1,
252                bidirectional: true,
253            },
254            LinkMetric {
255                from: 1,
256                to: 2,
257                cost: 1,
258                bidirectional: true,
259            },
260        ];
261        let mut table = SpfTable::EMPTY;
262        compute_spf(0, &links, &mut table).unwrap();
263        let dest_c = table.dest.iter().position(|d| *d == 2).unwrap();
264        assert_eq!(out_hop(&table, dest_c), 1);
265    }
266
267    fn out_hop(table: &SpfTable, idx: usize) -> u8 {
268        table.hops[idx][0].node
269    }
270
271    #[test]
272    fn one_sided_link_is_ignored() {
273        let links = [LinkMetric {
274            from: 0,
275            to: 1,
276            cost: 1,
277            bidirectional: false,
278        }];
279        let mut table = SpfTable::EMPTY;
280        compute_spf(0, &links, &mut table).unwrap();
281        assert!(table.dest.iter().take(table.nodes).all(|d| *d == 0));
282    }
283
284    #[test]
285    fn bellman_ford_dual_witness_verifies_optimal_path_and_rejects_suboptimal() {
286        let links = [
287            LinkMetric {
288                from: 0,
289                to: 1,
290                cost: 2,
291                bidirectional: true,
292            },
293            LinkMetric {
294                from: 1,
295                to: 2,
296                cost: 3,
297                bidirectional: true,
298            },
299            LinkMetric {
300                from: 0,
301                to: 2,
302                cost: 9,
303                bidirectional: true,
304            },
305        ];
306        let mut table = SpfTable::EMPTY;
307        compute_spf(0, &links, &mut table).unwrap();
308        let w = table.dual_witness();
309        assert_eq!(w.potentials[0], 0);
310        assert_eq!(w.potentials[1], 2);
311        assert_eq!(w.potentials[2], 5);
312
313        // Optimal path 0 -> 1 -> 2 satisfies d(v) == d(u) + w(u,v)
314        assert_eq!(
315            verify_spf_dual_witness(0, 2, &links, &w.potentials, &[0, 1, 2]),
316            Ok(())
317        );
318        // Suboptimal direct edge 0 -> 2 (cost 9 != 5) is rejected by tightness check
319        assert_eq!(
320            verify_spf_dual_witness(0, 2, &links, &w.potentials, &[0, 2]),
321            Err(QdnfError::Conflict)
322        );
323        // Dishonest potential (claiming d(2) = 9 so 0 -> 2 looks tight) violates dual feasibility on edge (1, 2): 9 > 2 + 3
324        let mut dishonest = w.potentials;
325        dishonest[2] = 9;
326        assert_eq!(
327            verify_spf_dual_witness(0, 2, &links, &dishonest, &[0, 2]),
328            Err(QdnfError::Conflict)
329        );
330    }
331}