距離ベクトルルーティングアルゴリズムの仕組みを説明する

[[122231]]

現代のコンピュータ ネットワークでは、ネットワーク トポロジやトラフィックの変化に適応できるため、一般的に動的ルーティング アルゴリズムが使用されます。最も一般的な 2 つの動的ルーティング アルゴリズムは、「距離ベクトル ルーティング アルゴリズム」と「リンク状態ルーティング アルゴリズム」です。

距離ベクトル ルーティング (DV) は、ARPANET ネットワークで使用された最も初期のルーティング アルゴリズムです。ベルマン フォード ルーティング アルゴリズムやフォード フルカーソン アルゴリズムとも呼ばれます。主に RIP (ルート情報プロトコル) プロトコルで使用されます。 Cisco の IGRP および EIGRP ルーティング プロトコルも DV ルーティング アルゴリズムを使用します。

「距離ベクトル ルーティング アルゴリズム」の基本的な考え方は次のとおりです。各ルータは距離ベクトル テーブル (通常は遅延を変数として含む) を維持し、隣接するルータ間の距離ベクトル通知を通じて距離ベクトル テーブルを更新します。各距離ベクトル テーブル エントリは、宛先ノードへの最適な出力ルートと、宛先ノードに到達するのに必要な時間または距離の 2 つの部分で構成されます。通信サブネット内の他の各ルータは、テーブル内のエントリを占有し、エントリのインデックスとして機能します。ルータは、定期的に、各宛先ノードからの距離テーブルをすべての隣接ノードに送信し、各隣接ノードから送信された距離テーブルも受信します。などなど。一定期間が経過すると、ネットワーク内の各ルータが取得した距離ベクトル情報は各ルータ上で統合されるので、各ルータは距離ベクトル テーブルをチェックするだけで、異なるソースからのパケットに最適なルートを見つけることができます。

ここで、遅延が距離の尺度として使用されていると仮定します。図 7-37 に示すような簡単な例を見てみましょう。ある時点でルータ Y が隣接ルータ X の距離ベクトルを受信すると仮定します。ここで、m はルータ X に到達するまでに Y によって推定される遅延です。ルータ Y が、自分から隣接ルータ Z までの遅延が n であることを知っている場合、ルータ Y は、Z が Y 経由で X に到達するまでに m+n の時間がかかることを知ることができます。ルータ Z に他の隣接ルータがある場合、ルータ Z は他の各隣接ルータから受信した距離ベクトルに対して同じ計算を実行し、最短時間のルートを Z から X への最適ルートとして選択し、ルーティング テーブルを更新して隣接ルータに通知します。

距離ベクトルルーティングアルゴリズムの簡単な例

次の例は、距離ベクトル アルゴリズムにおけるルート決定プロセスを示しています。各リンク セグメントの遅延が図にマークされています。 A、B、C、D、E は 5 つのルータを表します。ルーティング テーブルの送信方向は、A → B → C → D → E であると仮定します (これは、ルータの起動順序に関連します)。具体的な手順は以下のとおりです。

（１）初期状態では、各ルータは直接接続されたリンクの遅延情報のみを収集し、各ルータノードは図7-39に示すように独自の初期ベクトルテーブルを取得します。ノードはまだルーティング情報を交換していないため、初期のルーティング テーブルもベクター テーブルと同様になります。

図7-38 距離ベクトルアルゴリズムによる経路決定の例

初期状態の各ノードのベクトルテーブル

（2）ルータAはルーティングテーブルをルータBに送信します。このとき、ルータAから送信されたルーティングテーブルと自身の初期ルーティングテーブルを組み合わせて、図7-40の左図に示すように、新しいベクターテーブルを更新します（最終的なベクターテーブルは図の暗い部分です）。図からわかるように、ノード B からノード E へのパスは 2 つあり、1 つは直接パスで、もう 1 つはノード A を経由するパスです。さらに、これら2つの回線のコストは異なります。ノードAを経由してノードEに到達するコスト（7）は、直接回線のコスト（8）よりも低くなります。そのため、最終的なルーティングテーブルでは、図7-40の右図に示すように、ノードEに到達する回線がノードAを通過する回線に変更されます。

ノードBの新しいベクターテーブルとルーティングテーブル

（３）Bは最終的なルーティングテーブルをルータCに送信します。同様に、ルータ C も、図 7-41 の左側に示すように、元の初期ルーティング テーブルとルータ B から送信されたルーティング テーブルを組み合わせて、新しいベクター テーブルを形成する必要があります (最終的なベクター テーブルは、図の暗い部分に表示されます)。新しいベクトルテーブルでは、ノード B と D 間の元の直接接続されたベクトルに加えて、ノード A と E に到達するベクトル情報も新たに収集されます。ノード C はノード A および E と直接接続されていないため、初期ルーティング テーブルにはこれらの 2 つのノードに到達するためのルーティング情報がありません。したがって、ルータ B によって送信されたルーティング テーブルからのパスを使用して、ノード B 経由でノード A および E に到達することしかできません。 #p#

ここで注目すべき点は、ノード B のルーティング テーブルでは、ノード B を経由して直接ノード E に到達するコスト (8) が、ノード B とノード A を順番に経由してノード E に到達するコスト (7) よりも大きいことがすでにわかっているため、ノード C のルーティング テーブルでは、ノード B とノード A を順番に経由してノード E に到達するパスが採用されることです。最終的なルーティング テーブルを図 7-41 の右側に示します。

ノードCの新しいベクターテーブルとルーティングテーブル

（4）ルータCは最終的なルーティングテーブルをルータDに送信します。同様に、ルータ D も、図 7-42 の左側に示すように、元の初期ルーティング テーブルとルータ C から送信されたルーティング テーブルを組み合わせて、新しいベクター テーブルを形成する必要があります (最終的なベクター テーブルは、図の暗い部分に表示されます)。新しいベクトルテーブルでは、直接接続された C ノードと E ノード間の元のベクトル情報に加えて、A ノードと B ノードに到達するベクトル情報も新たに収集されます。ノード D はノード A および B と直接接続されていないため、初期ルーティング テーブルにはこれら 2 つのノードに到達するためのベクトル情報がありません。この時点では、ノード C を経由してノード A および B に到達するパスが引き続き使用されます。

ここで注目すべき重要な点は、ノード D からノード E へのパスが 2 つあることです。1 つは直接到達するパス、もう 1 つはノード C、B、A を順に経由して到達するパスです。比較すると、直接接続のコスト (2) は、ノード C、B、A を経由してノード E に到達するパスのコスト (10) よりも小さいことがわかり、そのためノード D では直接接続ルートを使用してノード E に到達します。最終的なルーティング テーブルを図 7-42 の右側に示します。

（５）ルータDは最終的なルーティングテーブルをルータEに送信します。同様に、ルータ E も、図 7-43 の左側に示すように、元の初期ルーティング テーブルとルータ D から送信されたルーティング テーブルを組み合わせて、新しいベクター テーブルを形成する必要があります (最終的なベクター テーブルは、図の暗い部分に表示されます)。新しいベクトル テーブルでは、ノード A、B、D 間の元の直接接続されたベクトルに加えて、ノード E はノード C と直接接続されていないため、ノード C に到達するベクトル情報も新たに収集されます。このとき、ノード D を経由してノード C に到達するパスはまだ使用されます。

Dノードの新しいベクターテーブルとルーティングテーブル

ここで注意すべき点が 2 つあります。1 つは、ノード E からノード A へのパスの問題です。この時点では、ノード E とノード A は直接接続されており、そのコスト (1) は、ルータ D からノード D、C、B を経由してノード A に送信された元のルーティング テーブルのパス コスト (11) よりも小さくなります。したがって、ノード E の最終的なルーティング テーブルでは、ノード A へのルートは直接接続になります。 2番目に、ノードEもノードBに直接接続されていますが、そのコスト（8）は、ルータDから最初に送信されたルーティングテーブルに示されているように、ノードDとCを順番に通過してノードBに到達するコスト（5）よりも大きくなります。したがって、ノードEの最終的なルーティングテーブルでは、ノードBに到達するためのパスは、ノードDとCを順番に通過することになります。最終的なルーティング テーブルを図 7-43 の右側に示します。

Eノードの新しいベクターテーブルとルーティングテーブル

上記の手順により、ネットワーク内の各ルータはルーティングテーブル全体の決定を完了しました。もちろん、トポロジが変更されると、各ルータのルーティングテーブルも変更されるため、再度更新する必要があります。