rfc981.txt

RFC 相关的技术文档

RFC 981                                                       March 1986
An Experimental Multiple-Path Routing Algorithm


   from the data base regardless of distance.  It is expected that these
   procedures will be improved as experience with the implementation
   matures.

8.  Summary and Directions for Further Development

   Wiretap represents an initial experiment and evaluation of the
   effectiveness of passive monitoring in the management of the AX.25
   packet-radio channel.  While the results of initial experiments have
   been encouraging, considerable work needs to be done in the
   optimization effectively, some experience needs to be gained in the
   day-to-day operation of the prototype system during which various
   combinations of weight assignments can be tried.

   The prototype implementation has been in use for about four months at
   this writing;  however, a number of lessons were quickly learned. The
   implementation includes a finite-state automaton to manage initial
   connection requests, including the capability to retry SABM frames
   along alternate routes computed by Wiretap.  A simple but effective
   heuristic is used to generate speculative paths by artificially
   adding links between the destination station and the Wiretap station
   together with all other stations in the node table identified as
   digipeaters.  The algorithm then operates as described above to
   generate the primary and alternate routes.  An example of this
   technique is given in the Appendix.

   This technique works very well, at least in the initial-connection
   phase of virtual-circuit mode, although it requires significant
   computational resources, due to the large number of possible paths
   ranging from reasonable to outrageous.  In the case of datagram mode
   only the primary route is computed.  The heuristic path-abandonment
   strategy outlined above is a critical performance determinant in this
   area.

   While there is a mechanism for the TAPR-1 processor to notify the
   prototype implementation that a lower-level AX.25 virtual circuit has
   failed, so that an alternate path can be tried, there is no intrinsic
   mechanism to signal the failure of an upper-level TCP connection,
   which uses IP datagrams wrapped in AX.25 I frames (connection mode)
   or UI frames (connectionless mode).  This is a generic problem with
   any end-system protocol where the peers are located physically
   distant from the link-level entities.  Experience indicates the value
   of providing a two-way conduit to share control information between
   protocol layers may be seriously underestimated.

   The prototype implementation manages processor and storage demands in
   relatively simple ways, which can result in considerable


Mills                                                          [Page 12]



RFC 981                                                       March 1986
An Experimental Multiple-Path Routing Algorithm


   inefficiencies.  It is apparent that in any widely distributed
   version of Wiretap these demands will have to be carefully managed.
   As suggested above, effective provisions to purge old information,
   especially speculative links, are vital, as well as provisions to
   control the intervals between route computations, for instance as a
   function of link state and traffic mode.

   The next step in the evolution towards a fully distributed routing
   algorithm is the introduction of active probing techniques.  This
   should considerably improve the capability to discover new paths, as
   well as to fine-tune existing ones.  It should be possible to
   implement an active probing mechanism while maintaining compatibility
   with the passive-only Wiretap, as well as maintaining compatibilty
   with other stations using no routing algorithms at all.  It does seem
   that judicious use of beacons to discover and renew paths in the
   absence of traffic will be required, as well as some kind of
   echo/reply mechanism similar to the ICMP Echo/Reply support required
   of Internet hosts.

   In order to take advantage of the flexibility provided by routing
   algorithms like Wiretap, it will be necessary to revise the AX.25
   specification to include "loose" source routing in addition to the
   present "strict" source routing.  Strict source routing requires
   every forwarding stage (callsign) to be explicitly declared, while
   loose source routing would allow some or all stages to be left to the
   discretion of the local routing agent or digipeater.  One suggestion
   would be to devise a special collective indicator or callsign that
   could signal a Wiretap digipeater to insert the computed route string
   following its callsign in the AX.25 frame header.

   A particularly difficult area for any routing algorithm is in its
   detection and reponse to congestion.  Some hints on how the existing
   Wiretap mechanism can be improved are indicated in this document.
   Additional work, especially with respect to the hidden-station
   problem, is necessary.  Perhaps the most useful feature of all would
   be a link-quality indication derived from the radio, modem or
   frame-level procedures (checksum failures).  Conceivably, this
   information could be included in beacon messages broadcast
   occasionally by the digipeaters.

   It is quite likely that the most effective application of routing
   algorithms in general will be at the local-area digipeater sites.
   One reason for this is that these stations may have off-channel
   trunking facilities that connect different areas and may exchange
   wide-area routing information via these facilities.  The routing
   information collected by the local-area Wiretap stations could then
   be exchanged directly with the wide-area sites.


Mills                                                          [Page 13]



RFC 981                                                       March 1986
An Experimental Multiple-Path Routing Algorithm


9.  References

   [1]  Forney, G.D., Jr.  The Viterbi Algorithm.  Proc IEEE 61, 3
        (March 1973), 268-278.

   [2]  McQuillan, J., I.  Richer and E.  Rosen.  An overview of the new
        routing algorithm for the ARPANET.  Proc.  ACM/IEEE Sixth Data
        Comm. Symp., November 1979.

   [3]  Mills, D.L.  Exterior Gateway Protocol Formal Specification.
        DARPA Network Working Group Report RFC-904, M/A-COM Linkabit,
        April 1984.

   [4]  Fox, T.L., (Ed.).  AX.25 amateur packet-radio link-layer
        protocol, Version 2.0.  American Radio Relay League, October
        1984.

































Mills                                                          [Page 14]



RFC 981                                                       March 1986
An Experimental Multiple-Path Routing Algorithm


Appendix A.  An Example

   An example will illustrate how Wiretap constructs primary and
   alternate routes given candidate node and link tables.  The candidate
   tables resulted from a scenario monitoring normal traffic on the
   145.01-MHz AX.25 packet-radio channel in the Washington, DC, area
   during a typical 24-hour period.  The node and link tables
   illustrated below give an idea of what the constructed data base
   looks like, as well as provide the basis for the example.

   Figure 1 illustrates a candidate node table showing the node ID
   (NID), callsign and related information for each station.  The Route
   field contains the primary route (minimum-distance path), as a string
   of NIDs from the origination station (NID = 0) to the destination
   station shown, with the exception of the endpoint NIDs.  The absence
   of a route string indicates the station is directly reachable without
   the assistance of a digipeater.  Note that the originating station is
   always the first entry in the node table, in this case W3HCF, and is
   initialized with defaults before the algorithm is started.

      NID Callsign    Flags   Links   Last Rec    Wgt   Route
      -------------------------------------------------------
      0    W3HCF      005     26      15:00:19    255
      1    WB4APR-5   017     18      16:10:38    30
      2    DPTRID     000     3       00:00:00    210   1
      3    W9BVD      005     3       23:24:33    40
      4    W3IWI      015     5       16:15:30    35
      5    WB4JFI-5   017     34      16:15:30    35
      6    W3TMZ      015     2       01:00:49    150   1
      7    WB4APR-6   017     14      14:56:06    35
      8    WB4FQR-4   017     4       06:35:15    40
      9    WD9ARW     015     3       14:56:04    115   11

      10   WA4TSC     015     3       15:08:53    115   11
      11   WA4TSC-1   017     9       15:49:15    35
      12   KJ3E       015     4       15:57:26    155   1
      13   WB2RVX     017     3       09:19:46    135   7
      14   AK3P       015     2       12:57:53    185   7 15
      15   AK3P-5     016     4       12:57:53    135   7
      16   KC2TN      017     3       04:01:17    135   7
      17   WA4ZAJ     015     2       21:41:24    240   5
      18   KB3DE      015     3       23:38:16    35
      19   K4CG       015     3       13:29:14    35

      20   WB2MNF     015     2       04:01:17    180   7 16
      21   K4NGC      015     3       14:57:44    90    8
      22   K3SLV      005     2       03:40:01    160   1


Mills                                                          [Page 15]



RFC 981                                                       March 1986
An Experimental Multiple-Path Routing Algorithm


      23   KA4USE-1   017     6       14:57:44    35
      24   K4AF       005     3       12:46:38    40
      25   WB4UNB     015     2       06:45:09    240   5
      26   PK64       005     3       02:50:54    40
      27   N4JOG-2    015     3       13:24:53    35
      28   KX3C       015     4       02:57:29    35
      29   W3CSG      015     4       06:10:17    115   11

      30   WD4SKQ     015     3       16:00:33    35
      31   WA7DPK     015     3       01:28:11    35
      32   N4JGQ      015     3       22:57:50    35
      33   K3AEE      005     3       03:52:43    40
      34   WB3ANQ     015     3       04:01:27    140   7
      35   K2VPR      015     2       12:07:51    240   5
      36   G4MZF      015     3       01:38:30    35
      37   KA3ERW     015     2       03:11:17    155   1
      38   WB3ILO     015     2       02:10:34    140   7
      39   KB3FN-5    016     4       06:10:17    110   11

      40   KS3Q       015     5       15:54:57    35
      41   WA3WUL     015     2       03:36:18    135   7
      42   N3EGE      015     3       15:58:01    160   1
      43   N4JMQ      015     2       08:02:58    185   7 13
      44   K3JYD-5    016     5       15:58:01    155   1
      45   KA4TMB     015     3       16:15:23    115   11
      46   KC3Y       015     2       04:14:36    155   1
      47   W4CTT      005     2       12:21:33    245   5

      52   K3JYD      015     2       02:16:52    155   1
      54   WA5WTF     015     2       02:01:20    240   5
      55   KA4USE     005     3       23:56:02    105   23
      56   N3BRQ      005     2       02:00:36    40
      57   KC4B       015     2       22:10:37    240   5
      58   WA5ZAI     005     2       12:44:03    40
      59   K4UW       005     2       02:36:05    40
      60   K3RH       015     2       01:20:47    135   7
      61   N4KRR      015     3       10:56:50    35
      62   K4XY       015     2       04:53:16    240   5
      64   WA6YBT     015     2       05:13:07    190   7 15

                     Figure 1. Candidate Node Table

   In the above table the Dist field shows the total distance of the
   primary route, the Links field shows the complexity factor, which is
   the number of links incident at that node (plus one), and the Last
   Rec field shows the time (UT) the station was last heard, directly or
   indirectly. The Flags field shows, among other things, which stations


Mills                                                          [Page 16]



RFC 981                                                       March 1986
An Experimental Multiple-Path Routing Algorithm


   have originated frames and which have digipeated them.  The bits in
   this field, which is in octal format, are interpeted as follows (bit
   0 is the rightmost bit):

                Bit     Function                       
                --------------------                   
                0       originating station            
                1       digipeater station             
                2       station heard (Last Rec column)
                3       station synchronized connection

   Among the 58 stations shown in Figure 1 are eleven digipeaters, all
   but three of which also originate traffic.  All but twelve stations
   have either originated or digipeated a synchronized connection and
   only one "station" DPTRID, actually a beacon, has not been heard to
   either originate or digipeat traffic.

   Figure 2 illustrates a candidate node table of 98 links showing the
   from-NID, to-NID, Flags and Age information for each link as
   collected. The bits in the Flags field, which is in octal format, are
   interpeted as follows (bit 0 is the rightmost bit):

                          Bit     Function    
                          -------------------