`Case 1:16-cv-02690-AT Document 109-4 Filed 07/19/16 Page 1 of 23
`
`
`
`
`EXHIBIT C
`
`EXHIBIT C
`
`
`
`RFC 981 - Experimental multiple-path routing algorithm
`Case 1:16-cv-02690-AT Document 109-4 Filed 07/19/16 Page 2 of 23
`
`[Docs] [txt|pdf]
`
`
`
`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]
`
`https://tools.ietf.org/html/rfc981[10/15/2015 4:19:54 PM]
`
`
`
`RFC 981 - Experimental multiple-path routing algorithm
`Case 1:16-cv-02690-AT Document 109-4 Filed 07/19/16 Page 3 of 23
`
`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]
`
`https://tools.ietf.org/html/rfc981[10/15/2015 4:19:54 PM]
`
`
`
`RFC 981 - Experimental multiple-path routing algorithm
`Case 1:16-cv-02690-AT Document 109-4 Filed 07/19/16 Page 4 of 23
`
`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]
`
`https://tools.ietf.org/html/rfc981[10/15/2015 4:19:54 PM]
`
`
`
`RFC 981 - Experimental multiple-path routing algorithm
`Case 1:16-cv-02690-AT Document 109-4 Filed 07/19/16 Page 5 of 23
`
`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]
`
`https://tools.ietf.org/html/rfc981[10/15/2015 4:19:54 PM]
`
`
`
`RFC 981 - Experimental multiple-path routing algorithm
`Case 1:16-cv-02690-AT Document 109-4 Filed 07/19/16 Page 6 of 23
`
`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]
`
`https://tools.ietf.org/html/rfc981[10/15/2015 4:19:54 PM]
`
`
`
`RFC 981 - Experimental multiple-path routing algorithm
`Case 1:16-cv-02690-AT Document 109-4 Filed 07/19/16 Page 7 of 23
`
`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
` 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]
`
`https://tools.ietf.org/html/rfc981[10/15/2015 4:19:54 PM]
`
`
`
`RFC 981 - Experimental multiple-path routing algorithm
`Case 1:16-cv-02690-AT Document 109-4 Filed 07/19/16 Page 8 of 23
`
`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]
`
`https://tools.ietf.org/html/rfc981[10/15/2015 4:19:54 PM]
`
`
`
`RFC 981 - Experimental multiple-path routing algorithm
`Case 1:16-cv-02690-AT Document 109-4 Filed 07/19/16 Page 9 of 23
`
`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]
`
`https://tools.ietf.org/html/rfc981[10/15/2015 4:19:54 PM]
`
`
`
`RFC 981 - Experimental multiple-path routing algorithm
`Case 1:16-cv-02690-AT Document 109-4 Filed 07/19/16 Page 10 of 23
`
`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]
`
`https://tools.ietf.org/html/rfc981[10/15/2015 4:19:54 PM]
`
`
`
`RFC 981 - Experimental multiple-path routing algorithm
`Case 1:16-cv-02690-AT Document 109-4 Filed 07/19/16 Page 11 of 23
`
`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]
`
`https://tools.ietf.org/html/rfc981[10/15/2015 4:19:54 PM]
`
`
`
`RFC 981 - Experimental multiple-path routing algorithm
`Case 1:16-cv-02690-AT Document 109-4 Filed 07/19/16 Page 12 of 23
`
`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
`