RFC 981 (rfc981) - Page 1 of 22
Experimental multiple-path routing algorithm
Alternative Format: Original Text Document
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