Skip to main content

zigbee_host/
topology.rs

1//! The mesh as the coordinator sees it: links between devices, from the
2//! last hop of every message, from route records, and from neighbor-table
3//! scans. Passive sources cost nothing on the air; scans are explicit.
4
5use std::collections::HashMap;
6
7use serde::Serialize;
8use zigbee_primitives::NodeId;
9
10/// Where a link was learned.
11#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize)]
12#[serde(rename_all = "snake_case")]
13pub enum LinkSource {
14    /// The last hop of a message the coordinator received.
15    LastHop,
16    /// A hop in a route record.
17    RouteRecord,
18    /// A router's neighbor table (`Mgmt_Lqi_rsp`).
19    NeighborTable,
20}
21
22/// A link between two devices, from `from` to `to` (towards the
23/// coordinator for passive links).
24#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
25pub struct Link {
26    /// Sending side.
27    pub from: NodeId,
28    /// Receiving side.
29    pub to: NodeId,
30    /// Link quality, when known.
31    pub lqi: Option<u8>,
32    /// Signal strength in dBm, when known.
33    pub rssi: Option<i8>,
34    /// How it was learned.
35    pub source: LinkSource,
36    /// When, seconds since the Unix epoch.
37    pub seen_unix: u64,
38}
39
40/// Links older than this are dropped.
41pub const MAX_AGE_S: u64 = 24 * 3600;
42/// The most links kept, so a large or hostile network cannot grow memory.
43pub const MAX_LINKS: usize = 8192;
44
45/// The link table.
46#[derive(Debug, Default, Clone)]
47pub struct Topology {
48    links: HashMap<(NodeId, NodeId), Link>,
49    /// The last route record from each source: relays nearest the source first.
50    routes: HashMap<NodeId, Vec<NodeId>>,
51}
52
53impl Topology {
54    fn put(&mut self, link: Link) {
55        if self.links.len() >= MAX_LINKS && !self.links.contains_key(&(link.from, link.to)) {
56            self.expire(link.seen_unix);
57            if self.links.len() >= MAX_LINKS {
58                if let Some(oldest) = self
59                    .links
60                    .values()
61                    .min_by_key(|l| l.seen_unix)
62                    .map(|l| (l.from, l.to))
63                {
64                    self.links.remove(&oldest);
65                }
66            }
67        }
68        let key = (link.from, link.to);
69        match self.links.get_mut(&key) {
70            // A passive or route-record hop without quality keeps the last
71            // known quality.
72            Some(old) if link.lqi.is_none() => {
73                old.seen_unix = link.seen_unix;
74            }
75            _ => {
76                self.links.insert(key, link);
77            }
78        }
79    }
80
81    /// A message from `source` arrived with this last-hop quality. The
82    /// last hop is the last relay of `source`'s recorded route, or `source`
83    /// itself when it has none.
84    pub fn last_hop(
85        &mut self,
86        source: NodeId,
87        coordinator: NodeId,
88        lqi: u8,
89        rssi: Option<i8>,
90        now: u64,
91    ) {
92        let from = self
93            .routes
94            .get(&source)
95            .and_then(|r| r.last().copied())
96            .unwrap_or(source);
97        self.put(Link {
98            from,
99            to: coordinator,
100            lqi: Some(lqi),
101            rssi,
102            source: LinkSource::LastHop,
103            seen_unix: now,
104        });
105    }
106
107    /// A route record: `source` reached the coordinator through `relays`.
108    pub fn route_record(
109        &mut self,
110        source: NodeId,
111        relays: &[NodeId],
112        coordinator: NodeId,
113        lqi: Option<u8>,
114        rssi: Option<i8>,
115        now: u64,
116    ) {
117        let mut path = Vec::with_capacity(relays.len() + 2);
118        path.push(source);
119        path.extend_from_slice(relays);
120        path.push(coordinator);
121        for (i, pair) in path.windows(2).enumerate() {
122            if let [from, to] = pair {
123                let last = i + 2 == path.len();
124                self.put(Link {
125                    from: *from,
126                    to: *to,
127                    lqi: lqi.filter(|_| last),
128                    rssi: rssi.filter(|_| last),
129                    source: LinkSource::RouteRecord,
130                    seen_unix: now,
131                });
132            }
133        }
134        self.routes.insert(source, relays.to_vec());
135    }
136
137    /// A router reported a neighbor and the quality it hears it at.
138    pub fn neighbor(&mut self, router: NodeId, neighbor: NodeId, lqi: u8, now: u64) {
139        self.put(Link {
140            from: neighbor,
141            to: router,
142            lqi: Some(lqi),
143            rssi: None,
144            source: LinkSource::NeighborTable,
145            seen_unix: now,
146        });
147    }
148
149    /// Forget a device that left.
150    pub fn remove_node(&mut self, node: NodeId) {
151        self.links
152            .retain(|(from, to), _| *from != node && *to != node);
153        self.routes.remove(&node);
154    }
155
156    /// Drop links older than [`MAX_AGE_S`].
157    pub fn expire(&mut self, now: u64) {
158        self.links
159            .retain(|_, l| now.saturating_sub(l.seen_unix) <= MAX_AGE_S);
160    }
161
162    /// Every current link.
163    pub fn links(&self) -> Vec<Link> {
164        let mut out: Vec<Link> = self.links.values().cloned().collect();
165        out.sort_by_key(|l| (l.from, l.to));
166        out
167    }
168
169    /// The recorded route of a device, relays nearest it first.
170    pub fn route(&self, source: NodeId) -> Option<&[NodeId]> {
171        self.routes.get(&source).map(Vec::as_slice)
172    }
173}
174
175#[cfg(test)]
176mod tests {
177    use super::*;
178
179    #[test]
180    fn last_hop_follows_the_route_record() {
181        let mut t = Topology::default();
182        t.last_hop(0x1111, 0, 200, Some(-40), 10);
183        t.route_record(0x2222, &[0x3333, 0x1111], 0, Some(150), Some(-60), 11);
184        t.last_hop(0x2222, 0, 140, Some(-62), 12);
185        let links = t.links();
186        let hop = links
187            .iter()
188            .find(|l| l.from == 0x1111 && l.to == 0)
189            .unwrap();
190        assert_eq!(hop.lqi, Some(140));
191        assert!(links
192            .iter()
193            .any(|l| l.from == 0x2222 && l.to == 0x3333 && l.source == LinkSource::RouteRecord));
194        assert!(links.iter().any(|l| l.from == 0x3333 && l.to == 0x1111));
195        t.expire(11 + MAX_AGE_S + 1);
196        assert_eq!(t.links().len(), 1);
197        t.remove_node(0x1111);
198        assert!(t.links().is_empty());
199    }
200
201    #[test]
202    fn table_is_bounded() {
203        let mut t = Topology::default();
204        for i in 0..(MAX_LINKS as u32 + 100) {
205            t.neighbor((i % 65000) as u16 + 1, 0, 1, u64::from(i));
206        }
207        assert!(t.links().len() <= MAX_LINKS);
208    }
209}