距離ベクトルルーティングプロトコル

データ ネットワークの距離ベクトル ルーティング プロトコルは、距離に基づいてデータ パケットの最適なルートを決定します。距離ベクトル ルーティング プロトコルは、パケットが通過するルータの数で距離を測定します。1 台のルータは 1 ホップとしてカウントされます。一部の距離ベクトル プロトコルは、ネットワークの遅延や、特定のルートのトラフィックに影響を与えるその他の要因も考慮します。ネットワーク全体の最適なルートを決定するために、距離ベクトル プロトコルを使用するルータは、通常はルーティング テーブルと宛先ネットワークのホップ カウント、および場合によってはその他のトラフィック情報などの情報を相互に交換します。距離ベクトル ルーティング プロトコルでは、ルータがネットワーク トポロジの変更を近隣のルータに定期的に通知する必要もあります。

距離ベクトル ルーティング プロトコルは、ベルマン フォード アルゴリズムを使用して最適なルートを計算します。ネットワーク全体で最適なルートを計算するもう 1 つの方法は、リンク コストに基づいており、リンク ステート ルーティング プロトコルを通じて実装されます。

距離ベクトルという用語は、プロトコルがネットワーク内の他のノードまでの距離のベクトル(配列) を操作するという事実を指します。距離ベクトル アルゴリズムは、元のARPANETルーティング アルゴリズムであり、ルーティング情報プロトコル(RIP)によってローカル エリア ネットワークでより広く実装されました。

距離ベクトル ルーティング プロトコルは、ベルマンフォード アルゴリズムを使用します。これらのプロトコルでは、各ルータは完全なネットワーク トポロジに関する情報を保持しません。ローカル ネットワークまたは近隣ルータ (ルータ) で変更が行われない限り、ルータは計算された距離値 (DV) を他のルータに通知し、他のルータから同様の通知を受信します。これらのルーティング通知を使用して、各ルータはルーティング テーブルにデータを入力します。次の通知サイクルでは、ルータはルーティング テーブルから更新された情報を通知します。このプロセスは、各ルータのルーティング テーブルが安定した値に収束するまで続きます。

これらのプロトコルの中には、収束が遅いという欠点があるものもあります。

距離ベクトル ルーティング プロトコルの例:

• ルーティング情報プロトコル(RIP)
• ルーティング情報プロトコル バージョン 2 (RIPv2)
• RIPng ( Routing Information Protocol Next Generation ) は、 IPv6をサポートする RIP バージョン 2 の拡張版です。
• 内部ゲートウェイ ルーティング プロトコル(IGRP)
• 拡張内部ゲートウェイ ルーティング プロトコル(EIGRP)

距離ベクトル プロトコルを使用するルーターは、ルーター自身と宛先の間の距離を決定します。データ ネットワークを介したデータの最適ルートは、パケットが宛先ネットワークに到達するために通過しなければならないルーター(ホップ)の数で測定されます。さらに、一部の距離ベクトル プロトコルは、ネットワーク遅延などの他のトラフィック情報も考慮します。最適ルートを確立するために、ルーターは近隣のルーターと定期的に情報 (通常はルーティング テーブル、宛先ネットワークのホップ数、その他のトラフィック関連情報) を交換します。距離ベクトル プロトコルを実装するルーターは、他のルーターから提供される情報のみに依存し、ネットワーク トポロジを評価しません。^[1]

距離ベクトル プロトコルは、ルーターのルーティング テーブルを更新し、ルーターの出口インターフェイスである次のホップと受信ルーターのインターフェイスの IP アドレスによってパケットが送信されるルートを決定します。距離は、特定のノードに到達するためのコストの尺度です。任意の 2 つのノード間の最小コスト ルートは、最小距離のルートです。

距離ベクトル プロトコルでは、定期的に更新が行われ、ルーターのルーティング テーブルのすべてまたは一部が、同じ距離ベクトル ルーティング プロトコルを使用するように設定されているすべての近隣ルーターに送信されます。ルーターがこの情報を取得すると、変更を反映するように自身のルーティング テーブルを修正し、近隣ルーターに変更を通知することができます。このプロセスは、ルーターが他のルーターから受信した情報に依存しており、その情報が実際に有効で真実であるかどうかを判断できないため、「噂によるルーティング」と呼ばれています。不安定で不正確なルーティング情報に対処するために使用できる機能は多数あります。

最も古いルーティング プロトコルであり、最も古い距離ベクトル プロトコルは、ルーティング情報プロトコルのバージョン 1 (RIPv1) です。RIPv1 は 1988 年に正式に標準化されました。^[2] RIPv1 は、ホップ、つまり宛先ネットワークに到達するために通過する必要があるルーターの数に基づいて、ネットワーク全体の最短パスを確立します。RIP は内部ゲートウェイ プロトコルであるため、内部ルーターまたは境界ルーターのローカル エリア ネットワーク(LAN)で使用できます。RIPv1 を実装したルーターは、接続されているすべてのネットワークに 30 秒ごとに RIPv1 パケットをブロードキャストすることにより、近隣ルーターとルーティング テーブルを交換します。RIPv1 はホップ数を 15 に制限しているため、大規模ネットワークには適していません。このホップ制限はルーティング ループを回避するために導入されましたが、15 を超えるルーターを介して接続されているネットワークには到達できないことも意味します。^[3]

ワイドエリアネットワーク(WAN)で使用するために設計された距離ベクトルプロトコルは、ボーダーゲートウェイプロトコル(BGP) です。BGP は外部ゲートウェイプロトコルであるため、インターネット上の境界ルータと外部ルータに実装されています。ルータ間の情報は、伝送制御プロトコル(TCP) セッションを通じて交換されます。BGP を実装したルータは、ホップ以外のさまざまな要因に基づいて、ネットワーク全体の最短パスを決定します。管理者は、特定のルートを優先または回避するように BGP を構成することもできます。BGP は、インターネットサービスプロバイダー(ISP) と通信会社によって使用されています。^[4]

ハイブリッドと説明されている距離ベクトル プロトコルの中には、リンク ステート ルーティング プロトコルに関連するルーティング方法を使用するため、独自のEnhanced Interior Gateway Routing Protocol (EIGRP) があります。これは 1980 年代にシスコによって開発され、リンク ステート ルーティング プロトコルOpen Shortest Path First (OSPF)よりも優れた収束性を提供し、ルータ間のネットワーク トラフィックを減らすように設計されています。^[5]

距離ベクトル ルーティング プロトコルの別の例として、Babelがあります。

ベルマン・フォード アルゴリズムはルーティング ループの発生を防止せず、無限カウント問題に悩まされます。無限カウント問題の核心は、A が B にどこかにパスがあることを伝えた場合、B がそのパスの一部に B が含まれているかどうかを知る方法がないことです。この問題を理解するには、A–B–C–D–E–F のように接続されたサブネットを想像し、ルーター間のメトリックを「ジャンプ数」とします。ここで、A がオフラインになったとします。ベクトル更新プロセスで、B は A へのルート (距離 1) がダウンしていることに気付きます。B は A からベクトル更新を受信しません。問題は、B も C から更新を受信し、C はまだ A がダウンしているという事実を認識していないことです。そのため、B は A が C から 2 ジャンプ (C から B から A) だけであると B に伝えます。B は C から A へのパスが自分自身 (B) を通ることを知らないため、新しい値「B から A = 2 + 1」でテーブルを更新します。その後、B は更新を C に転送し、A は B 経由で到達可能であるという事実 (C の観点から) により、C はテーブルを「C から A = 3 + 1」に更新することを決定します。これは、ネットワークを通じてゆっくりと伝播し、無限大になります (この場合、ベルマンフォードの緩和特性により、アルゴリズムは自動的に修正されます)。

RIP は、ループが形成される可能性を減らすためにポイズン リバース テクニックを使用したスプリット ホライズンを使用し、最大ホップ数を使用して「無限カウント」問題に対処します。これらの対策により、ルーティング ループの形成が回避される場合もありますが、すべてのケースで回避できるわけではありません。[ 6 ^]ホールド タイム の追加(ルート撤回後、数分間ルート更新を拒否する) により、ほぼすべてのケースでループの形成が回避されますが、収束時間が大幅に増加します。

最近では、ループのない距離ベクトル プロトコルが数多く開発されています。注目すべき例としては、EIGRP、DSDV、Babelなどがあります。これらは、すべてのケースでループの形成を回避しますが、複雑さが増すという問題があり、 OSPFなどのリンク ステート ルーティング プロトコルの成功により、その導入は遅れています。

このネットワークには、A、B、C、D の 4 つのルータがあります。

アルゴリズムの現在の時間 (または反復) を T でマークし、各ルータからそのすぐ隣のルータまでの距離マトリックスを作成することから始めます (時間 0、または T=0)。以下のルーティング テーブルを作成すると、最短パスは緑色で強調表示され、新しい最短パスは黄色で強調表示されます。灰色の列は、現在のノードの隣接ノードではないノードを示し、そのためテーブルでは有効な方向とは見なされません。赤色は、ノードからノード自体までの距離、またはノード自体を経由した距離を参照するため、テーブル内の無効なエントリを示します。

• G. Malkin (1998 年 11 月). RIP バージョン 2. ネットワーク ワーキング グループ. doi : 10.17487/RFC2453 . STD 53. RFC 2453. インターネット標準。RFC 1723 および 1388 は廃止されました。RFC 4822 によって更新されました。
• 「ループフリールーティングのためのパス検索アルゴリズム」、JJ Garcia-Luna-Aceves および S. Murthy、IEEE/ACM Transactions on Networking、1997 年 2 月
• 「RIP プロトコルにおける無効なルーティング通知の検出」、D. Pei、D. Massey、L. Zhang、IEEE グローバル コミュニケーション カンファレンス (Globecom)、2003 年 12 月

• セクション「リンク ステート対距離ベクトル」は、Cisco の「インターネットワーキング テクノロジー ハンドブック」の「ルーティングの基本」の章の 2010-12-14 にWayback Machineでアーカイブされています。
• Andrew S. Tanenbaum 著「コンピュータ ネットワーク」第 4 版の「5 ネットワーク層」の章のセクション 5.2「ルーティング アルゴリズム」