diff options
Diffstat (limited to 'doc/rfc/rfc981.txt')
| -rw-r--r-- | doc/rfc/rfc981.txt | 1254 |
1 files changed, 1254 insertions, 0 deletions
diff --git a/doc/rfc/rfc981.txt b/doc/rfc/rfc981.txt new file mode 100644 index 0000000..ebf6b5a --- /dev/null +++ b/doc/rfc/rfc981.txt @@ -0,0 +1,1254 @@ + + +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 + 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] + + + +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 + ------------------- + 0 source + 1 digipeated + 2 heard + 3 synchronized + 4 reciprocal + + From To Flags Age From To Flags Age + --------------------------- --------------------------- + 5 0 017 0 1 0 037 5 + 4 0 015 0 5 4 035 0 + 4 1 015 28 7 0 017 60 + 9 5 015 60 1 5 006 56 + 4 7 015 60 11 0 017 24 + 7 15 036 62 7 13 037 60 + 12 1 015 71 15 14 035 62 + 7 16 037 70 12 5 015 71 + 19 0 015 61 16 20 035 70 + 5 11 036 60 23 0 017 60 + 5 24 035 73 30 0 015 71 + 29 11 015 69 5 29 035 73 + 8 21 035 67 8 5 017 67 + 31 0 015 72 31 5 015 72 + 32 0 015 74 32 5 015 69 + + +Mills [Page 17] + + + +RFC 981 March 1986 +An Experimental Multiple-Path Routing Algorithm + + + 40 5 015 17 40 0 015 19 + 34 7 015 70 35 5 015 62 + 1 40 035 74 38 7 015 71 + 5 36 035 72 45 5 015 0 + 36 0 015 72 5 30 035 14 + 37 1 015 70 44 5 016 14 + 12 44 015 17 46 1 015 69 + 34 1 015 72 44 1 016 70 + 5 23 036 60 9 11 015 79 + 10 11 015 60 1 6 035 72 + 27 5 015 61 11 1 006 83 + 45 11 015 76 52 1 015 71 + + 5 2 000 14 8 0 005 76 + 57 5 015 75 17 5 015 75 + 3 0 005 74 3 5 005 74 + 26 5 005 71 26 0 005 74 + 18 5 015 74 18 0 015 74 + 55 5 005 73 24 0 005 62 + 61 0 015 63 55 23 005 73 + 54 5 015 71 61 5 015 63 + 59 0 005 71 56 0 005 71 + 5 7 006 71 7 60 035 72 + 28 0 015 71 62 5 015 69 + 1 7 036 70 28 5 015 71 + 7 41 035 70 28 1 015 71 + 58 0 005 62 1 22 005 70 + 33 7 005 70 33 0 005 70 + 64 15 015 69 25 5 015 67 + 39 10 035 68 11 39 036 68 + 43 13 015 65 29 39 015 68 + 40 7 015 62 47 5 005 62 + 19 23 015 61 27 0 015 61 + 42 1 005 23 23 21 035 60 + 1 2 000 5 42 44 015 14 + + Figure 2. Candidate Link Table + + The following tables illustrate the operation of the routing + algorithm in several typical scenarios. Each line in the table + represents the step where an entry is extracted from the path list + and new entries are determined. The "Step" column indexes each step, + while the "To" column indicates the NID of the station at that step. + The "Ptr" column is the index of the preceeding step along the path + to the destination, while the "Hop" and "Dist" columns represent the + total hop count and computed distance along that path. + + + +Mills [Page 18] + + + +RFC 981 March 1986 +An Experimental Multiple-Path Routing Algorithm + + + Following is a fairly typical example where the destination station + is not directly reachable, but several multiple-hop paths exist via + various digipeaters. The algorithm finds four digipeaters: 1, 5, 11 + and 39, all but the last of which are directly reachable from the + originating station, to generate two routes of two hops and two of + three hops, as shown below. Note that only the steps leading to + complete paths are shown. + + Destination: 29 Station: W3CSG + Step NID Ptr Hop Dist Comments + ------------------------------------------------------------- + 0 29 0 0 0 + 1 5 0 1 30 + 2 11 0 1 35 + 3 39 0 1 35 + 4 0 1 2 235 Complete path: 0 5 29 + 35 0 2 2 115 Complete path: 0 11 29 + 37 9 2 2 115 + 38 10 2 2 115 + 39 1 2 2 120 + 40 45 2 2 115 + 41 39 2 2 110 + 42 11 3 2 85 + 43 10 3 2 85 + 46 0 39 3 240 Complete path: 0 1 11 29 + 63 0 42 3 165 Complete path: 0 11 39 29 + + The algorithm ranks these routes first by distance and then by order + in the list, so that the two-hop route at N = 35 would be chosen + first, followed by the three-hop route at N = 63, the two-hop route + at N = 4 and, finally the three-hop route at N = 46. The reason why + the second choice is a three-hop route and the third a two-hop route + is because of the extreme congestion at the digipeater station 5, + which has 34 incident links. + + Following is an example showing how the path-pruning mechanisms + operate to limit the scope of exploration to those paths most likely + to lead to useful routes. The algorithm finds one two-hop route and + four three-hop routes. In this example the complete list is shown, + including all the steps which are abandond for the reasons given. + + + + + + + + + +Mills [Page 19] + + + +RFC 981 March 1986 +An Experimental Multiple-Path Routing Algorithm + + + Destination: 13 Station: WB2RVX + Step NID Ptr Hop Dist Comments + ------------------------------------------------------------- + 0 13 0 0 0 + 1 7 0 1 30 + 2 43 0 1 35 No path + 3 0 1 2 135 Complete path: 0 7 13 + 4 4 1 2 135 + 5 15 1 2 130 + 6 16 1 2 130 + 7 34 1 2 135 + 8 38 1 2 135 No path + 9 60 1 2 130 No path + + 10 5 1 2 140 Max distance 310 + 11 1 1 2 130 + 12 41 1 2 130 No path + 13 33 1 2 140 + 14 40 1 2 135 + 15 5 4 3 210 Max distance 380 + 16 0 4 3 215 Complete path: 0 4 7 13 + 17 1 4 3 215 Max distance 305 + 18 14 5 3 180 Max hops 4 + 19 64 5 3 185 Max hops 4 + + 20 20 6 3 175 Max hops 4 + 21 1 7 3 205 Max distance 295 + 22 0 11 3 250 Complete path: 0 1 7 13 + 23 4 11 3 255 Max distance 300 + 24 12 11 3 255 Max distance 295 + 25 40 11 3 250 Max distance 295 + 26 37 11 3 255 Max distance 285 + 27 46 11 3 255 Max distance 285 + 28 44 11 3 255 Max distance 280 + 29 34 11 3 255 Max distance 290 + + 30 6 11 3 250 Max distance 280 + 31 52 11 3 255 Max distance 285 + 32 28 11 3 255 Max distance 295 + 33 0 13 3 215 Complete path: 0 33 7 13 + 34 0 14 3 215 Complete path: 0 40 7 13 + 35 5 14 3 215 Max distance 385 + 36 1 14 3 210 Max distance 300 + + The steps labelled "No path" are abandonded because no links could be + found satisfying the constraints: (a) to-NID or from-NID matching + the NID of the step, (b) loop-free or (c) total path distance less + + +Mills [Page 20] + + + +RFC 981 March 1986 +An Experimental Multiple-Path Routing Algorithm + + + than 256. The steps labelled "Max distance" are abandonded because + the total distance, computed as the sum of the Dist value plus the + weighted node factors, would exceed 256 as shown. The steps labelled + "Max hops" are abandonded because the total hop count would exceed + the minimum hop count (plus one) as shown. + + Although this example shows the computations for all alternate + routes, if only the primary route is required all steps with total + distance greater than the minimum-distance (135) can be abandonded. + In this particular case path exploration terminates after only 14 + steps. + + The following example shows a typical scenario involving a previously + unknown station; that is, one not already in the data base. Although + not strictly part of the algorithm itself, the strategy in the + present system is to generate speculative paths consisting of an + imputed direct link between the originating station and the + destination station, together with imputed direct links between each + digipeater in the data base and the destination station. The new + links created will time out according to the cache-management + mechanism in about fifteen minutes. + + In the following example the destination station is 74, which results + in the following additions to the link table: + + fm-NID To-NID Flags Node Type + ---------------------------------- + 0 74 000 Originator + 1 74 000 Digipeater + 5 74 000 Digipeater + 7 74 000 Digipeater + 8 74 000 Digipeater + 11 74 000 Digipeater + 13 74 000 Digipeater + 15 74 000 Digipeater + 16 74 000 Digipeater + 23 74 000 Digipeater + 39 74 000 Digipeater + 44 74 000 Digipeater + + There are eleven digipeaters involved, not all of which may be used. + The resulting primary route and five alternate routes are shown + below. Note that only five of the eleven digipeaters are used. The + remainder were either too far away or too heavily congested. Note + that only the list entries leading to complete paths are shown. + + + + +Mills [Page 21] + + + +RFC 981 March 1986 +An Experimental Multiple-Path Routing Algorithm + + + Destination: 74 Station: CQ + Step NID Ptr Hop Dist Comments + ------------------------------------------------------------- + 0 74 0 0 0 + 1 0 0 1 90 Complete path: 0 74 + 2 1 0 1 90 + 4 7 0 1 90 + 5 8 0 1 90 + 6 11 0 1 90 + 7 13 0 1 90 + 8 15 0 1 90 + 9 16 0 1 90 + 10 23 0 1 90 + 11 39 0 1 90 + 12 44 0 1 90 + 13 0 2 2 210 Complete path: 0 1 74 + 29 0 4 2 195 Complete path: 0 7 74 + 44 0 5 2 150 Complete path: 0 8 74 + 45 0 6 2 170 Complete path: 0 11 74 + 60 0 10 2 155 Complete path: 0 23 74 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Mills [Page 22] + |