@DCN7.ARPA:mills@dcn6.arpa (10/31/85)
From: mills@dcn6.arpa Folks, I hope you enjoy the following enough that you won't get mad at me for bloating your mail file, which as we all know creates gas. Dave The Wiretap Algorithm Abstract This document introduces wiretap algorithms, which are a class of routing algorithms that compute quasi-optimal 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 on the Viterbi algorithm in that it constructs minimum-weight paths as a function of a weighted sum of factors derived from link and node quality estimates. 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 fiesty environment to implement and test 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. This document describes the design, implementation and initial testing of the algorithm. 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. 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 LAPB, but with an extended frame header consisting of a string of radio callsigns representing a path, usually selected by the operator, from the originating station to the destination station, possibly via one or more intermediate packet repeaters or digipeaters. Most stations can operate simultaneously as digipeaters and as end systems. 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 selects a minimum-weight path, 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. 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 note 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, 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. 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 over the entire path is the path weight. Wiretap incorporates an algorithm which constructs the minimum-weight paths 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. Note that Wiretap in effect constructs minimum-weight paths in the direction from another station to the Wiretap station and, based on that information, then computes the optimum reciprocal routes from the Wiretap station to the other station. The expectation is that the other station also runs its own routing algorithm, which then computes its own optimal 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 best 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, suboptimal 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. 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 routes 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 of 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 its assigned IP address (if known), 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 node-related routing information and other miscellaneous information. The example discussed later in this document 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 several-hour period on a busy evening. Each node table entry requires 30 bytes and each link table entry four bytes. The maximum size of the node table is presently 100 entries, while that of the link table is 300 entries. The data base illustrated in the example has 42 entries in the node table and 46 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 the shortest path 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 suboptimal routes. In practice in the Washington, DC, area, most stations use a digipeater, which is 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. 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 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 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). 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 marked heard in each direction independently. In the above diagram the link between 2 and 7 is marked heard in both directions. 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 frame is probably a beacon). 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 the 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. 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 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. Factors 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 optimal 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 optimal. 1. 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. 2. 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 importance of the factor in the total path calculation, with the larger values indicating greater importance. The weighted sum of factors is thus a metric and represents the quantity to be minimized in the routing computation. Obviously, the success of this method 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. Factor Weight Name How Determined ---------------------------------------------------------------- f0 30 hop 1 for each link f1 15 unverified 1 if not heard in either direction f2 5 non-reciprocal 1 if not heard in both directions f3 5 unsynchronized 1 if no I or S frame Table 1. Link Factors Factor Weight Name How Determined ---------------------------------------------------------------- f4 5 complexity 1 for each incident link f5 5 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 for either direction and zero otherwise, while the "non-reciprocal" factor is assigned as one if the heard bit is not set for 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 heard on the direction to the node, while the "congestion" factor (not yet implemented) 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. For the purposes of path-weight calculations, both of these factors are taken as zero for the endpoint nodes, since their contribution to any path would be the same. 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 shortest-path-first algorithm used in the ARPANET and elsewhere. It operates by constructing a set of candidate paths on the network graph, each assigned the weighted sum of the node and link factors along the path. Construction continues until all of the minimum-weight complete paths are found (each of the same minimum weight), which are the optimum routes. There are a number of algorithms to determine the mimimum-weight path on a graph between two nodes with given metric. The prototype implementation operates using a dynamic list of entries derived from the link table. Each list entry includes the from-NID and to-NID of a link in the path, along with the current accumulated path weight from the from-NID to the final destination NID of the path. The algorithm starts with an empty list and the final destination NID. It scans the link table for all links with either to-NID or from-NID matching the final destination NID, updates the path weights based on the link factors and node factors of the to-NIDs and adds them to the list. Next, the algorithm selects the first entry in the list and scans the node table again for all links with from-NID matching the to-NID of this entry, updating the path weights as it proceeds. The algorithm coontinues to select succeeding entries and scan the link table until no further entries remain to be processed. In order to prevent a size explosion in the list, duplicates are suppressed along with potential loops (new entries with a from-NID matching the to-NID of an existing entry). If the Wiretap station NID is found in the from-NID of a link to be added to the list a complete path has been found. The algorithm remembers the minimum path weight of all complete paths found as it proceeds. If the accumulated path weight found on any subsequent path exceeds this, the path is abandoned and no further list entries made for it. At the completion of processing the minimum-weight complete paths have been determined with the first one found identified as the optimum route. However, the path must be reversed, since it was constructed backwards starting at the destination. At the same time the callsigns can be extracted from the node table to build the TAPR-1 command line. Some idea of the time and space complexity of the routing routine can be determined from the observation that the example below with 42 nodes and 46 links requires 27 list entries, each of which requires a scan of up to 46 links and a search (for duplicates and loops) of up to 27 list entries, and is thus roughly linear in the number of links and quadratic in the number of hops. The number of links is roughly somewhere between linear and quadratic in the number of nodes, so that processing resources can become strained if the number of nodes grows very large. The prototype implementation requires about 283 milliseconds on an LSI-11/73 to calculate the routes to all 42 nodes. An Example An example will illustrate how Wiretap constructs optimum 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 on a weekend evening. 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 node in the order collected. The Route field contains the digipeater route, as a string of NIDs, on a minimum-weight path to that station, except for the last one, which is the station NID itself. The absence of a route string indicates the station is directly reachable without the assistance of a digipeater. The Wgt field shows the total path weight of the route string shown, while the Links field contains the complexity factor f5. The contents of the remaining fields can be ignored. Note that the first four entries of the table are wired; that is, they were initialized with defaults before Wiretap was started. NID Callsign IP Address Flags Links Last Rec Wgt Route ----------------------------------------------------------------------- 0 W3HCF [128.4.1.1] 000 14 00:00:00 0 1 1 WB4JFI-5 [128.4.1.2] 006 15 16:37:56 40 2 W4HCP [128.4.1.3] 000 0 00:00:00 0 1 3 WD5DBC [128.4.1.4] 000 0 00:00:00 0 1 4 DPTRID [0.0.0.0] 000 1 00:00:00 155 1 5 K4KMC [0.0.0.0] 007 0 14:46:39 40 6 WD4BAV [0.0.0.0] 000 1 00:00:00 115 5 7 7 K4ARO-1 [0.0.0.0] 006 1 14:46:39 75 5 8 WB2RVX [0.0.0.0] 007 3 16:25:42 85 18 9 W3IWI [0.0.0.0] 007 6 16:37:44 40 10 WB4APR-6 [0.0.0.0] 007 9 16:25:45 40 11 KB5ZU [0.0.0.0] 000 1 00:00:00 170 1 12 WB6RQN [0.0.0.0] 003 0 16:33:17 40 13 BEACON [0.0.0.0] 000 3 00:00:00 80 16 14 KA4USE-1 [0.0.0.0] 007 8 15:57:59 40 15 MAIL [0.0.0.0] 000 1 00:00:00 125 10 16 WA4TSC [0.0.0.0] 003 0 15:21:45 40 17 CQ [0.0.0.0] 000 1 00:00:00 80 5 18 KS3Q [0.0.0.0] 007 2 16:25:47 40 19 WB2MNF [0.0.0.0] 006 2 15:05:05 120 10 20 KC2TN [0.0.0.0] 007 3 15:05:05 85 18 21 AK3P [0.0.0.0] 007 1 14:00:07 130 24 22 22 AK3P-5 [0.0.0.0] 006 4 14:00:07 80 24 23 KC3BN [0.0.0.0] 007 2 05:42:41 80 24 24 WA3KXG-6 [0.0.0.0] 007 2 05:42:41 40 25 KA4USE [0.0.0.0] 003 0 15:57:57 115 14 26 TEST [0.0.0.0] 000 1 00:00:00 110 9 27 K4NGC [0.0.0.0] 007 0 15:14:51 40 28 KA3KIW [0.0.0.0] 007 1 11:39:26 85 29 29 KA3DBK [0.0.0.0] 007 2 16:21:08 40 30 K3SLV [0.0.0.0] 007 1 13:17:19 40 31 W3HCE [0.0.0.0] 000 3 00:00:00 80 30 32 W3VH [0.0.0.0] 007 0 12:49:21 40 33 KE4TZ [0.0.0.0] 003 1 13:11:27 90 29 34 WA4QNO [0.0.0.0] 000 1 00:00:00 165 5 7 35 35 K4UMI-5 [0.0.0.0] 002 1 14:43:26 120 5 7 36 WB4FJI-5 [0.0.0.0] 002 1 14:45:41 80 27 37 WA4SZK [0.0.0.0] 000 1 00:00:00 210 5 7 38 39 38 K4LKQ-1 [0.0.0.0] 002 1 14:46:39 120 5 7 39 W4ULH-1 [0.0.0.0] 002 1 14:46:39 165 5 7 38 40 WB4FQR-4 [0.0.0.0] 006 1 15:05:25 75 27 41 N4SN [0.0.0.0] 007 0 15:47:25 145 1 42 KX3C [0.0.0.0] 002 2 16:21:08 40 Figure 1. Candidate Node Table Figure 2 illustrates a candidate node table showing the from-NID, to-NID and associated information for each link in the order collected. In the Flags field, which is in octal format, bit 1 (numbering from the rightmost bit, which is bit 0) is the heard bit, bit 2 the synchronized bit and bit 7 the reciprocal bit. The remaining bits and fields can be ignored. From To Flags Age From To Flags Age --------------------------- --------------------------- 1 0 002 3 1 4 002 3 5 0 002 104 5 7 007 104 7 6 006 255 10 0 002 19 8 10 207 15 10 9 207 43 9 1 207 4 1 11 000 41 12 1 003 8 1 14 206 8 14 13 003 8 14 0 002 40 1 10 002 4 10 15 002 4 10 13 002 57 12 0 002 237 16 0 002 72 16 13 003 72 5 17 003 255 18 0 002 15 18 10 207 15 10 20 006 87 20 19 207 87 18 9 003 255 19 10 006 87 21 22 207 146 22 10 206 146 10 21 004 255 24 0 002 255 23 22 007 255 22 24 206 255 24 23 207 255 23 9 006 255 9 22 006 146 25 14 203 40 18 1 003 15 9 26 002 255 9 8 006 43 27 1 207 78 27 0 002 79 29 0 002 19 28 29 007 255 29 1 207 62 1 28 006 255 30 0 002 185 30 31 007 185 32 0 002 211 32 1 207 211 29 18 207 72 33 29 003 191 29 14 202 191 14 33 002 196 18 20 203 157 18 8 203 158 9 0 002 152 5 10 003 109 10 31 002 109 5 1 003 109 5 31 003 108 5 30 003 108 7 35 002 107 35 34 002 107 27 36 003 104 36 9 002 104 27 14 207 81 14 9 006 40 7 38 002 104 38 39 002 104 39 37 002 104 27 40 007 87 40 1 206 83 41 1 207 49 29 42 207 19 42 0 002 19 Figure 2. Candidate Link Table The following example shows how Wiretap operates to compute the optimum route with respect to the factor computations and weights previously described. The example also shows how the procedure reacts to congested nodes by routing around them. The route to be computed involves the Wiretap station W3HCF (NID 0) and station AK3P (NID 21). As it turns out, the latter is not direclty reachable from W3HCF, but is indirectly reachable via other stations, including W3IWI (NID 9), WB4APR-6 (NID 10), AK3P-5 (NID 22) and WA3KXG-6 (NID 24). Some possible paths that might be considered include those in the following diagrams (the NID is shown above the node and the complexity factor below): (0) (10) (21) (1) o-------o-------o 0 9 0 (0) (24) (22) (21) (2) o-------o-------o-------o 0 2 4 0 (0) (9) (22) (21) (3) o-------o-------o-------o 0 6 4 0 A minimum-hop algorithm would chose the first path (1) as the optimum on the basis that it has the least number of hops; however, node 10 is a very busy digipeater and is often congested, as suggested by the complexity factor of 9. The other two paths (2) and (3) are one hop longer, but have lower complexity factors. Actually, the choice can go either way depending upon the link factors, which are not shown in the diagrams. Following is the result of a step-by-step analysis of the routing algorithm as it constructs the optimum route. The contents of the list used by this algorithm are shown at each step along with the factors used to calculate the path weight. The Incr field shows the incremental weight computed for the entry, while the Total field shows the accumulated total path weight. Only the From, To and Total fields are actually stored in the list. First, the algorithm scans the link table for links leading to the destination 21, which results in two entries in the list: From To f0 f1 f2 f3 f4 Incr Total --------------------------------------------------------------------- 22 21 30 0 0 0 0 30 30 10 21 30 15 5 0 0 50 50 Since the Wiretap station 0 is not found in the From field, the link table is scanned again for links leading to 22, which causes the following entries to be added to the list: 10 22 30 0 0 0 20 50 80 23 22 30 0 5 0 20 55 85 24 22 30 0 0 0 20 50 80 9 22 30 0 5 0 20 55 85 The link table is scanned again for links leading to 10, which causes the following entries to be added: 0 10 30 0 5 5 45 85 135 8 10 30 0 0 0 45 75 125 9 10 30 0 0 0 45 75 125 1 10 30 0 5 5 45 85 135 15 10 30 0 5 5 45 85 135 13 10 30 0 5 5 45 85 135 18 10 30 0 0 0 45 75 125 20 10 30 0 5 0 45 80 130 19 10 30 0 5 0 45 80 130 5 10 30 0 5 5 45 85 135 31 10 30 0 5 5 45 85 135 The result is a complete path of total weight 135, which is up to this point the minimum-weight complete path. However, the algorithm may yet find a complete path of less weight. The next entry in the list is 10, which has already been processed, so the algorithm tries the next entry 23, which has not been processed, and then entry 24 after that, which results in the following additions to the list: 9 23 30 0 5 0 10 45 110 24 23 30 0 0 0 10 40 95 0 24 30 0 5 5 10 50 130 Another complete path has been found, this one of total path weight 130, which is now the minimum of all found so far. Continuing, the algorithm scans the link table for links leading to 9 and adds the following: 1 9 30 0 0 0 30 60 145 18 9 30 0 5 5 30 70 155 26 9 30 0 5 5 30 70 155 8 9 30 0 0 5 30 65 150 0 9 30 0 5 5 30 70 155 36 9 30 0 5 5 30 70 155 14 9 30 0 0 5 30 70 155 All of these paths have total weights greater than 130 and thus can never lead to a complete path of weight less than that. Inspection of all remaining entries in the list show that none of them can lead to a complete path of weight less than 130, so the algorithm terminates at this point with the declaration that the (reversed) optimum route is (2) in the diagram above. It remains to be shown, however, that this route is indeed superior to the minimum-hop route, but this can be determined only by experiment. Data Base Housekeeping As apparent from the example, Wiretap tends to pick up a good deal of what might be called routing trash on the channel. It can happen that a station may call any other station whatsoever, with the result that Wiretap may pick this up and add speculative links to the data base. In practice, this happens reasonably often as operators try various heuristic routes 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 of discovery of new paths. The number of speculative links can be expected to grow without limit as the Wiretap station continues to monitor the channel. Eventually some sort of garbage collection will be required, possibly based upon an activity timer. The prototype implementation includes in every link table entry an activity timer represented as a counter that is incremented once each minute and reset to zero when the link is found in a monitor header. The intent is that, should this counter exceed a threshold, say fifteen minutes, and the link is not marked heard on either direction or synchronized, the link should be purged from the data base. If this results in an isolated node; that is, one not represented by any to-NID or from-NID in the link table, the node is purged as well. It is possible that a more agressive purging policy may be required for exceptionally busy channels, especially if operation using active probes or third-party routing is implemented. An effective way to manage this is on the basis of the link factors, their weights and the activity timers, with the rule that, among links with the highest weighted sum of link factors, the one not heard for the longest time should be the first one purged from the data base. Other heuristics may be useful as well. Summary and Directions for Further Development Wiretap represents an initial experiment and evaluation of the effectiveness of passive monitoring in the management of the packet-radio channel. While the results of initial experiments have been encouraging, considerable work needs to be done in the optimization of factor computations and weight assignments. For this to be done 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 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. 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 the text. Additional work, especially with respect to the hidden-station problem, is necessary. 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. -------