ネットワーク層 ─ ルーティング(IGP/EGP・BGP 概要)

学習目標

本講を終えると、以下の問いに学術的な言葉で答えられるようになります。

• ルータがパケットを受け取ってから次ホップへ渡すまでの一連の処理(受信→宛先 IP 確認→ルーティングテーブル参照→次ホップへ転送) を順を追って説明できる
• ルーティングテーブルからの経路選択ルール Longest Prefix Match(最長一致) を、複数の候補プレフィクスから選ぶ具体例で説明できる
• 静的ルーティング と 動的ルーティング の違い、後者が必要な理由(障害復旧・トポロジ変化への自動追従) を述べられる
• 動的ルーティングの3方式 ─ 距離ベクトル型(Distance Vector) / リンクステート型(Link State) / パスベクトル型(Path Vector) の動作原理(Bellman-Ford / Dijkstra / AS パス伝搬) と長所・短所を比較できる
• AS(Autonomous System) の概念、 IGP(域内ルーティング:RIP/OSPF/IS-IS/EIGRP) と EGP(域間ルーティング:BGP-4) の役割分担を説明できる
• BGP-4 の特徴(ポリシーベース、TCP 179 番、ピアリング/トランジット、AS_PATH 属性) を述べ、なぜインターネット全体が「IGP+BGP の二段構え」で動いているのかを理解する
• ルーティングループの発生メカニズムと、その回避策(TTL / Split Horizon / Poison Reverse / ホールドダウン) の概要を説明できる
• BGP の経路ハイジャック・経路リークが、世界規模の通信障害につながる仕組みを直感的に説明できる

このレッスンの目次

ルータの仕事 ─ パケット受信から次ホップへ

ルーティングテーブルの正体

ルータの中には ルーティングテーブル(forwarding table とも呼ぶ) と呼ばれる表があり、各エントリは (宛先プレフィクス, 出力インタフェース, 次ホップ IP, メトリック) といった形をしています。「192.0.2.0/24 宛のパケットは eth1 から、次ホップ 10.0.0.2 へ」のようなルールが多数並んでいると思ってください。

図の見方:上段が データプレーン(1パケットごとに高速処理) 、下段が コントロールプレーン(テーブルを作る処理) 。本講で学ぶ RIP/OSPF/BGP は下段で動き、その結果が上段のテーブルに書き込まれます。

Longest Prefix Match(最長一致) ─ なぜ必要か

同じ宛先 IP に対して、ルーティングテーブルの複数のエントリが「俺が当てはまる」と主張することがよくあります。例えば 192.0.2.130 宛のパケットは、上の表だと 0.0.0.0/0(デフォルト) ・192.0.2.0/24 ・192.0.2.128/25 の3本に一致します。このとき マスク長(プレフィクス長) が最も長い ものを選ぶ ─ それが Longest Prefix Match です。

考えてみよう: 郵便配達でも「東京都」宛のルールと「東京都千代田区」宛のルールがあれば、千代田区行きは後者が優先されるはず。Longest Prefix Match はその「より細かい指示が勝つ」を機械的に行う仕組みです。

静的ルーティングと動的ルーティング

距離ベクトル型(Distance Vector) ─ RIP と Bellman-Ford

Bellman-Ford 式の更新ルール(分散ルーティング版)

各ルータ x は、各宛先 y について次の更新式を回します。

これだけで「ルーティングのアルゴリズム」と紹介されることが多いですが、これは 本来の Bellman-Ford アルゴリズム を分散環境向けに変形した形です。元のアルゴリズムを押さえておくと、なぜこの式で正しく収束するのかが腹落ちします。

本来の Bellman-Ford アルゴリズム(中央集権版)

Bellman-Ford は、教科書的には次のように定義される 単一始点最短路アルゴリズム です。重み付き有向グラフ G = (V, E) と始点 s が与えられたとき、s から各頂点 v までの最短距離 d[v] を計算します。Dijkstra と違い 負の重みも許容 でき、負閉路の検出までできるのが特徴。

擬似コード

function BellmanFord(G, w, s):
    # 1) 初期化
    for each v in V(G):
        d[v]    := infinity
        prev[v] := nil
    d[s] := 0

    # 2) |V|-1 回の緩和パス
    for i := 1 to |V| - 1:
        for each edge (u, v) in E(G):
            if d[v] > d[u] + w(u, v):
                d[v]    := d[u] + w(u, v)
                prev[v] := u

    # 3) 負閉路検出(オプション)
    for each edge (u, v) in E(G):
        if d[v] > d[u] + w(u, v):
            return "negative cycle reachable from s"

    return d, prev

「緩和」は1ステップだけ見るととてもシンプルです。「もし u 経由で行くほうが今知っている経路より安いなら、その値で更新」というだけ。これを |V|-1 回 繰り返すと、すべての頂点に最短距離が確定します。

Bellman-Ford をステップで追う

例として 4 頂点 A, B, C, D の有向グラフを考えます。始点は A。辺は A→B(1)、A→C(4)、B→C(2)、B→D(5)、C→D(1) の順に緩和します。

緩和ごとの更新表

図の見方:Bellman-Ford は「辺を1本見る → その辺を使うと安くなるなら更新」を繰り返します。A→C 直行は 4 ですが、途中で A→B→C が 1+2=3 と分かるので C の値が書き換わります。最後に D も A→B→C→D = 4 へ改善されます。

なぜ |V|-1 回で十分か

最短路は 単純路(同じ頂点を 2 度通らない)なので、含まれる辺の数は最大で |V|-1 本。各イテレーションで「最短路の k 番目までの辺」が確定することが帰納法で示せます。これは Bellman の最適性原理(最短路の部分路もまた最短路)の直接の帰結です。

• 計算量:O(|V| × |E|)。Dijkstra(O((|V|+|E|) log |V|))より遅いが、負の重みを扱える という強み
• 負閉路:|V| 回目の緩和でも更新が起きるなら、グラフに s から到達可能な負閉路がある(最短路は -∞ に発散する)。これを 1 ステップ余分に回すだけで検出できる のが Bellman-Ford の特徴

分散版への変形 ─ なぜルーティングに使えるか

中央集権 Bellman-Ford の前提は「誰か(中央のコンピュータ) がグラフ全体を把握している」こと。インターネットでは誰もそんな場所にいません。そこで、中央のテーブルを 各ルータが自分の行だけ持つ 形に分解します。

中央集権版 → 分散版への対応関係

つながる知識: 分散版では「同期で全員が同時に更新」する保証はありませんが、それでも リンクが安定なら有限時間で収束 する、という嬉しい性質があります(Bertsekas らの非同期反復の理論)。逆に、リンクが頻繁に変動する 環境では収束する前に新しい変動が起き、永久に追いつけない場合がある ─ これが距離ベクトル型の弱点となり、後の リンクステート型(全員が地図を共有) の登場につながります。

RIP の具体仕様

• コスト=ホップ数(経由するルータの数)。各リンクのコストは 1 で固定
• 最大 15 ホップ。16 は「到達不能」を示す番兵値となり、規模が制限される
• 30 秒ごと に経路情報を隣にフラッディング(マルチキャスト 224.0.0.9)
• 180 秒間更新が来なければそのリンクは切断と判断
• 歴史的には小規模 LAN・CPU の弱いルータ時代に普及

収束プロセスをステップで見る

ノード A・B・C が一直線につながり、リンクコストはすべて 1 とします。各ノードが持つのは「各宛先までのコスト」のみ。次/前ボタンで収束過程を1ステップずつ追ってください。

図の見方:各ルータは 隣からの情報だけ をもとに自分の表を更新。「全体の地図」は誰も持っていないが、繰り返し情報交換することで結果として全員の表が一致する(収束する)。

考えてみよう: 日常で例えるなら「自分の知っている最短距離だけを近所の友達に教え合う」ようなもの。誰も全体地図を持っていないのに、繰り返すうちにみんなが正しい距離を知るようになる ─ これが分散アルゴリズムの面白さです。

リンクステート型(Link State) ─ OSPF と Dijkstra

OSPF の動作の流れ

1. Hello パケット(マルチキャスト 224.0.0.5)を 10 秒に1回送り、隣接関係を発見・維持。40 秒応答が無ければリンクダウン判定
2. 確立した隣接関係上で LSA(Link State Advertisement) を交換し、LSDB を同期
3. リンクの状態に変化があった場合のみ、変化を フラッディング で AS 内のすべての OSPF ルータに広報(イベント駆動)
4. 各ルータは LSDB に基づいて Dijkstra 法 を実行し、自身を根とする最短経路木(SPT) を計算 → ルーティングテーブルへ反映

OSPF の特徴

• リンクのコストは任意(管理者が帯域・遅延などに応じて設計可能)。すべて 1 にすればホップ数と一致するが、ふつうは 10⁸/帯域[bps] のような自動設定
• 大規模 AS では「エリア」階層(階層化 OSPF) を導入。バックボーンエリア(area 0) と複数の通常エリアに分け、エリア境界ルータが要約情報のみを交換することで LSDB のサイズと SPF 計算量を抑える
• RIP と比べて収束が早く、ループに陥りにくい(全員が地図を持つので)
• IETF が標準化したオープンプロトコル。多ベンダ環境で広く採用

Dijkstra 法の疑似コード

Dijkstra 法は、始点から各頂点までの「いま分かっている最短距離」を少しずつ確定していくアルゴリズムです。OSPF では、各ルータが LSDB という同じ地図を持ったうえで、自分自身を始点にしてこの計算を行います。

入力:
  G = (V, E)     // ルータを頂点、リンクを辺とする地図
  start          // 自分自身のルータ

初期化:
  for each v in V:
    dist[v] = ∞          // start から v までの最短距離候補
    prev[v] = none       // v へ行く直前の頂点
    fixed[v] = false     // 距離が確定したか
  dist[start] = 0

本体:
  while fixed でない頂点が残っている:
    u = fixed でない頂点のうち dist[u] が最小のもの
    fixed[u] = true      // u までの最短距離を確定

    for each 辺 (u, v, cost) in E:
      if fixed[v] == false and dist[u] + cost < dist[v]:
        dist[v] = dist[u] + cost
        prev[v] = u

出力:
  dist[v] = start から v までの最短コスト
  prev[v] を逆にたどると、最短経路木(SPT)が得られる

ステップで追う: A から最短経路木を作る

次の小さな地図で、A を始点にして Dijkstra 法を実行します。ボタンを押すごとに「確定するノード」と「新しく分かる最短距離」が増えていきます。

Dijkstra 法の更新表

Dijkstra の最短経路木イメージ

図の見方:LSDB という地図がある以上、A は自分を根とした最短経路木を 1度の Dijkstra 計算 で得られる。各宛先の「次ホップ」もこの木を辿るだけで決まる。距離ベクトル型のような繰り返しの噂話は不要。

距離ベクトル型 vs リンクステート型 ─ 比較

AS(自律システム) と IGP/EGP の役割分担

なぜ分けるのか

もし全世界のルータを1つの OSPF で動かそうとしたら、LSDB のサイズと SPF 計算量が爆発し、誰のどんな細かい変化も全世界に届いてしまいます。さらに、企業 X が「うちの経路は競合 Y を経由させたくない」のような 運用ポリシー を表現する手段がありません。そこで「AS の内側 は技術的最適性で(IGP)、AS の外側 はビジネスポリシーで(EGP)」と役割を分けるのです。

図の見方:同じ色の雲(=AS) の中はその組織が好きなように IGP で経路を組み立てる。雲と雲の間は eBGP セッション でつながり、AS 番号と「経由した AS のリスト(AS_PATH) 」だけを交換する。

主な IGP 一覧

BGP-4 ─ インターネットの背骨

BGP メッセージの種類

• OPEN:セッション開始時、AS 番号や保持時間を交換し合意
• UPDATE:経路の追加・撤回(withdraw) を通知。本体の経路情報がここに乗る
• KEEPALIVE:相手生存確認のため定期的に送信
• NOTIFICATION:エラー時にセッションを切断する通知

パスベクトル型のスローガン

距離ベクトル型では「コスト」だけを伝えました。BGP は 「経路全体(経由した AS のリスト) 」を伝える 方式です。これによって、自分の AS 番号がリストに含まれていればすぐに 「ループだ」と検出 でき、距離ベクトル型の弱点(カウント・トゥ・インフィニティ) を構造的に回避します。

図の見方:AS 300 が 192.0.2.0/24 を持っているとき、その経路は AS_PATH を伸ばしながら隣の AS へ伝搬する。AS 50 から見ると「AS 100 → 200 → 300 と辿れば届く」と分かる。リストに自分の AS 番号があれば即座にループ検出できる仕組み。

ピアリングとトランジット ─ ビジネス的な関係

BGP の経路選択は技術的最短性ではなく、これらの商業的関係(LOCAL_PREF 属性で表現) が最優先になります。「最短だが高コストの経路」より「やや遠いが安いピアリング経路」が選ばれることはごく日常的です。

3方式まとめ・ループ回避・経路ハイジャック

RIP / OSPF / BGP の比較

RIP(IGP・距離ベクトル)

• 方式: 距離ベクトル(Bellman-Ford)
• メトリック: ホップ数のみ。最大 15
• 更新: 30 秒ごとの定期フラッディング(マルチキャスト 224.0.0.9)
• 収束: 遅い(数十秒〜数分)。ループ対策に Split Horizon, Poison Reverse, ホールドダウンが必須
• 長所: シンプル・実装が軽い・教育的に分かりやすい
• 短所: 規模に弱い、収束が遅い、ホップ数だけだと帯域差を反映できない
• 使いどころ: 小規模 LAN や演習。実運用では OSPF/IS-IS に置き換えられがち

OSPF(IGP・リンクステート)

• 方式: リンクステート(Dijkstra)
• メトリック: 任意のコスト(帯域から自動算出が一般的)
• 更新: Hello で隣接維持(10 秒)、変化時のみ LSA をフラッディング(マルチキャスト 224.0.0.5)
• 収束: 速い(秒オーダ)。地図共有でループに強い
• 長所: スケール、収束速度、エリア階層化、ベンダ中立
• 短所: LSDB のメモリと SPF 計算 CPU、設定がやや複雑
• 使いどころ: 企業・大学の AS 内部、ISP 内部の主流

BGP-4(EGP・パスベクトル)

• 方式: パスベクトル(AS_PATH を伝搬)
• メトリック: 属性とポリシー(LOCAL_PREF, AS_PATH 長, MED, …)
• 転送: TCP 179 番上で UPDATE / KEEPALIVE / OPEN / NOTIFICATION を送受信
• 収束: 中程度(秒〜分)、ポリシー変更には伝搬待ちが必要
• 長所: 数万 AS 規模、ビジネスポリシーを表現できる、構造的にループ検出可
• 短所: 経路選択が複雑、誤設定が世界に波及しうる、認証が弱い(後述)
• 使いどころ: AS 間ルーティングの事実上の唯一の標準

ルーティングループの問題

2台以上のルータがお互いに「君のほうが宛先に近いね」と判断し合い、パケットが 同じ場所をぐるぐる回り続ける 現象を ルーティングループ と呼びます。発生原因はトポロジ変化時の更新タイミングのずれや、誤設定など多岐にわたります。インターネットでは次の4種の防衛機構を組み合わせて被害を最小化しています。

BGP 経路ハイジャックと経路リーク

BGP は元々 性善説 で設計されており、隣の AS が広告してきた経路を「本物かどうか」を技術的に検証する手段がありませんでした。これが原因で次のような事故が世界規模で起きています(標準編では「歴史的な事例として概要を押さえる」程度で十分です)。

• 経路ハイジャック: 自分の AS のものではないプレフィクスを誤って(あるいは悪意で) 広告し、本来宛先でない場所へトラフィックを引き寄せる現象。著名な事例として2008年の YouTube への到達が一部地域で別 ISP に吸い込まれた事件などが知られる[要確認:具体年・関係 AS は最新の解説で再確認のこと]
• 経路リーク(route leak): 顧客から学んだ経路を本来流すべきでない上流ピアにも広告してしまい、自分の AS が大量のトランジットトラフィックを抱え込んでしまう運用事故。短時間でも世界の一部の到達性が崩れる

つながる知識: BGP は通信工学の問題であると同時に、運用ポリシー・契約・国際関係まで巻き込む社会技術 でもあります。「インターネットは技術と契約の集合体」だと実感できる代表例。

まとめと用語チェック

用語チェック

確認問題