Routing thoughts

[Stuart Longland]

So, I've been thinking about this for the past couple of days. The
routing infrastructure is what will make or break this system. This is
long, it's basically a brain dump of ideas that have been kicking around.

Going between nodes that have direct contact with one another is easy.
Going through a central hub is not much more difficult.

The challenge is when two nodes wish to exchange information, but have
no direct path, and no designated central point. They must invoke one
or more intermediate nodes to relay information on their behalf.
Ideally, the system should be able to discover this automatically
without end-user intervention and with optimal efficiency. This implies
a dynamic routing system that can detect new nodes as they appear, and
expire them when they appear to have gone away.

At the same time, it is useful to have a way to "preference" a given
route above others even if the dynamic data may suggest otherwise.

We need to work out how frequent they should make their presence known,
and how long we should wait before we consider them "dead".

There are three types of node we really need to consider:

- Permanent
- Temporary
- Mobile

Permanent nodes are ones that are fixed in a single spot, and will be
there for a long time, typically months or years. Examples would
include repeater sites, radio club houses, home stations. They'll be
installed, and continued to be maintained in that location for the
foreseeable future.

Temporary nodes are ones that will be deployed in a location for any
time period between a few hours up to a week or so. They'll be stood up
in response to some activity, operated for the duration, then torn down
and packed up at the end of the activity. Examples would be a base or
checkpoint station at an emergency communications exercise.

Mobile nodes are practically in constant motion. They might stop for an
hour or two at a location, but then they'll move on, and they may
communicate whilst in motion as well. Examples would be nodes mounted
to vehicles (cars, bicycles, ships…) or satellites.

The nodes may be interconnected by any one of:
- Internet protocol links: WiFi, Cellulcar, Ethernet, or a wide area
network (Internet)
- Radio links: AX.25, D-Star… possibly others too
- Point-to-point Optical
- Sneakernet (dump it on portable mass storage and transport it)

Sneakernet is high-latency, and high-MTU but as Andrew S Tanenbaum
pointed out, can be surprisingly high bandwidth.

Optical links like IR and laser beams can be used for point-to-point
links across a clear channel of high bandwidth -- but may be occluded by
fog and temporary obstructions.

Radio links will fade with band conditions, can be subject to
interference and are inherently broadcast, however are the most
practical means of communication for temporary set-ups or long-distance.

Internet Protocol is useful for linking isolated nodes and clusters over
the Internet, as well as for allowing for example, a mobile node to
collect data from a temporary or fixed node for transportation to a
different part of the network. (A form of drive-by sneakernet.)

These nodes all act as the routing backbone, passing traffic labelled
for specific groups to their destination. Radio in particular, is
inherently a broadcast medium: assuming multiple nodes are in earshot,
it is not possible to communicate with only one of them without the
others necessarily decoding the signal. We can "steer" it through
repeater nodes, but the signal effectively "beams" toward all nodes in a
given direction. This makes multicast communication far more efficient
than unicast.

In that context, it makes less sense to think of addressing in terms of
specific nodes, and instead makes more sense to think of specific
"topics". Here, existing solutions like UUCP fall down: UUCP is a
strictly point-to-point protocol, tailored for dial-up modems and fixed
serial links. While it supports Internet protocol, it exclusively uses
TCP connections, treating the TCP/IP stack like a glorified dial-up modem.

NNCP does better, it has a concept of groups (it calls them "areas").
Both UUCP and NNCP however statically configure routes (and groups in
the case of NNCP).

From the user perspective, a single user may be in possession of a
smartphone or tablet, and/or a laptop. Hypothetically, it may be
desirable that the user can access recent messages from the
smartphone/tablet, but that copies of all messages, both going in and
out, are kept on the laptop which has more mass storage available. This
is a key area where Winlink falls down: a user might have multiple
Winlink stations set up, and their messages get "scattered" between them.

In this story, the user effectively operates one or more "user agents",
these are the leaves on the network. They connect with a nearby node,
and via that node send and receive traffic. The user agents for a given
user effectively form a multicast "group", all agents effectively
listening for messages sent to that group address. The agents need not
be connected to the same node. They register their interest in a given
"group", and they then receive all traffic sent to that group within a
configured "hop limit".

Through the network, the agents synchronise messages: the user may
configure their collection of agents to forward all incoming and
outgoing messages to one or more specific agents of theirs (e.g. a
laptop or two), and only retain messages that are specifically flagged
as "keep" or are newer than some maximum age limit.

This implies a need on radio networks to differentiate between a node
address, and a group address.

AX.25 address fields are 7-bytes, with 6 bytes of "shifted" 7-bit ASCII.
Each character in the call-sign is left-shifted by one. The final
byte stores the SSID, extension bit, reserved bits, and the C/H bit: in
source/destination fields, this is the "command" bit, and in digipeater
fields, this is the "has been repeated" bit. The source and destination
fields each have a C/H bit, and AX.25 uses the following convention for
their usage:

- Source and destination C/H bits match: legacy AX.25 1.0 frame
- Source and destination C/H bits are opposite: AX.25 2.x frame

The actual value of the C/H bit for the "frame" is taken from the
destination field.

The C/H bit is meaningful when in connected mode, but in "unproto" mode
(using UI frames) has no special meaning. Now AX.25 connected mode is
inherently point-to-point, and can only be used to link two AX.25
stations, for multicast activities, we can only rely on UI frames as the
transport medium. Nominally in UI frames, the C/H bit is set to 0: if
we designate UI with C/H=1 as meaning "multicast", then we can
effectively address a multicast "group".

"VK4MSL-3" might be an AX.25 station (in hex: ac 96 68 9a a6 98 60)
implementing a user agent for the operator "VK4MSL"; it would then
listen for the group "VK4MSL" (in hex: ac 96 68 9a a6 98 e0) to receive
message traffic.

The nodes would need to relay an agent's desire to subscribe to a given
group for a given hop radius. This would need to be broadcast in a
manner similar to the APRS WIDEn-N scheme and the subscription would
have an expiry time reflective of the probability of the agent's current
movement velocity. (An agent travelling at speed should subscribe for a
shorter period than one that is stationary.) Subscriptions may also be
cancelled early to free up resources.

Routing needs to be decided fundamentally based on the following criteria:

1. explicit user preference (e.g. a user might choose to route traffic
via a mobile node that is currently stationed near them but will be
travelling to a location in proximity to the target node)
2. measured link quality
3. administrative preference (e.g. "cheaper" or "higher capacity" links
may be preferred over more expensive or constrained links)

Let's start at the bottom:

Administrative preference is used to "fudge" the preference of a given
route above or below others. An example might be a link that, rather
than going over a radio network, instead is routed through a commercial
satellite with timed and billed connections. It may provide a
high-quality link, but you want to avoid using it because it'll get
expensive fast. Alternatively, you might have nodes that have
point-to-point WiFi links that are high-speed and free, using those
frees up narrowband radio links.

Measured link quality uses packet loss statistics to try and gauge the
"quality" of a point-to-point link between two nodes. This is analogous
to Net/ROM's "quality" field, and serves a similar purpose. The concept
being, all other things being equal, we should choose the best quality
link available.

Each node should, keep a tally of the number of packets it has sent, and
the number of those that are re-transmissions. These should be stored
in a rolling series of time buckets, so that the "average packet loss"
over the past N minutes can be computed. Similarly, if it is known how
many packets the remote node received from us; that too can be compared
to our "total" count of packets we actually sent, and used to gauge how
well they are receiving us.

If however, a user decides they know better, we should not stand in
their way (and they may proceed to shoot any one of their toes). An
example might be if a big payload of data is to be delivered to a
far-off node at a checkpoint, and a mobile node is installed on a
vehicle that's presently being loaded up with equipment (or perhaps the
operators' meals) for that same checkpoint, the automatic routing system
won't "know" that mobile node's itinerary will bring it in close
proximity to the target. So we override the automatic route selection,
specify an explicit route via that node, and the message gets delivered
in a timely manner by way of the mobile node.

Another example would be two "sneakernet" linked nodes: link quality
would suggest the link is dead, however the humans know better.

Node discovery implies a periodic "heartbeat" to check liveliness. In
Net/ROM, stations broadcast a "NODES" manifest as a series of UI frames
to that address that effectively described all the network nodes the
sender knew of, and their relative qualities. This was typically sent
hourly (configurable). Each entry in the "NODES" manifest was 21 bytes,
so on big networks, this would generate quite a bit of traffic.

Under some jurisdictions, a station is required to identify themselves
periodically. ACMA rules here in Australia require identification "at
the start of transmission, and every 10 minutes afterwards". A periodic
"heartbeat" packet, with a listing of the most recently heard nodes (and
the tally of received packets from each) could be used by receiving
nodes to not only build up a list of immediate neighbours, but also
measure link quality by comparing the "received" count with their own
total transmit counter. For the sake of brevity, we should limit
ourselves to a single packet each heartbeat.

To find nodes that are a hop or more beyond, we need to engage the
"knowledge" of our neighbours. A "where is" packet, broadcast in a
similar manner to APRS WIDEn-N, could be used to query all nodes within
a given hop radius if they know of a route to a given node. It is
tempting that the response be sent back along that route, but that
assumes bi-directional routes. The response therefore should probably
go via WIDEn-N unless the responding node "knows" a better alternative.

The response should include an expiry time, each node in the route
should have an expiry reflective of the node type (permanent, temporary
or mobile) and the route expiry shall be the minimum of these node
expiry times. Similarly, the link quality shall be the minimum observed
along that route.

This handles currently "online" nodes, with offline nodes disregarded.
For "sneakernet" and offline nodes, the above system would require the
user know of the possibility of a route via a given path, and explicitly
provide the said path. I'm not sure there's a way to automatically
consider such routes.

A lot here assumes AX.25 as the underlying layer, but many of these
concepts will likely translate to other systems. In the case of TCP/IP,
nodes sharing an Ethernet segment or WiFi network could utilise
multicast UDP as the link layer to "discover" each-other, then either
use unicast or ad-hoc multicast to communicate from there. mDNS could
also play a role here.

As for cryptography: some of the routing/identification packets could be
digitally signed, but for actual transfers of payloads between nodes,
the payload itself should be signed as a whole. As the payload passes
between nodes (store-and-forward style), each node can hash the existing
payload, sign the hash, and append that attestation block to the end of
the payload.

Onion routing for privacy is probably not going to work in such a
context as the above assumes it's the "same" payload at each hop, and on
amateur radio is likely undesirable for legal reasons. It also would
mandate a source-routed path, which is the norm for UUCP/NNCP, but not
the approach taken above.

Anyway, that's some ideas that I had. Some of it pie-in-the-sky stuff,
but maybe in amongst it, there's something practical.

Regards,
--
Stuart Longland (aka Redhatter, VK4MSL)

I haven't lost my mind...
...it's backed up on a tape somewhere.


--
Stuart Longland (aka Redhatter, VK4MSL)

I haven't lost my mind...
...it's backed up on a tape somewhere.

[Stuart Longland]

Been doing some more thoughts on this. Slinging bits is the "easy"
part, but also something where things can go pear shaped rather quickly
if it's not done right.

AX.25 seems like a logical choice for that task, but it's a pretty
primitive building block akin to using raw TCP or UDP. It would seem
the payloads we're wishing to send are likely going to be bigger than
the 256 bytes allowed in an AX.25 frame.

UUCP was discussed before, but one limitation it has is that it's
strictly point-to-point, no multicast ability. We could try ripping
apart NNCP to make a cleartext version, but neither of these have an
instantaneous message ability. So it's not possible to report back that
a downstream node has custody of the payload (like ION-DTN).

I deal with Thread networking a lot at work, and in particular, a
protocol called CoAP, which can be considered like a binary HTTP run
over UDP. It's frugal on bits, supports instantaneous messaging, and
can handle transmission of large payloads through block-wise transfer.

CoAP also supports multicasting for small messages, and with some
creative application of RFC-7959, we might be able to make something
work for multicasting blockwise transfers too.

There is a specification for tunnelling it over serial links in draft
(https://datatracker.ietf.org/doc/html/draft-bormann-t2trg-slipmux-03)
but that won't help us for multicast.

At the cost of some overhead, I wonder if a link-local 6LoPWAN style
datagram encapsulation may help: we effectively make a simple link-local
6LoWPAN system between nodes over AX.25, then use CoAP over that.

https://vk4msl.com/2018/11/17/6lowham-a-draft-protocol-specification/
covers some of the ideas.

I have some C code that can create a `tap` interface and read/write
packets to `stdio`, basically a simple program that can be installed
with suitable capabilities (or setuid `root`):

https://codeberg.org/sjlongland/6lowham-tap-agent

With that, we can dissect a IPv6 datagram and translate that to a
6LoWPAN frame to put in an AX.25 UI datagram for transmission, or go
back the other way.

A proof of concept is discussed here:
https://vk4msl.com/2019/01/19/6lowham-dissecting-packets-in-python/

Now this in itself only offers real-time networking whilst all nodes are
up and operational, for offline nodes and sneakernet links, I think
static routing will play a part as there's only so much you can discover
dynamically.

For the dynamic routing part, there's some (perhaps naïve) ideas here:
https://vk4msl.com/2021/09/16/6lowham-thoughts-on-how-to-distribute-context-and-applications/
-- I'm almost of a thought of we just get linked-local messaging going
for now, but using this framing format does give us a building-block on
which we can expand routing further.

Doing things this way, we can then use an existing widely implemented
protocol like CoAP to shunt bigger payloads around and implement the
higher-level co-ordination messaging.

[Bruce Perens]

I think the way we keep this from being very high bandwidth and close
to an insoluble problem is to introduce the concept of geographical
delegation. Consider that we divide the world up by Maidenhead grid or
something like it. You get a number for your location. For most
stations, you might be able to manage a route set of 1-3 hops to reach
any station in the low 4 X by 4 Y bits of your grid location. A
dedicated station on a mountaintop might be able to manage the low 8 X
by 8 Y bits of its grid location, and by the field width it says it
can handle, we know it's better connected, in a better location, or
more powerful. Such a station might have long-range links to other
such stations, so it might advertise that it can relay to an 8 X by 8
Y area in another location. If we know of such stations, but we don't
have a direct route across the country, we can still forward to
stations that are in the right direction, in the hope that they can
complete that relaying through other such stations, and we can save
whether that works or not. A mobile knows where it is through GPS and
starts to pick up routes, and is likely to hand a message over to the
nearest fixed station until it has better routes to use.

Stations can also advertise their load average, the percentage of the
time that they are exchanging messages rather than being quiet. This
allows us to select routes through less busy stations.

I doubt any of this is an invention, and I surmise that someone has
already done it better. We should be looking at papers.

Thanks

Bruce

> --
> You received this message because you are subscribed to the Google Groups "emergency_communications" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to emergency_communic...@perens.com.
> To view this discussion visit https://groups.google.com/a/perens.com/d/msgid/emergency_communications/39045dad-0093-42c5-8626-d480ddfbedb9%40longlandclan.id.au.



--
Bruce Perens K6BP

[Bruce Perens]

It strikes me that we can simulate routing. We have at least the
mailing addresses of all licensed US hams. We can probably find a
height map of the USA and malke a rough estimate of what stations can
hear each other on packet (there is better estimation software but it
is unnecessary for this simulation). We can then model stations,
considering different percentages all licensed hams involved in our
network, and simulate the routes their stations might collect, and how
well we might route between them. We can also take repeater
information to model high-height stations that might be built and
their effect on the system.

Thanks

Bruce

--
Bruce Perens K6BP

[Bruce Perens]

Delegation is important if this project is not to become too large to
carry out. One aspect that is easy to delegate is the data link layer.
For that reason, it might be best to model with existing packet links,
and perhaps HF using Rowe's modems unless there is something
out-of-the-box that would work as an Open Source "naked" HF data link
layer.

Thanks

Bruce

--
Bruce Perens K6BP

[Bruce Perens]

Besides stations advertising their load average, they should advertise
the load-average of links - the percentage of time the channel is
busy, their height above sea level, and the link frequency, so that we
have an idea of what links overlap a channel, and can choose
non-overlapping links on less busy channels and avoid using wide-area
stations for last-mile transmissions. This simplifies much of the
reality of how radio actually works, but is probably sufficient for
routing.

On Mon, Mar 30, 2026 at 11:37 AM Bruce Perens <br...@perens.com> wrote:
>

--
Bruce Perens K6BP

[Stuart Longland]

On 31/3/26 04:56, Bruce Perens wrote:
> It strikes me that we can simulate routing. We have at least the
> mailing addresses of all licensed US hams. We can probably find a
> height map of the USA and malke a rough estimate of what stations can
> hear each other on packet (there is better estimation software but it
> is unnecessary for this simulation). We can then model stations,
> considering different percentages all licensed hams involved in our
> network, and simulate the routes their stations might collect, and how
> well we might route between them. We can also take repeater
> information to model high-height stations that might be built and
> their effect on the system.

APRS data might give some insights too. Especially as some _are_ in
fact digipeaters and they are real radio links, in some cases from
low-power mobile devices operating in VHF or UHF bands.

Sure they're using Bell203 modulation which is a terrible digital mode
for noise performance, but if they are "heard" via that medium, they'll
probably do a lot better with a properly designed physical layer.

[Stuart Longland]

On 31/3/26 05:08, Bruce Perens wrote:
> Delegation is important if this project is not to become too large to
> carry out. One aspect that is easy to delegate is the data link layer.
> For that reason, it might be best to model with existing packet links,
> and perhaps HF using Rowe's modems unless there is something
> out-of-the-box that would work as an Open Source "naked" HF data link
> layer.

The only other one that jumps out at me is ARDOP: there is an
open-source implementation of it. Often used with Winlink, but people
have re-purposed it for things like UUCP.

[Stuart Longland]

On 31/3/26 04:37, Bruce Perens wrote:
> I think the way we keep this from being very high bandwidth and close
> to an insoluble problem is to introduce the concept of geographical
> delegation. Consider that we divide the world up by Maidenhead grid or
> something like it. You get a number for your location. For most
> stations, you might be able to manage a route set of 1-3 hops to reach
> any station in the low 4 X by 4 Y bits of your grid location.

Location (especially 3D location) is a pretty good rough guide, and I
think it makes sense to factor it in where possible.

However, there may be circumstances where it is not available (lack of
hardware, poor reception of positioning satellites) and should have a
plan for handling that.

The other big factor would be the ERP of the station (a function of
antenna design and orientation, feedline loss and transmitter power),
and any local interference sources that might impair sensitivity.

[Bruce Perens]

On Mon, Mar 30, 2026 at 1:49 PM 'Stuart Longland' via
emergency_communications <emergency_co...@perens.com> wrote:
> However, there may be circumstances where it is not available (lack of
> hardware, poor reception of positioning satellites) and should have a
> plan for handling that.

Mobiles and portables might fit this category, but they will only work
for more temporary routes. I can see a portable set up over an
emergency site, etc. It can tell you what it hears, and we know it's
S/N.

[Stuart Longland]

True, and fixed stations, in theory we could just have it configurable
what the location and altitude is since you can read that off a GPS or
figure it out from a map and punch that in.

You install a repeater node on a mountain top tower, that tower is not
suddenly going to go galloping down the hill unless there's a landslide
(and in that circumstance, your node probably will be off-air anyway).

[Bruce Perens]

So, there are things we can say about stations in a bit field: whether
they are fixed, whether they can be expected to have emergency power,
whether emergency power is temporary (no solar) or expected to
continue, whether snow can be expected to interrupt emergency power
(it happens at my remote site).

--
Bruce Perens K6BP

[Stuart Longland]

On 31/3/26 06:49, Stuart Longland wrote:
> On 31/3/26 04:37, Bruce Perens wrote:
>> I think the way we keep this from being very high bandwidth and close
>> to an insoluble problem is to introduce the concept of geographical
>> delegation. Consider that we divide the world up by Maidenhead grid or
>> something like it. You get a number for your location. For most
>> stations, you might be able to manage a route set of 1-3 hops to reach
>> any station in the low 4 X by 4 Y bits of your grid location.
>
> Location (especially 3D location) is a pretty good rough guide, and I
> think it makes sense to factor it in where possible.
>
> However, there may be circumstances where it is not available (lack of
> hardware, poor reception of positioning satellites) and should have a
> plan for handling that.
>
> The other big factor would be the ERP of the station (a function of
> antenna design and orientation, feedline loss and transmitter power),
> and any local interference sources that might impair sensitivity.

One way of encoding a maidenhead locator is discussed here:
https://vk4msl.com/2011/02/05/geographic-ipv6-using-maidenhead-locators/

(I need to fix some bitrot on that post, but the gist is there.)

- Zone level, 18×18 grid: 5 bits for latitude, 5 bits for longitude, or
alternatively for 324 zones, 9 bits.
- Square level, 10×10 grid: 4 bits for latitude, 4 bits for longitude,
or alternatively for 100 squares, 7 bits.
- Subsquare level, 24×24 grid: 5 bits for latitude, 5 bits for longitude
or alternatively for 576 subsquares, 10 bits.

So two possible representations:

Zone Square Subsquare
Lat Lng La Ln Lat Lng
.---. .---. .--. .--. .---. .---.
10000 00110 0110 0010 01011 01101 = 28 bits

Zone Square Subsquare
.-------. .-----. .--------.
100100110 0111110 0100010101 = 26 bits

[Stuart Longland]

On 31/3/26 07:16, 'Stuart Longland' via emergency_communications wrote:
> One way of encoding a maidenhead locator is discussed here:
> https://vk4msl.com/2011/02/05/geographic-ipv6-using-maidenhead-locators/
>
> (I need to fix some bitrot on that post, but the gist is there.)
>
> - Zone level, 18×18 grid: 5 bits for latitude, 5 bits for longitude, or
> alternatively for 324 zones, 9 bits.
> - Square level, 10×10 grid: 4 bits for latitude, 4 bits for longitude,
> or alternatively for 100 squares, 7 bits.
> - Subsquare level, 24×24 grid: 5 bits for latitude, 5 bits for longitude
> or alternatively for 576 subsquares, 10 bits.
>
> So two possible representations:
>
>    Zone      Square    Subsquare
>  Lat   Lng   La   Ln   Lat   Lng
> .---. .---. .--. .--. .---. .---.
> 10000 00110 0110 0010 01011 01101 = 28 bits
>
>    Zone    Square  Subsquare
> .-------. .-----. .--------.
> 100100110 0111110 0100010101      = 26 bits

Thinking about this now, it seems the 28-bit representation would be
closer… but to be able to mask off LSBs easily, it would seem Latitude
and Longitude bits should be interleaved:

- bit 27: Zone Lat bit 4
- bit 26: Zone Lon bit 4
… etc …
- bit 19: Zone Lat bit 0
- bit 18: Zone Lon bit 0
- bit 17: Square Lat bit 3
- bit 16: Square Lon bit 3
… etc …
- bit 11: Square Lat bit 3
- bit 10: Square Lon bit 3
- bit 9: SubSq Lat bit 5
- bit 8: SubSq Lon bit 5
… etc …
- bit 1: SubSq Lat bit 0
- bit 0: SubSq Lon bit 0

Ugly as sin, but it does mean we can take a "CIDR-style" approach to
dicing up the maidenhead locator.

[Bruce Perens]

The way that grid squares are put together isn't best for this,
unfortunately. The best system would encode squares or rectangles by
increasing two-bit amounts, so that each additional two bits gives you
a 2x2 square 4 times the size of the contained squares.

> --
> You received this message because you are subscribed to the Google Groups "emergency_communications" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to emergency_communic...@perens.com.

> To view this discussion visit https://groups.google.com/a/perens.com/d/msgid/emergency_communications/cbb66a9e-88f7-4a7b-8c29-eb41b76b2911%40longlandclan.id.au.



--
Bruce Perens K6BP

[Bruce Perens]

Here we go. Somewhat down the article they discuss hierarchical ones.
https://en.wikipedia.org/wiki/Discrete_global_grid

--
Bruce Perens K6BP

[Bruce Perens]

Ooh. The hilbert curve grid preserves nearest cells as neighbors. It
might be a bit hard to explain, but close to optimum.

--
Bruce Perens K6BP

[Bruce Perens]

Here's the whole geographical solution, ready for use:
https://github.com/google/s2geometry

--
Bruce Perens K6BP

[Stuart Longland]

On 31/3/26 07:54, Bruce Perens wrote:
> Here's the whole geographical solution, ready for use:
> https://github.com/google/s2geometry

Yep, I'll have to have a closer look but on paper it looks like a good
option.