next up previous contents
Next: 7.3 Zebraの構造 Up: 7. 動的ルーティングとRIP Previous: 7.1.2 ルーティングプロトコルのアルゴリズム

7.2 距離ベクトル型とRIP

距離ベクトル型の特徴は、それぞれのノードに分散して計算を行い、 それらの結果が近隣に伝達される点にあります。まず、簡単にこうした 点を説明しましょう(但し、元々の距離ベクトル型のアルゴリズムに 基づいて説明し、改良されたアルゴリズムは考慮していません)。

以下の図ではルータA,B が何らかの形で接続され、ルーティング情報を 交換出来るものとします。ルータB の足には 192.168.0.0/24 のネットワーク がつながっています。

\epsfile{file=dv1,scale=0.7}

この時、まずルータA は 192.168.0.0/24 へは自分はコスト0で到達出来る という情報を作成し、これを隣のルータBへと伝達します。ルータB は A からの情報を元に、B から A へ行くためのコストを付加して 192.168.0.0/24 へ行くにはコスト2がかかると言う情報を作成する訳です。 ここで、コストは色々なものから計算されるもので、コストが低いものが 経路選択では優位にあるとみなします。

さて、次にもう少し実際的な例を考えましょう。今度は、先のルータA,Bに 加え、ルータC,Dがある場合を考えます。ルータC はルータAにつながっています がコストは3であるとします。ルータDはルータB,Cにつながっており、 そのコストは両方とも1であるとします。

\epsfile{file=dv2,scale=0.7}

さて先の場合と同じように考える と、ルータBはルータDに以下のように伝達します。

情報元ルータ 宛先 コスト
B 192.168.0.0/24 2
従って、ルータD は、B,D 間のコストを足して、 B を使えば 192.168.0.0/24 へはコスト3で到達する事が出来ると理解します。
情報1
ルータ 経由ルータ 宛先 コスト
D B 192.168.0.0/24 3

同時に、ルータCも同じようにルータDに情報をもたらし、それは 次のようになっていますから、

情報元ルータ 宛先 コスト
C 192.168.0.0/24 3
ルータ D は C を使えば 192.168.0.0/24 へはコスト4で到達出来ることを理解 します。

情報2
ルータ 経由ルータ 宛先 コスト
D C 192.168.0.0/24 4
このようにして最終的にルータD は宛先に対するリストを以下のように手に入れます。

ルータDの持つリスト
情報番号 経由ルータ 宛先 コスト
1 B 192.168.0.0/24 3
2 C 192.168.0.0/24 4
そして、コストが最も低い1の情報に基づいて、192.168.0.0/24 への 経路としてルータ B に送り出す経路を選択する訳です。

ここから分かるように距離ベクトル型では、ルータDからはルータAの 存在は見えていません。隣接するルータB,C が見えているだけで、 言わばその背後にあるネットワークは見えていないのです。これが、 距離ベクトル型が一種の分散計算を行っていると言った理由であり、 距離ベクトル型が単純であると言われる理由なのです。

しかし、一方ここに上げなかった問題が存在します。それは実は上の場合でも ルータDは自分が手に入れた情報を常に隣接するルータ B,C に流し続ける という事です。勿論、B,C はその情報を受け取り、例えばBは次のように 自分のリストを作成します。

ルータBの持つリスト
情報番号 経由ルータ 宛先 コスト
1 A 192.168.0.0/24 2
2 D 192.168.0.0/24 4
少し変な気もしますが、経路選択という点ではコスト2の1の経路 が選ばれますから、この時点ではまだ問題ではありません。(ちなみに、 こうして全てのルータのリストが定まった時点を収束したと言います。)

問題はルータA の 192.168.0.0/24 へのインターフェースが故障した 時に起こります。この場合、元々のRIPのアルゴリズムでは、自分が 分かっている経路のみを流すことになっているので、ルータA は自分 のインターフェースがダウンした事は分かりますが、その情報を積極的には 流さず、単に隣接ルータに流す情報から削除します(これを改善するアルゴリズム が Poison reverse です)。

すると、この時点ではルータB のリストは以下のようになります。

ルータBの持つリスト
情報番号 経由ルータ 宛先 コスト
1 D 192.168.0.0/24 4
なんと、B はルータD を経由して 192.168.0.0/24 に到達出来ると 解釈してしまうのです。そして、その結果を隣接ルータに伝達します。 この情報を受け取ったルータD は自身のリストを以下のように 書き換えるでしょう(ルータCからの情報は簡単のために省略して考え ます)。
ルータDの持つリスト
情報番号 経由ルータ 宛先 コスト
1 B 192.168.0.0/24 5
そして、この情報を再びルータBに伝達します。当然、先程とは違って 今度はコストが往復の分だけ上乗せされてコスト6となります。

ルータBの持つリスト
情報番号 経由ルータ 宛先 コスト
1 D 192.168.0.0/24 6
もう分かりましたでしょう。プログラムの無限ループと同じように 無限にカウントするために、コストが一定の値で止まること無く 無限に大きくなっていきます。これを無限カウント問題と言い、 距離ベクトル型ではこれを回避するために、上限を設定します。 つまり、ある値に(あるいはその値以上に)なったらそれを無限で あるとみなす訳です。RIP などでは16が無限であると定めて います。

勿論、ここに掲げた例のような2つのルータ間のピンポンを抑制する ことはそれほど難しくありませんが、メッシュ状に構成された ネットワークの各所にできるループで同じような現象が距離ベクトル型 では発生します。

このように、いくつかの条件においては距離ベクトル型は収束に時間が かかるという欠点を持っています(通常、RIPは30秒に一度メッセージを ブロードキャストあるいはマルチキャストで流します)。 こうした欠点を回避するアルゴリズム も色々と考えられましたが、ネットワークの構造を理解しないという 欠点から来る収束の問題は解決が困難でした。そのために、BGP など では宛先へのコストだけではなく、そこに至る全てのルータのリスト を付加して伝達することで解決を計っています(自分がそのリストに含まれて いたら破棄することでループを抑制します)。このためにBGPは単純 な距離ベクトル型ではなく、パスベクトル型とも分類されます。 勿論、距離ベクトル型を改善する更に複雑なアルゴリズムもありますが、 複雑なアルゴリズムは 逆に収束時間を大きくする傾向にありますので、なかなか難しい問題です。

RIP を考えると、以上のような理由のために大きなネットワークでは 使われていません。しかし、非常に小さなネットワーク(1ないし 2程度のセグメントで構成)の場合には、設定が簡単なので RIP でも 大丈夫でしょう(設定は全くなく、起動するだけなので簡単以上です)。

もっとも、実際的な利用方法は、OSPFなどの他のルーティングプロトコル と併用することでしょう。何故ならば、OSPFが実装されていなくとも、 RIPならば実装されているという場合は非常に多いからです。つまり、 ネットワーク全体のルーティングは OSPF で行い、RIPはそれを末端に 伝達するために使うような場合がそれに当たります。


next up previous contents
Next: 7.3 Zebraの構造 Up: 7. 動的ルーティングとRIP Previous: 7.1.2 ルーティングプロトコルのアルゴリズム
Noriyo Kanayama