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