RFC 981
Experimental multiple-path routing algorithm
RFC 981: An Experimental Multiple-Path Routing Algorithm 🦋
okay bestie, this is part 1 of 6 💖 Here's the title block so you know who wrote it and where it fits:
- Series: Network Working Group 🌸
- Number: RFC 981
- Author: D. L. Mills, M/A-COM Linkabit ✨
- Date: March 1986 📅
- Status: experimental (the Status of This Memo section below says so too) 🧪
- Obsoletes / Updates: the header doesn't list any RFCs that this one obsoletes or updates 🫶
Status of This Memo ✨
okay so this RFC is about an experimental multiple-path routing algorithm 🧪 It was built for a packet-radio broadcast channel, and it talks about how the prototype was designed and tested. It's presented as an example of a whole class of routing algorithms and database management techniques that could end up being useful for the wider Internet community 🌈 The part that's highkey the most interesting is how it computes, picks, and ranks a ton of speculative routes without blowing through the limited computational resources it has 🧠 Discussion and suggestions for improvements are totally welcome 💬 And distribution of this memo is unlimited 🎀
Abstract 💜
this doc introduces wiretap algorithms 🕵️♀️ These are a class of routing algorithms that work out quasi-optimum routes for stations that share a broadcast channel, even when some stations are hidden from others. The wiretapper secretly watches the paths (source routes) that other stations use to send traffic on the channel, and then uses a heuristic set of factors and weights to build speculative paths for its own traffic 👀
The prototype, called the Wiretap Algorithm here, was designed for the AX.25 packet-radio channel 📻 It's pretty similar in a lot of ways to the shortest-path-first (spf) algorithm used in the ARPANET and elsewhere. Honestly it's a variation within a class of algorithms (the Viterbi Algorithm is in there too!) that build optimum paths on a graph, using a distance that's a weighted sum of factors assigned to the nodes and edges 🧚
Here's where Wiretap is different from conventional algorithms. It doesn't just compute the primary route (a minimum-distance path). It also computes extra paths, ordered by distance, that act as backups if the primary route fails 🔥 That's also super useful for discovering new paths that haven't been spotted on the channel before 🦋
Since the amateur AX.25 packet-radio channel is very active around the Washington, DC, area and carries a good amount of traffic under punishing conditions, it was considered a sufficiently heroic environment for a convincing demo of the prototype 💅 It was implemented as part of an IP/TCP driver for the LSI-11 processor running the "fuzzball" operating system 🍓 The driver connects over a serial line to a 6809-based TAPR-1 processor running the WA8DED firmware, which controls the radio equipment in both virtual-circuit and datagram modes 📡 The prototype gives you primary and alternate routes, can route around congested areas, and can change routes during a connection, which is giving main character energy 👑 This document describes the design, implementation, and initial testing of the algorithm 🌸
1. Introduction ✨
okay so this document covers the design, implementation, and initial testing of the Wiretap Algorithm, which is a dynamic routing algorithm for the AX.25 packet-radio channel [4] 📻 The AX.25 channel runs in CSMA contention mode on VHF frequencies, using AFSK/FM modulation at 1200 bps 🎶 The AX.25 protocol itself is similar to the X.25 link-layer protocol LAPB, but it has an extended frame header. That header holds a string of radio callsigns that represents a path between two end stations. The path is usually picked by the operator, and it might go through one or more intermediate packet repeaters, a.k.a. digipeaters 🐾 Most stations can work as intermediate systems (digipeaters) and as end systems in terms of the ISO model, so they're multitaskers 💖
Wiretap passively monitors the frames sent on the channel so it can build a dynamic database that's used to figure out optimum routes 👀 The algorithm runs in real time and produces a set of paths ordered by increasing total distance. It gets that distance from a shortest-path-first procedure that's similar to the one the ARPANET uses now and that's planned for the new Internet gateway system [2] 🧚 The implementation gives you optimum routes (based on the chosen factors and weights) at initial-connection time for virtual circuits, and again for each datagram transmission 🎀 This document is an initial status report and overview of the prototype for the LSI-11 processor running the "fuzzball" operating system 🍓
The big win with routing algorithms like Wiretap is that digipeater paths can be avoided when direct paths are available. Digipeaters only get used when they're actually necessary, and also to discover hidden stations 🦋 At this exploratory stage, Wiretap's scope has been intentionally limited to passive monitoring 🔍 In a later stage, the scope might expand to include active probes to find hidden stations, and clustering techniques to manage the distribution of large amounts of routing information 🌈
The AX.25 channel interface is the 6809-based TAPR-1 processor running the WA8DED firmware (version 1.0). It's connected to the LSI-11 by a 4800-bps serial line 🔌 As an option, the WA8DED firmware produces a monitor report for each received frame of a selected type, including U, I, and S frames 📋 Wiretap processes each of these reports to pull out routing information, and (optionally) saves them in the system log file 💾 Here's a typical report:
fm KS3Q to W4CQI via WB4JFI-5* WB4APR-6 ctl I11 pid F0So the originating station is KS3Q and the destination is W4CQI 🎯 The frame got digipeated first by WB4JFI-5 and then by WB4APR-6. It's an I frame (the sequence numbers follow the I indicator), and it has protocol identifier F0 (hex) 🧾 The asterisk "*" means the report was received from that station. If there's no asterisk, the report was received from the originator 🫶
2. Design Principles 💅
okay so a path is a concatenation of directed links 🔗 It starts at one station, goes through one or more digipeaters, and ends at another station. Each link is described by a set of factors, like cost, delay, or throughput, which can be computed or estimated 📊 Wiretap computes several intrinsic factors for each link and updates the routing database, which is made up of node and link tables 🗂️ The weighted sum of these factors for a link is that link's distance. The sum of the link distances along a path is that path's distance 🧮
Here's the vibe Wiretap is going for. The distance of a link should reflect the a-priori probability that a packet will successfully get across that link, relative to the other choices the sending node has 🎯 So the probability of a non-looping path is the product of the probabilities of its links 🌸 Following the technique of Viterbi [1], it's convenient to represent distance as a logarithmic transformation of probability, and that transformation then becomes a metric 🧠 That said, the underlying probabilities aren't considered directly in what follows, because the distances are estimated on a heuristic basis 🙈
Wiretap includes an algorithm that builds a set of paths, ordered by distance, between given end stations. It uses the factors and weights stored in the routing database 🧚 Those paths can be thought of as optimum routes between these stations, given that particular assignment of factors and weights ✨ In the prototype, one of the end stations has to be the Wiretap station itself. In principle though, the Wiretap station can generate routes for other stations, as long as the information in its database applies to them 💜
Note that Wiretap effectively builds minimum-distance paths in the direction from the destination station to the Wiretap station 🔄 Then, based on that info, it computes the optimum reciprocal routes from the Wiretap station to the destination station. The expectation is that the destination station also runs its own routing algorithm, which computes its own optimum reciprocal routes (i.e. the optimum direct routes from the Wiretap station) 🫂 But the routing databases at the two stations might diverge because of congestion or hidden stations, so the computed routes might not match up 🙃
In principle, Wiretap-computed routes can be fine-tuned using information from not only the stations it's directly talking to, but also from others that might hear them 👂 The most interesting scenario would be for all stations to exchange Wiretap information using a suitable distributed protocol. But at the moment that's beyond the scope of the prototype 🚧 Still, suboptimum but useful paths can be obtained the traditional, simple way: one station uses a Wiretap-computed route, and the other uses its reciprocal, as determined from the received frame header 📦 So yep, Wiretap is compatible with existing channel procedures and protocols, which is iconic behavior 🌈🫶
3. Implementation Overview ✨
okay so the prototype Wiretap implementation for the LSI-11 has two routines 💅. The first is the wiretap routine, which pulls info out of received monitor headers and builds the routing data base. The second is the routing routine, which calculates paths using whatever's in that data base. The data base has three tables: the channel table, node table and link table.
The channel table has an entry for each channel (virtual circuit) supported by the TAPR-1 processor running the WA8DED firmware, five in the present configuration. Honestly, the structure and use of this table are only incidental to the algorithm, so we won't be digging into it any further 🙈
The node table has an entry for each distinct callsign heard on the channel (which may be a collective or beacon identifier). Each entry holds node-related routing info, the latest computed route and other misc stuff. The table is indexed by node ID (NID), which gets used in the computed route and in other tables instead of the awkward callsign string 🎀. The link table has an entry for each distinct (unordered) node pair seen in a monitor header. Each entry stores the from-NID and to-NID of the first instance found, plus link-related routing info and other misc stuff. Both tables are dynamically managed using a cache algorithm based on a weighted least-recently-used replacement mechanism, which we'll get to later 🧚
Appendix A has candidate node and link tables for illustration. These were built in real time by the prototype from off-the-air monitor headers collected over a typical 24-hour period 🌈. Each node table entry takes 26 bytes and each link table entry takes four bytes. The maximum size of the node table is currently 75 entries, and the link table can hold 150. Once the cache algorithm has stabilized for a day or two, it's normal to have about 60 entries in the node table and 100 in the link table 💜.
The node table and link table together have everything needed to build a network graph and calculate paths on that graph between any two end stations, not just the ones involving the Wiretap station. BUT (and this is a big but 😭), the Wiretap station doesn't in general hear all the other stations on the channel, so it may pick suboptimum routes. In the Washington, DC, area, though, most stations use one of several digipeaters, which are in general heard reliably by other stations in the area. So a Wiretap station can eventually capture routes to almost all other stations using the above tables and the routing algorithm described later ✨.
4. The Wiretap Routine
The wiretap routine gets called to process each monitor header 🦋. It pulls each callsign out of the header in turn and searches the node table for the corresponding NID, making a new entry and NID if one isn't already there. The result is a string of NIDs, starting at the originating station, going through a maximum of eight digipeaters, and ending at the destination station. For each pair of NIDs along this string, the link table gets searched for either the direct link (as shown in the string) or its reciprocal, which is the direction towards the originator.
Here's a diagram of what happens, for a monitor header with an apparent path from station 4 to station 6 via digipeaters 7, 2 and 9 in sequence. It just so happens the header was heard by the Wiretap station (0) from station 2 👀.
(4) (7) (2) (9) (6)
orig o------>o<=====>o------>o------>o dest
|
|
V
(0)
wiretapSo, the fact that the header was heard from station 2 suggests the path from station 4 to station 2 and then on to station 0 is viable. That means each link along this path can be marked "heard" in that direction. The viability of the path from station 2 to station 6, though, can only be presumed, unless there's additional evidence 🤔. If the header is from an AX.25 I or S frame (but not a U frame), then an AX.25 virtual circuit has apparently been previously established between the end stations, and the presumption gets stronger 💪. In that case, each link from 4 to 6 is marked "synchronized" (but not the link from 2 to 0).
Not all stations can both originate frames and digipeat them 💀. Station 4 is observed to originate, and station 7 is observed to digipeat. Station 9 is only a presumptive digipeater, and there's no evidence that the remaining stations can originate frames. So the link from station 4 to station 7 is marked "source", and the link from station 7 to station 2 is marked "digipeated."
Depending on congestion and hidden stations, the reciprocal path (from station 6 back to station 4) might have pretty different link characteristics 🌸. That's why a link can be recognized as heard in each direction independently. In the diagram above, the link between 2 and 7 has been heard in both directions, so it's marked "reciprocal." There's only one "synchronized" mark, though, and it can be set in either direction. If a link isn't marked either heard or synchronized, then any presumption about whether it can carry traffic is highly speculative (the traffic is probably a beacon or "CQ"). If it gets marked synchronized later, the presumption gets stronger, and if it gets marked heard in the reciprocal direction later, the presumption is confirmed 🎉.
Experience shows that a successful routing algorithm for any packet-radio channel needs provisions for congestion avoidance 🚦. There are two straightforward ways to handle this. The first is a static measure of node congestion, based on the number of links in the network graph incident at each node. The wiretap routine computes this number and stores it in the node table as it adds entries to the link table.
The second one is a dynamic measure of node congestion, and it isn't implemented yet 🛠️. It tallies the number of link references during the most recent time interval (of a specified length). The plan was suggested by the reachability mechanism used in the ARPANET and the Exterior Gateway Protocol [3]. Each node gets an eight-bit shift register, shifted from high-order to low-order bits, with zero-bits preceding the high-order bit. The shift happens at the rate of one shift every ten seconds. If a header with a path involving that node is found during the preceding ten-second period, the high-order bit of the register gets set to one. When a path is calculated, the one-bits in the register are totalled and used as a measure of dynamic node congestion. The time interval specified here is 80 seconds, which is believed appropriate for the AX.25 channel dynamics 🦄.
5. Factor Computations and Weights
The data items produced by the wiretap routine get processed to produce a set of factors. The routing routine uses those factors to develop optimum routes 🧠. To make sure the algorithm converges in a stable and reliable way as it builds and discards candidate paths leading to these routes, the factor computations should have the following properties:
- All factors should be positive, monotone functions which increase in value as system performance degrades from optimum.
- The criteria used to estimate link factors should be symmetric. In other words, their values should not depend on the particular direction the link is used.
- The criteria used to estimate node factors should not depend on the particular links that traffic enters or leaves the node.
Each factor has a weight assignment that reflects its contribution to the distance calculation, with larger weights meaning greater importance ⚖️. For comparison with other common routing algorithms, and for effective control of the computational resources required, it may be desirable to impose additional restrictions on these computations. That could be a topic for further study. Obviously, the success of this routing algorithm depends on cleverly (i.e. experimentally) determined factor computations and weight assignments 🔬.
The particular choices in the prototype implementation should be considered educated first guesses 🎀. They might get changed, perhaps in dramatic ways, in later implementations. Still, the operation of the algorithm in finding optimum routes holds across all choices of factor computations and weights, so it's unchanged 👑. Remember, the wiretap routine generates data items for each node and link heard, and saves them in the node and link tables. The routing routine processes these items to generate the factors shown below in Table 1 and Table 2 💅.
Factor Weight Name How Determined
---------------------------------------------------------------
f0 30 hop 1 for each link
f1 50 unverified 1 if not heard either direction
f2 5 non-reciprocal 1 if not heard both directions
f3 5 unsynchronized 1 if no I or S frame heard
Table 1. Link Factors Factor Weight Name How Determined
---------------------------------------------------------------
f4 5 complexity 1 for each incident link
f5 20 digipeated 1 if station does not digipeat
f6 - congestion (see text)
Table 2. Node FactorsLet's talk link factors first 🔗. The "hop" factor is assigned as one for each link, and it represents the bias found in other routing algorithms of this type. The goal is for the routing mechanism to degenerate to minimum-hop when there's no other information 🦋. The "unverified" factor is assigned as one if the heard bit isn't set (not heard in either direction). The "non-reciprocal" factor is assigned as one if the reciprocal bit isn't set (not heard in both directions). The "unsynchronized" factor is assigned as one if the synchronized bit isn't set (no I or S frames observed in either direction).
Now for node factors 🌟. The "complexity" factor is computed as the number of links incident at the node. The "congestion" factor is computed as the number of intervals, out of the eight ten-second intervals preceding the time of observation, in which a frame was transmitted to or through the node. The "digipeated" factor is assigned as one if the node is only a source (i.e. no digipeated frames have been heard from it). For the purposes of path-distance calculations, the node factors are taken as zero for the endpoint nodes, since their contribution to any path would be the same 🥰.
6. The Routing Routine ✨
okay so the dynamic database that the wiretap routine builds gets used by the routing routine to work out routes whenever they're needed 🗺️. Usually that only has to happen when the first frame to a new destination gets sent, and then again at intervals after that. The intervals can be adjusted based on the retry count, congestion thresholds, and so on. The technique is a variation of the Viterbi Algorithm [1], which is kind of like the shortest-path-first algorithm used in the ARPANET and elsewhere [2]. It builds a set of candidate paths across the network graph, going from the destination back to the source, in increasing number of hops. It keeps going until it has found all the complete paths that meet a specified condition. Then it picks the one with the minimum distance as the primary route and ranks the rest as alternate routes. so clean 💅
There are a bunch of algorithms for finding the minimum-distance path between two nodes on a graph with a given metric. The prototype implementation uses a dynamic path list of entries that gets derived from the link table 🧩. Each list entry holds (a) the NID of the current node, (b) a pointer to the preceding node on the path, (c) the hop count, and (d) the distance from that node to the final destination node of the path:
[ NID, pointer, hop, distance ] .The algorithm starts with a list that only contains the entry [ dest-NID, 0, 0, 0 ], where dest-NID is the final destination NID. Then it scans the list, starting from that entry. For each entry, it scans the link table for every link where either the to-NID or the from-NID matches NID, and for each match it inserts a new entry:
[ new-NID, new-pointer, hop + 1, distance + weight ] ,The new-NID is the link's to-NID if its from-NID matches the old NID. Otherwise it's the link's from-NID. The new-pointer is set to the address of the old entry, and the weight is computed from the factors and weights we covered earlier 🎀. The algorithm keeps picking up the next entries and scanning the link table until one of these happens: no entries are left to process, the allocated list area is full, or the maximum hop count or distance gets exceeded, as explained below.
Now here's the vibe check 👀. In the Viterbi Algorithm, which works in a similar way, when paths merge at a single node, all but one of the minimum-distance paths (called survivors) get abandoned. If you only need one minimum-distance path, Wiretap does exactly that. But when you need alternate paths, every non-looping path is a potential survivor. To stop the list from exploding in size, and to suppress loops, any new list entry whose new-NID matches the NID of an existing entry on the path to the final destination NID gets suppressed. Paths with a hop count above (currently) eight, or a distance above 255, get abandoned 🙅♀️.
If the Wiretap station NID shows up in the from-NID of an entry that gets inserted into the list, then a complete path has been found 🏁. As it goes, the algorithm keeps track of the minimum distance and minimum hop count across all the complete paths it finds. If you only want the primary route (one minimum-distance path), then any list entry whose distance is greater than the minimum distance, or whose hop count is greater than the maximum hop count (plus one), gets abandoned, and no more processing happens for it. If you want alternate routes, the hop-count test still applies, but the minimum-distance test doesn't 🦋.
The pruning mechanisms above are designed so that the algorithm always finds all complete paths with the minimum hop count and with the minimum hop count (plus one). Those are the ones designated as alternate routes. The factor computations and weights are meant to favor minimum-hop paths in most situations, but to let the path length grow by no more than one extra hop when things are extremely congested 🚦. So the minimum-distance path (the primary route) has to be found among the alternate paths. Usually it's one of the minimum-hop paths, but not always!!
When processing finishes, the complete paths get ranked first by distance, then by the position of the final entry in the list. Since the list is built in hop-count order, that gives a well-defined ordering 📋. The first path is the primary route, and the remaining ones are alternatives to fall back on if all the lower-ranked routes fail.
Time and space complexity is worth thinking about too 🧠. For the example in Appendix A, which has 58 nodes and 98 links, computing all the primary and secondary routes takes an average of about 30 list entries. Sometimes it overflows the maximum size, which is currently 100 entries. Each step means scanning all the links and searching for loops along the maximum path length. In principle, that could add most of the links to the list at every new hop. So the resources needed can escalate dramatically unless you use effective pruning techniques like the ones above 😭.
The prototype implementation needs 316 milliseconds on an LSI-11/73 to calculate the 58 primary routes to all 58 nodes, which works out to an average of about 5.4 milliseconds per route. It needs 1416 milliseconds to calculate the 201 combined primary and alternate routes to all 58 nodes, which is an average of about 3.4 milliseconds per route ⏱️.
7. Data Base Housekeeping 🧹
In normal operation, Wiretap picks up a lot of errors and random junk 🗑️. That's because any station can call any other station using ad-hoc heuristics, and those strategies are often counterproductive. So Wiretap can end up adding speculative and erroneous links to the database. In practice this happens pretty often, because operators manually try different paths to stations that might be shut down, busy, or blocked by congestion. Still, since Wiretap works entirely by passive monitoring, speculative links may be the main way new paths get discovered 🔍.
The number of nodes and links, speculative or not, can grow without limit as the Wiretap station keeps monitoring the channel 📈. When the node table or link table gets close to its maximum size, a garbage-collection procedure is invoked automatically 🗑️✨. The prototype borrows the idea from virtual-memory storage management, where the oldest unreferenced page gets replaced when a new page frame is needed. Every link table entry has an age field. It gets incremented once each minute while its value is less than 60, and once each hour after that. It gets reset to zero when the link is found in a monitor header. When the link table needs new space, the link with the largest product of age and distance (as determined by the factor computations and weights) gets removed first 💀.
Every node table entry includes the congestion factor from earlier. That's a count of the links incident at that node, plus one 🔢. As links get removed from the link table, those counts go down. If a node's count drops to one, that node gets removed. So when the node table needs new space, links get removed as described above until enough space has been reclaimed 🫶.
On top of all that, there's a safety net 🛟. Tables shouldn't get captured by occasional speculative spasms on one hand, or go stagnant from excessively stale information on the other. So if the age counter goes past a predetermined threshold, the link is removed from the database regardless of its distance. Right now that threshold is fifteen minutes for a speculative link and 24 hours for other links 🌸. The authors expect these procedures to get better as experience with the implementation matures 🌈.
8. Summary and Directions for Further Development ✨
okay bestie, Wiretap is basically an initial experiment to see how well passive monitoring works for managing the AX.25 packet-radio channel 📻💖 the early results are giving encouraging vibes, but the optimization effectively still needs a LOT of work 💀 we also need some real day-to-day experience running the prototype, where people can try out different combinations of weight assignments 🎀
the prototype has been in use for about four months as of this writing 🌸 and a bunch of lessons were learned pretty quickly 🫶 it has a finite-state automaton to manage the initial connection requests, and it can retry SABM frames along alternate routes that Wiretap computes 🦋 there's also a simple but effective heuristic for generating speculative paths: it artificially adds links between the destination station and the Wiretap station, plus links to every other station in the node table that is identified as a digipeater 🧚 after that, the algorithm runs as described above to generate the primary and alternate routes. there's an example of this technique in the Appendix 💅
this technique works very well, at least during the initial-connection phase of virtual-circuit mode 🔥 the catch is that it needs a lot of computational resources, because there are so many possible paths, ranging from reasonable to absolutely outrageous 💀 in datagram mode, only the primary route is computed 🍓 and the heuristic path-abandonment strategy described above is a critical performance determinant in this area 👑
⚠️ there is a mechanism that lets the TAPR-1 processor tell the prototype that a lower-level AX.25 virtual circuit has failed, so an alternate path can be tried. BUT there is no built-in mechanism to signal the failure of an upper-level TCP connection 😭 TCP uses IP datagrams wrapped in AX.25 I frames (connection mode) or UI frames (connectionless mode). this is a generic problem with any end-system protocol where the peers are physically far away from the link-level entities. experience suggests that providing a two-way conduit for sharing control information between protocol layers may be seriously underestimated 🙈
the prototype manages processor and storage demands in relatively simple ways, which can lead to a lot of inefficiencies 🌈 it's very clear that in any widely distributed version of Wiretap, these demands will have to be carefully managed 💜 like we said earlier, effective provisions to purge old information (especially speculative links) are vital 🧚 and we also need provisions to control the intervals between route computations, for instance as a function of link state and traffic mode ⭐
the next step in the evolution toward a fully distributed routing algorithm is introducing active probing techniques 🦋 this should considerably improve the ability to discover new paths and fine-tune existing ones 💖 it should be possible to implement an active probing mechanism while staying compatible with the passive-only Wiretap, and also compatible with other stations that use no routing algorithms at all 🫶 it does seem like judicious use of beacons will be needed to discover and renew paths when there's no traffic, along with some kind of echo/reply mechanism similar to the ICMP Echo/Reply support that is required of Internet hosts 🎀
to really take advantage of the flexibility that routing algorithms like Wiretap provide, the AX.25 specification will need a revision to include "loose" source routing in addition to the current "strict" source routing 🌸 strict source routing requires every forwarding stage (callsign) to be explicitly declared 🙈 loose source routing would let some or all stages be left to the discretion of the local routing agent or digipeater ✨ one suggestion is to devise a special collective indicator or callsign that could signal a Wiretap digipeater to insert the computed route string following its callsign in the AX.25 frame header 👑
congestion detection and response is a particularly difficult area for any routing algorithm 😭 some hints on how the existing Wiretap mechanism can be improved are indicated in this document. more work is needed, especially on the hidden-station problem 🧚 and perhaps the most useful feature of all would be a link-quality indication derived from the radio, modem, or frame-level procedures (checksum failures) 💅 conceivably, this information could be included in beacon messages that digipeaters broadcast occasionally 📻
it's quite likely that the most effective application of routing algorithms in general will be at local-area digipeater sites 🌈 one reason is that these stations may have off-channel trunking facilities that connect different areas, and they may exchange wide-area routing information over those facilities 💖 the routing information collected by the local-area Wiretap stations could then be exchanged directly with the wide-area sites 🦋
9. References
- [1] Forney, G.D., Jr. The Viterbi Algorithm. Proc IEEE 61, 3 (March 1973), 268-278. 📚
- [2] McQuillan, J., I. Richer and E. Rosen. An overview of the new routing algorithm for the ARPANET. Proc. ACM/IEEE Sixth Data Comm. Symp., November 1979. 📚
- [3] Mills, D.L. Exterior Gateway Protocol Formal Specification. DARPA Network Working Group Report RFC-904, M/A-COM Linkabit, April 1984. 📚
- [4] Fox, T.L., (Ed.). AX.25 amateur packet-radio link-layer protocol, Version 2.0. American Radio Relay League, October 1984. 📚
Appendix A. An Example 🎀
okay so this example is going to show how Wiretap builds primary and alternate routes from candidate node and link tables 🧚 the candidate tables came from a scenario where normal traffic was monitored on the 145.01-MHz AX.25 packet-radio channel in the Washington, DC, area during a typical 24-hour period 🌆 the node and link tables below give you an idea of what the constructed data base looks like, and they're also the basis for the example 💜
Figure 1 is a candidate node table showing the node ID (NID), callsign, and related information for each station 💅 the Route field contains the primary route (the minimum-distance path) as a string of NIDs, going from the origination station (NID = 0) to the destination station shown, except for the endpoint NIDs 🦋 if there's no route string, the station is directly reachable without a digipeater's help ✨ also note that the originating station is always the first entry in the node table (here, W3HCF), and it's initialized with defaults before the algorithm starts 👑
NID Callsign Flags Links Last Rec Wgt Route
-------------------------------------------------------
0 W3HCF 005 26 15:00:19 255
1 WB4APR-5 017 18 16:10:38 30
2 DPTRID 000 3 00:00:00 210 1
3 W9BVD 005 3 23:24:33 40
4 W3IWI 015 5 16:15:30 35
5 WB4JFI-5 017 34 16:15:30 35
6 W3TMZ 015 2 01:00:49 150 1
7 WB4APR-6 017 14 14:56:06 35
8 WB4FQR-4 017 4 06:35:15 40
9 WD9ARW 015 3 14:56:04 115 11
10 WA4TSC 015 3 15:08:53 115 11
11 WA4TSC-1 017 9 15:49:15 35
12 KJ3E 015 4 15:57:26 155 1
13 WB2RVX 017 3 09:19:46 135 7
14 AK3P 015 2 12:57:53 185 7 15
15 AK3P-5 016 4 12:57:53 135 7
16 KC2TN 017 3 04:01:17 135 7
17 WA4ZAJ 015 2 21:41:24 240 5
18 KB3DE 015 3 23:38:16 35
19 K4CG 015 3 13:29:14 35
20 WB2MNF 015 2 04:01:17 180 7 16
21 K4NGC 015 3 14:57:44 90 8
22 K3SLV 005 2 03:40:01 160 1
23 KA4USE-1 017 6 14:57:44 35
24 K4AF 005 3 12:46:38 40
25 WB4UNB 015 2 06:45:09 240 5
26 PK64 005 3 02:50:54 40
27 N4JOG-2 015 3 13:24:53 35
28 KX3C 015 4 02:57:29 35
29 W3CSG 015 4 06:10:17 115 11
30 WD4SKQ 015 3 16:00:33 35
31 WA7DPK 015 3 01:28:11 35
32 N4JGQ 015 3 22:57:50 35
33 K3AEE 005 3 03:52:43 40
34 WB3ANQ 015 3 04:01:27 140 7
35 K2VPR 015 2 12:07:51 240 5
36 G4MZF 015 3 01:38:30 35
37 KA3ERW 015 2 03:11:17 155 1
38 WB3ILO 015 2 02:10:34 140 7
39 KB3FN-5 016 4 06:10:17 110 11
40 KS3Q 015 5 15:54:57 35
41 WA3WUL 015 2 03:36:18 135 7
42 N3EGE 015 3 15:58:01 160 1
43 N4JMQ 015 2 08:02:58 185 7 13
44 K3JYD-5 016 5 15:58:01 155 1
45 KA4TMB 015 3 16:15:23 115 11
46 KC3Y 015 2 04:14:36 155 1
47 W4CTT 005 2 12:21:33 245 5
52 K3JYD 015 2 02:16:52 155 1
54 WA5WTF 015 2 02:01:20 240 5
55 KA4USE 005 3 23:56:02 105 23
56 N3BRQ 005 2 02:00:36 40
57 KC4B 015 2 22:10:37 240 5
58 WA5ZAI 005 2 12:44:03 40
59 K4UW 005 2 02:36:05 40
60 K3RH 015 2 01:20:47 135 7
61 N4KRR 015 3 10:56:50 35
62 K4XY 015 2 04:53:16 240 5
64 WA6YBT 015 2 05:13:07 190 7 15
Figure 1. Candidate Node Tablein the table above, the Dist field shows the total distance of the primary route 📏 the Links field shows the complexity factor, which is the number of links incident at that node (plus one) 🧠 and the Last Rec field shows the time (UT) the station was last heard, directly or indirectly ⏰ the Flags field shows, among other things, which stations have originated frames and which have digipeated them 🙈 the bits in this field are in octal format, and they're interpreted as follows (bit 0 is the rightmost bit) 🔢
Bit Function
--------------------
0 originating station
1 digipeater station
2 station heard (Last Rec column)
3 station synchronized connectionout of the 58 stations shown in Figure 1, eleven are digipeaters, and all but three of those also originate traffic 🦋 all but twelve stations have either originated or digipeated a synchronized connection 🫶 and only one "station," DPTRID, which is actually a beacon, hasn't been heard originating or digipeating any traffic 😭
Figure 2 illustrates a candidate node table of 98 links 🌈 it shows the from-NID, to-NID, Flags, and Age information for each link as it was collected 💖 the bits in the Flags field, which is in octal format, are interpreted as follows (bit 0 is the rightmost bit):
Okay bestie, first up is the flags legend 🎀 Bit 0 is source, bit 1 is digipeated, bit 2 is heard, bit 3 is synchronized, and bit 4 is reciprocal ✨
Bit Function
-------------------
0 source
1 digipeated
2 heard
3 synchronized
4 reciprocalNext is the big candidate link table 🦋 Each row is a link: From, To, Flags, and Age.
Figure 2. Candidate Link Table
From To Flags Age From To Flags Age
--------------------------- ---------------------------
5 0 017 0 1 0 037 5
4 0 015 0 5 4 035 0
4 1 015 28 7 0 017 60
9 5 015 60 1 5 006 56
4 7 015 60 11 0 017 24
7 15 036 62 7 13 037 60
12 1 015 71 15 14 035 62
7 16 037 70 12 5 015 71
19 0 015 61 16 20 035 70
5 11 036 60 23 0 017 60
5 24 035 73 30 0 015 71
29 11 015 69 5 29 035 73
8 21 035 67 8 5 017 67
31 0 015 72 31 5 015 72
32 0 015 74 32 5 015 69
40 5 015 17 40 0 015 19
34 7 015 70 35 5 015 62
1 40 035 74 38 7 015 71
5 36 035 72 45 5 015 0
36 0 015 72 5 30 035 14
37 1 015 70 44 5 016 14
12 44 015 17 46 1 015 69
34 1 015 72 44 1 016 70
5 23 036 60 9 11 015 79
10 11 015 60 1 6 035 72
27 5 015 61 11 1 006 83
45 11 015 76 52 1 015 71
5 2 000 14 8 0 005 76
57 5 015 75 17 5 015 75
3 0 005 74 3 5 005 74
26 5 005 71 26 0 005 74
18 5 015 74 18 0 015 74
55 5 005 73 24 0 005 62
61 0 015 63 55 23 005 73
54 5 015 71 61 5 015 63
59 0 005 71 56 0 005 71
5 7 006 71 7 60 035 72
28 0 015 71 62 5 015 69
1 7 036 70 28 5 015 71
7 41 035 70 28 1 015 71
58 0 005 62 1 22 005 70
33 7 005 70 33 0 005 70
64 15 015 69 25 5 015 67
39 10 035 68 11 39 036 68
43 13 015 65 29 39 015 68
40 7 015 62 47 5 005 62
19 23 015 61 27 0 015 61
42 1 005 23 23 21 035 60
1 2 000 5 42 44 015 14The following tables show the routing algorithm doing its thing in a few typical situations 🧚 Each line is one step where an entry gets pulled off the path list and new entries get figured out. The "Step" column numbers each step, and the "To" column is the NID of the station at that step. The "Ptr" column points back to the earlier step on the path to the destination. "Hop" and "Dist" are the total hop count and the computed distance along that path. 💅
Here's a fairly typical one 👑 The destination station isn't directly reachable, but a few multi-hop paths exist through different digipeaters. The algorithm finds four digipeaters: 1, 5, 11 and 39. All of them except the last are directly reachable from the originating station. That gives two routes with two hops and two with three hops 🌸 Only the steps that lead to complete paths are shown.
Destination: 29 Station: W3CSG
Step NID Ptr Hop Dist Comments
-------------------------------------------------------------
0 29 0 0 0
1 5 0 1 30
2 11 0 1 35
3 39 0 1 35
4 0 1 2 235 Complete path: 0 5 29
35 0 2 2 115 Complete path: 0 11 29
37 9 2 2 115
38 10 2 2 115
39 1 2 2 120
40 45 2 2 115
41 39 2 2 110
42 11 3 2 85
43 10 3 2 85
46 0 39 3 240 Complete path: 0 1 11 29
63 0 42 3 165 Complete path: 0 11 39 29The algorithm ranks the routes by distance first, then by their order in the list. So the two-hop route at N = 35 gets picked first, then the three-hop route at N = 63, then the two-hop route at N = 4, and finally the three-hop route at N = 46 🔥 The second choice is a three-hop route, and the third is a two-hop route, because digipeater station 5 is extremely congested. It has 34 incident links 💀
Next up is an example showing the path-pruning mechanisms 🦋 These are what keep the search focused on the paths most likely to lead somewhere useful. The algorithm finds one two-hop route and four three-hop routes. This time the full list is shown, including every step that gets abandoned, along with the reasons 🫶
Destination: 13 Station: WB2RVX
Step NID Ptr Hop Dist Comments
-------------------------------------------------------------
0 13 0 0 0
1 7 0 1 30
2 43 0 1 35 No path
3 0 1 2 135 Complete path: 0 7 13
4 4 1 2 135
5 15 1 2 130
6 16 1 2 130
7 34 1 2 135
8 38 1 2 135 No path
9 60 1 2 130 No path
10 5 1 2 140 Max distance 310
11 1 1 2 130
12 41 1 2 130 No path
13 33 1 2 140
14 40 1 2 135
15 5 4 3 210 Max distance 380
16 0 4 3 215 Complete path: 0 4 7 13
17 1 4 3 215 Max distance 305
18 14 5 3 180 Max hops 4
19 64 5 3 185 Max hops 4
20 20 6 3 175 Max hops 4
21 1 7 3 205 Max distance 295
22 0 11 3 250 Complete path: 0 1 7 13
23 4 11 3 255 Max distance 300
24 12 11 3 255 Max distance 295
25 40 11 3 250 Max distance 295
26 37 11 3 255 Max distance 285
27 46 11 3 255 Max distance 285
28 44 11 3 255 Max distance 280
29 34 11 3 255 Max distance 290
30 6 11 3 250 Max distance 280
31 52 11 3 255 Max distance 285
32 28 11 3 255 Max distance 295
33 0 13 3 215 Complete path: 0 33 7 13
34 0 14 3 215 Complete path: 0 40 7 13
35 5 14 3 215 Max distance 385
36 1 14 3 210 Max distance 300Some quick decoder notes 🍓 Steps labelled "No path" get abandoned because no links could be found that satisfy the constraints: (a) the to-NID or from-NID has to match the NID of the step, (b) the path has to stay loop-free, or (c) the total path distance has to be less than 256. Steps labelled "Max distance" get abandoned because the total distance, which is the sum of the Dist value plus the weighted node factors, would go over 256 as shown. Steps labelled "Max hops" get abandoned because the total hop count would go over the minimum hop count plus one, as shown ✨
Quick flex: if you only need the primary route, you can abandon every step whose total distance is greater than the minimum distance (135). In this case, path exploration wraps up after only 14 steps 💖
Now for a previously unknown station 🎀 That means one that isn't already in the data base. This part isn't strictly the algorithm itself, but the current system generates speculative paths. Each one is made of an imputed direct link between the originating station and the destination station, plus imputed direct links between every digipeater in the data base and the destination station. The new links time out according to the cache-management mechanism, in about fifteen minutes ⏰
Here the destination station is 74, which adds these entries to the link table 🧚
fm-NID To-NID Flags Node Type
----------------------------------
0 74 000 Originator
1 74 000 Digipeater
5 74 000 Digipeater
7 74 000 Digipeater
8 74 000 Digipeater
11 74 000 Digipeater
13 74 000 Digipeater
15 74 000 Digipeater
16 74 000 Digipeater
23 74 000 Digipeater
39 74 000 Digipeater
44 74 000 DigipeaterThere are eleven digipeaters involved, but not all of them may get used 🦋 The primary route and five alternate routes are shown below. Only five of the eleven digipeaters actually end up in use. The rest were either too far away or too heavily congested 💅 Again, only the list entries that lead to complete paths are shown.
Okay bestie, the example table keeps going, and it's giving routing-table realness 🧚💜 Each row walks one step of the path toward Destination 74 (Station CQ), so you can follow the candidates as they stack up 🦋
Destination: 74 Station: CQ
Step NID Ptr Hop Dist Comments
-------------------------------------------------------------
0 74 0 0 0
1 0 0 1 90 Complete path: 0 74
2 1 0 1 90
4 7 0 1 90
5 8 0 1 90
6 11 0 1 90
7 13 0 1 90
8 15 0 1 90
9 16 0 1 90
10 23 0 1 90
11 39 0 1 90
12 44 0 1 90
13 0 2 2 210 Complete path: 0 1 74
29 0 4 2 195 Complete path: 0 7 74
44 0 5 2 150 Complete path: 0 8 74
45 0 6 2 170 Complete path: 0 11 74
60 0 10 2 155 Complete path: 0 23 74Look at those 'Complete path' comments 😭🎀 The rows that say "Complete path" are the ones that finish the whole trip to 74, and that's the moment everything clicks ✨
Heads up: the Step numbers skip around (3, 14 through 28, 30 through 43, and so on). That's on purpose, so don't go hunting for missing rows 🙈
📦 where this page comes from
- ietf: rfc981 1986-03
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms