rfc981.txt

RFC 相关的技术文档

   directions and is marked "reciprocal".  However, there is only one
   synchronized mark, which can be set in either direction.  If a
   particular link is not marked either heard or synchronized, any
   presumption on its viability to carry traffic is highly speculative
   (the traffic is probably a beacon or "CQ").  If later marked
   synchronized the presumption is strengthened and if later marked
   heard in the reciprocal direction the presumption is confirmed.

   Experience shows that a successful routing algorithm for any
   packet-radio channel must have provisions for congestion avoidance.
   There are two straightforward ways to cope with this.  The first is a
   static measure of node congestion based on the number of links in the
   network graph incident at each node.  This number is computed by the
   wiretap routine and stored in the node table as it adds entries to
   the link table.

   The second, not yet implemented, is a dynamic measure of node
   congestion which tallies the number of link references during the
   most recent time interval (of specified length).  The current plan
   was suggested by the reachability mechanism used in the ARPANET and
   the Exterior Gateway Protocol [3].  An eight-bit shift register for
   each node is shifted in the direction from high-order to low-order
   bits, with zero-bits preceeding the high-order bit, at the rate of
   one shift every ten seconds.  If during the preceeding ten-second


Mills                                                           [Page 6]



RFC 981                                                       March 1986
An Experimental Multiple-Path Routing Algorithm


   period a header with a path involving that node is found, the
   high-order bit of the register is set to one.  When a path is
   calculated the number of one-bits in the register is totalled and
   used as a measure of dynamic node congestion. Thus, the time interval
   specified is 80 seconds, which is believed appropriate for the AX.25
   channel dynamics.

5.  Factor Computations and Weights

   The data items produced by the wiretap routine are processed to
   produce a set of factors that can be used by the routing routine to
   develop optimum routes.  In order to insure a stable and reliable
   convergence as the routing algorithm constructs and discards
   candidate paths leading to these routes, the factor computations
   should have the following properties:

   1.  All factors should be positive, monotone functions which increase
       in value as system performance degrades from optimum.

   2.  The criteria used to estimate link factors should be symmetric;
       that is, their values should not depend on the particular
       direction the link is used.

   3.  The criteria used to estimate node factors should not depend on
       the particular links that traffic enters or leaves the node.

   Each factor is associated with a weight assignment which reflects the
   contribution of the factor in the distance calculation, with larger
   weights indicating greater importance.  For comparison with other
   common routing algorithms, as well as for effective control of the
   computational resources required, it may be desirable to impose
   additional restrictions on these computations, which may be a topic
   for further study.  Obviously, the success of this routing algorithm
   depends on cleverly (i.e.  experimentally) determined factor
   computations and weight assignments.

   The particular choices used in the prototype implementation should be
   considered educated first guesses that might be changed, perhaps in
   dramatic ways, in later implementations.  Nevertheless, the operation
   of the algorithm in finding optimum routes over all choices in factor
   computations and weights is unchanged.  Recall that the wiretap
   routine generates data items for each node and link heard and saves
   them in the node and link tables.  These items are processed by the
   routing routine to generate the factors shown below in Table 1 and
   Table 2.




Mills                                                           [Page 7]



RFC 981                                                       March 1986
An Experimental Multiple-Path Routing Algorithm


      Factor  Weight  Name            How Determined
      ---------------------------------------------------------------
      f0      30      hop             1 for each link
      f1      50      unverified      1 if not heard either direction
      f2      5       non-reciprocal  1 if not heard both directions
      f3      5       unsynchronized  1 if no I or S frame heard

                         Table 1. Link Factors

      Factor  Weight  Name            How Determined
      ---------------------------------------------------------------
      f4      5       complexity      1 for each incident link
      f5      20      digipeated      1 if station does not digipeat
      f6      -       congestion      (see text)

                         Table 2. Node Factors

   With regard to link factors, the "hop" factor is assigned as one for
   each link and represents the bias found in other routing algorithms
   of this type.  The intent is that the routing mechanism degenerate to
   minimum-hop in the absence of any other information.  The
   "unverified" factor is assigned as one if the heard bit is not set
   (not heard in either direction), while the "non-reciprocal" factor is
   assigned as one if the reciprocal bit is not set (not heard in both
   directions).  The "unsynchronized" factor is assigned as one if the
   synchronized bit is not set (no I or S frames observed in either
   direction).

   With regard to node factors, the "complexity" factor is computed as
   the number of links incident at the node, while the "congestion"
   factor is to be computed as the number of intervals in the eight
   ten-second intervals preceding the time of observation in which a
   frame was transmitted to or through the node.  The "digipeated"
   factor is assigned as one if the node is only a source (i.e.  no
   digipeated frames have been heard from it).  For the purposes of
   path-distance calculations, the node factors are taken as zero for
   the endpoint nodes, since their contribution to any path would be the
   same.











Mills                                                           [Page 8]



RFC 981                                                       March 1986
An Experimental Multiple-Path Routing Algorithm


6.  The Routing Routine

   The dynamic data base built by the wiretap routine is used by the
   routing routine to compute routes as required.  Ordinarily, this
   needs to be done only when the first frame to a new destination is
   sent and at intervals thereafter, with the intervals perhaps
   modulated by retry count together with congestion thresholds, etc.
   The technique used is a variation of the Viterbi Algorithm [1], which
   is similar to the the shortest-path-first algorithm used in the
   ARPANET and elsewhere [2].  It operates by constructing a set of
   candidate paths on the network graph from the destination to the
   source in increasing number of hops. Construction continues until all
   the complete paths satisfying a specified condition are found,
   following which one with minimum distance is selected as the primary
   route and the others ranked as alternate routes.

   There are a number of algorithms to determine the mimimum-distance
   path on a graph between two nodes with given metric.  The prototype
   implementation operates using a dynamic path list of entries derived
   from the link table.  Each list entry includes (a) the NID of the
   current node, (b) a pointer to the preceding node on the path and (c)
   the hop count and (d) distance from the node to the final destination
   node of the path:

                   [ NID, pointer, hop, distance ] .

   The algorithm starts with the list containing only the entry [
   dest-NID, 0, 0, 0 ], where dest-NID is the final destination NID, and
   then scans the list starting at this entry.  For each such entry it
   scans the link table for all links with either to-NID or from-NID
   matching NID and for each one found inserts a new entry:

         [ new-NID, new-pointer, hop + 1, distance + weight ] ,

   where the new-NID is the to-NID of the link if its from-NID matches
   the old NID and the from-NID of the link otherwise.  The new-pointer
   is set at the address of the old entry and the weight is computed
   from the factors and weights as described previously.  The algorithm
   coontinues to select succeeding entries and scan the link table until
   no further entries remain to be processed, the allocated list area is
   full or the maximum hop count or distance are exceeded, as explained
   below.

   Note that in the Viterbi Algorithm, which operates in a similar
   manner, when paths merge at a single node, all except one of the
   minimum-distance paths (called survivors) are abandonded.  If only
   one of the minimum-distance paths is required, Wiretap does the same;


Mills                                                           [Page 9]



RFC 981                                                       March 1986
An Experimental Multiple-Path Routing Algorithm


   however, in the more general case where alternate paths are required,
   all non-looping paths are potential survivors.  In order to prevent a
   size explosion in the list, as well as to suppress loops, new list
   entries with new-NID matching the NID of an existing entry on the
   path to the final destination NID are suppressed and paths with hop
   counts exceeding (currently) eight or distances exceeding 255 are
   abandoned.

   If the Wiretap station NID is found in the from-NID of an entry
   inserted in the list, a complete path has been found.  The algorithm
   remembers the minimum distance and minimum hop count of the complete
   paths found as it proceeds.  When only one of the minimum-distance
   paths (primary route) is required, then for any list entry where the
   distance exceeds the minimum distance or the hop count exceeds the
   maximum hop count (plus one), the path is abandoned and no further
   processing done for it.  When alternate routes are required the
   hop-count test is used, but the minimum-distance test is not.

   The above pruning mechanisms are designed so that the the algorithm
   always finds all complete paths with the minimum hop count and the
   minimum hop count (plus one), which are designated the alternate
   routes. The assignment of factor computations and weights is intended
   to favor minimum-hop paths under most conditions, but to allow the
   path length to grow by no more than one additional hop under
   conditions of extreme congestion.  Thus, the minimum-distance path
   (primary route) must be found among the alternate paths, usually, but
   not always, one of the minimum-hop paths.

   At the completion of processing the complete paths are ranked first
   by distance, then by the order of the final entry in the list, which
   is in hop-count order by construction, to establish a well-defined
   ordering.  The first of these paths represents the primary route,
   while the remaining represent alternatives should all lower-ranked
   routes fail.

   Some idea of the time and space complexity of the routing routine can
   be determined from the observation that the computations for all
   primary and secondary routes of the example in Appendix A with 58
   nodes and 98 links requires a average of about 30 list entries, but
   occasionally overflows the maximum size, currently 100 entries.  Each
   step requires a scan of all the links and a search (for loops) along
   the maximum path length, which in principle can add most of the links
   to the list for each new hop.  Obviously, the resources required can
   escalate dramatically, unless effective pruning techniques such as
   the above are used.

   The prototype implementation requires 316 milliseconds on an


Mills                                                          [Page 10]



RFC 981                                                       March 1986
An Experimental Multiple-Path Routing Algorithm


   LSI-11/73 to calculate the 58 primary routes to all 58 nodes for an
   average of about 5.4 milliseconds per route.  The implementation
   requires 1416 milliseconds to calculate the 201 combined primary and
   alternate routes to all 58 nodes for an average of about 3.4
   milliseconds per route.

7.  Data Base Housekeeping

   In normal operation Wiretap tends to pick up a good deal of errors
   and random junk, since it can happen that a station may call any
   other station using ad-hoc heuristics and often counterproductive
   strategies. The result is that Wiretap may add speculative and
   erroneous links to the data base.  In practice, this happens
   reasonably often as operators manually try various paths to stations
   that may be shut down, busy or blocked by congestion.  Nevertheless,
   since Wiretap operates entirely by passive monitoring, speculative
   links may represent the principal means for discovery of new paths.

   The number of nodes and links, speculative or not, can grow without
   limit as the Wiretap station continues to monitor the channel.  As
   the size of the node table or link table approaches the maximum, a
   garbage-collection procedure is automatically invoked.  The procedure
   used in the prototype implementation was suggested by virtual-memory
   storage-management techniques in which the oldest unreferenced page
   is replaced when a new page frame is required.  Every link table
   entry includes an age field, which is incremented once each minute if
   its value is less than 60, once each hour otherwise and reset to zero
   when the link is found in a monitor header.  When new space is
   required in the link table, the link with the largest product of age
   and distance, as determined by the factor computations and weights,
   is removed first.

   Every node table entry includes the congestion factor mentioned
   above, which is a count of the number of links (plus one) incident at
   that node.  As links are removed from the link table, these counts
   are decremented.  If the count for some node decrements to one, that
   node is removed.  Thus, if new space is required in the node table,
   links are removed as described above until the required space is
   reclaimed.

   In addition to the above, and in order to avoid capture of the tables
   by occasional speculative spasms on one hand and stagnation due to
   excessively stale information on the other, if the age counter
   exceeds a predetermined threshold, currently fifteen minutes for a
   speculative link and 24 hours for other links, the link is removed




Mills                                                          [Page 11]