RFC981 日本語訳
0981 Experimental multiple-path routing algorithm. D.L. Mills. March 1986. (Format: TXT=59069 bytes) (Status: UNKNOWN)
プログラムでの自動翻訳です。
RFC一覧
英語原文
Network Working Group D. L. Mills
Request for Comments: 981 M/A-COM Linkabit
March 1986
L.工場がコメントのために要求するワーキンググループD.をネットワークでつないでください: 1986年3月の1COM Linkabitの981M/
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.
このRFCはパケットラジオ放送チャンネルのために設計された実験的で、複数の経路のルーティング・アルゴリズムを説明して、原型実現のデザインとテストについて議論します。 それはインターネットコミュニティで、より広い法則を見つけるかもしれないルーティング・アルゴリズムとデータベースの管理のテクニックのクラスに関する例として提示されます。 特別の関心は利用可能な限られたcumputationalリソースに関して潜在的に多くの投機的なルートを計算して、選択して、格付けするメカニズムであるかもしれません。 改良のための議論と提案は歓迎されます。 このメモの分配は無制限です。
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.
このドキュメントは盗聴アルゴリズムを導入します。(放送チャンネルを共有するステーションに準最適なルートを計算するルーティング・アルゴリズムのクラスですが、アルゴリズムは他のもの隠されるいくつかのステーションでクラスです)。 盗聴者は、チャンネルの上に他のステーションによって使用された経路(送信元経路)が交通を送るのを観測して、発見的なセットの要素と重りを使用して、投機的な経路をそれ自身の交通に構成します。 原型アルゴリズム、ここにWiretap Algorithmを呼んで、AX.25パケットラジオチャンネルのために設計されています。 デザインがあらゆる点で同様である、最も短い経路、最初に、(spf)アルゴリズムは、ほかの場所で中でアルパネットを使用して、事実上、ノードと縁に割り当てられた要素の荷重している合計として計算された距離に従ってグラフの最適な経路を構成するViterbi Algorithmを含むアルゴリズムのクラスの変化です。
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.
Wiretap Algorithmは幹線道路(最小の距離経路)だけではなく、代替経路はルートが失敗する予備選挙が役立つべきであるように役立つ距離によって注文された追加経路も計算するという点において従来のアルゴリズムと異なっています。 また、この特徴も以前にチャンネルの上に観測されなかった新しい経路の発見の役に立ちます。
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
以来、アマチュアAX.25パケットラジオチャンネルは、ワシントン(DC)地域で非常にアクティブであり、制裁状態の下まで多くの交通を運んで、それは原型アルゴリズムの説得力があるデモンストレーションのための十分英雄の環境であると考えられました。 それは"fuzzball"オペレーティングシステムを動かすLSI-11プロセッサのためにIP/TCPドライバーの一部として実行されました。 ドライバーは、WA8DEDファームウェア(両方でラジオequipmnetを制御する)を走らせながら、6809年のベースのTAPR-1プロセッサへのシリアル・ラインを通って接されます。
Mills [Page 1]
工場[1ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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
1. 序論
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 Algorithm(AX.25パケットラジオチャンネル[4]のためのダイナミックルーティングアルゴリズム)のデザイン、実現、および初期のテストについて説明します。 AX.25チャンネルは、1200年のビーピーエスにAFSK/FM変調を使用しながら、VHF頻度でCSMA主張モードで働いています。 AX.25プロトコル自体は、X.25リンク層プロトコルLAPBと同様ですが、拡張フレームヘッダーが2つの端のステーションの間と、そして、ことによると1つ以上の中間的パケットリピータを通して通常、オペレータによって選択された経路を表すラジオcallsignsかdigipeatersのストリングから成っていて、同様です。 そして、ステーションが同時に中間システムdigipeatersとして運用できる大部分)、終わりとして、ISOに関するシステムはモデル化されます。
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.
盗聴は最適なルートを決定するのに使用できるダイナミックなデータベースを造るためにチャンネルで伝えられたフレームの受け身のモニターを使用します。 アルゴリズムは、総距離を増加させることによって注文された1セットの経路を、リアルタイムで、操作して、発生させます、aで決定するように最も短い経路、最初に、新しいインターネット・ゲートウェイシステム[2]において今、アルパネットに使用されて、使用のために計画されていたそれと同様の手順。 実現は仮想のサーキットへの初期の接続時間に最適なルート(要素と重りに関して、選択される)を提供します、よくそれぞれのデータグラムトランスミッションのように。 このドキュメントは、"fuzzball"オペレーティングシステムを動かすLSI-11プロセッサのための原型実現の初期の現状報告と概観です。
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.
そして、Wiretapのようなルーティング・アルゴリズムの使用における主要な利点は直接路が利用可能であるときに、digipeater経路を避けることができるということです、必要であるときにだけ使用されるdigipeatersでまた、隠されたステーションを発見するために。 現在の踏査のステージの発展では、Wiretapの範囲は故意に受け身のモニターに制限されました。 後期段階に、範囲は、クラスタリングのテクニックの隠されたステーションと使用が大量のルーティング情報の分配を管理すると発見するために活発な徹底的調査の使用を含むように広げられるかもしれません。
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,
AX.25チャンネル・インタフェースは4800ビーピーエスのシリアル・ラインによってWA8DEDファームウェア(バージョン1.0)を走らせて、LSI-11に接続された6809年のベースのTAPR-1プロセッサです。 WA8DEDファームウェアはオプションとして選択されたタイプのそれぞれの容認されたフレームのためのモニターレポートを製作します。
Mills [Page 2]
工場[2ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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:
Uを含んでいる、私、およびSフレーム。 盗聴は、ルーティング情報を抜粋するためにそれぞれのこれらを処理して、システムログファイルで(任意に)それらを貯蓄します。 以下に、典型的なレポートがあります:
fm KS3Q to W4CQI via WB4JFI-5* WB4APR-6 ctl I11 pid F0
WB4JFI-5*WB4APR-6 ctl I11 pid F0を通したW4CQIへのfm KS3Q
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.
由来しているステーションはKS3Qです、そして、目的地はW4CQIです。 フレームは、最初に、WB4JFI-5と次に、WB4APR-6によってdigipeatedされて、Iフレーム(一連番号はIインディケータに従う)であり、プロトコル識別子F0を持っています(魔法をかけます)。 アスタリスク「*」は、レポートがそのステーションから受け取られたのを示します。 アスタリスクが全く現れないなら、創始者からレポートを受け取りました。
2. Design Principles
2. 設計原理
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.
経路は1つのステーションで由来する指示されたリンクの連結です、1digipeatersを通して広がっていて、別のステーションで終わって。 各リンクは1セットの計算するか、または見積もることができる費用、遅れまたはスループットなどの要素によって特徴付けられます。 ノードとリンクテーブルから成って、盗聴は、各リンクのためのいくつかの本質的な要素を計算して、ルーティングデータベースをアップデートします。 各リンクのためのこれらの要素の荷重している合計はそのリンクの距離です、経路の各リンクへの距離の合計がその経路の距離ですが。
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デザインの意図です。 したがって、非ループ経路の確率はリンクの確率の製品です。 Viterbi[1]のテクニックに従って、メートル法で確率の対数の変化としての距離を表すのは便利です。次に、確率はaになります。 しかしながら中、以下、基本的な確率、距離が発見的ベースで見積もられているので、直接考えられません。
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.
ルーティングデータベースに保管されていた要素と重りに従って、盗聴は与えられた端のステーションの間に距離によって注文された1セットの経路を構成するアルゴリズムを組み込みます。 要素と重りの与えられた課題に関するこれらのステーションの間の最適なルートであるとそのような経路を考えることができます。 原型実現では、端のステーションの1つはWiretapステーション自体であるに違いありません。 しかしながら、原則として、Wiretapステーションはデータベースの中で情報の適用性を条件として他のステーションにルートを発生させることができます。
Note that Wiretap in effect constructs minimum-distance paths in the
事実上、そのWiretapが最小の距離経路を構成することに注意してください。
Mills [Page 3]
工場[3ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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.
目的地ステーションからの指示はWiretapステーションから目的地ステーションまでWiretapステーションとその情報に基づいたその時に最適な相互的なルートを計算します。 期待はまた、目的地局がそれ自身のルーティング・アルゴリズムを放映するということです。(次に、ルーティング・アルゴリズムはそれ自身の最適な相互的なルート(すなわち、Wiretapステーションからの最適な直航路)を計算します)。 しかしながら、2つのステーションのルーティングデータベースは混雑か隠されたステーションのため分岐するかもしれません、計算されたルートが一致しないように。
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.
原則として、直接交信しているステーションだけではなく、また、彼らを聞くかもしれない他のものが提供された情報を使用することでWiretapによって計算されたルートを微調整できます。 最もおもしろいシナリオがすべてのステーションが適当な分配されたプロトコルを使用することでWiretap情報を交換するだろうことですが、これは現在、原型実現の範囲を超えています。 それにもかかわらず、「副-最適条件」にもかかわらず、役に立つ経路は1つのステーションがWiretapによって計算されたルートともう片方を使用していて伝統的で簡単な方法で得て、それは相互的です、容認されたフレームヘッダーから決定するようにことであるかもしれません。 したがって、Wiretapは既存のチャンネル手順とプロトコルと互換性があります。
3. Implementation Overview
3. 実現概観
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.
LSI-11のための原型Wiretap実現は2つのルーチンと盗聴ルーチンとルーティングルーチン(データベースの中で情報を使用することで経路について計算するもの)を含んでいます。(それは、容認されたモニターヘッダーから情報を抜粋して、ルーティングデータベースを造ります)。 データベースは3個のテーブル、チャンネルテーブル、ノードテーブル、およびリンクテーブルから成ります。 チャンネルテーブルはWA8DEDファームウェア(現在の構成の5)を走らせるTAPR-1プロセッサによって支えられた各チャンネル(仮想のサーキット)のためのエントリーを含んでいます。 このテーブルの構造と使用について、単にアルゴリズムに付帯的であり、さらに議論しないでしょう。
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.
ノードテーブルはチャンネルの上に聞かれたそれぞれの異なったcallsign(集合体か標識識別子であるかもしれない)のためのエントリーを含んでいます、ノード関連のルーティング情報、最新の計算されたルート、および他の種々雑多な情報と共に。 テーブルはノードID(NID)によって索引をつけられます。(それは、計算されたルートと扱いにくいcallsignストリングの代わりに他のテーブルで使用されます)。 リンクテーブルはモニターヘッダーで観察されたそれぞれの異なった(順不同の)ノード組エントリーを含んでいます。 各エントリーはリンク関連のルーティング情報と他の種々雑多な情報と共に見つけられた最初の例のNIDでNIDを含んでいます。 両方のテーブルは、後で説明された荷重している最も最近でない中古の交換メカニズムに基づくキャッシュアルゴリズムを使用することでダイナミックに管理されます。
Mills [Page 4]
工場[4ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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.
Appendix Aで議論した例はイラストのために候補ノードとリンクテーブルを含んでいます。 これらのテーブルはリアルタイムで、典型的な24時間の期間、集められた放送されなかったモニターヘッダーからの原型実現で組み立てられました。 それぞれのノードテーブル項目は4バイトの26バイトとそれぞれのリンクテーブルエントリーを必要とします。 現在、ノードテーブルの最大サイズは75のエントリーですが、リンクテーブルのものは150のエントリーです。 キャッシュアルゴリズムが1日か2日間、いったん安定していると、ノードテーブルのおよそ60のエントリーとリンクテーブルの100のエントリーを持っているのは通常です。
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.
一緒にノードテーブルとリンクテーブルはWiretapステーションにかかわるものだけではなく、どんな2つの端のステーションの間でもそのグラフでネットワークグラフを作図して、経路について計算するのに必要なすべての情報を含んでいます。 しかしながら、Wiretapステーションが「副-最適条件」ルートを選ぶことができるように一般に、チャンネルの上の他のすべてのステーションを聞くというわけではないことに注意してください。 しかしながら、ワシントン(DC)地域では、ほとんどのステーションが数個のdigipeatersの1つを使用します。(一般に、digipeatersはその領域の他のステーションによって確かに聞かれます)。 したがって、Wiretapステーションは、結局、上のテーブルと後で説明されたルーティング・アルゴリズムを使用することで他のほとんどすべてのステーションとしてルートを得ることができます。
4. The Wiretap Routine
4. 盗聴ルーチン
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.
盗聴ルーチンは、それぞれのモニターヘッダーを処理するために呼ばれます。 それは、ヘッダーから各callsignを順番に抽出して、対応するNIDのためにノードテーブルを捜します、そうでなければ、そこで既に新しいエントリーとNIDを作って。 結果は一連のNIDsです、由来しているステーションで始まって、最大8digipeatersを通して広がっていて、目的地ステーションで終わって。 このストリングに沿った各組のNIDsに関しては、リンクテーブルはストリングにみられるように直リンクかその逆数のどちらかを捜されます。 すなわち、創始者に向かった指示。
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.
以下のダイヤグラムでここに起こる操作は例証できます。(それは、digipeaters7、2、および9を通して4番射台から6番射台まで連続して見かけの経路があるモニターヘッダーの代理をします)。 それは起こります。ヘッダーはWiretapステーション(0)によって2番射台から聞かれました。
(4) (7) (2) (9) (6)
orig o------>o<=====>o------>o------>o dest
|
|
V
(0)
wiretap
(4) (7) (2) (9)(6)orig o------>o<===>o------>o------>o dest| | V(0)盗聴
Mills [Page 5]
工場[5ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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).
おそらく、ヘッダーが2番射台から聞かれたという事実は、4番射台から2番射台までそして、ステーション0への経路が実行可能であることを示します、「聞かれること」をその方向にこの経路に沿った各リンクを示されることができるように。 しかしながら、2番射台から6番射台までの経路の生存力を推定できるだけです、追加証拠が利用可能でない場合。 事実上、ヘッダーが私かSが縁どるAX.25(しかし、Uフレームでない)から来ているなら、AXの.25の仮想のサーキットは以前に端のステーションの間で明らかに確立されました、そして、推定は強まっています。 この場合、各4〜6までのリンクは「連動していること」が(しかし、2〜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."
すべてのステーションが、フレームを溯源して、それらをdigipeatすることができるというわけではありません。 ステーション9は仮定のdigipeaterにすぎません、そして、4番射台は、digipeatへの溯源するために観測されるのと7番射台ですが、残っているステーションがフレームを溯源できるというどんな証拠も利用可能ではありません。 したがって、4番射台から7番射台へのリンクは、「ソース」であるとマークされて、"digipeatedする"であることが7番射台から2番射台まで示されます。
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.
混雑と隠されたステーションの存在によって、6番射台から4番射台への方向への相互的な経路には全く異なったリンクの特性があるのは起こるかもしれません。 したがって、独自に各方向に聞かれるようにリンクを認識できます。 上のダイヤグラムで、2と7とのリンクは、両方の方向に聞かれて、「相互的であること」が示されます。 しかしながら、1つの連動しているマークしかありません。(どちらの方向にもそれを設定できます)。 特定のリンクが聞かれるのはマークもされませんし、連動もしないなら、交通を運ぶ生存力におけるどんな推定も非常に投機的です(交通は、たぶん標識か"CQ"です)。 後で連動しているとマークされるなら、推定は強まっています、そして、後で相互的な方向に聞かれるとマークされるなら、推定は確認されます。
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.
経験は、どんなパケットラジオチャンネルにおいても、うまくいっているルーティング・アルゴリズムには輻輳回避のための条項がなければならないのを示します。 これに対処する2つの簡単な方法があります。 1番目は各ノードのネットワークグラフ事件における、リンクの数に基づくノード混雑の静態分析法です。 リンクテーブルにエントリーを加えるとき、この数は、盗聴ルーチンで計算されて、ノードテーブルに格納されます。
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
まだ実行されなかった2番目は最新の時間間隔(指定された長さの)の間にリンク参照の数を記録するノード混雑のダイナミックな手段です。 現在のプランはアルパネットに使用される可到達性メカニズムとExteriorゲートウェイプロトコル[3]によって示されました。 各ノードのための8ビットシフトのレジスタは高位から下位のビットまで方向に移行します、ゼロ・ビットが高位のビットをpreceedingしている状態で、10秒毎の1つのシフトの速度で。 preceedingの間12番目
Mills [Page 6]
工場[6ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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.
以上、経路があるノードが見つけられるヘッダーがかかわって、レジスタの高位のビットは1つに設定されます。 経路が計算されるとき、レジスタの1ビットの数は、ダイナミックなノード混雑の手段として合計されて、使用されます。 したがって、指定された時間間隔は80秒です。(その秒はAX.25チャンネル力学に適切であると信じられています)。
5. Factor Computations and Weights
5. 要素計算と重り
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セットの要素を作り出すために処理されます。 ルーティング・アルゴリズムがこれらのルートにつながる候補道を構成して、捨てるとき安定して信頼できる集合を保障するために、要素計算には、以下の特性があるべきです:
1. All factors should be positive, monotone functions which increase
in value as system performance degrades from optimum.
1. すべての要素はシステム性能が最適条件から下がるのに従って値を増やす上向きの一本調子機能であるべきです。
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.
2. 評価基準は、以前はよくリンク要素が左右対称であるべきであると見積もっていました。 すなわち、それらの値は特定の方向に依存するべきではありません。使用されるリンク。
3. The criteria used to estimate node factors should not depend on
the particular links that traffic enters or leaves the node.
3. 評価基準は、以前はよくノード要素を交通がノードを入力するか、または残す特定のリンクに依存するべきでないと見積もっていました。
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.
原型実現に使用される特定の選択は変えられるかもしれない教育された最初の推測であると考えられるべきです、恐らく劇的な方法で、後の実現で。 それにもかかわらず、要素計算と重りにおけるすべての選択に関して最適なルートを見つけることにおける、アルゴリズムの操作は変わりがありません。 盗聴ルーチンが各ノードのためにデータ項目を発生させて、リンクがノードとリンクテーブルでそれらを聞いて、救うと思い出してください。 これらの項目は、Table1とTable2に以下に示された要素を発生させるようにルーティングルーチンで処理されます。
Mills [Page 7]
工場[7ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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
どれくらい断固としていたか状態で重さの名を因数分解してください。--------------------------------------------------------------- それぞれのリンクf1 50のためのf0 30ホップ1は、1を非検証したか、指示f2 5の非相互的な1を聞いたか、またはいいえが私かSが縁どる聞かれたなら、両方の指示f3 5 unsynchronized1を聞きました。
Table 1. Link Factors
1を見送ってください。 リンク要素
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)
どれくらい断固としていたか状態で重さの名を因数分解してください。--------------------------------------------------------------- ステーションがどんなdigipeat f6もしないなら、それぞれの付随しているリンクf5 20のためのf4 5複雑さ1は1をdigipeatedしました--、混雑(テキストを見ます)
Table 2. Node Factors
2を見送ってください。 ノード要素
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).
リンク要素に関して、「ホップ」要素は、各リンクあたり1つとして割り当てられて、このタイプの他のルーティング・アルゴリズムで見つけられた偏見を表します。 意図はルーティングメカニズムがいかなる他の情報がないとき最小のホップに退化しているということです。 聞かれたビットが設定されないなら(どちらの方向にも聞かれません)、"非検証"の要素は1として割り当てられます、相互的なビットが設定されないなら(両方の方向に聞かれません)、「非互恵」要素は1として割り当てられますが。 連動しているビットが設定されないなら(いいえは私かSが縁どるどちらの方向にも見ました)、"非連動"の要素は1として割り当てられます。
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.
フレームがノードかノードを通して伝えられた観測の時に前のノード要素、8における、間隔の数として計算されて、要素が「混雑」要素がそうである間のノードのリンク事件の数として計算される「複雑さ」12番目の間隔に関して。 "digipeatedする"の要素はノードがソースにすぎない(すなわち、digipeatedフレームは全くそれから聞かれていない)なら1として割り当てられます。 経路距離計算の目的のために、ノード要素は終点ノードのためのゼロとしてみなされます、どんな経路への彼らの貢献も同じでしょう、したがって。
Mills [Page 8]
工場[8ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
6. The Routing Routine
6. ルート設定ルーチン
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.
盗聴ルーチンで造られたダイナミックなデータベースは、必要に応じてルートを計算するのにルーティングルーチンで使用されます。 通常、これは、その後単に新しい目的地への最初のフレームを送る時と間隔を置いてする必要があります、恐らく混雑敷居などと共に再試行カウントで調節された間隔で 使用されるテクニックがViterbi Algorithm[1]の変化である、最も短い経路、最初に、アルゴリズムはアルパネットとほかの場所で[2]を使用しました。Viterbi Algorithmは同様です。 それは、増加する数のホップで目的地からソースまでネットワークグラフの1セットの候補道を構成することによって、作動します。 指定された状態を満たすすべての完全な経路が見つけられるまで、工事は続きます、どれが幹線道路として最小の距離で選定されるか、そして、代替経路として格付けされた他のものに続いて。
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:
メートル法で与えられるのがある2つのノードの間のグラフのmimimum-距離経路を決定するために、多くのアルゴリズムがあります。 原型実現は、リンクテーブルから得られたエントリーの動態的経路リストを使用することで作動します。 それぞれのリストエントリーは(c) ノードから最終的な経路の目的地ノードまでの(a) 現在のノードのNID、(b) 経路の前のノードへのポインタ、ホップカウント、および(d)距離を含んでいます:
[ NID, pointer, hop, distance ] .
[NID、ポインタ、ホップ、距離。]
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:
エントリーだけを含んでいて、アルゴリズムはリストから始まります。[dest-NID、0、0、0(dest-NIDは最終的な目的地NIDと、その時である)は]このエントリーでリスト始めをスキャンします。 それがスキャンするそのような各エントリーのために、NIDかNIDからの合っているNIDとのすべてのリンクとそれぞれのためのリンクテーブルは新しいエントリーに差し込みに当たりました:
[ new-NID, new-pointer, hop + 1, distance + weight ] ,
[新しいNIDの、そして、新しいポインタのホップ+1、距離+重さ]
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.
そうでなければ、新しいNIDがそうでは、それがNIDであるなら、リンクのNIDはリンクの古いNIDでNIDに合っています。 新しいポインタは古いエントリーのアドレスに設定されます、そして、重さは以前に説明されるように要素と重りから計算されます。 一層のエントリーが全く処理されるために残らないまで、続くエントリーを選択して、リンクテーブルをスキャンするアルゴリズムcoontinues、割り当てられたリスト領域が完全であるか、または最大のホップカウントか距離が超えられています、以下で説明されるように。
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;
Viterbi Algorithmでは、最小の距離経路(生存者と呼ばれる)の1つ以外のすべてがabandondedされることに注意してください。(経路がただ一つのノードで合併すると、Viterbi Algorithmは同じように作動します)。 最小の距離経路の1つだけが必要であるなら、Wiretapは同じようにします。
Mills [Page 9]
工場[9ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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.
しかしながら、代替パスが必要であるより一般的な場合では、すべての非ループ経路が潜在的生存者です。 リストにおけるサイズ爆発を防いで、輪を抑圧するために、新しいNIDとの経路の既存のエントリーのNIDを最終的な目的地NIDに合わせる新しいリストエントリーは抑圧されます、そして、ホップカウントが(現在)の8を超えていて、距離が255を超えている経路は捨てられます。
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.
WiretapステーションNIDがリストに挿入されたエントリーのNIDから見つけられるなら、完全な経路は見つけられました。 アルゴリズムは最小の距離と続くので見つけられた完全な経路の最小のホップカウントを覚えています。 1だけであるときに、最小の距離では、経路(幹線道路)が必要です、そして、距離が最小の距離を超えるか、ホップカウントが最大のホップカウント(プラス1)を超えて、または経路が捨てられるどんなリストエントリーもしますが、それのために行われなかったどんなより遠い処理も。 代替経路が必要であるときに、ホップカウントテストは使用されていますが、最小の距離テストは使用するというわけではありません。
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.
上の刈り込みメカニズムは、いつも最小のホップカウントと最小のホップがあるすべての完全な経路が代替経路に指定される(プラス1)を数えるのがアルゴリズムによってわかるように、設計されています。 経路の長さが極端な混雑の状態の1つ未満の追加ホップで成長するのを許容するためにしかし、要素計算と重りの課題がほとんどの条件のもとで最小のホップ経路を支持することを意図します。 したがって、最小の距離経路(幹線道路)は、代替パスの中で通常見つけられますが、いつも見つけられなければならないというわけではありません、最小のホップ経路の1つ。
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.
処理の完成のときに、完全な経路は最初に、距離によって格付けされます、そして、リストにおける、最終記入の注文で。(明確な注文を証明するために、リストはホップカウント命令に工事であります)。 これらの経路の1番目は幹線道路を表して、残りは代替手段を表しますが、より低く格付けされたルートが失敗するすべてがそうするべきです。
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.
ルーティングルーチンの時間と空間的コストの何らかの考えが58のノードと98個のリンクがあるAppendix Aの例のすべての第一の、そして、二次のルートのための計算をおよそ30のリストエントリーの平均を必要としますが、最大サイズ(現在の100のエントリー)から時折はみ出させるという観測から決定できます。 各ステップは最大の経路の長さに沿ってすべてのリンクのスキャンと検索(輪のための)を必要とします。原則として、長さはそれぞれの新しいホップのためのリストへのリンクの大部分を加えることができます。 明らかに、上記などの効果的な刈り込みのテクニックが使用されていない場合、必要であるリソースは劇的に徐々に拡大することができます。
The prototype implementation requires 316 milliseconds on an
原型実現が316ミリセカンド後で必要です。
Mills [Page 10]
工場[10ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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.
58予備選挙を計算するLSI-11/73は1ルートあたり平均およそ5.4ミリセカンドと同じくらいのノードをすべての58に発送します。 実現は、1ルートあたり平均およそ3.4ミリセカンドと同じくらいのすべての58のノードへの201の結合した第一の、そして、交互のルートを計算するために1416人のミリセカンドを必要とします。
7. Data Base Housekeeping
7. データベース家事
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.
通常の操作では、Wiretapは、多くの誤りと無作為のくずを再開する傾向があります、ステーションが、いかなる他のステーションも臨時の発見的教授法としばしば反生産的の戦略を使用すると呼ぶかもしれないのを起こることができるので。 結果はWiretapが投機的で誤ったリンクをデータベースに加えるかもしれないということです。 実際には、オペレータが手動で下がっていて、忙しい状態で閉められるか、または混雑で妨げられるかもしれないステーションに様々な経路を試みるとき、これはしばしば合理的に起こります。 それにもかかわらず、Wiretapが完全に受け身のモニターで作動するので、投機的なリンクは新しい経路の発見のための主要な手段を表すかもしれません。
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.
Wiretapステーションが、限りなくチャンネルをモニターし続けているのに応じて、ノードとリンクの投機的な数は成長できます。 ノードテーブルかリンクテーブルのサイズが最大にアプローチするとき、ガーベージコレクション手順は自動的に呼び出されます。 原型実現における実行した手順は新しいページフレームが必要であるときに取り替えられる中で参照されないページ最も古い仮想記憶保管管理のテクニックで示されました。 あらゆるリンクテーブルエントリーが時代分野を含んでいます。(リンクがモニターヘッダーで見つけられるとき、それは、それぞれの分の一度、値が60未満であるならかつてのそれぞれの時間に別の方法で増加されて、ゼロにリセットされます)。 新しいスペースがリンクテーブルで必要であるときに、時代と距離の最も大きい製品との要素計算と重りで決定するリンクは最初に、取り外されます。
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.
あらゆるノードテーブル項目がそのノードで付随していた状態で前記のように混雑要素を含んでいます。(それは、リンク(プラス1)の数のカウントです)。 リンクがリンクテーブルから取り外されるのに従って、これらのカウントは減少します。 1つへのいくつかのノード減少のためのカウントであるなら、そのノードは取り除かれます。 したがって、新しいスペースがノードテーブルで必要であるなら、リンクは必要なスペースが取り戻されるまで上で説明されるように取り外されます。
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
に加えて上記であり、現在の投機的なリンクへの15分間と他のリンクへの24時間、リンクは、時代カウンタが予定された敷居を超えているならもう片方の過度に聞き古した情報による片手と停滞で時々の投機的な発作によるテーブルの捕獲を避けるために取り外されます。
Mills [Page 11]
工場[11ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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
8. さらなる開発のための概要と指示
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.
盗聴はAXの管理で.25パケットラジオチャンネルをモニターする受動態の有効性の初期の実験と評価を表します。 初期の実験の結果が奨励している間、かなりの仕事が、重さの課題の様々な組み合わせを試みることができるプロトタイプ装置の日常業務で獲得するのに事実上、何らかの経験が必要とする最適化でする必要があります。
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.
原型実現はおよそ4カ月この文を草するときに使用中です。 しかしながら、多くのレッスンがすばやく学習されました。 実現は初期の接続要求を管理するために有限状態オートマトンを含んでいます、Wiretapによって計算された代替経路に沿ってSABMフレームを再試行する能力を含んでいて。 簡単な、しかし、有効なヒューリスティックは、digipeatersとして特定されたノードテーブルの他のすべてのステーションと共に目的地ステーションとWiretapステーションとのリンクを人工的に加えることによって投機的な経路を発生させるのに使用されます。 そして、アルゴリズムは第一の、そして、交互のルートを発生させるように上で説明されるように作動します。 このテクニックに関する例は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.
TAPR-1プロセッサが、低レベルのAXの.25の仮想のサーキットが失敗したことを原型実現に通知するように、メカニズムがありますが、代替パスを試みることができて、上側のレベルTCP接続、私がIPデータグラムがAX.25で包装したどの用途を縁どるか、そして、(接続モード)またはUIフレーム(コネクションレスなモード)の失敗に合図するために、どんな本質的なメカニズムもありません。 これは同輩が物理的にリンク・レベル実体から遠方であることで位置しているどんなエンドシステムプロトコルに関する一般的な問題です。 経験は、プロトコル層の間の制御情報を共有するために両用導管を提供する値が真剣に過小評価されるかもしれないのを示します。
The prototype implementation manages processor and storage demands in relatively simple ways, which can result in considerable
原型実現は比較的簡単な方法でプロセッサと格納要求を管理します。(方法はかなりに結果として生じることができます)。
Mills [Page 12]
工場[12ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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.
非能率。 Wiretapのどんな広く分配されたバージョンでもこれらの要求が慎重に管理されなければならないのは、明らかです。 上に示されるように、旧情報を掃除する有効な条項(特に投機的なリンク)は重大です、例えばリンク状態と交通モードの関数として経路計算の間隔を制御する条項と同様に。
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.
完全に分配されたルーティング・アルゴリズムに向かった発展における次のステップはアクティブな調べのテクニックの導入です。 これは新しい経路を発見して、既存のものについて微調整する能力をかなり改良するべきです。 他のステーションがルーティング・アルゴリズムを全く使用していないcompatibiltyを維持することと同様にアクティブな調べメカニズムを実行するのは受け身に唯一のWiretapとの互換性を維持している間、可能であるべきです。 交通がないとき経路を発見して、更新する標識の賢明な使用が必要であるように思えて、ある種のエコー/回答と同様にICMP Echo/回答サポートと同様のメカニズムがインターネット・ホストに必要です。
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.
Wiretapのようなルーティング・アルゴリズムで提供された柔軟性を利用するために、現在の「厳しい」ソースルーティングに加えて「ゆるい」ソースルーティングを含むようにAX.25仕様を改訂するのが必要でしょう。 厳しいソースルーティングは、あらゆる推進ステージ(callsign)が明らかに申告されるのを必要とします、ゆるいソースルーティングが地元のルーティングエージェントに残されるいくつかかすべてのステージかdigipeaterを許容するでしょうが。 1つの提案はAX.25フレームヘッダーでcallsignに続いて、計算されたルートストリングを挿入するようにWiretap digipeaterに示すことができた特別な集合的なインディケータかcallsignについて工夫するだろうことです。
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.
混雑にはどんなルーティング・アルゴリズムのための特に難しい領域もその検出とreponseにあります。 どう既存のWiretapメカニズムを改良できるかにおけるいくつかのヒントが本書では示されます。 特に隠されたステーション問題に関して、追加仕事が必要です。 恐らくすべての最も役に立つ特徴はラジオから得られたリンク品質指示でしょう、モデムかフレーム・レベル手順(チェックサム失敗)。 多分、時折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.
一般に、ルーティング・アルゴリズムの最も効果的な利用が局部digipeaterサイトにかなりありそうでしょう。 この1つの理由はこれらのステーションが異なった領域をつなげるオフチャンネル中継方式施設を持って、これらの施設を通って広い領域ルーティング情報を交換するかもしれないということです。 そして、直接広い領域サイトで局部Wiretapステーションによって集められたルーティング情報は交換できました。
Mills [Page 13]
工場[13ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
9. References
9. 参照
[1] Forney, G.D., Jr. The Viterbi Algorithm. Proc IEEE 61, 3
(March 1973), 268-278.
[1] フォーニィ、G.D.、Jr.Viterbiアルゴリズム。 Proc IEEE61、3(1973年3月)、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.
[2] マッキラン、J.、I.リシェ、およびE.ローゼン。 アルパネットのための新しいルーティング・アルゴリズムの概観。 Proc。 ACM/IEEE第6データComm。 Symp、11月1979日
[3] Mills, D.L. Exterior Gateway Protocol Formal Specification.
DARPA Network Working Group Report RFC-904, M/A-COM Linkabit,
April 1984.
[3] 工場、D.L.の外のゲートウェイは形式仕様を議定書の中で述べます。 DARPAは1984年4月に1COM Linkabitである状態でワーキンググループレポートRFC-904、M/をネットワークでつなぎます。
[4] Fox, T.L., (Ed.). AX.25 amateur packet-radio link-layer
protocol, Version 2.0. American Radio Relay League, October
1984.
[4]フォックス、T.L.、編。 AX.25のアマチュアパケットラジオリンク層プロトコル、バージョン2.0。 1984年10月のアメリカの無線中継連盟。
Mills [Page 14]
工場[14ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
Appendix A. An Example
付録A.は例です。
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.
例は、候補ノードを考えて、Wiretapがどう第一の、そして、交互のルートを構成するかを例証して、テーブルをリンクするでしょう。 候補テーブルはワシントン(DC)(典型的な24時間の期間の領域)の145.01MHzのAX.25パケットラジオチャンネルにおけるシナリオのモニターしている通常の交通から生じました。 ノードと以下で例証されたリンクテーブルは、組み立てられたデータベースが似ていることに関する考えを与えて、例の基礎を備えます。
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.
図1は各ステーションのためのノードID(NID)、callsign、および関連情報を見せている候補ノードテーブルを例証します。 Route分野は一連の創作ステーション(NID=0)から終点NIDsを除いて、見せられた目的地ステーションまでのNIDsとして幹線道路(最小の距離経路)を含んでいます。 ルートストリングの欠如は、ステーションにdigipeaterの支援なしで直接届いているのを示します。 由来しているステーションがいつもノードテーブルの初記入、この場合W3HCFであり、アルゴリズムが始められる前にデフォルトで初期化されることに注意してください。
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
NID Callsignは最後のRec Wgtが発送するリンクに旗を揚げさせます。------------------------------------------------------- 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
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
20WB2MNF、015、2、04:01:17、180、7、16 21K4NGC、015、3、14:57:44 90、8、22K3SLV、005、2、03:40:01、160、1
Mills [Page 15]
工場[15ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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
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
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
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
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
図1。 候補ノードテーブル
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
予備選挙の総距離のDist分野ショーが発送する上のテーブルでは、リンクス分野は複雑さ要素を示しています、そして、Last Rec分野はステーションが最後に直接か間接的に聞かれたのを時間(ユタ)に示します。(要素はそのノード(プラス1)で付随しているリンクの数です)。 Flags分野は特にどのステーションを見せているか。
Mills [Page 16]
工場[16ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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):
溯源されたフレームとそれらをdigipeatedしたものを持ってください。 8進形式にはあるこの分野のビットは以下の通りinterpetedされます(ビット0は一番右のビットです):
Bit Function
--------------------
0 originating station
1 digipeater station
2 station heard (Last Rec column)
3 station synchronized connection
ビット機能-------------------- 0 由来している1番射台digipeater2番射台ステーションは、3ステーションが接続を同時にさせたと聞きました(最後のRecコラム)。
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.
図1に58のステーションの中に示されているのは、11digipeaters(また、3つを除いたそれのすべてが交通を溯源する)です。 12のステーション以外のすべてが、連動している接続とDPTRID(実際に標識)が持っている由来するのを聞かれなかった1「ステーション」かdigipeat交通だけを溯源するか、またはdigipeatedしました。
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):
図2は集められるようにNIDへのFlagsと各リンクのためのAge情報をNIDに見せている98個のリンクの候補ノードテーブルを例証します。 8進形式にはあるFlags分野のビットは以下の通りinterpetedされます(ビット0は一番右のビットです):
Bit Function
-------------------
0 source
1 digipeated
2 heard
3 synchronized
4 reciprocal
ビット機能------------------- 0 ソース1は2の聞かれた3連動している4逆数をdigipeatedしました。
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
旗は旗の時代まで年をとります。--------------------------- --------------------------- 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]
工場[17ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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
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
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
図2。 候補リンクテーブル
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.
以下のテーブルはいくつかの典型的なシナリオにおける、ルーティング・アルゴリズムの操作を例証します。 テーブルの各線はエントリーが経路リストから抽出されるステップを表します、そして、新しいエントリーは断固としています。 「ステップ」コラムは各ステップに索引をつけますが、“To"コラムはそのステップでステーションのNIDを示します。 "Ptr"コラムは目的地へのpreceedingステップの経路に沿ったインデックスです、「ホップ」と"Dist"コラムはその経路に沿って総ホップカウントと計算された距離を表しますが。
Mills [Page 18]
工場[18ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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.
以下に、目的地ステーションが直接届いていませんが、いくつかの複数のホップ経路が様々なdigipeatersを通して存在するかなり典型的な例があります。 アルゴリズムは4digipeatersを見つけます: 1、5、11、および39。最終以外のそれのすべてが、2つのホップの2つのルートと3つのホップのうち2を発生させるように以下に示されるように由来しているステーションから直接届いています。 完全な経路につながるステップだけが示されることに注意してください。
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
目的地: 29駅: W3CSGステップNID PtrホップDistコメント------------------------------------------------------------- 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の完全な経路: 0 5、29 35、0 2 2の115の完全な経路: 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の完全な経路: 0 1、11 29 63の0の42の3の165の完全な経路: 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.
アルゴリズムはリストで最初に、距離とそして、注文でこれらのルートを格付けします、3ホップのルートがNで支えた第1=63、2ホップのルートがN=4でN=35の2ホップのルートに選ばれて、最終的にNの3ホップのルートが46と等しいように。 第二希望が3ホップのルートであり、3番目が2ホップのルートである理由が極端な混雑のためにdigipeater5番射台にあります。(それは、34個の付随しているリンクを持っています)。
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.
以下に、経路を剪定するメカニズムが探検の範囲を役に立つルートに最も通じそうなそれらの経路に制限するためにどう動作するかを示している例があります。 アルゴリズムは1つの2ホップのルートと4つの3ホップのルートを見つけます。 この例では、あげられた理由でどれがabandondであるかをすべてのステップで含んでいて、全リストは見せられます。
Mills [Page 19]
工場[19ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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
目的地: 13駅: WB2RVXステップNID PtrホップDistコメント------------------------------------------------------------- 0 13 0 0 0 1 7 0 1 30 2 43 0 1 35いいえ経路3 0 1 2 135Complete経路: 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ノー経路9 60 1 2 130いいえ経路
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
10 5 1 2 140マックス距離310 11 1 1 2 130 12 41 1 2 130いいえ経路13 33 1 2 140 14 40 1 2 135 15 5 4 3 210マックス距離380 16、0 4 3 215Complete経路: 0 4 7 13 17 1 4 3 215マックス距離305 18 14 5 3 180マックスホップ4 19 64、5 3、185のマックスホップ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
20 20 6 3 175のマックスホップ4 21 1 7 3 205マックス距離295 22 0 11 3 250Complete経路: 0 1 7 13 23 4 11 3 255マックス距離300 24 12 11 3 255マックス距離295 25 40 11 3 250マックス距離295 26 37 11 3 255マックス距離285 27 46 11 3 255マックス距離285 28 44 11 3 255マックス距離280 29 34 11 3 255マックス距離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
30 6 11 3 250 マックス距離280 31 52 11 3 255マックス距離285 32 28 11 3 255マックス距離295 33 0 13 3 215Complete経路: 0 33 7 13 34の0の14の3の215の完全な経路: 0 40 7 13 35 5 14 3 215マックス距離385 36 1 14 3 210マックス距離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
規制を満たしているのをリンクを全く見つけることができなかったので、「経路がありません」とラベルされたステップはabandondedされます: (a) NIDかNIDから、合っていて、ステップのNID、(b)の輪なしの、または、(c)総経路は以下を遠ざけます。
Mills [Page 20]
工場[20ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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.
256より。 Dist価値の合計と荷重しているノード要素として計算された総距離は示されるように256を超えているでしょう、したがって、「マックス距離」とラベルされたステップはabandondedされます。 総ホップカウントは示されるように最小のホップカウント(プラス1)を超えているでしょう、したがって、「マックスホップ」とラベルされたステップはabandondedされます。
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.
この例はすべての代替経路のための計算を示していますが、総距離が最小の距離(135)をabandondedされることができるより長い状態で幹線道路がすべてのステップで必要でさえある場合、よかったでしょう。 この場合は経路探検は14ステップだけ後に終わります。
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.
以下の例は、典型的なシナリオが以前に未知のステーションにかかわるのを示します。 すなわち、既に中でないののデータが基礎づける1つ。 厳密でなく、離れてください。アルゴリズム自体では、現行制度の戦略はデータベースと目的地ステーションの各digipeaterの間の転嫁された直リンクと共に由来しているステーションと目的地ステーションの間の転嫁された直リンクから成る投機的な経路を発生させることです。 作成された新しいリンクはおよそ15分でキャッシュ管理メカニズムに従ったタイムアウトがそうするでしょう。
In the following example the destination station is 74, which results in the following additions to the link table:
以下の例では、目的地ステーションは74です:(リンクへの以下の追加における結果は74を見送ります)。
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
fm-NIDはNIDにノード種別に旗を揚げさせます。---------------------------------- 0 74 000 1創始者74 000Digipeater5 74 000Digipeater7 74 000Digipeater8 74 000Digipeater11 74 000Digipeater13 74 000Digipeater15 74 000Digipeater16 74 000Digipeater23 74 000Digipeater39 74 000Digipeater44 74 000Digipeater
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.
digipeatersが伴った11があります。そのすべてが使用されるかもしれないというわけではありません。 結果として起こる幹線道路と5個の代替経路が以下で見せられます。 5 11digipeatersだけが使用されていることに注意してください。 残りは、遠過ぎたか、またはあまりにずっしりと充血しました。 完全な経路に通じるリストエントリーだけが示されることに注意してください。
Mills [Page 21]
工場[21ページ]
RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm
実験複数の経路ルーティング・アルゴリズムあたりのRFC981 1986年3月
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
目的地: 74駅: CQステップNID PtrホップDistコメント------------------------------------------------------------- 0 74 0 0 0 1 0 0 1の90の完全な経路: 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の完全な経路: 0 1、74 29、0 4 2の195の完全な経路: 0 7、74 44、0 5 2の150の完全な経路: 0 8、74 45、0 6 2の170の完全な経路: 0 11 74 60の0の10の2の155の完全な経路: 0 23 74
Mills [Page 22]
工場[22ページ]
一覧
スポンサーリンク
