第 5 回 ルーティング(2)

本日の内容

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

画像を含めて印刷したい場合は Java の機能を切って下さい。

5-1. 距離ベクトル型

ここでは、ダイナミックルーティングの一方式である距離ベクトルアルゴリズ ムについて解説します。

これは、基本的には自分の持っているルーティングテーブルを放送するもので す。そして、他のルータが放送しているものを受信したら、有効な情報を集計 してルーティングテーブルに追加します。 ここで、有効とは距離(メトリック)が短いことを意味します。 距離ベクトル型ではメトリックとしてネットワークを中継した数である ホップ数を使用します。

例えば、ネットワーク A と B に接続しているルータ R1 があったとします。

  1. すると初期のルーティングテーブルはネットワーク A にメトリック 1, ネッ トワーク B にメトリック 1 という二つだけ登録されていることになります。 一方ネットワーク B と C に接続しているルータ R2 には同様にネットワーク B と C がそれぞれメトリック 1 で登録されています。
  2. ここで、相互にルーティングテーブルを放送します。 そして、R1 は R2 のルーティングテーブルを受信します。
    1. R1 は R2 のルーティングテーブルのメトリックを 1 増やします。
    2. R2 のルーティングテーブルにはネットワーク A の情報はありませんので、 A の情報はそのままです。
    3. R1 のネットワーク B のメトリックは 1 です。一方、R2 のルーティング テーブルのネットワーク B もメトリックはもともと 1 ですが、 1 増やされ ているので 2 になっています。 本来新しい情報に書き変わるのですが、ネットワークBは直接接続されている ため、障害が無い限りどちらも最新の情報として取り扱われます。 その場合、メトリックが最小のものが採用されます。 よって、メトリック 1 であるもともとの情報のままになります。
    4. R1 にはネットワーク C の情報はありません。 一方、R2 のルーティングテーブルにはネットワーク C がメトリック 1 で含 まれています。 メトリックは 1 増やされているので 2 になりますが、もともとのルーティン グテーブルにはありませんので、ネットワーク C はゲートウェイ R2 メトリッ ク 2 で登録されます。

情報は放送されますので、一ステップで一ホップ情報は伝達されてい きます。未知の情報は必ずルーティングテーブルに登録され、隣のルータに伝 搬します。 従ってすべての情報は必ずネットワーク内を伝搬していきます。 なお、放送は、ホストアドレスのビットがすべて 1 であるブロードキャ ストアドレスに対して行われます。 また、 TCP では一対一の通信しかできませんので、放送はできません。そこ で、 UDP というプロトコルで放送が行われます。 ポート番号は 520 番です。

さて、ネットワークで途中で経路がなくなったら、この距離ベクトルルーティ ングはどうなるでしょうか? ルータ R1 が接続しているネットワーク A に対して、 ルータ R2 はネットワー ク B で R1 と接続し、ルータ R3 はネットワーク C で R1 と接続している状 況を考えます。 そして、さらにルータ R2 と R3 がネットワーク D で接続しているとします。 つまり、 R1, R2, R3 が三角形につながっていて、R1 から外側にネットワー クが出ているとします。

  1. さて、この状況では、 R2 のネットワーク A はゲートウェイ R1 メトリック 2 で登録されます。 同様に R3 のネットワーク A もゲートウェイ R1 メトリック 2 で登録されま す。 この時点では問題ありません。
  2. しかし、このネットワーク A がシステムダウンしてしまった状況を考えましょ う。 すると、もう R1 はネットワーク A の経路情報を放送しなくなります。 R2 に来るネットワーク A の情報は、今までは R1 からメトリック 1, R3 か らはメトリック 2 でやってきました。そこで、 R1 のを採用してメトリック 2 になってました。
  3. それが来なくなってしまうため、本来はネットワーク A の経路情報は消えるべきですが、それが R2 は R3 から来るメトリック 2 の 情報を採用して、ゲートウェイ R3 メトリック 3 で登録されてします。
  4. すると、ルータ R3 にはネットワーク A の情報は R2 から来るメトリック 3 の情報のみになります。 そして、ルータ R3 にはゲートウェイ R2 メトリック 4 で登録されてしまい ます。
  5. つまり、放送を繰り返すたびにメトリックが 1 ずつ増えていきますが、本来 消えるべきネットワーク A への経路情報は消えません。

そこで、ある程度メトリックが大きくなったらそれはもう届かないと思うこと にします。 その値の値のことを無限と言います。そして、 RIP プロトコルはこ の無限の値を 16 に設定しています。 この 16 という値は少ないかと思うかも知れませんが、各ルータの放送間隔は 30 秒です。 R2 が放送して、R3 が放送し、また R2 が放送するまで 30 秒です。従って、 故障が発生した後、30 秒でメトリックは 2 しか増えません。よってメトリッ ク 2 が16 に増えるまで 210 秒=3 分半もかかりますので、その間ネットワー A に接続できないことに気づかないわけです。 この時間を短縮することはできないでしょうか?

水平分離

そこで考えられたアルゴリズムは Split horizon や Split horizon with poisoned reverse です。

Split horizon は経路情報がどこから送られてきたかを覚えておいて、送られ てきた経路情報は元に戻さないというものです。一方、 Split horizon with poisoned reverse は送られてきた経路情報に関してはメトリックを無限に設 定して送り返すと言うものです。

Split horizon では嘘の情報を流しているルータに、その情報を裏付ける情報 を流してくる情報源を断つ事ができますので、タイムアウト(120秒)するとルー ティングテーブルから消失します。

一方、Split horizon with poisoned reverse では嘘の情報を流してくるルー タは今度は積極的に接続していないという情報を返してくるので、それをうの みにしてしまえば接続してないことにすぐになり最短時間でルーティング情報 が正常になります。

Triggerd Updates

しかし、 Split horizon with poisoned reverse では三つ以上のルータの錯誤には役に 立ちません。 つまり、三つのルータがそれぞれ輪になるように転送先を選んでいる場合は一 ステップでメトリックが一ずつ増えると言う状況になります。 そこで、今度はこのステップをなるべく短時間で進めることを考えます。 そのため、Triggerd Updates は次のルールを追加します。 「もし、経路のメトリックだけが書き変わったら、すぐに新しい経路情報の放 送を始める」 これにより安定していない経路に関しては素早く更新が行われ、なくなった経 路はすばやく消去されます。

5-2. RIP

RIP(Routing Information Protocol RFC 1058)は距離ベクトル型のルーティン グプロトコルです。 RIP は UDP のポート番号 520 番を利用します。

プロトコルフォーマット

RIP のパケットの書式は以下の通りです。

01234567 89101112131415 1617181920212223 2425262728293031
コマンド バージョン 全て 0
アドレスファミリーの識別子 全て 0
IP アドレス
全て 0
全て 0
メトリック
...

このうち「アドレスファミリの識別子」から「メトリック」の間は 25 回まで 繰り返して良いです。

コマンドは以下のようになっています。

1 - request
返答可能なシステムに対して、一部または全てのルーティングテーブルを要求 するメッセージ。
2 - response
送信者の持っている一部または全てのルーティングテーブルを含むメッセー ジであることを示します。 このメッセージは定期的に送られるか、要求メッセージへの答として送られる か、または、送信者が作成した更新したメッセージとして送られます。
3 - traceon
これは廃止されたので、無視されます。
4 - traceoff
これは廃止されたので、無視されます。
5 - 予約
無視されます。

RIP は IP 以外のネットワークアドレスのルーティング情報を運ぶことができ ます。 そこで、 IP ネットワークのルーティング情報を交換するには、アドレスファ ミリの識別子に IP を示す 2 を入れておく必要があります。 メトリックには 1 から 15 までのホップ数を表す数か、到達不能を示す 16 が入ります。

RIP ver.1 はサブネットマスクを伝搬しません。 したがって、送られてきた IP アドレスは、ネットワークアドレスか、サブネッ トのアドレスか、ホストのアドレスか、デフォルト(0.0.0.0) のいずれかです が、この見分け方が難しいです。 但し、ローカルネットワーク内では単に受けとった情報をそのまま流すだけで 無事ルーティングは行われます。

境界ルータの経路情報 しかし、他のネットワークと接続する境界ルータ(border router) は別です。 境界ルータは他のネットワーク組織にはサブネットの情報を出さず、単純に (ナチュラルマスクの)ネットワークアドレス一個を送ります。この時、メトリッ クはルーティングテーブル内の最小の値にセットします。

また、0.0.0.0(default)は他のテーブルと同様に扱いますが、どのルータが発 生させるかは実装に依存します。 ただ、例えば、 EGP を喋るルータが発生させるということはよく行われてい ます。

タイマー

30 秒毎に隣接するすべてのルータに返答を返します。 一つのネットワークに多くのルータが存在していると、それぞれのルータがお 互いに同期をとりあうような動作になってしまうことが起きます。 これはシステムの負荷にこの 30 秒のタイマーが左右される時に起きやすいと 言う傾向があります。 しかし、すべてのルータが同時に返答を始めるとネットワークの負荷が高くなっ てしまうため、それを避ける必要があります。 従って、次の二つのうちの一つを実装する必要があります。

  1. システムに影響せず正確に 30 秒毎に発する。
  2. 30 秒から微妙にランダムにずれて発する

次に二つのタイマーについて説明します。 一つはタイムアウトタイマー、もう一つはガベージコレクションタイマーです。 各ルーティングの要素はタイムアウトタイマーにより 120 秒数えられます。 120 秒間の間ルーティングの情報を受信しなかった場合、その要素は正当なも のでないと見なされます。 つまり、この時点でメトリックが 16 に書き換えられます。 そして、この書き換えられた情報は広告されます。 この要素は、新たな情報の受信がない限り、さらにガベージコレクションタイ マーで120 秒間保持された後、ルーティングテーブルから削除されます。

入力処理

要求メッセージ

要求メッセージは各エントリ毎に処理されます。 但し、アドレスファミリ識別子が 0 でメトリックが無限(16)の場合はすべて のルーティングテーブルを送ります。 その他は送られてきた各要素について、知っているメトリックを埋め、知らな い時はメトリックを無限(16)にセットして送り返します。 ここで、全ルーティングテーブルを送る時は水平分割を行いますが、個別の要 素については必要な情報は送り返し水平分割は行いません。

出力処理

テーブルの出力は次の場合に行われます。

  1. 30 秒ごと
  2. リクエストを受け取った時
  3. triggerd update 処理

5-3. RIP ver. 2

RIP ver.2 は次の特徴を持ちます。

  1. マルチキャスト 224.0.0.9 で通信します。
  2. サブネットマスクを伝搬します。したがって VLSM(Valuable Length Subnet Mask) をサポートします。
  3. ネクストホップ

5-4. RIPng

RIPng の ng は New Generation の意味で、IPv6 用の距離ベクトルルーティ ングプロトコルを指します(RFC2080)。

  1. 使用アドレスは FF02::9, the all-rip-routers multicast group
  2. UDP 521

  3. プロトコルフォーマットは簡略化されている

    01234567 89101112131415 1617181920212223 2425262728293031
    コマンド バージョン 全て 0
    エントリテーブル1(20byte)
    エントリテーブル2(20byte)
    ...
    エントリテーブル20(20byte)
  4. バージョン番号は1
  5. エントリーテーブルは IPV6プリフィックス(128bit)、ルートタグ(16bit)、プリフィックス長(8bit)、 メトリック(8bit)。 但し、メトリックは最大 15
坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科