RFC1058 - Routing Information Protocol Network Working Group
Request for Comments: 1058 | C. Hedrick
Rutgers University |
Routing Information Protocol
Status of this Memo
この RFC は、ゲートウェイと他のホスト間で、経路情報を交換するためのプロトコルを規定している。これは、インターネット社会でゲートウェイソフトウェアを開発するための基礎として使用されることを意図している。このメモの配布は制限されない。
Table of Contents
1. 導入
1.1. プロトコルの制限
1.2. このドキュメントの構成
2. 距離ベクトルアルゴリズム
2.1. トポロジの変更の取り扱い
2.2. 不安定性の防止
2.2.1. 水平分割
2.2.2. トリガ更新
3. プロトコル規定
3.1. メッセージ形式
3.2. アドレス付けの考慮
3.3. タイマ
3.4. 入力処理
3.4.1. 要求
3.4.2. 応答
3.5. 出力処理
3.6. 互換性
4. 制御機能
参照と文献
概要
このメモは、以下の事柄を行うことを意図している。
- ルーティングで広く使用されているが、公式的には文書化されていなかったプロトコルやアルゴリズムを文書化する。
- 大規模なネットワークにおける経路の安定性を改善する為の、幾つかのアルゴリズムの改良を規定する。これらの改善は、既存の実装との非互換性をもたらさない。それらは、このプロトコルの全ての実装に吸収される。
- より多くの構成や制御を可能にする為の幾つかのオプショナルな特性を提案する。これらの特性は特に、NSFnet 社会で実際に使用される過程で検出された問題を解決する為に開発された。しかし。それらはより一般的な実用性を持つはずである。
ここで示されている経路情報プロトコル (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 として使用することを基本的に意図している。加えて、以下の特定の制限について触れなければならない。
- このプロトコルは、最長 15 ホップのパスに閉じるネットワークに制限されている。設計者は、基本的なプロトコル設計がより長いネットワークは不適切でだと考えている。注記: この制限では、1 のコストが各ネットワークで使用されると仮定している。これは、RIP が通常構成される方法である。もしシステム管理者がより大きなコストを使用することを選択したら、15 という上限値はたやすく問題になり得る。
- このプロトコルは、ある普通でない状態を解決する為に "無限に数える" ことに依存している。(これは、次のセクションで説明する)。もしネットワークのシステムが、数 100 ものネットワークを持っており、ルーティングループがこれら全てを巻き込んで形成されていたら、ループの解決は大量の時間 (ルーティングの更新頻度が制限されていれば) か、大量の帯域 (変更が検知される度に更新情報が送信されたら) のどちらかが必要になるだろう。このようなループは、ループが正常になる前に大量のネットワーク帯域を消費する。現実的なケースでは、これは低速回線を除いては問題にならないと考えている。問題になったとしても、大半のケースでこれらの問題を防ぐための様々な警告がなされるはずなので、これは非常に稀なケースである。
- このプロトコルは、代替経路を比較するのに固定 "メトリック" を使用する。これは、遅延時間、信頼性、負荷等のリアルタイムなパラメタに基づいて経路を選択する必要がある状況では適切でない。このタイプのメトリックを許すために明白な拡張を行うと、プロトコルがそれを扱うよう設計されていないので、ある種の不安定さを招く可能性がある。
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 レベルで目に見える内部構造を持たないものとして考えているからこそ、意味をなす。従って、与えられたネットワークの全てのエンティティに対しては、同一の距離を通常割り当てる。
上記で、各エンティティは、一つのエントリにつきシステムにおいて全てのあり得る宛先をもつ経路データベースを持つと述べた。実際の実装では、各宛先に関する以下の情報を保持する必要がありそうである。
- アドレス: これらのアルゴリズムの IP 実装では、これはホストかネットワークの IP アドレスになるだろう。
- ゲートウェイ: 宛先への経路の中で、一番最初にあるゲートウェイ。
- インタフェース: 一番最初のゲートウェイに到達する為に使用しなければならない物理ネットワーク。
- メトリック: 宛先までの距離を示す数。
- タイマ: エントリが最後に更新されてからの総時間。
加えて、様々なフラグや他の内部情報が、恐らく含まれるだろう。このデータベースは、システムに直接接続されているエンティティの記述で初期化される。そしてこれは、隣接するゲートウェイから受信したメッセージの情報に従って更新される。
ホストとゲートウェイ間で交換される最も重要な情報は、更新メッセージで運ばれるものである。ルーティングに参加している各々のエンティティは、現在そのエンティティに存在する経路データベースを記した更新メッセージを送信する。隣接するエンティティから得られる情報だけを使用して、システム全体の最適な経路を維持することは可能である。そこで使用されるアルゴリズムについては、次のセクションで説明されている。
上記で言及したように、ルーティングの目的は、データグラムを最終の宛先に到達させる方法を見つけることである。距離ベクトルアルゴリズムは、システムにおける全ての宛先への最善経路を持つテーブルに基づいている。勿論、どの経路が最善かを定義する為に、善さを測る何らかの方法を持たなければならない。これが、"メトリック" と呼ばれるものである。
単純なネットワークでは、いくつのゲートウェイを通過しなければならないかを単に数えただけのメトリックを使用することが普通である。より複雑なネットワークでは、メトリックはメッセージが被る遅延総数、送信コスト、最小化してもよい量を表す為に選択される。主要な要件は、メトリックを個々のホップにかかる "コスト" の合計として表すことが可能でなければならないということである。
