| |
PE1NNZ > FLXNET 30.06.21 17:48l 280 Lines 19792 Bytes #999 (0) @ WW
BID : 1583_PE1NNZ
Read: GUEST
Subj: FlexNet protocol
Path: IZ3LSV<IW8PGT<I3XTY<GB7COW<GB7YEW<W9GM<PE1RRR<PE1NNZ
Sent: 210630/1632Z 1583@PE1NNZ.#NBW.NLD.EURO LinBPQ6.0.20
FlexNet protocol description
July, 2021 - Guido <pe1nnz@amsat.org>
This is a draft version, please let me know your feedback and comments and I will incorporate them in the final version.
Introduction
FlexNet is a packet radio switch software, developed by G. Jost, DK7WD in 1987-1998. Around 1995, there were about 500 active nodes deployed in central Europe, allowing packet radio users to connect instantly to distant nodes, spanning over hundreds of kilometers with connections over tens of digipeater nodes, and response times of typically a few seconds on 9600 baud interlinks.
This was revolutionary, as it was not seen before and not hardly possible with the present (TheNet) NET/ROM network at the time; packet radio users were experiencing unreliable and slow connections when hopping over multiple nodes in the network, resulting in frustration and changed user's behavior into single-stepping from node to node in order to reach a final destination reliably.
FlexNet's design is different; it does have a hop-to-hop acknowledgement mechanism that made the connection fast and reliable and it had an auto router that tested the links on their quality and ensured that connections were made over the fastest and most reliable paths in the network.
While FlexNet nodes was widely adopted and a success, its implementation details of the actual protocol remained undocumented and a proprietary part of the FlexNet software. In this document the FlexNet protocol is documented based on some analysis of FlexNet 3.3g software; it contains the frame formats and how the node behavior how to handle them. The main reasons for documenting it is that we can learn and understand why this network technology performed so well and to understand its weaknesses, so that we can experiment with it and apply the good parts in other designs.
This document do not cover the details about the FlexNet history, hardware and software, its functions and design decisions; they can be found in the ARRL conference papers [JOST90], [JOST95] and the Sysop FlexNet manual [JOST98].
1. FlexNet general operation
A FlexNet auto router is using the L2 digipeater fields to route frames over the FlexNet network. By convention, the first digipeater field contains the entry node where the user is connecting to, and the last digipeater field contains the next node to reach the destination. On the next node, the last digipeater field is replaced with the node call.
When a FlexNet node receives SABM frame with its node call in a digipeater field, it immediately accepts the connection by answering with UA, and it binds and establish a second connection with the next node in the last digipeater field. The main advantage here is that information frames are immediately acknowledged (or rejected) without the latency and packet-loss probability of the entire routing path.
Note that this hop-to-hop acknowledgment mechanism keeps state at nodes in between the path and makes it impossible to move active sessions to alternative or better paths, and hence connections break when there is a link failure in the path; but, since nodes are frequently testing the link quality, in practice only these paths are selected by FlexNet nodes that are stable, instable paths are de-prioritized due to a higher trip times.
While it is technically possible to discover neighbor nodes, the current FlexNet protocol does only support statically defined routes to neighbors.
Example:
PE1NNZ to DB0RES-10 via PE1NNZ-1* N9SEO-9 ctl SABM
DB0RES-10 to PE1NNZ via N9SEO-9* PE1NNZ-1 ctl UA-
DB0RES-10 to PE1NNZ via N9SEO-9* PE1NNZ-1 ctl I00^ pid F0 [236]
0000 2A 2A 2A 2A 2A 2A 2A 2A 20 44 42 30 52 45 53 2D ******** DB0RES-
0010 31 30 20 2A 2A 2A 20 42 6F 61 72 64 65 72 2D 4E 10 *** Boarder-N
0020 6F 64 65 2F 57 6F 72 6C 64 47 61 74 65 20 2A 2A ode/WorldGate **
0030 2A 20 4C 69 6E 75 28 58 29 4E 65 74 20 56 20 31 * Linu(X)Net V 1
0040 2E 33 39 20 2A 2A 2A 2A 2A 2A 2A 0D 20 20 20 20 .39 *******.
0050 20 20 20 20 20 20 20 20 20 57 65 6C 63 6F 6D 65 Welcome
0060 20 74 6F 20 52 65 65 73 2F 52 68 69 6E 65 20 28 to Rees/Rhine (
0070 47 65 72 6D 61 6E 79 29 20 6C 6F 63 2E 20 4A 4F Germany) loc. JO
0080 33 31 45 53 0D 0D 20 20 20 20 20 20 20 20 20 20 31ES..
0090 3C 4C 3E 69 6E 6B 73 20 20 3C 44 3E 65 73 74 20 <L>inks <D>est
00A0 20 3C 48 3E 65 6C 70 20 20 3C 49 3E 6E 66 6F 20 <H>elp <I>nfo
00B0 20 3C 4E 3E 6F 64 65 73 20 20 3C 51 3E 75 69 74 <N>odes <Q>uit
00C0 0D 20 20 20 20 20 20 20 20 20 20 3C 47 3E 61 74 . <G>at
00D0 65 20 74 6F 20 44 4C 20 5B 44 42 30 52 45 53 2D e to DL [DB0RES-
00E0 30 5D 20 20 3C 44 58 3E 43 6C 75 73 0] <DX>Clus
2. FlexNet Protocol Frames
2.0. Link Initialization
A Link Initialization frame is the first message that is exchanged with a neighbor node to express software versions and SSID range used by the nodes. A node establishes an exclusive AX.25 connection with a neighbor, whereby the PID set to 0xCE and where the SSID of the source address is set to the lowest SSID that is used by the node. When Link Initialization has been sent, the link-state becomes up and the node starts emitting Link Test Messages; when the link fails (retry time-out), the link-state becomes down and the node may try to reconnect (and optionally initialize again).
Format: 0HTVV.
H Node's highest SSID (ASCII '0' biased, (0..?)) of the range SSIDs used by the node (lowest SSID in source address)
T Type of software (ASCII ' ' biased)
Reserved: 0=FlexNet, 1=Baycom Node, 2=Digiware, 3=TheNetNode, 4=SNET, 5=XNET
V Version, 1-2 characters, biased with ASCII ' '
For instance: 01 for FlexNet 3.3g, 2 for XNET 1.38
. End of frame (ASCII Carriage Return)
Example: 01 !.
N9SEO-9 to PE1NNZ-1 ctl SABM
PE1NNZ-1 to N9SEO-9 ctl UA-
PE1NNZ-1 to N9SEO-9 ctl I00^ pid CE [6]
0000 30 31 20 20 21 0D 01 !.
N9SEO-9 to PE1NNZ-1 ctl RR1v
N9SEO-9 to PE1NNZ-1 ctl I10^ pid CE [5]
0000 30 38 25 21 0D 08w
2.1. Link Test Response
Send in response to a Link Test Frame. By measuring the time-difference of the two, a node can derive the link round-trip time. Note that the Response Frame carriers the round-trip time measurement of the neighbor, so that both the up- and downlinks round-trip times are known on both nodes at any given time. The receiving node keeps a round-trip time history and calculates a moving average from the last 16 measurements, a minimum response time of 100ms applies for the calculation.
Format: 1TTTT.
T Neighbors link time measurement result in 100ms units, 1-4 decimals
. End of frame (ASCII Carriage Return)
Example: 18.
PE1NNZ-1 to N9SEO-9 ctl I67^ pid CE [3]
0000 31 38 0D 18.
2.2. Link Test
A Link Test frame is sent periodically to test the healthiness (availability and responsiveness) of the link with a neighbor node. A Link Test frame is sent at least every 600s. Link Test frames are sent to evaluate the actual link response time under influence of user-load and varying link-performance, and to trigger potential route information updates when link properties are changing.
Format: 2SSS...S.
S A sequence of 199 ASCII ' ' characters
. End of frame (ASCII Carriage Return)
Note that some implementations may use a different payload; e.g XNet is using 250 ASCII ' ' characters, and leaving out the CR character.
Example: 2 .
PE1NNZ-1 to N9SEO-9 ctl I21^ pid CE [201]
0000 32 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2
0010 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0020 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0030 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0040 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0050 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0060 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0070 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0080 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0090 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
00A0 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
00B0 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
00C0 20 20 20 20 20 20 20 20 0D
2.3. Route Information
Route information frames updates the node's route destination entries with their actual trip times and link directions.
Changes in link-state or link round-trip time updates the route destination entry of the neighbor, and will together with incoming Routing Information frames trigger the forwarding of routing information to neighbors when there are new or unreachable routing destinations to report, or when trip times are changing. When Route Information is forwarded, the round-trip times of the links and routing step (20¨f the link RTTs) are accumulated.
Route information updates are only sent to neighbors that were not announcing it. In addition, a certain trip time threshold may be set on which updates are no longer propagated. For a node with multiple paths to a destination, only the fastest trip time is announced to neighbors. In case a destination is reported as unreachable, the node denounce the unreachability to other nodes once there is no alternative path is available, otherwise the trip time of the fastest alternative path may be announced (only to the neighbors that were not announcing the unreachability, to prevent erroneous behavior in case of loops!). When a link fails and it is detected by its neighbor node, then the neighbor node denounces all its destinations for that link.
Routing information can be distributed in a push-based fashion, polled (token-based) fashion, or a combination of both. A token-based exchange gives the node control on when it receives routing updates from a neighbor. A node can for a certain time, hold up a certain amount of routing updates (e.g. to fill-up a complete AX25 frame), before sending it to a neighbor. Destination trip time updates (and unreachability) are usually collected and pushed. Nodes that operate with three or more links may poll updates for new destinations from their neighbors. Nodes that are not playing a central role in the network (node with a single link), do not need to receive Routing Information as there is nothing to route between nodes.
For each destination entry the node may maintain a flag to keep track which links already have received a update. When a link is initialized, the flag should indicate that none of the entries were received yet, and hence the node start sending all destinations towards the neighbor.
Format: 3[DDDDDDLHTTTT ][ |-].
D Destination callsign, 6 characters filled with blanks
L Lowest SSID of range associated to destination (0..?)
H Highest SSID of range associated to destination (0..?)
T Destination trip time in 100ms units, 4 decimals
This is the accumulated link times of all links in the path,
plus, an additional 20śharge for each routing hop.
0 means that the destination became unreachable
Token is given away to other node, so that it can send routing frames
- Token is given back by other node, sending of routing frames is halted
. End of frame (ASCII Carriage Return)
Example (push): 3VE3TOK::411 VE3TOK<<411 VK3ATM55358 CX2SA 00424 IK2DUW662088
PE1NNZ-1 to N9SEO-9 ctl I53^ pid CE [63]
0000 33 56 45 33 54 4F 4B 3A 3A 34 31 31 20 56 45 33 3VE3TOK::411 VE3
0010 54 4F 4B 3C 3C 34 31 31 20 56 4B 33 41 54 4D 35 TOK<<411 VK3ATM5
0020 35 33 35 38 20 43 58 32 53 41 20 30 30 34 32 34 5358 CX2SA 00424
0030 20 49 4B 32 44 55 57 36 36 32 30 38 38 20 0D IK2DUW662088 .
Example (poll token-give): 3 .
PE1NNZ-1 to N9SEO-9 ctl I41^ pid CE [3]
0000 33 2B 0D 3 .
Example (poll token-back): 3VE3MUS::56 VE3TOK1150 VE3TOK::2250 VE3TOK::50 VE3TOK<<50 F4DUR 88102 HG8LXL0057 HG8PXL5563 K5DAT 00244 K5DAT 99140 VA3BAL5552 VA3BAL7752.3-.
N9SEO-9 to PE1NNZ-1 ctl I57^ pid CE [148]
0000 33 56 45 33 4D 55 53 3A 3A 35 36 20 56 45 33 54 3VE3MUS::56 VE3T
0010 4F 4B 31 31 35 30 20 56 45 33 54 4F 4B 32 32 35 OK1150 VE3TOK225
0020 30 20 56 45 33 54 4F 4B 3A 3A 35 30 20 56 45 33 0 VE3TOK::50 VE3
0030 54 4F 4B 3C 3C 35 30 20 46 34 44 55 52 20 38 38 TOK<<50 F4DUR 88
0040 31 30 32 20 48 47 38 4C 58 4C 30 30 35 37 20 48 102 HG8LXL0057 H
0050 47 38 50 52 43 30 30 35 37 20 48 47 38 50 58 4C G8PRC0057 HG8PXL
0060 35 35 36 33 20 4B 35 44 41 54 20 30 30 32 34 34 5563 K5DAT 00244
0070 20 4B 35 44 41 54 20 39 39 31 34 30 20 56 41 33 K5DAT 99140 VA3
0080 42 41 4C 35 35 35 32 20 56 41 33 42 41 4C 37 37 BAL5552 VA3BAL77
0090 35 32 20 0D 52 .
N9SEO-9 to PE1NNZ-1 ctl I60^ pid CE [3]
0000 33 2D 0D 3-.
Example (poll token-back): 3IW2OHX>>13 IW6NDX0>10 IW8PGT>>10 IW8PGT??8 IZ3LSV2210 OE6XPE0?15 OK0DXI0026 OK0NAG0?2 OK0NCC003 OK0NI 097 OK0NI ::2 -
N9SEO-9 to PE1NNZ-1 ctl I57^ pid CE [119]
0000 33 49 57 32 4F 48 58 3E 3E 31 33 20 49 57 36 4E 3IW2OHX>>13 IW6N
0010 44 58 30 3E 31 30 20 49 57 38 50 47 54 3E 3E 31 DX0>10 IW8PGT>>1
0020 30 20 49 57 38 50 47 54 3F 3F 38 20 49 5A 33 4C 0 IW8PGT??8 IZ3L
0030 53 56 32 32 31 30 20 4F 45 36 58 50 45 30 3F 31 SV2210 OE6XPE0?1
0040 35 20 4F 4B 30 44 58 49 30 30 32 36 20 4F 4B 30 5 OK0DXI0026 OK0
0050 4E 41 47 30 3F 32 20 4F 4B 30 4E 43 43 30 30 33 NAG0?2 OK0NCC003
0060 20 4F 4B 30 4E 49 20 30 39 37 20 4F 4B 30 4E 49 OK0NI 097 OK0NI
0070 20 3A 32 30 20 2D 0D ::2 -.
2.4. Link Management
Format: 4TTTTX
T Link round trip time for ...
X when ASCII '!' is specified, all Route Information has been purged
Example: ...
2.6. Route Test Request
Route Test Request frames are issued on nodes where a user wants to know the actual routing path to a certain destination. The frame is forwarded to neighbors according the routing table. For each hop the TTL count is increased (starting at 1 at origin) and Digipeater Node is inserted.
Format: 6HQQQQQSSSSSSSSS [XXXXXXXXX ]DDDDDDDDD
H TTL Hop-count (ASCII ' ' biased)
Q User's QSO number on the source node where the Route Test was initiated
S Source Node (variable string with Callsign and optional '-' SSID when not zero)
X Digipeater Node, there can be multiple entries
D Destination Node
Example: 6! 1PE1NNZ-1 SP7YDD-11 DB0RES-10
PE1NNZ-1 to SP7YDD-11 ctl I73^ pid CE [35]
0000 36 21 20 20 20 20 31 50 45 31 4E 4E 5A 2D 31 20 6! 1PE1NNZ-1
0010 53 50 37 59 44 44 2D 31 31 20 44 42 30 52 45 53 SP7YDD-11 DB0RES
0020 2D 31 30 -10
2.7. Route Test Response
Once a Route Test Request Frame reaches its destination, a Route Test Response is sent by the destination node towards the source node. The frame is forwarded to neighbors according the routing table. The hop count is increased for each hop. Note that a response frame may follow a different path backwards to the source node when there are differences in the routing path for the source and destination along the path. Once a Route Test Response reaches the source node, the user session will be informed (via the QSO number) and routing entries may be updated with actual route round trip time (the time between the request and response).
Format: 7HQQQQQSSSSSSSSS [XXXXXXXXX ]DDDDDDDDD
H TTL Hop-count (ASCII ' ' biased)
Q User's QSO number on the source node where the Route Test was initiated
S Source Node (variable string with Callsign and optional '-' SSID, when not zero)
X Digipeater Node, there can be multiple entries
D Destination Node
Example: 7. 1PE1NNZ-1 SP7YDD-11 SR1DSZ SR6DWH-11 SR6DWC-11 IW8PGT-15 IW6NDX DB0ERF-13 DB0RES-10
SP7YDD-11 to PE1NNZ-1 ctl I47^ pid CE [89]
0000 37 2E 20 20 20 20 31 50 45 31 4E 4E 5A 2D 31 20 7. 1PE1NNZ-1
0010 53 50 37 59 44 44 2D 31 31 20 53 52 31 44 53 5A SP7YDD-11 SR1DSZ
0020 20 53 52 36 44 57 48 2D 31 31 20 53 52 36 44 57 SR6DWH-11 SR6DW
0030 43 2D 31 31 20 49 57 38 50 47 54 2D 31 35 20 49 C-11 IW8PGT-15 I
0040 57 36 4E 44 58 20 44 42 30 45 52 46 2D 31 33 20 W6NDX DB0ERF-13
0050 44 42 30 52 45 53 2D 31 30 DB0RES-10
and will notify the user with:
*** DB0RES (10-10) T=12
=>
*** route: PE1NNZ-1 SP7YDD-11 SR1DSZ SR6DWH-11 SR6DWC-11 IW8PGT-15 IW6NDX DB0ERF-13 DB0RES-10
Conclusion
The FlexNet auto router routes a packet to a destination by looking-up it up and setting the digipeater field to the next node in the path for that destination. The actual transport of users sessions are terminated per hop and hence the auto router does not route packet but proxies the connections.
For the route management, the FlexNet nodes establish a dedicated connection for each link over which the SSID ranges of the nodes are initially communicated; test frames and route information follows.
Test frames periodically measure the round-trip time of a link to derive an idea about the actual link-quality (availability, the effects of utilization, packet-loss and link-speed). Changes in the link quality will lead to the forwarding of route updates to neighbor links, which in effect are forwarded further and further to their neighbor links. Since with each forwarding step the trip times are continuously incremented with the routing and link round trip-times, the entire network do have a single view what the fastest (and most reliable) path is to a destination, and this is used by the auto router for routing.
The following rule applies: when a neighbor sends a route update for a certain destination; 1. it shall not be forwarded back to the neighbor; 2. it shall not be forwarded when there is already a destination entry with a faster trip-time; 3. it shall not be forwarded above a certain trip time threshold. In this way, network information can be propagating through the network, even when there are circular loops.
A change in the link-state or RTT will be detected by the nodes and result in the forwarding of route updates according the rule. When a link goes down, all the destinations that were originally announced by the neighbor will be dropped (or replaced by trip time of alternate path), and result in the forwarding of route updates according the rule.
Route information may be distributed in a pushed or polled (token-based) fashion, or a combination. Trip time updates and unreachability should be pushed to spread fast, new destination entries may be retrieved in polled fashion and are therefore slower and this gives a certain degree of control on the network expansion rate.
References
[JOST90] G. Jost, DK7WJ and J. Sonnabend, DG3FBL, “FlexNet, the European Solution”, p.127-133, 1990
https://www.scribd.com/document/464843132/ARRL-Computer-Networking-Conference-9-1990
[JOS95] G. Jost, DK7WJ, “An Introduction to FlexNet”, 2nd edition, 1995.
https://web.tapr.org/meetings/DCC_1995/DCC1995-FlexNet-DK7WJ-N2IRZ.pdf
[JOST98] G. Jost, DK7WJ, "FlexNet Sysop Manual v3.3h", 1998
http://db0fhn.efi.fh-nuernberg.de/doku.php?id=projects:pcflex:doc
Read previous mail | Read next mail
| |
