RIPでルーティングテーブルにルートを載せる規則

ベルマンフォードアルゴリズム

RIPパケットを受け取ったルータは、RIPパケット内のネットワークのエントリがすでに自分のルーティングテーブルに存在しているか、それとも存在していないか。
もし、存在しているなら、メトリックやネクストホップアドレスが何であるかといった情報に基づいて、ルーティングテーブルに載せるかどうかを判断しています。この判断のアルゴリズムのことを
「ベルマンフォードアルゴリズム」といいます。

ベルマンフォードアルゴリズムは、次の図のようになります。





ベルマンフォードアルゴリズムによるルーティングテーブルの更新のパターンは次の3種類あります。


1.ルーティングテーブル上にエントリがない場合
2.ルーティングテーブル上にエントリが存在し、ネクストホップアドレスが異なる場合
3.ルーティングテーブル上にエントリが存在し、ネクストホップアドレスが同一の場合




ベルマンフォードアルゴリズムの例

実際のルーティングテーブルを例にとって、ベルマンフォードアルゴリズムの動きを確認しましょう。現在次のようなルーティングテーブルがあるとします。


ネットワーク ネクストホップ メトリック(ホップ数)
10.0.0.0/8 ルータA 2
20.0.0.0/8 ルータB 3


まず1つ目のパターンです。ルータAから、RIPで(30.0.0.0,3)というアップデートを受け取ったとします。この場合、ルーティングテーブル上に30.0.0.0のエントリはありません。またアップデートに含まれるホップ数は16よりも小さいので、ルーティングテーブルに追加されることになります。


ネットワーク ネクストホップ メトリック(ホップ数)
10.0.0.0/8 ルータA 2
20.0.0.0/8 ルータB 3
30.0.0.0/8 ルータA 3


次に2つめのパターンです。ルータCから(20.0.0.0,4)というアップデートを受け取ったとします。20.0.0.0のエントリはすでにルーティングテーブルに存在します。次にネクストホップアドレスを比べます。ルーティングテーブル上のネクストホップアドレスと受信したアップデートのネクストホップアドレスが異なっています。そのときには、ホップ数の小さいものが優先されます。
この場合は、もともとのルーティングテーブル上にあるエントリのホップ数の方が小さいのでルーティングテーブルはそのままです。

もし、他のルータDから(20.0.0.0,2)というアップデートを受信すると、
こちらのホップ数がルーティングテーブル上のものより小さいので、次のようにルーティングテーブルが書き換わります。


ネットワーク ネクストホップ メトリック(ホップ数)
10.0.0.0/8 ルータA 2
20.0.0.0/8 ルータD 2
30.0.0.0/8 ルータA 3


そして、最後に3つ目のパターンを考えます。ルータAから(10.0.0.0,3)というアップデートを受け取ったときを考えます。すでに10.0.0.0はルーティングテーブル上にあるので、ネクストホップアドレスを比べると同じアドレスです。
ルーティングテーブル上のエントリのネクストホップアドレスと、受信したアップデートのネクストホップアドレスが同一の場合はホップ数に関係なく、次のようなルーティングテーブルになります。


ネットワーク ネクストホップ メトリック(ホップ数)
10.0.0.0/8 ルータA 3
20.0.0.0/8 ルータD 2
30.0.0.0/8 ルータA 3



以前に教えてもらったネクストホップ(ルータ)からの情報は正しいものだろうという仮定に基づいて、このような動作を行っています。しかし、
この動作はルーティングループが発生する主な要因となってしまいます。







『ネットワークのおべんきょしませんか?』 を購読しませんか?
めろんぱん E-mail
メールマガジンも購読してくださいね!!購読者限定のプレゼントあり!!


(C) Copyright 2000-2004 Gene All Rights Reserved