メインコンテンツまでスキップ

14. Routing Table Calculation (ルーティングテーブル計算)

本章では、Dijkstra SPF アルゴリズムを使用したルーティングテーブル計算を説明します。

14.1 Dijkstra アルゴリズム概要​

目的​

  • リンクステートデータベースから最短パスツリー (SPF Tree) を構築
  • ルート：計算ルーター自身
  • エッジ重み：リンクコスト

データ構造​

  • 候補リスト: 処理待ちノード
  • SPF ツリー: 処理済みノード
  • ルーティングテーブル: 最終ルート

14.2 アルゴリズム手順​

フェーズ 1: 初期化​

  • ルートノード（自身）を SPF ツリーに追加
  • 距離 = 0

フェーズ 2: SPF ツリー構築​

WHILE 候補リスト非空:
    1. 最小距離のノード V を選択
    2. V を SPF ツリーに追加
    3. V の各隣接ノード W について:
       - 距離を計算
       - 候補リストを更新

等価パス (ECMP)​

  • 同一コストの複数パス
  • すべての等価パスを保持

14.3 ルート計算段階​

エリア内ルート (Intra-Area)​

  • SPF ツリーから生成
  • 最高優先度

エリア間ルート (Inter-Area)​

  • Type 3 LSA から計算
  • 中間優先度

外部ルート (External)​

  • Type 5 LSA から計算
  • Type 1: コスト = 内部 + 外部
  • Type 2: コスト = 外部のみ（デフォルト）

14.4 ルート選択優先順位​

  1. エリア内ルート
  2. エリア間ルート
  3. Type 1 外部ルート
  4. Type 2 外部ルート

計算トリガー​

再計算が必要な場合​

  • LSDB 変更
  • インターフェース状態変更
  • 隣接状態変更

最適化​

  • 遅延計算
  • 増分 SPF (iSPF)

技術要点​

アルゴリズム複雑度​

  • 標準実装: O(N²)
  • 最適化実装: O((E + N) log N)

実装ポイント​

  • 効率的な優先キュー
  • 高速 LSDB 検索
  • 正確な ECMP 処理

参考資料 (References)

に最終更新