📄 rfc981.txt
字号:
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 69Mills [Page 17] RFC 981 March 1986An 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 1986An 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 1986An 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 lessMills [Page 20] RFC 981 March 1986An 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 1986An 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 74Mills [Page 22] ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -