RFC 981 (rfc981) - Page 1 of 22

Experimental multiple-path routing algorithm

Alternative Format: Original Text Document
Next >
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
Next >