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

2. The Link-state Database: Organization and Calculations (リンクステートデータベース：組織と計算)

本章では、OSPF リンクステートデータベースの組織構造と、このデータベースを使用してルーティングテーブルを計算する方法について説明します。

章の概要 (Chapter Overview)​

本章では以下の主要トピックをカバーします：

  • ルーターとネットワークの表現方法
  • 最短経路ツリーの構築
  • 外部ルーティング情報の使用
  • 等コストマルチパスの実装

2.1 Representation of Routers and Networks (ルーターとネットワークの表現)​

核心概念 (Core Concepts)​

グラフ理論表現 (Graph Representation)

  • 自律システムは有向グラフとしてモデル化 (AS modeled as directed graph)
  • 頂点 (Vertices)：ルーターとネットワーク
  • エッジ (Edges)：ルーターインターフェース
  • コスト (Cost)：各エッジの重み

ルーター表現 (Router Representation)

  • ルーター ID：32 ビットの一意識別子
  • インターフェースリスト：ネットワークに接続されたインターフェース
  • ネイバー関係：隣接ルーターとの接続
  • リンク状態：各インターフェースの状態情報

ネットワークタイプ (Network Types)

ネットワークタイプ英語特徴例
ポイントツーポイントPoint-to-Point2 つのルーターを接続T1 回線、PPP
ブロードキャストBroadcastマルチアクセス、ブロードキャストサポートEthernet、Token Ring
NBMANon-Broadcast Multi-Accessマルチアクセス、ブロードキャスト非対応Frame Relay、X.25
ポイントツーマルチポイントPoint-to-MultiPointポイントツーポイントリンクの集合として処理パーシャルメッシュ Frame Relay

2.1.1 Representation of Non-broadcast Networks (非ブロードキャストネットワークの表現)​

NBMA ネットワーク特性 (NBMA Network Characteristics)

  • リンク層ブロードキャストまたはマルチキャスト非対応
  • 手動でのネイバー設定が必要
  • 指定ルーター (DR) とバックアップ指定ルーター (BDR) の選出が必要
  • フルメッシュ接続またはポイントツーマルチポイントモードが必須

設定要件 (Configuration Requirements)

  • ネイバーリスト設定
  • DR 優先度設定
  • Hello 間隔と Dead 間隔
  • ポーリング間隔 (Poll Interval)

このセクションでは、具体例を通じてリンクステートデータベースの構造と内容を示します。

ネットワークトポロジー例 (Example Network Topology)

  • 複数のルーターの相互接続
  • 異なるタイプのネットワーク
  • エリア分割
  • 仮想リンク

LSA タイプ (LSA Types)

LSA タイプ名称説明フラッディング範囲
Type 1Router-LSAルーターリンク状態エリア内
Type 2Network-LSAネットワークリンク状態エリア内
Type 3Summary-LSA (ネットワーク)エリア間ネットワークルート単一エリア
Type 4Summary-LSA (ASBR)ASBR ルート単一エリア
Type 5AS-external-LSA外部ルートAS 全体

2.2 The Shortest-path Tree (最短経路ツリー)​

Dijkstra アルゴリズム (Dijkstra's Algorithm)​

アルゴリズムステップ (Algorithm Steps)

  1. 初期化：自身をルートノードに設定
  2. 候補リスト：処理待ちの頂点リストを維持
  3. 最小コスト頂点を選択
  4. ネイバーコストを更新
  5. すべての頂点が処理されるまで繰り返し

コスト計算 (Cost Calculation)

  • インターフェースコスト：帯域幅または手動設定に基づく
  • パスコスト：パス上のすべてのインターフェースコストの合計
  • デフォルトコスト式：コスト = 参照帯域幅 / インターフェース帯域幅

ツリーの構築 (Tree Construction)

  • ルートノード：計算を実行するルーター
  • 内部ノード：AS 内のルーターとネットワーク
  • リーフノード：外部ルート (AS-external-LSA)

主要用語 (Key Terms)​

用語英語定義
SPF ツリーSPF Treeルーターをルートとする最短経路ツリー
候補リストCandidate Listツリーに追加される予定の頂点
親ノードParentツリー内の前任ノード
距離Distanceルートからノードまでのコスト
ネクストホップNext Hop宛先に到達するための最初のルーター

2.3 Use of External Routing Information (外部ルーティング情報の使用)​

外部ルートタイプ (External Route Types)​

Type 1 外部ルート (Type 1 External)

  • コスト = 内部コスト + 外部コスト
  • 比較可能なメトリック
  • 同一 AS 内の IGP に適用

Type 2 外部ルート (Type 2 External)

  • コスト = 外部コスト（内部コストはタイブレークのみに使用）
  • 比較不可能なメトリック
  • 異なる AS の EGP に適用
  • OSPF のデフォルトタイプ

ASBR (Autonomous System Boundary Router)​

ASBR の役割 (ASBR Role)

  • 外部ルートを OSPF に導入
  • AS-external-LSA を生成
  • 任意の OSPF ルーターが可能
  • Type 4 Summary-LSA でアドバタイズ

ルート再配布 (Route Redistribution)

  • 他のプロトコルからルートをインポート
  • 外部ルートタイプを設定
  • ルートタグを設定 (Route Tag)
  • 転送アドレスを設定 (Forwarding Address)

2.4 Equal-cost Multipath (等コストマルチパス)​

ECMP 概念 (ECMP Concept)​

基本原理 (Basic Principles)

  • 同一宛先への複数の等価パス
  • パスコストが完全に同一
  • トラフィックが複数パス間で分散
  • 帯域幅利用率と冗長性の向上

実装方法 (Implementation Methods)

方法説明利点欠点
パケット単位ラウンドロビンPer-packet round-robinシンプルアウトオブオーダーの可能性
フロー単位分散Per-flow distribution順序維持フロー識別が必要
ハッシュベースHash-based効率的、決定的不均衡の可能性

設定パラメータ (Configuration Parameters)

  • 最大パス数：システムがサポートする最大 ECMP パス数
  • ロードバランシングアルゴリズム：トラフィック分散方法の選択
  • コスト閾値：許容されるコスト差の範囲

ルーティングテーブルエントリ (Routing Table Entries)​

マルチパス表現 (Multipath Representation)

  • 単一の宛先プレフィックス
  • 複数のネクストホップインターフェース
  • 同一のルートコスト
  • 同一のルートタイプ

技術要点まとめ (Technical Summary)​

主要データ構造 (Key Data Structures)​

  1. リンクステートデータベース (LSDB)：すべての LSA を格納
  2. SPF ツリー：最短経路ツリー構造
  3. ルーティングテーブル：最終的な転送テーブル
  4. ネイバーテーブル：隣接ルーター情報

重要アルゴリズム (Important Algorithms)​

  1. Dijkstra SPF：最短経路の計算
  2. LSA フラッディング：リンク状態情報の配布
  3. ルート計算：SPF ツリーからルーティングテーブルを生成
  4. ECMP 選択：マルチパスロードバランシング

パフォーマンス考慮事項 (Performance Considerations)​

  • SPF 計算の複雑度：O(N log N)
  • データベースサイズ：メモリ使用量への影響
  • コンバージェンス時間：トポロジー変更からルート更新まで
  • スケーラビリティ：大規模ネットワークのエリア分割

参考資料 (References)

  • 完全な原文：RFC 2328 Section 2
  • Dijkstra アルゴリズム：E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs"

注意 (Note)：本文書は RFC 2328 公式仕様に基づいています。完全な技術詳細、アルゴリズム擬似コード、および規範的な言語については原文書を参照してください。

に最終更新