Experimental multiple-path routing algorithm
RFC 981

Document Type RFC - Unknown (March 1986; No errata)
Last updated 2013-03-02
Stream Legacy
Formats plain text pdf html bibtex
Stream Legacy state (None)
Consensus Boilerplate Unknown
RFC Editor Note (None)
IESG IESG state RFC 981 (Unknown)
Telechat date
Responsible AD (None)
Send notices to (None)
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
Show full document text