コンピューターサイエンス：アルゴリズム / OS / ネットワーク / DB
ルーティングと経路選択
ルーティングと経路選択
このレッスンで分かること
- ルーターはルーティングテーブルを参照し、宛先 IP に対して最長プレフィックスマッチで経路を決めます
- 家庭ネットワークは基本「デフォルトゲートウェイに全部投げる」だけで動きます
- 大規模ネットワークでは OSPF (AS 内)、BGP (AS 間) などの動的ルーティングプロトコルが裏で動いています
ルーティングと経路選択 とは
ルーターがパケットの次の宛先を決めるアルゴリズムを学びます。本レッスンでは、ルーティングと経路選択 の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
ルーティングとは (要約)
ルーターが「次にどのルーターへパケットを渡すか」を決める仕組み。 ルーティングテーブル を 最長プレフィックスマッチ で引き、合致したエントリの ネクストホップ に転送します。
主要ルーティングプロトコル比較
| プロトコル | 適用範囲 | コスト指標 | 特徴 |
|---|---|---|---|
| RIP | 小規模 AS 内 (IGP) | ホップ数 | 最大 15 ホップ、現代では限定的 |
| OSPF | 中-大規模 AS 内 (IGP) | 帯域コスト | リンクステート方式、収束が速い |
| IS-IS | 大規模 AS 内 (IGP) | メトリック | ISP バックボーンで採用 |
| BGP | AS 間 (EGP) | パス属性 + ポリシー | インターネット全体の経路を構成 |
traceroute で実経路を確認できます。* が連続する場合は、ICMP を遮断するルーターに当たっていることがほとんどです。
このレッスンで学ぶこと
ルーターがどうやって「次にどこへパケットを送るか」を決めているのか、ルーティングテーブルとルーティングプロトコルを学びます。
ルーティングテーブル
ルーターはルーティングテーブルという表を持っており、これを参照して経路を決めます。各エントリは下記の情報を持ちます。
- 宛先ネットワーク (CIDR)
- ネクストホップ (次に渡すべきルーターの IP)
- 出力インターフェース (どのポートから出すか)
- メトリック (経路のコスト)
PC が 8.8.8.8 に ping を打つと、ルーターはルーティングテーブル内で宛先 IP に合致する全エントリを洗い出し、最長マッチ (longest prefix match) の原則で最もプレフィックスが長い（最も具体的な）エントリを選びます。マッチはエントリの登録順や格納順に依存しません。
プレーンテキスト
0.0.0.0/0 via 203.0.113.1 (デフォルトルート)
10.0.0.0/8 via 10.0.0.1
192.168.1.0/24 directly connected (eth0)たとえば宛先が 10.5.0.1 なら 10.0.0.0/8 にマッチします。マッチしなければ 0.0.0.0/0 のデフォルトルートが使われます。
デフォルトゲートウェイ
家の PC の場合、ほとんどの通信先がインターネット上のサーバーなので、ルーティングテーブルは「家のルーター (= デフォルトゲートウェイ) に全部投げる」というシンプルな構成です。
プレーンテキスト
default via 192.168.1.1 dev eth0PC は宛先 IP が自分のサブネット内 (192.168.1.0/24) なら直接スイッチに送り、そうでなければデフォルトゲートウェイ (家のルーター) に送ります。家のルーターがそこからプロバイダに、プロバイダがコアルーターに、と次々と中継していきます。
静的ルーティングと動的ルーティング
ルーティングテーブルの更新方法には 2 種類あります。
- 静的ルーティング — 管理者が手動でテーブルを設定する。小規模ネットワーク向け。設定は楽だが、経路障害時に手動切り替えが必要。
- 動的ルーティング — ルーター同士でルーティングプロトコルを使ってテーブルを自動交換する。大規模ネットワーク必須。障害時に自動迂回。
家のルーターは静的ルーティングだけで動きますが、インターネット全体は動的ルーティングなしには成立しません。
代表的なルーティングプロトコル
- RIP (Routing Information Protocol) — ホップ数 (経由ルーター数) でコストを判断する古典的プロトコル。最大 15 ホップ。
- OSPF (Open Shortest Path First) — 帯域幅などをコスト化して最短経路を計算する。組織内 (AS 内) で広く使われる。
- BGP (Border Gateway Protocol) — 組織と組織 (AS 間) を接続する大規模プロトコル。インターネット全体の経路はこれで決まる。
BGP のスケール感
インターネット全体には現在 100 万件以上のグローバル経路が存在し、各バックボーンルーターはそれをすべて保持しています。BGP は単純な「最短経路」ではなく、政治的・経済的なポリシー (どの ISP を優先するかなど) も含めた経路選択を可能にする独特のプロトコルです。
ルーティングの障害事例
BGP は信頼ベースで動いており、AS 間で「私はこの経路を持っている」と互いに広告し合います。誤った広告をしてしまうと、世界中のトラフィックが意図せず一箇所に集中する事故が起きます。これが BGP ハイジャックと呼ばれるインターネット規模の障害です。
実際に誤ったBGP広告による大規模障害は何度も起きており（2008年のPakistan TelecomによるYouTubeの経路乗っ取りなど）、ルーティングの信頼性は今もインターネットの大きな課題です。
traceroute で経路を見る
実際の経路は traceroute コマンドで確認できます。
プレーンテキスト
$ traceroute noimancode.com
1 192.168.1.1 1.234 ms
2 203.0.113.1 8.765 ms
3 10.10.10.1 9.111 ms
...
12 noimancode.com 35.678 ms各行が 1 ホップで、宛先まで何台のルーターを経由しているかが分かります。「特定の地域だけ遅い」「途中で止まる」などの障害切り分けに重宝します。
まとめ
このレッスンの要点は、ルーティングテーブル / 静的 vs 動的 / RIP・OSPF・BGP の使い分け の 3 点です。実務でこれらを切り分けて説明できるようになると、設計レビューや障害対応の精度が一段上がります。
理解度チェック
Q. ルーティングテーブルで複数のエントリが宛先に合致したとき、どのルールで選ばれる？
- 最初に登録されたエントリ
- メトリックが最大のエントリ
- 最長プレフィックスマッチ (最も具体的なエントリ)
- 最短プレフィックスマッチ (最も一般的なエントリ)
答えを見る
正解は 3。より具体的な (= プレフィックスが長い) エントリが優先されます。たとえば 10.0.0.0/8 と 10.0.0.0/24 の両方に合致する場合、/24 のほうが選ばれます。
出典 (References)
最終更新: 2026-05-28
関連レッスン
よくある質問
Q. このトピックは実務でどう役立ちますか？
A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。
Q. 計算量はどう求めれば良いですか？
A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。
Q. 覚えるべき定番アルゴリズムは何ですか？
A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。
次のレッスン
次は ファイアウォール基礎 で、ルーターがパケットの次の宛先を決めるアルゴリズムを学びます を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- ルーティング の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. ルーティング とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
復習ミニクイズ
インターネット全体の AS 間ルーティングで使われるプロトコルはどれですか