RFC1058 - Routing Information Protocol

この RFC は、ゲートウェイと他のホスト間で、経路情報を交換するためのプロトコルを規定している。これは、インターネット社会でゲートウェイソフトウェアを開発するための基礎として使用されることを意図している。このメモの配布は制限されない。

概要

ここで示されている経路情報プロトコル (RIP: Routing Information Protocol) は、4.3BSD (Barkley Software Distribution) で配布されている "routed" プログラムに大体基づいている。しかし、同じプロトコルを意図した幾つかの他の実装も存在する。不幸にも、これらの様々な実装は、幾つかの詳細な部分において一致していない。この規約は様々な実装から取り出した特徴の組み合わせを表している。このドキュメントに従って設計されたプログラムは、routed や我々が知っている RIP の他の全ての実装と相互接続できると信じている。

注記: このドキュメントは、メトリックが加算される時について大半の既存の実装とは異なる観点を採用している。ローカルネットワークで使用されるメトリックに応じて変更することにより、他の既存の実装と互換性を保った。この問題についての詳細は、セクション3.6 を参照されたし。

1. 導入

このメモは、Bellman-Ford (または距離ベクトル)アルゴリズムに基づく一連のルーティングプロトコルにおける一つのプロトコルを規定している。このアルゴリズムは、ARPANET の初期以来、コンピュータネットワークのルーティングの算出で使用されていた。ここで規定された特定のパケットフォーマットとプロトコルは、UNIX のバークレイに含まれている "routed" プログラムに基づいている。routed は、ゲートウェイやホストの中で経路情報を交換する為のデファクト標準になった。これは、大半の商用ベンダによって、この目的のために実装されている。しかし、これらのベンダは、自身のゲートウェイ内で使用される独自のプロトコルを持っている。

このプロトコルは、"インターネットゲートウェイプロトコル" として最も有効である。現在のインターネットのように、単一のルーティングプロトコルがネットワーク全体で使用されることは稀である。むしろ、ネットワークは "自律システム" の集合体として組織されるだろう。一つの自律システムは通常、単一のエンティティによって管理されている。あるいは、少なくとも技術上や管理上、制御するのに効率的な程度である。各々の自律システムは、独自のルーティング技術を持っている。これは、異なる独自システムのために、異なっているのかもしれない。自律システムの範囲内で使用されるルーティングプロトコルは、内部ゲートウェイプロトコル (IGP: interior gateway protocol) と呼ばれる。それとは別のプロトコルが、自律システム間をインタフェースする為に使用される。その様なプロトコルで最も昔からあり、今でもインターネットで使用されているプロトコルは、EGP (exterior gateway protocol) である。このようなプロトコルは大抵、内部-AS (inter-AS) ルーティングプロトコルと呼ばれる。RIP は、効率的で均等な技術を使用し、適当なサイズのネットワークで動作するよう設計された。従って、速度が広く変化しないシリアル回線を使用した多くの大学や地域ネットワーク用の IGP に適している。RIP は、より複雑な環境で使用されることを意図していない。RIP が何に適切であるかを意図したかのコンテキストの詳細な情報については、Braden and Postel [3] を参照されたい。

RTP は、"距離ベクトルアルゴリズム" として知られたアルゴリズムのクラスの一つである。アルゴリズムのこのクラスの最も古い記述は、Ford and Fulkerson [6] によって書かれたものである。その為、それらは時々 Ford-Fulkerson アルゴリズムとして知られている。Bellman-Ford という用語もまた使用される。これは、この公式が "動的プログラミング" を基礎とした、Bellman's 方程式に基づいているという事実から来る。(この分野への標準的な紹介については、[1] を参照されたし)。このドキュメントのプレゼンテーションは、ほぼ [2] に基づいている。このテキストは、ルーティングアルゴリズムの数学を導入している。また、他の数多くの関連するアルゴリズムだけでなく、ここで提供されているアルゴリズムの幾つかの変形も説明し、正当化している。このプロトコルで記述されている基本的なアルゴリズムは、ARPANET の 1969年と同じ時期にコンピュータルーティングとして使用されていた。しかし、このプロトコルの特定の祖先は、Xerox ネットワークプロトコルの中にある。PUP プロトコル ([4] 参照) は、経路情報の交換のためにゲートウェイ情報プロトコルを使用した。このプロトコルの幾つかの更新版が、経路情報プロトコルという名前で、Xerox ネットワークシステム (XNS: Xerox Network Systems) アーキテクチャで採用された([7] 参照)。バークレイの routed は、大部分において経路情報プロトコルと同じであり、XNS アドレスが、IP や他のタイプのアドレスを扱うより一般的なアドレス形式能力に置き換わり、ルーティングの更新が 30秒に 1回に制限された。この類似性のために、経路情報プロトコル (あるいは単に RIP) という用語は、XNS プロトコルと routed で使用されるプロトコルの両方を呼ぶのに使用される。

RIP は IP ベースのインターネットの中で使用されることを意図している。インターネットは、ゲートウェイで接続された数多くのネットワークの中に組織されている。ネットワークは、ポイントツーポイントかより複雑なネットワーク、例えばイーサネットや ARPANET のどちらかであってもよい。ホストとゲートウェイは、IP データグラムアドレスで幾つかのホストに表される。ルーティングとは、ホストかゲートウェイがどこにデータグラムを送信するかを決定する方法である。もし宛先が、直接ホストかゲートウェイに接続されたネットワークの一つの上にあるならば、その宛先に直接データグラムを送信することが可能である。しかし、興味深いケースは、宛先が直接到達可能な場所にいない時である。この場合、ホストやゲートウェイは、宛先により近いゲートウェイにデータグラムを送信しようと試みる。ルーティングプロトコルの目標は、非常に簡単である。ルーティングに必要な情報を供給することである。

1.1. プロトコルの制限

このプロトコルは、全てのルーティング問題を解決していない。上記で言及しているように、適切なサイズの効率上均等なネットワークにおける IGP として使用することを基本的に意図している。加えて、以下の特定の制限について触れなければならない。

1.2. このドキュメントの構成

このドキュメントの本文は、以下の 2 つのセクションを占める 2 つの部分で構成される。

2) 一般的な距離ベクトルアルゴリズムの、概念的な開発と正当性。
3) 実際のプロトコル規定

これらの各 2 セクションは、大半それ自身で成り立っている。セクション 2 は、アルゴリズムを数学的に補強する為の情報提供を行っている。それは、"スパイラル" 方式に従っている。初歩の、まさに単純なアルゴリズムが説明されている。その後、継続するセクションでその改良が追加されている。セクション 3 は、実際のプロトコル規定である。セクション 2 に向けられた特定の参照を除いて、セクション 3 に記述された規定だけで、完全に RIP を実装できるはずである。

2. 距離ベクトルアルゴリズム

ルーティングとは、送信元から望まれた宛先へのパスを見つける作業である。IP "Catenet モデル" では、これは主にネットワーク間のゲートウェイを見つける問題を減らす。メッセージが単一のネットワークかサブネットに残る限り、あらゆるルーティングの問題がそのネットワークに特定の技術によって解決される。例えば、イーサネットと ARPANET はそれぞれ、全ての送信者が一つのネットワークの中で指定されたあらゆる宛先に話ができる方法を定義している。IP ルーティングは、あるそのようなネットワーク上の送信者から、異なるネットワーク上の宛先にメッセージが行かなければならない時、主に発生する。そのような場合、メッセージはネットワークに接続されているゲートウェイを通過しなければならない。もしネットワークが隣接していなければ、複数の中間ネットワークやそれに接続しているゲートウェイを通過してもよい。一旦、メッセージが宛先と同じネットワーク上にあるゲートウェイに到達したら、宛先に到達させるために、そのネットワーク自身の技術が使用される。

このセクションを通じて、"ネットワーク" という用語は、概して単一のブロードキャストネットワーク (例えばイーサネット) か、ポイントツーポイント回線、ARPANET をカバーする為に使用される。着目すべき点は、ネットワークが IP によって単一のエンティティとして扱われることである。何らルーティングが必要ない (ポイントツーポイント回線等の場合) か、IP に透過的なある方法でルーティングが実行されても、IP が単一の完全に接続されたシステム (イーサネットや ARPANET のように) としてネットワーク全体を扱うことを可能にする。注記: "ネットワーク" という用語は、IP アドレス付けにおいては、多少異なる方法で使用される。単一の IP ネットワーク番号はネットワークの集合に割り当ててもよく、"サブネット" のアドレス付けは個々のネットワークを示すのに使用される。実際に、サブネットのアドレス付けが使用される場合はサブネットを参照するのに "ネットワーク" という用語を使用している。

ネットワーク間の経路を見つけるためのアプローチは数多く存在する。これらのアプローチをカテコライズするひとつの効果的な方法は、ゲートウェイが経路を見つけるために交換が必要な情報のタイプに基づくことである。距離ベクトルアルゴリズムは、少量の情報のみの交換に基づいている。ルーティングプロトコルに参加している各々のエンティティ(ゲートウェイやホスト)は、システム内の宛先全てに関する情報を保持しているものと想定する。通常、一つのネットワークに接続された全てのエンティティについての情報は、単一のエンティティによって要約され、それはそのネットワーク上の全ての宛先への経路を示す。IP に関する限りネットワーク内のルーティングは見えないので、この要約が可能である。この経路データベース中の各々のエントリは、そのエンティティ宛てのデータグラムが送信される次のゲートウェイを含んでいる。加えてこのエントリは、エンティティへの総距離を計測した "メトリック" を含む。この距離は、ある程度一般的なコンセプトであり、メッセージがエンティティに到達する際の遅延時間や、メッセージを送信する為のドル立てのコスト等をカバーしてもよい。距離ベクトルアルゴリズムは、交換される唯一の情報がこれらの距離のリストである時、最適な経路を算出することが可能であるという事実からその名前を得ている。さらに情報は隣接するエンティティ内、すなわち共通のネットワークを共有するエンティティ内で交換されるだけである。

ルーティングは、大部分において共通してネットワークに関する情報に基づくが、個々のホストへの経路の足跡を保持することが時々必要になる。RIP プロトコルは、ネットワークとホストを形式的に区別しない。RIP は、ネットワークかホストのどちらでもよい単に宛先に関する情報の交換を規定する。(しかし、実装者がホスト経路をサポートしないよう選択することは可能である。セクション3.2 参照)事実、数学上の発展は、あるホストやゲートウェイから別のホストやゲートウェイへの経路に関して最も都合よく考えられる。そのアルゴリズムを抽象的な言葉で論じる時、ネットワークの経路エントリを、そのネットワークに接続されたエンティティの全ての経路エントリの略称として考えることは最も良い。この種の略称は、ネットワークを IP レベルで目に見える内部構造を持たないものとして考えているからこそ、意味をなす。従って、与えられたネットワークの全てのエンティティに対しては、同一の距離を通常割り当てる。

上記で、各エンティティは、一つのエントリにつきシステムにおいて全てのあり得る宛先をもつ経路データベースを持つと述べた。実際の実装では、各宛先に関する以下の情報を保持する必要がありそうである。

加えて、様々なフラグや他の内部情報が、恐らく含まれるだろう。このデータベースは、システムに直接接続されているエンティティの記述で初期化される。そしてこれは、隣接するゲートウェイから受信したメッセージの情報に従って更新される。

ホストとゲートウェイ間で交換される最も重要な情報は、更新メッセージで運ばれるものである。ルーティングに参加している各々のエンティティは、現在そのエンティティに存在する経路データベースを記した更新メッセージを送信する。隣接するエンティティから得られる情報だけを使用して、システム全体の最適な経路を維持することは可能である。そこで使用されるアルゴリズムについては、次のセクションで説明されている。

上記で言及したように、ルーティングの目的は、データグラムを最終の宛先に到達させる方法を見つけることである。距離ベクトルアルゴリズムは、システムにおける全ての宛先への最善経路を持つテーブルに基づいている。勿論、どの経路が最善かを定義する為に、善さを測る何らかの方法を持たなければならない。これが、"メトリック" と呼ばれるものである。

単純なネットワークでは、いくつのゲートウェイを通過しなければならないかを単に数えただけのメトリックを使用することが普通である。より複雑なネットワークでは、メトリックはメッセージが被る遅延総数、送信コスト、最小化してもよい量を表す為に選択される。主要な要件は、メトリックを個々のホップにかかる "コスト" の合計として表すことが可能でなければならないということである。

形式的に、もしエンティティ i からエンティティ j まで直接得ることができるならば (例えば、別のゲートウェイを通過しない等)、そのコスト d(i,j) は、i と j 間のホップと関連付けられる。ネットワーク上の全てのエンティティは同一と通常見なされる場合、d(i,j) は、与えられたネットワーク上の全ての宛先と同値であり、ネットワークを使用するコストを表す。完全な経路のメトリックを取得するには、経路を示す個々のホップのコストを単純にカウントアップする。このメモの目的では、コストは正の整数値であると仮定する。

D(i,j) は、エンティティ i からエンティティ j までの最善経路のメトリックを表すものとする。これは、エンティティの全てのペアを定義しなければならない。d(i,j) は個々のステップのコストを表す。形式的に、d(i,j) はエンティティ i からエンティティ j まで直接行く際のコストを表すものとする。もし i と j が直接隣接していないならば、それは固定ではない。(d(i,i) は固定ではないことに注意されたい。すなわち、ノードから自身への直接のコネクションが存在すると考えない)。コストは加算されるので、最善のメトリックは以下のように示さなければならないことを示すのは容易である。

最善経路は、i から d(i,k)+D(k,j) が最小値を持つような隣接する k に行くことによって始まる。(これらは、経路におけるステップ数の帰納法によって表すことができる)。二番目の式は、i の直接の隣接者である k に制限できることに注意されたい。その他の場合、d(i,k) は無限であり、それを含む間は最小では有り得ない。

メトリックをこれに基づく単純なアルゴリズムによって算出できることは明白である。エンティティ i は、宛先 j までの距離見積もりを隣接者 k に送信させる。i が k から見積もりを取得したら、i は各々の数に d(i,k) を追加する。これは、単に i と k 間のネットワークを横切るコストである。そして、i は全隣接者から取得した値を比較し、最も小さい値を抽出する。

このアルゴリズムは将来トポロジの変更が無ければ、D(i,j) の正しい見積もりに収束するだろうということが、[2] で証明されている。著者は、エンティティがお互いに情報を送信する順番や、分を再計算する時についてはほとんど仮定していない。基本的には、エンティティは更新情報の送信やメトリックの再計算を停止することはできず、ネットワークはメッセージを永久に遅延させることは出来ない。(ルーティングエンティティの破壊は、トポロジーの変更である)。また、その証明は非否定でなければならないことを除いて、D(i,j) の初期見積もりについて仮定していない。これらのかなり弱い仮定は十分に適切であるという事実は重要である。いつ更新情報を送信するかについて仮定する必要が無いので、そのアルゴリズムを非同期に動作させることが安全に行える。すなわち、各々のエンティティは、自分自身のクロックに従って更新情報を送信することができる。更新情報は全て落ちない限り、ネットワークによって落ちてもよい。開始状態について仮定する必要が無いので、そのアルゴリズムが変更を扱うことができる。システムが変更された時、ルーティングアルゴリズムは新しい均衡に向けて移行し始め、古いものは開始点として使用される。開始点が何であれ、アルゴリズムが有限の時間に収束することは重要である。さもなくば、ある種の変更が非収束的な振る舞いを導くかもしれない。

上記に記述されたアルゴリズムの言明 (とその証明) は、各々のエンティティが各隣接者から来た見積もりのコピーを保持し、時々隣接者の全ての最小値を得るものと仮定している。実際は、真の実装体ではそれをする必要はない。それらは単に、これまで見られた最善のメトリックと送信した隣接者のアイデンティティを覚えているだけである。そして、より良い (より小さい) メトリックを見つける度に、この情報を置き換える。それにより、全隣接者からのデータを格納せずに、最初値を徐々に計算することが可能である。

テキストで記述されたアルゴリズムと、RIP のようなプロトコルで実際に使用されているアルゴリズムとの間には、もう一つ別の相違がある。上記の説明は、0 の距離を示す自分自身のエンティティを含む各々のエンティティを持つ。実際は、これは通常なされない。ネットワーク上の全てのエンティティは通常、ネットワークの単一のエントリによって要約されることを思い起こしてほしい。ネットワーク A に接続されているホストかゲートウェイ G の状態を考慮する。C はネットワーク A を使用するコストを表す (通常はメトリック 1)。(ネットワークの内部構造は IP には見えず、従ってネットワーク A 上の二つのエンティティ間を行くコストは同じであることを思い起こしてほしい)。原理的には、G はネットワーク A 上の他の全てのエンティティ H からメッセージを取得すべきであり、0 のコストは自分自身へのエントリからの取得を表す。そして、G は H までの距離として C + 0 を計算するだろう。G はこれらの個々のメッセージを全てチェックせずに、テーブルにネットワーク A に対するエントリを作成し、それに C のメトリックを割り当てることによって単に開始すればよい。ネットワーク A に対するこのエントリは、ネットワーク A 上の他の全てのエンティティを要約していると考えるべきである。ネットワーク A 上の共通のエントリで要約できない唯一のエンティティは、G 自身である。というのは、G から G まで行くコストは C ではなく 0 だからである。しかし、0 エントリは必要ないので、単にネットワーク A の単一のエントリに安全に従うことができる。この戦略のもう一つの意味についての注記: 0 エントリを使用する必要はないので、ゲートウェイとして機能しないホストは、更新メッセージを送信する必要はない。明確にゲートウェイとして機能しないホスト (すなわち、一つのネットワークにしか接続されていないホスト) は、、自身のエントリ D(i,i)=0 以外に提供する有効な情報を持っていない。それらは一つのインタフェースしか持たないので、そのインタフェースを通った他のネットワークへの経路はそのインタフェースに単に行って、そこからすぐに戻るだけであると見ることは容易である。従って、そのような経路のコストは少なくとも C による最善のコストよりも大きいだろう。0 エントリは必要としないので、非ゲートウェイはルーティングプロトコルに全く参加する必要が無い。

ホストやゲートウェイ G が行うことを要約しよう。システムにおける各々の宛先に対して、G はその宛先に対するメトリックの現在の見積もり (すなわち、そこに至る全体のコスト) と、そのメトリックが基づくデータを持った隣接するゲートウェイの識別子を保持する。もし宛先が G に直接接続されているネットワーク上にあるならば、G はネットワークを使用するコストを示すエントリと、その宛先に達するのに何のゲートウェイも必要ないという事実を単に使用するだけである。一旦計算が正しいメトリックに収束したら、この技術によって記録された隣接者は、実際宛先までのバス上の一番最初のゲートウェイであることを示すことは容易である。(もし複数の適切なパスが存在するならば、それらのうちの一つが一番最初のゲートウェイである)。宛先、メトリック、ゲートウェイのこの結合は、そのゲートウェイを使用した、そのメトリックを持った宛先までの経路として通常参照される。

既存のメトリックはより小さい値が表れるまで保持され、メトリックを下げる方法はそれしかない。初期見積もりが小さ過ぎることも有り得る。従って、メトリックを上げる方法も存在しなければならない。次の規則を適用すれば十分であることが分かる: 宛先までの現在の経路がメトリック D を持ち、ゲートウェイ G を使用するものとする仮定する。G 以外の別の送信元から新しい情報のセットが到着したら、もし新しいメトリックが D よりも良いならばその経路を更新するだけである。しかし、もし G 自身から新しい情報のセットが到着したら、必ず D を新しい値に更新する。この規則で、逐次的な更新処理は、全ての隣接者からの最新の情報を記憶し、明確な最小値を割り出す計算と同じ経路を生成することを示すことは容易である。(これまでの議論では、ネットワークの構成が静的であると仮定していることに注意されたい。それは、システムが失敗する可能性を考慮していない)。

要約すると、それまで発展してきた基本的な距離ベクトルアルゴリズムがここにある。(注: これは RIP プロトコルの言明ではない。まだ追加すべき幾つかの改善がある)。ルーティングプロトコルに参加する全てのエンティティによって、以下の手続きが実現される。これは、システムの全てのゲートウェイを含まなければならない。ゲートウェイではないホストもまた参加してよい。

2.1. トポロジの変更の取り扱い

上記の議論は、ネットワークのトポロジが固定であることを仮定している。実際は、ゲートウェイや回線はしばしば異常がおき、そして復旧する。この可能性を扱うために、若干アルゴリズムを修正する必要がある。アルゴリズムの理論上の版は、直接の隣接者全ての最小値を含んでいた。もしトポロジが変わったら、隣接者のセットが変わる。従って次のタイミングで計算が行われ、その変更が反映される。しかし上述したように、実際の実装体は最小値の算出で逐次的な版を使用する。与えられた宛先の最善の経路しか覚えていないのである。もしその経路に含まれたゲートウェイがクラッシュしているか、そこへのネットワークコネクションが切断されていたら、その計算は決して変更を反映しないだろう。これまで示されていたアルゴリズムは、メトリックが変わったか否かを隣接者に通知するゲートウェイに依存している。もしそのゲートウェイがクラッシュしたら、変更を隣接者に通知する方法が無いのである。

この種の問題を扱うために、距離ベクトルプロトコルはタイムアウトの経路に対する準備を施さなければならない。その詳細は、特定のプロトコルに依存している。例えば、RIP ではルーティングに参加する全てのゲートウェイは、30 秒毎に更新メッセージを全ての隣接者に送信する。ネットワーク N の現在の経路がゲートウェイ G を使用するとする。もし G から180 秒間何も受信しないならば、そのゲートウェイがクラッシュしたか、そこに接続しているネットワークが利用できなくなったと想定する。よって、その経路は無効であるとマークする。別の隣接者から有効なNまでの経路を受信した時、有効な経路が無効な経路に置き換わる。各隣接者から 30 秒毎に受信することを期待していても、経路のタイムアウトまで 180 秒間待つことに注意されたい。不幸にも、メッセージは時々ネットワークによって欠損する。従って、単一のメッセージの失敗で経路を無効化することは、おそらく適切な考えではないだろう。

以下で述べるが、あるネットワークへの有効な経路が現在存在しないことを隣接者に通知する方法があると便利である。RIP は、このクラスの他の幾つかのプロトコルと一緒に、通常の更新メッセージを通じて、そのネットワークは到達不能とマークすることによってこれを実施する。特定のメトリック値は、到達不能な宛先を示すために選択される。そのメトリック値は、期待されるメトリックの最大値よりも大きい値である。既存の RIP の実装体では、16 が使用されている。メトリックの最大値よりも大きいので、この値は通常 "無限" と呼ばれる。16 は驚くほど小さい数に見えるかもしれない。これから述べる理由により、この小さい値が選択される。大半の実装体では、経路が無効であるとマークするために、同じ慣習が内部で使用されている。

2.2. 不安定性の防止

これまで述べられてきたアルゴリズムは、ホストかゲートウェイが常に正しいルーティングテーブルを計算するのを可能にする。しかし、実際に便利にするにはまだ極めて不十分である。上記で参照されている証明は、ルーティングテーブルは有限の時間で正しい値に収束するだろうということを示しているにすぎない。この時間が、十分便利であるほど小さいことを保証していないし、アクセス不能になったネットワークのメトリックに何が起きるか言及していない。

アクセス不能になった経路を扱うために、算数を拡張することは十分に容易である。上記で提案された慣習はそれをするだろう。我々は、"無限" を表すために大きなメトリック値を使うことを選択する。この値は、実際のメトリックがかつてそこまで大きくなったことは無いくらい十分に大きい。これを例示するために、値 16 を使うことにする。ネットワークがアクセス不能になったと仮定する。直接隣接している全てのゲートウェイはタイムアウトとなり、そのネットワークのメトリックに 16 を設定する。分析するために、全ての隣接しているゲートウェイが、16 のコストを持つ消滅したネットワークに直接接続するハードウェアの新しい部品を持ったと仮定できる。それは消滅したネットワークへの唯一のコネクションなので、システム中の他の全てのゲートウェイは、それらのゲートウェイのうちの一つを通じて行く新しい経路に収束するだろう。一旦収束が起きたら、全てのゲートウェイは消滅したネットワークに対して少なくとも 16 のメトリックを持つだろうと見ることは容易である。元の隣接者から 1 ホップ離れたゲートウェイは、少なくとも 17 のメトリックで終了し、2 ホップ離れたゲートウェイは少なくとも 18 で終了するだろう。これらのメトリックは最大のメトリック値よりも大きいので、それらは皆 16 に設定する。システムが全てのゲートウェイで、消滅したネットワークに対して 16 のメトリックに新たに収束することは明白である。

不幸にも、収束するのにどのくらい時間がかかるかという質問は、ごく簡単な答えを得られていない。先に進む前に、例を見ることは有効だろう([2]から抜粋)。ところで、ここで示そうとしているものは、正しい RIP の実装体では起らないだろうということに注意されたい。ある特徴が必要とされる理由を示そうとしているのである。文字がゲートウェイに該当し、線がネットワークに該当する。

A-----B                           
 \   / \                          
  \ /  |                          
   C  /                           
   | /                            
   |/                             
   D                              
   |<=== ターゲットネットワーク

C から D に直接接続されているネットワークがコスト10を持つのを除いて、他の全てのネットワークはコスト 1 を持つ。

各ゲートウェイは、各ネットワークへの経路を示すテーブルを持つ。

しかし、この図の目的では、各々のゲートウェイから図の下部にマークされたネットワークまでの経路のみを示す。

D:　直接接続されており、メトリック 1
B:　D を経由し、メトリック 2
C:　B を経由し、メトリック 3
A:　B を経由し、メトリック 3

B から D までの線が故障したと仮定する。経路は、C から D の線を使用するよう補正しなければならない。不幸にも、これを行うにはしばらく時間がかかる。B が D までの経路がもう利用できないことに気づいた時、ルーティングの変更が始まる。簡単にするために、以下のチャートでは、全てのゲートウェイは更新情報を同じ時間に送信するものと仮定する。そのチャートは、各々のゲートウェイのルーティングテーブルに表れる、ターゲットネットワークに対するメトリックを示している。

ここに問題がある。B はタイムアウトメカニズムを使用して、故障した経路を取り除くことができる。しかし、その痕跡はしばらくの間システム中に残り続ける。最初、A と C は、D まで B 経由で行けるとまだ思っている。よって、A と C は 3 のメトリックをリスト化した更新情報を送信する。次の繰り返しで、B は A か C のいずれかを使用して D に到着することができると主張する。もちろんそれはできない。A と C によって主張されていた経路は、現在無くなっている。しかし、まだそのことを認識する方法が無い。B を経由した経路が無くなったことを発見したときでさえ、その他を経由した利用可能な経路が存在すると各々が思っている。最終的には、全ての算数がしなければならないと主張した時にシステムは収束する。しかし、そうなるまである程度時間がかかり得る。最悪のケースは、ネットワークがシステムのある部分から完全にアクセス不能になる時である。その場合、それらが最終的に無限に達するまで、メトリックは上記のようなパターンでゆっくりと加算される。この理由から、その問題は "無限まで継続" と呼ばれる。

なぜ "無限" に可能な限り小さい値が選択されるのか理解できるはずである。もしネットワークが完全にアクセス不能になったら、可能な限り早く止まるよう無限値まで数えたいのである。無限値は、実際の経路がそこまで大きくない程十分大きくなければならない。しかし、必要以上に大きくなるべきではない。従って無限値の選択は、ネットワークサイズと無限値まで数えることが起きた場合の収束速度とのトレードオフである。RIP の設計者は、このプロトコルは直径 15 以上の大きさのネットワークでは実践的ではなさそうであると信じていた。

この様な問題を避けるために行えることはいくつかある。RIP で使用されているものは、"有毒な逆を持つ水平分割 (split horizon with poisoned reverse)" と "トリガ更新 (triggered updates)" である。

2.2.1. 水平分割

上記の問題の幾つかは、A と C が相互に虚偽のパターンで結びついているという事実に起因していることに注意されたい。各々が、一方を経由して D に到達することができると主張している。これは、どこの情報が送信されたかについて少し注意深くなることで避けることができる。特に、経路情報を教わった隣接者への宛先ネットワークへの到達性を主張することは有効ではない。"水平分割" は、教わったゲートウェイに送信する更新情報の中に、経路を含むことに起因する問題を避けるための方策である。"単純水平分割" の方策は、その隣接者に送信する更新情報の中にある一つの隣接者から、教わった経路を省略する。"有毒な逆を持つ水平分割" はそのような経路を更新情報の中に含むが、そのメトリックを無限に設定する。

もし A が C を経由して D に到達できると思っていたら、C へのそのメッセージは D は到達不可であると示すべきである。もし C を通る経路が真実であれば、C は D に直接接続されているか、ある別のゲートウェイを通じて接続されているかのいずれかである。ループを形成してしまうため、C の経路は恐らく A に戻れない。D が到達不能であるとCに告げることによって、C が混乱して、A を通じた経路が存在すると信じるかもしれない可能性を簡単に防ぐことができる。これは、ポイントツーポイント回線でも明白である。しかし、A と C がイーサネットのようなブロードキャストネットワーク接続され、そのネットワーク上に別のゲートウェイが存在する可能性を考慮されたい。もし A が C を通じた経路を持っているならば、A はそのネットワーク上にある別のゲートウェイと話をする時、D が到達不可であることを示すべきである。そのネットワーク上の他のゲートウェイは、C 自身に到達しえる。それらは、A を経由して C に到達する必要は決してない。もし A の最善経路が実際にCを通るならば、そのネットワーク上の他のゲートウェイは、A が D に到達できることを知る必要が無い。C のために使用された同じ更新メッセージが、同じネットワーク上の他の全てのゲートウェイでも使用できることを意味するので、これは幸いである。従って、更新メッセージはブロードキャストによって送信できる。

通常、有毒な逆を持つ水平分割は単純な水平分割よりも安全である。もし二つのゲートウェイがお互いを指している経路を持っていたら、16 のメトリックを持つ逆の経路を伝播すると、即座にループを壊すだろう。もし逆の経路が単に伝播されなければ、異常な経路はタイムアウトを待って除去されなければならない。数多くのことなる建物に接続されているキャンパスバックボーンのケースについて考慮してみる。各々の建物には、バックボーンをローカルネットワークに接続するゲートウェイが存在する。バックボーンネットワーク上でゲートウェイがブロードキャストすべきルーティング更新情報が何かを考慮されたい。残りのネットワークが各々のゲートウェイについて知る必要があるものは、そのゲートウェイが接続されているローカルネットワークが何かである。単純な水平分割を使用すると、バックボーンネットワークへの経路のみが、ゲートウェイによって送信される更新メッセージの中に現われる。もし有毒な逆を持つ水平分割が使用されたら、ゲートウェイはバックボーンから教わった全ての経路を、メトリック 16 として言及しなければならない。もしシステムが大規模ならば、これはほとんど全てのエントリが到達不可を示す大きな更新メッセージを結果として生じ得る。

静的な方法では、メトリック 16 を持つ逆経路を伝播することは、何の付加情報も提供しない。一つのブロードキャストネットワーク上に多くのゲートウェイが存在するならば、これらの余分なエントリは重要な帯域を使用し得る。その理由は動的な振る舞いを改善することである。トポロジが変わったとき、ゲートウェイを通過すべき経路だけでなく、通過すべきでない経路について言及することにより、収束速度を速めることができる。しかしある状況では、ルーティングのオーバヘットを最小化するために、ネットワーク管理者がより遅い収束を望むかもしれない。従って、実装体は有毒な逆を持つ水平分割ではなく、単純な水平分割をオプションで実装してもよい。あるいは、ネットワーク管理者がどの動作を使用するかを選択できる構成オプションを提供してもよい。ある逆経路は 16 のメトリックを持ち、その他は省略するという混成スキームを実装することも許される。そうしたスキームの例として、それらを巻き込むルーティングの変更後、ある時間の間は逆経路に対して 16 のメトリックを使用し、その後で更新情報からそれを省略するという方法がある。

2.2.2. トリガ更新

有毒な逆を持つ水平分割は、二つのゲートウェイだけを巻き込むルーティングループを防ぐだろう。しかし、三つのゲートウェイが相互の虚偽で結びつくパターンで起きることは依然として有り得る。例えば、A は B を通じた経路、C を通じた B、A を通じた C の経路があると信じるかもしれない。水平分割は、そのようなループを停止することができない。このループは、メトリックが無限に達して、巻き込まれたネットワークが到達不可と宣言された時にのみ解決できる。トリガ更新は、この収束を早めるための試みである。トリガ更新を取得するために、ゲートウェイが経路に対するメトリックを変更する場合は必ず、たとえ規則的な更新メッセージの送信時間に達していなくても、ほとんど直ぐに更新メッセージを送信する必要があるという規則を単に追加する。(そのタイミングの詳細はプロトコル毎に異なるだろう。RIP を含む幾つかの距離ベクトルアルゴリズムは、トリガ更新が極端なネットワークトラフィックを生み出すのを避けるために小さい遅延時間を規定する)。これが、どのように新しいメトリックを算出するための規則と結合するかに注意されたい。宛先 N までのゲートウェイの経路がゲートウェイ G を通過すると仮定する。もし更新情報が G 自身から到着したら、その新しいメトリックが古いものより高くあれ低くあれ、受信側のゲートウェイはその新しい情報を信じる必要がある。その結果、もしメトリックが変更されたら、受信側ゲートウェイは自分に接続されている全てのホストやゲートウェイにトリガ更新を送信するだろう。代わってそれらは、各々お互いに自分の隣接者に更新情報を送信するだろう。その結果はトリガ更新のカスケードである。どのホストやゲートウェイが、そのカスケードに巻き込まれているかを示すことは容易である。ゲートウェイ G が宛先 N までの経路をタイムアウトすると仮定する。G は自分の隣接者全てにトリガ更新を送信する。しかし、新しい情報を信じる唯一の隣接者は、N までの経路が G を通過するゲートウェイである。他のゲートウェイやホストは、既に使用している経路よりも悪い新しい経路についての情報としてこれを見て、無視するだろう。その経路がGを通過する隣接者はそのメトリックを更新し、自分の隣接者全てにトリガ更新を送信する。また、その経路はそれらを通過する隣接者のみが注意を払う。従って、トリガ更新はメトリックを無限に更新しながら、ゲートウェイ G につながる全てのパスに沿って後方に波及する。この波及は、宛先 N までの経路として別のパスを採用するネットワークの部分に到達すると止まるだろう。

もし、トリガ更新のカスケードが起きる間、システムが黙っていられたら、無限値まで数えることは起きないことを証明することは可能である。悪い経路は必ず即座に削除されるので、ルーティングループは形成されないのである。

不幸にも、物事はそう上手くいかない。トリガ更新が送信される間、規則的な更新情報が同時に送信されるかもしれない。トリガ更新をまだ受信していないゲートウェイは、もはや存在しない経路に基づく情報をまだ送出しているかもしれない。トリガ更新がゲートウェイを通過した後、まだ一言かけられていないこれらのゲートウェイの一つから通常の更新情報を受信することは有り得る。これは、欠陥のある経路の残存を再確立し得る。もしトリガ更新が十分素早く行われたら、これは極めて起こりにくい。しかし、無限まで数えることは依然として起こり得る。

3. プロトコル規定

RIP は、ホストとゲートウェイが IP ベースのネットワークを通じた経路を算出する為の情報の交換を可能とすることを意図している。RIP は距離ベクトルプロトコルである。従って、それはセクション 2 で説明している一般的な特徴を持っている。RIP は、ホストとゲートウェイの両方で実装されるかもしれない。大半の IP のドキュメントにある様に、"ホスト" という言葉はそのどちらかをカバーする為に使用される。それは個々のホストか又はネットワーク、あるいはデフォルトの経路を運ぶ為に使用される特定の宛先かもしれない。

RIP を使用するホストは、一つ以上のネットワークへのインタフェースを持つことが想定される。これらは "直接接続されたネットワーク" として参照される。プロトコルは、これらのネットワークの各々に関するある情報へのアクセスに頼る。最も重要な点はメトリック、又は "コスト" である。ネットワークのメトリックは 1 ～ 15 の間の整数である。これは、このプロトコルで規定されない方法で設定される。最も普及している実装では、常にメトリックとして 1 の値を使用している。新たに作成する実装は、システム管理者が各々のネットワークのコストを設定できる様にしなければならない。コストに加えて、各々のネットワークは IP のネットワーク番号と、それに割り当てられたサブネットマスクを持つ。これらはシステム管理者により、このプロトコルで規定されない方法で設定される。

注記: 3.2 節で規定された規則は、各々の IP ネットワークに適用される単一のサブネットマスクが存在し、直接接続されたネットワークの為のサブネットマスクだけが認識されているものと想定している。単一ネットワークの範囲内で、異なるサブネットで異なるサブネットマスクを使用するシステムが存在するかもしれない。システムが遠隔ネットワークのサブネットマスクを知ることを望むインスタンス (実体) もまた存在するかもしれない。しかし、そのような状況はサブネット情報の広がりを統治する規則の修正を必要とするだろう。その様な修正は相互接続性の問題を起こすので、プロトコルを修正するよう検討しなければならない。

RIP を実装する各ホストは、経路テーブルを持つと想定される。このテーブルは、RIP で示されたシステムを経由して到達可能な全ての宛先の為の一個のエントリを持つ。各エントリは、少なくとも以下の情報を含む。

直接接続されたネットワークのエントリは、このプロトコルで規定されていない手段によって増やされる情報を使用して、ホストによって設定される。既存の RIP 実装は、コストとして 1 が常に使用される。その場合、RIP メトリックは単純にホップ数に減らされる。より複雑なメトリックは、例えば帯域や信頼性の為に、あるネットワークの優先度を示すことが望まれる時使用してもよい。

実装者は、システム管理者が追加経路を入力できることを選択してもよい。これらは、ルーティングシステムのスコープ外のホストかネットワークへの経路に最もありえる。

これらの初期の宛先以外の宛先エントリは、以下の節で説明されているアルゴリズムによって追加、または更新される。

完全な経路情報を提供するプロトコルの為に、システム中の全てのゲートウェイがそこに参加しなければならない。ゲートウェイではないホストは参加する必要がないが、多くの実装は経路テーブルの維持を可能にする為に、経路情報をリッスンする準備を行う。

3.1. メッセージ形式

RIP は UDP ベースのプロトコルである。RIP を使用する各ホストは、UDP ポート番号 520 上でデータグラムを送受信するルーティングプロセスを持つ。別のホストの RIP プロセッサに接続された全ての通信は、ポート 520 に送信される。全ての経路更新メッセージはポート 520 から送信される。望まれれない経路更新メッセージは、520 の送信元と宛先ポートを持つ。要求に対する応答として送信されるこれらの情報は、要求が来たポートに送信される。特定のキュエリとデバッグ要求は、520 以外のポートから送信してもよいが、ターゲットマシンの 520 のポートに向けられる。

プロトコルでは、"黙った" RIP プロセスを可能にする為の規定がある。黙ったプロセスは、通常何のメッセージも送出しない。しかし、他者によって送信されるメッセージを監視している。黙った RIP は、ゲートウェイとしては動作しないが、自側のゲートウェイを監視し、内部の経路テーブルを更新し続ける為に経路情報をリッスンしたいホストが使用してもよい。(ホストがネットワークトポロジの経路を保持できる様々な方法についての議論は、[5] を参照されたし)。全てとの接続を失ったがそのネットワークの一つであるゲートウェイは、効果としてはもうゲートウェイではないので黙ることを選択してもよい。

しかし、もし隣りのゲートウェイが障害のあるネットワークの復旧を検出する為のメッセージに従う機会があるなら、これはしてはならない。(4BSD routed プログラムは、ポイントツウポイントリンクの処理を監視する為に経路パケットを使用する)。

ネットワーク情報を含んでいるデータグラムの形式。フィールド長は、オクテット単位で付与される。もし他に指定されていなければ、フィールドはバイナリ整数を含み、最上位オクテットが最初に来るという通常のインターネットオーダである。各チックマークは、1 ビットを表わしている。

 0                   1                   2                   3 3 
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| command (1)   | version (1)   |      must be zero (2)         |
+---------------+---------------+-------------------------------+
| address family identifier (2) |      must be zero (2)         |
+-------------------------------+-------------------------------+
|                         IP address (4)                        |
+---------------------------------------------------------------+
|                        must be zero (4)                       |
+---------------------------------------------------------------+
|                        must be zero (4)                       |
+---------------------------------------------------------------+
|                          metric (4)                           |
+---------------------------------------------------------------+
                                .                                
                                .                                
                                .                                

Figure 1. Packet format

アドレスファミリ識別子からメトリックまでのデータグラムの部分は、最大 25 回表れてよい。IP アドレスは通常 4 オクテットのインターネットアドレスで、ネットワークオーダである。

全てのデータグラムはコマンド、バージョン番号、可能なアーギュメントを含む。このドキュメントはプロトコルのバージョン 1 について記述している。バージョン番号の処理の詳細は、3.4 節で説明している。コマンドフィールドは、このデータグラムの目的を指定する為に使用される。以下は、バージョン 1 で実装されるコマンドの詳細である。

1 - request
経路テーブルの全て又は一部を送信してほしいという、応答側システムに対する要求

2 - response
送信側の経路テーブルの全て又は一部を含んでいるメッセージ。このメッセージは要求、又はポーリングの応答として送信されるかもしれないし、送信者によって生成された更新メッセージであるかもしれない。

3 - traceon
廃止された。このコマンドを含むメッセージは無視される。

4 - traceoff
廃止された。このコマンドを含むメッセージは無視される。

5 - reserved
この値は Sun Microsystems によって使用されている。もし以降の版で新しいコマンドが追加されたら、コマンド番号は 6 から開始されなければならない。このコマンドを含むメッセージは、これに応答することを選択していない実装によって安全に無視される。

要求と応答に関し、データグラムの残りはそれぞれの情報を持つ宛先のリストを含む。このリスト中の各々のエントリは、宛先ネットワークかホスト、それに対するメトリックを含む。パケット形式は、複数の異なるプロトコルの為の RIP を運べるよう意図されている。従って、各々のエントリはそのエントリで何のタイプのアドレスが指定されているかを示す為に、アドレスファミリ識別子を含む。このドキュメントは、インターネットネットワークのルーティングについてのみ記述している。 IP のアドレスファミリ識別子は 2 である。他のタイプのアドレスの実装に利用可能な RIP 実装はない。しかし、将来の実装の為に、実装はサポートしていないアドレスファミリを指定しているエントリをスキップすることが要求される。(これらのエントリのサイズは、IP アドレスを指定しているエントリのサイズと同じである)。未サポートのエントリをスキップした後、普通にメッセージの処理が続く。IP アドレスは、ネットワークオーダで4オクテットで格納された通常のインターネットアドレスである。メトリックフィールドは、宛先に対する現在のメトリックを示す 1～15 までの値か、宛先が到達不可であることを示す値 16 を含まなければならない。ゲートウェイによって送信される各々の経路は、前の経路を同じゲートウェイからの同じ宛先に上書きする。

データグラムの最大長は 512 オクテットである。これは、上記に記述された部分のみを含む。IP か UDP ヘッダはカウントしない。ネットワーク情報を伴うコマンドは、情報を複数のデータグラムに分割することを可能にする。もしデータグラムが個々に処理されたら正しい結果が発生するので、継続するのに特別な用意は必要でない。

3.2. アドレス付けの考慮

セクション2 で示されているように、距離ベクトルルーティングは個々のホストかネットワークへの経路を示すのに使用できる。RIP プロトコルは、これらの可能性のいずれかを可能にする。要求と応答メッセージに表れる宛先は、ネットワーク、ホスト、デフォルトアドレスを示すために使用される特殊なコードである。通常、実際に使用される経路の種類は、特定のネットワークで使用されるルーティング方式に依存する。多くのネットワークは、個々のホストのための経路情報が必要無いようセットアップされている。もし、与えられたネットワークかサブネット上の全てのホストが同じゲートウェイを通じてアクセス可能ならば、ルーティングテーブル中の個々のホストについて言及する理由はない。しかし、ポイントツーポイント回線を含むネットワークは、あるホストへの経路の足跡を保持するために、時々ゲートウェイを必要とする。従って、幾つかの実装体はホスト経路をサポートしないことを選択してもよい。もしホスト経路がサポートされていなければ、応答メッセージで受信した時、それらは落される (セクション3.4.2 参照)。

RIPパケット形式は、様々なアドレスのタイプを区別しない。"アドレス" とラベルが付けられたフィールドは、以下を含む。

　　ホストアドレス
　　サブネット番号
　　ネットワーク番号
　　0, デフォルト経路を示す

RIP を使用するエンティティは、データグラムをルーティングする時に利用可能な最も特定の情報を使用すると仮定される。すなわち、データグラムをルーティングする時、その宛先アドレスをホストアドレスのリストに対して、一番最初にチェックしなければならない。そして、知っているサブネットかネットワーク番号と一致するか否かチェックしなければならない。最後に、一致するものが無かったら、デフォルトの経路が使用される。

ホストが RIP を経由して受信した情報を評価する時、アドレスの解釈はそのネットに適用するサブネットマスクを知っているか否かに因る。もし知っているならば、アドレスの意味を決定することが可能である。例えば、ネット 128.6 について考える。それは、255.255.255.0 のサブネットマスクを持っているとする。従って、128.6.0.0 がネットワーク番号であり、128.6.4 がサブネット番号であり、128.6.4.1 がホストアドレスである。しかし、もしホストがサブネットマスクを知らなければ、アドレスの評価が曖昧になるかもしれない。もし 0 でないホスト部があるならば、そのアドレスがサブネット番号を表しているのか、ホストアドレスを表しているのかを決定するための明確な方法が無い。サブネット番号は、サブネットマスク無しでは有効でないので、アドレスはこの状況ではホストを表すものと仮定する。この種の曖昧さを避けるために、ホストは適切なサブネットマスクを知ることを期待できないホストにサブネット経路を送信してはならない。通常ホストは、直接接続されたネットワークのサブネットマスクを知るだけである。従って、もし特別な用意がなされていないならば、サブネットへの経路はサブネットが一部分であるネットワークの外側に送信してはならない。

フィルタリングは、サブネット化されたネットワークの "境界" でゲートウェイによって実行される。これらは、ネットワークを他の幾つかのネットワークに接続するゲートウェイである。サブネット化されたネットワークの範囲内で、各々のサブネットは別個のネットワークとして扱われる。各サブネットのルーティングエントリは、RIP によって算出される。しかし、境界のゲートウェイは、他のネットワークのホストにネットワーク全体で単一のエントリのみを送信する。これは、境界のゲートウェイは異なる隣接者に異なる情報を送信することを意味する。サブネット化されたネットワークに接続されている隣接者のために、ゲートウェイは直接接続されている全てのサブネットのリストを、サブネット番号を使用して生成する。他のネットワークに接続されている隣接者のために、ネットワーク全体として単一のエントリを作成し、そのネットワークに関連したメトリックを示す。(このメトリックは通常、ゲートウェイが接続されているサブネットで最も小さいメトリックである)。

同様に境界のゲートウェイは、直接接続されたネットワークの一つの中のホストのためのホスト経路を、他のネットワークにメッセージで言及してはならない。それらの経路は、ネットワーク全体の一つのエントリに包含される。"離れた" ホスト (すなわち、直接接続されたネットワークの一部ではないホスト) のホスト経路で何をするかは規定しない。一般的にこれらの経路は、ホストが一部を成すネットワーク上の他のホストをサポートしていない経路を経由して到達可能なホストの幾つかを示す。

特別なアドレス 0.0.0.0 は、デフォルト経路を示すのに使用される。デフォルト経路は、RIP の更新情報で全ての有り得るネットワークをリスト化することが効率的でない時や、システムで一つ以上近くに接続されたゲートウェイが、明示的にリスト化されていないネットワークへのトラフィックを扱う準備がされている時に使用される。これらのゲートウェイは、あたかも自分が接続しているネットワークであるかのように、アドレス 0.0.0.0 の RIP エントリを作成しなければならない。ゲートウェイが 0.0.0.0 のエントリを作成する方法についての決定は、実装者に任される。最も共通的に、システム管理者は、どのゲートウェイが 0.0.0.0 のエントリを作成するかを指定する方法を提供されるだろう。しかし、他のメカニズムも可能である。例えば、EGP を話すゲートウェイは全てデフォルトゲートウェイとして宣言すべきであると、実装者は決定するかもしれない。ネットワーク管理者が、これらのエントリで使用されるメトリックを選択することは有効かもしれない。もし一つ以上のデフォルトゲートウェイが存在するならば、他よりも上の優先度の表現を可能にするだろう。0.0.0.0 のエントリは、このネットワークのアドレスが実際に存在するかのように、RIP によって全く同じ方法で扱われる。しかし、そのエントリは、宛先アドレスがテーブル中の他のネットワークに一致しないデータグラムをルーティングするために使用される。実装体は、この取り決めをサポートする必要はない。しかし、実装することが強く推奨される。0.0.0.0 をサポートしていない実装体は、このアドレスを持つエントリを無視しなければならない。その場合、それらは自身の RIP 更新情報でそのエントリを渡してはならない。システム管理者は、0.0.0.0 への経路が意図した以上に流布されないことを保証するよう注意しなければならない。一般的に、各々の自律システムは自分が望むデフォルトゲートウェイを持つ。従って、0.0.0.0 を含む経路は通常、自律システムの境界を残すべきではない。これを強制するメカニズムは、このドキュメントでは規定しない。

3.3. タイマ

このセクションは、タイマがトリガとなる全てのイベントを説明する。

30 秒毎に、全ての隣接するゲートウェイへの完全な応答を生成するために出力処理が指示される。単一のネットワーク上に多くのゲートウェイが存在する時、同時に更新情報を発行するように、お互いに同期をとる傾向がある。これは、30 秒タイマがシステム上の処理負荷に影響される時は常に起こり得る。ブロードキャストネットワーク上に不必要な衝突を導き得るので、更新メッセージが同期をとることは望ましくない。従って、実装体は二つの警戒のうち一つを採用する必要がある。

各々の経路に割り当てられた二つのタイマが存在する。"タイムアウト" と "ガーベージコレクション時間" である。タイムアウトが満了すると、その経路はもはや有効ではない。しかし、それはテーブルに短時間保持され、それによって隣接者に経路が落ちたことを通知できる。ガーベージコレクションタイマが満了したとき、その経路は最終的にテーブルから削除される。

タイムアウトは、経路が確立される時と、経路に対する更新メッセージを受信した時に初期化される。タイムアウトが最後に初期化されてから180 秒経過したら、その経路は満了したと見なされ、これから説明しようとする削除プロセスが開始される。

削除は、二つの理由の一つにより発生し得る。(1) タイムアウトが満了した。(2) 現在のゲートウェイから受信した更新情報のために、メトリックが 16 に設定された。(他のゲートウェイからの更新情報の処理については、セクション3.4.2を参照されたい)。いずれかのケースで、以下のイベントが起きる。

ガーベージコレクションタイマが満了するまで、その経路はこのホストから送信される全ての更新情報に、メトリック 16(永久) を持って含まれる。ガーベージコレクションタイマが満了した時、その経路はテーブルから削除される。

もしガーベージコレクションタイマが作動中に、この経路への新しいネットワークが確立されたら、その新しい経路は削除されようとしている経路から置き換わる。この場合、ガーベージコレクションタイマをクリアしなければならない。

トリガ更新を実行する必要がある遅延については、セクション 3.5を参照されたい。遅延の実装はタイマを必要とするが、ここよりもセクション3.5で論じた方が自然である。

3.4. 入力処理

このセクションでは、UDP ポート 520 上で受信されたデータグラムの扱いについて説明する。データグラムを詳細に処理する前に、一般形式チェックを施さなければならない。これらは、データグラムのバージョン番号フィールドに依存する。以下の通り。

0 -- バージョン番号が 0 であるデータグラムは無視される。これらは、このプロトコルより前のものであり、そのパケット形式はマシン特定である。

1 -- バージョン番号が1であるデータグラムは、この規約の残りで規定されるように処理される。上記で "0 でなければならない" と規定されている全てのフィールドをチェックする。もしそのフィールドが 0 でない値を含むならば、メッセージ全体を無視する。

1> -- バージョン番号が 1 よりも大きいデータグラムは、この規約の残りで規定されるように処理される。上記で "0 でなければならない" と規定されている全てのフィールドを無視する。このプロトコルの後のバージョンがこれらのフィールドにデータを入れているかもしれない。バージョン 1 の実装体はこの余分なデータを無視し、このドキュメントで規定されているフィールドのみを処理する。

バージョン番号のチェックと、他の初期チェックを行った後、処理はコマンドフィールドの値に依存する。

3.4.1. 要求

要求は、ホストのルーティングテーブルの全て、又は一部を含む応答を求めるために使用される。[ホストという用語はホストかゲートウェイのいずれかのために使用され、大抵の場合、非ゲートウェイのホストが RIP メッセージを送信するのは普通でない]。通常、要求は UDP 送信元ポート 520 から、ブロードキャストで送信される。この場合、黙ったプロセスは要求に対する応答を送信しない。黙ったプロセスとは定義により、通常、ルーティング情報を見たくないプロセスである。しかし、黙ったプロセスであってもルーティングテーブルを見ることを望むようなゲートウェイの監視を伴う状況が存在するかもしれない。この場合、要求は 520 以外の UDP ポート番号から送信すべきである。もし要求が他のポートから来たら、たとえ黙っていても応答しなければならない。

要求はエントリ毎に処理される。もしエントリが存在しなければ、応答は返さない。特殊なケースが一つ存在する。もし、要求の中に 0 のアドレスファミリ識別子 (未規定の意味) と無限のメトリック (現実装では 16) を持つエントリが一つだけ存在しているならば、これはルーティングテーブル全体を送信してほしいという要求である。その場合、出力プロセスを呼び出して、要求側ポートにルーティングテーブルを送信する。

この特殊なケースを除いて、処理は極めて単純である。要求の中のエントリのリストを一つずつ下る。各々のエントリに対して、ホストのルーティングデータベース中の宛先を調べる。もし経路が存在するならば、メトリックフィールドにある経路のメトリックをデータグラムに入れる。もし指定された宛先へのルートが存在しないならば、データグラムに無限 (すなわち 16) を入れる。全てのエントリが埋まったら、コマンドに応答を設定し、そのデータグラムを来たポートに返送する。

要求が宛先の特定のセットに対してか、ルーティングテーブル全体に対してかによって扱いに相違があることに注意されたい。もし要求がホストテーブル全体に対してのものならば、通常の出力処理が行われる。これは、水平分割 (セクション2.2.1)とサブネット隠蔽 (セクション3.2) を含む。よって、ルーティングテーブルからエントリは表れない。もし要求が特定のエントリに対してのものならば、ホストテーブル内を調べて情報を返却する。水平分割の処理は行われず、もし要求されたらサブネットが返却される。これらの要求は異なる目的で使用されるだろうと予測する。ホストが最初に立ち上がったとき、ホストはルーティングテーブル全体を求めるために、接続された全てのネットワークに要求をブロードキャストする。通常、ルーティングテーブル全体は別のホストのルーティングテーブルを更新するために使用すると仮定している。この理由により、水平分割や他の全てのフィルタリングを使用しなければならない。特定のネットワークに対する要求は、診断ソフトウェアによってのみ行われ、ルーティングには使用されない。この場合、要求者はルーティングデータベースの正確な内容を知りたがり、隠蔽された情報は望まないだろう。

3.4.2. 応答

応答は、幾つかの異なる理由により受信される。

　　特定のキュエリへの応答
　　規則的な更新
　　メトリックの変更に伴うトリガ更新

応答の処理は、ホストのルーティングテーブルを更新するかもしれないので、正当性のチェックは注意深く行わなければならない。応答は、ポート 520 から来ていなければ無視しなければならない。IP 送信元アドレスは、そのデータグラムが正しい隣接者からのものであるかチェックすべきである。データグラムの送信元は、直接接続されたネットワーク上にいなければならない。応答がホスト自身のアドレスの一つから来たかをチェックすることも価値がある。ブロードキャストネットワーク上のインタフェースは、自分のブロードキャストのコピーを即座に受信するかもしれない。もしホストが自分自身の出力を新しい入力として処理したら混乱が起きるかもしれず、そのようなデータグラムは無視しなければならない (次のパラグラフで論じていることを除く)。

実際に応答を処理する前に、インタフェース状態の足跡を保つために、プロセスへの入力時の存在を使用することは有効かもしれない。上述したように、ある時間そのゲートウェイから何も聞かなかったら経路をタイムアウトする。これは、別のゲートウェイから来た経路に対して上手く作用する。自分達自身の直接接続されたネットワークの一つが、いつ失敗したかを知ることも望ましい。このドキュメントは、これを行うための特定の方法は規定しない。その方法は、ネットワークの特性やハードウェアインタフェースに依存するからである。しかし、その方法はしばしばインタフェース上に到着するデータグラムのリスニングを伴う。データグラムが到着することは、インタフェースが動作しているという指示として使用できる。しかし、幾つかの警告を使用しなければならない。なぜなら、出力データグラムを正常に送信できないが、入力データグラムを受信するような方法でインタフェースが失敗することがありえるからである。

データグラム全体を評価したら、そのエントリを一つずつ処理する。そして再び評価を実施する。もしメトリックが無限よりも大きければ、そのエントリを無視する。(もし他のホストが正しく動作しているならば、これは有り得ない。不正なメトリックや他の形式のエラーにより警告やログ採取を行うべきである)。その後、宛先アドレスをチェックし、アドレスファミリ識別子をチェックする。もし期待した値でないならば (インターネットアドレスでは 2)、そのエントリを無視する。そして、そのアドレス自身を、不適切なアドレスの様々な種類に対してチェックする。もしアドレスがネット 0 上のものならば、そのアドレスがクラス D か E ならばエントリを無視する (もしデフォルト経路を受け入れるならば、0.0.0.0 は除く)。さらに、ブロードキャストアドレス、すなわちブロードキャストをサポートするネットワーク上でホスト部が全て 1 に対してチェックし、そのエントリを無視する。もし実装体がホスト経路をサポートしないことを選択したならば (セクション3.2参照)、アドレスのホスト部が 0 でないかをチェックしる。その場合、もし 0 ならそのエントリを無視する。

アドレスフィールドが沢山の未使用オクテットを含んでいることを思い出して欲しい。もしデータグラムのバージョン番号が 1 ならば、それらをチェックしなければならない。もしそれらのどれかが 0 でないならば、そのエントリを無視する。(これらのクラスの多くは、メッセージを送ったホストが正しく動作していないことを示している。従って、エラーログの採取や警告を発するトリガとすべきである)。

メッセージが到着したネットワークのコストを追加することによってメトリックを更新する。もしその結果が16よりも大きいならば、16を使用する。すなわち、

　　metric = MIN (metric + cost, 16)

そして、既に経路として持っているか否かを見るためにアドレスをチェックする。通常、もしそうでなければ (経路として持っていなければ) 一つ追加したい。しかし、幾つかの例外がある。もしメトリックが無限ならば、エントリを追加しない。(既存のものは更新するが、メトリックが無限のエントリは新たに追加しない)。もしホストが少なくとも同じ位良い経路のネットかサブネットの一部ならば、そのホストへの経路を追加することを避けたい。これらの例外がいずれも適用されないならば、ルーティングデータベースに新しいエントリを追加する。これは、次の動作を含む。

もし既存の経路が存在するならば、最初にゲートウェイを比較する。もしこのデータグラムが既存の経路と同じゲートウェイからのものならば、タイムアウトを再起動する。次にメトリックを比較する。もしそのデータグラムが既存の経路と同じゲートウェイからのもので、新しいメトリックが古いものとは異なっている、あるいは新しいメトリックが古いものよりも小さいならば、以下の動作を実行する。

もし新しいメトリックが 16(無限) ならば、その経路を削除するためのプロセスを開始する。その経路はもはやルーティングパケットには使用されず、削除タイマが開始される (セクション3.3参照)。削除は、メトリックが初めて 16 に設定された時にのみ開始される。もしメトリックが既に 16 ならば、新たに削除は開始されない。(削除の開始によりタイマは設定される。心配なのは、新しいメッセージが無限のメトリックを持って到着する際、30 秒毎にタイマをリセットしたくないことである)。

もし新しいメトリックが古いものと同じならば、最も簡単なことは何も実行しないことである (上述したように、タイムアウトの再起動は除く)。しかし、4BSD の routed はここで追加の自発的診断を使用する。通常、既存の経路と同じメトリックを持つが、ゲートウェイが異なる経路に変更することは無意味である。しかし、もし既存の経路がタイムアウトの兆候を示しているならば、タイムアウトの発生を待つよりも、メトリックの等しい代替経路に即座に切り替えることはより良いかもしれない。(タイムアウトの議論については、セクション3.3参照)。従って、もし新しいメトリックが古いものと同じならば、routed は既存の経路のタイムアウトをチェックする。もしそれが少なくとも満了点の半分ならば、routed は新しい経路に切り替える。すなわち、ゲートウェイが現在のメッセージの送信元に変更される。この自発的診断はオプションである。

これらのテストが失敗したエントリは、現在の経路ほど優れていないので無視される。

3.5. 出力処理

このセクションは、ルーティングテーブルの全てあるいは一部を含む応答メッセージを作成する処理について説明する。この処理は、以下の事象がトリガとなって実行される。

各々の直接接続されたネットワークでメッセージを作成する方法を記述する前に、後者の二つのケースで宛先をどのように選択するかについてコメントする。通常、応答が全ての宛先に送信される (すなわち、定期更新かトリガ更新が用意される) とき、応答は各々接続されたポイントツーポイント回線の対の終端のホストに送信され、応答はブロードキャストをサポートしている全ての接続されたネットワーク上でブロードキャストされる。従って、各々の直接接続されたネットワークに対して一つの応答が用意され、対応する (宛先またはブロードキャスト) アドレスに送信される。ほとんどのケースでは、これは全ての隣接ゲートウェイに到着する。しかし、幾つかのケースで、これでは十分でない場合が存在する。これはブロードキャストをサポートしていないネットワーク (例えば ARPANET) や、ダムゲートウェイを含む状況に由来する。そのようなケースでは、隣接するホストやゲートウェイの実リストを指定し、銘々に明示的にデータグラムを送信する必要があるかもしれない。そのようなメカニズムが必要であるか否かの決定や、リストの指定方法の定義については実装者に任される。

トリガ更新は、二つの理由のために特殊な操作を必要とする。第一にトリガ更新は、制限された容量を持つか、その上に多くのゲートウェイを持つネットワークに過度の負荷を引き起こし得ることが、経験上分かっている。従って、プロトコルは、実装体がトリガ更新の頻度を制限する機能を含むことを必要とする。トリガ更新を送信した後、タイマを 1～5 秒のランダムな時間に設定すべきである。もし、タイマが満了する前に他の変更がトリガ更新を発生したならば、タイマが満了したとき単一の更新のトリガとし、その後タイマを別の 1～5 秒のランダムな時間に設定する。もしトリガ更新を送信する際に定期更新が行われたら、トリガ更新を抑止してもよい。

第二に、トリガ更新はルーティングテーブル全体を含む必要はない。原則的には、含める必要があるのは変更があった経路だけである。従って、トリガ更新の一部として生成されたメッセージは、少なくとも経路更新フラグが設定された経路を含まなければならない。実装者の裁量で追加経路や全ての経路を含んでもよいが、全体のルーティング更新は複数のパケットを必要とする時、全経路を送信しないことを強く推奨する。トリガ更新を処理するとき、全ての直接接続されたネットワークに対してメッセージを作成すべきである。水平分割処理は、通常の更新だけでなくトリガ更新の生成時も行われる (次を参照)。

もし水平分割の処理後、変更された経路がネットワーク上で前と同じならば、その経路は送信する必要は無い。結果的にどの経路も送信する必要が無いならば、そのネットワーク上では更新を省略してもよい。(もし経路がメトリックのみの変更であったり、古いゲートウェイと同じネットワーク上にある新しいゲートウェイを使用するならば、その経路は無限のメトリックを持つ古いゲートウェイのネットワークに、変更の前後両方で送信されるだろう)。一旦トリガ更新の全てを生成したら、経路変更フラグをクリアすべきである。

もし出力情報が生成されている間に入力処理が許されているならば、適切な相互ロックを実施しなければならない。経路変更フラグは、トリガ更新メッセージが生成されている間の入力処理の結果で変更すべきではない。

トリガ更新と他の更新メッセージの唯一の相違は、変更されない経路の省略が可能であることである。その他のメカニズムは、全てトリガ更新に適用しなければならない。

これは、応答データグラムがどのように特定の直接接続されたネットワークに対して生成されるかである。

IP 送信元アドレスは、送信したホストのネットワーク上のアドレスでなければならない。送信元アドレスは他のホスト中のルーティングテーブルに入れられるので、これは重要である。もし不正な送信元アドレスが使用されると、他のホストはデータグラムを振り分けられないかもしれない。時々ゲートウェイは、単一の物理インタフェースに対して複数の IP アドレスを設定される。通常これは、複数の論理的な IP ネットワークが一つの物理媒体上で運用されることを意味する。そのような場合、そのアドレスを IP 送信元アドレスとして持つ別々の更新メッセージを、各々のアドレスに対して送信しなければならない。

バージョン番号に現在の RIP のバージョンを設定する。(このドキュメントで示されているバージョンは 1 である)。コマンドに応答を設定する。"0 でなければならない" バイトに 0 を設定する。そしてエントリを設定する。

エントリを設定するために、内部のルーティングテーブル中の全ての経路を記録する。最大データサイズが 512 バイトであることを思い出してほしい。データグラムにもう余裕が無いとき、そのメッセージを送信し、新たに開始する。もしトリガ更新が作成されたら、経路変更フラグが指定されているエントリのみを含む必要がある。

サブネットとホスト経路による問題の議論については、セクション3.2の説明を参照されたい。サブネットへの経路はそのネットワークの外側では無意味であり、もし宛先が同じサブネット化されたネットワークでないならば、省略しなければならない。その場合、そのサブネットの部分であるネットワークへの単独の経路に置き換わる。同様にホストへの経路は、セクション3.2の議論で説明されているように、ネットワーク経路によって包含されるならば除去しなければならない。

もし経路がこれらのテストをパスしたならば、その宛先とメトリックを出力データグラムのエントリに含める。たとえメトリックが無限であっても、その経路をデータグラム中に含めなければならない。もしその経路のためのゲートウェイが、データグラムが準備されているネットワーク上にあるならば、そのエントリ中のメトリックを 16 に設定するか、そのエントリ全体を省略する。そのエントリを省略することは、単純な水平分割である。メトリック 16 を持つエントリを含めることは、有毒な逆を持つ水平分割である。これらの代替のより完全な議論については、セクション2.2を参照されたい。

3.6. 互換性

このドキュメントで規定されているプロトコルは、routed や他の既存の RIP 実装と相互接続することを意図している。しかし、メトリックを増加する時について、最も最近の実装で使用されたものとは異なる観点が適用されている。以前の観点を使用すると、内部のルーティングテーブルは全ての直接接続されたネットワークに対して 0 のメトリックを持つ。その経路が更新メッセージで送信されるとき、コスト (常に 1) がメトリックに追加される。対照的に、このドキュメントでは直接接続されたネットワークは、内部ルーティングテーブルにそのコストと等しいメトリックを持って表れる。そのメトリックは 1 である必要はない。このドキュメントでは、更新メッセージで経路を受信した時にメトリックにコストが追加される。ルーティングテーブルからのメトリックは、変更せずに更新メッセージ更新メッセージで送信される (もし水平分割による修正が無いならば)。

これらの二つの観点により、同一の更新メッセージが結果的に送信される。二つの規定でのルーティングテーブル中のメトリックは、一定して一異なる。従って、効果としては相違が無い。新しい規定は、直接接続されたネットワーク上で、異なるメトリックが使用される状況の扱いを容易にするために変更された。

一のネットワークコストしかサポートしていない実装は、表現の新しいスタイルに一致させるために変更する必要は無い。しかし、このドキュメントに記述されている他の全てのやり方には従わなければならない。

4. 制御機能

このセクションは、管理制御について規定する。これらはプロトコルの一部ではない。しかし、既存ネットワークでの経験により、これらは重要なことである。これらはプロトコルの必要な部分ではないので、オプションとして見なされる。しかし、少なくともこれらの幾つかが全ての実装に含まれることを強く推奨する。

これらの制御は、RIP をルーティングが不安定でエラーが起こりやすいようなネットワークへの接続を可能にすることを基本的に意図している。幾つかの例がある。

ホストとゲートウェイを受諾できる情報から制限することは時々望ましい。たまに、ホストは不適切な情報を送信するように誤って設定される。

数多くのサイトは、更新メッセージで許可するネットワークのセットを制限している。組織 A は、直接通信で使用する組織 B へのコネクションを持つかもしれない。セキュリティやパフォーマンスのために、A はそのコネクションへのアクセス権を他の組織に与えようとしなくともよい。そのような場合、A は A がサードパーティに送信する更新メッセージの中に、B のネットワークを含むべきではない。

以下は、幾つかの典型的な制御である。しかし、RIP プロトコルは、これらの制御や他の如何なる制御も要求していないことに注意されたい。

参照と文献

[1] Bellman, R. E., "Dynamic Programming", Princeton University Press, Princeton, N.J., 1957.

[2] Bertsekas, D. P., and Gallaher, R. G., "Data Networks", Prentice-Hall, Englewood Cliffs, N.J., 1987.

[3] Braden, R., and Postel, J., "Requirements for Internet Gateways", USC/Information Sciences Institute, RFC-1009, June 1987.

[4] Boggs, D. R., Shoch, J. F., Taft, E. A., and Metcalfe, R. M., "Pup: An Internetwork Architecture", IEEE Transactions on Communications, April 1980.

[6] Ford, L. R. Jr., and Fulkerson, D. R., "Flows in Networks", Princeton University Press, Princeton, N.J., 1962.

[7] Xerox Corp., "Internet Transport Protocols", Xerox System Integration Standard XSIS 028112, December 1981.

D	dir, 1	dir, 1	dir, 1	dir, 1	...	dir, 1	dir, 1
B	unreach C	C, 4	C, 5	C, 6	...	C, 11	C, 12
C	B, 3	A, 4	A, 5	A, 6	...	A, 11	D, 11
A	B, 3	A, 4	C, 5	C, 6	...	C, 11	C, 12

Routing Information Protocol

Status of this Memo

概要