OSPF の SPF 計算とリンクステート同期

リンクステート型が解く問題

OSPF はリンクステート型の IGP です。ルーティングプロトコル（OSPF / BGP） で触れたとおり、距離ベクタ型が「隣の言い値」を信じて距離を積み上げるのに対し、リンクステート型は 全ルータが同一のトポロジ地図を共有し、各自がその地図から最短経路を計算する という思想に立ちます。地図さえ一致していれば、各ルータの計算結果は矛盾せず、ループや無限カウント問題を構造的に避けられます。

OSPF の動作は大きく2段に分かれます。前半が リンクステート同期（全員の地図を一致させる）、後半が SPF 計算（その地図から経路木を作る）。この2段を分けて理解するのが要点です。

LSA のフラッディングと LSDB 同期

各ルータは自分のリンク状態を LSA（Link State Advertisement） として記述し、これを隣接全体へ氾濫（フラッディング）させます。受け取ったルータは内容を LSDB（Link State Database） に格納し、自分が受信していないインターフェース側へ再送出する。こうして1つの LSA がエリア全体へ波及し、最終的に エリア内の全ルータの LSDB が同一になる（同期する）ことを目指します。

無秩序な再送出はループするため、OSPF は LSA ごとに シーケンス番号・Age（経過時間）・チェックサム を持たせ、新旧を判定します。

隣接間で LSDB をすり合わせる際は、まず DBD（Database Description） でヘッダ一覧を交換して差分を洗い出し、足りない分だけを LSR（Link State Request）→ LSU（Link State Update） で要求・受領します。受領した LSA には必ず LSAck を返し、信頼性のある氾濫を保証します。全データを毎回送らず差分同期する点が、規模に対する効率の鍵です。

ダイクストラ法による SPF ツリー構築

LSDB が揃うと、各ルータは 自分自身を根（ルート） としてダイクストラ法を走らせ、各宛先までの最短経路木（SPF ツリー）を作ります。エッジの重みは各リンクの コスト（既定では参照帯域 / 帯域で算出される非負値）です。非負である点がダイクストラ適用の前提を満たします。

# 各ルータがローカルに実行（root = 自分）
dist[root] = 0、その他は無限大
候補集合（tentative）に root を投入
while 候補が空でない:
    u = 候補から dist 最小のノードを取り出す  # ここで u が確定（PATHへ）
    for each (u, v, cost) を LSDB から参照:
        if dist[u] + cost < dist[v]:
            dist[v] = dist[u] + cost          # 緩和
            next_hop[v] = root から u 方向の第一ホップを継承

確定したノードへの第一ホップが、そのままルーティングテーブルのネクストホップになります。重要なのは、全ルータが同じ LSDB を入力にしながら、根だけが異なる SPF を各自で解く こと。入力（地図）が一致しているので、各ルータの経路は互いに整合し、転送ループが生じません。これがリンクステート型の正しさの根拠です。

エリア分割が SPF をスケールさせる

ネットワークが大きくなると、LSDB も SPF の計算量も膨らみます。OSPF は エリア で網を分割し、LSA の氾濫範囲と SPF 再計算の範囲を1エリア内に閉じ込めます。あるエリアでリンクが揺れても、その Type1/2 LSA は他エリアへ出ないため、他エリアのルータは SPF を再計算しません。これがエリア分割の本質的な利得です。

全エリアは中枢の バックボーン（エリア0） に接続し、エリア間トラフィックは必ずエリア0を通ります。エリアの境界に立つのが ABR（Area Border Router）、外部ドメイン（他プロトコルや別 AS）との境界が ASBR（AS Boundary Router） です。

LSA タイプの内部動作

エリアをまたぐと、詳細トポロジはそのまま運ばれず、ABR で 経路情報（プレフィックスとコスト）へ要約 されます。「他エリアの中身は見えないが、そこへ何コストで届くかは分かる」状態を作ることで、エリア外の SPF 計算から詳細を切り離します。主な LSA タイプは次のとおりです。

Type1 と Type2 が 詳細トポロジ（ダイクストラの入力グラフそのもの）で、エリア内に閉じます。Type3 以降は 要約された経路 であり、受信側はこれをグラフのノードとして扱わず、最終的な距離計算に足し込む形で使います。つまり SPF の「グラフ探索」はエリア内のトポロジ（Type1/2）に対してだけ行われ、エリア間（Type3/4）や外部（Type5）はツリーの末端へコストを加算する という二層構造になっています。

全体像を一段で

OSPF は「地図を完全に一致させ（フラッディングによる LSDB 同期）、各自が同じ地図から自分中心の最短経路木を解く（ダイクストラ法）」プロトコルです。一致した地図を前提とするからループに強く、その代償として全員へ地図を配り続けるコストが生じます。エリア分割と LSA タイプは、この「配る範囲」と「計算する範囲」を局所化し、規模に耐えさせるための仕組みです。挙動の確認は show ip ospf database（LSDB）や show ip route ospf（SPF 結果）で行い、同じ AS 内でもエリア間ポリシーは BGP の経路選択とは別レイヤで決まる点を意識すると、設計の責務が切り分けられます。