Network Working Group D. L. Mills
Request for Comments: 981 M/A-COM Linkabit
March 1986
An Experimental Multiple-Path Routing Algorithm
Status of This Memo
This RFC describes an experimental, multiple-path routing algorithm
designed for a packet-radio broadcast channel and discusses the
design and testing of a prototype implementation. It is presented as
an example of a class of routing algorithms and data-base management
techniques that may find wider application in the Internet community.
Of particular interest may be the mechanisms to compute, select and
rank a potentially large number of speculative routes with respect to
the limited cumputational resources available. Discussion and
suggestions for improvements are welcomed. Distribution of this memo
is unlimited.
Abstract
This document introduces wiretap algorithms, which are a class of
routing algorithms that compute quasi-optimum routes for stations
sharing a broadcast channel, but with some stations hidden from
others. The wiretapper observes the paths (source routes) used by
other stations sending traffic on the channel and, using a heuristic
set of factors and weights, constructs speculative paths for its own
traffic. A prototype algorithm, called here the Wiretap Algorithm,
has been designed for the AX.25 packet-radio channel. Its design is
similar in many respects to the shortest-path-first (spf) algorithm
used in the ARPANET and elsewhere, and is in fact a variation in the
class of algorithms, including the Viterbi Algorithm, that construct
optimum paths on a graph according to a distance computed as a
weighted sum of factors assigned to the nodes and edges.
The Wiretap Algorithm differs from conventional algorithms in that it
computes not only the primary route (a minimum-distance path), but
also additional paths ordered by distance, which serve as alternate
routes should the primary route fail. This feature is also useful
for the discovery of new paths not previously observed on the
channel.
Since the amateur AX.25 packet-radio channel is very active in the
Washington, DC, area and carries a good deal of traffic under
punishing conditions, it was considered a sufficiently heroic
environment for a convincing demonstration of the prototype
algorithm. It was implemented as part of an IP/TCP driver for the
LSI-11 processor running the "fuzzball" operating system. The driver
is connected via serial line to a 6809-based TAPR-1 processor running
the WA8DED firmware, which controls the radio equipmnet in both
Mills [Page 1]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
virtual-circuit and datagram modes. The prototype implementation
provides primary and alternate routes, can route around congested
areas and can change routes during a connection. This document
describes the design, implementation and initial testing of the
algorithm.
1. Introduction
This document describes the design, implementation and initial
testing of the Wiretap Algorithm, a dynamic routing algorithm for the
AX.25 packet-radio channel [4]. The AX.25 channel operates in CSMA
contention mode at VHF frequencies using AFSK/FM modulation at 1200
bps. The AX.25 protocol itself is similar to X.25 link-layer protocol
LAPB, but with an extended frame header consisting of a string of
radio callsigns representing a path, usually selected by the
operator, between two end stations, possibly via one or more
intermediate packet repeaters or digipeaters. Most stations can
operate simultaneously as intermediate systems digipeaters) and as
end systems with respect to the ISO model.
Wiretap uses passive monitoring of frames transmitted on the channel
in order to build a dynamic data base which can be used to determine
optimum routes. The algorithm operates in real time and generates a
set of paths ordered by increasing total distance, as determined by a
shortest-path-first procedure similar to that used now in the ARPANET
and planned for use in the new Internet gateway system [2]. The
implementation provides optimum routes (with respect to the factors
and weights selected) at initial-connection time for virtual
circuits, as well as for each datagram transmission. This document
is an initial status report and overview of the prototype
implementation for the LSI-11 processor running the "fuzzball"
operating system.
The principal advantage in the use of routing algorithms like Wiretap
is that digipeater paths can be avoided when direct paths are
available, with digipeaters used only when necessary and also to
discover hidden stations. In the present exploratory stage of
evolution, the scope of Wiretap has been intentionally restricted to
passive monitoring. In a later stage the scope may be extended to
include the use of active probes to discover hidden stations and the
use of clustering techniques to manage the distribution of large
quantities of routing information.
The AX.25 channel interface is the 6809-based TAPR-1 processor
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 option
a monitor report for each received frame of a selected type,
Mills [Page 2]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
including U, I and S frames. Wiretap processes each of these to
extract routing information and (optionally) saves them in the system
log file. Following is a typical report:
fm KS3Q to W4CQI via WB4JFI-5* WB4APR-6 ctl I11 pid F0
The originating station is KS3Q and the destination is W4CQI. The
frame has been digipeated first by WB4JFI-5 and then WB4APR-6, is an
I frame (sequence numbers follow the I indicator) and has protocol
identifier F0 (hex). The asterisk "*" indicates the report was
received from that station. If no asterisk appears, the report was
received from the originator.
2. Design Principles
A path is a concatenation of directed links originating at one
station, extending through one or more digipeaters and terminating at
another station. Each link is characterized by a set of factors such
as cost, delay or throughput that can be computed or estimated.
Wiretap computes several intrinsic factors for each link and updates
the routing data base, consisting of node and link tables. The
weighted sum of these factors for each link is the distance of that
link, while the sum of the distances for each link in the path is the
distance of that path.
It is the intent of the Wiretap design that the distance of a link
reflect the a-priori probability that a packet will successfully
negotiate that link relative to the other choices possible at the
sending node. Thus, the probability of a non-looping path is the
product of the probabilities of its links. Following the technique
of Viterbi [1], it is convenient to represent distance as a
logarithmic transformation of probability, which then becomes a
metric. However, in the following the underlying probabilities are
not considered directly, since the distances are estimated on a
heuristic basis.
Wiretap incorporates an algorithm which constructs a set of paths,
ordered by distance, between given end stations according to the
factors and weights contained in the routing data base. Such paths
can be considered optimum routes between these stations with respect
to the given assignment of factors and weights. In the prototype
implementation one of the end stations must be the Wiretap station
itself; however, in principle, the Wiretap station can generate
routes for other stations subject to the applicability of the
information in its data base.
Note that Wiretap in effect constructs minimum-distance paths in the
Mills [Page 3]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
direction from the destination station to the Wiretap station and,
based on that information, then 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 then computes its own optimum reciprocal routes
(i.e. the optimum direct routes from the Wiretap station). However,
the routing data bases at the two stations may diverge due to
congestion or hidden stations, so that the computed routes may not
coincide.
In principle, Wiretap-computed routes can be fine-tuned using
information provided not only by its directly communicating stations
but others that may hear them as well. The most interesting scenario
would be for all stations to exchange Wiretap information using a
suitable distributed protocol, but this is at the moment beyond the
scope of the prototype implementation. Nevertheless, suboptimum but
useful paths can be obtained in the traditional and simple way with
one station using a Wiretap-computed route and the other its
reciprocal, as determined from the received frame header. Thus,
Wiretap is compatible with existing channel procedures and protocols.
3. Implementation Overview
The prototype Wiretap implementation for the LSI-11 includes two
routines, the wiretap routine, which extracts information from
received monitor headers and builds the routing data base, and the
routing routine, which calculates paths using the information in the
data base. The data base consists of three tables, the channel table,
node table and link table. The channel table includes an entry for
each channel (virtual circuit) supported by the TAPR-1 processor
running the WA8DED firmware, five in the present configuration. The
structure and use of this table are only incidental to the algorithm
and will not be discussed further.
The node table includes an entry for each distinct callsign (which
may be a collective or beacon identifier) heard on the channel,
together with node-related routing information, the latest computed
route and other miscellaneous information. The table is indexed by
node ID (NID), which is used in the computed route and in other
tables instead of the awkward callsign string. The link table
contains an entry for each distinct (unordered) node pair observed in
a monitor header. Each entry includes the from-NID and to-NID of the
first instance found, together with link-related routing information
and other miscellaneous information. Both tables are dynamically
managed using a cache algorithm based on a weighted
least-recently-used replacement mechanism described later.
Mills [Page 4]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
The example discussed in Appendix A includes candidate node and link
tables for illustration. These tables were constructed in real time
by the prototype implementation from off-the-air monitor headers
collected over a typical 24-hour period. Each node table entry
requires 26 bytes and each link table entry four bytes. The maximum
size of the node table is presently 75 entries, while that of the
link table is 150 entries. Once the cache algorithm has stabilized
for a day or two, it is normal to have about 60 entries in the node
table and 100 entries in the link table.
The node table and link table together contain all the information
necessary to construct a network graph, as well as calculate paths on
that graph between any two end stations, not just those involving the
Wiretap station. Note, however, that the Wiretap station does not in
general hear all other stations on the channel, so may choose
suboptimum routes. However, in the Washington, DC, area most
stations use one of several digipeaters, which are in general heard
reliably by other stations in the area. Thus, 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 is called to process each monitor header. It
extracts each callsign from the header in turn and searches the node
table for corresponding NID, making a new entry and NID if not
already there. The result is a string of NIDs, starting at the
originating station, extending through a maximum of eight digipeaters
and ending at the destination station. For each pair of NIDs along
this string the link table is searched for either the direct link, as
indicated in the string, or its reciprocal; that is, the direction
towards the originator.
The operations that occur at this point can be illustrated by the
following diagram, which represents a monitor header with apparent
path from station 4 to station 6 via digipeaters 7, 2 and 9 in
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 dest
|
|
V
(0)
wiretap
Mills [Page 5]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
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" in
that direction. However, the viability of the path from station 2 to
station 6 can only be presumed, unless additional evidence is
available. If in fact the header is from an AX.25 I or S frame (but
not a U frame), an AX.25 virtual circuit has apparently been
previously established between the end stations and the presumption
is strengthened. In this 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 to digipeat, but station 9
is only a presumptive digipeater and no evidence is available that
the remaining stations can originate frames. Thus, the link from
station 4 to station 7 is marked "source" and from station 7 to
station 2 is marked "digipeated."
Depending on the presence of congestion and hidden stations, it may
happen that the reciprocal path in the direction from station 6 to
station 4 has quite different link characteristics; therefore, a
link can be recognized as heard in each direction independently. In
the above diagram the link between 2 and 7 has been heard in both
directions and is marked "reciprocal". However, there is only one
synchronized mark, which can be set in either direction. If a
particular link is not marked either heard or synchronized, any
presumption on its viability to carry traffic is highly speculative
(the traffic is probably a beacon or "CQ"). If later marked
synchronized the presumption is strengthened and if later marked
heard in the reciprocal direction the presumption is confirmed.
Experience shows that a successful routing algorithm for any
packet-radio channel must have provisions for congestion avoidance.
There are two straightforward ways to cope with this. The first is a
static measure of node congestion based on the number of links in the
network graph incident at each node. This number is computed by the
wiretap routine and stored in the node table as it adds entries to
the link table.
The second, not yet implemented, is a dynamic measure of node
congestion which tallies the number of link references during the
most recent time interval (of specified length). The current plan
was suggested by the reachability mechanism used in the ARPANET and
the Exterior Gateway Protocol [3]. An eight-bit shift register for
each node is shifted in the direction from high-order to low-order
bits, with zero-bits preceeding the high-order bit, at the rate of
one shift every ten seconds. If during the preceeding ten-second
Mills [Page 6]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
period a header with a path involving that node is found, the
high-order bit of the register is set to one. When a path is
calculated the number of one-bits in the register is totalled and
used as a measure of dynamic node congestion. Thus, the time interval
specified 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 are processed to
produce a set of factors that can be used by the routing routine to
develop optimum routes. In order to insure a stable and reliable
convergence as the routing algorithm constructs and discards
candidate paths leading to these routes, the factor computations
should have the following properties:
1. All factors should be positive, monotone functions which increase
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 particular
direction the link is used.
3. The criteria used to estimate node factors should not depend on
the particular links that traffic enters or leaves the node.
Each factor is associated with a weight assignment which reflects the
contribution of the factor in the distance calculation, with larger
weights indicating greater importance. For comparison with other
common routing algorithms, as well as for effective control of the
computational resources required, it may be desirable to impose
additional restrictions on these computations, which may 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 used in the prototype implementation should be
considered educated first guesses that might be changed, perhaps in
dramatic ways, in later implementations. Nevertheless, the operation
of the algorithm in finding optimum routes over all choices in factor
computations and weights is unchanged. Recall that the wiretap
routine generates data items for each node and link heard and saves
them in the node and link tables. These items are processed by the
routing routine to generate the factors shown below in Table 1 and
Table 2.
Mills [Page 7]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
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 Factors
With regard to link factors, the "hop" factor is assigned as one for
each link and represents the bias found in other routing algorithms
of this type. The intent is that the routing mechanism degenerate to
minimum-hop in the absence of any other information. The
"unverified" factor is assigned as one if the heard bit is not set
(not heard in either direction), while the "non-reciprocal" factor is
assigned as one if the reciprocal bit is not set (not heard in both
directions). The "unsynchronized" factor is assigned as one if the
synchronized bit is not set (no I or S frames observed in either
direction).
With regard to node factors, the "complexity" factor is computed as
the number of links incident at the node, while the "congestion"
factor is to be computed as the number of intervals in 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.
Mills [Page 8]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
6. The Routing Routine
The dynamic data base built by the wiretap routine is used by the
routing routine to compute routes as required. Ordinarily, this
needs to be done only when the first frame to a new destination is
sent and at intervals thereafter, with the intervals perhaps
modulated by retry count together with congestion thresholds, etc.
The technique used is a variation of the Viterbi Algorithm [1], which
is similar to the the shortest-path-first algorithm used in the
ARPANET and elsewhere [2]. It operates by constructing a set of
candidate paths on the network graph from the destination to the
source in increasing number of hops. Construction continues until all
the complete paths satisfying a specified condition are found,
following which one with minimum distance is selected as the primary
route and the others ranked as alternate routes.
There are a number of algorithms to determine the mimimum-distance
path on a graph between two nodes with given metric. The prototype
implementation operates using a dynamic path list of entries derived
from the link table. Each list entry includes (a) the NID of the
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 destination
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, and
then scans the list starting at this entry. For each such entry it
scans the link table for all links with either to-NID or from-NID
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 matches
the old NID and the from-NID of the link otherwise. The new-pointer
is set at the address of the old entry and the weight is computed
from the factors and weights as described previously. The algorithm
coontinues to select succeeding entries and scan the link table until
no further entries remain to be processed, the allocated list area is
full or the maximum hop count or distance are exceeded, as explained
below.
Note that in the Viterbi Algorithm, which operates in a similar
manner, when paths merge at a single node, all except one of the
minimum-distance paths (called survivors) are abandonded. If only
one of the minimum-distance paths is required, Wiretap does the same;
Mills [Page 9]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
however, in the more general case where alternate paths are required,
all non-looping paths are potential survivors. In order to prevent a
size explosion in the list, as well as to suppress loops, new list
entries with new-NID matching the NID of an existing entry on the
path to the final destination NID are suppressed and paths with hop
counts exceeding (currently) eight or distances exceeding 255 are
abandoned.
If the Wiretap station NID is found in the from-NID of an entry
inserted in the list, a complete path has been found. The algorithm
remembers the minimum distance and minimum hop count of the complete
paths found as it proceeds. When only one of the minimum-distance
paths (primary route) is required, then for any list entry where the
distance exceeds the minimum distance or the hop count exceeds the
maximum hop count (plus one), the path is abandoned and no further
processing done for it. When alternate routes are required the
hop-count test is used, but the minimum-distance test is not.
The above pruning mechanisms are designed so that the the algorithm
always finds all complete paths with the minimum hop count and the
minimum hop count (plus one), which are designated the alternate
routes. The assignment of factor computations and weights is intended
to favor minimum-hop paths under most conditions, but to allow the
path length to grow by no more than one additional hop under
conditions of extreme congestion. Thus, the minimum-distance path
(primary route) must be found among the alternate paths, usually, but
not always, one of the minimum-hop paths.
At the completion of processing the complete paths are ranked first
by distance, then by the order of the final entry in the list, which
is in hop-count order by construction, to establish a well-defined
ordering. The first of these paths represents the primary route,
while the remaining represent alternatives should all lower-ranked
routes fail.
Some idea of the time and space complexity of the routing routine can
be determined from the observation that the computations for all
primary and secondary routes of the example in Appendix A with 58
nodes and 98 links requires a average of about 30 list entries, but
occasionally overflows the maximum size, currently 100 entries. Each
step requires a scan of all the links and a search (for loops) along
the maximum path length, which in principle can add most of the links
to the list for each new hop. Obviously, the resources required can
escalate dramatically, unless effective pruning techniques such as
the above are used.
The prototype implementation requires 316 milliseconds on an
Mills [Page 10]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
LSI-11/73 to calculate the 58 primary routes to all 58 nodes for an
average of about 5.4 milliseconds per route. The implementation
requires 1416 milliseconds to calculate the 201 combined primary and
alternate routes to all 58 nodes for an average of about 3.4
milliseconds per route.
7. Data Base Housekeeping
In normal operation Wiretap tends to pick up a good deal of errors
and random junk, since it can happen that a station may call any
other station using ad-hoc heuristics and often counterproductive
strategies. The result is that Wiretap may add speculative and
erroneous links to the data base. In practice, this happens
reasonably often as operators manually try various paths to stations
that may be shut down, busy or blocked by congestion. Nevertheless,
since Wiretap operates entirely by passive monitoring, speculative
links may represent the principal means for discovery of new paths.
The number of nodes and links, speculative or not, can grow without
limit as the Wiretap station continues to monitor the channel. As
the size of the node table or link table approaches the maximum, a
garbage-collection procedure is automatically invoked. The procedure
used in the prototype implementation was suggested by virtual-memory
storage-management techniques in which the oldest unreferenced page
is replaced when a new page frame is required. Every link table
entry includes an age field, which is incremented once each minute if
its value is less than 60, once each hour otherwise and reset to zero
when the link is found in a monitor header. When new space is
required in the link table, the link with the largest product of age
and distance, as determined by the factor computations and weights,
is removed first.
Every node table entry includes the congestion factor mentioned
above, which is a count of the number of links (plus one) incident at
that node. As links are removed from the link table, these counts
are decremented. If the count for some node decrements to one, that
node is removed. Thus, if new space is required in the node table,
links are removed as described above until the required space is
reclaimed.
In addition to the above, and in order to avoid capture of the tables
by occasional speculative spasms on one hand and stagnation due to
excessively stale information on the other, if the age counter
exceeds a predetermined threshold, currently fifteen minutes for a
speculative link and 24 hours for other links, the link is removed
Mills [Page 11]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
from the data base regardless of distance. It is expected that these
procedures will be improved as experience with the implementation
matures.
8. Summary and Directions for Further Development
Wiretap represents an initial experiment and evaluation of the
effectiveness of passive monitoring in the management of the AX.25
packet-radio channel. While the results of initial experiments have
been encouraging, considerable work needs to be done in the
optimization effectively, some experience needs to be gained in the
day-to-day operation of the prototype system during which various
combinations of weight assignments can be tried.
The prototype implementation has been in use for about four months at
this writing; however, a number of lessons were quickly learned. The
implementation includes a finite-state automaton to manage initial
connection requests, including the capability to retry SABM frames
along alternate routes computed by Wiretap. A simple but effective
heuristic is used to generate speculative paths by artificially
adding links between the destination station and the Wiretap station
together with all other stations in the node table identified as
digipeaters. The algorithm then operates as described above to
generate the primary and alternate routes. An example of this
technique is given in the Appendix.
This technique works very well, at least in the initial-connection
phase of virtual-circuit mode, although it requires significant
computational resources, due to the large number of possible paths
ranging from reasonable to outrageous. In the case of datagram mode
only the primary route is computed. The heuristic path-abandonment
strategy outlined above is a critical performance determinant in this
area.
While there is a mechanism for the TAPR-1 processor to notify the
prototype implementation that a lower-level AX.25 virtual circuit has
failed, so that an alternate path can be tried, there is no intrinsic
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 with
any end-system protocol where the peers are located physically
distant from the link-level entities. Experience indicates the value
of providing a two-way conduit to share control information between
protocol layers may be seriously underestimated.
The prototype implementation manages processor and storage demands in
relatively simple ways, which can result in considerable
Mills [Page 12]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
inefficiencies. It is apparent that in any widely distributed
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 to
control the intervals between route computations, for instance as a
function of link state and traffic mode.
The next step in the evolution towards a fully distributed routing
algorithm is the introduction of active probing techniques. This
should considerably improve the capability to discover new paths, as
well as to fine-tune existing ones. It should be possible to
implement an active probing mechanism while maintaining compatibility
with the passive-only Wiretap, as well as maintaining compatibilty
with other stations using no routing algorithms at all. It does seem
that judicious use of beacons to discover and renew paths in the
absence of traffic will be required, as well as some kind of
echo/reply mechanism similar to the ICMP Echo/Reply support required
of Internet hosts.
In order to take advantage of the flexibility provided by routing
algorithms like Wiretap, it will be necessary to revise the AX.25
specification to include "loose" source routing in addition to the
present "strict" source routing. Strict source routing requires
every forwarding stage (callsign) to be explicitly declared, while
loose source routing would allow some or all stages to be left to the
discretion of the local routing agent or digipeater. One suggestion
would be 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.
A particularly difficult area for any routing algorithm is in its
detection and reponse to congestion. Some hints on how the existing
Wiretap mechanism can be improved are indicated in this document.
Additional work, especially with respect to the hidden-station
problem, is necessary. 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 broadcast
occasionally by the digipeaters.
It is quite likely that the most effective application of routing
algorithms in general will be at the local-area digipeater sites.
One reason for this is that these stations may have off-channel
trunking facilities that connect different areas and may exchange
wide-area routing information via these facilities. The routing
information collected by the local-area Wiretap stations could then
be exchanged directly with the wide-area sites.
Mills [Page 13]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
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.
Mills [Page 14]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
Appendix A. An Example
An example will illustrate how Wiretap constructs primary and
alternate routes given candidate node and link tables. The candidate
tables resulted from a scenario monitoring normal traffic 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
illustrated below give an idea of what the constructed data base
looks like, as well as provide the basis for the example.
Figure 1 illustrates a candidate node table showing the node ID
(NID), callsign and related information for each station. The Route
field contains the primary route (minimum-distance path), as a string
of NIDs from the origination station (NID = 0) to the destination
station shown, with the exception of the endpoint NIDs. The absence
of a route string indicates the station is directly reachable without
the assistance of a digipeater. Note that the originating station is
always the first entry in the node table, in this case W3HCF, and is
initialized with defaults before the algorithm is started.
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
Mills [Page 15]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
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 Table
In the above table 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
Mills [Page 16]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
have originated frames and which have digipeated them. The bits in
this field, which is in octal format, are interpeted 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 connection
Among the 58 stations shown in Figure 1 are eleven digipeaters, all
but three of which also originate traffic. All but twelve stations
have either originated or digipeated a synchronized connection and
only one "station" DPTRID, actually a beacon, has not been heard to
either originate or digipeat traffic.
Figure 2 illustrates a candidate node table of 98 links showing the
from-NID, to-NID, Flags and Age information for each link as
collected. The bits in the Flags field, which is in octal format, are
interpeted as follows (bit 0 is the rightmost bit):
Bit Function
-------------------
0 source
1 digipeated
2 heard
3 synchronized
4 reciprocal
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
Mills [Page 17]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
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 Table
The following tables illustrate the operation of the routing
algorithm in several typical scenarios. Each line in the table
represents the step where an entry is extracted from the path list
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 path
to the destination, while the "Hop" and "Dist" columns represent the
total hop count and computed distance along that path.
Mills [Page 18]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
Following is a fairly typical example where the destination station
is not directly reachable, but several multiple-hop paths exist via
various digipeaters. The algorithm finds four digipeaters: 1, 5, 11
and 39, all but the last of which are directly reachable from the
originating station, to generate two routes of two hops and two of
three hops, as shown below. Note that only the steps leading 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 29
The algorithm ranks these routes first by distance and then by order
in the list, so that the two-hop route at N = 35 would be chosen
first, followed by the three-hop route at N = 63, the two-hop route
at N = 4 and, finally the three-hop route at N = 46. The reason why
the second choice is a three-hop route and the third a two-hop route
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 mechanisms
operate to limit the scope of exploration to those paths most likely
to lead to useful routes. The algorithm finds one two-hop route and
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 Algorithm
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 300
The steps labelled "No path" are abandonded because no links could be
found satisfying the constraints: (a) to-NID or from-NID matching
the NID of the step, (b) loop-free or (c) total path distance less
Mills [Page 20]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
than 256. The steps labelled "Max distance" are abandonded because
the total distance, computed as the sum of the Dist value plus the
weighted node factors, would exceed 256 as shown. The steps labelled
"Max hops" are abandonded because the total hop count would exceed
the minimum hop count (plus one) as shown.
Although this example shows the computations for all alternate
routes, if only the primary route is required all steps with total
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 previously
unknown station; that is, one not already in the data base. Although
not strictly part of the algorithm itself, the strategy in the
present system is to generate speculative paths consisting of an
imputed direct link between the originating station and the
destination station, together with imputed direct links between each
digipeater in the data base and the destination station. The new
links created will time out according to the cache-management
mechanism in about fifteen minutes.
In the following example the destination station is 74, which results
in the following additions 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 Digipeater
There are eleven digipeaters involved, not all of which may be used.
The resulting primary route and five alternate routes are shown
below. Note that only five of the eleven digipeaters are used. The
remainder were either too far away or too heavily congested. Note
that only the list entries leading to complete paths are shown.
Mills [Page 21]
RFC 981 March 1986
An Experimental Multiple-Path Routing Algorithm
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 74
Mills [Page 22]
|
