ルーティングの基本アルゴリズム設計の目標とタイプ

基本的なルーティング アルゴリズムの設計目標とタイプは、基本的なルーティング アルゴリズムに関する知識の一部を理解するのに役立ちます。まず、アルゴリズム設計者の特定の目標がルーティング プロトコルの動作に影響します。次に、ルーティング アルゴリズムは複数存在し、それぞれがネットワークとルーターのリソースに異なる影響を及ぼします。最後に、ルーティング アルゴリズムは、最適なパスの計算に影響するさまざまなメトリックを使用します。次のセクションでは、これらのルーティング アルゴリズムの特性を分析します。

1. 基本的なルーティングアルゴリズムの設計目標

ルーティング アルゴリズムには通常、次の 1 つ以上の設計目標があります。
◆最適化◆シンプル、低消費◆堅牢、安定◆高速集約◆柔軟性

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

ルーティングの基礎 ルーティングアルゴリズム

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

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

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

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

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

2. 基本的なルーティングアルゴリズムの種類

ルーティング アルゴリズム間の違いは次のとおりです。
◆静的 vs. 動的 ◆単一パス vs. マルチパス ◆フラット vs. 階層型 ◆ホストインテリジェンス vs. ルーターインテリジェンス ◆ドメイン内 vs. ドメイン間 ◆リンク状態 vs. 距離ベクトル

（１）静的と動的

静的ルーティング アルゴリズムはアルゴリズムとはほとんど考えられず、ルーティングが開始される前にネットワーク管理者によって作成されるテーブル マッピングにすぎません。これらのマッピング自体は、ネットワーク管理者によって変更されない限り変更されません。静的ルーティングを使用するアルゴリズムは設計が容易で、ネットワーク トラフィックが予測可能で単純なネットワークで適切に機能します。静的ルーティング システムはネットワークの変更に対応できないため、今日の大規模で不安定なネットワークには不適切であると一般的に考えられています。

1990 年代の主なルーティング アルゴリズムは、受信したルーティング更新情報を分析してネットワーク環境の変化に適応する動的ルーティング アルゴリズムでした。情報によってネットワークが変更されたことが示される場合、ルーティング ソフトウェアはルートを再計算し、新しいルーティング更新を送信します。この情報はネットワーク全体に伝わり、ルータはルーティング テーブルを再計算し、対応する変更を加えます。動的ルーティング アルゴリズムは、適切な場合には静的ルーティングによって補完できます。たとえば、ルーティングできないすべてのパケットのパスである最後の手段のルーターは、すべてのデータが少なくとも 1 つの方法で処理されることを保証します。

（２）シングルパスとマルチパス

一部の複雑なルーティング プロトコルは、同じ宛先への複数のパスをサポートします。単一パス ルーティング ベースのアルゴリズムとは異なり、これらのマルチパス アルゴリズムでは、データを複数の回線にわたって多重化できます。マルチパス アルゴリズムの利点は明らかです。より優れたスループットと信頼性を実現できます。

（３）平坦性と成層性

一部のルーティング プロトコルはフラットな空間で動作しますが、他のルーティング プロトコルは階層構造になっています。フラット ルーティング システムでは、各ルータは他のすべてのルータとピアです。階層型ルーティング システムでは、複数のルータがルーティング バックボーンを形成し、データは非バックボーン ルータからバックボーン ルータに流れ、宛先エリアに到達するまでバックボーン上を移動します。宛先エリアでは、最後のバックボーン ルータから 1 つ以上の非バックボーン ルータを経由して宛先に渡されます。

ルーティング システムは通常、ドメイン、自律システム、または間隔と呼ばれるノードの論理グループを使用して設計されます。階層型システムでは、一部のルータは他のドメインのルータと通信できますが、他のルータは自身のドメイン内のルータとのみ通信できます。非常に大規模なネットワークでは、追加のレベルが存在する場合があり、最上位レベルのルーターがルーティング バックボーンを形成します。

階層型ルーティングの主な利点は、ほとんどの企業の構造を模倣し、通信を適切にサポートすることです。ほとんどのネットワーク通信はグループ (ドメイン) 内で行われます。ドメイン内のルータはドメイン内の他のルータのみを認識していればよいため、ルーティング アルゴリズムを簡素化でき、使用するルーティング アルゴリズムに応じて、ルーティング更新トラフィックの量を削減できます。

（4）ホストインテリジェンスとルーターインテリジェンス

一部のルーティング ベースのアルゴリズムでは、ソース ノードがパス全体を決定すると想定しており、これは通常、ソース ルーティングと呼ばれます。ソース ルーティング システムでは、ルータはストア アンド フォワード デバイスとしてのみ機能し、無意識のうちにパケットを次のホップに送信します。他のルーティング アルゴリズムでは、ホストがパスを認識していないことを前提としています。これらのアルゴリズムでは、ルータが独自の計算に基づいてネットワーク上のパスを決定します。前者のシステムでは、ホストがルートを決定するインテリジェンスを持ちますが、後者のシステムでは、ルーターがこの機能を持ちます。

ホスト インテリジェンスとルーター インテリジェンス間のトレードオフは、実際には最適なルーティングと追加のオーバーヘッドの間のバランスです。ホスト インテリジェント システムは、データを送信する前にすべての可能なパスを探索し、特定のシステムの「最適」の定義に基づいて最適なパスを選択するため、多くの場合、より適切なパスを選択できます。ただし、すべてのパスの動作を決定するには、通常、大量の探索トラフィックと長い時間が必要になります。

（５）ドメイン内とドメイン間

ルーティング アルゴリズムの中には、ドメイン内でのみ機能するものもあれば、ドメイン内とドメイン間の両方で機能するものもあります。これら 2 つのアルゴリズムの性質は異なります。この理由は、最適化されたドメイン内ルーティング アルゴリズムは、最適化されたドメイン間ルーティング アルゴリズムである必要がないためです。

（６）リンク状態と距離ベクトル

リンク ステート アルゴリズム (最短パス ファースト アルゴリズムとも呼ばれます) は、ネットワーク内のすべてのノードにルーティング情報を拡散しますが、各ルータは自身のリンク ステートを記述するルーティング テーブルの部分のみを送信します。距離ベクトル アルゴリズム (ベルマンフォード アルゴリズムとも呼ばれる) では、各ルータはルーティング テーブルのすべてまたは一部を近隣ルータにのみ送信します。つまり、リンク ステート アルゴリズムはすべての場所に更新を送信する回数が少なくなりますが、距離ベクトル アルゴリズムは隣接ルータにのみ更新を送信します。

リンクステート アルゴリズムは収束が速いため、距離アルゴリズムよりもルーティング ループが発生する可能性が低くなります。一方、リンク ステート アルゴリズムではより多くの CPU およびメモリ リソースが必要になるため、リンク ステート アルゴリズムの実装とサポートにはコストがかかります。違いはあるものの、どちらのアルゴリズム タイプもほとんどの環境で適切に機能します。

3. ルーティングの基本アルゴリズムルーティングメトリック

ルーティング テーブルには、スイッチング ソフトウェアが最適なパスを選択するために使用する情報が含まれています。しかし、ルーティング テーブルはどのように作成されるのでしょうか?そこに含まれる情報の性質は何ですか?ルーティング アルゴリズムは、この情報に基づいてどのパスが最適かをどのように決定するのでしょうか?ルーティング アルゴリズムは、さまざまなメトリックを使用して最適なパスを決定します。複雑なルーティング アルゴリズムでは、複数のメトリックに基づいてルートを選択し、それらを複合メトリックに組み合わせることができます。一般的に使用されるメトリックは次のとおりです。
◆ パスの長さ ◆ 信頼性 ◆ 遅延 ◆ 帯域幅 ◆ 負荷 ◆ 通信コスト

パスの長さは、最も一般的に使用されるルーティング メトリックです。一部のルーティング プロトコルでは、ネットワーク管理者が各ネットワーク リンクにコスト値を手動で割り当てることができます。この場合、ルートの長さは通過する各リンクのコストの合計になります。その他のルーティング プロトコルはホップ数を定義します。ホップ数とは、パケットが送信元から宛先までの間に通過しなければならないルーターなどのネットワーク製品の数です。

ルーティング ベースのアルゴリズムにおける信頼性とは、ネットワーク リンクの信頼性を指します (通常はビット エラー レートで表されます)。一部のネットワーク リンクは他のリンクよりも頻繁に障害が発生する可能性があり、ネットワーク障害が発生した後、一部のネットワーク リンクは他のリンクよりも修復が容易または高速である可能性があります。信頼性値を割り当てる際には、通常、ネットワーク管理者がネットワーク リンクにメトリック値を割り当てることによって、あらゆる信頼性要因を考慮に入れることができます。

ルーティング遅延とは、パケットが送信元からネットワークを経由して宛先まで移動するのにかかる時間を指します。中間ネットワーク リンクの帯域幅、通過する各ルーターのポート キュー、すべての中間ネットワーク リンクの輻輳レベル、物理的な距離など、多くの要因がレイテンシに影響します。レイテンシはいくつかの重要な変数が混在しているため、一般的かつ効果的なメトリックです。

帯域幅とは、リンク上で利用可能なトラフィック容量を指します。他の条件が同じであれば、10Mbps のイーサネット リンクは 64kbps の専用回線よりも優れています。帯域幅はリンク上で達成可能な最大スループットですが、帯域幅の大きいリンクを介したルーティングが、低速のリンクを介したルーティングよりも必ずしも優れているとは限りません。たとえば、高速リンクがビジー状態の場合、パケットが宛先に到達するまでに時間がかかることがあります。

負荷とは、ルーターなどのネットワーク リソースの使用状況を指します。負荷は、CPU 使用率や 1 秒あたりに処理されるパケット数など、さまざまな方法で計算できます。これらのパラメータを継続的に監視することは、それ自体が大量のリソースを消費します。通信コストは、パフォーマンスよりも運用コストを重視する企業もあるため、もう 1 つの重要な指標です。回線の遅延が長くなる可能性はありますが、高価な公衆回線を使用するよりも、自社の回線でデータを送信することを望んでいます。