拡散更新アルゴリズム

拡散更新アルゴリズム（DUAL）は、CiscoのEIGRP ^[1]ルーティングプロトコルで使用されるアルゴリズムであり、ルーティングループが発生する可能性がある場合は常に、特定のルートがグローバルに再計算されるようにします。これは、SRI InternationalのJJ Garcia-Luna-Acevesによって開発されました。アルゴリズムの正式名称は、DUAL有限状態マシン（DUAL FSM）です。EIGRPは自律システム内のルーティングを担当し、DUALはルーティングトポロジの変更に応答して、ルーターのルーティングテーブルを自動的に動的に調整します。

EIGRP は、ループのないルートのみが選択されるようにするために、実現可能性条件を使用します。実現可能性条件は保守的です。条件が真である場合、ループは発生しませんが、状況によっては、一部がループのないルートであっても、宛先へのすべてのルートが拒否される可能性があります。

目的地への実行可能な経路がない場合、DUALアルゴリズム^[2]は拡散計算^[3]を呼び出し、問題のある経路の痕跡がすべてネットワークから除去されるようにします。この時点で、通常のベルマンフォードアルゴリズムを使用して新しい経路を回復します。

DUAL は、ルート計算に 3 つの個別のテーブルを使用します。これらのテーブルは、EIGRP ルータ間で交換される情報を使用して作成されます。この情報は、リンク ステート ルーティング プロトコルによって交換される情報とは異なります。EIGRP では、交換される情報には、ルート、各ルートの「メトリック」またはコスト、およびネイバー関係を形成するために必要な情報 (AS 番号、タイマー、K 値など) が含まれます。3 つのテーブルとその機能の詳細は、次のとおりです。

• ネイバー テーブルには、直接接続されている他のすべてのルーターの情報が含まれています。サポートされているプロトコル (IP、IPX など) ごとに個別のテーブルが存在します。各エントリは、ネットワーク インターフェイスとアドレスの説明を持つネイバーに対応しています。さらに、接続がアクティブであるかどうかを定期的に検出するためのタイマーが初期化されます。これは、「Hello」パケットによって実現されます。指定された期間内にネイバーから「Hello」パケットを受信しない場合、ルーターはダウンしていると見なされ、ネイバー テーブルから削除されます。
• トポロジ テーブルには、自律システム内の任意の宛先へのすべてのルートのメトリック (コスト情報) が含まれています。この情報は、ネイバー テーブルに含まれる隣接ルータから受信されます。宛先へのプライマリ (後続) ルートとセカンダリ (実行可能な後続) ルートは、トポロジ テーブルの情報を使用して決定されます。特に、トポロジ テーブルの各エントリには次の情報が含まれています。

「FD (実行可能距離)」: 自律システム内の目的地までのルートの計算されたメトリック。

「RD (報告距離)」: 隣接ルータによって通知される宛先までのメトリック。RD は、FD を計算し、ルートが「実現可能性条件」を満たしているかどうかを判断するために使用されます。

ルート ステータス: ルートは「アクティブ」または「パッシブ」のいずれかでマークされます。「パッシブ」ルートは安定しており、データ転送に使用できます。「アクティブ」ルートは再計算中であるか、使用できません。

• ルーティング テーブルには、宛先への最適なルート (最も低い「メトリック」の観点から) が含まれています。これらのルートは、トポロジ テーブルからの後継ルートです。

DUAL は、トポロジ テーブル内の他のルータから受信したデータを評価し、プライマリ (後継) ルートおよびセカンダリ (実行可能な後継) ルートを計算します。プライマリ パスは通常、宛先に到達するためのメトリックが最も低いパスであり、冗長パスは 2 番目にコストが低いパスです (実行可能条件を満たしている場合)。後継パスと実行可能な後継パスは複数存在する場合があります。後継パスと実行可能な後継パスは両方ともトポロジ テーブルに保持されますが、ルーティング テーブルに追加され、パケットのルーティングに使用されるのは後継パスのみです。

ルートが実行可能な後継ルートになるためには、その RD が後継ルートの FD より小さくなければなりません。この実行可能性条件が満たされている場合、このルートをルーティング テーブルに追加してもループが発生することはありません。

宛先への後続ルートがすべて失敗した場合、実行可能な後続ルートが後続ルートとなり、すぐにルーティング テーブルに追加されます。トポロジ テーブルに実行可能な後続ルートがない場合、新しいルートを探すためのクエリ プロセスが開始されます。

伝説：

+ = ルーター

− または | = リンク

(X) = リンクのメトリック

     A (2) B (1) C
     + - - - - - + - - - - - +
                 | |
              （2）| | （3）
                 | |
                 + - - - - - +
                 D (1) イー

ここで、ルータ E 上のクライアントはルータ A 上のクライアントと通信したいと考えています。つまり、ルータ A とルータ E 間のルートが利用可能である必要があります。このルートは次のように計算されます。

ルータ E のすぐ隣にはルータ C とルータ D があります。ルータ E の DUAL は、ルータ C と D からルータ A までの報告距離 (RD) をそれぞれ要求します。結果は次のとおりです。

宛先: ルータA

D経由：RD(4)

C経由:RD(3)

したがって、C 経由のルートはコストが最も低くなります。次のステップでは、ルータ E から隣接ルータまでの距離が報告された距離に追加され、実現可能な距離 (FD) が算出されます。

宛先: ルータA

D経由：RD(4)、FD(5)

C経由：RD(3)、FD(6)

したがって、DUAL は、D 経由のルートの総コストが最も低いことを検出します。次に、D 経由のルートは「後継」としてマークされ、パッシブ ステータスが付与され、ルーティング テーブルに登録されます。C 経由のルートは、RD が後継の FD よりも小さいため、「実行可能な後継」として保持されます。

宛先: ルータA

D経由：RD(4)、FD(5)後継

C経由: RD(3)、FD(6) 実行可能な後継