ルーティングアルゴリズムの概念

この記事では主にルーティング アルゴリズムの概念を説明し、ルーティング アルゴリズムの基本的な概念を紹介します。この記事を詳しく読むことで、ルーティング アルゴリズムについてよく知らない読者は、より明確な理解を得ることができます。

ルーティング アルゴリズムは、ルーティング プロトコルが機能を効率的に提供し、ソフトウェアとアプリケーションのオーバーヘッドを最小限に抑えるために実行する必要があるものです。ルーティング アルゴリズムを実装するソフトウェアを、物理リソースが限られたコンピューター上で実行する必要がある場合、効率は特に重要です。ルーティング アルゴリズムの原則 ルーティング アルゴリズムは堅牢である必要があります。つまり、ハードウェア障害、高負荷、不適切な実装などの異常なイベントや予期しないイベントに対処できる必要があります。ルータはネットワークの接続ポイントに配置されているため、故障すると大きな問題を引き起こす可能性があります。最良のルーティング アルゴリズムとは、通常、長期間の使用に耐え、さまざまなネットワーク条件下で安定していることが証明されているアルゴリズムです。さらに、ルーティング アルゴリズムは、すべてのルータが最適なパスについて合意に達するプロセスである収束を迅速に実行できる必要があります。ネットワーク イベントによってパスが切断されたり使用できなくなったりすると、ルータはネットワーク全体にルーティング更新情報を配布し、最適なパスの再計算を促して、最終的にすべてのルータが合意に達することができるようにします。収束が遅いルーティング アルゴリズムでは、ルーティング ループやネットワーク停止が発生する可能性があります。

ルーティング アルゴリズムは、非適応型と適応型に分けられます。非適応型アルゴリズムは、トラフィックとトポロジの現在の測定値や推定値に基づいてルーティングの決定を調整しません。このプロセスは静的ルーティングとも呼ばれます。対照的に、適応型アルゴリズムは、トポロジの変化、通常はトラフィック量の変化を反映してルーティングの決定を変更します。このプロセスは動的ルーティングと呼ばれます。

ルーティング アルゴリズムは、着信パケットをどの発信回線に送信するかを決定するネットワーク層ソフトウェアの一部です。サブネット内でデータグラムが使用されている場合、最適なパスは最後にパスが選択されてから変更されている可能性があるため、ルータは到着するデータ パケットごとにパスを再選択する必要があります。サブネット内で仮想回線が使用されている場合、新しい仮想回線が確立されたときにのみルーティング パスを決定する必要があります。したがって、データ パケットは確立されたパスに沿って転送されるだけで済みます。ルーティング パスがパケットごとに独立して選択されるか、または新しい接続が確立されたときにのみルーティング パスが選択されるかどうかにかかわらず、ルーティング アルゴリズムには、正確性、単純性、堅牢性、安定性、公平性、最適性などの特性が必要です。

ルーターはルーティング アルゴリズムを使用して、宛先までの最適なルートを見つけます。 「最適なルート」について話すとき、考慮されるパラメータには、ホップ数 (パケットがネットワーク内の 1 つのルータまたは中間ノードから別のルータまたは中間ノードまで移動する距離)、待ち時間、パケットが移動するのにかかる通信時間などが含まれます。ルーティング アルゴリズムのフローチャート ルータがネットワークの構造情報を収集し、それを分析して最適なルートを決定する方法については、全体的なルーティング アルゴリズムと分散ルーティング アルゴリズムという 2 つの主要なルーティング アルゴリズムがあります。分散型ルーティング アルゴリズムでは、各ルータには、ネットワーク内のすべてのルータの情報ではなく、直接接続されているルータの情報のみが保持されます。これらのアルゴリズムは、DV (距離ベクトル) アルゴリズムとも呼ばれます。総合的なルーティング アルゴリズムを使用する場合、各ルータにはネットワーク内の他のすべてのルータに関するすべての情報と、ネットワークのトラフィックの状態が保持されます。これらのアルゴリズムは、LS (リンク ステート) アルゴリズムとも呼ばれます。