rfc981.txt
来自「RFC 的详细文档！」· 文本 代码 · 共 1,255 行 · 第 1/4 页
TXT
1,255 行
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
-------------------
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?