rfc981.txt

RFC 相关的技术文档

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