完全なルーティングアルゴリズムの設計目標の分析

ルーティング アルゴリズムには通常、次の 1 つ以上の設計目標があります。

最適化：

最適化とは、メトリックの値と重みに基づいて計算される最適なパスを選択するルーティング アルゴリズムの機能を指します。たとえば、ルーティング アルゴリズムではホップ カウントと遅延の両方が使用される場合がありますが、遅延の方が重み付けが大きい場合があります。もちろん、ルーティング プロトコルはメトリックを計算するためのアルゴリズムを厳密に定義する必要があります。

シンプルで低消費：

ルーティング アルゴリズムも、可能な限りシンプルになるように設計できます。言い換えれば、ルーティング プロトコルは、ソフトウェアとアプリケーションのオーバーヘッドを最小限に抑えながら、効率的に機能を提供する必要があります。ルーティング アルゴリズムを実装するソフトウェアを、物理リソースが限られたコンピューター上で実行する必要がある場合、効率は特に重要です。

堅牢で安定:

ルーティング アルゴリズムは堅牢である必要があり、ハードウェア障害、高負荷、不適切な実装などの異常なイベントや予期しないイベントに対処できる必要があります。ルータはネットワークの接続ポイントに配置されているため、故障すると大きな問題を引き起こす可能性があります。最良のルーティング アルゴリズムとは、通常、長期間の使用に耐え、さまざまなネットワーク条件下で安定していることが証明されているアルゴリズムです。

高速集約:

さらに、ルーティング アルゴリズムは、すべてのルータが最適なパスについて合意に達するプロセスである収束を迅速に実行できる必要があります。ネットワーク イベントによってパスが切断されたり使用できなくなったりすると、ルータはネットワークを通じてルーティング更新情報を配布し、*** パスの再計算を促して、最終的にすべてのルータが合意に達することができるようにします。収束が遅いルーティング アルゴリズムでは、ルーティング ループやネットワーク停止が発生する可能性があります。

下の図のルーティング リングでは、パケットは時刻 t1 にルータ 1 に到着します。ルータ 1 は更新されており、宛先への最適なパスはルータ 2 をネクスト ホップとすることであると認識しているため、パケットをルータ 2 に転送します。ただし、ルータ 2 はまだ更新されていません。ルータ 2 は最適なネクスト ホップはルータ 1 であると判断しているため、パケットをルータ 1 に送り返します。その結果、ルータ 2 がルーティング更新情報を受信するか、パケットの有効期限が切れるまで、パケットは 2 つのルータ間でやり取りされます。

柔軟性

ルーティング アルゴリズムも柔軟である必要があり、さまざまなネットワーク環境に迅速かつ正確に適応する必要があります。たとえば、ネットワーク セグメントがダウンしているとします。問題が判明すると、多くのルーティング アルゴリズムでは、通常そのセグメントを使用するパスの次善のパスがすぐに選択されます。ルーティング アルゴリズムは、ネットワーク帯域幅、ルーターのキュー サイズ、およびネットワーク遅延に適応するように設計できます。