データの通るルートを決める方法［後編］

Pict3.適応的ルーティングの方法は二つ

[画像のクリックで拡大表示]

あて先までに経由するルーターの数で決める

　適応的ルーティングで使われる代表的な方式は2種類あります。それぞれ距離ベクトル・アルゴリズム，リンク状態アルゴリズムと呼ばれます（pict.3[拡大表示]）。

　距離ベクトル・アルゴリズムはその名の通り，目的地までの距離でルートを決める方法です。具体的にはあて先のネットワークに到達するために経由するルーターの数で距離を測ります。これをホップ数と呼びます。１ホップであれば，1個のルーターを経由します。ルーターはホップ数がいちばん少ない経路を選び，パケットを送り出します。

　距離ベクトル・アルゴリズムでは，それぞれのルーターがあて先のネットワークに対するホップ数を管理します。さらに，この距離情報が集まった一覧表（これを距離ベクトルと呼びます）を隣接したルーター間で交換します（pict.3の左）。

　図ではルーターAと隣接するルーターBから受け取った距離ベクトル情報を受け取っています。この距離ベクトル情報は，ルーターBからそれぞれのあて先までのホップ数の集まりです。ルーターBの距離ベクトルにそれぞれ１ホップ加えれば，ルーターAからルーターBを経由してパケットを送る場合のホップ数になります。ルーターAは，同じ目的地について，この値と自分自身が持っている距離ベクトルを比べます。その結果，ホップ数が小さいのものを見つけたら，ルーターBを経由するように経路表を書き換えます。

　距離ベクトル・アルゴリズムは相互接続されたルーターの台数が増えると，欠点が目立ってきます。ネットワークの状況変化を個別のルーターが伝言ゲームのように順番に伝えるので，台数が増えると変化が全体に伝わるまでにとても時間がかかるのです。また，伝える途中で間違った情報になることもあります。

リンクの状態をブロードキャストする

　こうした欠点を解消できるのが，リンク状態アルゴリズムです（pict.3の右）。リンク状態アルゴリズムではルーターが隣り合うルーターとのリンクの状態を監視します。リンクが切れたり，復旧したり，新たなリンクが加わったりしたら，ルーターはその情報をネットワーク上にブロードキャストします。

　それぞれのルーターがリンク状態をブロードキャストした情報を集めると，ネットワーク上にどんなルーターが存在し，それぞれどのように接続しているかがわかります。つまり，ネットワーク全体の地図を自分で作れるわけです。ちょうどカーナビが地図を基に経路を見つけだすのと同じように，ルーターは自分で作成したネットワーク全体の地図を使って，あて先ネットワークまでの最短のルートを計算できます。ブロードキャストする情報として，リンクの接続状態だけでなく，リンクの通信速度や混雑状況を加えておけば，より効率的なルートを選ぶことも可能です。

　リンク状態アルゴリズムでは障害に対してそれぞれのルーターが経路を切り替えるまでが迅速です。障害の情報がブロードキャストで伝わるからです。

　IPネットワークで使われる距離ベクトル・アルゴリズムを用いたルーティング・プロトコルの代表例はRIP（リップ）（routing information protocol）です。RIPは，初期に開発されたため，距離ベクトル・アルゴリズム特有の問題点のほか，扱えるホップ数に上限があるなど，大規模のネットワークには適用しにくい欠点もありました。そのため，企業ネットワークなどでは現在，リンク状態アルゴリズムを使ったOSPF（open shortest path first）と呼ばれるルーティング・プロトコルが広く使われています

　RIPとOSPFは一つの組織内で使われるのを想定したルーティング・プロトコルです。インターネットではこうした組織間を接続するためのルーティング・プロトコルも使われています。こうしたプロトコルの代表例はBGP（border gateway protocol）です。BGPは距離ベクトル・アルゴリズムを使っています。