RFC 981 (rfc981) - Page 2 of 22


Experimental multiple-path routing algorithm



Alternative Format: Original Text Document





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