RFC relevance of distance

As per Relevance of the word distance, we have this rfc below:

Network Working Group D. L.
Request for Comments: 981 M/A-COM
March 1986

An Experimental Multiple-Path Routing

Status of This

This RFC describes an experimental, multiple-path routing
designed for a packet-radio broadcast channel and discusses
design and testing of a prototype implementation. It is presented
an example of a class of routing algorithms and data-base
techniques that may find wider application in the Internet community
Of particular interest may be the mechanisms to compute, select
rank a potentially large number of speculative routes with respect
the limited cumputational resources available. Discussion
suggestions for improvements are welcomed. Distribution of this
is unlimited

This document introduces wiretap algorithms, which are a class
routing algorithms that compute quasi-optimum routes for
sharing a broadcast channel, but with some stations hidden
others. The wiretapper observes the paths (source routes) used
other stations sending traffic on the channel and, using a
set of factors and weights, constructs speculative paths for its
traffic. A prototype algorithm, called here the Wiretap Algorithm
has been designed for the AX.25 packet-radio channel. Its design
similar in many respects to the shortest-path-first (spf)
used in the ARPANET and elsewhere, and is in fact a variation in
class of algorithms, including the Viterbi Algorithm, that
optimum paths on a graph according to a distance computed as
weighted sum of factors assigned to the nodes and edges

The Wiretap Algorithm differs from conventional algorithms in that
computes not only the primary route (a minimum-distance path),
also additional paths ordered by distance, which serve as
routes should the primary route fail. This feature is also
for the discovery of new paths not previously observed on
channel

Since the amateur AX.25 packet-radio channel is very active in
Washington, DC, area and carries a good deal of traffic
punishing conditions, it was considered a sufficiently
environment for a convincing demonstration of the
algorithm. It was implemented as part of an IP/TCP driver for
LSI-11 processor running the "fuzzball" operating system. The
is connected via serial line to a 6809-based TAPR-1 processor
the WA8DED firmware, which controls the radio equipmnet in

Mills [Page 1]

RFC 981 March 1986
An Experimental Multiple-Path Routing

virtual-circuit and datagram modes. The prototype
provides primary and alternate routes, can route around
areas and can change routes during a connection. This
describes the design, implementation and initial testing of
algorithm

1.

This document describes the design, implementation and
testing of the Wiretap Algorithm, a dynamic routing algorithm for
AX.25 packet-radio channel [4]. The AX.25 channel operates in
contention mode at VHF frequencies using AFSK/FM modulation at 1200
bps. The AX.25 protocol itself is similar to X.25 link-layer
LAPB, but with an extended frame header consisting of a string
radio callsigns representing a path, usually selected by
operator, between two end stations, possibly via one or
intermediate packet repeaters or digipeaters. Most stations
operate simultaneously as intermediate systems digipeaters) and
end systems with respect to the ISO model

Wiretap uses passive monitoring of frames transmitted on the
in order to build a dynamic data base which can be used to
optimum routes. The algorithm operates in real time and generates
set of paths ordered by increasing total distance, as determined by
shortest-path-first procedure similar to that used now in the
and planned for use in the new Internet gateway system [2].
implementation provides optimum routes (with respect to the
and weights selected) at initial-connection time for
circuits, as well as for each datagram transmission. This
is an initial status report and overview of the
implementation for the LSI-11 processor running the "fuzzball
operating system

The principal advantage in the use of routing algorithms like
is that digipeater paths can be avoided when direct paths
available, with digipeaters used only when necessary and also
discover hidden stations. In the present exploratory stage
evolution, the scope of Wiretap has been intentionally restricted
passive monitoring. In a later stage the scope may be extended
include the use of active probes to discover hidden stations and
use of clustering techniques to manage the distribution of
quantities of routing information

The AX.25 channel interface is the 6809-based TAPR-1
running the WA8DED firmware (version 1.0) and connected to the LSI-11
by a 4800-bps serial line. The WA8DED firmware produces as an
a monitor report for each received frame of a selected type

Mills [Page 2]

RFC 981 March 1986
An Experimental Multiple-Path Routing

including U, I and S frames. Wiretap processes each of these
extract routing information and (optionally) saves them in the
log file. Following is a typical report

fm KS3Q to W4CQI via WB4JFI-5* WB4APR-6 ctl I11 pid F

The originating station is KS3Q and the destination is W4CQI.
frame has been digipeated first by WB4JFI-5 and then WB4APR-6, is
I frame (sequence numbers follow the I indicator) and has
identifier F0 (hex). The asterisk "*" indicates the report
received from that station. If no asterisk appears, the report
received from the originator

2. Design

A path is a concatenation of directed links originating at
station, extending through one or more digipeaters and terminating
another station. Each link is characterized by a set of factors
as cost, delay or throughput that can be computed or estimated
Wiretap computes several intrinsic factors for each link and
the routing data base, consisting of node and link tables.
weighted sum of these factors for each link is the distance of
link, while the sum of the distances for each link in the path is
distance of that path

It is the intent of the Wiretap design that the distance of a
reflect the a-priori probability that a packet will
negotiate that link relative to the other choices possible at
sending node. Thus, the probability of a non-looping path is
product of the probabilities of its links. Following the
of Viterbi [1], it is convenient to represent distance as
logarithmic transformation of probability, which then becomes
metric. However, in the following the underlying probabilities
not considered directly, since the distances are estimated on
heuristic basis

Wiretap incorporates an algorithm which constructs a set of paths
ordered by distance, between given end stations according to
factors and weights contained in the routing data base. Such
can be considered optimum routes between these stations with
to the given assignment of factors and weights. In the
implementation one of the end stations must be the Wiretap
itself; however, in principle, the Wiretap station can
routes for other stations subject to the applicability of
information in its data base

Note that Wiretap in effect constructs minimum-distance paths in

Mills [Page 3]

RFC 981 March 1986
An Experimental Multiple-Path Routing

direction from the destination station to the Wiretap station and
based on that information, then computes the optimum
routes from the Wiretap station to the destination station.
expectation is that the destination station also runs its own
algorithm, which then computes its own optimum reciprocal
(i.e. the optimum direct routes from the Wiretap station). However
the routing data bases at the two stations may diverge due
congestion or hidden stations, so that the computed routes may
coincide

In principle, Wiretap-computed routes can be fine-tuned
information provided not only by its directly communicating
but others that may hear them as well. The most interesting
would be for all stations to exchange Wiretap information using
suitable distributed protocol, but this is at the moment beyond
scope of the prototype implementation. Nevertheless, suboptimum
useful paths can be obtained in the traditional and simple way
one station using a Wiretap-computed route and the other
reciprocal, as determined from the received frame header. Thus
Wiretap is compatible with existing channel procedures and protocols

3. Implementation

The prototype Wiretap implementation for the LSI-11 includes
routines, the wiretap routine, which extracts information
received monitor headers and builds the routing data base, and
routing routine, which calculates paths using the information in
data base. The data base consists of three tables, the channel table
node table and link table. The channel table includes an entry
each channel (virtual circuit) supported by the TAPR-1
running the WA8DED firmware, five in the present configuration.
structure and use of this table are only incidental to the
and will not be discussed further

The node table includes an entry for each distinct callsign (
may be a collective or beacon identifier) heard on the channel
together with node-related routing information, the latest
route and other miscellaneous information. The table is indexed
node ID (NID), which is used in the computed route and in
tables instead of the awkward callsign string. The link
contains an entry for each distinct (unordered) node pair observed
a monitor header. Each entry includes the from-NID and to-NID of
first instance found, together with link-related routing
and other miscellaneous information. Both tables are
managed using a cache algorithm based on a
least-recently-used replacement mechanism described later

Mills [Page 4]

RFC 981 March 1986
An Experimental Multiple-Path Routing

The example discussed in Appendix A includes candidate node and
tables for illustration. These tables were constructed in real
by the prototype implementation from off-the-air monitor
collected over a typical 24-hour period. Each node table
requires 26 bytes and each link table entry four bytes. The
size of the node table is presently 75 entries, while that of
link table is 150 entries. Once the cache algorithm has
for a day or two, it is normal to have about 60 entries in the
table and 100 entries in the link table

The node table and link table together contain all the
necessary to construct a network graph, as well as calculate paths
that graph between any two end stations, not just those involving
Wiretap station. Note, however, that the Wiretap station does not
general hear all other stations on the channel, so may
suboptimum routes. However, in the Washington, DC, area
stations use one of several digipeaters, which are in general
reliably by other stations in the area. Thus, a Wiretap station
eventually capture routes to almost all other stations using
above tables and the routing algorithm described later

4. The Wiretap

The wiretap routine is called to process each monitor header.
extracts each callsign from the header in turn and searches the
table for corresponding NID, making a new entry and NID if
already there. The result is a string of NIDs, starting at
originating station, extending through a maximum of eight
and ending at the destination station. For each pair of NIDs
this string the link table is searched for either the direct link,
indicated in the string, or its reciprocal; that is, the
towards the originator

The operations that occur at this point can be illustrated by
following diagram, which represents a monitor header with
path from station 4 to station 6 via digipeaters 7, 2 and 9
sequence. It happens the header was heard by the Wiretap station (0)
from station 2.

(4) (7) (2) (9) (6)
orig o------>o<=====>o------>o------>o
|
|

(0)

Mills [Page 5]

RFC 981 March 1986
An Experimental Multiple-Path Routing

Presumably, the fact that the header was heard from station 2
indicates the path from station 4 to station 2 and then to station 0
is viable, so that each link along this path can be marked "heard"
that direction. However, the viability of the path from station 2
station 6 can only be presumed, unless additional evidence
available. If in fact the header is from an AX.25 I or S frame (
not a U frame), an AX.25 virtual circuit has apparently
previously established between the end stations and the
is strengthened. In this case each link from 4 to 6 is
"synchronized" (but not the link from 2 to 0).

Not all stations can both originate frames and digipeat them.
4 is observed to originate and station 7 to digipeat, but station 9
is only a presumptive digipeater and no evidence is available
the remaining stations can originate frames. Thus, the link
station 4 to station 7 is marked "source" and from station 7
station 2 is marked "digipeated."

Depending on the presence of congestion and hidden stations, it
happen that the reciprocal path in the direction from station 6
station 4 has quite different link characteristics; therefore,
link can be recognized as heard in each direction independently.
the above diagram the link between 2 and 7 has been heard in
directions and is marked "reciprocal". However, there is only
synchronized mark, which can be set in either direction. If
particular link is not marked either heard or synchronized,
presumption on its viability to carry traffic is highly
(the traffic is probably a beacon or "CQ"). If later
synchronized the presumption is strengthened and if later
heard in the reciprocal direction the presumption is confirmed

Experience shows that a successful routing algorithm for
packet-radio channel must have provisions for congestion avoidance
There are two straightforward ways to cope with this. The first is
static measure of node congestion based on the number of links in
network graph incident at each node. This number is computed by
wiretap routine and stored in the node table as it adds entries
the link table

The second, not yet implemented, is a dynamic measure of
congestion which tallies the number of link references during
most recent time interval (of specified length). The current
was suggested by the reachability mechanism used in the ARPANET
the Exterior Gateway Protocol [3]. An eight-bit shift register
each node is shifted in the direction from high-order to low-
bits, with zero-bits preceeding the high-order bit, at the rate
one shift every ten seconds. If during the preceeding ten-

Mills [Page 6]

RFC 981 March 1986
An Experimental Multiple-Path Routing

period a header with a path involving that node is found,
high-order bit of the register is set to one. When a path
calculated the number of one-bits in the register is totalled
used as a measure of dynamic node congestion. Thus, the time
specified is 80 seconds, which is believed appropriate for the AX.25
channel dynamics

5. Factor Computations and

The data items produced by the wiretap routine are processed
produce a set of factors that can be used by the routing routine
develop optimum routes. In order to insure a stable and
convergence as the routing algorithm constructs and
candidate paths leading to these routes, the factor
should have the following properties

1. All factors should be positive, monotone functions which
in value as system performance degrades from optimum

2. The criteria used to estimate link factors should be symmetric
that is, their values should not depend on the
direction the link is used

3. The criteria used to estimate node factors should not depend
the particular links that traffic enters or leaves the node

Each factor is associated with a weight assignment which reflects
contribution of the factor in the distance calculation, with
weights indicating greater importance. For comparison with
common routing algorithms, as well as for effective control of
computational resources required, it may be desirable to
additional restrictions on these computations, which may be a
for further study. Obviously, the success of this routing
depends on cleverly (i.e. experimentally) determined
computations and weight assignments

The particular choices used in the prototype implementation should
considered educated first guesses that might be changed, perhaps
dramatic ways, in later implementations. Nevertheless, the
of the algorithm in finding optimum routes over all choices in
computations and weights is unchanged. Recall that the
routine generates data items for each node and link heard and
them in the node and link tables. These items are processed by
routing routine to generate the factors shown below in Table 1
Table 2.

Mills [Page 7]

RFC 981 March 1986
An Experimental Multiple-Path Routing

Factor Weight Name How
---------------------------------------------------------------
f0 30 hop 1 for each
f1 50 unverified 1 if not heard either
f2 5 non-reciprocal 1 if not heard both
f3 5 unsynchronized 1 if no I or S frame

Table 1. Link

Factor Weight Name How
---------------------------------------------------------------
f4 5 complexity 1 for each incident
f5 20 digipeated 1 if station does not
f6 - congestion (see text

Table 2. Node

With regard to link factors, the "hop" factor is assigned as one
each link and represents the bias found in other routing
of this type. The intent is that the routing mechanism degenerate
minimum-hop in the absence of any other information.
"unverified" factor is assigned as one if the heard bit is not
(not heard in either direction), while the "non-reciprocal" factor
assigned as one if the reciprocal bit is not set (not heard in
directions). The "unsynchronized" factor is assigned as one if
synchronized bit is not set (no I or S frames observed in
direction).

With regard to node factors, the "complexity" factor is computed
the number of links incident at the node, while the "congestion
factor is to be computed as the number of intervals in the
ten-second intervals preceding the time of observation in which
frame was transmitted to or through the node. The "digipeated
factor is assigned as one if the node is only a source (i.e.
digipeated frames have been heard from it). For the purposes
path-distance calculations, the node factors are taken as zero
the endpoint nodes, since their contribution to any path would be
same

Mills [Page 8]

RFC 981 March 1986
An Experimental Multiple-Path Routing

6. The Routing

The dynamic data base built by the wiretap routine is used by
routing routine to compute routes as required. Ordinarily,
needs to be done only when the first frame to a new destination
sent and at intervals thereafter, with the intervals
modulated by retry count together with congestion thresholds, etc
The technique used is a variation of the Viterbi Algorithm [1],
is similar to the the shortest-path-first algorithm used in
ARPANET and elsewhere [2]. It operates by constructing a set
candidate paths on the network graph from the destination to
source in increasing number of hops. Construction continues until
the complete paths satisfying a specified condition are found
following which one with minimum distance is selected as the
route and the others ranked as alternate routes

There are a number of algorithms to determine the mimimum-
path on a graph between two nodes with given metric. The
implementation operates using a dynamic path list of entries
from the link table. Each list entry includes (a) the NID of
current node, (b) a pointer to the preceding node on the path and (c
the hop count and (d) distance from the node to the final
node of the path

[ NID, pointer, hop, distance ] .

The algorithm starts with the list containing only the entry [
dest-NID, 0, 0, 0 ], where dest-NID is the final destination NID,
then scans the list starting at this entry. For each such entry
scans the link table for all links with either to-NID or from-
matching NID and for each one found inserts a new entry

[ new-NID, new-pointer, hop + 1, distance + weight ] ,

where the new-NID is the to-NID of the link if its from-NID
the old NID and the from-NID of the link otherwise. The new-
is set at the address of the old entry and the weight is
from the factors and weights as described previously. The
coontinues to select succeeding entries and scan the link table
no further entries remain to be processed, the allocated list area
full or the maximum hop count or distance are exceeded, as
below

Note that in the Viterbi Algorithm, which operates in a
manner, when paths merge at a single node, all except one of
minimum-distance paths (called survivors) are abandonded. If
one of the minimum-distance paths is required, Wiretap does the same

Mills [Page 9]

RFC 981 March 1986
An Experimental Multiple-Path Routing

however, in the more general case where alternate paths are required
all non-looping paths are potential survivors. In order to prevent
size explosion in the list, as well as to suppress loops, new
entries with new-NID matching the NID of an existing entry on
path to the final destination NID are suppressed and paths with
counts exceeding (currently) eight or distances exceeding 255
abandoned

If the Wiretap station NID is found in the from-NID of an
inserted in the list, a complete path has been found. The
remembers the minimum distance and minimum hop count of the
paths found as it proceeds. When only one of the minimum-
paths (primary route) is required, then for any list entry where
distance exceeds the minimum distance or the hop count exceeds
maximum hop count (plus one), the path is abandoned and no
processing done for it. When alternate routes are required
hop-count test is used, but the minimum-distance test is not

The above pruning mechanisms are designed so that the the
always finds all complete paths with the minimum hop count and
minimum hop count (plus one), which are designated the
routes. The assignment of factor computations and weights is
to favor minimum-hop paths under most conditions, but to allow
path length to grow by no more than one additional hop
conditions of extreme congestion. Thus, the minimum-distance
(primary route) must be found among the alternate paths, usually,
not always, one of the minimum-hop paths

At the completion of processing the complete paths are ranked
by distance, then by the order of the final entry in the list,
is in hop-count order by construction, to establish a well-
ordering. The first of these paths represents the primary route
while the remaining represent alternatives should all lower-
routes fail

Some idea of the time and space complexity of the routing routine
be determined from the observation that the computations for
primary and secondary routes of the example in Appendix A with 58
nodes and 98 links requires a average of about 30 list entries,
occasionally overflows the maximum size, currently 100 entries.
step requires a scan of all the links and a search (for loops)
the maximum path length, which in principle can add most of the
to the list for each new hop. Obviously, the resources required
escalate dramatically, unless effective pruning techniques such
the above are used

The prototype implementation requires 316 milliseconds on

Mills [Page 10]

RFC 981 March 1986
An Experimental Multiple-Path Routing

LSI-11/73 to calculate the 58 primary routes to all 58 nodes for
average of about 5.4 milliseconds per route. The
requires 1416 milliseconds to calculate the 201 combined primary
alternate routes to all 58 nodes for an average of about 3.4
milliseconds per route

7. Data Base

In normal operation Wiretap tends to pick up a good deal of
and random junk, since it can happen that a station may call
other station using ad-hoc heuristics and often
strategies. The result is that Wiretap may add speculative
erroneous links to the data base. In practice, this
reasonably often as operators manually try various paths to
that may be shut down, busy or blocked by congestion. Nevertheless
since Wiretap operates entirely by passive monitoring,
links may represent the principal means for discovery of new paths

The number of nodes and links, speculative or not, can grow
limit as the Wiretap station continues to monitor the channel.
the size of the node table or link table approaches the maximum,
garbage-collection procedure is automatically invoked. The
used in the prototype implementation was suggested by virtual-
storage-management techniques in which the oldest unreferenced
is replaced when a new page frame is required. Every link
entry includes an age field, which is incremented once each minute
its value is less than 60, once each hour otherwise and reset to
when the link is found in a monitor header. When new space
required in the link table, the link with the largest product of
and distance, as determined by the factor computations and weights
is removed first

Every node table entry includes the congestion factor
above, which is a count of the number of links (plus one) incident
that node. As links are removed from the link table, these
are decremented. If the count for some node decrements to one,
node is removed. Thus, if new space is required in the node table
links are removed as described above until the required space
reclaimed

In addition to the above, and in order to avoid capture of the
by occasional speculative spasms on one hand and stagnation due
excessively stale information on the other, if the age
exceeds a predetermined threshold, currently fifteen minutes for
speculative link and 24 hours for other links, the link is

Mills [Page 11]

RFC 981 March 1986
An Experimental Multiple-Path Routing

from the data base regardless of distance. It is expected that
procedures will be improved as experience with the
matures

8. Summary and Directions for Further

Wiretap represents an initial experiment and evaluation of
effectiveness of passive monitoring in the management of the AX.25
packet-radio channel. While the results of initial experiments
been encouraging, considerable work needs to be done in
optimization effectively, some experience needs to be gained in
day-to-day operation of the prototype system during which
combinations of weight assignments can be tried

The prototype implementation has been in use for about four months
this writing; however, a number of lessons were quickly learned.
implementation includes a finite-state automaton to manage
connection requests, including the capability to retry SABM
along alternate routes computed by Wiretap. A simple but
heuristic is used to generate speculative paths by
adding links between the destination station and the Wiretap
together with all other stations in the node table identified
digipeaters. The algorithm then operates as described above
generate the primary and alternate routes. An example of
technique is given in the Appendix

This technique works very well, at least in the initial-
phase of virtual-circuit mode, although it requires
computational resources, due to the large number of possible
ranging from reasonable to outrageous. In the case of datagram
only the primary route is computed. The heuristic path-
strategy outlined above is a critical performance determinant in
area

While there is a mechanism for the TAPR-1 processor to notify
prototype implementation that a lower-level AX.25 virtual circuit
failed, so that an alternate path can be tried, there is no
mechanism to signal the failure of an upper-level TCP connection
which uses IP datagrams wrapped in AX.25 I frames (connection mode
or UI frames (connectionless mode). This is a generic problem
any end-system protocol where the peers are located
distant from the link-level entities. Experience indicates the
of providing a two-way conduit to share control information
protocol layers may be seriously underestimated

The prototype implementation manages processor and storage demands
relatively simple ways, which can result in

Mills [Page 12]

RFC 981 March 1986
An Experimental Multiple-Path Routing

inefficiencies. It is apparent that in any widely
version of Wiretap these demands will have to be carefully managed
As suggested above, effective provisions to purge old information
especially speculative links, are vital, as well as provisions
control the intervals between route computations, for instance as
function of link state and traffic mode

The next step in the evolution towards a fully distributed
algorithm is the introduction of active probing techniques.
should considerably improve the capability to discover new paths,
well as to fine-tune existing ones. It should be possible
implement an active probing mechanism while maintaining
with the passive-only Wiretap, as well as maintaining
with other stations using no routing algorithms at all. It does
that judicious use of beacons to discover and renew paths in
absence of traffic will be required, as well as some kind
echo/reply mechanism similar to the ICMP Echo/Reply support
of Internet hosts

In order to take advantage of the flexibility provided by
algorithms like Wiretap, it will be necessary to revise the AX.25
specification to include "loose" source routing in addition to
present "strict" source routing. Strict source routing
every forwarding stage (callsign) to be explicitly declared,
loose source routing would allow some or all stages to be left to
discretion of the local routing agent or digipeater. One
would be to devise a special collective indicator or callsign
could signal a Wiretap digipeater to insert the computed route
following its callsign in the AX.25 frame header

A particularly difficult area for any routing algorithm is in
detection and reponse to congestion. Some hints on how the
Wiretap mechanism can be improved are indicated in this document
Additional work, especially with respect to the hidden-
problem, is necessary. Perhaps the most useful feature of all
be a link-quality indication derived from the radio, modem
frame-level procedures (checksum failures). Conceivably,
information could be included in beacon messages
occasionally by the digipeaters

It is quite likely that the most effective application of
algorithms in general will be at the local-area digipeater sites
One reason for this is that these stations may have off-
trunking facilities that connect different areas and may
wide-area routing information via these facilities. The
information collected by the local-area Wiretap stations could
be exchanged directly with the wide-area sites

Mills [Page 13]

RFC 981 March 1986
An Experimental Multiple-Path Routing

9.

[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
routing algorithm for the ARPANET. Proc. ACM/IEEE Sixth
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-
protocol, Version 2.0. American Radio Relay League,
1984.

Mills [Page 14]

RFC 981 March 1986
An Experimental Multiple-Path Routing

Appendix A. An

An example will illustrate how Wiretap constructs primary
alternate routes given candidate node and link tables. The
tables resulted from a scenario monitoring normal traffic on
145.01-MHz AX.25 packet-radio channel in the Washington, DC,
during a typical 24-hour period. The node and link
illustrated below give an idea of what the constructed data
looks like, as well as provide the basis for the example

Figure 1 illustrates a candidate node table showing the node
(NID), callsign and related information for each station. The
field contains the primary route (minimum-distance path), as a
of NIDs from the origination station (NID = 0) to the
station shown, with the exception of the endpoint NIDs. The
of a route string indicates the station is directly reachable
the assistance of a digipeater. Note that the originating station
always the first entry in the node table, in this case W3HCF, and
initialized with defaults before the algorithm is started

NID Callsign Flags Links Last Rec Wgt
-------------------------------------------------------
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

Mills [Page 15]

RFC 981 March 1986
An Experimental Multiple-Path Routing

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

In the above table the Dist field shows the total distance of
primary route, the Links field shows the complexity factor, which
the number of links incident at that node (plus one), and the
Rec field shows the time (UT) the station was last heard, directly
indirectly. The Flags field shows, among other things, which

Mills [Page 16]

RFC 981 March 1986
An Experimental Multiple-Path Routing

have originated frames and which have digipeated them. The bits
this field, which is in octal format, are interpeted as follows (
0 is the rightmost bit):

Bit Function
--------------------
0 originating station
1 digipeater station
2 station heard (Last Rec column
3 station synchronized

Among the 58 stations shown in Figure 1 are eleven digipeaters,
but three of which also originate traffic. All but twelve
have either originated or digipeated a synchronized connection
only one "station" DPTRID, actually a beacon, has not been heard
either originate or digipeat traffic

Figure 2 illustrates a candidate node table of 98 links showing
from-NID, to-NID, Flags and Age information for each link
collected. The bits in the Flags field, which is in octal format,
interpeted as follows (bit 0 is the rightmost bit):

Bit Function
-------------------
0 source
1 digipeated
2 heard
3
4 reciprocal

From To Flags Age From To Flags
--------------------------- ---------------------------
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

Mills [Page 17]

RFC 981 March 1986
An Experimental Multiple-Path Routing

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 14

Figure 2. Candidate Link

The following tables illustrate the operation of the
algorithm in several typical scenarios. Each line in the
represents the step where an entry is extracted from the path
and new entries are determined. The "Step" column indexes each step
while the "To" column indicates the NID of the station at that step
The "Ptr" column is the index of the preceeding step along the
to the destination, while the "Hop" and "Dist" columns represent
total hop count and computed distance along that path

Mills [Page 18]

RFC 981 March 1986
An Experimental Multiple-Path Routing

Following is a fairly typical example where the destination
is not directly reachable, but several multiple-hop paths exist
various digipeaters. The algorithm finds four digipeaters: 1, 5, 11
and 39, all but the last of which are directly reachable from
originating station, to generate two routes of two hops and two
three hops, as shown below. Note that only the steps leading
complete paths are shown

Destination: 29 Station: W3
Step NID Ptr Hop Dist
-------------------------------------------------------------
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 29

The algorithm ranks these routes first by distance and then by
in the list, so that the two-hop route at N = 35 would be
first, followed by the three-hop route at N = 63, the two-hop
at N = 4 and, finally the three-hop route at N = 46. The reason
the second choice is a three-hop route and the third a two-hop
is because of the extreme congestion at the digipeater station 5,
which has 34 incident links

Following is an example showing how the path-pruning
operate to limit the scope of exploration to those paths most
to lead to useful routes. The algorithm finds one two-hop route
four three-hop routes. In this example the complete list is shown
including all the steps which are abandond for the reasons given

Mills [Page 19]

RFC 981 March 1986
An Experimental Multiple-Path Routing

Destination: 13 Station: WB2
Step NID Ptr Hop Dist
-------------------------------------------------------------
0 13 0 0 0
1 7 0 1 30
2 43 0 1 35 No
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
9 60 1 2 130 No

10 5 1 2 140 Max distance 310
11 1 1 2 130
12 41 1 2 130 No
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 300

The steps labelled "No path" are abandonded because no links could
found satisfying the constraints: (a) to-NID or from-NID
the NID of the step, (b) loop-free or (c) total path distance

Mills [Page 20]

RFC 981 March 1986
An Experimental Multiple-Path Routing

than 256. The steps labelled "Max distance" are abandonded
the total distance, computed as the sum of the Dist value plus
weighted node factors, would exceed 256 as shown. The steps
"Max hops" are abandonded because the total hop count would
the minimum hop count (plus one) as shown

Although this example shows the computations for all
routes, if only the primary route is required all steps with
distance greater than the minimum-distance (135) can be abandonded
In this particular case path exploration terminates after only 14
steps

The following example shows a typical scenario involving a
unknown station; that is, one not already in the data base.
not strictly part of the algorithm itself, the strategy in
present system is to generate speculative paths consisting of
imputed direct link between the originating station and
destination station, together with imputed direct links between
digipeater in the data base and the destination station. The
links created will time out according to the cache-
mechanism in about fifteen minutes

In the following example the destination station is 74, which
in the following additions to the link table

fm-NID To-NID Flags Node
----------------------------------
0 74 000
1 74 000
5 74 000
7 74 000
8 74 000
11 74 000
13 74 000
15 74 000
16 74 000
23 74 000
39 74 000
44 74 000

There are eleven digipeaters involved, not all of which may be used
The resulting primary route and five alternate routes are
below. Note that only five of the eleven digipeaters are used.
remainder were either too far away or too heavily congested.
that only the list entries leading to complete paths are shown

Mills [Page 21]

RFC 981 March 1986
An Experimental Multiple-Path Routing

Destination: 74 Station:
Step NID Ptr Hop Dist
-------------------------------------------------------------
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 74

Mills [Page 22]

if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.

RFC documents can be found at I.E.T.F.

Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX